Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitbc37473

Browse files
david-rowleypull[bot]
authored andcommitted
Allow Incremental Sorts on GiST and SP-GiST indexes
Previously an "amcanorderbyop" index would only be used when the indexcould provide sorted results which satisfied all query_pathkeys. Herewe relax this so that we also allow these indexes to be considered by theplanner when they only provide partially sorted results. This allows theplanner to later consider making use of an Incremental Sort to satisfy theremaining pathkeys. This change is particularly useful for KNN-typequeries which contain a LIMIT clause and an additional ORDER BY clause fora non-indexed column.Author: Miroslav BendikReviewed-by: Richard Guo, David RowleyDiscussion:https://postgr.es/m/CAPoEpV0QYDtzjwamwWUBqyWpaCVbJV2d6qOD7Uy09bWn47PJtw%40mail.gmail.com
1 parentdb660eb commitbc37473

File tree

3 files changed

+77
-25
lines changed

3 files changed

+77
-25
lines changed

‎src/backend/optimizer/path/indxpath.c

Lines changed: 28 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -974,14 +974,20 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
974974
}
975975
elseif (index->amcanorderbyop&&pathkeys_possibly_useful)
976976
{
977-
/* see if we can generate ordering operators for query_pathkeys */
977+
/*
978+
* See if we can generate ordering operators for query_pathkeys or at
979+
* least some prefix thereof. Matching to just a prefix of the
980+
* query_pathkeys will allow an incremental sort to be considered on
981+
* the index's partially sorted results.
982+
*/
978983
match_pathkeys_to_index(index,root->query_pathkeys,
979984
&orderbyclauses,
980985
&orderbyclausecols);
981-
if (orderbyclauses)
986+
if (list_length(root->query_pathkeys)==list_length(orderbyclauses))
982987
useful_pathkeys=root->query_pathkeys;
983988
else
984-
useful_pathkeys=NIL;
989+
useful_pathkeys=list_copy_head(root->query_pathkeys,
990+
list_length(orderbyclauses));
985991
}
986992
else
987993
{
@@ -3051,24 +3057,24 @@ expand_indexqual_rowcompare(PlannerInfo *root,
30513057

30523058
/*
30533059
* match_pathkeys_to_index
3054-
*Test whether an index can produce output ordered according to the
3055-
*given pathkeys using "ordering operators".
3056-
*
3057-
* If it can, return a list of suitable ORDER BY expressions, each of the form
3058-
* "indexedcol operator pseudoconstant", along with an integer list of the
3059-
* index column numbers (zero based) that each clause would be used with.
3060-
* NIL lists are returned if the ordering is not achievable this way.
3061-
*
3062-
* On success, the result list is ordered by pathkeys, and in fact is
3063-
* one-to-one with the requested pathkeys.
3060+
*For the given 'index' and 'pathkeys', output a list of suitable ORDER
3061+
*BY expressions, each of the form "indexedcol operator pseudoconstant",
3062+
*along with an integer list of the index column numbers (zero based)
3063+
*that each clause would be used with.
3064+
*
3065+
* This attempts to find an ORDER BY and index column number for all items in
3066+
* the pathkey list, however, if we're unable to match any given pathkey to an
3067+
* index column, we return just the ones matched by the function so far. This
3068+
* allows callers who are interested in partial matches to get them. Callers
3069+
* can determine a partial match vs a full match by checking the outputted
3070+
* list lengths. A full match will have one item in the output lists for each
3071+
* item in the given 'pathkeys' list.
30643072
*/
30653073
staticvoid
30663074
match_pathkeys_to_index(IndexOptInfo*index,List*pathkeys,
30673075
List**orderby_clauses_p,
30683076
List**clause_columns_p)
30693077
{
3070-
List*orderby_clauses=NIL;
3071-
List*clause_columns=NIL;
30723078
ListCell*lc1;
30733079

30743080
*orderby_clauses_p=NIL;/* set default results */
@@ -3084,10 +3090,6 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
30843090
boolfound= false;
30853091
ListCell*lc2;
30863092

3087-
/*
3088-
* Note: for any failure to match, we just return NIL immediately.
3089-
* There is no value in matching just some of the pathkeys.
3090-
*/
30913093

30923094
/* Pathkey must request default sort order for the target opfamily */
30933095
if (pathkey->pk_strategy!=BTLessStrategyNumber||
@@ -3133,8 +3135,8 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
31333135
pathkey->pk_opfamily);
31343136
if (expr)
31353137
{
3136-
orderby_clauses=lappend(orderby_clauses,expr);
3137-
clause_columns=lappend_int(clause_columns,indexcol);
3138+
*orderby_clauses_p=lappend(*orderby_clauses_p,expr);
3139+
*clause_columns_p=lappend_int(*clause_columns_p,indexcol);
31383140
found= true;
31393141
break;
31403142
}
@@ -3144,12 +3146,13 @@ match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys,
31443146
break;
31453147
}
31463148

3147-
if (!found)/* fail if no match for this pathkey */
3149+
/*
3150+
* Return the matches found so far when this pathkey couldn't be
3151+
* matched to the index.
3152+
*/
3153+
if (!found)
31483154
return;
31493155
}
3150-
3151-
*orderby_clauses_p=orderby_clauses;/* success! */
3152-
*clause_columns_p=clause_columns;
31533156
}
31543157

31553158
/*

‎src/test/regress/expected/incremental_sort.out

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1660,3 +1660,36 @@ order by 1, 2;
16601660
-> Function Scan on generate_series
16611661
(7 rows)
16621662

1663+
reset enable_hashagg;
1664+
reset enable_seqscan;
1665+
reset enable_incremental_sort;
1666+
reset parallel_tuple_cost;
1667+
reset parallel_setup_cost;
1668+
reset min_parallel_table_scan_size;
1669+
reset min_parallel_index_scan_size;
1670+
-- Ensure incremental sorts work for amcanorderbyop type indexes
1671+
create table point_table (a point, b int);
1672+
create index point_table_a_idx on point_table using gist(a);
1673+
-- Ensure we get an incremental sort plan for both of the following queries
1674+
explain (costs off) select a, b, a <-> point(5, 5) dist from point_table order by dist, b limit 1;
1675+
QUERY PLAN
1676+
---------------------------------------------------------------
1677+
Limit
1678+
-> Incremental Sort
1679+
Sort Key: ((a <-> '(5,5)'::point)), b
1680+
Presorted Key: ((a <-> '(5,5)'::point))
1681+
-> Index Scan using point_table_a_idx on point_table
1682+
Order By: (a <-> '(5,5)'::point)
1683+
(6 rows)
1684+
1685+
explain (costs off) select a, b, a <-> point(5, 5) dist from point_table order by dist, b desc limit 1;
1686+
QUERY PLAN
1687+
---------------------------------------------------------------
1688+
Limit
1689+
-> Incremental Sort
1690+
Sort Key: ((a <-> '(5,5)'::point)), b DESC
1691+
Presorted Key: ((a <-> '(5,5)'::point))
1692+
-> Index Scan using point_table_a_idx on point_table
1693+
Order By: (a <-> '(5,5)'::point)
1694+
(6 rows)
1695+

‎src/test/regress/sql/incremental_sort.sql

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -276,3 +276,19 @@ from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
276276
explain (costs off)selectsub.unique1, stringu1|| random()::text
277277
from tenk1, lateral (selecttenk1.unique1from generate_series(1,1000))as sub
278278
order by1,2;
279+
280+
reset enable_hashagg;
281+
reset enable_seqscan;
282+
reset enable_incremental_sort;
283+
reset parallel_tuple_cost;
284+
reset parallel_setup_cost;
285+
reset min_parallel_table_scan_size;
286+
reset min_parallel_index_scan_size;
287+
288+
-- Ensure incremental sorts work for amcanorderbyop type indexes
289+
createtablepoint_table (apoint, bint);
290+
createindexpoint_table_a_idxon point_table using gist(a);
291+
292+
-- Ensure we get an incremental sort plan for both of the following queries
293+
explain (costs off)select a, b, a<->point(5,5) distfrom point_tableorder by dist, blimit1;
294+
explain (costs off)select a, b, a<->point(5,5) distfrom point_tableorder by dist, bdesclimit1;

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp