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
