diff options
Diffstat (limited to 'src/backend/optimizer/path/orindxpath.c')
| -rw-r--r-- | src/backend/optimizer/path/orindxpath.c | 301 |
1 files changed, 31 insertions, 270 deletions
diff --git a/src/backend/optimizer/path/orindxpath.c b/src/backend/optimizer/path/orindxpath.c index c30c26562c..fb055400d4 100644 --- a/src/backend/optimizer/path/orindxpath.c +++ b/src/backend/optimizer/path/orindxpath.c @@ -8,32 +8,19 @@ * * * IDENTIFICATION - * $PostgreSQL: pgsql/src/backend/optimizer/path/orindxpath.c,v 1.68 2005/04/21 02:28:01 tgl Exp $ + * $PostgreSQL: pgsql/src/backend/optimizer/path/orindxpath.c,v 1.69 2005/04/25 01:30:13 tgl Exp $ * *------------------------------------------------------------------------- */ #include "postgres.h" -#include "optimizer/clauses.h" #include "optimizer/cost.h" -#include "optimizer/pathnode.h" #include "optimizer/paths.h" +#include "optimizer/planmain.h" #include "optimizer/restrictinfo.h" -static IndexPath *best_or_subclause_indexes(Query *root, RelOptInfo *rel, - List *subclauses); -static bool best_or_subclause_index(Query *root, - RelOptInfo *rel, - Expr *subclause, - IndexOptInfo **retIndexInfo, - List **retIndexClauses, - List **retIndexQuals, - Cost *retStartupCost, - Cost *retTotalCost); - - /*---------- * create_or_index_quals * Examine join OR-of-AND quals to see if any useful restriction OR @@ -94,7 +81,7 @@ static bool best_or_subclause_index(Query *root, bool create_or_index_quals(Query *root, RelOptInfo *rel) { - IndexPath *bestpath = NULL; + BitmapOrPath *bestpath = NULL; RestrictInfo *bestrinfo = NULL; List *newrinfos; RestrictInfo *or_rinfo; @@ -103,8 +90,7 @@ create_or_index_quals(Query *root, RelOptInfo *rel) ListCell *i; /* - * We use the best_or_subclause_indexes() machinery to locate the best - * combination of restriction subclauses. Note we must ignore any + * Find potentially interesting OR joinclauses. We must ignore any * joinclauses that are not marked valid_everywhere, because they * cannot be pushed down due to outer-join rules. */ @@ -120,18 +106,31 @@ create_or_index_quals(Query *root, RelOptInfo *rel) if (restriction_is_or_clause(rinfo) && rinfo->valid_everywhere) { - IndexPath *pathnode; - - pathnode = best_or_subclause_indexes(root, - rel, - ((BoolExpr *) rinfo->orclause)->args); - - if (pathnode) + /* + * Use the generate_bitmap_or_paths() machinery to estimate + * the value of each OR clause. We can use regular + * restriction clauses along with the OR clause contents to + * generate indexquals. We pass outer_relids = NULL so that + * sub-clauses that are actually joins will be ignored. + */ + List *orpaths; + ListCell *k; + + orpaths = generate_bitmap_or_paths(root, rel, + list_make1(rinfo), + rel->baserestrictinfo, + false, NULL); + + /* Locate the cheapest OR path */ + foreach(k, orpaths) { + BitmapOrPath *path = (BitmapOrPath *) lfirst(k); + + Assert(IsA(path, BitmapOrPath)); if (bestpath == NULL || - pathnode->path.total_cost < bestpath->path.total_cost) + path->path.total_cost < bestpath->path.total_cost) { - bestpath = pathnode; + bestpath = path; bestrinfo = rinfo; } } @@ -144,13 +143,14 @@ create_or_index_quals(Query *root, RelOptInfo *rel) return false; /* - * Convert the indexclauses structure to a RestrictInfo tree, and add - * it to the rel's restriction list. + * Convert the path's indexclauses structure to a RestrictInfo tree, + * and add it to the rel's restriction list. */ - newrinfos = make_restrictinfo_from_indexclauses(bestpath->indexclauses, - true, true); + newrinfos = create_bitmap_restriction((Path *) bestpath); Assert(list_length(newrinfos) == 1); or_rinfo = (RestrictInfo *) linitial(newrinfos); + Assert(IsA(or_rinfo, RestrictInfo)); + rel->baserestrictinfo = list_concat(rel->baserestrictinfo, newrinfos); /* @@ -176,242 +176,3 @@ create_or_index_quals(Query *root, RelOptInfo *rel) /* Tell caller to recompute rel's rows estimate */ return true; } - -/* - * create_or_index_paths - * Creates multi-scan index paths for indexes that match OR clauses. - * - * 'rel' is the relation entry for which the paths are to be created - * - * Returns nothing, but adds paths to rel->pathlist via add_path(). - * - * Note: check_partial_indexes() must have been run previously. - */ -void -create_or_index_paths(Query *root, RelOptInfo *rel) -{ - ListCell *l; - - /* - * Check each restriction clause to see if it is an OR clause, and if - * so, try to make a path using it. - */ - foreach(l, rel->baserestrictinfo) - { - RestrictInfo *rinfo = (RestrictInfo *) lfirst(l); - - if (restriction_is_or_clause(rinfo)) - { - IndexPath *pathnode; - - pathnode = best_or_subclause_indexes(root, - rel, - ((BoolExpr *) rinfo->orclause)->args); - - if (pathnode) - add_path(rel, (Path *) pathnode); - } - } -} - -/* - * best_or_subclause_indexes - * Determine the best index to be used in conjunction with each subclause - * of an OR clause, and build a Path for a multi-index scan. - * - * 'rel' is the node of the relation to be scanned - * 'subclauses' are the subclauses of the OR clause (must be the modified - * form that includes sub-RestrictInfo clauses) - * - * Returns an IndexPath if successful, or NULL if it is not possible to - * find an index for each OR subclause. - * - * NOTE: we choose each scan on the basis of its total cost, ignoring startup - * cost. This is reasonable as long as all index types have zero or small - * startup cost, but we might have to work harder if any index types with - * nontrivial startup cost are ever invented. - * - * This routine also creates the indexqual list that will be needed by - * the executor. The indexqual list has one entry for each scan of the base - * rel, which is a sublist of indexqual conditions to apply in that scan. - * The implicit semantics are AND across each sublist of quals, and OR across - * the toplevel list (note that the executor takes care not to return any - * single tuple more than once). - */ -static IndexPath * -best_or_subclause_indexes(Query *root, - RelOptInfo *rel, - List *subclauses) -{ - List *infos = NIL; - List *clauses = NIL; - List *quals = NIL; - Cost path_startup_cost = 0; - Cost path_total_cost = 0; - ListCell *slist; - IndexPath *pathnode; - - /* Gather info for each OR subclause */ - foreach(slist, subclauses) - { - Expr *subclause = lfirst(slist); - IndexOptInfo *best_indexinfo; - List *best_indexclauses; - List *best_indexquals; - Cost best_startup_cost; - Cost best_total_cost; - - if (!best_or_subclause_index(root, rel, subclause, - &best_indexinfo, - &best_indexclauses, &best_indexquals, - &best_startup_cost, &best_total_cost)) - return NULL; /* failed to match this subclause */ - - infos = lappend(infos, best_indexinfo); - clauses = lappend(clauses, best_indexclauses); - quals = lappend(quals, best_indexquals); - - /* - * Path startup_cost is the startup cost for the first index scan - * only; startup costs for later scans will be paid later on, so - * they just get reflected in total_cost. - * - * Total cost is sum of the per-scan costs. - */ - if (slist == list_head(subclauses)) /* first scan? */ - path_startup_cost = best_startup_cost; - path_total_cost += best_total_cost; - } - - /* We succeeded, so build an IndexPath node */ - pathnode = makeNode(IndexPath); - - pathnode->path.pathtype = T_IndexScan; - pathnode->path.parent = rel; - pathnode->path.startup_cost = path_startup_cost; - pathnode->path.total_cost = path_total_cost; - - /* - * This is an IndexScan, but the overall result will consist of tuples - * extracted in multiple passes (one for each subclause of the OR), so - * the result cannot be claimed to have any particular ordering. - */ - pathnode->path.pathkeys = NIL; - - pathnode->indexinfo = infos; - pathnode->indexclauses = clauses; - pathnode->indexquals = quals; - - /* It's not an innerjoin path. */ - pathnode->isjoininner = false; - - /* We don't actually care what order the index scans in. */ - pathnode->indexscandir = NoMovementScanDirection; - - /* - * The number of rows is the same as the parent rel's estimate, since - * this isn't a join inner indexscan. - */ - pathnode->rows = rel->rows; - - return pathnode; -} - -/* - * best_or_subclause_index - * Determines which is the best index to be used with a subclause of an - * OR clause by estimating the cost of using each index and selecting - * the least expensive (considering total cost only, for now). - * - * Returns FALSE if no index exists that can be used with this OR subclause; - * in that case the output parameters are not set. - * - * 'rel' is the node of the relation to be scanned - * 'subclause' is the OR subclause being considered - * - * '*retIndexInfo' gets the IndexOptInfo of the best index - * '*retIndexClauses' gets a list of the index clauses for the best index - * '*retIndexQuals' gets a list of the expanded indexquals for the best index - * '*retStartupCost' gets the startup cost of a scan with that index - * '*retTotalCost' gets the total cost of a scan with that index - */ -static bool -best_or_subclause_index(Query *root, - RelOptInfo *rel, - Expr *subclause, - IndexOptInfo **retIndexInfo, /* return value */ - List **retIndexClauses, /* return value */ - List **retIndexQuals, /* return value */ - Cost *retStartupCost, /* return value */ - Cost *retTotalCost) /* return value */ -{ - bool found = false; - ListCell *ilist; - - foreach(ilist, rel->indexlist) - { - IndexOptInfo *index = (IndexOptInfo *) lfirst(ilist); - List *indexclauses; - List *indexquals; - IndexPath subclause_path; - - /* - * Ignore partial indexes that do not match the query. If predOK - * is true then the index's predicate is implied by top-level - * restriction clauses, so we can use it. However, it might also - * be implied by the current OR subclause (perhaps in conjunction - * with the top-level clauses), in which case we can use it for this - * particular scan. - * - * XXX this code is partially redundant with logic in - * group_clauses_by_indexkey_for_or(); consider refactoring. - */ - if (index->indpred != NIL && !index->predOK) - { - List *subclauserinfos; - - if (and_clause((Node *) subclause)) - subclauserinfos = list_copy(((BoolExpr *) subclause)->args); - else if (IsA(subclause, RestrictInfo)) - subclauserinfos = list_make1(subclause); - else - continue; /* probably can't happen */ - if (!pred_test(index->indpred, - list_concat(subclauserinfos, - rel->baserestrictinfo))) - continue; - } - - /* Collect index clauses usable with this index */ - indexclauses = group_clauses_by_indexkey_for_or(index, subclause); - - /* - * Ignore index if it doesn't match the subclause at all; except - * that if it's a partial index matching the current OR subclause, - * consider it anyway, since effectively we are using the index - * predicate to match the subclause. (Note: we exclude partial - * indexes that are predOK; else such a partial index would be - * considered to match *every* OR subclause, generating bogus OR - * plans that are redundant with the basic scan on that index.) - */ - if (indexclauses == NIL && (index->indpred == NIL || index->predOK)) - continue; - - /* Convert clauses to indexquals the executor can handle */ - indexquals = expand_indexqual_conditions(index, indexclauses); - - cost_index(&subclause_path, root, index, indexquals, false); - - if (!found || subclause_path.path.total_cost < *retTotalCost) - { - *retIndexInfo = index; - *retIndexClauses = flatten_clausegroups_list(indexclauses); - *retIndexQuals = indexquals; - *retStartupCost = subclause_path.path.startup_cost; - *retTotalCost = subclause_path.path.total_cost; - found = true; - } - } - - return found; -} |