diff options
Diffstat (limited to 'src/backend/optimizer')
| -rw-r--r-- | src/backend/optimizer/path/costsize.c | 11 | ||||
| -rw-r--r-- | src/backend/optimizer/path/indxpath.c | 198 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/createplan.c | 86 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/planner.c | 2 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/setrefs.c | 4 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/subselect.c | 5 | ||||
| -rw-r--r-- | src/backend/optimizer/util/pathnode.c | 6 |
7 files changed, 298 insertions, 14 deletions
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index 0724f9a6c9..e6edbdb1e8 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -209,6 +209,7 @@ cost_seqscan(Path *path, PlannerInfo *root, * * 'index' is the index to be used * 'indexQuals' is the list of applicable qual clauses (implicit AND semantics) + * 'indexOrderBys' is the list of ORDER BY operators for amcanorderbyop indexes * 'outer_rel' is the outer relation when we are considering using the index * scan as the inside of a nestloop join (hence, some of the indexQuals * are join clauses, and we should expect repeated scans of the index); @@ -218,18 +219,19 @@ cost_seqscan(Path *path, PlannerInfo *root, * additional fields of the IndexPath besides startup_cost and total_cost. * These fields are needed if the IndexPath is used in a BitmapIndexScan. * + * indexQuals is a list of RestrictInfo nodes, but indexOrderBys is a list of + * bare expressions. + * * NOTE: 'indexQuals' must contain only clauses usable as index restrictions. * Any additional quals evaluated as qpquals may reduce the number of returned * tuples, but they won't reduce the number of tuples we have to fetch from * the table, so they don't reduce the scan cost. - * - * NOTE: as of 8.0, indexQuals is a list of RestrictInfo nodes, where formerly - * it was a list of bare clause expressions. */ void cost_index(IndexPath *path, PlannerInfo *root, IndexOptInfo *index, List *indexQuals, + List *indexOrderBys, RelOptInfo *outer_rel) { RelOptInfo *baserel = index->rel; @@ -263,10 +265,11 @@ cost_index(IndexPath *path, PlannerInfo *root, * the fraction of main-table tuples we will have to retrieve) and its * correlation to the main-table tuple order. */ - OidFunctionCall8(index->amcostestimate, + OidFunctionCall9(index->amcostestimate, PointerGetDatum(root), PointerGetDatum(index), PointerGetDatum(indexQuals), + PointerGetDatum(indexOrderBys), PointerGetDatum(outer_rel), PointerGetDatum(&indexStartupCost), PointerGetDatum(&indexTotalCost), diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index f73e0e6dc6..90ccb3928b 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -89,6 +89,9 @@ static bool match_rowcompare_to_indexcol(IndexOptInfo *index, Oid opfamily, RowCompareExpr *clause, Relids outer_relids); +static List *match_index_to_pathkeys(IndexOptInfo *index, List *pathkeys); +static Expr *match_clause_to_ordering_op(IndexOptInfo *index, + int indexcol, Expr *clause, Oid pk_opfamily); static Relids indexable_outerrelids(PlannerInfo *root, RelOptInfo *rel); static bool matches_any_index(RestrictInfo *rinfo, RelOptInfo *rel, Relids outer_relids); @@ -286,6 +289,7 @@ find_usable_indexes(PlannerInfo *root, RelOptInfo *rel, IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist); IndexPath *ipath; List *restrictclauses; + List *orderbyclauses; List *index_pathkeys; List *useful_pathkeys; bool useful_predicate; @@ -388,9 +392,24 @@ find_usable_indexes(PlannerInfo *root, RelOptInfo *rel, ForwardScanDirection); useful_pathkeys = truncate_useless_pathkeys(root, rel, index_pathkeys); + orderbyclauses = NIL; + } + else if (index->amcanorderbyop && possibly_useful_pathkeys && + istoplevel && outer_rel == NULL && scantype != ST_BITMAPSCAN) + { + /* see if we can generate ordering operators for query_pathkeys */ + orderbyclauses = match_index_to_pathkeys(index, + root->query_pathkeys); + if (orderbyclauses) + useful_pathkeys = root->query_pathkeys; + else + useful_pathkeys = NIL; } else + { useful_pathkeys = NIL; + orderbyclauses = NIL; + } /* * 3. Generate an indexscan path if there are relevant restriction @@ -402,6 +421,7 @@ find_usable_indexes(PlannerInfo *root, RelOptInfo *rel, { ipath = create_index_path(root, index, restrictclauses, + orderbyclauses, useful_pathkeys, index_is_ordered ? ForwardScanDirection : @@ -425,6 +445,7 @@ find_usable_indexes(PlannerInfo *root, RelOptInfo *rel, { ipath = create_index_path(root, index, restrictclauses, + NIL, useful_pathkeys, BackwardScanDirection, outer_rel); @@ -1385,6 +1406,179 @@ match_rowcompare_to_indexcol(IndexOptInfo *index, /**************************************************************************** + * ---- ROUTINES TO CHECK ORDERING OPERATORS ---- + ****************************************************************************/ + +/* + * match_index_to_pathkeys + * Test whether an index can produce output ordered according to the + * given pathkeys using "ordering operators". + * + * If it can, return a list of suitable ORDER BY expressions, each of the form + * "indexedcol operator pseudoconstant". If not, return NIL. + */ +static List * +match_index_to_pathkeys(IndexOptInfo *index, List *pathkeys) +{ + List *orderbyexprs = NIL; + ListCell *lc1; + + /* Only indexes with the amcanorderbyop property are interesting here */ + if (!index->amcanorderbyop) + return NIL; + + foreach(lc1, pathkeys) + { + 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 NIL; + + /* If eclass is volatile, no hope of using an indexscan */ + if (pathkey->pk_eclass->ec_has_volatile) + return NIL; + + /* Try to match eclass member expression(s) to index */ + 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; + + for (indexcol = 0; indexcol < index->ncolumns; indexcol++) + { + Expr *expr; + + expr = match_clause_to_ordering_op(index, + indexcol, + member->em_expr, + pathkey->pk_opfamily); + if (expr) + { + orderbyexprs = lappend(orderbyexprs, expr); + found = true; + break; + } + } + + if (found) /* don't want to look at remaining members */ + break; + } + + if (!found) /* fail if no match for this pathkey */ + return NIL; + } + + return orderbyexprs; /* success! */ +} + +/* + * match_clause_to_ordering_op + * Determines whether an ordering operator expression matches an + * index column. + * + * This is similar to, but simpler than, match_clause_to_indexcol. + * We only care about simple OpExpr cases. The input is a bare + * expression that is being ordered by, which must be of the form + * (indexkey op const) or (const op indexkey) where op is an ordering + * operator for the column's opfamily. + * + * 'index' is the index of interest. + * 'indexcol' is a column number of 'index' (counting from 0). + * 'clause' is the ordering expression to be tested. + * 'pk_opfamily' is the btree opfamily describing the required sort order. + * + * If successful, return 'clause' as-is if the indexkey is on the left, + * otherwise a commuted copy of 'clause'. If no match, return NULL. + */ +static Expr * +match_clause_to_ordering_op(IndexOptInfo *index, + int indexcol, + Expr *clause, + Oid pk_opfamily) +{ + Oid opfamily = index->opfamily[indexcol]; + Node *leftop, + *rightop; + Oid expr_op; + Oid sortfamily; + bool commuted; + + /* + * Clause must be a binary opclause. + */ + if (!is_opclause(clause)) + return NULL; + leftop = get_leftop(clause); + rightop = get_rightop(clause); + if (!leftop || !rightop) + return NULL; + expr_op = ((OpExpr *) clause)->opno; + + /* + * Check for clauses of the form: (indexkey operator constant) or + * (constant operator indexkey). + */ + if (match_index_to_operand(leftop, indexcol, index) && + !contain_var_clause(rightop) && + !contain_volatile_functions(rightop)) + { + commuted = false; + } + else if (match_index_to_operand(rightop, indexcol, index) && + !contain_var_clause(leftop) && + !contain_volatile_functions(leftop)) + { + /* Might match, but we need a commuted operator */ + expr_op = get_commutator(expr_op); + if (expr_op == InvalidOid) + return NULL; + commuted = true; + } + else + return NULL; + + /* + * Is the (commuted) operator an ordering operator for the opfamily? + * And if so, does it yield the right sorting semantics? + */ + sortfamily = get_op_opfamily_sortfamily(expr_op, opfamily); + if (sortfamily != pk_opfamily) + return NULL; + + /* We have a match. Return clause or a commuted version thereof. */ + if (commuted) + { + OpExpr *newclause = makeNode(OpExpr); + + /* flat-copy all the fields of clause */ + memcpy(newclause, clause, sizeof(OpExpr)); + + /* commute it */ + newclause->opno = expr_op; + newclause->opfuncid = InvalidOid; + newclause->args = list_make2(rightop, leftop); + + clause = (Expr *) newclause; + } + + return clause; +} + + +/**************************************************************************** * ---- ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS ---- ****************************************************************************/ @@ -2630,7 +2824,7 @@ expand_indexqual_rowcompare(RestrictInfo *rinfo, expr_op = linitial_oid(clause->opnos); if (!var_on_left) expr_op = get_commutator(expr_op); - get_op_opfamily_properties(expr_op, index->opfamily[indexcol], + get_op_opfamily_properties(expr_op, index->opfamily[indexcol], false, &op_strategy, &op_lefttype, &op_righttype); @@ -2698,7 +2892,7 @@ expand_indexqual_rowcompare(RestrictInfo *rinfo, break; /* Add opfamily and datatypes to lists */ - get_op_opfamily_properties(expr_op, index->opfamily[i], + get_op_opfamily_properties(expr_op, index->opfamily[i], false, &op_strategy, &op_lefttype, &op_righttype); diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index 41ad512a29..1bbf35ed74 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -81,6 +81,8 @@ static Node *replace_nestloop_params(PlannerInfo *root, Node *expr); static Node *replace_nestloop_params_mutator(Node *node, PlannerInfo *root); static List *fix_indexqual_references(PlannerInfo *root, IndexPath *index_path, List *indexquals); +static List *fix_indexorderby_references(PlannerInfo *root, IndexPath *index_path, + List *indexorderbys); static Node *fix_indexqual_operand(Node *node, IndexOptInfo *index); static List *get_switched_clauses(List *clauses, Relids outerrelids); static List *order_qual_clauses(PlannerInfo *root, List *clauses); @@ -89,6 +91,7 @@ static void copy_plan_costsize(Plan *dest, Plan *src); static SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid); static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid, Oid indexid, List *indexqual, List *indexqualorig, + List *indexorderby, List *indexorderbyorig, ScanDirection indexscandir); static BitmapIndexScan *make_bitmap_indexscan(Index scanrelid, Oid indexid, List *indexqual, @@ -1028,11 +1031,13 @@ create_indexscan_plan(PlannerInfo *root, List *scan_clauses) { List *indexquals = best_path->indexquals; + List *indexorderbys = best_path->indexorderbys; Index baserelid = best_path->path.parent->relid; Oid indexoid = best_path->indexinfo->indexoid; List *qpqual; List *stripped_indexquals; List *fixed_indexquals; + List *fixed_indexorderbys; ListCell *l; IndexScan *scan_plan; @@ -1053,6 +1058,11 @@ create_indexscan_plan(PlannerInfo *root, fixed_indexquals = fix_indexqual_references(root, best_path, indexquals); /* + * Likewise fix up index attr references in the ORDER BY expressions. + */ + fixed_indexorderbys = fix_indexorderby_references(root, best_path, indexorderbys); + + /* * If this is an innerjoin scan, the indexclauses will contain join * clauses that are not present in scan_clauses (since the passed-in value * is just the rel's baserestrictinfo list). We must add these clauses to @@ -1123,11 +1133,12 @@ create_indexscan_plan(PlannerInfo *root, /* * We have to replace any outer-relation variables with nestloop params - * in the indexqualorig and qpqual expressions. A bit annoying to have to - * do this separately from the processing in fix_indexqual_references --- - * rethink this when generalizing the inner indexscan support. But note - * we can't really do this earlier because it'd break the comparisons to - * predicates above ... (or would it? Those wouldn't have outer refs) + * in the indexqualorig, qpqual, and indexorderbyorig expressions. A bit + * annoying to have to do this separately from the processing in + * fix_indexqual_references --- rethink this when generalizing the inner + * indexscan support. But note we can't really do this earlier because + * it'd break the comparisons to predicates above ... (or would it? Those + * wouldn't have outer refs) */ if (best_path->isjoininner) { @@ -1135,6 +1146,8 @@ create_indexscan_plan(PlannerInfo *root, replace_nestloop_params(root, (Node *) stripped_indexquals); qpqual = (List *) replace_nestloop_params(root, (Node *) qpqual); + indexorderbys = (List *) + replace_nestloop_params(root, (Node *) indexorderbys); } /* Finally ready to build the plan node */ @@ -1144,6 +1157,8 @@ create_indexscan_plan(PlannerInfo *root, indexoid, fixed_indexquals, stripped_indexquals, + fixed_indexorderbys, + indexorderbys, best_path->indexscandir); copy_path_costsize(&scan_plan->scan.plan, &best_path->path); @@ -2395,6 +2410,63 @@ fix_indexqual_references(PlannerInfo *root, IndexPath *index_path, } /* + * fix_indexorderby_references + * Adjust indexorderby clauses to the form the executor's index + * machinery needs. + * + * This is a simplified version of fix_indexqual_references. The input does + * not have RestrictInfo nodes, and we assume that indxqual.c already + * commuted the clauses to put the index keys on the left. Also, we don't + * bother to support any cases except simple OpExprs, since nothing else + * is allowed for ordering operators. + */ +static List * +fix_indexorderby_references(PlannerInfo *root, IndexPath *index_path, + List *indexorderbys) +{ + IndexOptInfo *index = index_path->indexinfo; + List *fixed_indexorderbys; + ListCell *l; + + fixed_indexorderbys = NIL; + + foreach(l, indexorderbys) + { + Node *clause = (Node *) lfirst(l); + + /* + * Replace any outer-relation variables with nestloop params. + * + * This also makes a copy of the clause, so it's safe to modify it + * in-place below. + */ + clause = replace_nestloop_params(root, clause); + + if (IsA(clause, OpExpr)) + { + OpExpr *op = (OpExpr *) clause; + + if (list_length(op->args) != 2) + elog(ERROR, "indexorderby clause is not binary opclause"); + + /* + * Now, determine which index attribute this is and change the + * indexkey operand as needed. + */ + linitial(op->args) = fix_indexqual_operand(linitial(op->args), + index); + } + else + elog(ERROR, "unsupported indexorderby type: %d", + (int) nodeTag(clause)); + + fixed_indexorderbys = lappend(fixed_indexorderbys, clause); + } + + return fixed_indexorderbys; +} + +/* * fix_indexqual_operand * Convert an indexqual expression to a Var referencing the index column. */ @@ -2685,6 +2757,8 @@ make_indexscan(List *qptlist, Oid indexid, List *indexqual, List *indexqualorig, + List *indexorderby, + List *indexorderbyorig, ScanDirection indexscandir) { IndexScan *node = makeNode(IndexScan); @@ -2699,6 +2773,8 @@ make_indexscan(List *qptlist, node->indexid = indexid; node->indexqual = indexqual; node->indexqualorig = indexqualorig; + node->indexorderby = indexorderby; + node->indexorderbyorig = indexorderbyorig; node->indexorderdir = indexscandir; return node; diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index a1e5900592..6d0b3dbce9 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -3135,7 +3135,7 @@ plan_cluster_use_sort(Oid tableOid, Oid indexOid) /* Estimate the cost of index scan */ indexScanPath = create_index_path(root, indexInfo, - NIL, NIL, + NIL, NIL, NIL, ForwardScanDirection, NULL); return (seqScanAndSortPath.total_cost < indexScanPath->path.total_cost); diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c index 9aef7fc35a..0074679207 100644 --- a/src/backend/optimizer/plan/setrefs.c +++ b/src/backend/optimizer/plan/setrefs.c @@ -301,6 +301,10 @@ set_plan_refs(PlannerGlobal *glob, Plan *plan, int rtoffset) fix_scan_list(glob, splan->indexqual, rtoffset); splan->indexqualorig = fix_scan_list(glob, splan->indexqualorig, rtoffset); + splan->indexorderby = + fix_scan_list(glob, splan->indexorderby, rtoffset); + splan->indexorderbyorig = + fix_scan_list(glob, splan->indexorderbyorig, rtoffset); } break; case T_BitmapIndexScan: diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c index 754753cc12..39ef420284 100644 --- a/src/backend/optimizer/plan/subselect.c +++ b/src/backend/optimizer/plan/subselect.c @@ -1942,10 +1942,13 @@ finalize_plan(PlannerInfo *root, Plan *plan, Bitmapset *valid_params, case T_IndexScan: finalize_primnode((Node *) ((IndexScan *) plan)->indexqual, &context); + finalize_primnode((Node *) ((IndexScan *) plan)->indexorderby, + &context); /* * we need not look at indexqualorig, since it will have the same - * param references as indexqual. + * param references as indexqual. Likewise, we can ignore + * indexorderbyorig. */ context.paramids = bms_add_members(context.paramids, scan_params); break; diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index 231d221b21..2439d814ce 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -414,6 +414,8 @@ create_seqscan_path(PlannerInfo *root, RelOptInfo *rel) * 'index' is a usable index. * 'clause_groups' is a list of lists of RestrictInfo nodes * to be used as index qual conditions in the scan. + * 'indexorderbys' is a list of bare expressions (no RestrictInfos) + * to be used as index ordering operators in the scan. * 'pathkeys' describes the ordering of the path. * 'indexscandir' is ForwardScanDirection or BackwardScanDirection * for an ordered index, or NoMovementScanDirection for @@ -427,6 +429,7 @@ IndexPath * create_index_path(PlannerInfo *root, IndexOptInfo *index, List *clause_groups, + List *indexorderbys, List *pathkeys, ScanDirection indexscandir, RelOptInfo *outer_rel) @@ -463,6 +466,7 @@ create_index_path(PlannerInfo *root, pathnode->indexinfo = index; pathnode->indexclauses = allclauses; pathnode->indexquals = indexquals; + pathnode->indexorderbys = indexorderbys; pathnode->isjoininner = (outer_rel != NULL); pathnode->indexscandir = indexscandir; @@ -504,7 +508,7 @@ create_index_path(PlannerInfo *root, pathnode->rows = rel->rows; } - cost_index(pathnode, root, index, indexquals, outer_rel); + cost_index(pathnode, root, index, indexquals, indexorderbys, outer_rel); return pathnode; } |