How we built scalable spatial indexing in CockroachDB | Hacker News Reader

How we built scalable spatial indexing in CockroachDB

cockroachlabs.com

153 pointsorangechairs29 comments

Blog post author here -- happy to answer any questions about the article.

What can it do that Citus can't while being less compatible with postgres?

Hi there! I have a question:

In the article you demonstrate how quad-trees are used for indexing spatial data, but does Cockroach DB do this in 3D as well (i.e. octree)?

I was fairly interested in PG Pointcloud [1] back when I was in grad school, but storing arbitrary 3D information seemed to present unique challenges in this space (especially with regards to indexing). Would the approach used here extend to 3D? I don't know if I see a clear reason it wouldn't, but I was wondering if there's anything in Cockroach that might make that extension difficult. I recognize you're using the S2 library here as well, which doesn't seem to have all the 3D primitives, but I'd be interested to hear your thoughts!

[1] https://github.com/pgpointcloud/pointcloud

CockroachDB does not yet support 3D shapes or indexing. We've discussed extending it to 3D, and you are correct that S2 does not support 3D. S2 was a very convenient starting point for us, but we use a small subset of it, for computing the covering. It is viable to replace that part and consider a decomposition of 3D space.

We would probably need more than 64 bits for the cell-IDs, which is fine given that the IDs are being stored in the inverted index. And since we only represent the actual cells that are populated, it would likely not effect the index size. The main performance challenge is that as the trees get deeper, the number of ancestors one has to search increases -- unlike subtrees, which can be searched with a single range lookup regardless of depth, the ancestors are not in a single range. This can slow down queries even if most of the ancestor space is empty. We have some ideas to prune this search.

I am not familiar with PG Pointcloud. Thanks for the link.

Not an expert, but curious if space-filling curves (like Peano curves) [0] can be used to convert 3D to 2D representations and then the current cdb API/architecture can be used as-is?

[0] https://en.m.wikipedia.org/wiki/Space-filling_curve

Yes, we would probably use a space-filling curve to convert from 3D, just like the current scheme uses a Hilbert curve from 2D.

There are some practical performance challenges when the (sparse) tree gets deeper, as I mentioned in my previous response.

I've used both approaches, GiST in PG and S2 in Mongo, and I feel that S2 has given me more tools to do queries like "which polygons contain this single point?" efficiently in my use case.

Smart!

Reply on news.ycombinator.com