SP-GiST failing to complete SP-GiST index build

Hi,

While preparing for an upcoming presentation, I was playing around
with SP-GiST indexes on tstz ranges and was having an issue where
some would fail to build to completion in a reasonable time, especially
compared to corresponding GiST builds.

Version:

PostgreSQL 10.4 on x86_64-apple-darwin16.7.0,
compiled by Apple LLVM version 9.0.0 (clang-900.0.39.2), 64-bit

Relevant Config:

shared_buffers = 1GB
work_mem = 64MB
maintenance_work_mem = 1GB

System was not under unusual load.

I thought perhaps it was a result of my data being relatively sparse,
but then I had an issue getting one scenario to build where the data
was much more common use case. I wanted to run this scenario
by just to ensure there are no bugs, as the “common case” was working
fine for me.

First, see “good.sql” for a base case: 1.2MM rows “densely” clustered
rows inserted, both GiST and SP-GiST index build in reasonable time
periods (< 15s on my machine).

Next, see bad.sql. 1.2MM sparsely clustered rows inserted, GiST indexes
builds in about 30s on my machine. SP-GiST does not build at all, or at
least I have been composing this email for about 10 minutes since I kicked
off my latest and it has yet to terminate.

I can understand this being an extreme case for SP-GiST as it’s better
for data set that’s more densely clustered, but I wanted to provide
this info to rule out whether or not this is a bug.

Thanks,

Jonathan