|From:||Oleg Bartunov <obartunov(at)gmail(dot)com>|
|To:||Alexander Lebedev <a(dot)lebedev(at)postgrespro(dot)ru>|
|Cc:||Pgsql Hackers <pgsql-hackers(at)postgresql(dot)org>|
|Subject:||Re: [PATCH] we have added support for box type in SP-GiST index|
|Views:||Raw Message | Whole Thread | Download mbox|
On Sat, Oct 31, 2015 at 9:49 PM, Alexander Lebedev <a(dot)lebedev(at)postgrespro(dot)ru
> 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:
|Next Message||Amit Kapila||2015-11-01 06:11:43||Re: ParallelContexts can get confused about which worker is which|
|Previous Message||Noah Misch||2015-10-31 21:02:46||Re: September 2015 Commitfest|