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.lebedev@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.

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