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

On Sat, Oct 31, 2015 at 9:49 PM, Alexander Lebedev <a(dot)lebedev(at)postgrespro(dot)ru
> wrote:

> Hello, Hacker.
>
> * [PATCH] add a box index to sp-gist
>
> We have extended sp-gist with an index that keeps track of boxes
>
> We have used ideas underlying sp-gist range implementation to
> represent 2D boxes as points in 4D space. We use quad tree
> analogue, but in 4-dimensional space. We call this tree q4d. Each
> node of this tree is a box (a point in 4D space) which splits space
> in 16 hyperrectangles.
>
> Rationale: r-tree assumes that boxes we're trying to index don't
> overlap much. When this assumption fails, r-tree performs badly,
> while our proposal to represent a rectangle as a point in 4D space
> solves this problem.
>
> NB: the index uses traversalValue introduced in a separate patch.
>
> * [PATCH] add traversalValue in sp-gist
>
> During implementation of box index for sp-gist we saw that we only
> keep rectangles, but to determine traversal direction we may need
> to know boundaries of a hyperrectangle. So we calculate them
> on the fly and store them in traversalValue, available
> when traversing child nodes, because otherwise we would't be able to
> calculate them from inside the inner_consistent function call.
>
> This patch was written by Teodor Sigaev.
>
> * [PATCH] change reconstructValue -> traversalValue in range_spgist.c
>
> During traversal, local context is
> insufficient to pick traversal direction. As of now, this is worked
> around with the help of reconstructValue. reconstructValue only
> stores data of the same type as a tree node, that is, a range.
>
> We have written a patch that calculates auxillary values and makes
> them accessible during traversal.
>
> We then use traversalValue in a new box index and change
> range_spgist.c to use it in place of reconstructValue.
>
> NB: apply this patch after traversalValue patch.
>
>
Did you forget to show us performance numbers ?

>
>
> --
> Sent via pgsql-hackers mailing list (pgsql-hackers(at)postgresql(dot)org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-hackers
>
>