Incremental sort for access method with ordered scan support (amcanorderbyop) - Mailing list pgsql-hackers

From Miroslav Bendik
Subject Incremental sort for access method with ordered scan support (amcanorderbyop)
Date
Msg-id CAPoEpV0QYDtzjwamwWUBqyWpaCVbJV2d6qOD7Uy09bWn47PJtw@mail.gmail.com
Whole thread Raw
Responses Re: Incremental sort for access method with ordered scan support (amcanorderbyop)
List 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

pgsql-hackers by date:

Previous
From: Noah Misch
Date:
Subject: Re: Protecting allocator headers with Valgrind
Next
From: Tom Lane
Date:
Subject: Re: Direct I/O