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
0001-Add-regression-coverage-for-cube-GiST-page-splits.patch
Description: Binary data
0002-Use-double-sorting-for-cube-GiST-page-splits.patch
Description: Binary data
