Hacker News Reader

Comment by DennisP | Hacker News Reader

> Second, the database is built on discrete topology internals, not ordered sets, which is more efficient for massively parallelizing most database operations, notably geospatial and join operations...relational databases could be designed with similar characteristics.

Anybody know how a relational join algorithm like this would work?

View on HN

Yes. The closest analogy is a distributed hash join, though it is more general than just equi-joins. In a distributed hash join, there is a hashing stage that reorganizes the data to improve locality and selectivity before the actual join stage. For topological representations, there is information theoretic locality inherent in the sharding organization but the underlying "shape" of two tables may look very different such that there is no direct mapping of records between the two. Fortunately, there is a trivially constructible and very fast transform function on shard definition (which is just a constraint) that allows it to directly map to constraints (shards) in different data models without moving any data. In effect, it is as though the table is already been hash distributed for whatever join you want to run.

The capability of these generalized parallel ad hoc join algorithms where demonstrated on a supercomputer circa 2009.

> The capability of these generalized parallel ad hoc join algorithms where demonstrated on a supercomputer circa 2009.

Is this external work? If so, do you have any pointers to it?

It is easy to forget that in 2009 even MapReduce was still considered exotic. Particularly back then, this was far in front of what most people were thinking about.

The only people at the time that immediately grokked the broad implications and had a deep interest in the theory behind it were computer science researchers at certain government agencies. Hence why so much of the early computer science was verified on supercomputers instead of commodity clusters. Unlike today, you could not rent a cluster for this type of thing back then.

None of the early research produced public results.

Reply on news.ycombinator.com