Re: [PATCH] we have added support for box type in SP-GiST index

> On 22 Mar 2016, at 01:47, Jim Nasby <Jim(dot)Nasby(at)BlueTreble(dot)com> wrote:
>
> On 3/21/16 11:57 AM, Teodor Sigaev wrote:
>> A and B are points of intersection of lines. So, box PBCAis a bounding
>> box for points contained in 3-rd (see labeling above). For example X
>> labeled point is not a descendace of child node with centroid C because
>> it must be in branch of 1-st quad of parent node. So, each node (except
>> root) will have a limitation in its quadrant. To transfer that
>> limitation the traversalValue is used.
>
> Isn't this basically the same thing that the cube contrib module does? (Which has the added benefit of kNN-capable operators).

Cube and postgres own geometric types are indexed by building R-tree. While this is one of the most popular solutions it
degrades almost to linear search when bounding boxes for each index node overlaps a lot. This problem will arise when one will
try to index streets in the city with grid system — a lot of street's bounding boxes will just coincide with bounding box for whole city.

But that patch use totally different strategy for building index and do not suffer from above problem.

>
> If that's true then ISTM it'd be better to work on pulling cube's features into box?
>
> If it's not true, I'm still wondering if there's enough commonality here that we should pull cube into core…

There is also intarray module with very common functionality, but it also addressing different data pattern.

Optimal indexing and kNN strategy are very sensible to the data itself and if we want some general multidimensional search routines,
then I think none of the mentioned extensions is general enough. Cube barely applicable when dimensions number is higher than 10-20,
intarray performs bad on data with big sets of possible coordinates, this patch is also intended to help with specific, niche problem.

While people tends to use machine learning and regressions models more and more it is interesting to have some general n-dim indexing with kNN,
but I think it is different problem and should be solved in a different way.

Stas Kelvich
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company