sumeer

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.

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.

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