Re: SP-GiST failing to complete SP-GiST index build

On Sun, May 27, 2018 at 5:10 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Instrumenting the test case suggests that getQuadrant pretty much always
> returns 1, resulting in a worst-case unbalanced SPGiST tree.  I think this
> is related to the fact that the test case inserts the values in increasing
> order, so that new values are always greater than existing values in the
> index.

I suspected the same. It reminded me of the weird behavior that the
Postgres qsort() sometimes exhibits.

> SPGiST is unable to rebalance its tree on the fly, so it's pretty
> well screwed in this situation.  It does finish eventually, but in about
> 50x longer than GiST.  I imagine the index's query performance would be
> equally awful.

Can you think of some way of side-stepping the issue? It's unfortunate
that SP-GiST is potentially so sensitive to input order.

-- 
Peter Geoghegan