diff --git a/contrib/bloom/blutils.c b/contrib/bloom/blutils.c index 6458376..9bff793 100644 --- a/contrib/bloom/blutils.c +++ b/contrib/bloom/blutils.c @@ -109,7 +109,6 @@ blhandler(PG_FUNCTION_ARGS) amroutine->amstrategies = BLOOM_NSTRATEGIES; amroutine->amsupport = BLOOM_NPROC; amroutine->amcanorder = false; - amroutine->amcanorderbyop = false; amroutine->amcanbackward = false; amroutine->amcanunique = false; amroutine->amcanmulticol = true; @@ -143,6 +142,7 @@ blhandler(PG_FUNCTION_ARGS) amroutine->amestimateparallelscan = NULL; amroutine->aminitparallelscan = NULL; amroutine->amparallelrescan = NULL; + amroutine->ammatchorderby = NULL; PG_RETURN_POINTER(amroutine); } diff --git a/src/backend/access/brin/brin.c b/src/backend/access/brin/brin.c index 8f008dd..5cd06c7 100644 --- a/src/backend/access/brin/brin.c +++ b/src/backend/access/brin/brin.c @@ -88,7 +88,6 @@ brinhandler(PG_FUNCTION_ARGS) amroutine->amstrategies = 0; amroutine->amsupport = BRIN_LAST_OPTIONAL_PROCNUM; amroutine->amcanorder = false; - amroutine->amcanorderbyop = false; amroutine->amcanbackward = false; amroutine->amcanunique = false; amroutine->amcanmulticol = true; @@ -122,6 +121,7 @@ brinhandler(PG_FUNCTION_ARGS) amroutine->amestimateparallelscan = NULL; amroutine->aminitparallelscan = NULL; amroutine->amparallelrescan = NULL; + amroutine->ammatchorderby = NULL; PG_RETURN_POINTER(amroutine); } diff --git a/src/backend/access/gin/ginutil.c b/src/backend/access/gin/ginutil.c index afc2023..0f6714d 100644 --- a/src/backend/access/gin/ginutil.c +++ b/src/backend/access/gin/ginutil.c @@ -41,7 +41,6 @@ ginhandler(PG_FUNCTION_ARGS) amroutine->amstrategies = 0; amroutine->amsupport = GINNProcs; amroutine->amcanorder = false; - amroutine->amcanorderbyop = false; amroutine->amcanbackward = false; amroutine->amcanunique = false; amroutine->amcanmulticol = true; @@ -75,6 +74,7 @@ ginhandler(PG_FUNCTION_ARGS) amroutine->amestimateparallelscan = NULL; amroutine->aminitparallelscan = NULL; amroutine->amparallelrescan = NULL; + amroutine->ammatchorderby = NULL; PG_RETURN_POINTER(amroutine); } diff --git a/src/backend/access/gist/gist.c b/src/backend/access/gist/gist.c index b75b3a8..77ca187 100644 --- a/src/backend/access/gist/gist.c +++ b/src/backend/access/gist/gist.c @@ -18,6 +18,7 @@ #include "access/gistscan.h" #include "catalog/pg_collation.h" #include "miscadmin.h" +#include "optimizer/paths.h" #include "storage/lmgr.h" #include "storage/predicate.h" #include "nodes/execnodes.h" @@ -64,7 +65,6 @@ gisthandler(PG_FUNCTION_ARGS) amroutine->amstrategies = 0; amroutine->amsupport = GISTNProcs; amroutine->amcanorder = false; - amroutine->amcanorderbyop = true; amroutine->amcanbackward = false; amroutine->amcanunique = false; amroutine->amcanmulticol = true; @@ -98,6 +98,7 @@ gisthandler(PG_FUNCTION_ARGS) amroutine->amestimateparallelscan = NULL; amroutine->aminitparallelscan = NULL; amroutine->amparallelrescan = NULL; + amroutine->ammatchorderby = match_orderbyop_pathkeys; PG_RETURN_POINTER(amroutine); } diff --git a/src/backend/access/hash/hash.c b/src/backend/access/hash/hash.c index f1f01a0..bb5c6a1 100644 --- a/src/backend/access/hash/hash.c +++ b/src/backend/access/hash/hash.c @@ -59,7 +59,6 @@ hashhandler(PG_FUNCTION_ARGS) amroutine->amstrategies = HTMaxStrategyNumber; amroutine->amsupport = HASHNProcs; amroutine->amcanorder = false; - amroutine->amcanorderbyop = false; amroutine->amcanbackward = true; amroutine->amcanunique = false; amroutine->amcanmulticol = false; @@ -93,6 +92,7 @@ hashhandler(PG_FUNCTION_ARGS) amroutine->amestimateparallelscan = NULL; amroutine->aminitparallelscan = NULL; amroutine->amparallelrescan = NULL; + amroutine->ammatchorderby = NULL; PG_RETURN_POINTER(amroutine); } diff --git a/src/backend/access/nbtree/nbtree.c b/src/backend/access/nbtree/nbtree.c index 98917de..c56ee5e 100644 --- a/src/backend/access/nbtree/nbtree.c +++ b/src/backend/access/nbtree/nbtree.c @@ -110,7 +110,6 @@ bthandler(PG_FUNCTION_ARGS) amroutine->amstrategies = BTMaxStrategyNumber; amroutine->amsupport = BTNProcs; amroutine->amcanorder = true; - amroutine->amcanorderbyop = false; amroutine->amcanbackward = true; amroutine->amcanunique = true; amroutine->amcanmulticol = true; @@ -144,6 +143,7 @@ bthandler(PG_FUNCTION_ARGS) amroutine->amestimateparallelscan = btestimateparallelscan; amroutine->aminitparallelscan = btinitparallelscan; amroutine->amparallelrescan = btparallelrescan; + amroutine->ammatchorderby = NULL; PG_RETURN_POINTER(amroutine); } diff --git a/src/backend/access/spgist/spgutils.c b/src/backend/access/spgist/spgutils.c index 8e63c1f..37de33c 100644 --- a/src/backend/access/spgist/spgutils.c +++ b/src/backend/access/spgist/spgutils.c @@ -22,6 +22,7 @@ #include "access/transam.h" #include "access/xact.h" #include "catalog/pg_amop.h" +#include "optimizer/paths.h" #include "storage/bufmgr.h" #include "storage/indexfsm.h" #include "storage/lmgr.h" @@ -31,7 +32,6 @@ #include "utils/lsyscache.h" #include "utils/syscache.h" - /* * SP-GiST handler function: return IndexAmRoutine with access method parameters * and callbacks. @@ -44,7 +44,6 @@ spghandler(PG_FUNCTION_ARGS) amroutine->amstrategies = 0; amroutine->amsupport = SPGISTNProc; amroutine->amcanorder = false; - amroutine->amcanorderbyop = true; amroutine->amcanbackward = false; amroutine->amcanunique = false; amroutine->amcanmulticol = false; @@ -78,6 +77,7 @@ spghandler(PG_FUNCTION_ARGS) amroutine->amestimateparallelscan = NULL; amroutine->aminitparallelscan = NULL; amroutine->amparallelrescan = NULL; + amroutine->ammatchorderby = match_orderbyop_pathkeys; PG_RETURN_POINTER(amroutine); } diff --git a/src/backend/commands/opclasscmds.c b/src/backend/commands/opclasscmds.c index 5d73848..a595c79 100644 --- a/src/backend/commands/opclasscmds.c +++ b/src/backend/commands/opclasscmds.c @@ -1097,7 +1097,7 @@ assignOperTypes(OpFamilyMember *member, Oid amoid, Oid typeoid) */ IndexAmRoutine *amroutine = GetIndexAmRoutineByAmId(amoid, false); - if (!amroutine->amcanorderbyop) + if (!amroutine->ammatchorderby) ereport(ERROR, (errcode(ERRCODE_INVALID_OBJECT_DEFINITION), errmsg("access method \"%s\" does not support ordering operators", diff --git a/src/backend/executor/nodeIndexscan.c b/src/backend/executor/nodeIndexscan.c index 324356e..805abd2 100644 --- a/src/backend/executor/nodeIndexscan.c +++ b/src/backend/executor/nodeIndexscan.c @@ -198,7 +198,7 @@ IndexNextWithReorder(IndexScanState *node) * with just Asserting here because the system will not try to run the * plan backwards if ExecSupportsBackwardScan() says it won't work. * Currently, that is guaranteed because no index AMs support both - * amcanorderbyop and amcanbackward; if any ever do, + * ammatchorderby and amcanbackward; if any ever do, * ExecSupportsBackwardScan() will need to consider indexorderbys * explicitly. */ @@ -1148,7 +1148,7 @@ ExecInitIndexScan(IndexScan *node, EState *estate, int eflags) * 5. NullTest ("indexkey IS NULL/IS NOT NULL"). We just fill in the * ScanKey properly. * - * This code is also used to prepare ORDER BY expressions for amcanorderbyop + * This code is also used to prepare ORDER BY expressions for ammatchorderby * indexes. The behavior is exactly the same, except that we have to look up * the operator differently. Note that only cases 1 and 2 are currently * possible for ORDER BY. diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 3434219..6cf0b0d 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -17,6 +17,7 @@ #include +#include "access/amapi.h" #include "access/stratnum.h" #include "access/sysattr.h" #include "catalog/pg_am.h" @@ -182,8 +183,9 @@ static IndexClause *expand_indexqual_rowcompare(RestrictInfo *rinfo, Oid expr_op, bool var_on_left); static void match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys, + List *index_clauses, List **orderby_clauses_p, - List **clause_columns_p); + List **orderby_clause_columns_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, @@ -1001,10 +1003,11 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, orderbyclauses = NIL; orderbyclausecols = NIL; } - else if (index->amcanorderbyop && pathkeys_possibly_useful) + else if (index->ammatchorderby && pathkeys_possibly_useful) { /* see if we can generate ordering operators for query_pathkeys */ match_pathkeys_to_index(index, root->query_pathkeys, + index_clauses, &orderbyclauses, &orderbyclausecols); if (orderbyclauses) @@ -2927,6 +2930,113 @@ match_rowcompare_to_indexcol(RestrictInfo *rinfo, return NULL; } +/**************************************************************************** + * ---- ROUTINES TO CHECK ORDERING OPERATORS ---- + ****************************************************************************/ + +/* + * Try to match order-by-operator pathkey to the specified index column + * (*indexcol_p >= 0) or to all index columns (*indexcol_p < 0). + * + * Returned matched index clause exression. + * Number of matched index column is returned in *indexcol_p. + */ +Expr * +match_orderbyop_pathkey(IndexOptInfo *index, PathKey *pathkey, int *indexcol_p) +{ + ListCell *lc; + + /* Pathkey must request default sort order for the target opfamily */ + if (pathkey->pk_strategy != BTLessStrategyNumber || + pathkey->pk_nulls_first) + return NULL; + + /* If eclass is volatile, no hope of using an indexscan */ + if (pathkey->pk_eclass->ec_has_volatile) + return NULL; + + /* + * Try to match eclass member expression(s) to index. Note that child EC + * members are considered, but only when they belong to the target + * relation. (Unlike regular members, the same expression could be a + * child member of more than one EC. Therefore, the same index could be + * considered to match more than one pathkey list, which is OK here. See + * also get_eclass_for_sort_expr.) + */ + foreach(lc, pathkey->pk_eclass->ec_members) + { + EquivalenceMember *member = lfirst_node(EquivalenceMember, lc); + Expr *expr; + + /* No possibility of match if it references other relations. */ + if (!bms_equal(member->em_relids, index->rel->relids)) + continue; + + /* If *indexcol_p is non-negative then try to match only to it. */ + if (*indexcol_p >= 0) + { + expr = match_clause_to_ordering_op(index, *indexcol_p, + member->em_expr, + pathkey->pk_opfamily); + + if (expr) + return expr; /* don't want to look at remaining members */ + } + else + { + int indexcol; + + /* + * We allow any column of this index to match each pathkey; they + * don't have to match left-to-right as you might expect. + */ + for (indexcol = 0; indexcol < index->nkeycolumns; indexcol++) + { + expr = match_clause_to_ordering_op(index, indexcol, + member->em_expr, + pathkey->pk_opfamily); + if (expr) + { + *indexcol_p = indexcol; + return expr; /* don't want to look at remaining members */ + } + } + } + } + + return NULL; +} + +/* Try to match order-by-operator pathkeys to any index columns. */ +bool +match_orderbyop_pathkeys(IndexOptInfo *index, List *pathkeys, + List *index_clauses, List **orderby_clauses_p, + List **orderby_clausecols_p) +{ + ListCell *lc; + + foreach(lc, pathkeys) + { + PathKey *pathkey = lfirst_node(PathKey, lc); + Expr *expr; + int indexcol = -1; /* match all index columns */ + + expr = match_orderbyop_pathkey(index, pathkey, &indexcol); + + /* + * Note: for any failure to match, we just return NIL immediately. + * There is no value in matching just some of the pathkeys. + */ + if (!expr) + return false; + + *orderby_clauses_p = lappend(*orderby_clauses_p, expr); + *orderby_clausecols_p = lappend_int(*orderby_clausecols_p, indexcol); + } + + return true; /* success */ +} + /* * expand_indexqual_rowcompare --- expand a single indexqual condition * that is a RowCompareExpr @@ -3183,92 +3293,31 @@ expand_indexqual_rowcompare(RestrictInfo *rinfo, */ static void match_pathkeys_to_index(IndexOptInfo *index, List *pathkeys, + List *index_clauses, List **orderby_clauses_p, - List **clause_columns_p) + List **orderby_clause_columns_p) { List *orderby_clauses = NIL; - List *clause_columns = NIL; - ListCell *lc1; - - *orderby_clauses_p = NIL; /* set default results */ - *clause_columns_p = NIL; + List *orderby_clause_columns = NIL; + ammatchorderby_function ammatchorderby = + (ammatchorderby_function) index->ammatchorderby; - /* Only indexes with the amcanorderbyop property are interesting here */ - if (!index->amcanorderbyop) - return; - - foreach(lc1, pathkeys) + /* Only indexes with the ammatchorderby function are interesting here */ + if (ammatchorderby && + ammatchorderby(index, pathkeys, index_clauses, + &orderby_clauses, &orderby_clause_columns)) { - PathKey *pathkey = (PathKey *) lfirst(lc1); - bool found = false; - ListCell *lc2; - - /* - * Note: for any failure to match, we just return NIL immediately. - * There is no value in matching just some of the pathkeys. - */ - - /* Pathkey must request default sort order for the target opfamily */ - if (pathkey->pk_strategy != BTLessStrategyNumber || - pathkey->pk_nulls_first) - return; - - /* If eclass is volatile, no hope of using an indexscan */ - if (pathkey->pk_eclass->ec_has_volatile) - return; - - /* - * Try to match eclass member expression(s) to index. Note that child - * EC members are considered, but only when they belong to the target - * relation. (Unlike regular members, the same expression could be a - * child member of more than one EC. Therefore, the same index could - * be considered to match more than one pathkey list, which is OK - * here. See also get_eclass_for_sort_expr.) - */ - foreach(lc2, pathkey->pk_eclass->ec_members) - { - EquivalenceMember *member = (EquivalenceMember *) lfirst(lc2); - int indexcol; - - /* No possibility of match if it references other relations */ - if (!bms_equal(member->em_relids, index->rel->relids)) - continue; + Assert(list_length(pathkeys) == list_length(orderby_clauses)); + Assert(list_length(pathkeys) == list_length(orderby_clause_columns)); - /* - * We allow any column of the index to match each pathkey; they - * don't have to match left-to-right as you might expect. This is - * correct for GiST, and it doesn't matter for SP-GiST because - * that doesn't handle multiple columns anyway, and no other - * existing AMs support amcanorderbyop. We might need different - * logic in future for other implementations. - */ - for (indexcol = 0; indexcol < index->nkeycolumns; indexcol++) - { - Expr *expr; - - expr = match_clause_to_ordering_op(index, - indexcol, - member->em_expr, - pathkey->pk_opfamily); - if (expr) - { - orderby_clauses = lappend(orderby_clauses, expr); - clause_columns = lappend_int(clause_columns, indexcol); - found = true; - break; - } - } - - if (found) /* don't want to look at remaining members */ - break; - } - - if (!found) /* fail if no match for this pathkey */ - return; + *orderby_clauses_p = orderby_clauses; /* success! */ + *orderby_clause_columns_p = orderby_clause_columns; + } + else + { + *orderby_clauses_p = NIL; /* set default results */ + *orderby_clause_columns_p = NIL; } - - *orderby_clauses_p = orderby_clauses; /* success! */ - *clause_columns_p = clause_columns; } /* diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c index d6dc83c..2d81fd1 100644 --- a/src/backend/optimizer/util/plancat.c +++ b/src/backend/optimizer/util/plancat.c @@ -267,7 +267,7 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent, /* We copy just the fields we need, not all of rd_indam */ amroutine = indexRelation->rd_indam; - info->amcanorderbyop = amroutine->amcanorderbyop; + info->ammatchorderby = amroutine->ammatchorderby; info->amoptionalkey = amroutine->amoptionalkey; info->amsearcharray = amroutine->amsearcharray; info->amsearchnulls = amroutine->amsearchnulls; diff --git a/src/backend/utils/adt/amutils.c b/src/backend/utils/adt/amutils.c index 060ffe5..3907065 100644 --- a/src/backend/utils/adt/amutils.c +++ b/src/backend/utils/adt/amutils.c @@ -298,7 +298,7 @@ indexam_property(FunctionCallInfo fcinfo, * a nonkey column, and null otherwise (meaning we don't * know). */ - if (!iskey || !routine->amcanorderbyop) + if (!iskey || !routine->ammatchorderby) { res = false; isnull = false; diff --git a/src/include/access/amapi.h b/src/include/access/amapi.h index 653ddc9..d8fb7d3 100644 --- a/src/include/access/amapi.h +++ b/src/include/access/amapi.h @@ -21,6 +21,9 @@ */ struct PlannerInfo; struct IndexPath; +struct IndexOptInfo; +struct PathKey; +struct Expr; /* Likewise, this file shouldn't depend on execnodes.h. */ struct IndexInfo; @@ -140,6 +143,13 @@ typedef void (*ammarkpos_function) (IndexScanDesc scan); /* restore marked scan position */ typedef void (*amrestrpos_function) (IndexScanDesc scan); +/* does AM support ORDER BY result of an operator on indexed column? */ +typedef bool (*ammatchorderby_function) (struct IndexOptInfo *index, + List *pathkeys, + List *index_clauses, + List **orderby_clauses_p, + List **orderby_clause_columns_p); + /* * Callback function signatures - for parallel index scans. */ @@ -170,8 +180,6 @@ typedef struct IndexAmRoutine uint16 amsupport; /* does AM support ORDER BY indexed column's value? */ bool amcanorder; - /* does AM support ORDER BY result of an operator on indexed column? */ - bool amcanorderbyop; /* does AM support backward scanning? */ bool amcanbackward; /* does AM support UNIQUE indexes? */ @@ -221,6 +229,7 @@ typedef struct IndexAmRoutine amendscan_function amendscan; ammarkpos_function ammarkpos; /* can be NULL */ amrestrpos_function amrestrpos; /* can be NULL */ + ammatchorderby_function ammatchorderby; /* can be NULL */ /* interface functions to support parallel index scans */ amestimateparallelscan_function amestimateparallelscan; /* can be NULL */ diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index a008ae0..4680cb8 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -814,7 +814,6 @@ struct IndexOptInfo bool hypothetical; /* true if index doesn't really exist */ /* Remaining fields are copied from the index AM's API struct: */ - bool amcanorderbyop; /* does AM support order by operator result? */ bool amoptionalkey; /* can query omit key for the first column? */ bool amsearcharray; /* can AM handle ScalarArrayOpExpr quals? */ bool amsearchnulls; /* can AM search for NULL/NOT NULL entries? */ @@ -823,6 +822,12 @@ struct IndexOptInfo bool amcanparallel; /* does AM support parallel scan? */ /* Rather than include amapi.h here, we declare amcostestimate like this */ void (*amcostestimate) (); /* AM's cost estimator */ + /* AM order-by match function */ + bool (*ammatchorderby) (struct IndexOptInfo *index, + List *pathkeys, + List *index_clause_columns, + List **orderby_clauses_p, + List **orderby_clause_columns_p); }; /* @@ -1133,7 +1138,7 @@ typedef struct Path * An empty list implies a full index scan. * * 'indexorderbys', if not NIL, is a list of ORDER BY expressions that have - * been found to be usable as ordering operators for an amcanorderbyop index. + * been found to be usable as ordering operators for an ammatchorderby index. * The list must match the path's pathkeys, ie, one expression per pathkey * in the same order. These are not RestrictInfos, just bare expressions, * since they generally won't yield booleans. It's guaranteed that each diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h index 6d087c2..bd6ce97 100644 --- a/src/include/nodes/plannodes.h +++ b/src/include/nodes/plannodes.h @@ -388,7 +388,7 @@ typedef struct SampleScan * indexorderbyops is a list of the OIDs of the operators used to sort the * ORDER BY expressions. This is used together with indexorderbyorig to * recheck ordering at run time. (Note that indexorderby, indexorderbyorig, - * and indexorderbyops are used for amcanorderbyop cases, not amcanorder.) + * and indexorderbyops are used for ammatchorderby cases, not amcanorder.) * * indexorderdir specifies the scan ordering, for indexscans on amcanorder * indexes (for other indexes it should be "don't care"). diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index 040335a..e9f4f75 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -79,6 +79,11 @@ extern bool indexcol_is_bool_constant_for_query(IndexOptInfo *index, extern bool match_index_to_operand(Node *operand, int indexcol, IndexOptInfo *index); extern void check_index_predicates(PlannerInfo *root, RelOptInfo *rel); +extern Expr *match_orderbyop_pathkey(IndexOptInfo *index, PathKey *pathkey, + int *indexcol_p); +extern bool match_orderbyop_pathkeys(IndexOptInfo *index, List *pathkeys, + List *index_clauses, List **orderby_clauses_p, + List **orderby_clause_columns_p); /* * tidpath.h