From a8025f544854ad8b865c6b4509030ee84aa8f4a0 Mon Sep 17 00:00:00 2001 From: Peter Eisentraut Date: Sun, 6 Apr 2025 14:43:51 +0200 Subject: [PATCH] Relax ordering-related hardcoded btree requirements in planning There were several places in ordering-related planning where a requirement for btree was hardcoded but an amcanorder index could suffice. This fixes that. We just need to do the necessary mapping between strategy numbers and compare types and adjust some related APIs so that this works independent of btree strategy numbers. For instance, non-btree amcanorder indexes can now be used to support sorting and merge joins. Also, predtest.c works independent of btree strategy numbers now. To avoid performance regressions, some details on btree and other built-in index types are still hardcoded as shortcuts, but other index types now have access to the same features by providing the required flags and callbacks. Author: Mark Dilger Co-authored-by: Peter Eisentraut Discussion: https://www.postgresql.org/message-id/flat/E72EAA49-354D-4C2E-8EB9-255197F55330@enterprisedb.com --- src/backend/access/index/amapi.c | 10 ++ src/backend/executor/nodeMergejoin.c | 2 +- src/backend/optimizer/path/allpaths.c | 28 ++-- src/backend/optimizer/path/equivclass.c | 3 +- src/backend/optimizer/path/pathkeys.c | 22 ++-- src/backend/optimizer/plan/createplan.c | 10 +- src/backend/optimizer/util/plancat.c | 38 +++--- src/backend/optimizer/util/predtest.c | 122 +++++++++--------- src/backend/parser/parse_clause.c | 4 +- src/backend/parser/parse_expr.c | 34 ++--- src/backend/utils/adt/selfuncs.c | 62 +++++---- src/backend/utils/cache/lsyscache.c | 165 ++++++++++++++++-------- src/backend/utils/sort/sortsupport.c | 6 +- src/include/utils/lsyscache.h | 14 +- src/include/utils/selfuncs.h | 2 +- src/tools/pgindent/typedefs.list | 2 +- 16 files changed, 298 insertions(+), 226 deletions(-) diff --git a/src/backend/access/index/amapi.c b/src/backend/access/index/amapi.c index d6b8dad4d52..f0f4f974bce 100644 --- a/src/backend/access/index/amapi.c +++ b/src/backend/access/index/amapi.c @@ -120,6 +120,11 @@ IndexAmTranslateStrategy(StrategyNumber strategy, Oid amoid, Oid opfamily, bool CompareType result; IndexAmRoutine *amroutine; + /* shortcut for common case */ + if (amoid == BTREE_AM_OID && + (strategy > InvalidStrategy && strategy <= BTMaxStrategyNumber)) + return (CompareType) strategy; + amroutine = GetIndexAmRoutineByAmId(amoid, false); if (amroutine->amtranslatestrategy) result = amroutine->amtranslatestrategy(strategy, opfamily); @@ -145,6 +150,11 @@ IndexAmTranslateCompareType(CompareType cmptype, Oid amoid, Oid opfamily, bool m StrategyNumber result; IndexAmRoutine *amroutine; + /* shortcut for common case */ + if (amoid == BTREE_AM_OID && + (cmptype > COMPARE_INVALID && cmptype <= COMPARE_GT)) + return (StrategyNumber) cmptype; + amroutine = GetIndexAmRoutineByAmId(amoid, false); if (amroutine->amtranslatecmptype) result = amroutine->amtranslatecmptype(cmptype, opfamily); diff --git a/src/backend/executor/nodeMergejoin.c b/src/backend/executor/nodeMergejoin.c index f70239a2c9d..a233313128a 100644 --- a/src/backend/executor/nodeMergejoin.c +++ b/src/backend/executor/nodeMergejoin.c @@ -220,7 +220,7 @@ MJExamineQuals(List *mergeclauses, &op_strategy, &op_lefttype, &op_righttype); - if (op_strategy != BTEqualStrategyNumber) /* should not happen */ + if (IndexAmTranslateStrategy(op_strategy, get_opfamily_method(opfamily), opfamily, true) != COMPARE_EQ) /* should not happen */ elog(ERROR, "cannot merge using non-equality operator %u", qual->opno); diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index df3453f99f0..905250b3325 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -2313,16 +2313,15 @@ find_window_run_conditions(Query *subquery, RangeTblEntry *rte, Index rti, runopexpr = NULL; runoperator = InvalidOid; - opinfos = get_op_btree_interpretation(opexpr->opno); + opinfos = get_op_index_interpretation(opexpr->opno); foreach(lc, opinfos) { - OpBtreeInterpretation *opinfo = (OpBtreeInterpretation *) lfirst(lc); - int strategy = opinfo->strategy; + OpIndexInterpretation *opinfo = (OpIndexInterpretation *) lfirst(lc); + CompareType cmptype = opinfo->cmptype; /* handle < / <= */ - if (strategy == BTLessStrategyNumber || - strategy == BTLessEqualStrategyNumber) + if (cmptype == COMPARE_LT || cmptype == COMPARE_LE) { /* * < / <= is supported for monotonically increasing functions in @@ -2339,8 +2338,7 @@ find_window_run_conditions(Query *subquery, RangeTblEntry *rte, Index rti, break; } /* handle > / >= */ - else if (strategy == BTGreaterStrategyNumber || - strategy == BTGreaterEqualStrategyNumber) + else if (cmptype == COMPARE_GT || cmptype == COMPARE_GE) { /* * > / >= is supported for monotonically decreasing functions in @@ -2357,9 +2355,9 @@ find_window_run_conditions(Query *subquery, RangeTblEntry *rte, Index rti, break; } /* handle = */ - else if (strategy == BTEqualStrategyNumber) + else if (cmptype == COMPARE_EQ) { - int16 newstrategy; + CompareType newcmptype; /* * When both monotonically increasing and decreasing then the @@ -2383,19 +2381,19 @@ find_window_run_conditions(Query *subquery, RangeTblEntry *rte, Index rti, * below the value in the equality condition. */ if (res->monotonic & MONOTONICFUNC_INCREASING) - newstrategy = wfunc_left ? BTLessEqualStrategyNumber : BTGreaterEqualStrategyNumber; + newcmptype = wfunc_left ? COMPARE_LE : COMPARE_GE; else - newstrategy = wfunc_left ? BTGreaterEqualStrategyNumber : BTLessEqualStrategyNumber; + newcmptype = wfunc_left ? COMPARE_GE : COMPARE_LE; /* We must keep the original equality qual */ *keep_original = true; runopexpr = opexpr; /* determine the operator to use for the WindowFuncRunCondition */ - runoperator = get_opfamily_member(opinfo->opfamily_id, - opinfo->oplefttype, - opinfo->oprighttype, - newstrategy); + runoperator = get_opfamily_member_for_cmptype(opinfo->opfamily_id, + opinfo->oplefttype, + opinfo->oprighttype, + newcmptype); break; } } diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c index 9cd54c573a8..5fb2cf0daf8 100644 --- a/src/backend/optimizer/path/equivclass.c +++ b/src/backend/optimizer/path/equivclass.c @@ -1845,8 +1845,7 @@ select_equality_operator(EquivalenceClass *ec, Oid lefttype, Oid righttype) Oid opfamily = lfirst_oid(lc); Oid opno; - opno = get_opfamily_member(opfamily, lefttype, righttype, - BTEqualStrategyNumber); + opno = get_opfamily_member_for_cmptype(opfamily, lefttype, righttype, COMPARE_EQ); if (!OidIsValid(opno)) continue; /* If no barrier quals in query, don't worry about leaky operators */ diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index 6fac08cb0d9..981802d7b9d 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -219,13 +219,13 @@ make_pathkey_from_sortinfo(PlannerInfo *root, * more than one opfamily. So we have to look up the opfamily's equality * operator and get its membership. */ - equality_op = get_opfamily_member(opfamily, - opcintype, - opcintype, - BTEqualStrategyNumber); + equality_op = get_opfamily_member_for_cmptype(opfamily, + opcintype, + opcintype, + COMPARE_EQ); if (!OidIsValid(equality_op)) /* shouldn't happen */ elog(ERROR, "missing operator %d(%u,%u) in opfamily %u", - BTEqualStrategyNumber, opcintype, opcintype, opfamily); + COMPARE_EQ, opcintype, opcintype, opfamily); opfamilies = get_mergejoin_opfamilies(equality_op); if (!opfamilies) /* certainly should find some */ elog(ERROR, "could not find opfamilies for equality operator %u", @@ -264,11 +264,11 @@ make_pathkey_from_sortop(PlannerInfo *root, Oid opfamily, opcintype, collation; - int16 strategy; + CompareType cmptype; /* Find the operator in pg_amop --- failure shouldn't happen */ if (!get_ordering_op_properties(ordering_op, - &opfamily, &opcintype, &strategy)) + &opfamily, &opcintype, &cmptype)) elog(ERROR, "operator %u is not a valid ordering operator", ordering_op); @@ -1006,12 +1006,12 @@ build_expression_pathkey(PlannerInfo *root, List *pathkeys; Oid opfamily, opcintype; - int16 strategy; + CompareType cmptype; PathKey *cpathkey; /* Find the operator in pg_amop --- failure shouldn't happen */ if (!get_ordering_op_properties(opno, - &opfamily, &opcintype, &strategy)) + &opfamily, &opcintype, &cmptype)) elog(ERROR, "operator %u is not a valid ordering operator", opno); @@ -1020,8 +1020,8 @@ build_expression_pathkey(PlannerInfo *root, opfamily, opcintype, exprCollation((Node *) expr), - (strategy == BTGreaterStrategyNumber), - (strategy == BTGreaterStrategyNumber), + (cmptype == COMPARE_GT), + (cmptype == COMPARE_GT), 0, rel, create_it); diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index 359db4ba9dd..a8f22a8c154 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -6893,13 +6893,13 @@ make_unique_from_pathkeys(Plan *lefttree, List *pathkeys, int numCols) * Look up the correct equality operator from the PathKey's slightly * abstracted representation. */ - eqop = get_opfamily_member(pathkey->pk_opfamily, - pk_datatype, - pk_datatype, - BTEqualStrategyNumber); + eqop = get_opfamily_member_for_cmptype(pathkey->pk_opfamily, + pk_datatype, + pk_datatype, + COMPARE_EQ); if (!OidIsValid(eqop)) /* should not happen */ elog(ERROR, "missing operator %d(%u,%u) in opfamily %u", - BTEqualStrategyNumber, pk_datatype, pk_datatype, + COMPARE_EQ, pk_datatype, pk_datatype, pathkey->pk_opfamily); uniqColIdx[keyno] = tle->resno; diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c index 441684a72b1..67d879be8b8 100644 --- a/src/backend/optimizer/util/plancat.c +++ b/src/backend/optimizer/util/plancat.c @@ -365,14 +365,10 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent, * Since "<" uniquely defines the behavior of a sort * order, this is a sufficient test. * - * XXX This method is rather slow and also requires the - * undesirable assumption that the other index AM numbers - * its strategies the same as btree. It'd be better to - * have a way to explicitly declare the corresponding - * btree opfamily for each opfamily of the other index - * type. But given the lack of current or foreseeable - * amcanorder index types, it's not worth expending more - * effort on now. + * XXX This method is rather slow and complicated. It'd + * be better to have a way to explicitly declare the + * corresponding btree opfamily for each opfamily of the + * other index type. */ info->sortopfamily = (Oid *) palloc(sizeof(Oid) * nkeycolumns); info->reverse_sort = (bool *) palloc(sizeof(bool) * nkeycolumns); @@ -382,27 +378,27 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent, { int16 opt = indexRelation->rd_indoption[i]; Oid ltopr; - Oid btopfamily; - Oid btopcintype; - int16 btstrategy; + Oid opfamily; + Oid opcintype; + CompareType cmptype; info->reverse_sort[i] = (opt & INDOPTION_DESC) != 0; info->nulls_first[i] = (opt & INDOPTION_NULLS_FIRST) != 0; - ltopr = get_opfamily_member(info->opfamily[i], - info->opcintype[i], - info->opcintype[i], - BTLessStrategyNumber); + ltopr = get_opfamily_member_for_cmptype(info->opfamily[i], + info->opcintype[i], + info->opcintype[i], + COMPARE_LT); if (OidIsValid(ltopr) && get_ordering_op_properties(ltopr, - &btopfamily, - &btopcintype, - &btstrategy) && - btopcintype == info->opcintype[i] && - btstrategy == BTLessStrategyNumber) + &opfamily, + &opcintype, + &cmptype) && + opcintype == info->opcintype[i] && + cmptype == COMPARE_LT) { /* Successful mapping */ - info->sortopfamily[i] = btopfamily; + info->sortopfamily[i] = opfamily; } else { diff --git a/src/backend/optimizer/util/predtest.c b/src/backend/optimizer/util/predtest.c index b76fc81b08d..ac28573cd0a 100644 --- a/src/backend/optimizer/util/predtest.c +++ b/src/backend/optimizer/util/predtest.c @@ -1605,36 +1605,36 @@ clause_is_strict_for(Node *clause, Node *subexpr, bool allow_false) /* - * Define "operator implication tables" for btree operators ("strategies"), + * Define "operator implication tables" for index operators ("cmptypes"), * and similar tables for refutation. * - * The strategy numbers defined by btree indexes (see access/stratnum.h) are: - * 1 < 2 <= 3 = 4 >= 5 > + * The row compare numbers defined by indexes (see access/cmptype.h) are: + * 1 < 2 <= 3 = 4 >= 5 > 6 <> * and in addition we use 6 to represent <>. <> is not a btree-indexable * operator, but we assume here that if an equality operator of a btree * opfamily has a negator operator, the negator behaves as <> for the opfamily. - * (This convention is also known to get_op_btree_interpretation().) + * (This convention is also known to get_op_index_interpretation().) * - * BT_implies_table[] and BT_refutes_table[] are used for cases where we have + * RC_implies_table[] and RC_refutes_table[] are used for cases where we have * two identical subexpressions and we want to know whether one operator * expression implies or refutes the other. That is, if the "clause" is * EXPR1 clause_op EXPR2 and the "predicate" is EXPR1 pred_op EXPR2 for the * same two (immutable) subexpressions: - * BT_implies_table[clause_op-1][pred_op-1] + * RC_implies_table[clause_op-1][pred_op-1] * is true if the clause implies the predicate - * BT_refutes_table[clause_op-1][pred_op-1] + * RC_refutes_table[clause_op-1][pred_op-1] * is true if the clause refutes the predicate - * where clause_op and pred_op are strategy numbers (from 1 to 6) in the - * same btree opfamily. For example, "x < y" implies "x <= y" and refutes + * where clause_op and pred_op are cmptype numbers (from 1 to 6) in the + * same opfamily. For example, "x < y" implies "x <= y" and refutes * "x > y". * - * BT_implic_table[] and BT_refute_table[] are used where we have two + * RC_implic_table[] and RC_refute_table[] are used where we have two * constants that we need to compare. The interpretation of: * - * test_op = BT_implic_table[clause_op-1][pred_op-1] + * test_op = RC_implic_table[clause_op-1][pred_op-1] * - * where test_op, clause_op and pred_op are strategy numbers (from 1 to 6) - * of btree operators, is as follows: + * where test_op, clause_op and pred_op are cmptypes (from 1 to 6) + * of index operators, is as follows: * * If you know, for some EXPR, that "EXPR clause_op CONST1" is true, and you * want to determine whether "EXPR pred_op CONST2" must also be true, then @@ -1645,7 +1645,7 @@ clause_is_strict_for(Node *clause, Node *subexpr, bool allow_false) * For example, if clause is "Quantity > 10" and pred is "Quantity > 5" * then we test "5 <= 10" which evals to true, so clause implies pred. * - * Similarly, the interpretation of a BT_refute_table entry is: + * Similarly, the interpretation of a RC_refute_table entry is: * * If you know, for some EXPR, that "EXPR clause_op CONST1" is true, and you * want to determine whether "EXPR pred_op CONST2" must be false, then @@ -1659,17 +1659,17 @@ clause_is_strict_for(Node *clause, Node *subexpr, bool allow_false) * An entry where test_op == 0 means the implication cannot be determined. */ -#define BTLT BTLessStrategyNumber -#define BTLE BTLessEqualStrategyNumber -#define BTEQ BTEqualStrategyNumber -#define BTGE BTGreaterEqualStrategyNumber -#define BTGT BTGreaterStrategyNumber -#define BTNE COMPARE_NE +#define RCLT COMPARE_LT +#define RCLE COMPARE_LE +#define RCEQ COMPARE_EQ +#define RCGE COMPARE_GE +#define RCGT COMPARE_GT +#define RCNE COMPARE_NE /* We use "none" for 0/false to make the tables align nicely */ #define none 0 -static const bool BT_implies_table[6][6] = { +static const bool RC_implies_table[6][6] = { /* * The predicate operator: * LT LE EQ GE GT NE @@ -1682,7 +1682,7 @@ static const bool BT_implies_table[6][6] = { {none, none, none, none, none, true} /* NE */ }; -static const bool BT_refutes_table[6][6] = { +static const bool RC_refutes_table[6][6] = { /* * The predicate operator: * LT LE EQ GE GT NE @@ -1695,30 +1695,30 @@ static const bool BT_refutes_table[6][6] = { {none, none, true, none, none, none} /* NE */ }; -static const StrategyNumber BT_implic_table[6][6] = { +static const CompareType RC_implic_table[6][6] = { /* * The predicate operator: * LT LE EQ GE GT NE */ - {BTGE, BTGE, none, none, none, BTGE}, /* LT */ - {BTGT, BTGE, none, none, none, BTGT}, /* LE */ - {BTGT, BTGE, BTEQ, BTLE, BTLT, BTNE}, /* EQ */ - {none, none, none, BTLE, BTLT, BTLT}, /* GE */ - {none, none, none, BTLE, BTLE, BTLE}, /* GT */ - {none, none, none, none, none, BTEQ} /* NE */ + {RCGE, RCGE, none, none, none, RCGE}, /* LT */ + {RCGT, RCGE, none, none, none, RCGT}, /* LE */ + {RCGT, RCGE, RCEQ, RCLE, RCLT, RCNE}, /* EQ */ + {none, none, none, RCLE, RCLT, RCLT}, /* GE */ + {none, none, none, RCLE, RCLE, RCLE}, /* GT */ + {none, none, none, none, none, RCEQ} /* NE */ }; -static const StrategyNumber BT_refute_table[6][6] = { +static const CompareType RC_refute_table[6][6] = { /* * The predicate operator: * LT LE EQ GE GT NE */ - {none, none, BTGE, BTGE, BTGE, none}, /* LT */ - {none, none, BTGT, BTGT, BTGE, none}, /* LE */ - {BTLE, BTLT, BTNE, BTGT, BTGE, BTEQ}, /* EQ */ - {BTLE, BTLT, BTLT, none, none, none}, /* GE */ - {BTLE, BTLE, BTLE, none, none, none}, /* GT */ - {none, none, BTEQ, none, none, none} /* NE */ + {none, none, RCGE, RCGE, RCGE, none}, /* LT */ + {none, none, RCGT, RCGT, RCGE, none}, /* LE */ + {RCLE, RCLT, RCNE, RCGT, RCGE, RCEQ}, /* EQ */ + {RCLE, RCLT, RCLT, none, none, none}, /* GE */ + {RCLE, RCLE, RCLE, none, none, none}, /* GT */ + {none, none, RCEQ, none, none, none} /* NE */ }; @@ -2165,23 +2165,23 @@ lookup_proof_cache(Oid pred_op, Oid clause_op, bool refute_it) * operator. This can happen in cases with incomplete sets of cross-type * comparison operators. */ - clause_op_infos = get_op_btree_interpretation(clause_op); + clause_op_infos = get_op_index_interpretation(clause_op); if (clause_op_infos) - pred_op_infos = get_op_btree_interpretation(pred_op); + pred_op_infos = get_op_index_interpretation(pred_op); else /* no point in looking */ pred_op_infos = NIL; foreach(lcp, pred_op_infos) { - OpBtreeInterpretation *pred_op_info = lfirst(lcp); + OpIndexInterpretation *pred_op_info = lfirst(lcp); Oid opfamily_id = pred_op_info->opfamily_id; foreach(lcc, clause_op_infos) { - OpBtreeInterpretation *clause_op_info = lfirst(lcc); - StrategyNumber pred_strategy, - clause_strategy, - test_strategy; + OpIndexInterpretation *clause_op_info = lfirst(lcc); + CompareType pred_cmptype, + clause_cmptype, + test_cmptype; /* Must find them in same opfamily */ if (opfamily_id != clause_op_info->opfamily_id) @@ -2189,51 +2189,51 @@ lookup_proof_cache(Oid pred_op, Oid clause_op, bool refute_it) /* Lefttypes should match */ Assert(clause_op_info->oplefttype == pred_op_info->oplefttype); - pred_strategy = pred_op_info->strategy; - clause_strategy = clause_op_info->strategy; + pred_cmptype = pred_op_info->cmptype; + clause_cmptype = clause_op_info->cmptype; /* * Check to see if we can make a proof for same-subexpressions * cases based on the operators' relationship in this opfamily. */ if (refute_it) - same_subexprs |= BT_refutes_table[clause_strategy - 1][pred_strategy - 1]; + same_subexprs |= RC_refutes_table[clause_cmptype - 1][pred_cmptype - 1]; else - same_subexprs |= BT_implies_table[clause_strategy - 1][pred_strategy - 1]; + same_subexprs |= RC_implies_table[clause_cmptype - 1][pred_cmptype - 1]; /* - * Look up the "test" strategy number in the implication table + * Look up the "test" cmptype number in the implication table */ if (refute_it) - test_strategy = BT_refute_table[clause_strategy - 1][pred_strategy - 1]; + test_cmptype = RC_refute_table[clause_cmptype - 1][pred_cmptype - 1]; else - test_strategy = BT_implic_table[clause_strategy - 1][pred_strategy - 1]; + test_cmptype = RC_implic_table[clause_cmptype - 1][pred_cmptype - 1]; - if (test_strategy == 0) + if (test_cmptype == 0) { /* Can't determine implication using this interpretation */ continue; } /* - * See if opfamily has an operator for the test strategy and the + * See if opfamily has an operator for the test cmptype and the * datatypes. */ - if (test_strategy == BTNE) + if (test_cmptype == RCNE) { - test_op = get_opfamily_member(opfamily_id, - pred_op_info->oprighttype, - clause_op_info->oprighttype, - BTEqualStrategyNumber); + test_op = get_opfamily_member_for_cmptype(opfamily_id, + pred_op_info->oprighttype, + clause_op_info->oprighttype, + COMPARE_EQ); if (OidIsValid(test_op)) test_op = get_negator(test_op); } else { - test_op = get_opfamily_member(opfamily_id, - pred_op_info->oprighttype, - clause_op_info->oprighttype, - test_strategy); + test_op = get_opfamily_member_for_cmptype(opfamily_id, + pred_op_info->oprighttype, + clause_op_info->oprighttype, + test_cmptype); } if (!OidIsValid(test_op)) diff --git a/src/backend/parser/parse_clause.c b/src/backend/parser/parse_clause.c index 2e64fcae7b2..9f20a70ce13 100644 --- a/src/backend/parser/parse_clause.c +++ b/src/backend/parser/parse_clause.c @@ -2915,7 +2915,7 @@ transformWindowDefinitions(ParseState *pstate, { SortGroupClause *sortcl; Node *sortkey; - int16 rangestrategy; + CompareType rangecmptype; if (list_length(wc->orderClause) != 1) ereport(ERROR, @@ -2928,7 +2928,7 @@ transformWindowDefinitions(ParseState *pstate, if (!get_ordering_op_properties(sortcl->sortop, &rangeopfamily, &rangeopcintype, - &rangestrategy)) + &rangecmptype)) elog(ERROR, "operator %u is not a valid ordering operator", sortcl->sortop); /* Record properties of sort ordering */ diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c index bc602f00ae3..1f8e2d54673 100644 --- a/src/backend/parser/parse_expr.c +++ b/src/backend/parser/parse_expr.c @@ -2832,7 +2832,7 @@ make_row_comparison_op(ParseState *pstate, List *opname, ListCell *l, *r; List **opinfo_lists; - Bitmapset *strats; + Bitmapset *cmptypes; int nopers; int i; @@ -2897,45 +2897,45 @@ make_row_comparison_op(ParseState *pstate, List *opname, /* * Now we must determine which row comparison semantics (= <> < <= > >=) - * apply to this set of operators. We look for btree opfamilies - * containing the operators, and see which interpretations (strategy - * numbers) exist for each operator. + * apply to this set of operators. We look for opfamilies containing the + * operators, and see which interpretations (cmptypes) exist for each + * operator. */ opinfo_lists = (List **) palloc(nopers * sizeof(List *)); - strats = NULL; + cmptypes = NULL; i = 0; foreach(l, opexprs) { Oid opno = ((OpExpr *) lfirst(l))->opno; - Bitmapset *this_strats; + Bitmapset *this_cmptypes; ListCell *j; - opinfo_lists[i] = get_op_btree_interpretation(opno); + opinfo_lists[i] = get_op_index_interpretation(opno); /* - * convert strategy numbers into a Bitmapset to make the intersection + * convert comparison types into a Bitmapset to make the intersection * calculation easy. */ - this_strats = NULL; + this_cmptypes = NULL; foreach(j, opinfo_lists[i]) { - OpBtreeInterpretation *opinfo = lfirst(j); + OpIndexInterpretation *opinfo = lfirst(j); - this_strats = bms_add_member(this_strats, opinfo->strategy); + this_cmptypes = bms_add_member(this_cmptypes, opinfo->cmptype); } if (i == 0) - strats = this_strats; + cmptypes = this_cmptypes; else - strats = bms_int_members(strats, this_strats); + cmptypes = bms_int_members(cmptypes, this_cmptypes); i++; } /* * If there are multiple common interpretations, we may use any one of - * them ... this coding arbitrarily picks the lowest btree strategy + * them ... this coding arbitrarily picks the lowest comparison type * number. */ - i = bms_next_member(strats, -1); + i = bms_next_member(cmptypes, -1); if (i < 0) { /* No common interpretation, so fail */ @@ -2969,9 +2969,9 @@ make_row_comparison_op(ParseState *pstate, List *opname, foreach(j, opinfo_lists[i]) { - OpBtreeInterpretation *opinfo = lfirst(j); + OpIndexInterpretation *opinfo = lfirst(j); - if (opinfo->strategy == cmptype) + if (opinfo->cmptype == cmptype) { opfamily = opinfo->opfamily_id; break; diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c index 021ea7517d7..588d991fa57 100644 --- a/src/backend/utils/adt/selfuncs.c +++ b/src/backend/utils/adt/selfuncs.c @@ -2947,7 +2947,7 @@ scalargejoinsel(PG_FUNCTION_ARGS) * first join pair is found, which will affect the join's startup time. * * clause should be a clause already known to be mergejoinable. opfamily, - * strategy, and nulls_first specify the sort ordering being used. + * cmptype, and nulls_first specify the sort ordering being used. * * The outputs are: * *leftstart is set to the fraction of the left-hand variable expected @@ -2958,7 +2958,7 @@ scalargejoinsel(PG_FUNCTION_ARGS) */ void mergejoinscansel(PlannerInfo *root, Node *clause, - Oid opfamily, int strategy, bool nulls_first, + Oid opfamily, CompareType cmptype, bool nulls_first, Selectivity *leftstart, Selectivity *leftend, Selectivity *rightstart, Selectivity *rightend) { @@ -2966,6 +2966,7 @@ mergejoinscansel(PlannerInfo *root, Node *clause, *right; VariableStatData leftvar, rightvar; + Oid opmethod; int op_strategy; Oid op_lefttype; Oid op_righttype; @@ -2979,6 +2980,10 @@ mergejoinscansel(PlannerInfo *root, Node *clause, leop, revltop, revleop; + StrategyNumber ltstrat, + lestrat, + gtstrat, + gestrat; bool isgt; Datum leftmin, leftmax, @@ -3005,12 +3010,14 @@ mergejoinscansel(PlannerInfo *root, Node *clause, examine_variable(root, left, 0, &leftvar); examine_variable(root, right, 0, &rightvar); + opmethod = get_opfamily_method(opfamily); + /* Extract the operator's declared left/right datatypes */ get_op_opfamily_properties(opno, opfamily, false, &op_strategy, &op_lefttype, &op_righttype); - Assert(op_strategy == BTEqualStrategyNumber); + Assert(IndexAmTranslateStrategy(op_strategy, opmethod, opfamily, true) == COMPARE_EQ); /* * Look up the various operators we need. If we don't find them all, it @@ -3019,19 +3026,21 @@ mergejoinscansel(PlannerInfo *root, Node *clause, * Note: we expect that pg_statistic histograms will be sorted by the '<' * operator, regardless of which sort direction we are considering. */ - switch (strategy) + switch (cmptype) { - case BTLessStrategyNumber: + case COMPARE_LT: isgt = false; + ltstrat = IndexAmTranslateCompareType(COMPARE_LT, opmethod, opfamily, true); + lestrat = IndexAmTranslateCompareType(COMPARE_LE, opmethod, opfamily, true); if (op_lefttype == op_righttype) { /* easy case */ ltop = get_opfamily_member(opfamily, op_lefttype, op_righttype, - BTLessStrategyNumber); + ltstrat); leop = get_opfamily_member(opfamily, op_lefttype, op_righttype, - BTLessEqualStrategyNumber); + lestrat); lsortop = ltop; rsortop = ltop; lstatop = lsortop; @@ -3043,43 +3052,46 @@ mergejoinscansel(PlannerInfo *root, Node *clause, { ltop = get_opfamily_member(opfamily, op_lefttype, op_righttype, - BTLessStrategyNumber); + ltstrat); leop = get_opfamily_member(opfamily, op_lefttype, op_righttype, - BTLessEqualStrategyNumber); + lestrat); lsortop = get_opfamily_member(opfamily, op_lefttype, op_lefttype, - BTLessStrategyNumber); + ltstrat); rsortop = get_opfamily_member(opfamily, op_righttype, op_righttype, - BTLessStrategyNumber); + ltstrat); lstatop = lsortop; rstatop = rsortop; revltop = get_opfamily_member(opfamily, op_righttype, op_lefttype, - BTLessStrategyNumber); + ltstrat); revleop = get_opfamily_member(opfamily, op_righttype, op_lefttype, - BTLessEqualStrategyNumber); + lestrat); } break; - case BTGreaterStrategyNumber: + case COMPARE_GT: /* descending-order case */ isgt = true; + ltstrat = IndexAmTranslateCompareType(COMPARE_LT, opmethod, opfamily, true); + gtstrat = IndexAmTranslateCompareType(COMPARE_GT, opmethod, opfamily, true); + gestrat = IndexAmTranslateCompareType(COMPARE_GE, opmethod, opfamily, true); if (op_lefttype == op_righttype) { /* easy case */ ltop = get_opfamily_member(opfamily, op_lefttype, op_righttype, - BTGreaterStrategyNumber); + gtstrat); leop = get_opfamily_member(opfamily, op_lefttype, op_righttype, - BTGreaterEqualStrategyNumber); + gestrat); lsortop = ltop; rsortop = ltop; lstatop = get_opfamily_member(opfamily, op_lefttype, op_lefttype, - BTLessStrategyNumber); + ltstrat); rstatop = lstatop; revltop = ltop; revleop = leop; @@ -3088,28 +3100,28 @@ mergejoinscansel(PlannerInfo *root, Node *clause, { ltop = get_opfamily_member(opfamily, op_lefttype, op_righttype, - BTGreaterStrategyNumber); + gtstrat); leop = get_opfamily_member(opfamily, op_lefttype, op_righttype, - BTGreaterEqualStrategyNumber); + gestrat); lsortop = get_opfamily_member(opfamily, op_lefttype, op_lefttype, - BTGreaterStrategyNumber); + gtstrat); rsortop = get_opfamily_member(opfamily, op_righttype, op_righttype, - BTGreaterStrategyNumber); + gtstrat); lstatop = get_opfamily_member(opfamily, op_lefttype, op_lefttype, - BTLessStrategyNumber); + ltstrat); rstatop = get_opfamily_member(opfamily, op_righttype, op_righttype, - BTLessStrategyNumber); + ltstrat); revltop = get_opfamily_member(opfamily, op_righttype, op_lefttype, - BTGreaterStrategyNumber); + gtstrat); revleop = get_opfamily_member(opfamily, op_righttype, op_lefttype, - BTGreaterEqualStrategyNumber); + gestrat); } break; default: diff --git a/src/backend/utils/cache/lsyscache.c b/src/backend/utils/cache/lsyscache.c index 82031c1e8e5..c460a72b75d 100644 --- a/src/backend/utils/cache/lsyscache.c +++ b/src/backend/utils/cache/lsyscache.c @@ -206,11 +206,46 @@ get_opfamily_member_for_cmptype(Oid opfamily, Oid lefttype, Oid righttype, return get_opfamily_member(opfamily, lefttype, righttype, strategy); } +/* + * get_opmethod_canorder + * Return amcanorder field for given index AM. + * + * To speed things up in the common cases, we're hardcoding the results from + * the built-in index types. Note that we also need to hardcode the negative + * results from the built-in non-btree index types, since you'll usually get a + * few hits for those as well. It would be nice to organize and cache this a + * bit differently to avoid the hardcoding. + */ +static bool +get_opmethod_canorder(Oid amoid) +{ + switch (amoid) + { + case BTREE_AM_OID: + return true; + case HASH_AM_OID: + case GIST_AM_OID: + case GIN_AM_OID: + case SPGIST_AM_OID: + case BRIN_AM_OID: + return false; + default: + { + bool result; + IndexAmRoutine *amroutine = GetIndexAmRoutineByAmId(amoid, false); + + result = amroutine->amcanorder; + pfree(amroutine); + return result; + } + } +} + /* * get_ordering_op_properties - * Given the OID of an ordering operator (a btree "<" or ">" operator), + * Given the OID of an ordering operator (a "<" or ">" operator), * determine its opfamily, its declared input datatype, and its - * strategy number (BTLessStrategyNumber or BTGreaterStrategyNumber). + * comparison type. * * Returns true if successful, false if no matching pg_amop entry exists. * (This indicates that the operator is not a valid ordering operator.) @@ -228,7 +263,7 @@ get_opfamily_member_for_cmptype(Oid opfamily, Oid lefttype, Oid righttype, */ bool get_ordering_op_properties(Oid opno, - Oid *opfamily, Oid *opcintype, int16 *strategy) + Oid *opfamily, Oid *opcintype, CompareType *cmptype) { bool result = false; CatCList *catlist; @@ -237,7 +272,7 @@ get_ordering_op_properties(Oid opno, /* ensure outputs are initialized on failure */ *opfamily = InvalidOid; *opcintype = InvalidOid; - *strategy = 0; + *cmptype = COMPARE_INVALID; /* * Search pg_amop to see if the target operator is registered as the "<" @@ -249,13 +284,18 @@ get_ordering_op_properties(Oid opno, { HeapTuple tuple = &catlist->members[i]->tuple; Form_pg_amop aform = (Form_pg_amop) GETSTRUCT(tuple); + CompareType am_cmptype; - /* must be btree */ - if (aform->amopmethod != BTREE_AM_OID) + /* must be ordering index */ + if (!get_opmethod_canorder(aform->amopmethod)) continue; - if (aform->amopstrategy == BTLessStrategyNumber || - aform->amopstrategy == BTGreaterStrategyNumber) + am_cmptype = IndexAmTranslateStrategy(aform->amopstrategy, + aform->amopmethod, + aform->amopfamily, + true); + + if (am_cmptype == COMPARE_LT || am_cmptype == COMPARE_GT) { /* Found it ... should have consistent input types */ if (aform->amoplefttype == aform->amoprighttype) @@ -263,7 +303,7 @@ get_ordering_op_properties(Oid opno, /* Found a suitable opfamily, return info */ *opfamily = aform->amopfamily; *opcintype = aform->amoplefttype; - *strategy = aform->amopstrategy; + *cmptype = am_cmptype; result = true; break; } @@ -277,7 +317,7 @@ get_ordering_op_properties(Oid opno, /* * get_equality_op_for_ordering_op - * Get the OID of the datatype-specific btree equality operator + * Get the OID of the datatype-specific equality operator * associated with an ordering operator (a "<" or ">" operator). * * If "reverse" isn't NULL, also set *reverse to false if the operator is "<", @@ -292,19 +332,19 @@ get_equality_op_for_ordering_op(Oid opno, bool *reverse) Oid result = InvalidOid; Oid opfamily; Oid opcintype; - int16 strategy; + CompareType cmptype; /* Find the operator in pg_amop */ if (get_ordering_op_properties(opno, - &opfamily, &opcintype, &strategy)) + &opfamily, &opcintype, &cmptype)) { /* Found a suitable opfamily, get matching equality operator */ - result = get_opfamily_member(opfamily, - opcintype, - opcintype, - BTEqualStrategyNumber); + result = get_opfamily_member_for_cmptype(opfamily, + opcintype, + opcintype, + COMPARE_EQ); if (reverse) - *reverse = (strategy == BTGreaterStrategyNumber); + *reverse = (cmptype == COMPARE_GT); } return result; @@ -312,7 +352,7 @@ get_equality_op_for_ordering_op(Oid opno, bool *reverse) /* * get_ordering_op_for_equality_op - * Get the OID of a datatype-specific btree "less than" ordering operator + * Get the OID of a datatype-specific "less than" ordering operator * associated with an equality operator. (If there are multiple * possibilities, assume any one will do.) * @@ -341,20 +381,25 @@ get_ordering_op_for_equality_op(Oid opno, bool use_lhs_type) { HeapTuple tuple = &catlist->members[i]->tuple; Form_pg_amop aform = (Form_pg_amop) GETSTRUCT(tuple); + CompareType cmptype; - /* must be btree */ - if (aform->amopmethod != BTREE_AM_OID) + /* must be ordering index */ + if (!get_opmethod_canorder(aform->amopmethod)) continue; - if (aform->amopstrategy == BTEqualStrategyNumber) + cmptype = IndexAmTranslateStrategy(aform->amopstrategy, + aform->amopmethod, + aform->amopfamily, + true); + if (cmptype == COMPARE_EQ) { /* Found a suitable opfamily, get matching ordering operator */ Oid typid; typid = use_lhs_type ? aform->amoplefttype : aform->amoprighttype; - result = get_opfamily_member(aform->amopfamily, - typid, typid, - BTLessStrategyNumber); + result = get_opfamily_member_for_cmptype(aform->amopfamily, + typid, typid, + COMPARE_LT); if (OidIsValid(result)) break; /* failure probably shouldn't happen, but keep looking if so */ @@ -369,7 +414,7 @@ get_ordering_op_for_equality_op(Oid opno, bool use_lhs_type) /* * get_mergejoin_opfamilies * Given a putatively mergejoinable operator, return a list of the OIDs - * of the btree opfamilies in which it represents equality. + * of the amcanorder opfamilies in which it represents equality. * * It is possible (though at present unusual) for an operator to be equality * in more than one opfamily, hence the result is a list. This also lets us @@ -394,7 +439,7 @@ get_mergejoin_opfamilies(Oid opno) /* * Search pg_amop to see if the target operator is registered as the "=" - * operator of any btree opfamily. + * operator of any opfamily of an ordering index type. */ catlist = SearchSysCacheList1(AMOPOPID, ObjectIdGetDatum(opno)); @@ -403,9 +448,12 @@ get_mergejoin_opfamilies(Oid opno) HeapTuple tuple = &catlist->members[i]->tuple; Form_pg_amop aform = (Form_pg_amop) GETSTRUCT(tuple); - /* must be btree equality */ - if (aform->amopmethod == BTREE_AM_OID && - aform->amopstrategy == BTEqualStrategyNumber) + /* must be ordering index equality */ + if (get_opmethod_canorder(aform->amopmethod) && + IndexAmTranslateStrategy(aform->amopstrategy, + aform->amopmethod, + aform->amopfamily, + true) == COMPARE_EQ) result = lappend_oid(result, aform->amopfamily); } @@ -611,20 +659,20 @@ get_op_hash_functions(Oid opno, } /* - * get_op_btree_interpretation - * Given an operator's OID, find out which btree opfamilies it belongs to, + * get_op_index_interpretation + * Given an operator's OID, find out which amcanorder opfamilies it belongs to, * and what properties it has within each one. The results are returned - * as a palloc'd list of OpBtreeInterpretation structs. + * as a palloc'd list of OpIndexInterpretation structs. * * In addition to the normal btree operators, we consider a <> operator to be * a "member" of an opfamily if its negator is an equality operator of the * opfamily. COMPARE_NE is returned as the strategy number for this case. */ List * -get_op_btree_interpretation(Oid opno) +get_op_index_interpretation(Oid opno) { List *result = NIL; - OpBtreeInterpretation *thisresult; + OpIndexInterpretation *thisresult; CatCList *catlist; int i; @@ -637,20 +685,26 @@ get_op_btree_interpretation(Oid opno) { HeapTuple op_tuple = &catlist->members[i]->tuple; Form_pg_amop op_form = (Form_pg_amop) GETSTRUCT(op_tuple); - StrategyNumber op_strategy; + CompareType cmptype; - /* must be btree */ - if (op_form->amopmethod != BTREE_AM_OID) + /* must be ordering index */ + if (!get_opmethod_canorder(op_form->amopmethod)) continue; - /* Get the operator's btree strategy number */ - op_strategy = (StrategyNumber) op_form->amopstrategy; - Assert(op_strategy >= 1 && op_strategy <= 5); + /* Get the operator's comparision type */ + cmptype = IndexAmTranslateStrategy(op_form->amopstrategy, + op_form->amopmethod, + op_form->amopfamily, + true); + + /* should not happen */ + if (cmptype == COMPARE_INVALID) + continue; - thisresult = (OpBtreeInterpretation *) - palloc(sizeof(OpBtreeInterpretation)); + thisresult = (OpIndexInterpretation *) + palloc(sizeof(OpIndexInterpretation)); thisresult->opfamily_id = op_form->amopfamily; - thisresult->strategy = op_strategy; + thisresult->cmptype = cmptype; thisresult->oplefttype = op_form->amoplefttype; thisresult->oprighttype = op_form->amoprighttype; result = lappend(result, thisresult); @@ -675,25 +729,28 @@ get_op_btree_interpretation(Oid opno) { HeapTuple op_tuple = &catlist->members[i]->tuple; Form_pg_amop op_form = (Form_pg_amop) GETSTRUCT(op_tuple); - StrategyNumber op_strategy; + IndexAmRoutine *amroutine = GetIndexAmRoutineByAmId(op_form->amopmethod, false); + CompareType cmptype; - /* must be btree */ - if (op_form->amopmethod != BTREE_AM_OID) + /* must be ordering index */ + if (!amroutine->amcanorder) continue; - /* Get the operator's btree strategy number */ - op_strategy = (StrategyNumber) op_form->amopstrategy; - Assert(op_strategy >= 1 && op_strategy <= 5); + /* Get the operator's comparision type */ + cmptype = IndexAmTranslateStrategy(op_form->amopstrategy, + op_form->amopmethod, + op_form->amopfamily, + true); /* Only consider negators that are = */ - if (op_strategy != BTEqualStrategyNumber) + if (cmptype != COMPARE_EQ) continue; - /* OK, report it with "strategy" COMPARE_NE */ - thisresult = (OpBtreeInterpretation *) - palloc(sizeof(OpBtreeInterpretation)); + /* OK, report it as COMPARE_NE */ + thisresult = (OpIndexInterpretation *) + palloc(sizeof(OpIndexInterpretation)); thisresult->opfamily_id = op_form->amopfamily; - thisresult->strategy = COMPARE_NE; + thisresult->cmptype = COMPARE_NE; thisresult->oplefttype = op_form->amoplefttype; thisresult->oprighttype = op_form->amoprighttype; result = lappend(result, thisresult); diff --git a/src/backend/utils/sort/sortsupport.c b/src/backend/utils/sort/sortsupport.c index 0b4f08ed2ec..e0f500b9aa2 100644 --- a/src/backend/utils/sort/sortsupport.c +++ b/src/backend/utils/sort/sortsupport.c @@ -135,16 +135,16 @@ PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup) { Oid opfamily; Oid opcintype; - int16 strategy; + CompareType cmptype; Assert(ssup->comparator == NULL); /* Find the operator in pg_amop */ if (!get_ordering_op_properties(orderingOp, &opfamily, &opcintype, - &strategy)) + &cmptype)) elog(ERROR, "operator %u is not a valid ordering operator", orderingOp); - ssup->ssup_reverse = (strategy == BTGreaterStrategyNumber); + ssup->ssup_reverse = (cmptype == COMPARE_GT); FinishSortSupportFunction(opfamily, opcintype, ssup); } diff --git a/src/include/utils/lsyscache.h b/src/include/utils/lsyscache.h index d42380a0d46..fa7c7e0323b 100644 --- a/src/include/utils/lsyscache.h +++ b/src/include/utils/lsyscache.h @@ -21,14 +21,14 @@ /* avoid including subscripting.h here */ struct SubscriptRoutines; -/* Result list element for get_op_btree_interpretation */ -typedef struct OpBtreeInterpretation +/* Result list element for get_op_index_interpretation */ +typedef struct OpIndexInterpretation { - Oid opfamily_id; /* btree opfamily containing operator */ - int strategy; /* its strategy number */ + Oid opfamily_id; /* opfamily containing operator */ + CompareType cmptype; /* its generic comparison type */ Oid oplefttype; /* declared left input datatype */ Oid oprighttype; /* declared right input datatype */ -} OpBtreeInterpretation; +} OpIndexInterpretation; /* I/O function selector for get_type_io_data */ typedef enum IOFuncSelector @@ -78,7 +78,7 @@ extern Oid get_opfamily_member(Oid opfamily, Oid lefttype, Oid righttype, extern Oid get_opfamily_member_for_cmptype(Oid opfamily, Oid lefttype, Oid righttype, CompareType cmptype); extern bool get_ordering_op_properties(Oid opno, - Oid *opfamily, Oid *opcintype, int16 *strategy); + Oid *opfamily, Oid *opcintype, CompareType *cmptype); extern Oid get_equality_op_for_ordering_op(Oid opno, bool *reverse); extern Oid get_ordering_op_for_equality_op(Oid opno, bool use_lhs_type); extern List *get_mergejoin_opfamilies(Oid opno); @@ -86,7 +86,7 @@ extern bool get_compatible_hash_operators(Oid opno, Oid *lhs_opno, Oid *rhs_opno); extern bool get_op_hash_functions(Oid opno, RegProcedure *lhs_procno, RegProcedure *rhs_procno); -extern List *get_op_btree_interpretation(Oid opno); +extern List *get_op_index_interpretation(Oid opno); extern bool equality_ops_are_compatible(Oid opno1, Oid opno2); extern bool comparison_ops_are_compatible(Oid opno1, Oid opno2); extern Oid get_opfamily_proc(Oid opfamily, Oid lefttype, Oid righttype, diff --git a/src/include/utils/selfuncs.h b/src/include/utils/selfuncs.h index 82ac8c6d9da..013049b3098 100644 --- a/src/include/utils/selfuncs.h +++ b/src/include/utils/selfuncs.h @@ -210,7 +210,7 @@ extern Selectivity rowcomparesel(PlannerInfo *root, int varRelid, JoinType jointype, SpecialJoinInfo *sjinfo); extern void mergejoinscansel(PlannerInfo *root, Node *clause, - Oid opfamily, int strategy, bool nulls_first, + Oid opfamily, CompareType cmptype, bool nulls_first, Selectivity *leftstart, Selectivity *leftend, Selectivity *rightstart, Selectivity *rightend); diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list index 0c81d03950d..1a30437ad96 100644 --- a/src/tools/pgindent/typedefs.list +++ b/src/tools/pgindent/typedefs.list @@ -1794,11 +1794,11 @@ OnConflictAction OnConflictClause OnConflictExpr OnConflictSetState -OpBtreeInterpretation OpClassCacheEnt OpExpr OpFamilyMember OpFamilyOpFuncGroup +OpIndexInterpretation OpclassInfo Operator OperatorElement -- 2.39.5