Incremental sort for access method with ordered scan support (amcanorderbyop)
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
Attachments:
am_orderbyop_incremental_sort_v1.patchtext/x-patch; charset=US-ASCII; name=am_orderbyop_incremental_sort_v1.patchDownload
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! */
On Sun, Apr 16, 2023 at 1:20 AM Miroslav Bendik <miroslav.bendik@gmail.com>
wrote:
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.
I think this is a meaningful optimization. I reviewed the patch and
here are the comments from me.
* I understand the new param 'match_pathkeys_length_p' is used to tell
how many presorted keys are useful. I think list_length(orderbyclauses)
will do the same. So there is no need to add the new param, thus we can
reduce the code diffs.
* Now that match_pathkeys_to_index() returns a prefix of the pathkeys
rather than returns NIL immediately when there is a failure to match, it
seems the two local variables 'orderby_clauses' and 'clause_columns' are
not necessary any more. I think we can instead lappend the matched
'expr' and 'indexcol' to '*orderby_clauses_p' and '*clause_columns_p'
directly. In this way we can still call 'return' when we come to a
failure to match.
* In build_index_paths(), I think the diff can be reduced to
- if (orderbyclauses)
- useful_pathkeys = root->query_pathkeys;
- else
- useful_pathkeys = NIL;
+ useful_pathkeys = list_truncate(list_copy(root->query_pathkeys),
+ list_length(orderbyclauses));* Several comments in match_pathkeys_to_index() are out of date. We
need to revise them to cope with the change.
* I think it's better to provide a test case.
Thanks
Richard
po 17. 4. 2023 o 15:26 Richard Guo <guofenglinux@gmail.com> napísal(a):
On Sun, Apr 16, 2023 at 1:20 AM Miroslav Bendik <miroslav.bendik@gmail.com> wrote:
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.I think this is a meaningful optimization. I reviewed the patch and
here are the comments from me.* I understand the new param 'match_pathkeys_length_p' is used to tell
how many presorted keys are useful. I think list_length(orderbyclauses)
will do the same. So there is no need to add the new param, thus we can
reduce the code diffs.* Now that match_pathkeys_to_index() returns a prefix of the pathkeys
rather than returns NIL immediately when there is a failure to match, it
seems the two local variables 'orderby_clauses' and 'clause_columns' are
not necessary any more. I think we can instead lappend the matched
'expr' and 'indexcol' to '*orderby_clauses_p' and '*clause_columns_p'
directly. In this way we can still call 'return' when we come to a
failure to match.* In build_index_paths(), I think the diff can be reduced to
- if (orderbyclauses) - useful_pathkeys = root->query_pathkeys; - else - useful_pathkeys = NIL; + useful_pathkeys = list_truncate(list_copy(root->query_pathkeys), + list_length(orderbyclauses));* Several comments in match_pathkeys_to_index() are out of date. We
need to revise them to cope with the change.* I think it's better to provide a test case.
Thanks
Richard
Thank you for advice,
here is an updated patch with proposed changes.
--
Best regards
Miroslav
Attachments:
am_orderbyop_incremental_sort_v2.patchtext/x-patch; charset=US-ASCII; name=am_orderbyop_incremental_sort_v2.patchDownload
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index b8000da56d..202779fb10 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -864,8 +864,8 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
List *index_clauses;
Relids outer_relids;
double loop_count;
- List *orderbyclauses;
- List *orderbyclausecols;
+ List *orderbyclauses = NIL;
+ List *orderbyclausecols = NIL;
List *index_pathkeys;
List *useful_pathkeys;
bool found_lower_saop_clause;
@@ -1001,10 +1001,8 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
match_pathkeys_to_index(index, root->query_pathkeys,
&orderbyclauses,
&orderbyclausecols);
- if (orderbyclauses)
- useful_pathkeys = root->query_pathkeys;
- else
- useful_pathkeys = NIL;
+ useful_pathkeys = list_truncate(list_copy(root->query_pathkeys),
+ list_length(orderbyclauses));
}
else
{
@@ -3071,16 +3069,14 @@ expand_indexqual_rowcompare(PlannerInfo *root,
* index column numbers (zero based) that each clause would be used with.
* NIL lists are returned if the ordering is not achievable this way.
*
- * On success, the result list is ordered by pathkeys, and in fact is
- * one-to-one with the requested pathkeys.
+ * On success, the result list is ordered by pathkeys. Result can be shorter
+ * than pathkeys on partial prefix match.
*/
static void
match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
List **orderby_clauses_p,
List **clause_columns_p)
{
- List *orderby_clauses = NIL;
- List *clause_columns = NIL;
ListCell *lc1;
*orderby_clauses_p = NIL; /* set default results */
@@ -3104,11 +3100,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
@@ -3145,8 +3141,8 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
pathkey->pk_opfamily);
if (expr)
{
- orderby_clauses = lappend(orderby_clauses, expr);
- clause_columns = lappend_int(clause_columns, indexcol);
+ *orderby_clauses_p = lappend(*orderby_clauses_p, expr);
+ *clause_columns_p = lappend_int(*clause_columns_p, indexcol);
found = true;
break;
}
@@ -3156,12 +3152,9 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
break;
}
- if (!found) /* fail if no match for this pathkey */
+ if (!found) /* end after first not matching expression */
return;
}
-
- *orderby_clauses_p = orderby_clauses; /* success! */
- *clause_columns_p = clause_columns;
}
/*
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index 0a631124c2..dcf2c0762d 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1672,3 +1672,33 @@ order by 1, 2;
-> Function Scan on generate_series
(7 rows)
+-- Incremental sort for not ordered indexes, but with AM order operator
+set enable_incremental_sort = on;
+-- table with GiST index supports closest points retrieval,
+-- but has not sorted index
+create table t (a point, b int);
+create index on t using gist(a);
+insert into t select point(mod(i, 7), mod(i, 11)), i from generate_series(1, 1000) s(i);
+analyze t;
+explain (costs off) select a, b, a <-> point(5, 5) dist from t order by dist, b limit 1;
+ QUERY PLAN
+-------------------------------------------------
+ Limit
+ -> Incremental Sort
+ Sort Key: ((a <-> '(5,5)'::point)), b
+ Presorted Key: ((a <-> '(5,5)'::point))
+ -> Index Scan using t_a_idx on t
+ Order By: (a <-> '(5,5)'::point)
+(6 rows)
+
+explain (costs off) select a, b, a <-> point(5, 5) dist from t order by dist, b desc limit 1;
+ QUERY PLAN
+----------------------------------------------------
+ Limit
+ -> Incremental Sort
+ Sort Key: ((a <-> '(5,5)'::point)), b DESC
+ Presorted Key: ((a <-> '(5,5)'::point))
+ -> Index Scan using t_a_idx on t
+ Order By: (a <-> '(5,5)'::point)
+(6 rows)
+
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index 284a354dbb..5cef0ba12c 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -281,3 +281,14 @@ from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
explain (costs off) select sub.unique1, stringu1 || random()::text
from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub
order by 1, 2;
+
+-- Incremental sort for not ordered indexes, but with AM order operator
+set enable_incremental_sort = on;
+-- table with GiST index supports closest points retrieval,
+-- but has not sorted index
+create table t (a point, b int);
+create index on t using gist(a);
+insert into t select point(mod(i, 7), mod(i, 11)), i from generate_series(1, 1000) s(i);
+analyze t;
+explain (costs off) select a, b, a <-> point(5, 5) dist from t order by dist, b limit 1;
+explain (costs off) select a, b, a <-> point(5, 5) dist from t order by dist, b desc limit 1;
On Tue, 18 Apr 2023 at 19:29, Miroslav Bendik <miroslav.bendik@gmail.com> wrote:
here is an updated patch with proposed changes.
Here's a quick review:
1. I don't think this is required. match_pathkeys_to_index() sets
these to NIL and they're set accordingly by the other code paths.
- List *orderbyclauses;
- List *orderbyclausecols;
+ List *orderbyclauses = NIL;
+ List *orderbyclausecols = NIL;2. You can use list_copy_head(root->query_pathkeys,
list_length(orderbyclauses)); instead of:
+ useful_pathkeys = list_truncate(list_copy(root->query_pathkeys),
+ list_length(orderbyclauses));3. The following 2 changes don't seem to be needed:
@@ -3104,11 +3100,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;There's no code after the loop you're breaking out of, so it seems to
me that return is the same as break and there's no reason to change
it.
David
Thanks for feedback
2. You can use list_copy_head(root->query_pathkeys,
list_length(orderbyclauses)); instead of:+ useful_pathkeys = list_truncate(list_copy(root->query_pathkeys), + list_length(orderbyclauses));
This code will crash if query_pathkeys is NIL. I need either modify
list_copy_head (v3.1) or add checks before call (v3.2).
I don't know if it's a good idea to modify list_copy_head. It will add
additional overhead to every call.
--
Best regards
Miroslav
Attachments:
am_orderbyop_incremental_sort_v3.1.patchtext/x-patch; charset=US-ASCII; name=am_orderbyop_incremental_sort_v3.1.patchDownload
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index b8000da56d..880eecd31c 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -1001,10 +1001,8 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
match_pathkeys_to_index(index, root->query_pathkeys,
&orderbyclauses,
&orderbyclausecols);
- if (orderbyclauses)
- useful_pathkeys = root->query_pathkeys;
- else
- useful_pathkeys = NIL;
+ useful_pathkeys = list_copy_head(root->query_pathkeys,
+ list_length(orderbyclauses));
}
else
{
@@ -3071,16 +3069,14 @@ expand_indexqual_rowcompare(PlannerInfo *root,
* index column numbers (zero based) that each clause would be used with.
* NIL lists are returned if the ordering is not achievable this way.
*
- * On success, the result list is ordered by pathkeys, and in fact is
- * one-to-one with the requested pathkeys.
+ * On success, the result list is ordered by pathkeys. Result can be shorter
+ * than pathkeys on partial prefix match.
*/
static void
match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
List **orderby_clauses_p,
List **clause_columns_p)
{
- List *orderby_clauses = NIL;
- List *clause_columns = NIL;
ListCell *lc1;
*orderby_clauses_p = NIL; /* set default results */
@@ -3145,8 +3141,8 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
pathkey->pk_opfamily);
if (expr)
{
- orderby_clauses = lappend(orderby_clauses, expr);
- clause_columns = lappend_int(clause_columns, indexcol);
+ *orderby_clauses_p = lappend(*orderby_clauses_p, expr);
+ *clause_columns_p = lappend_int(*clause_columns_p, indexcol);
found = true;
break;
}
@@ -3156,12 +3152,9 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
break;
}
- if (!found) /* fail if no match for this pathkey */
+ if (!found) /* end after first not matching expression */
return;
}
-
- *orderby_clauses_p = orderby_clauses; /* success! */
- *clause_columns_p = clause_columns;
}
/*
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index 0a631124c2..dcf2c0762d 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1672,3 +1672,33 @@ order by 1, 2;
-> Function Scan on generate_series
(7 rows)
+-- Incremental sort for not ordered indexes, but with AM order operator
+set enable_incremental_sort = on;
+-- table with GiST index supports closest points retrieval,
+-- but has not sorted index
+create table t (a point, b int);
+create index on t using gist(a);
+insert into t select point(mod(i, 7), mod(i, 11)), i from generate_series(1, 1000) s(i);
+analyze t;
+explain (costs off) select a, b, a <-> point(5, 5) dist from t order by dist, b limit 1;
+ QUERY PLAN
+-------------------------------------------------
+ Limit
+ -> Incremental Sort
+ Sort Key: ((a <-> '(5,5)'::point)), b
+ Presorted Key: ((a <-> '(5,5)'::point))
+ -> Index Scan using t_a_idx on t
+ Order By: (a <-> '(5,5)'::point)
+(6 rows)
+
+explain (costs off) select a, b, a <-> point(5, 5) dist from t order by dist, b desc limit 1;
+ QUERY PLAN
+----------------------------------------------------
+ Limit
+ -> Incremental Sort
+ Sort Key: ((a <-> '(5,5)'::point)), b DESC
+ Presorted Key: ((a <-> '(5,5)'::point))
+ -> Index Scan using t_a_idx on t
+ Order By: (a <-> '(5,5)'::point)
+(6 rows)
+
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index 284a354dbb..5cef0ba12c 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -281,3 +281,14 @@ from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
explain (costs off) select sub.unique1, stringu1 || random()::text
from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub
order by 1, 2;
+
+-- Incremental sort for not ordered indexes, but with AM order operator
+set enable_incremental_sort = on;
+-- table with GiST index supports closest points retrieval,
+-- but has not sorted index
+create table t (a point, b int);
+create index on t using gist(a);
+insert into t select point(mod(i, 7), mod(i, 11)), i from generate_series(1, 1000) s(i);
+analyze t;
+explain (costs off) select a, b, a <-> point(5, 5) dist from t order by dist, b limit 1;
+explain (costs off) select a, b, a <-> point(5, 5) dist from t order by dist, b desc limit 1;
am_orderbyop_incremental_sort_v3.2.patchtext/x-patch; charset=US-ASCII; name=am_orderbyop_incremental_sort_v3.2.patchDownload
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index b8000da56d..fb8e4edf9a 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -1001,10 +1001,11 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
match_pathkeys_to_index(index, root->query_pathkeys,
&orderbyclauses,
&orderbyclausecols);
- if (orderbyclauses)
- useful_pathkeys = root->query_pathkeys;
- else
+ if (root->query_pathkeys == NIL)
useful_pathkeys = NIL;
+ else
+ useful_pathkeys = list_copy_head(root->query_pathkeys,
+ list_length(orderbyclauses));
}
else
{
@@ -3071,16 +3072,14 @@ expand_indexqual_rowcompare(PlannerInfo *root,
* index column numbers (zero based) that each clause would be used with.
* NIL lists are returned if the ordering is not achievable this way.
*
- * On success, the result list is ordered by pathkeys, and in fact is
- * one-to-one with the requested pathkeys.
+ * On success, the result list is ordered by pathkeys. Result can be shorter
+ * than pathkeys on partial prefix match.
*/
static void
match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
List **orderby_clauses_p,
List **clause_columns_p)
{
- List *orderby_clauses = NIL;
- List *clause_columns = NIL;
ListCell *lc1;
*orderby_clauses_p = NIL; /* set default results */
@@ -3145,8 +3144,8 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
pathkey->pk_opfamily);
if (expr)
{
- orderby_clauses = lappend(orderby_clauses, expr);
- clause_columns = lappend_int(clause_columns, indexcol);
+ *orderby_clauses_p = lappend(*orderby_clauses_p, expr);
+ *clause_columns_p = lappend_int(*clause_columns_p, indexcol);
found = true;
break;
}
@@ -3156,12 +3155,9 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
break;
}
- if (!found) /* fail if no match for this pathkey */
+ if (!found) /* end after first not matching expression */
return;
}
-
- *orderby_clauses_p = orderby_clauses; /* success! */
- *clause_columns_p = clause_columns;
}
/*
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index 0a631124c2..dcf2c0762d 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1672,3 +1672,33 @@ order by 1, 2;
-> Function Scan on generate_series
(7 rows)
+-- Incremental sort for not ordered indexes, but with AM order operator
+set enable_incremental_sort = on;
+-- table with GiST index supports closest points retrieval,
+-- but has not sorted index
+create table t (a point, b int);
+create index on t using gist(a);
+insert into t select point(mod(i, 7), mod(i, 11)), i from generate_series(1, 1000) s(i);
+analyze t;
+explain (costs off) select a, b, a <-> point(5, 5) dist from t order by dist, b limit 1;
+ QUERY PLAN
+-------------------------------------------------
+ Limit
+ -> Incremental Sort
+ Sort Key: ((a <-> '(5,5)'::point)), b
+ Presorted Key: ((a <-> '(5,5)'::point))
+ -> Index Scan using t_a_idx on t
+ Order By: (a <-> '(5,5)'::point)
+(6 rows)
+
+explain (costs off) select a, b, a <-> point(5, 5) dist from t order by dist, b desc limit 1;
+ QUERY PLAN
+----------------------------------------------------
+ Limit
+ -> Incremental Sort
+ Sort Key: ((a <-> '(5,5)'::point)), b DESC
+ Presorted Key: ((a <-> '(5,5)'::point))
+ -> Index Scan using t_a_idx on t
+ Order By: (a <-> '(5,5)'::point)
+(6 rows)
+
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index 284a354dbb..5cef0ba12c 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -281,3 +281,14 @@ from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
explain (costs off) select sub.unique1, stringu1 || random()::text
from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub
order by 1, 2;
+
+-- Incremental sort for not ordered indexes, but with AM order operator
+set enable_incremental_sort = on;
+-- table with GiST index supports closest points retrieval,
+-- but has not sorted index
+create table t (a point, b int);
+create index on t using gist(a);
+insert into t select point(mod(i, 7), mod(i, 11)), i from generate_series(1, 1000) s(i);
+analyze t;
+explain (costs off) select a, b, a <-> point(5, 5) dist from t order by dist, b limit 1;
+explain (costs off) select a, b, a <-> point(5, 5) dist from t order by dist, b desc limit 1;
Sorry for spamming, but I found a more elegant way to check if
query_paths is NIL without modified list_copy_head.
Here is a third iteration of this patch.
--
Miroslav
Attachments:
am_orderbyop_incremental_sort_v3.3.patchtext/x-patch; charset=US-ASCII; name=am_orderbyop_incremental_sort_v3.3.patchDownload
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index b8000da56d..735b41552a 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -995,16 +995,14 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
orderbyclauses = NIL;
orderbyclausecols = NIL;
}
- else if (index->amcanorderbyop && pathkeys_possibly_useful)
+ else if (index->amcanorderbyop && root->query_pathkeys && pathkeys_possibly_useful)
{
/* 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;
- else
- useful_pathkeys = NIL;
+ useful_pathkeys = list_copy_head(root->query_pathkeys,
+ list_length(orderbyclauses));
}
else
{
@@ -3071,16 +3069,14 @@ expand_indexqual_rowcompare(PlannerInfo *root,
* index column numbers (zero based) that each clause would be used with.
* NIL lists are returned if the ordering is not achievable this way.
*
- * On success, the result list is ordered by pathkeys, and in fact is
- * one-to-one with the requested pathkeys.
+ * On success, the result list is ordered by pathkeys. Result can be shorter
+ * than pathkeys on partial prefix match.
*/
static void
match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
List **orderby_clauses_p,
List **clause_columns_p)
{
- List *orderby_clauses = NIL;
- List *clause_columns = NIL;
ListCell *lc1;
*orderby_clauses_p = NIL; /* set default results */
@@ -3145,8 +3141,8 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
pathkey->pk_opfamily);
if (expr)
{
- orderby_clauses = lappend(orderby_clauses, expr);
- clause_columns = lappend_int(clause_columns, indexcol);
+ *orderby_clauses_p = lappend(*orderby_clauses_p, expr);
+ *clause_columns_p = lappend_int(*clause_columns_p, indexcol);
found = true;
break;
}
@@ -3156,12 +3152,9 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
break;
}
- if (!found) /* fail if no match for this pathkey */
+ if (!found) /* end after first not matching expression */
return;
}
-
- *orderby_clauses_p = orderby_clauses; /* success! */
- *clause_columns_p = clause_columns;
}
/*
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index 0a631124c2..dcf2c0762d 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1672,3 +1672,33 @@ order by 1, 2;
-> Function Scan on generate_series
(7 rows)
+-- Incremental sort for not ordered indexes, but with AM order operator
+set enable_incremental_sort = on;
+-- table with GiST index supports closest points retrieval,
+-- but has not sorted index
+create table t (a point, b int);
+create index on t using gist(a);
+insert into t select point(mod(i, 7), mod(i, 11)), i from generate_series(1, 1000) s(i);
+analyze t;
+explain (costs off) select a, b, a <-> point(5, 5) dist from t order by dist, b limit 1;
+ QUERY PLAN
+-------------------------------------------------
+ Limit
+ -> Incremental Sort
+ Sort Key: ((a <-> '(5,5)'::point)), b
+ Presorted Key: ((a <-> '(5,5)'::point))
+ -> Index Scan using t_a_idx on t
+ Order By: (a <-> '(5,5)'::point)
+(6 rows)
+
+explain (costs off) select a, b, a <-> point(5, 5) dist from t order by dist, b desc limit 1;
+ QUERY PLAN
+----------------------------------------------------
+ Limit
+ -> Incremental Sort
+ Sort Key: ((a <-> '(5,5)'::point)), b DESC
+ Presorted Key: ((a <-> '(5,5)'::point))
+ -> Index Scan using t_a_idx on t
+ Order By: (a <-> '(5,5)'::point)
+(6 rows)
+
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index 284a354dbb..5cef0ba12c 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -281,3 +281,14 @@ from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
explain (costs off) select sub.unique1, stringu1 || random()::text
from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub
order by 1, 2;
+
+-- Incremental sort for not ordered indexes, but with AM order operator
+set enable_incremental_sort = on;
+-- table with GiST index supports closest points retrieval,
+-- but has not sorted index
+create table t (a point, b int);
+create index on t using gist(a);
+insert into t select point(mod(i, 7), mod(i, 11)), i from generate_series(1, 1000) s(i);
+analyze t;
+explain (costs off) select a, b, a <-> point(5, 5) dist from t order by dist, b limit 1;
+explain (costs off) select a, b, a <-> point(5, 5) dist from t order by dist, b desc limit 1;
On Wed, 19 Apr 2023 at 16:53, Miroslav Bendik <miroslav.bendik@gmail.com> wrote:
2. You can use list_copy_head(root->query_pathkeys,
list_length(orderbyclauses)); instead of:+ useful_pathkeys = list_truncate(list_copy(root->query_pathkeys), + list_length(orderbyclauses));This code will crash if query_pathkeys is NIL. I need either modify
list_copy_head (v3.1) or add checks before call (v3.2).I don't know if it's a good idea to modify list_copy_head. It will add
additional overhead to every call.
That's a bug in list_copy_head(). Since NIL is how we represent empty
Lists, crashing on some valid representation of a List is not how it
should work.
That function is pretty new and was exactly added so we didn't have to
write list_truncate(list_copy(...), n) anymore. That gets pretty
wasteful when the input List is long and we only need a small portion
of it.
I've just pushed a fix to master for this. See [1]https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=e35ded29566f679e52888a8d34468bb51bc78bed. If you base your
patch atop of that you should be able to list list_copy_head() without
any issues.
David
On Thu, Apr 20, 2023 at 6:38 AM David Rowley <dgrowleyml@gmail.com> wrote:
That function is pretty new and was exactly added so we didn't have to
write list_truncate(list_copy(...), n) anymore. That gets pretty
wasteful when the input List is long and we only need a small portion
of it.
I searched the codes and found some other places where the manipulation
of lists can be improved in a similar way.
* lappend(list_copy(list), datum) as in get_required_extension().
This is not very efficient as after list_copy it would need to enlarge
the list immediately. It can be improved by inventing a new function,
maybe called list_append_copy, that do the copy and append all together.
* lcons(datum, list_copy(list)) as in get_query_def().
This is also not efficient. Immediately after list_copy, we'd need to
enlarge the list and move all the entries. It can also be improved by
doing all these things all together in one function.
* lcons(datum, list_delete_nth_cell(list_copy(list), n)) as in
sort_inner_and_outer.
It'd need to copy all the elements, and then delete the n'th entry which
would cause all following entries be moved, and then move all the
remaining entries for lcons. Maybe we can invent a new function for it?
So is it worthwhile to improve these places?
Besides, I found one place that can be improved the same way as what we
did in 9d299a49.
--- a/src/backend/rewrite/rewriteSearchCycle.c
+++ b/src/backend/rewrite/rewriteSearchCycle.c
@@ -523,7 +523,7 @@ rewriteSearchAndCycle(CommonTableExpr *cte) fexpr = makeFuncExpr(F_INT8INC, INT8OID, list_make1(fs),
InvalidOid, InvalidOid, COERCE_EXPLICIT_CALL);
- lfirst(list_head(search_col_rowexpr->args)) = fexpr;
+ linitial(search_col_rowexpr->args) = fexpr;Also, in applyparallelworker.c we have the usage as
TransactionId xid_tmp = lfirst_xid(list_nth_cell(subxactlist, i));
I wonder if we can invent function list_nth_xid to do it, to keep
consistent with list_nth/list_nth_int/list_nth_oid.
Thanks
Richard
I've just pushed a fix to master for this. See [1]. If you base your
patch atop of that you should be able to list list_copy_head() without
any issues.
Thanks for this fix. Now the version
am_orderbyop_incremental_sort_v3.1.patch [1]/messages/by-id/attachment/146450/am_orderbyop_incremental_sort_v3.1.patch works without issues
using the master branch.
[1]: /messages/by-id/attachment/146450/am_orderbyop_incremental_sort_v3.1.patch
I searched the codes and found some other places where the manipulation
of lists can be improved in a similar way.
* lappend(list_copy(list), datum) as in get_required_extension().
This is not very efficient as after list_copy it would need to enlarge
the list immediately. It can be improved by inventing a new function,
maybe called list_append_copy, that do the copy and append all together.
* lcons(datum, list_copy(list)) as in get_query_def().
This is also not efficient. Immediately after list_copy, we'd need to
enlarge the list and move all the entries. It can also be improved by
doing all these things all together in one function.
* lcons(datum, list_delete_nth_cell(list_copy(list), n)) as in
sort_inner_and_outer.
It'd need to copy all the elements, and then delete the n'th entry which
would cause all following entries be moved, and then move all the
remaining entries for lcons. Maybe we can invent a new function for it?
So is it worthwhile to improve these places?
I think yes. It's very inefficient coping and moving, unnecessarily.
Perhaps, like the attached patch?
lcons_copy_delete needs a careful review.
I wonder if we can invent function list_nth_xid to do it, to keep
consistent with list_nth/list_nth_int/list_nth_oid.
Perhaps list_nth_xid(const List *list, int n)?
regards,
Ranier Vilela
Attachments:
0001-add-new-list-functions.patchapplication/octet-stream; name=0001-add-new-list-functions.patchDownload
diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c
index 750ee5a7e5..17d96a9291 100644
--- a/src/backend/nodes/list.c
+++ b/src/backend/nodes/list.c
@@ -349,6 +349,37 @@ lappend(List *list, void *datum)
return list;
}
+/*
+ * Append a pointer to the new list (copy).
+ * A pointer to the modified list is returned.
+ * Note that this function may or may not destructively
+ * modify the list; callers should always use this function's return
+ * value, rather than continuing to use the pointer passed as the
+ * first argument.
+ */
+List *
+lappend_copy(List *list, void *datum)
+{
+ Assert(IsPointerList(list));
+
+ if (list == NIL)
+ list = new_list(T_List, 1);
+ else
+ {
+ List *newlist;
+
+ newlist = new_list(list->type, list->length + 1);
+ memcpy(newlist->elements, list->elements,
+ list->length * sizeof(ListCell));
+
+ list = newlist;
+ }
+
+ llast(list) = datum;
+ check_list_invariants(list);
+ return list;
+}
+
/*
* Append an integer to the specified list. See lappend()
*/
@@ -541,6 +572,78 @@ lcons_oid(Oid datum, List *list)
return list;
}
+/*
+ * Prepend a new element to the new list (copy).
+ * A pointer to the modified list is returned.
+ * Note that this function may or may not destructively
+ * modify the list; callers should always use this function's return
+ * value, rather than continuing to use the pointer passed as the
+ * second argument.
+ *
+ * Note that this takes time proportional to the length of the list,
+ * since the existing entries must be moved.
+ *
+ * Caution: before Postgres 8.0, the original List was unmodified and
+ * could be considered to retain its separate identity. This is no longer
+ * the case.
+ */
+List *
+lcons_copy(void *datum, List *list)
+{
+ Assert(IsPointerList(list));
+
+ if (list == NIL)
+ list = new_list(T_List, 1);
+ else
+ {
+ List *newlist;
+
+ newlist = new_list(list->type, list->length + 1);
+ memcpy(newlist->elements + 1, list->elements,
+ list->length * sizeof(ListCell));
+
+ list = newlist;
+ }
+
+ linitial(list) = datum;
+ check_list_invariants(list);
+ return list;
+}
+
+/*
+ * Prepend a new element to the new list (copy) and
+ * delete the n'th cell (counting from 0) in new list (copy).
+ *
+ * The List is pfree'd if this was the last member.
+ *
+ * Note that this takes time proportional to the distance to the end of the
+ * list, since the following entries must be moved.
+ */
+
+List *
+lcons_copy_delete(void *datum, List *list, int n)
+{
+ check_list_invariants(list);
+ Assert(IsPointerList(list));
+
+ if (list == NIL)
+ list = new_list(T_List, 1);
+ else if (n > 1 && list->length > n)
+ {
+ List *newlist;
+
+ newlist = new_list(list->type, list->length - 1 - n);
+ memcpy(&newlist->elements[n], &list->elements[n + 1],
+ (list->length - 1 - n) * sizeof(ListCell));
+
+ list = newlist;
+ }
+
+ linitial(list) = datum;
+ check_list_invariants(list);
+ return list;
+}
+
/*
* Concatenate list2 to the end of list1, and return list1.
*
diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h
index 529a382d28..78376158dc 100644
--- a/src/include/nodes/pg_list.h
+++ b/src/include/nodes/pg_list.h
@@ -324,6 +324,17 @@ list_nth_oid(const List *list, int n)
return lfirst_oid(list_nth_cell(list, n));
}
+/*
+ * Return the TransactionId value contained in the n'th element of the specified
+ * list.
+ */
+static inline TransactionId
+list_nth_xid(const List *list, int n)
+{
+ Assert(IsA(list, TransactionList));
+ return lfirst_xid(list_nth_cell(list, n));
+}
+
#define list_nth_node(type,list,n) castNode(type, list_nth(list, n))
/*
@@ -569,6 +580,8 @@ extern pg_nodiscard List *list_insert_nth_oid(List *list, int pos, Oid datum);
extern pg_nodiscard List *lcons(void *datum, List *list);
extern pg_nodiscard List *lcons_int(int datum, List *list);
extern pg_nodiscard List *lcons_oid(Oid datum, List *list);
+extern pg_nodiscard List *lcons_copy(void *datum, List *list);
+extern pg_nodiscard List *lcons_copy_delete(void *datum, List *list, int n);
extern pg_nodiscard List *list_concat(List *list1, const List *list2);
extern pg_nodiscard List *list_concat_copy(const List *list1, const List *list2);Import Notes
Resolved by subject fallback
On Thu, 20 Apr 2023 at 18:46, Richard Guo <guofenglinux@gmail.com> wrote:
On Thu, Apr 20, 2023 at 6:38 AM David Rowley <dgrowleyml@gmail.com> wrote:
That function is pretty new and was exactly added so we didn't have to
write list_truncate(list_copy(...), n) anymore. That gets pretty
wasteful when the input List is long and we only need a small portion
of it.I searched the codes and found some other places where the manipulation
of lists can be improved in a similar way.
I'd be happy to discuss our thought about List inefficiencies, but I
think to be fair to Miroslav, we should do that somewhere else. The
list_copy_head() discussion was directly related to his patch due to
the list of list_truncate(list_copy(..), ..). The other things you've
mentioned are not. Feel free to start a thread and copy me in.
David
On Fri, Apr 21, 2023 at 5:43 AM David Rowley <dgrowleyml@gmail.com> wrote:
On Thu, 20 Apr 2023 at 18:46, Richard Guo <guofenglinux@gmail.com> wrote:
I searched the codes and found some other places where the manipulation
of lists can be improved in a similar way.I'd be happy to discuss our thought about List inefficiencies, but I
think to be fair to Miroslav, we should do that somewhere else. The
list_copy_head() discussion was directly related to his patch due to
the list of list_truncate(list_copy(..), ..). The other things you've
mentioned are not. Feel free to start a thread and copy me in.
Yeah, that's right. Thank you for the suggestion. I started a new
thread here:
/messages/by-id/CAMbWs49dJnpezDQDDxCPKq7+=_3NyqLqGqnhqCjd+dYe4MS15w@mail.gmail.com
Thanks
Richard
On Thu, Apr 20, 2023 at 9:37 PM Miroslav Bendik <miroslav.bendik@gmail.com>
wrote:
Thanks for this fix. Now the version
am_orderbyop_incremental_sort_v3.1.patch [1] works without issues
using the master branch.
The v3.1 patch looks good to me, except that the comments around
match_pathkeys_to_index still need some polish.
1. For comment "On success, the result list is ordered by pathkeys.", I
think it'd be more accurate if we say something like "On success, the
result list is ordered by pathkeys or a prefix list of pathkeys."
considering the possibility of incremental sort.
2. The comment below is not true anymore.
/*
* Note: for any failure to match, we just return NIL immediately.
* There is no value in matching just some of the pathkeys.
*/
We should either remove it or change it to emphasize that we may return
a prefix of the pathkeys for incremental sort.
BTW, would you please add the patch to the CF to not lose track of it?
Thanks
Richard
Thanks, for suggestions.
On Sun 02. 07. 2023 at 10:18 Richard Guo <guofenglinux@gmail.com> wrote:
1. For comment "On success, the result list is ordered by pathkeys.", I
think it'd be more accurate if we say something like "On success, the
result list is ordered by pathkeys or a prefix list of pathkeys."
considering the possibility of incremental sort.2. The comment below is not true anymore.
/*
* Note: for any failure to match, we just return NIL immediately.
* There is no value in matching just some of the pathkeys.
*/
We should either remove it or change it to emphasize that we may return
a prefix of the pathkeys for incremental sort.
Comments are updated now.
BTW, would you please add the patch to the CF to not lose track of it?
Submitted <https://commitfest.postgresql.org/43/4433/>
--
Best regards
Miroslav
Attachments:
am_orderbyop_incremental_sort_v4.patchtext/x-patch; charset=US-ASCII; name=am_orderbyop_incremental_sort_v4.patchDownload
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 0065c8992b..a1daa31d07 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -978,10 +978,8 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
match_pathkeys_to_index(index, root->query_pathkeys,
&orderbyclauses,
&orderbyclausecols);
- if (orderbyclauses)
- useful_pathkeys = root->query_pathkeys;
- else
- useful_pathkeys = NIL;
+ useful_pathkeys = list_copy_head(root->query_pathkeys,
+ list_length(orderbyclauses));
}
else
{
@@ -3059,16 +3057,14 @@ expand_indexqual_rowcompare(PlannerInfo *root,
* index column numbers (zero based) that each clause would be used with.
* NIL lists are returned if the ordering is not achievable this way.
*
- * On success, the result list is ordered by pathkeys, and in fact is
- * one-to-one with the requested pathkeys.
+ * On success, the result list is ordered by pathkeys or a prefix list of
+ * pathkeys. Result can be shorter than pathkeys on partial prefix match.
*/
static void
match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
List **orderby_clauses_p,
List **clause_columns_p)
{
- List *orderby_clauses = NIL;
- List *clause_columns = NIL;
ListCell *lc1;
*orderby_clauses_p = NIL; /* set default results */
@@ -3085,8 +3081,8 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
ListCell *lc2;
/*
- * Note: for any failure to match, we just return NIL immediately.
- * There is no value in matching just some of the pathkeys.
+ * Note: for any failure to match, we just stop matching. Current
+ * longest match is already accumulated.
*/
/* Pathkey must request default sort order for the target opfamily */
@@ -3133,8 +3129,8 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
pathkey->pk_opfamily);
if (expr)
{
- orderby_clauses = lappend(orderby_clauses, expr);
- clause_columns = lappend_int(clause_columns, indexcol);
+ *orderby_clauses_p = lappend(*orderby_clauses_p, expr);
+ *clause_columns_p = lappend_int(*clause_columns_p, indexcol);
found = true;
break;
}
@@ -3144,12 +3140,9 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
break;
}
- if (!found) /* fail if no match for this pathkey */
+ if (!found) /* end after first not matching expression */
return;
}
-
- *orderby_clauses_p = orderby_clauses; /* success! */
- *clause_columns_p = clause_columns;
}
/*
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index 0c3433f8e5..41c62e0268 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1660,3 +1660,33 @@ order by 1, 2;
-> Function Scan on generate_series
(7 rows)
+-- Incremental sort for not ordered indexes, but with AM order operator
+set enable_incremental_sort = on;
+-- table with GiST index supports closest points retrieval,
+-- but has not sorted index
+create table t (a point, b int);
+create index on t using gist(a);
+insert into t select point(mod(i, 7), mod(i, 11)), i from generate_series(1, 1000) s(i);
+analyze t;
+explain (costs off) select a, b, a <-> point(5, 5) dist from t order by dist, b limit 1;
+ QUERY PLAN
+-------------------------------------------------
+ Limit
+ -> Incremental Sort
+ Sort Key: ((a <-> '(5,5)'::point)), b
+ Presorted Key: ((a <-> '(5,5)'::point))
+ -> Index Scan using t_a_idx on t
+ Order By: (a <-> '(5,5)'::point)
+(6 rows)
+
+explain (costs off) select a, b, a <-> point(5, 5) dist from t order by dist, b desc limit 1;
+ QUERY PLAN
+----------------------------------------------------
+ Limit
+ -> Incremental Sort
+ Sort Key: ((a <-> '(5,5)'::point)), b DESC
+ Presorted Key: ((a <-> '(5,5)'::point))
+ -> Index Scan using t_a_idx on t
+ Order By: (a <-> '(5,5)'::point)
+(6 rows)
+
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index 071f8a5268..c89e8e7409 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -276,3 +276,14 @@ from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
explain (costs off) select sub.unique1, stringu1 || random()::text
from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub
order by 1, 2;
+
+-- Incremental sort for not ordered indexes, but with AM order operator
+set enable_incremental_sort = on;
+-- table with GiST index supports closest points retrieval,
+-- but has not sorted index
+create table t (a point, b int);
+create index on t using gist(a);
+insert into t select point(mod(i, 7), mod(i, 11)), i from generate_series(1, 1000) s(i);
+analyze t;
+explain (costs off) select a, b, a <-> point(5, 5) dist from t order by dist, b limit 1;
+explain (costs off) select a, b, a <-> point(5, 5) dist from t order by dist, b desc limit 1;
On Sun, Jul 2, 2023 at 12:02 PM Miroslav Bendik <miroslav.bendik@gmail.com>
wrote:
Thanks, for suggestions.
On Sun 02. 07. 2023 at 10:18 Richard Guo <guofenglinux@gmail.com> wrote:
1. For comment "On success, the result list is ordered by pathkeys.", I
think it'd be more accurate if we say something like "On success, the
result list is ordered by pathkeys or a prefix list of pathkeys."
considering the possibility of incremental sort.2. The comment below is not true anymore.
/*
* Note: for any failure to match, we just return NIL immediately.
* There is no value in matching just some of the pathkeys.
*/
We should either remove it or change it to emphasize that we may return
a prefix of the pathkeys for incremental sort.Comments are updated now.
BTW, would you please add the patch to the CF to not lose track of it?
The v4 patch looks good to me (maybe some cosmetic tweaks are still
needed for the comments). I think it's now 'Ready for Committer'.
Thanks
Richard
On Tue, 4 Jul 2023 at 20:12, Richard Guo <guofenglinux@gmail.com> wrote:
The v4 patch looks good to me (maybe some cosmetic tweaks are still
needed for the comments). I think it's now 'Ready for Committer'.
I agree. I went and hit the comments with a large hammer and while
there also adjusted the regression tests. I didn't think having "t" as
a table name was a good idea as it seems like a name with a high risk
of conflicting with a concurrently running test. Also, there didn't
seem to be much need to insert data into that table as the tests
didn't query any of it.
The only other small tweak I made was to not call list_copy_head()
when the list does not need to be shortened. It's likely not that
important, but if the majority of cases are not partial matches, then
we'd otherwise be needlessly making copies of the list.
I pushed the adjusted patch.
David
On Tue, Jul 4, 2023 at 7:15 PM David Rowley <dgrowleyml@gmail.com> wrote:
On Tue, 4 Jul 2023 at 20:12, Richard Guo <guofenglinux@gmail.com> wrote:
The v4 patch looks good to me (maybe some cosmetic tweaks are still
needed for the comments). I think it's now 'Ready for Committer'.I agree. I went and hit the comments with a large hammer and while
there also adjusted the regression tests. I didn't think having "t" as
a table name was a good idea as it seems like a name with a high risk
of conflicting with a concurrently running test. Also, there didn't
seem to be much need to insert data into that table as the tests
didn't query any of it.The only other small tweak I made was to not call list_copy_head()
when the list does not need to be shortened. It's likely not that
important, but if the majority of cases are not partial matches, then
we'd otherwise be needlessly making copies of the list.I pushed the adjusted patch.
The adjustments improve the patch a lot. Thanks for adjusting and
pushing the patch.
Thanks
Richard
On 7/5/23 2:15 AM, Richard Guo wrote:
On Tue, Jul 4, 2023 at 7:15 PM David Rowley <dgrowleyml@gmail.com
<mailto:dgrowleyml@gmail.com>> wrote:On Tue, 4 Jul 2023 at 20:12, Richard Guo <guofenglinux@gmail.com
<mailto:guofenglinux@gmail.com>> wrote:The v4 patch looks good to me (maybe some cosmetic tweaks are still
needed for the comments). I think it's now 'Ready for Committer'.I agree. I went and hit the comments with a large hammer and while
there also adjusted the regression tests. I didn't think having "t" as
a table name was a good idea as it seems like a name with a high risk
of conflicting with a concurrently running test. Also, there didn't
seem to be much need to insert data into that table as the tests
didn't query any of it.The only other small tweak I made was to not call list_copy_head()
when the list does not need to be shortened. It's likely not that
important, but if the majority of cases are not partial matches, then
we'd otherwise be needlessly making copies of the list.I pushed the adjusted patch.
The adjustments improve the patch a lot. Thanks for adjusting and
pushing the patch.
Thanks for working on this! While it allows the planner to consider
choosing an incremental sort for indexes that implement
"amcanorderbyop", it also has a positive side-effect that the planner
will also consider choosing a plan for spawning parallel workers!
Because of that, I'd like to open the discussion that we consider
backpatching this. Currently, extensions that implement index access
methods (e.g. pgvector[1]https://github.com/pgvector/pgvector) that are built primarily around
"amcanorderbyop" are unable to get the planner to consider choosing a
parallel scan, i.e. at this point in "create_order_paths"[2]https://git.postgresql.org/gitweb/?p=postgresql.git;a=blob;f=src/backend/optimizer/plan/planner.c;#l5188:
/*
* If cheapest partial path doesn't need a sort, this is redundant
* with what's already been tried.
*/
if (!pathkeys_contained_in(root->sort_pathkeys,
cheapest_partial_path->pathkeys))
However, 625d5b3c does unlock this path for these types of indexes to
allow for a parallel index scan to be chosen, which would allow
extensions that implement a "amcanorderbyop" scan to use it. I would
argue that this is a bug, given we offer the ability for index access
methods to implement parallel index scans.
That said, I do think they may still need to be one planner tweak to
properly support parallel index scan in this case, as I have yet to see
costs generated where the parallel index scan is cheaper. However, I
have not yet narrowed what/where that is.
Thanks,
Jonathan
[1]: https://github.com/pgvector/pgvector
[2]: https://git.postgresql.org/gitweb/?p=postgresql.git;a=blob;f=src/backend/optimizer/plan/planner.c;#l5188
https://git.postgresql.org/gitweb/?p=postgresql.git;a=blob;f=src/backend/optimizer/plan/planner.c;#l5188