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.
