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), October 23, 2026 at 08:15 AM.
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
Attachments:
t253360_10001-Add-regression-coverage-for-cube-GiST-page-splits.patchapplication/octet-stream; name=0001-Add-regression-coverage-for-cube-GiST-page-splits.patch; x-unix-mode=0644Download+68-6
0002-Use-double-sorting-for-cube-GiST-page-splits.patchapplication/octet-stream; name=0002-Use-double-sorting-for-cube-GiST-page-splits.patch; x-unix-mode=0644Download+430-117
The following review has been posted through the commitfest application:
make installcheck-world: tested, passed
Implements feature: tested, failed
Spec compliant: tested, passed
Documentation: tested, passed
Hi Andrey,
I tested 0001+0002 on master (3c5d9d9). contrib/cube's regression
tests pass. I also compared index scans with seq scans for &&, @>, <@,
= and <-> on random cubes with finite coordinates. With 1, 2, 3 or 7
dimensions per table, they agree on both master and the patch.
The split quality looks good too. At 20k rows the patched index is
never worse than master (cassert, -O0 builds):
pages buffers/query
rand3d_points 205 -> 180 21.1 -> 18.6
rand2d_boxes 240 -> 217 42.2 -> 41.1
rand16d_points 757 -> 621 412.9 -> 322.1
long_stripes 232 -> 223 103.7 -> 103.4
cross_stripes 930 -> 235 140.3 -> 115.9
many_dups2d 310 -> 152 15.5 -> 13.3
mixed_dims 3193 -> 148 45.9 -> 17.1
clustered2d 169 -> 144 16.3 -> 13.6
However, I found two cases where data that master accepts now makes
the page split fail with an ERROR.
1. NaN coordinates: "division by zero"
create table n (c cube);
create index on n using gist (c);
insert into n select cube(array[case when g % 2 = 1
then 'NaN'::float8 else g end])
from generate_series(1, 300) g;
master: INSERT 0 300
patch: ERROR: division by zero
The bounding interval and cube_coord_low()/cube_coord_high() use the
plain Min()/Max() macros. With NaN they give different answers
depending on argument order: Min(x, NaN) is NaN, but Min(NaN, y) is y.
So after "..., NaN, 5" the bounding interval collapses to [5,5]. The
range is then 0 even though there are distinct values, and the
float8_div() in cube_consider_split() raises the error.
gist_box_picksplit() builds its bounding box with adjustBox(), which
compares using float8_lt()/float8_gt(), and the equivalent insert into
a gist-indexed box column works on master.
2. Large coordinates: "value out of range: overflow"
create table h (c cube);
create index on h using gist (c);
insert into h select cube(array[case when g % 2 = 0
then 1e308 else -1e308 end])
from generate_series(1, 300) g;
master: INSERT 0 300
patch: ERROR: value out of range: overflow
float8_mi() raises this error when bounding_upper - bounding_lower,
or left_upper - right_lower, overflows. The Guttman code it replaces
used plain C arithmetic, which can't fail. The box opclass already
behaves like this on master (the equivalent insert into a
gist-indexed box column fails), so the patch inherits it from there.
For cube, though, it is new.
Both errors also hit CREATE INDEX on existing data. A pg_dump of a
master database with such indexes restores into a patched server
without any of them: each CREATE INDEX fails with one of the errors
above.
Regards,
--
Rustam Allakov
The new status of this patch is: Waiting on Author