Incremental sort for access method with ordered scan support (amcanorderbyop)
Miroslav Bendik <miroslav.bendik@gmail.com>
From: Miroslav Bendik <miroslav.bendik@gmail.com>
To: pgsql-hackers@postgresql.org
Date: 2023-04-15T16:55:51Z
Lists: pgsql-hackers
Attachments
- am_orderbyop_incremental_sort_v1.patch (text/x-patch) patch v1
Current version of postgresql don't support incremental sort using ordered scan on access method. Example database: CREATE TABLE t (id serial, p point, PRIMARY KEY(id)); INSERT INTO t (SELECT generate_series(1, 10000000), point(random(), random())); CREATE INDEX p_idx ON t USING gist(p); ANALYZE; Now i want closest points to center: SELECT id, p <-> point(0.5, 0.5) dist FROM t ORDER BY dist LIMIT 10; Everything works good (Execution Time: 0.276 ms). Now i want predictable sorting for points with same distance: SELECT id, p <-> point(0.5, 0.5) dist FROM t ORDER BY dist, id LIMIT 10; Execution time is now 1 000 x slower (589.486 ms) and postgresql uses full sort istead of incremental: Sort (cost=205818.51..216235.18 rows=4166667 width=12) Postgres allows incremental sort only for ordered indexes. Function build_index_paths dont build partial order paths for access methods with order support. My patch adds support for incremental ordering with access method. Results with patch: Incremental Sort (cost=5522.10..1241841.02 rows=10000000 width=12) (actual time=0.404..0.405 rows=10 loops=1) Sort Key: ((p <-> '(0.5,0.5)'::point)), id Presorted Key: ((p <-> '(0.5,0.5)'::point)) Execution Time: 0.437 ms
Commits
-
Allow Incremental Sorts on GiST and SP-GiST indexes
- 625d5b3ca096 17.0 landed
-
Fix list_copy_head() with empty Lists
- 63a03aea6bc8 15.3 landed
- e35ded29566f 16.0 landed