Re: [PATCH] reduce page overlap of GiST indexes built using sorted method

Hey!

Postgres 14 introduces an option to create a GiST index using a sort method. It allows to create indexes much faster but as it had been mentioned in sort support patch discussion the faster build performance comes at cost of higher degree of overlap between pages than for indexes built with regular method.

Sort support was implemented for GiST opclass in PostGIS but eventually got removed as default behaviour in latest 3.2 release because as it had been discovered by Paul Ramsey https://lists.osgeo.org/pipermail/postgis-devel/2021-November/029225.html performance of queries might degrade by 50%.

Together with Darafei Praliaskouski, Andrey Borodin and me we tried several approaches to solve query performance degrade:

• The first attempt was try to decide whether to make a split depending on direction of curve (Z-curve for Postgres geometry type, Hilbert curve for PostGIS). It was implemented by filling page until fillfactor / 2 and then checking penalty for every next item and keep inserting in current page if penalty is 0 or start new page if penalty is not 0. It turned out that with this approach index becomes significantly larger whereas pages overlap still remains high.
• Andrey Borodin implemented LRU + split: a fixed amount of pages are kept in memory and the best candidate page to insert the next item in is selected by minimum penalty among these pages. If the best page for insertion is full, it gets splited into multiple pages, and if the amount of candidate pages after split exceeds the limit, the pages insertion to which has not happened recently are flushed. https://github.com/x4m/postgres_g/commit/0f2ed5f32a00f6c3019048e0c145b7ebda629e73. We made some tests and while query performance speed using index built with this approach is fine a size of index is extremely large.

Eventually we made implementation of an idea outlined in sort support patch discussion here https://www.postgresql.org/message-id/flat/08173bd0-488d-da76-a904-912c35da446b@iki.fi#09ac9751a4cde897c99b99b2170faf3a that several pages can be collected and then divided into actual index pages by calling picksplit. My benchmarks with data provided in postgis-devel show that query performance using index built with patched sort support is comparable with performance of query using index built with regular method. The size of index is also matches size of index built with non-sorting method.

It should be noted that with the current implementation of the sorting build method, pages are always filled up to fillfactor. This patch changes this behavior to what it would be if using a non-sorting method, and pages are not always filled to fillfactor for the sake of query performance. I'm interested in improving it and I wonder if there are any ideas on this.

Benchmark summary:

create index roads_rdr_idx on roads_rdr using gist (geom);

with sort support before patch / CREATE INDEX 76.709 ms

with sort support after patch / CREATE INDEX 225.238 ms

without sort support / CREATE INDEX 446.071 ms

select count(*) from roads_rdr a, roads_rdr b where a.geom && b.geom;

with sort support before patch / SELECT 5766.526 ms

with sort support after patch / SELECT 2646.554 ms 

without sort support / SELECT 2721.718 ms

index size

with sort support before patch / IDXSIZE 2940928 bytes

with sort support after patch / IDXSIZE 4956160 bytes

without sort support / IDXSIZE 5447680 bytes

More detailed:

Before patch using sorted method:

postgres=# create index roads_rdr_geom_idx_sortsupport on roads_rdr using gist(geom);

CREATE INDEX

Time: 76.709 ms

postgres=# select count(*) from roads_rdr a, roads_rdr b where a.geom && b.geom;

 count  

--------

 505806

(1 row)

Time: 5766.526 ms (00:05.767)

postgres=# select count(*) from roads_rdr a, roads_rdr b where a.geom && b.geom;

 count  

--------

 505806

(1 row)

Time: 5880.142 ms (00:05.880)

postgres=# select count(*) from roads_rdr a, roads_rdr b where a.geom && b.geom;

 count  

--------

 505806

(1 row)

Time: 5778.437 ms (00:05.778)

postgres=# select gist_stat('roads_rdr_geom_idx_sortsupport');

                gist_stat                 

------------------------------------------

 Number of levels:          3            +

 Number of pages:           359          +

 Number of leaf pages:      356          +

 Number of tuples:          93034        +

 Number of invalid tuples:  0            +

 Number of leaf tuples:     92676        +

 Total size of tuples:      2609260 bytes+

 Total size of leaf tuples: 2599200 bytes+

 Total size of index:       2940928 bytes+

 

(1 row)

After patch using sorted method:

postgres=# create index roads_rdr_geom_idx_sortsupport on roads_rdr using gist(geom);

CREATE INDEX

Time: 225.238 ms

postgres=# select count(*) from roads_rdr a, roads_rdr b where a.geom && b.geom;

 count  

--------

 505806

(1 row)

Time: 2646.554 ms (00:02.647)

postgres=# select count(*) from roads_rdr a, roads_rdr b where a.geom && b.geom;

 count  

--------

 505806

(1 row)

Time: 2499.107 ms (00:02.499)

postgres=# select count(*) from roads_rdr a, roads_rdr b where a.geom && b.geom;

 count  

--------

 505806

(1 row)

Time: 2519.815 ms (00:02.520)

postgres=# select gist_stat('roads_rdr_geom_idx_sortsupport');

                gist_stat                 

------------------------------------------

 Number of levels:          3            +

 Number of pages:           605          +

 Number of leaf pages:      600          +

 Number of tuples:          93280        +

 Number of invalid tuples:  0            +

 Number of leaf tuples:     92676        +

 Total size of tuples:      2619100 bytes+

 Total size of leaf tuples: 2602128 bytes+

 Total size of index:       4956160 bytes+

 

(1 row)

With index built using default method:

postgres=# create index roads_rdr_geom_idx_no_sortsupport on roads_rdr using gist(geom);

CREATE INDEX

Time: 446.071 ms

postgres=# select count(*) from roads_rdr a, roads_rdr b where a.geom && b.geom;

 count  

--------

 505806

(1 row)

Time: 2721.718 ms (00:02.722)

postgres=# select count(*) from roads_rdr a, roads_rdr b where a.geom && b.geom;

 count  

--------

 505806

(1 row)

Time: 3549.549 ms (00:03.550)

postgres=# select count(*) from roads_rdr a, roads_rdr b where a.geom && b.geom;

 count  

--------

 505806

(1 row)

postgres=# select gist_stat('roads_rdr_geom_idx_no_sortsupport');

                gist_stat                 

------------------------------------------

 Number of levels:          3            +

 Number of pages:           665          +

 Number of leaf pages:      660          +

 Number of tuples:          93340        +

 Number of invalid tuples:  0            +

 Number of leaf tuples:     92676        +

 Total size of tuples:      2621500 bytes+

 Total size of leaf tuples: 2602848 bytes+

 Total size of index:       5447680 bytes+

(1 row)