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

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
Date: 2015-10-31 21:15:40
Views: Raw Message | Whole Thread | Download mbox
Lists: pgsql-hackers

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:

In response to


Browse pgsql-hackers by date

  From Date Subject
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