Hi,
In 2016 I noticed that cube's Guttman polynomial split can produce
very unbalanced GiST trees [0], but never got around to fixing it. The
problem is a bit dramatic for sorted input: repeated splits make
insertion quadratic and produce an enormous index.
For example, I inserted sorted two-dimensional points with an O2 build
without assertions. These are medians of three runs:
rows | master time | patched time | master pages | patched pages
------+-------------+--------------+--------------+--------------
1000 | 5.91 s | 0.0119 s | 1757 | 9
2000 | 24.74 s | 0.0150 s | 7929 | 18
4000 | 110.63 s | 0.0219 s | 33712 | 36
The workload was:
CREATE TABLE t (id int, c cube);
CREATE INDEX ON t USING gist (c);
INSERT INTO t
SELECT g, cube(ARRAY[g::float8 / 4000, g::float8 / 4000 + 1])
FROM generate_series(1, 4000) g;
The patch generalizes the double-sorting split used by the built-in box
and point GiST operator classes to arbitrary cube dimensionality. The
first patch adds regression coverage. The second implements the new
split.
PFA the patch set.
Best regards, Andrey Borodin
[0] https://www.postgresql.org/message-id/CAJEAwVEVq9Ry7KxApHbFTB67E0ntn2EBTQiUXBG%3Dq5E4P7w1VQ%40mail.gmail.com
