search

attic-labs / noms

The versioned, forkable, syncable database
Apache License 2.0
7.44k stars 266 forks source link

Any chance to add spatial datatypes? #3871

Open palmerj opened 4 years ago

palmerj commented 4 years ago

Something like https://postgis.net/docs/using_postgis_dbmanagement.html#RefObject

I see https://github.com/attic-labs/noms/blob/master/doc/intro.md#types which makes me think that add a Geometry spatial datatype (POINTS, LINESTRINGS, POLYGONS) which indexing might not be possible.

aboodman commented 4 years ago

It's trivial to define any types you want using Noms structs. But it seems like what you'd want from this support is the ability to search (efficiently).

We experimented with implementing quadtrees in Noms waaaay back when. I don't think any of the code would be useful. But I think you could implement quadtrees relatively efficiently on top of prolly trees. Which is to say you ought to be able to build an efficient geoindex in Noms.

There's nothing built-in though.

palmerj commented 4 years ago

Thanks for the reply.

Great news about quadtrees, however they tend to need tuning parameters with spatial distributions. Would it also be easy enough to implement a good performing r-tree index on top of prolly trees?

aboodman commented 4 years ago

I'm not an expert (or even a novice) at spatial searching, but ... reviewing r-trees:

On the one hand, sure it seems like you could implement an r-tree out of the more primitive Noms data structures like maps and sets.

On the other hand, r-trees appear to be history-dependent. Noms' primitive data structures are history-independent, and this is an important invariant.

Thus you'd want to think carefully about what it would mean to model r-trees directly in Noms. I guess at a simple level, it would make diff a lot less useful, and merge would be harder to reason about. Depending on your application, maybe this is ok.

But it would fit with the spirit of Noms better to use a data structure that is history independent. This would preserve the benefits of all the rest of the features and tools. Prolly trees are a pretty obvious tweak to b-trees to make them history independent. I wonder if there is a similar tweak to r-trees.