Incremental sort for access method with ordered scan support (amcanorderbyop)

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

Responses

Browse pgsql-hackers by date

  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