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

From: Alexander Lebedev <a(dot)lebedev(at)postgrespro(dot)ru>
To: pgsql-hackers(at)postgresql(dot)org
Subject: [PATCH] we have added support for box type in SP-GiST index
Date: 2015-10-31 20:49:54
Message-ID: 56352972.9020608@postgrespro.ru
Views: Raw Message | Whole Thread | Download mbox
Thread:
Lists: pgsql-hackers

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.

Attachment Content-Type Size
traversalValue.patch text/plain 6.4 KB
q4d.patch text/plain 31.8 KB
range.patch text/plain 2.5 KB

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Noah Misch 2015-10-31 21:02:46 Re: September 2015 Commitfest
Previous Message Peter Geoghegan 2015-10-31 19:42:08 Minor clarifying changes to abbreviated key abort code comments