Improve cube GiST page splits
Hackorum builds and tests every patch posted to the lists, not only commitfest submissions. This is Hackorum's own CI rather than the PostgreSQL project's, and it is still under testing - please report anything that looks wrong.
You can run a PostgreSQL built from this patch straight from Docker, with no checkout and no build:
docker run --rm -p 5432:5432 ghcr.io/hackorum-dev/postgres-patch:t253360psql -h localhost -U postgresBuilt from patchset v1 (message #1), August 23, 2026 at 01:46 PM.
Every patchset is also pushed to a branch of our PostgreSQL fork, so you can check out the same tree CI built. Without a PostgreSQL checkout:
git clone --branch t253360_1 https://github.com/hackorum-dev/postgres.gitIn a checkout you already have, add the fork once:
git remote add hackorum https://github.com/hackorum-dev/postgres.gitthen, for this patchset and every later one:
git fetch hackorum t253360_1 && git checkout t253360_1Patchset v1 (message #1) is on t253360_1
Hi,
In 2016 I noticed that cube's Guttman polynomial split can produce
very unbalanced GiST trees [0]/messages/by-id/CAJEAwVEVq9Ry7KxApHbFTB67E0ntn2EBTQiUXBG=q5E4P7w1VQ@mail.gmail.com, 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]: /messages/by-id/CAJEAwVEVq9Ry7KxApHbFTB67E0ntn2EBTQiUXBG=q5E4P7w1VQ@mail.gmail.com