> 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.
