[postgis-devel] Multi-D Indexing and Serialized Form

[Paul Ramsey]

For my "geography" work, I am trying to ensure that what I do either
uses existing liblwgeom hooks, or creates new things that liblwgeom2
could use. I'll be doing indexing as a 3-space index, and that works
OK for geography, things are static:

bbox dims = 3
coordinate dims = 2

However, for geometry, we were thinking about adding multidimensional
indexing. Right now we have a situation like this for geometry:

bbox dims = 2
coordinate dims = 2/3/4

No problem, because we only calculate a 2d box, no matter what our
dimensionality. But when we add the possibility of multi-dimensional
indexes, we get in a bind. How many dimensions of bbox should we
calculate? We need enough to support the index, but we don't know what
the dimensionality of the index using the bbox will be. That leaves us
forced to calculate the full multi-dimensional bbox even if we only
want a 2-d index. We also could end up with some interesting problems,
for example, returning results from a 4d index given a 2d query bbox.

The straightest line solution, IMO, is to just create a bbox with
enough dimensionality to handle the coordinates. So we'll end up with

coordinate dims = 2 => bbox dims = 2
coordinate dims = 3 => bbox dims = 3
coordinate dims = 4 => bbox dims = 4

For 2-vertex 3d points that you only want a 2d index on (the worst
case, since we don't put boxes on points), that implies a storage
overhead of about 10%.

P.