On Sat, Oct 31, 2015 at 9:49 PM, Alexander Lebedev <a.lebe...@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. > > Did you forget to show us performance numbers ? > > > -- > Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) > To make changes to your subscription: > http://www.postgresql.org/mailpref/pgsql-hackers > >
