From: | Miroslav Bendik <miroslav(dot)bendik(at)gmail(dot)com> |
---|---|
To: | pgsql-hackers(at)postgresql(dot)org |
Subject: | Incremental sort for access method with ordered scan support (amcanorderbyop) |
Date: | 2023-04-15 16:55:51 |
Message-ID: | CAPoEpV0QYDtzjwamwWUBqyWpaCVbJV2d6qOD7Uy09bWn47PJtw@mail.gmail.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
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
Attachment | Content-Type | Size |
---|---|---|
am_orderbyop_incremental_sort_v1.patch | text/x-patch | 3.1 KB |
From | Date | Subject | |
---|---|---|---|
Next Message | Tom Lane | 2023-04-15 18:19:35 | Re: Direct I/O |
Previous Message | Noah Misch | 2023-04-15 15:25:58 | Re: Protecting allocator headers with Valgrind |