On Sat, Oct 31, 2015 at 9:49 PM, Alexander Lebedev <a.lebe...@postgrespro.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@postgresql.org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-hackers
>
>

Reply via email to