[PATCH] sort leaf pages by ctid for gist indexes built using sorted method
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:t45246psql -h localhost -U postgresBuilt from patchset v1 (message #1), July 27, 2026 at 03:51 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 t45246_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 t45246_1 && git checkout t45246_1Patchset v1 (message #1) is on t45246_1
Hi!
With the current implementation, for GiST indexes created by doing multiple
inserts, index tuples match heap tuples order, but it doesn't work that way
for sorted method where index tuples on all levels are ordered using
comparator provided in sortsupport (z-order for geometry type, for
example). This means two tuples that are on the same heap page can be far
apart from one another on an index page, and the heap page may be read
twice and prefetch performance will degrade.
I've created a patch intended to improve that by sorting index tuples by
heap tuples TID order on leaf pages.
With the current implementation, for GiST indexes created by doing multiple inserts, index tuples match heap tuples order, but it doesn't work that way for sorted method where index tuples on all levels are ordered using comparator provided in sortsupport (z-order for geometry type, for example). This means two tuples that are on the same heap page can be far apart from one another on an index page, and the heap page may be read twice and prefetch performance will degrade.
I've created a patch intended to improve that by sorting index tuples by heap tuples TID order on leaf pages.
Hi!
Thanks you for the patch. The code looks nice and clean.
From my POV this optimization certainly makes sense.
But can we have some benchmarks showing that this optimization really helps?
I've tried it on my laptop extra build efforts cost us about 5% or CREATE INDEX performance. How big would be benefit for scans that we get?
before patch
postgres=# create table x as select point (random(),random()) from generate_series(1,3000000,1);
SELECT 3000000
postgres=# \timing
Timing is on.
postgres=# create index ON x using gist (point );
CREATE INDEX
Time: 1872,503 ms (00:01,873)
postgres=# create index ON x using gist (point );
CREATE INDEX
Time: 1797,329 ms (00:01,797)
postgres=# create index ON x using gist (point );
CREATE INDEX
Time: 1787,362 ms (00:01,787)
postgres=# create index ON x using gist (point );
CREATE INDEX
Time: 1793,545 ms (00:01,794)
postgres=# create index ON x using gist (point );
CREATE INDEX
Time: 1805,572 ms (00:01,806)
After patch
postgres=# create table x as select point (random(),random()) from generate_series(1,3000000,1);
SELECT 3000000
postgres=# \timing
Timing is on.
postgres=# create index ON x using gist (point );
CREATE INDEX
Time: 2134,448 ms (00:02,134)
postgres=# create index ON x using gist (point );
CREATE INDEX
Time: 1945,978 ms (00:01,946)
postgres=# create index ON x using gist (point );
CREATE INDEX
Time: 1965,045 ms (00:01,965)
postgres=# create index ON x using gist (point );
CREATE INDEX
Time: 1973,248 ms (00:01,973)
postgres=# create index ON x using gist (point );
CREATE INDEX
Time: 1970,578 ms (00:01,971)
Thanks!
Best regards, Andrey Borodin.
Hi,
On 2021-12-16 14:49:25 +0500, Andrey Borodin wrote:
With the current implementation, for GiST indexes created by doing multiple inserts, index tuples match heap tuples order, but it doesn't work that way for sorted method where index tuples on all levels are ordered using comparator provided in sortsupport (z-order for geometry type, for example). This means two tuples that are on the same heap page can be far apart from one another on an index page, and the heap page may be read twice and prefetch performance will degrade.
I've created a patch intended to improve that by sorting index tuples by heap tuples TID order on leaf pages.
Thanks you for the patch. The code looks nice and clean.
The patch fails currently doesn't apply: http://cfbot.cputube.org/patch_37_3454.log
But can we have some benchmarks showing that this optimization really helps?
As there hasn't been a response to this even in the last CF, I'm going to mark
this entry as returned with feedback (IMO shouldn't even have been moved to
this CF).
Greetings,
Andres Freund