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
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 9f4698f2a2..c580d657cf 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -186,7 +186,8 @@ static IndexClause *expand_indexqual_rowcompare(PlannerInfo *root,
bool var_on_left);
static void match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
List **orderby_clauses_p,
- List **clause_columns_p);
+ List **clause_columns_p,
+ int *match_pathkeys_length_p);
static Expr *match_clause_to_ordering_op(IndexOptInfo *index,
int indexcol, Expr *clause, Oid pk_opfamily);
static bool ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel,
@@ -853,6 +854,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
bool index_is_ordered;
bool index_only_scan;
int indexcol;
+ int match_pathkeys_length;
/*
* Check that index supports the desired scan type(s)
@@ -977,9 +979,14 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
/* see if we can generate ordering operators for query_pathkeys */
match_pathkeys_to_index(index, root->query_pathkeys,
&orderbyclauses,
- &orderbyclausecols);
- if (orderbyclauses)
- useful_pathkeys = root->query_pathkeys;
+ &orderbyclausecols,
+ &match_pathkeys_length);
+ if (orderbyclauses) {
+ if (match_pathkeys_length == list_length(root->query_pathkeys))
+ useful_pathkeys = root->query_pathkeys;
+ else
+ useful_pathkeys = list_truncate(list_copy(root->query_pathkeys), match_pathkeys_length);
+ }
else
useful_pathkeys = NIL;
}
@@ -3065,7 +3072,8 @@ expand_indexqual_rowcompare(PlannerInfo *root,
static void
match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
List **orderby_clauses_p,
- List **clause_columns_p)
+ List **clause_columns_p,
+ int *match_pathkeys_length_p)
{
List *orderby_clauses = NIL;
List *clause_columns = NIL;
@@ -3073,6 +3081,7 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
*orderby_clauses_p = NIL; /* set default results */
*clause_columns_p = NIL;
+ *match_pathkeys_length_p = 0;
/* Only indexes with the amcanorderbyop property are interesting here */
if (!index->amcanorderbyop)
@@ -3092,11 +3101,11 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
/* Pathkey must request default sort order for the target opfamily */
if (pathkey->pk_strategy != BTLessStrategyNumber ||
pathkey->pk_nulls_first)
- return;
+ break;
/* If eclass is volatile, no hope of using an indexscan */
if (pathkey->pk_eclass->ec_has_volatile)
- return;
+ break;
/*
* Try to match eclass member expression(s) to index. Note that child
@@ -3140,12 +3149,14 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
}
}
- if (found) /* don't want to look at remaining members */
+ if (found) { /* don't want to look at remaining members */
+ (*match_pathkeys_length_p)++;
break;
+ }
}
if (!found) /* fail if no match for this pathkey */
- return;
+ break;
}
*orderby_clauses_p = orderby_clauses; /* success! */
