Re: SP-GiST for ranges based on 2d-mapping and quad-tree

On Thu, 2012-06-14 at 02:56 +0400, Alexander Korotkov wrote:
> Hackers,
>
>
> attached patch implements quad-tree on ranges. Some performance
> results in comparison with current GiST indexing.
> Index creation is slightly slower. Probably, it need some
> investigation. Search queries on SP-GiST use much more pages. However
> this comparison can be not really correct, because SP-GiST can pin
> same buffer several times during one scan. In CPU search queries on
> SP-GiST seems to be slightly faster. Dramatical difference in "column
> <@ const" query is thanks to 2d-mapping.
>
Looking at this patch now. I see that it fails the opr_sanity test (on
master), can you look into that?

It looks very promising from a performance standpoint. I think the "col
<@ const" query will be a common query; and I also think that pattern
will be useful to restrict a large table down to something more
manageable.

In the bounds_connected function, it might make more sense to use the
word "adjacent" which I already used for ordinary ranges, rather than
using the new word "connected".

Also, I'm getting a little confused switching between thinking in terms
of "X and Y" and "lower and upper" (particularly since lower and upper
can be confused with > or <). I don't have a suggestion yet how to
clarify that, but it might be good to use the spatial terminology in
more places and avoid lower/upper except where needed.

Please excuse the slow review, I'm catching up on the SP-GiST API.

Regards,
Jeff Davis