SpaceCurve: A Unique and Fast Geospatial Database

As a caveat, the VMware image is really for demoing basic functionality. It is a true parallel-distributed database engine, and is not designed to run as a tiny local instance. The VMware instance is a custom build that disables a bunch of things mooted by being non-distributed and to be reasonably well-behaved on a system small enough that almost any GIS database would likely work.

I spent a few years designing new parallel algorithms on a number of supercomputing architectures that I enjoyed immensely, mixed in with my usual database work. I learned a tremendous amount about software design and optimization I probably would have not learned otherwise. There is a lot of knowledge in HPC that tends not to travel beyond that domain. It gave me the "assume you have a million cores..." mindset when thinking about algorithms and data structures.

In fact, debugging an HPC code on a Cray machine late one night, staring at large dumps of binary coded hyper-rectangles, was where I first noticed the deep bit-wise patterns in some types of spatial representations that SpaceCurve now exploits. It allows computation on hyper-rectangle primitives to be nearly as fast as integer primitives on ordinary silicon, which was not the case with earlier versions of my work.

Common misconception. It is not related to space-filling curves. Space-filling curves are for linearizing points but have limited utility for interval data types. Technically though, all binary space decompositions can be described in terms of space-filling curves. However, for most kinds of space decomposition it is a mistake to use something describable on a fixed curve (e.g. Hilbert); the curve definitions are dynamically constructed and expressed in terms of a simple algebra. In extremely adaptive representations that squeeze as much information theoretic locality as possible out of the data model, those expressions can be pretty long but from a software standpoint you only need to reason about a local fragment of the expression at any point in the processing.

In SpaceCurve, all points are represented as hyper-rectangles. Literally everything is a hyper-rectangle. It is the most unusual part of the whole thing. There is no linearization on a space-filling curve.

I'd imagine so - space filling curves are good for indexing multidimensional data like geospatial information, so the name is pretty telling.

Specifically, the linked paper models indexes on a table as sets of n-dimensional volumes showing where rows aren't. It then gives a join algorithm that is asymptotically instance-optimal (up to a poly-log factor) ie better than any previous result.

Unfortunately it relies on efficiently representing and querying the set of volumes built up during the query process and the data structure used in the paper is ridiculously impractical. I haven't seen an implementation yet that managed to tame the constant factors. Perhaps seeing how the OP models volumes/constraints would help.

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.

Please don't post dismissive comments to HN.

The OP may not answer every question but this is obviously serious work, so it deserves a fair treatment, not a glib dismissal—especially since the people working on it are here answering questions. This is deeply interesting stuff and there's no excuse for unsubstantive discussion.

I was lead architect at SimpleGeo and spent most of the time working on our distributed geospatial database. I haven't looked at the MongoDB implementation in years, but at that time it was really a toy compared to what other people were doing. Basically, they used a space-filling curve to do dimensionality reduction and then stored geospatial data in the same b-tree index that they use for everything else. It's suitable for a lot of trivial use cases at scale, and even for non-trivial use cases at low data/throughput scale. But the architecture was (too lazy to determine if it still is) not suitable for large data set sizes, query throughput, or distribution for fault tolerance / improved locality, etc.

At the time it was really frustrating to here comments like yours since the MongoDB solution was superficially similar to the consumer, but was basically worse on every measurable dimension if you knew what you were doing. I hadn't heard of SpaceCurve before today, but I skimmed the linked article and some other stuff on the blog and it looks like this guy knows what he's talking about. My guess is it's a much better geospatial architecture than MongoDB's.