diff options
author | Bruce Momjian <bruce@momjian.us> | 2000-04-12 17:17:23 +0000 |
---|---|---|
committer | Bruce Momjian <bruce@momjian.us> | 2000-04-12 17:17:23 +0000 |
commit | 52f77df613cea1803ce86321c37229626d9f213c (patch) | |
tree | bd9ac9f667f295cb65f4c448a5bb5a062d656b27 /src/backend/optimizer/path | |
parent | db4518729d85da83eafdacbcebaeb12618517595 (diff) | |
download | postgresql-52f77df613cea1803ce86321c37229626d9f213c.tar.gz |
Ye-old pgindent run. Same 4-space tabs.
Diffstat (limited to 'src/backend/optimizer/path')
-rw-r--r-- | src/backend/optimizer/path/_deadcode/predmig.c | 4 | ||||
-rw-r--r-- | src/backend/optimizer/path/allpaths.c | 33 | ||||
-rw-r--r-- | src/backend/optimizer/path/clausesel.c | 131 | ||||
-rw-r--r-- | src/backend/optimizer/path/costsize.c | 197 | ||||
-rw-r--r-- | src/backend/optimizer/path/indxpath.c | 375 | ||||
-rw-r--r-- | src/backend/optimizer/path/joinpath.c | 184 | ||||
-rw-r--r-- | src/backend/optimizer/path/joinrels.c | 60 | ||||
-rw-r--r-- | src/backend/optimizer/path/orindxpath.c | 41 | ||||
-rw-r--r-- | src/backend/optimizer/path/pathkeys.c | 168 | ||||
-rw-r--r-- | src/backend/optimizer/path/tidpath.c | 159 |
10 files changed, 743 insertions, 609 deletions
diff --git a/src/backend/optimizer/path/_deadcode/predmig.c b/src/backend/optimizer/path/_deadcode/predmig.c index 377a836d9a..434780d664 100644 --- a/src/backend/optimizer/path/_deadcode/predmig.c +++ b/src/backend/optimizer/path/_deadcode/predmig.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/_deadcode/Attic/predmig.c,v 1.6 2000/01/26 05:56:36 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/_deadcode/Attic/predmig.c,v 1.7 2000/04/12 17:15:21 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -485,7 +485,7 @@ xfunc_form_groups(Query *queryInfo, Stream root, Stream bottom) } -/* ------------------- UTILITY FUNCTIONS ------------------------- */ +/* ------------------- UTILITY FUNCTIONS ------------------------- */ /* ** xfunc_free_stream diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 572ef00d2e..a2e636395e 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/allpaths.c,v 1.59 2000/02/15 20:49:16 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/allpaths.c,v 1.60 2000/04/12 17:15:19 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -24,8 +24,10 @@ #ifdef GEQO bool enable_geqo = true; + #else bool enable_geqo = false; + #endif int geqo_rels = GEQO_RELS; @@ -36,6 +38,7 @@ static RelOptInfo *make_one_rel_by_joins(Query *root, int levels_needed); #ifdef OPTIMIZER_DEBUG static void debug_print_rel(Query *root, RelOptInfo *rel); + #endif @@ -64,6 +67,7 @@ make_one_rel(Query *root) if (levels_needed == 1) { + /* * Single relation, no more processing is required. */ @@ -71,6 +75,7 @@ make_one_rel(Query *root) } else { + /* * Generate join tree. */ @@ -100,8 +105,8 @@ set_base_rel_pathlist(Query *root) /* * Generate paths and add them to the rel's pathlist. * - * Note: add_path() will discard any paths that are dominated - * by another available path, keeping only those paths that are + * Note: add_path() will discard any paths that are dominated by + * another available path, keeping only those paths that are * superior along at least one dimension of cost or sortedness. */ @@ -116,9 +121,10 @@ set_base_rel_pathlist(Query *root) rel->baserestrictinfo, rel->joininfo); - /* Note: create_or_index_paths depends on create_index_paths - * to have marked OR restriction clauses with relevant indices; - * this is why it doesn't need to be given the list of indices. + /* + * Note: create_or_index_paths depends on create_index_paths to + * have marked OR restriction clauses with relevant indices; this + * is why it doesn't need to be given the list of indices. */ create_or_index_paths(root, rel, rel->baserestrictinfo); @@ -153,11 +159,11 @@ make_one_rel_by_joins(Query *root, int levels_needed) return geqo(root); /* - * We employ a simple "dynamic programming" algorithm: we first - * find all ways to build joins of two base relations, then all ways - * to build joins of three base relations (from two-base-rel joins - * and other base rels), then four-base-rel joins, and so on until - * we have considered all ways to join all N relations into one rel. + * We employ a simple "dynamic programming" algorithm: we first find + * all ways to build joins of two base relations, then all ways to + * build joins of three base relations (from two-base-rel joins and + * other base rels), then four-base-rel joins, and so on until we have + * considered all ways to join all N relations into one rel. */ for (lev = 2; lev <= levels_needed; lev++) @@ -185,9 +191,10 @@ make_one_rel_by_joins(Query *root, int levels_needed) rel = (RelOptInfo *) lfirst(x); #ifdef NOT_USED + /* - * * for each expensive predicate in each path in each distinct - * rel, * consider doing pullup -- JMH + * * for each expensive predicate in each path in each + * distinct rel, * consider doing pullup -- JMH */ if (XfuncMode != XFUNC_NOPULL && XfuncMode != XFUNC_OFF) xfunc_trypullup(rel); diff --git a/src/backend/optimizer/path/clausesel.c b/src/backend/optimizer/path/clausesel.c index 985155edf9..d430059a1e 100644 --- a/src/backend/optimizer/path/clausesel.c +++ b/src/backend/optimizer/path/clausesel.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/clausesel.c,v 1.33 2000/03/23 23:35:47 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/clausesel.c,v 1.34 2000/04/12 17:15:19 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -28,17 +28,18 @@ * Data structure for accumulating info about possible range-query * clause pairs in clauselist_selectivity. */ -typedef struct RangeQueryClause { - struct RangeQueryClause *next; /* next in linked list */ +typedef struct RangeQueryClause +{ + struct RangeQueryClause *next; /* next in linked list */ Node *var; /* The common variable of the clauses */ bool have_lobound; /* found a low-bound clause yet? */ bool have_hibound; /* found a high-bound clause yet? */ - Selectivity lobound; /* Selectivity of a var > something clause */ - Selectivity hibound; /* Selectivity of a var < something clause */ + Selectivity lobound; /* Selectivity of a var > something clause */ + Selectivity hibound; /* Selectivity of a var < something clause */ } RangeQueryClause; static void addRangeClause(RangeQueryClause **rqlist, Node *clause, - int flag, bool isLTsel, Selectivity s2); + int flag, bool isLTsel, Selectivity s2); /**************************************************************************** @@ -59,7 +60,7 @@ restrictlist_selectivity(Query *root, int varRelid) { List *clauselist = get_actual_clauses(restrictinfo_list); - Selectivity result; + Selectivity result; result = clauselist_selectivity(root, clauselist, varRelid); freeList(clauselist); @@ -75,7 +76,7 @@ restrictlist_selectivity(Query *root, * See clause_selectivity() for the meaning of the varRelid parameter. * * Our basic approach is to take the product of the selectivities of the - * subclauses. However, that's only right if the subclauses have independent + * subclauses. However, that's only right if the subclauses have independent * probabilities, and in reality they are often NOT independent. So, * we want to be smarter where we can. @@ -92,7 +93,7 @@ restrictlist_selectivity(Query *root, * see that hisel is the fraction of the range below the high bound, while * losel is the fraction above the low bound; so hisel can be interpreted * directly as a 0..1 value but we need to convert losel to 1-losel before - * interpreting it as a value. Then the available range is 1-losel to hisel.) + * interpreting it as a value. Then the available range is 1-losel to hisel.) * If the calculation yields zero or negative, however, we chicken out and * use the default interpretation; that probably means that one or both * selectivities is a default estimate rather than an actual range value. @@ -104,9 +105,9 @@ clauselist_selectivity(Query *root, List *clauses, int varRelid) { - Selectivity s1 = 1.0; - RangeQueryClause *rqlist = NULL; - List *clist; + Selectivity s1 = 1.0; + RangeQueryClause *rqlist = NULL; + List *clist; /* * Initial scan over clauses. Anything that doesn't look like a @@ -116,13 +117,13 @@ clauselist_selectivity(Query *root, foreach(clist, clauses) { Node *clause = (Node *) lfirst(clist); - Selectivity s2; + Selectivity s2; /* - * See if it looks like a restriction clause with a constant. - * (If it's not a constant we can't really trust the selectivity!) - * NB: for consistency of results, this fragment of code had - * better match what clause_selectivity() would do. + * See if it looks like a restriction clause with a constant. (If + * it's not a constant we can't really trust the selectivity!) NB: + * for consistency of results, this fragment of code had better + * match what clause_selectivity() would do. */ if (varRelid != 0 || NumRelids(clause) == 1) { @@ -147,11 +148,12 @@ clauselist_selectivity(Query *root, root->rtable), attno, constval, flag); + /* - * If we reach here, we have computed the same result - * that clause_selectivity would, so we can just use s2 - * if it's the wrong oprrest. But if it's the right - * oprrest, add the clause to rqlist for later processing. + * If we reach here, we have computed the same result that + * clause_selectivity would, so we can just use s2 if it's + * the wrong oprrest. But if it's the right oprrest, add + * the clause to rqlist for later processing. */ switch (oprrest) { @@ -166,7 +168,7 @@ clauselist_selectivity(Query *root, s1 = s1 * s2; break; } - continue; /* drop to loop bottom */ + continue; /* drop to loop bottom */ } } /* Not the right form, so treat it generically. */ @@ -179,12 +181,12 @@ clauselist_selectivity(Query *root, */ while (rqlist != NULL) { - RangeQueryClause *rqnext; + RangeQueryClause *rqnext; if (rqlist->have_lobound && rqlist->have_hibound) { /* Successfully matched a pair of range clauses */ - Selectivity s2 = rqlist->hibound + rqlist->lobound - 1.0; + Selectivity s2 = rqlist->hibound + rqlist->lobound - 1.0; /* * A zero or slightly negative s2 should be converted into a @@ -199,14 +201,20 @@ clauselist_selectivity(Query *root, { if (s2 < -0.01) { - /* No data available --- use a default estimate that + + /* + * No data available --- use a default estimate that * is small, but not real small. */ s2 = 0.01; } else { - /* It's just roundoff error; use a small positive value */ + + /* + * It's just roundoff error; use a small positive + * value + */ s2 = 1.0e-10; } } @@ -239,15 +247,15 @@ static void addRangeClause(RangeQueryClause **rqlist, Node *clause, int flag, bool isLTsel, Selectivity s2) { - RangeQueryClause *rqelem; - Node *var; - bool is_lobound; + RangeQueryClause *rqelem; + Node *var; + bool is_lobound; /* get_relattval sets flag&SEL_RIGHT if the var is on the LEFT. */ if (flag & SEL_RIGHT) { var = (Node *) get_leftop((Expr *) clause); - is_lobound = ! isLTsel; /* x < something is high bound */ + is_lobound = !isLTsel; /* x < something is high bound */ } else { @@ -257,23 +265,27 @@ addRangeClause(RangeQueryClause **rqlist, Node *clause, for (rqelem = *rqlist; rqelem; rqelem = rqelem->next) { - /* We use full equal() here because the "var" might be a function + + /* + * We use full equal() here because the "var" might be a function * of one or more attributes of the same relation... */ - if (! equal(var, rqelem->var)) + if (!equal(var, rqelem->var)) continue; /* Found the right group to put this clause in */ if (is_lobound) { - if (! rqelem->have_lobound) + if (!rqelem->have_lobound) { rqelem->have_lobound = true; rqelem->lobound = s2; } else { - /* We have found two similar clauses, such as - * x < y AND x < z. Keep only the more restrictive one. + + /* + * We have found two similar clauses, such as x < y AND x + * < z. Keep only the more restrictive one. */ if (rqelem->lobound > s2) rqelem->lobound = s2; @@ -281,15 +293,17 @@ addRangeClause(RangeQueryClause **rqlist, Node *clause, } else { - if (! rqelem->have_hibound) + if (!rqelem->have_hibound) { rqelem->have_hibound = true; rqelem->hibound = s2; } else { - /* We have found two similar clauses, such as - * x > y AND x > z. Keep only the more restrictive one. + + /* + * We have found two similar clauses, such as x > y AND x + * > z. Keep only the more restrictive one. */ if (rqelem->hibound > s2) rqelem->hibound = s2; @@ -331,7 +345,7 @@ addRangeClause(RangeQueryClause **rqlist, Node *clause, * nestloop join's inner relation --- varRelid should then be the ID of the * inner relation. * - * When varRelid is 0, all variables are treated as variables. This + * When varRelid is 0, all variables are treated as variables. This * is appropriate for ordinary join clauses and restriction clauses. */ Selectivity @@ -339,12 +353,13 @@ clause_selectivity(Query *root, Node *clause, int varRelid) { - Selectivity s1 = 1.0; /* default for any unhandled clause type */ + Selectivity s1 = 1.0; /* default for any unhandled clause type */ if (clause == NULL) return s1; if (IsA(clause, Var)) { + /* * we have a bool Var. This is exactly equivalent to the clause: * reln.attribute = 't' so we compute the selectivity as if that @@ -352,7 +367,7 @@ clause_selectivity(Query *root, * didn't want to have to do system cache look ups to find out all * of that info. */ - Index varno = ((Var *) clause)->varno; + Index varno = ((Var *) clause)->varno; if (varRelid == 0 || varRelid == (int) varno) s1 = restriction_selectivity(F_EQSEL, @@ -377,7 +392,7 @@ clause_selectivity(Query *root, { /* inverse of the selectivity of the underlying clause */ s1 = 1.0 - clause_selectivity(root, - (Node*) get_notclausearg((Expr*) clause), + (Node *) get_notclausearg((Expr *) clause), varRelid); } else if (and_clause(clause)) @@ -389,18 +404,21 @@ clause_selectivity(Query *root, } else if (or_clause(clause)) { + /* * Selectivities for an 'or' clause are computed as s1+s2 - s1*s2 - * to account for the probable overlap of selected tuple sets. - * XXX is this too conservative? + * to account for the probable overlap of selected tuple sets. XXX + * is this too conservative? */ - List *arg; + List *arg; + s1 = 0.0; foreach(arg, ((Expr *) clause)->args) { - Selectivity s2 = clause_selectivity(root, + Selectivity s2 = clause_selectivity(root, (Node *) lfirst(arg), varRelid); + s1 = s1 + s2 - s1 * s2; } } @@ -411,17 +429,20 @@ clause_selectivity(Query *root, if (varRelid != 0) { + /* - * If we are considering a nestloop join then all clauses - * are restriction clauses, since we are only interested in - * the one relation. + * If we are considering a nestloop join then all clauses are + * restriction clauses, since we are only interested in the + * one relation. */ is_join_clause = false; } else { + /* - * Otherwise, it's a join if there's more than one relation used. + * Otherwise, it's a join if there's more than one relation + * used. */ is_join_clause = (NumRelids(clause) > 1); } @@ -432,8 +453,8 @@ clause_selectivity(Query *root, RegProcedure oprjoin = get_oprjoin(opno); /* - * if the oprjoin procedure is missing for whatever reason, use a - * selectivity of 0.5 + * if the oprjoin procedure is missing for whatever reason, + * use a selectivity of 0.5 */ if (!oprjoin) s1 = (Selectivity) 0.5; @@ -460,8 +481,8 @@ clause_selectivity(Query *root, RegProcedure oprrest = get_oprrest(opno); /* - * if the oprrest procedure is missing for whatever reason, use a - * selectivity of 0.5 + * if the oprrest procedure is missing for whatever reason, + * use a selectivity of 0.5 */ if (!oprrest) s1 = (Selectivity) 0.5; @@ -484,6 +505,7 @@ clause_selectivity(Query *root, } else if (is_funcclause(clause)) { + /* * This is not an operator, so we guess at the selectivity. THIS * IS A HACK TO GET V4 OUT THE DOOR. FUNCS SHOULD BE ABLE TO HAVE @@ -493,6 +515,7 @@ clause_selectivity(Query *root, } else if (is_subplan(clause)) { + /* * Just for the moment! FIX ME! - vadim 02/04/98 */ diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index f6bdcb828b..6ecfb2a471 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -19,7 +19,7 @@ * * Obviously, taking constants for these values is an oversimplification, * but it's tough enough to get any useful estimates even at this level of - * detail. Note that all of these parameters are user-settable, in case + * detail. Note that all of these parameters are user-settable, in case * the default values are drastically off for a particular platform. * * We compute two separate costs for each path: @@ -37,12 +37,12 @@ * will be no zero divide.) RelOptInfos, Paths, and Plans themselves never * account for LIMIT. * - * + * * Portions Copyright (c) 1996-2000, PostgreSQL, Inc * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/costsize.c,v 1.56 2000/04/09 04:31:36 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/costsize.c,v 1.57 2000/04/12 17:15:19 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -118,6 +118,7 @@ cost_seqscan(Path *path, RelOptInfo *baserel) /* disk costs */ if (lfirsti(baserel->relids) < 0) { + /* * cost of sequentially scanning a materialized temporary relation */ @@ -125,15 +126,17 @@ cost_seqscan(Path *path, RelOptInfo *baserel) } else { + /* * The cost of reading a page sequentially is 1.0, by definition. * Note that the Unix kernel will typically do some amount of - * read-ahead optimization, so that this cost is less than the true - * cost of reading a page from disk. We ignore that issue here, - * but must take it into account when estimating the cost of + * read-ahead optimization, so that this cost is less than the + * true cost of reading a page from disk. We ignore that issue + * here, but must take it into account when estimating the cost of * non-sequential accesses! */ - run_cost += baserel->pages; /* sequential fetches with cost 1.0 */ + run_cost += baserel->pages; /* sequential fetches with cost + * 1.0 */ } /* CPU costs */ @@ -151,7 +154,7 @@ cost_seqscan(Path *path, RelOptInfo *baserel) * * The simplistic model that the cost is random_page_cost is what we want * to use for large relations; but for small ones that is a serious - * overestimate because of the effects of caching. This routine tries to + * overestimate because of the effects of caching. This routine tries to * account for that. * * Unfortunately we don't have any good way of estimating the effective cache @@ -221,12 +224,12 @@ cost_index(Path *path, Query *root, Cost cpu_per_tuple; Cost indexStartupCost; Cost indexTotalCost; - Selectivity indexSelectivity; + Selectivity indexSelectivity; double tuples_fetched; double pages_fetched; /* Should only be applied to base relations */ - Assert(IsA(baserel, RelOptInfo) && IsA(index, IndexOptInfo)); + Assert(IsA(baserel, RelOptInfo) &&IsA(index, IndexOptInfo)); Assert(length(baserel->relids) == 1); if (!enable_indexscan && !is_injoin) @@ -234,8 +237,9 @@ cost_index(Path *path, Query *root, /* * Call index-access-method-specific code to estimate the processing - * cost for scanning the index, as well as the selectivity of the index - * (ie, the fraction of main-table tuples we will have to retrieve). + * cost for scanning the index, as well as the selectivity of the + * index (ie, the fraction of main-table tuples we will have to + * retrieve). */ fmgr(index->amcostestimate, root, baserel, index, indexQuals, &indexStartupCost, &indexTotalCost, &indexSelectivity); @@ -249,17 +253,18 @@ cost_index(Path *path, Query *root, * * If the number of tuples is much smaller than the number of pages in * the relation, each tuple will cost a separate nonsequential fetch. - * If it is comparable or larger, then probably we will be able to avoid - * some fetches. We use a growth rate of log(#tuples/#pages + 1) --- - * probably totally bogus, but intuitively it gives the right shape of - * curve at least. + * If it is comparable or larger, then probably we will be able to + * avoid some fetches. We use a growth rate of log(#tuples/#pages + + * 1) --- probably totally bogus, but intuitively it gives the right + * shape of curve at least. * * XXX if the relation has recently been "clustered" using this index, - * then in fact the target tuples will be highly nonuniformly distributed, - * and we will be seriously overestimating the scan cost! Currently we - * have no way to know whether the relation has been clustered, nor how - * much it's been modified since the last clustering, so we ignore this - * effect. Would be nice to do better someday. + * then in fact the target tuples will be highly nonuniformly + * distributed, and we will be seriously overestimating the scan cost! + * Currently we have no way to know whether the relation has been + * clustered, nor how much it's been modified since the last + * clustering, so we ignore this effect. Would be nice to do better + * someday. */ tuples_fetched = indexSelectivity * baserel->tuples; @@ -274,8 +279,8 @@ cost_index(Path *path, Query *root, pages_fetched = tuples_fetched; /* - * Now estimate one nonsequential access per page fetched, - * plus appropriate CPU costs per tuple. + * Now estimate one nonsequential access per page fetched, plus + * appropriate CPU costs per tuple. */ /* disk costs for main table */ @@ -283,16 +288,18 @@ cost_index(Path *path, Query *root, /* CPU costs */ cpu_per_tuple = cpu_tuple_cost + baserel->baserestrictcost; + /* - * Normally the indexquals will be removed from the list of restriction - * clauses that we have to evaluate as qpquals, so we should subtract - * their costs from baserestrictcost. For a lossy index, however, we - * will have to recheck all the quals and so mustn't subtract anything. - * Also, if we are doing a join then some of the indexquals are join - * clauses and shouldn't be subtracted. Rather than work out exactly - * how much to subtract, we don't subtract anything in that case either. + * Normally the indexquals will be removed from the list of + * restriction clauses that we have to evaluate as qpquals, so we + * should subtract their costs from baserestrictcost. For a lossy + * index, however, we will have to recheck all the quals and so + * mustn't subtract anything. Also, if we are doing a join then some + * of the indexquals are join clauses and shouldn't be subtracted. + * Rather than work out exactly how much to subtract, we don't + * subtract anything in that case either. */ - if (! index->lossy && ! is_injoin) + if (!index->lossy && !is_injoin) cpu_per_tuple -= cost_qual_eval(indexQuals); run_cost += cpu_per_tuple * tuples_fetched; @@ -326,7 +333,7 @@ cost_tidscan(Path *path, RelOptInfo *baserel, List *tideval) path->startup_cost = startup_cost; path->total_cost = startup_cost + run_cost; } - + /* * cost_sort * Determines and returns the cost of sorting a relation. @@ -341,7 +348,7 @@ cost_tidscan(Path *path, RelOptInfo *baserel, List *tideval) * If the total volume exceeds SortMem, we switch to a tape-style merge * algorithm. There will still be about t*log2(t) tuple comparisons in * total, but we will also need to write and read each tuple once per - * merge pass. We expect about ceil(log6(r)) merge passes where r is the + * merge pass. We expect about ceil(log6(r)) merge passes where r is the * number of initial runs formed (log6 because tuplesort.c uses six-tape * merging). Since the average initial run should be about twice SortMem, * we have @@ -385,8 +392,8 @@ cost_sort(Path *path, List *pathkeys, double tuples, int width) /* * CPU costs * - * Assume about two operator evals per tuple comparison - * and N log2 N comparisons + * Assume about two operator evals per tuple comparison and N log2 N + * comparisons */ startup_cost += 2.0 * cpu_operator_cost * tuples * LOG2(tuples); @@ -408,7 +415,7 @@ cost_sort(Path *path, List *pathkeys, double tuples, int width) /* * Note: should we bother to assign a nonzero run_cost to reflect the - * overhead of extracting tuples from the sort result? Probably not + * overhead of extracting tuples from the sort result? Probably not * worth worrying about. */ path->startup_cost = startup_cost; @@ -440,19 +447,22 @@ cost_nestloop(Path *path, startup_cost += disable_cost; /* cost of source data */ + /* - * NOTE: we assume that the inner path's startup_cost is paid once, not - * over again on each restart. This is certainly correct if the inner - * path is materialized. Are there any cases where it is wrong? + * NOTE: we assume that the inner path's startup_cost is paid once, + * not over again on each restart. This is certainly correct if the + * inner path is materialized. Are there any cases where it is wrong? */ startup_cost += outer_path->startup_cost + inner_path->startup_cost; run_cost += outer_path->total_cost - outer_path->startup_cost; run_cost += outer_path->parent->rows * (inner_path->total_cost - inner_path->startup_cost); - /* Number of tuples processed (not number emitted!). If inner path is + /* + * Number of tuples processed (not number emitted!). If inner path is * an indexscan, be sure to use its estimated output row count, which - * may be lower than the restriction-clause-only row count of its parent. + * may be lower than the restriction-clause-only row count of its + * parent. */ if (IsA(inner_path, IndexPath)) ntuples = ((IndexPath *) inner_path)->rows; @@ -498,11 +508,12 @@ cost_mergejoin(Path *path, startup_cost += disable_cost; /* cost of source data */ + /* * Note we are assuming that each source tuple is fetched just once, - * which is not right in the presence of equal keys. If we had a way of - * estimating the proportion of equal keys, we could apply a correction - * factor... + * which is not right in the presence of equal keys. If we had a way + * of estimating the proportion of equal keys, we could apply a + * correction factor... */ if (outersortkeys) /* do we need to sort outer? */ { @@ -537,10 +548,10 @@ cost_mergejoin(Path *path, } /* - * Estimate the number of tuples to be processed in the mergejoin itself - * as one per tuple in the two source relations. This could be a drastic - * underestimate if there are many equal-keyed tuples in either relation, - * but we have no good way of estimating that... + * Estimate the number of tuples to be processed in the mergejoin + * itself as one per tuple in the two source relations. This could be + * a drastic underestimate if there are many equal-keyed tuples in + * either relation, but we have no good way of estimating that... */ ntuples = outer_path->parent->rows + inner_path->parent->rows; @@ -575,9 +586,9 @@ cost_hashjoin(Path *path, Cost cpu_per_tuple; double ntuples; double outerbytes = relation_byte_size(outer_path->parent->rows, - outer_path->parent->width); + outer_path->parent->width); double innerbytes = relation_byte_size(inner_path->parent->rows, - inner_path->parent->width); + inner_path->parent->width); long hashtablebytes = SortMem * 1024L; if (!enable_hashjoin) @@ -592,7 +603,8 @@ cost_hashjoin(Path *path, startup_cost += cpu_operator_cost * inner_path->parent->rows; run_cost += cpu_operator_cost * outer_path->parent->rows; - /* the number of tuple comparisons needed is the number of outer + /* + * the number of tuple comparisons needed is the number of outer * tuples times the typical hash bucket size, which we estimate * conservatively as the inner disbursion times the inner tuple count. */ @@ -601,9 +613,9 @@ cost_hashjoin(Path *path, /* * Estimate the number of tuples that get through the hashing filter - * as one per tuple in the two source relations. This could be a drastic - * underestimate if there are many equal-keyed tuples in either relation, - * but we have no good way of estimating that... + * as one per tuple in the two source relations. This could be a + * drastic underestimate if there are many equal-keyed tuples in + * either relation, but we have no good way of estimating that... */ ntuples = outer_path->parent->rows + inner_path->parent->rows; @@ -614,33 +626,31 @@ cost_hashjoin(Path *path, /* * if inner relation is too big then we will need to "batch" the join, * which implies writing and reading most of the tuples to disk an - * extra time. Charge one cost unit per page of I/O (correct since - * it should be nice and sequential...). Writing the inner rel counts - * as startup cost, all the rest as run cost. + * extra time. Charge one cost unit per page of I/O (correct since it + * should be nice and sequential...). Writing the inner rel counts as + * startup cost, all the rest as run cost. */ if (innerbytes > hashtablebytes) { - double outerpages = page_size(outer_path->parent->rows, - outer_path->parent->width); - double innerpages = page_size(inner_path->parent->rows, - inner_path->parent->width); + double outerpages = page_size(outer_path->parent->rows, + outer_path->parent->width); + double innerpages = page_size(inner_path->parent->rows, + inner_path->parent->width); startup_cost += innerpages; run_cost += innerpages + 2 * outerpages; } /* - * Bias against putting larger relation on inside. We don't want - * an absolute prohibition, though, since larger relation might have + * Bias against putting larger relation on inside. We don't want an + * absolute prohibition, though, since larger relation might have * better disbursion --- and we can't trust the size estimates - * unreservedly, anyway. Instead, inflate the startup cost by - * the square root of the size ratio. (Why square root? No real good + * unreservedly, anyway. Instead, inflate the startup cost by the + * square root of the size ratio. (Why square root? No real good * reason, but it seems reasonable...) */ if (innerbytes > outerbytes && outerbytes > 0) - { startup_cost *= sqrt(innerbytes / outerbytes); - } path->startup_cost = startup_cost; path->total_cost = startup_cost + run_cost; @@ -656,7 +666,7 @@ cost_hashjoin(Path *path, Cost cost_qual_eval(List *quals) { - Cost total = 0; + Cost total = 0; cost_qual_eval_walker((Node *) quals, &total); return total; @@ -667,10 +677,11 @@ cost_qual_eval_walker(Node *node, Cost *total) { if (node == NULL) return false; + /* * Our basic strategy is to charge one cpu_operator_cost for each - * operator or function node in the given tree. Vars and Consts - * are charged zero, and so are boolean operators (AND, OR, NOT). + * operator or function node in the given tree. Vars and Consts are + * charged zero, and so are boolean operators (AND, OR, NOT). * Simplistic, but a lot better than no model at all. * * Should we try to account for the possibility of short-circuit @@ -678,7 +689,7 @@ cost_qual_eval_walker(Node *node, Cost *total) */ if (IsA(node, Expr)) { - Expr *expr = (Expr *) node; + Expr *expr = (Expr *) node; switch (expr->opType) { @@ -691,17 +702,19 @@ cost_qual_eval_walker(Node *node, Cost *total) case NOT_EXPR: break; case SUBPLAN_EXPR: + /* - * A subplan node in an expression indicates that the subplan - * will be executed on each evaluation, so charge accordingly. - * (We assume that sub-selects that can be executed as - * InitPlans have already been removed from the expression.) + * A subplan node in an expression indicates that the + * subplan will be executed on each evaluation, so charge + * accordingly. (We assume that sub-selects that can be + * executed as InitPlans have already been removed from + * the expression.) * * NOTE: this logic should agree with the estimates used by - * make_subplan() in plan/subselect.c. + * make_subplan() in plan/subselect.c. */ { - SubPlan *subplan = (SubPlan *) expr->oper; + SubPlan *subplan = (SubPlan *) expr->oper; Plan *plan = subplan->plan; Cost subcost; @@ -730,13 +743,14 @@ cost_qual_eval_walker(Node *node, Cost *total) } /* fall through to examine args of Expr node */ } + /* - * expression_tree_walker doesn't know what to do with RestrictInfo nodes, - * but we just want to recurse through them. + * expression_tree_walker doesn't know what to do with RestrictInfo + * nodes, but we just want to recurse through them. */ if (IsA(node, RestrictInfo)) { - RestrictInfo *restrictinfo = (RestrictInfo *) node; + RestrictInfo *restrictinfo = (RestrictInfo *) node; return cost_qual_eval_walker((Node *) restrictinfo->clause, total); } @@ -755,7 +769,7 @@ cost_qual_eval_walker(Node *node, Cost *total) * * We set the following fields of the rel node: * rows: the estimated number of output tuples (after applying - * restriction clauses). + * restriction clauses). * width: the estimated average output tuple width in bytes. * baserestrictcost: estimated cost of evaluating baserestrictinfo clauses. */ @@ -769,9 +783,11 @@ set_baserel_size_estimates(Query *root, RelOptInfo *rel) restrictlist_selectivity(root, rel->baserestrictinfo, lfirsti(rel->relids)); + /* * Force estimate to be at least one row, to make explain output look - * better and to avoid possible divide-by-zero when interpolating cost. + * better and to avoid possible divide-by-zero when interpolating + * cost. */ if (rel->rows < 1.0) rel->rows = 1.0; @@ -812,10 +828,10 @@ set_joinrel_size_estimates(Query *root, RelOptInfo *rel, temp = outer_rel->rows * inner_rel->rows; /* - * Apply join restrictivity. Note that we are only considering clauses - * that become restriction clauses at this join level; we are not - * double-counting them because they were not considered in estimating - * the sizes of the component rels. + * Apply join restrictivity. Note that we are only considering + * clauses that become restriction clauses at this join level; we are + * not double-counting them because they were not considered in + * estimating the sizes of the component rels. */ temp *= restrictlist_selectivity(root, restrictlist, @@ -823,7 +839,8 @@ set_joinrel_size_estimates(Query *root, RelOptInfo *rel, /* * Force estimate to be at least one row, to make explain output look - * better and to avoid possible divide-by-zero when interpolating cost. + * better and to avoid possible divide-by-zero when interpolating + * cost. */ if (temp < 1.0) temp = 1.0; @@ -833,8 +850,8 @@ set_joinrel_size_estimates(Query *root, RelOptInfo *rel, * We could apply set_rel_width() to compute the output tuple width * from scratch, but at present it's always just the sum of the input * widths, so why work harder than necessary? If relnode.c is ever - * taught to remove unneeded columns from join targetlists, go back - * to using set_rel_width here. + * taught to remove unneeded columns from join targetlists, go back to + * using set_rel_width here. */ rel->width = outer_rel->width + inner_rel->width; } @@ -859,7 +876,7 @@ set_rel_width(Query *root, RelOptInfo *rel) * compute_attribute_width * Given a target list entry, find the size in bytes of the attribute. * - * If a field is variable-length, we make a default assumption. Would be + * If a field is variable-length, we make a default assumption. Would be * better if VACUUM recorded some stats about the average field width... * also, we have access to the atttypmod, but fail to use it... */ diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 8c63d9e1c3..98c5112f7c 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -9,7 +9,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.81 2000/03/22 22:08:33 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.82 2000/04/12 17:15:19 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -46,62 +46,63 @@ #define is_indexable_operator(clause,opclass,relam,indexkey_on_left) \ (indexable_operator(clause,opclass,relam,indexkey_on_left) != InvalidOid) -typedef enum { +typedef enum +{ Prefix_None, Prefix_Partial, Prefix_Exact } Prefix_Status; static void match_index_orclauses(RelOptInfo *rel, IndexOptInfo *index, - List *restrictinfo_list); + List *restrictinfo_list); static List *match_index_orclause(RelOptInfo *rel, IndexOptInfo *index, - List *or_clauses, - List *other_matching_indices); + List *or_clauses, + List *other_matching_indices); static bool match_or_subclause_to_indexkey(RelOptInfo *rel, - IndexOptInfo *index, - Expr *clause); + IndexOptInfo *index, + Expr *clause); static List *group_clauses_by_indexkey(RelOptInfo *rel, IndexOptInfo *index, - int *indexkeys, Oid *classes, - List *restrictinfo_list); + int *indexkeys, Oid *classes, + List *restrictinfo_list); static List *group_clauses_by_ikey_for_joins(RelOptInfo *rel, - IndexOptInfo *index, - int *indexkeys, Oid *classes, - List *join_cinfo_list, - List *restr_cinfo_list); + IndexOptInfo *index, + int *indexkeys, Oid *classes, + List *join_cinfo_list, + List *restr_cinfo_list); static bool match_clause_to_indexkey(RelOptInfo *rel, IndexOptInfo *index, - int indexkey, Oid opclass, - Expr *clause, bool join); + int indexkey, Oid opclass, + Expr *clause, bool join); static bool pred_test(List *predicate_list, List *restrictinfo_list, - List *joininfo_list); + List *joininfo_list); static bool one_pred_test(Expr *predicate, List *restrictinfo_list); static bool one_pred_clause_expr_test(Expr *predicate, Node *clause); static bool one_pred_clause_test(Expr *predicate, Node *clause); static bool clause_pred_clause_test(Expr *predicate, Node *clause); static void indexable_joinclauses(RelOptInfo *rel, IndexOptInfo *index, - List *joininfo_list, List *restrictinfo_list, - List **clausegroups, List **outerrelids); + List *joininfo_list, List *restrictinfo_list, + List **clausegroups, List **outerrelids); static List *index_innerjoin(Query *root, RelOptInfo *rel, IndexOptInfo *index, - List *clausegroup_list, List *outerrelids_list); + List *clausegroup_list, List *outerrelids_list); static bool useful_for_mergejoin(RelOptInfo *rel, IndexOptInfo *index, - List *joininfo_list); + List *joininfo_list); static bool useful_for_ordering(Query *root, RelOptInfo *rel, - IndexOptInfo *index, - ScanDirection scandir); + IndexOptInfo *index, + ScanDirection scandir); static bool match_index_to_operand(int indexkey, Var *operand, - RelOptInfo *rel, IndexOptInfo *index); + RelOptInfo *rel, IndexOptInfo *index); static bool function_index_operand(Expr *funcOpnd, RelOptInfo *rel, - IndexOptInfo *index); + IndexOptInfo *index); static bool match_special_index_operator(Expr *clause, Oid opclass, Oid relam, - bool indexkey_on_left); + bool indexkey_on_left); static Prefix_Status like_fixed_prefix(char *patt, char **prefix); static Prefix_Status regex_fixed_prefix(char *patt, bool case_insensitive, - char **prefix); + char **prefix); static List *prefix_quals(Var *leftop, Oid expr_op, - char *prefix, Prefix_Status pstatus); -static char *make_greater_string(const char * str, Oid datatype); -static Oid find_operator(const char * opname, Oid datatype); -static Datum string_to_datum(const char * str, Oid datatype); -static Const *string_to_const(const char * str, Oid datatype); -static bool string_lessthan(const char * str1, const char * str2, - Oid datatype); + char *prefix, Prefix_Status pstatus); +static char *make_greater_string(const char *str, Oid datatype); +static Oid find_operator(const char *opname, Oid datatype); +static Datum string_to_datum(const char *str, Oid datatype); +static Const *string_to_const(const char *str, Oid datatype); +static bool string_lessthan(const char *str1, const char *str2, + Oid datatype); /* @@ -153,34 +154,34 @@ create_index_paths(Query *root, List *joinouterrelids; /* - * If this is a partial index, we can only use it if it passes - * the predicate test. + * If this is a partial index, we can only use it if it passes the + * predicate test. */ if (index->indpred != NIL) if (!pred_test(index->indpred, restrictinfo_list, joininfo_list)) continue; /* - * 1. Try matching the index against subclauses of restriction 'or' - * clauses (ie, 'or' clauses that reference only this relation). - * The restrictinfo nodes for the 'or' clauses are marked with lists - * of the matching indices. No paths are actually created now; - * that will be done in orindxpath.c after all indexes for the rel - * have been examined. (We need to do it that way because we can - * potentially use a different index for each subclause of an 'or', - * so we can't build a path for an 'or' clause until all indexes have - * been matched against it.) + * 1. Try matching the index against subclauses of restriction + * 'or' clauses (ie, 'or' clauses that reference only this + * relation). The restrictinfo nodes for the 'or' clauses are + * marked with lists of the matching indices. No paths are + * actually created now; that will be done in orindxpath.c after + * all indexes for the rel have been examined. (We need to do it + * that way because we can potentially use a different index for + * each subclause of an 'or', so we can't build a path for an 'or' + * clause until all indexes have been matched against it.) * * We don't even think about special handling of 'or' clauses that - * involve more than one relation (ie, are join clauses). - * Can we do anything useful with those? + * involve more than one relation (ie, are join clauses). Can we + * do anything useful with those? */ match_index_orclauses(rel, index, restrictinfo_list); /* - * 2. If the keys of this index match any of the available non-'or' - * restriction clauses, then create a path using those clauses - * as indexquals. + * 2. If the keys of this index match any of the available + * non-'or' restriction clauses, then create a path using those + * clauses as indexquals. */ restrictclauses = group_clauses_by_indexkey(rel, index, @@ -191,7 +192,7 @@ create_index_paths(Query *root, if (restrictclauses != NIL) add_path(rel, (Path *) create_index_path(root, rel, index, restrictclauses, - NoMovementScanDirection)); + NoMovementScanDirection)); /* * 3. If this index can be used for a mergejoin, then create an @@ -205,16 +206,17 @@ create_index_paths(Query *root, if (restrictclauses == NIL) { if (useful_for_mergejoin(rel, index, joininfo_list) || - useful_for_ordering(root, rel, index, ForwardScanDirection)) + useful_for_ordering(root, rel, index, ForwardScanDirection)) add_path(rel, (Path *) create_index_path(root, rel, index, NIL, ForwardScanDirection)); } + /* - * Currently, backwards scan is never considered except for the case - * of matching a query result ordering. Possibly should consider - * it in other places? + * Currently, backwards scan is never considered except for the + * case of matching a query result ordering. Possibly should + * consider it in other places? */ if (useful_for_ordering(root, rel, index, BackwardScanDirection)) add_path(rel, (Path *) @@ -223,11 +225,11 @@ create_index_paths(Query *root, BackwardScanDirection)); /* - * 4. Create an innerjoin index path for each combination of - * other rels used in available join clauses. These paths will - * be considered as the inner side of nestloop joins against - * those sets of other rels. indexable_joinclauses() finds sets - * of clauses that can be used with each combination of outer rels, + * 4. Create an innerjoin index path for each combination of other + * rels used in available join clauses. These paths will be + * considered as the inner side of nestloop joins against those + * sets of other rels. indexable_joinclauses() finds sets of + * clauses that can be used with each combination of outer rels, * and index_innerjoin builds the paths themselves. We add the * paths to the rel's innerjoin list, NOT to the result list. */ @@ -247,7 +249,7 @@ create_index_paths(Query *root, /**************************************************************************** - * ---- ROUTINES TO PROCESS 'OR' CLAUSES ---- + * ---- ROUTINES TO PROCESS 'OR' CLAUSES ---- ****************************************************************************/ @@ -280,6 +282,7 @@ match_index_orclauses(RelOptInfo *rel, if (restriction_is_or_clause(restrictinfo)) { + /* * Add this index to the subclause index list for each * subclause that it matches. @@ -309,7 +312,7 @@ match_index_orclauses(RelOptInfo *rel, * that have already been matched to subclauses within this * particular 'or' clause (i.e., a list previously generated by * this routine), or NIL if this routine has not previously been - * run for this 'or' clause. + * run for this 'or' clause. * * Returns a list of the form ((a b c) (d e f) nil (g h) ...) where * a,b,c are nodes of indices that match the first subclause in @@ -326,7 +329,8 @@ match_index_orclause(RelOptInfo *rel, List *index_list; List *clist; - /* first time through, we create list of same length as OR clause, + /* + * first time through, we create list of same length as OR clause, * containing an empty sublist for each subclause. */ if (!other_matching_indices) @@ -374,8 +378,8 @@ match_or_subclause_to_indexkey(RelOptInfo *rel, IndexOptInfo *index, Expr *clause) { - int indexkey = index->indexkeys[0]; - Oid opclass = index->classlist[0]; + int indexkey = index->indexkeys[0]; + Oid opclass = index->classlist[0]; if (and_clause((Node *) clause)) { @@ -400,10 +404,10 @@ match_or_subclause_to_indexkey(RelOptInfo *rel, * used as indexquals. * * In the simplest case this just means making a one-element list of the - * given opclause. However, if the OR subclause is an AND, we have to + * given opclause. However, if the OR subclause is an AND, we have to * scan it to find the opclause(s) that match the index. (There should * be at least one, if match_or_subclause_to_indexkey succeeded, but there - * could be more.) Also, we apply expand_indexqual_conditions() to convert + * could be more.) Also, we apply expand_indexqual_conditions() to convert * any special matching opclauses to indexable operators. * * The passed-in clause is not changed. @@ -413,9 +417,9 @@ extract_or_indexqual_conditions(RelOptInfo *rel, IndexOptInfo *index, Expr *orsubclause) { - List *quals = NIL; - int indexkey = index->indexkeys[0]; - Oid opclass = index->classlist[0]; + List *quals = NIL; + int indexkey = index->indexkeys[0]; + Oid opclass = index->classlist[0]; if (and_clause((Node *) orsubclause)) { @@ -514,8 +518,9 @@ group_clauses_by_indexkey(RelOptInfo *rel, clausegroup = lappend(clausegroup, rinfo); } - /* If no clauses match this key, we're done; we don't want to - * look at keys to its right. + /* + * If no clauses match this key, we're done; we don't want to look + * at keys to its right. */ if (clausegroup == NIL) break; @@ -533,7 +538,7 @@ group_clauses_by_indexkey(RelOptInfo *rel, /* * group_clauses_by_ikey_for_joins - * Generates a list of join clauses that can be used with an index + * Generates a list of join clauses that can be used with an index * to scan the inner side of a nestloop join. * * This is much like group_clauses_by_indexkey(), but we consider both @@ -593,8 +598,9 @@ group_clauses_by_ikey_for_joins(RelOptInfo *rel, clausegroup = lappend(clausegroup, rinfo); } - /* If no clauses match this key, we're done; we don't want to - * look at keys to its right. + /* + * If no clauses match this key, we're done; we don't want to look + * at keys to its right. */ if (clausegroup == NIL) break; @@ -607,8 +613,8 @@ group_clauses_by_ikey_for_joins(RelOptInfo *rel, } while (!DoneMatchingIndexKeys(indexkeys, index)); /* - * if no join clause was matched then there ain't clauses for - * joins at all. + * if no join clause was matched then there ain't clauses for joins at + * all. */ if (!jfound) { @@ -623,8 +629,8 @@ group_clauses_by_ikey_for_joins(RelOptInfo *rel, /* * match_clause_to_indexkey() - * Determines whether a restriction or join clause matches - * a key of an index. + * Determines whether a restriction or join clause matches + * a key of an index. * * To match, the clause: @@ -673,43 +679,46 @@ match_clause_to_indexkey(RelOptInfo *rel, *rightop; /* Clause must be a binary opclause. */ - if (! is_opclause((Node *) clause)) + if (!is_opclause((Node *) clause)) return false; leftop = get_leftop(clause); rightop = get_rightop(clause); - if (! leftop || ! rightop) + if (!leftop || !rightop) return false; if (!join) { + /* * Not considering joins, so check for clauses of the form: * (indexkey operator constant) or (constant operator indexkey). * We will accept a Param as being constant. */ - if ((IsA(rightop, Const) || IsA(rightop, Param)) && + if ((IsA(rightop, Const) ||IsA(rightop, Param)) && match_index_to_operand(indexkey, leftop, rel, index)) { if (is_indexable_operator(clause, opclass, index->relam, true)) return true; + /* - * If we didn't find a member of the index's opclass, - * see whether it is a "special" indexable operator. + * If we didn't find a member of the index's opclass, see + * whether it is a "special" indexable operator. */ if (match_special_index_operator(clause, opclass, index->relam, true)) return true; return false; } - if ((IsA(leftop, Const) || IsA(leftop, Param)) && + if ((IsA(leftop, Const) ||IsA(leftop, Param)) && match_index_to_operand(indexkey, rightop, rel, index)) { if (is_indexable_operator(clause, opclass, index->relam, false)) return true; + /* - * If we didn't find a member of the index's opclass, - * see whether it is a "special" indexable operator. + * If we didn't find a member of the index's opclass, see + * whether it is a "special" indexable operator. */ if (match_special_index_operator(clause, opclass, index->relam, false)) @@ -719,20 +728,21 @@ match_clause_to_indexkey(RelOptInfo *rel, } else { + /* - * Check for an indexqual that could be handled by a nestloop join. - * We need the index key to be compared against an expression - * that uses none of the indexed relation's vars. + * Check for an indexqual that could be handled by a nestloop + * join. We need the index key to be compared against an + * expression that uses none of the indexed relation's vars. */ if (match_index_to_operand(indexkey, leftop, rel, index)) { List *othervarnos = pull_varnos((Node *) rightop); bool isIndexable; - isIndexable = ! intMember(lfirsti(rel->relids), othervarnos); + isIndexable = !intMember(lfirsti(rel->relids), othervarnos); freeList(othervarnos); if (isIndexable && - is_indexable_operator(clause, opclass, index->relam, true)) + is_indexable_operator(clause, opclass, index->relam, true)) return true; } else if (match_index_to_operand(indexkey, rightop, rel, index)) @@ -740,10 +750,10 @@ match_clause_to_indexkey(RelOptInfo *rel, List *othervarnos = pull_varnos((Node *) leftop); bool isIndexable; - isIndexable = ! intMember(lfirsti(rel->relids), othervarnos); + isIndexable = !intMember(lfirsti(rel->relids), othervarnos); freeList(othervarnos); if (isIndexable && - is_indexable_operator(clause, opclass, index->relam, false)) + is_indexable_operator(clause, opclass, index->relam, false)) return true; } } @@ -768,7 +778,7 @@ match_clause_to_indexkey(RelOptInfo *rel, * * Returns the OID of the matching operator, or InvalidOid if no match. * Note that the returned OID will be different from the one in the given - * expression if we used a binary-compatible substitution. Also note that + * expression if we used a binary-compatible substitution. Also note that * if indexkey_on_left is FALSE (meaning we need to commute), the returned * OID is *not* commuted; it can be plugged directly into the given clause. */ @@ -818,13 +828,14 @@ indexable_operator(Expr *clause, Oid opclass, Oid relam, if (HeapTupleIsValid(newop)) { - Oid new_expr_op = oprid(newop); + Oid new_expr_op = oprid(newop); if (new_expr_op != expr_op) { + /* - * OK, we found a binary-compatible operator of the same name; - * now does it match the index? + * OK, we found a binary-compatible operator of the same + * name; now does it match the index? */ if (indexkey_on_left) commuted_op = new_expr_op; @@ -883,12 +894,12 @@ useful_for_mergejoin(RelOptInfo *rel, { if (restrictinfo->left_sortop == ordering[0] && match_index_to_operand(indexkeys[0], - get_leftop(restrictinfo->clause), + get_leftop(restrictinfo->clause), rel, index)) return true; if (restrictinfo->right_sortop == ordering[0] && match_index_to_operand(indexkeys[0], - get_rightop(restrictinfo->clause), + get_rightop(restrictinfo->clause), rel, index)) return true; } @@ -1127,7 +1138,7 @@ one_pred_clause_test(Expr *predicate, Node *clause) */ static StrategyNumber -BT_implic_table[BTMaxStrategyNumber][BTMaxStrategyNumber] = { + BT_implic_table[BTMaxStrategyNumber][BTMaxStrategyNumber] = { {2, 2, 0, 0, 0}, {1, 2, 0, 0, 0}, {1, 2, 3, 4, 5}, @@ -1346,13 +1357,13 @@ clause_pred_clause_test(Expr *predicate, Node *clause) * rel's restrictinfo list. Therefore, every clause in the group references * the current rel plus the same set of other rels (except for the restrict * clauses, which only reference the current rel). Therefore, this set - * of clauses could be used as an indexqual if the relation is scanned + * of clauses could be used as an indexqual if the relation is scanned * as the inner side of a nestloop join when the outer side contains * (at least) all those "other rels". * * XXX Actually, given that we are considering a join that requires an * outer rel set (A,B,C), we should use all qual clauses that reference - * any subset of these rels, not just the full set or none. This is + * any subset of these rels, not just the full set or none. This is * doable with a doubly nested loop over joininfo_list; is it worth it? * * Returns two parallel lists of the same length: the clause groups, @@ -1430,10 +1441,11 @@ index_innerjoin(Query *root, RelOptInfo *rel, IndexOptInfo *index, pathnode->path.pathtype = T_IndexScan; pathnode->path.parent = rel; + /* * There's no point in marking the path with any pathkeys, since - * it will only ever be used as the inner path of a nestloop, - * and so its ordering does not matter. + * it will only ever be used as the inner path of a nestloop, and + * so its ordering does not matter. */ pathnode->path.pathkeys = NIL; @@ -1441,7 +1453,8 @@ index_innerjoin(Query *root, RelOptInfo *rel, IndexOptInfo *index, /* expand special operators to indexquals the executor can handle */ indexquals = expand_indexqual_conditions(indexquals); - /* Note that we are making a pathnode for a single-scan indexscan; + /* + * Note that we are making a pathnode for a single-scan indexscan; * therefore, both indexid and indexqual should be single-element * lists. */ @@ -1456,14 +1469,15 @@ index_innerjoin(Query *root, RelOptInfo *rel, IndexOptInfo *index, /* * We must compute the estimated number of output rows for the - * indexscan. This is less than rel->rows because of the additional - * selectivity of the join clauses. Since clausegroup may contain - * both restriction and join clauses, we have to do a set union to - * get the full set of clauses that must be considered to compute - * the correct selectivity. (We can't just nconc the two lists; - * then we might have some restriction clauses appearing twice, - * which'd mislead restrictlist_selectivity into double-counting - * their selectivity.) + * indexscan. This is less than rel->rows because of the + * additional selectivity of the join clauses. Since clausegroup + * may contain both restriction and join clauses, we have to do a + * set union to get the full set of clauses that must be + * considered to compute the correct selectivity. (We can't just + * nconc the two lists; then we might have some restriction + * clauses appearing twice, which'd mislead + * restrictlist_selectivity into double-counting their + * selectivity.) */ pathnode->rows = rel->tuples * restrictlist_selectivity(root, @@ -1490,7 +1504,7 @@ index_innerjoin(Query *root, RelOptInfo *rel, IndexOptInfo *index, * match_index_to_operand() * Generalized test for a match between an index's key * and the operand on one side of a restriction or join clause. - * Now check for functional indices as well. + * Now check for functional indices as well. */ static bool match_index_to_operand(int indexkey, @@ -1500,6 +1514,7 @@ match_index_to_operand(int indexkey, { if (index->indproc == InvalidOid) { + /* * Normal index. */ @@ -1530,7 +1545,7 @@ function_index_operand(Expr *funcOpnd, RelOptInfo *rel, IndexOptInfo *index) /* * sanity check, make sure we know what we're dealing with here. */ - if (funcOpnd == NULL || ! IsA(funcOpnd, Expr) || + if (funcOpnd == NULL || !IsA(funcOpnd, Expr) || funcOpnd->opType != FUNC_EXPR || funcOpnd->oper == NULL || indexKeys == NULL) return false; @@ -1550,9 +1565,9 @@ function_index_operand(Expr *funcOpnd, RelOptInfo *rel, IndexOptInfo *index) i = 0; foreach(arg, funcargs) { - Var *var = (Var *) lfirst(arg); + Var *var = (Var *) lfirst(arg); - if (! IsA(var, Var)) + if (!IsA(var, Var)) return false; if (indexKeys[i] == 0) return false; @@ -1578,10 +1593,10 @@ function_index_operand(Expr *funcOpnd, RelOptInfo *rel, IndexOptInfo *index) * indexscan machinery. The key idea is that these operators allow us * to derive approximate indexscan qual clauses, such that any tuples * that pass the operator clause itself must also satisfy the simpler - * indexscan condition(s). Then we can use the indexscan machinery + * indexscan condition(s). Then we can use the indexscan machinery * to avoid scanning as much of the table as we'd otherwise have to, * while applying the original operator as a qpqual condition to ensure - * we deliver only the tuples we want. (In essence, we're using a regular + * we deliver only the tuples we want. (In essence, we're using a regular * index as if it were a lossy index.) * * An example of what we're doing is @@ -1630,11 +1645,12 @@ match_special_index_operator(Expr *clause, Oid opclass, Oid relam, char *patt; char *prefix; - /* Currently, all known special operators require the indexkey - * on the left, but this test could be pushed into the switch statement - * if some are added that do not... + /* + * Currently, all known special operators require the indexkey on the + * left, but this test could be pushed into the switch statement if + * some are added that do not... */ - if (! indexkey_on_left) + if (!indexkey_on_left) return false; /* we know these will succeed */ @@ -1643,7 +1659,7 @@ match_special_index_operator(Expr *clause, Oid opclass, Oid relam, expr_op = ((Oper *) clause->oper)->opno; /* again, required for all current special ops: */ - if (! IsA(rightop, Const) || + if (!IsA(rightop, Const) || ((Const *) rightop)->constisnull) return false; constvalue = ((Const *) rightop)->constvalue; @@ -1657,7 +1673,8 @@ match_special_index_operator(Expr *clause, Oid opclass, Oid relam, /* the right-hand const is type text for all of these */ patt = textout((text *) DatumGetPointer(constvalue)); isIndexable = like_fixed_prefix(patt, &prefix) != Prefix_None; - if (prefix) pfree(prefix); + if (prefix) + pfree(prefix); pfree(patt); break; @@ -1668,7 +1685,8 @@ match_special_index_operator(Expr *clause, Oid opclass, Oid relam, /* the right-hand const is type text for all of these */ patt = textout((text *) DatumGetPointer(constvalue)); isIndexable = regex_fixed_prefix(patt, false, &prefix) != Prefix_None; - if (prefix) pfree(prefix); + if (prefix) + pfree(prefix); pfree(patt); break; @@ -1679,13 +1697,14 @@ match_special_index_operator(Expr *clause, Oid opclass, Oid relam, /* the right-hand const is type text for all of these */ patt = textout((text *) DatumGetPointer(constvalue)); isIndexable = regex_fixed_prefix(patt, true, &prefix) != Prefix_None; - if (prefix) pfree(prefix); + if (prefix) + pfree(prefix); pfree(patt); break; } /* done if the expression doesn't look indexable */ - if (! isIndexable) + if (!isIndexable) return false; /* @@ -1699,32 +1718,32 @@ match_special_index_operator(Expr *clause, Oid opclass, Oid relam, case OID_TEXT_LIKE_OP: case OID_TEXT_REGEXEQ_OP: case OID_TEXT_ICREGEXEQ_OP: - if (! op_class(find_operator(">=", TEXTOID), opclass, relam) || - ! op_class(find_operator("<", TEXTOID), opclass, relam)) + if (!op_class(find_operator(">=", TEXTOID), opclass, relam) || + !op_class(find_operator("<", TEXTOID), opclass, relam)) isIndexable = false; break; case OID_BPCHAR_LIKE_OP: case OID_BPCHAR_REGEXEQ_OP: case OID_BPCHAR_ICREGEXEQ_OP: - if (! op_class(find_operator(">=", BPCHAROID), opclass, relam) || - ! op_class(find_operator("<", BPCHAROID), opclass, relam)) + if (!op_class(find_operator(">=", BPCHAROID), opclass, relam) || + !op_class(find_operator("<", BPCHAROID), opclass, relam)) isIndexable = false; break; case OID_VARCHAR_LIKE_OP: case OID_VARCHAR_REGEXEQ_OP: case OID_VARCHAR_ICREGEXEQ_OP: - if (! op_class(find_operator(">=", VARCHAROID), opclass, relam) || - ! op_class(find_operator("<", VARCHAROID), opclass, relam)) + if (!op_class(find_operator(">=", VARCHAROID), opclass, relam) || + !op_class(find_operator("<", VARCHAROID), opclass, relam)) isIndexable = false; break; case OID_NAME_LIKE_OP: case OID_NAME_REGEXEQ_OP: case OID_NAME_ICREGEXEQ_OP: - if (! op_class(find_operator(">=", NAMEOID), opclass, relam) || - ! op_class(find_operator("<", NAMEOID), opclass, relam)) + if (!op_class(find_operator(">=", NAMEOID), opclass, relam) || + !op_class(find_operator("<", NAMEOID), opclass, relam)) isIndexable = false; break; } @@ -1736,7 +1755,7 @@ match_special_index_operator(Expr *clause, Oid opclass, Oid relam, * expand_indexqual_conditions * Given a list of (implicitly ANDed) indexqual clauses, * expand any "special" index operators into clauses that the indexscan - * machinery will know what to do with. Clauses that were not + * machinery will know what to do with. Clauses that were not * recognized by match_special_index_operator() must be passed through * unchanged. */ @@ -1749,6 +1768,7 @@ expand_indexqual_conditions(List *indexquals) foreach(q, indexquals) { Expr *clause = (Expr *) lfirst(q); + /* we know these will succeed */ Var *leftop = get_leftop(clause); Var *rightop = get_rightop(clause); @@ -1760,11 +1780,13 @@ expand_indexqual_conditions(List *indexquals) switch (expr_op) { - /* - * LIKE and regex operators are not members of any index opclass, - * so if we find one in an indexqual list we can assume that - * it was accepted by match_special_index_operator(). - */ + + /* + * LIKE and regex operators are not members of any index + * opclass, so if we find one in an indexqual list we can + * assume that it was accepted by + * match_special_index_operator(). + */ case OID_TEXT_LIKE_OP: case OID_BPCHAR_LIKE_OP: case OID_VARCHAR_LIKE_OP: @@ -1776,7 +1798,8 @@ expand_indexqual_conditions(List *indexquals) resultquals = nconc(resultquals, prefix_quals(leftop, expr_op, prefix, pstatus)); - if (prefix) pfree(prefix); + if (prefix) + pfree(prefix); pfree(patt); break; @@ -1791,7 +1814,8 @@ expand_indexqual_conditions(List *indexquals) resultquals = nconc(resultquals, prefix_quals(leftop, expr_op, prefix, pstatus)); - if (prefix) pfree(prefix); + if (prefix) + pfree(prefix); pfree(patt); break; @@ -1806,7 +1830,8 @@ expand_indexqual_conditions(List *indexquals) resultquals = nconc(resultquals, prefix_quals(leftop, expr_op, prefix, pstatus)); - if (prefix) pfree(prefix); + if (prefix) + pfree(prefix); pfree(patt); break; @@ -1833,7 +1858,7 @@ like_fixed_prefix(char *patt, char **prefix) int pos, match_pos; - *prefix = match = palloc(strlen(patt)+1); + *prefix = match = palloc(strlen(patt) + 1); match_pos = 0; for (pos = 0; patt[pos]; pos++) @@ -1849,14 +1874,15 @@ like_fixed_prefix(char *patt, char **prefix) if (patt[pos] == '\0') break; } + /* - * NOTE: this code used to think that %% meant a literal %, - * but textlike() itself does not think that, and the SQL92 - * spec doesn't say any such thing either. + * NOTE: this code used to think that %% meant a literal %, but + * textlike() itself does not think that, and the SQL92 spec + * doesn't say any such thing either. */ match[match_pos++] = patt[pos]; } - + match[match_pos] = '\0'; /* in LIKE, an empty pattern is an exact match! */ @@ -1905,7 +1931,7 @@ regex_fixed_prefix(char *patt, bool case_insensitive, } /* OK, allocate space for pattern */ - *prefix = match = palloc(strlen(patt)+1); + *prefix = match = palloc(strlen(patt) + 1); match_pos = 0; /* note start at pos 1 to skip leading ^ */ @@ -1916,9 +1942,11 @@ regex_fixed_prefix(char *patt, bool case_insensitive, patt[pos] == '*' || patt[pos] == '[' || patt[pos] == '$' || - /* XXX I suspect isalpha() is not an adequately locale-sensitive - * test for characters that can vary under case folding? - */ + + /* + * XXX I suspect isalpha() is not an adequately locale-sensitive + * test for characters that can vary under case folding? + */ (case_insensitive && isalpha(patt[pos]))) break; if (patt[pos] == '\\') @@ -1932,9 +1960,9 @@ regex_fixed_prefix(char *patt, bool case_insensitive, match[match_pos] = '\0'; - if (patt[pos] == '$' && patt[pos+1] == '\0') + if (patt[pos] == '$' && patt[pos + 1] == '\0') return Prefix_Exact; /* pattern specifies exact match */ - + if (match_pos > 0) return Prefix_Partial; return Prefix_None; @@ -2020,7 +2048,8 @@ prefix_quals(Var *leftop, Oid expr_op, result = lcons(expr, NIL); /* - * If we can create a string larger than the prefix, say "x < greaterstr". + * If we can create a string larger than the prefix, say "x < + * greaterstr". */ greaterstr = make_greater_string(prefix, datatype); if (greaterstr) @@ -2058,17 +2087,20 @@ prefix_quals(Var *leftop, Oid expr_op, * given "foos" and return "foot", will this actually be greater than "fooss"? */ static char * -make_greater_string(const char * str, Oid datatype) +make_greater_string(const char *str, Oid datatype) { char *workstr; int len; - /* Make a modifiable copy, which will be our return value if successful */ + /* + * Make a modifiable copy, which will be our return value if + * successful + */ workstr = pstrdup((char *) str); while ((len = strlen(workstr)) > 0) { - unsigned char *lastchar = (unsigned char *) (workstr + len - 1); + unsigned char *lastchar = (unsigned char *) (workstr + len - 1); /* * Try to generate a larger string by incrementing the last byte. @@ -2077,14 +2109,15 @@ make_greater_string(const char * str, Oid datatype) { (*lastchar)++; if (string_lessthan(str, workstr, datatype)) - return workstr; /* Success! */ + return workstr; /* Success! */ } + /* - * Truncate off the last character, which might be more than 1 byte - * in MULTIBYTE case. + * Truncate off the last character, which might be more than 1 + * byte in MULTIBYTE case. */ #ifdef MULTIBYTE - len = pg_mbcliplen((const unsigned char *) workstr, len, len-1); + len = pg_mbcliplen((const unsigned char *) workstr, len, len - 1); workstr[len] = '\0'; #else *lastchar = '\0'; @@ -2102,7 +2135,7 @@ make_greater_string(const char * str, Oid datatype) /* See if there is a binary op of the given name for the given datatype */ static Oid -find_operator(const char * opname, Oid datatype) +find_operator(const char *opname, Oid datatype) { HeapTuple optup; @@ -2122,10 +2155,12 @@ find_operator(const char * opname, Oid datatype) * returned value should be pfree'd if no longer needed. */ static Datum -string_to_datum(const char * str, Oid datatype) +string_to_datum(const char *str, Oid datatype) { - /* We cheat a little by assuming that textin() will do for - * bpchar and varchar constants too... + + /* + * We cheat a little by assuming that textin() will do for bpchar and + * varchar constants too... */ if (datatype == NAMEOID) return PointerGetDatum(namein((char *) str)); @@ -2137,7 +2172,7 @@ string_to_datum(const char * str, Oid datatype) * Generate a Const node of the appropriate type from a C string. */ static Const * -string_to_const(const char * str, Oid datatype) +string_to_const(const char *str, Oid datatype) { Datum conval = string_to_datum(str, datatype); @@ -2151,7 +2186,7 @@ string_to_const(const char * str, Oid datatype) * "<" operator function, to ensure we get the right result... */ static bool -string_lessthan(const char * str1, const char * str2, Oid datatype) +string_lessthan(const char *str1, const char *str2, Oid datatype) { Datum datum1 = string_to_datum(str1, datatype); Datum datum2 = string_to_datum(str2, datatype); diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c index 9261437496..64e9443ab1 100644 --- a/src/backend/optimizer/path/joinpath.c +++ b/src/backend/optimizer/path/joinpath.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v 1.53 2000/02/18 23:47:19 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinpath.c,v 1.54 2000/04/12 17:15:19 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -28,25 +28,27 @@ #include "utils/lsyscache.h" static void sort_inner_and_outer(Query *root, RelOptInfo *joinrel, - RelOptInfo *outerrel, RelOptInfo *innerrel, - List *restrictlist, List *mergeclause_list); + RelOptInfo *outerrel, RelOptInfo *innerrel, + List *restrictlist, List *mergeclause_list); static void match_unsorted_outer(Query *root, RelOptInfo *joinrel, - RelOptInfo *outerrel, RelOptInfo *innerrel, - List *restrictlist, List *mergeclause_list); + RelOptInfo *outerrel, RelOptInfo *innerrel, + List *restrictlist, List *mergeclause_list); + #ifdef NOT_USED static void match_unsorted_inner(Query *root, RelOptInfo *joinrel, - RelOptInfo *outerrel, RelOptInfo *innerrel, - List *restrictlist, List *mergeclause_list); + RelOptInfo *outerrel, RelOptInfo *innerrel, + List *restrictlist, List *mergeclause_list); + #endif static void hash_inner_and_outer(Query *root, RelOptInfo *joinrel, - RelOptInfo *outerrel, RelOptInfo *innerrel, - List *restrictlist); + RelOptInfo *outerrel, RelOptInfo *innerrel, + List *restrictlist); static Path *best_innerjoin(List *join_paths, List *outer_relid); static Selectivity estimate_disbursion(Query *root, Var *var); static List *select_mergejoin_clauses(RelOptInfo *joinrel, - RelOptInfo *outerrel, - RelOptInfo *innerrel, - List *restrictlist); + RelOptInfo *outerrel, + RelOptInfo *innerrel, + List *restrictlist); /* @@ -79,32 +81,33 @@ add_paths_to_joinrel(Query *root, restrictlist); /* - * 1. Consider mergejoin paths where both relations must be - * explicitly sorted. + * 1. Consider mergejoin paths where both relations must be explicitly + * sorted. */ sort_inner_and_outer(root, joinrel, outerrel, innerrel, restrictlist, mergeclause_list); /* - * 2. Consider paths where the outer relation need not be - * explicitly sorted. This includes both nestloops and - * mergejoins where the outer path is already ordered. + * 2. Consider paths where the outer relation need not be explicitly + * sorted. This includes both nestloops and mergejoins where the outer + * path is already ordered. */ match_unsorted_outer(root, joinrel, outerrel, innerrel, restrictlist, mergeclause_list); #ifdef NOT_USED + /* - * 3. Consider paths where the inner relation need not be - * explicitly sorted. This includes mergejoins only - * (nestloops were already built in match_unsorted_outer). + * 3. Consider paths where the inner relation need not be explicitly + * sorted. This includes mergejoins only (nestloops were already + * built in match_unsorted_outer). * - * Diked out as redundant 2/13/2000 -- tgl. There isn't any - * really significant difference between the inner and outer - * side of a mergejoin, so match_unsorted_inner creates no paths - * that aren't equivalent to those made by match_unsorted_outer - * when add_paths_to_joinrel() is invoked with the two rels given - * in the other order. + * Diked out as redundant 2/13/2000 -- tgl. There isn't any really + * significant difference between the inner and outer side of a + * mergejoin, so match_unsorted_inner creates no paths that aren't + * equivalent to those made by match_unsorted_outer when + * add_paths_to_joinrel() is invoked with the two rels given in the + * other order. */ match_unsorted_inner(root, joinrel, outerrel, innerrel, restrictlist, mergeclause_list); @@ -144,31 +147,31 @@ sort_inner_and_outer(Query *root, /* * Each possible ordering of the available mergejoin clauses will - * generate a differently-sorted result path at essentially the - * same cost. We have no basis for choosing one over another at - * this level of joining, but some sort orders may be more useful - * than others for higher-level mergejoins. Generating a path here - * for *every* permutation of mergejoin clauses doesn't seem like - * a winning strategy, however; the cost in planning time is too high. + * generate a differently-sorted result path at essentially the same + * cost. We have no basis for choosing one over another at this level + * of joining, but some sort orders may be more useful than others for + * higher-level mergejoins. Generating a path here for *every* + * permutation of mergejoin clauses doesn't seem like a winning + * strategy, however; the cost in planning time is too high. * * For now, we generate one path for each mergejoin clause, listing that - * clause first and the rest in random order. This should allow at least - * a one-clause mergejoin without re-sorting against any other possible - * mergejoin partner path. But if we've not guessed the right ordering - * of secondary clauses, we may end up evaluating clauses as qpquals when - * they could have been done as mergeclauses. We need to figure out a - * better way. (Two possible approaches: look at all the relevant index - * relations to suggest plausible sort orders, or make just one output - * path and somehow mark it as having a sort-order that can be rearranged - * freely.) + * clause first and the rest in random order. This should allow at + * least a one-clause mergejoin without re-sorting against any other + * possible mergejoin partner path. But if we've not guessed the + * right ordering of secondary clauses, we may end up evaluating + * clauses as qpquals when they could have been done as mergeclauses. + * We need to figure out a better way. (Two possible approaches: look + * at all the relevant index relations to suggest plausible sort + * orders, or make just one output path and somehow mark it as having + * a sort-order that can be rearranged freely.) */ foreach(i, mergeclause_list) { - RestrictInfo *restrictinfo = lfirst(i); - List *curclause_list; - List *outerkeys; - List *innerkeys; - List *merge_pathkeys; + RestrictInfo *restrictinfo = lfirst(i); + List *curclause_list; + List *outerkeys; + List *innerkeys; + List *merge_pathkeys; /* Make a mergeclause list with this guy first. */ if (i != mergeclause_list) @@ -176,13 +179,14 @@ sort_inner_and_outer(Query *root, lremove(restrictinfo, listCopy(mergeclause_list))); else - curclause_list = mergeclause_list; /* no work at first one... */ + curclause_list = mergeclause_list; /* no work at first one... */ - /* Build sort pathkeys for both sides. + /* + * Build sort pathkeys for both sides. * - * Note: it's possible that the cheapest paths will already be - * sorted properly. create_mergejoin_path will detect that case - * and suppress an explicit sort step, so we needn't do so here. + * Note: it's possible that the cheapest paths will already be sorted + * properly. create_mergejoin_path will detect that case and + * suppress an explicit sort step, so we needn't do so here. */ outerkeys = make_pathkeys_for_mergeclauses(root, curclause_list, @@ -198,8 +202,8 @@ sort_inner_and_outer(Query *root, /* * And now we can make the path. We only consider the cheapest- * total-cost input paths, since we are assuming here that a sort - * is required. We will consider cheapest-startup-cost input paths - * later, and only if they don't need a sort. + * is required. We will consider cheapest-startup-cost input + * paths later, and only if they don't need a sort. */ add_path(joinrel, (Path *) create_mergejoin_path(joinrel, @@ -225,7 +229,7 @@ sort_inner_and_outer(Query *root, * inner path, one on the cheapest-startup-cost inner path (if different), * and one on the best inner-indexscan path (if any). * - * We also consider mergejoins if mergejoin clauses are available. We have + * We also consider mergejoins if mergejoin clauses are available. We have * two ways to generate the inner path for a mergejoin: sort the cheapest * inner path, or use an inner path that is already suitably ordered for the * merge. If we have several mergeclauses, it could be that there is no inner @@ -255,8 +259,8 @@ match_unsorted_outer(Query *root, List *i; /* - * Get the best innerjoin indexpath (if any) for this outer rel. - * It's the same for all outer paths. + * Get the best innerjoin indexpath (if any) for this outer rel. It's + * the same for all outer paths. */ bestinnerjoin = best_innerjoin(innerrel->innerjoin, outerrel->relids); @@ -274,8 +278,8 @@ match_unsorted_outer(Query *root, /* * The result will have this sort order (even if it is implemented - * as a nestloop, and even if some of the mergeclauses are implemented - * by qpquals rather than as true mergeclauses): + * as a nestloop, and even if some of the mergeclauses are + * implemented by qpquals rather than as true mergeclauses): */ merge_pathkeys = build_join_pathkeys(outerpath->pathkeys, joinrel->targetlist, @@ -318,11 +322,12 @@ match_unsorted_outer(Query *root, /* Compute the required ordering of the inner path */ innersortkeys = make_pathkeys_for_mergeclauses(root, mergeclauses, - innerrel->targetlist); + innerrel->targetlist); /* - * Generate a mergejoin on the basis of sorting the cheapest inner. - * Since a sort will be needed, only cheapest total cost matters. + * Generate a mergejoin on the basis of sorting the cheapest + * inner. Since a sort will be needed, only cheapest total cost + * matters. */ add_path(joinrel, (Path *) create_mergejoin_path(joinrel, @@ -335,11 +340,11 @@ match_unsorted_outer(Query *root, innersortkeys)); /* - * Look for presorted inner paths that satisfy the mergeclause list - * or any truncation thereof. Here, we consider both cheap startup - * cost and cheap total cost. + * Look for presorted inner paths that satisfy the mergeclause + * list or any truncation thereof. Here, we consider both cheap + * startup cost and cheap total cost. */ - trialsortkeys = listCopy(innersortkeys); /* modifiable copy */ + trialsortkeys = listCopy(innersortkeys); /* modifiable copy */ cheapest_startup_inner = NULL; cheapest_total_inner = NULL; num_mergeclauses = length(mergeclauses); @@ -349,8 +354,9 @@ match_unsorted_outer(Query *root, Path *innerpath; List *newclauses = NIL; - /* Look for an inner path ordered well enough to merge with - * the first 'clausecnt' mergeclauses. NB: trialsortkeys list + /* + * Look for an inner path ordered well enough to merge with + * the first 'clausecnt' mergeclauses. NB: trialsortkeys list * is modified destructively, which is why we made a copy... */ trialsortkeys = ltruncate(clausecnt, trialsortkeys); @@ -391,14 +397,16 @@ match_unsorted_outer(Query *root, /* Found a cheap (or even-cheaper) sorted path */ if (innerpath != cheapest_total_inner) { - /* Avoid rebuilding clause list if we already made one; - * saves memory in big join trees... + + /* + * Avoid rebuilding clause list if we already made + * one; saves memory in big join trees... */ if (newclauses == NIL) { if (clausecnt < num_mergeclauses) newclauses = ltruncate(clausecnt, - listCopy(mergeclauses)); + listCopy(mergeclauses)); else newclauses = mergeclauses; } @@ -461,11 +469,12 @@ match_unsorted_inner(Query *root, /* Compute the required ordering of the outer path */ outersortkeys = make_pathkeys_for_mergeclauses(root, mergeclauses, - outerrel->targetlist); + outerrel->targetlist); /* - * Generate a mergejoin on the basis of sorting the cheapest outer. - * Since a sort will be needed, only cheapest total cost matters. + * Generate a mergejoin on the basis of sorting the cheapest + * outer. Since a sort will be needed, only cheapest total cost + * matters. */ merge_pathkeys = build_join_pathkeys(outersortkeys, joinrel->targetlist, @@ -479,10 +488,11 @@ match_unsorted_inner(Query *root, mergeclauses, outersortkeys, NIL)); + /* * Now generate mergejoins based on already-sufficiently-ordered - * outer paths. There's likely to be some redundancy here with paths - * already generated by merge_unsorted_outer ... but since + * outer paths. There's likely to be some redundancy here with + * paths already generated by merge_unsorted_outer ... but since * merge_unsorted_outer doesn't consider all permutations of the * mergeclause list, it may fail to notice that this particular * innerpath could have been used with this outerpath. @@ -491,7 +501,8 @@ match_unsorted_inner(Query *root, outersortkeys, TOTAL_COST); if (totalouterpath == NULL) - continue; /* there won't be a startup-cost path either */ + continue; /* there won't be a startup-cost path + * either */ merge_pathkeys = build_join_pathkeys(totalouterpath->pathkeys, joinrel->targetlist, @@ -552,8 +563,8 @@ hash_inner_and_outer(Query *root, List *i; /* - * Scan the join's restrictinfo list to find hashjoinable clauses - * that are usable with this pair of sub-relations. Since we currently + * Scan the join's restrictinfo list to find hashjoinable clauses that + * are usable with this pair of sub-relations. Since we currently * accept only var-op-var clauses as hashjoinable, we need only check * the membership of the vars to determine whether a particular clause * can be used with this pair of sub-relations. This code would need @@ -568,7 +579,7 @@ hash_inner_and_outer(Query *root, *right, *inner; List *hashclauses; - Selectivity innerdisbursion; + Selectivity innerdisbursion; if (restrictinfo->hashjoinoperator == InvalidOid) continue; /* not hashjoinable */ @@ -595,9 +606,9 @@ hash_inner_and_outer(Query *root, innerdisbursion = estimate_disbursion(root, inner); /* - * We consider both the cheapest-total-cost and cheapest-startup-cost - * outer paths. There's no need to consider any but the cheapest- - * total-cost inner path, however. + * We consider both the cheapest-total-cost and + * cheapest-startup-cost outer paths. There's no need to consider + * any but the cheapest- total-cost inner path, however. */ add_path(joinrel, (Path *) create_hashjoin_path(joinrel, @@ -644,7 +655,8 @@ best_innerjoin(List *join_paths, Relids outer_relids) Assert(IsA(path, IndexPath)); - /* path->joinrelids is the set of base rels that must be part of + /* + * path->joinrelids is the set of base rels that must be part of * outer_relids in order to use this inner path, because those * rels are used in the index join quals of this inner path. */ @@ -661,7 +673,7 @@ best_innerjoin(List *join_paths, Relids outer_relids) * * We use a default of 0.1 if we can't figure out anything better. * This will typically discourage use of a hash rather strongly, - * if the inner relation is large. We do not want to hash unless + * if the inner relation is large. We do not want to hash unless * we know that the inner rel is well-dispersed (or the alternatives * seem much worse). */ @@ -670,7 +682,7 @@ estimate_disbursion(Query *root, Var *var) { Oid relid; - if (! IsA(var, Var)) + if (!IsA(var, Var)) return 0.1; relid = getrelid(var->varno, root->rtable); @@ -690,7 +702,7 @@ estimate_disbursion(Query *root, Var *var) * Since we currently allow only plain Vars as the left and right sides * of mergejoin clauses, this test is relatively simple. This routine * would need to be upgraded to support more-complex expressions - * as sides of mergejoins. In theory, we could allow arbitrarily complex + * as sides of mergejoins. In theory, we could allow arbitrarily complex * expressions in mergejoins, so long as one side uses only vars from one * sub-relation and the other side uses only vars from the other. */ diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c index e872b67623..09003eb9fa 100644 --- a/src/backend/optimizer/path/joinrels.c +++ b/src/backend/optimizer/path/joinrels.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinrels.c,v 1.43 2000/02/07 04:40:59 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinrels.c,v 1.44 2000/04/12 17:15:20 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -22,7 +22,7 @@ static RelOptInfo *make_join_rel(Query *root, RelOptInfo *rel1, - RelOptInfo *rel2); + RelOptInfo *rel2); /* @@ -44,22 +44,23 @@ make_rels_by_joins(Query *root, int level) /* * First, consider left-sided and right-sided plans, in which rels of * exactly level-1 member relations are joined against base relations. - * We prefer to join using join clauses, but if we find a rel of level-1 - * members that has no join clauses, we will generate Cartesian-product - * joins against all base rels not already contained in it. + * We prefer to join using join clauses, but if we find a rel of + * level-1 members that has no join clauses, we will generate + * Cartesian-product joins against all base rels not already contained + * in it. * * In the first pass (level == 2), we try to join each base rel to each * base rel that appears later in base_rel_list. (The mirror-image - * joins are handled automatically by make_join_rel.) In later passes, - * we try to join rels of size level-1 from join_rel_list to each - * base rel in base_rel_list. + * joins are handled automatically by make_join_rel.) In later + * passes, we try to join rels of size level-1 from join_rel_list to + * each base rel in base_rel_list. * * We assume that the rels already present in join_rel_list appear in * decreasing order of level (number of members). This should be true * since we always add new higher-level rels to the front of the list. */ if (level == 2) - r = root->base_rel_list; /* level-1 is base rels */ + r = root->base_rel_list;/* level-1 is base rels */ else r = root->join_rel_list; for (; r != NIL; r = lnext(r)) @@ -68,21 +69,23 @@ make_rels_by_joins(Query *root, int level) int old_level = length(old_rel->relids); List *other_rels; - if (old_level != level-1) + if (old_level != level - 1) break; if (level == 2) - other_rels = lnext(r); /* only consider remaining base rels */ + other_rels = lnext(r); /* only consider remaining base + * rels */ else - other_rels = root->base_rel_list; /* consider all base rels */ + other_rels = root->base_rel_list; /* consider all base rels */ if (old_rel->joininfo != NIL) { + /* - * Note that if all available join clauses for this rel require - * more than one other rel, we will fail to make any joins against - * it here. That's OK; it'll be considered by "bushy plan" join - * code in a higher-level pass. + * Note that if all available join clauses for this rel + * require more than one other rel, we will fail to make any + * joins against it here. That's OK; it'll be considered by + * "bushy plan" join code in a higher-level pass. */ make_rels_by_clause_joins(root, old_rel, @@ -90,6 +93,7 @@ make_rels_by_joins(Query *root, int level) } else { + /* * Oops, we have a relation that is not joined to any other * relation. Cartesian product time. @@ -103,10 +107,11 @@ make_rels_by_joins(Query *root, int level) /* * Now, consider "bushy plans" in which relations of k base rels are * joined to relations of level-k base rels, for 2 <= k <= level-2. - * The previous loop left r pointing to the first rel of level level-2. + * The previous loop left r pointing to the first rel of level + * level-2. * - * We only consider bushy-plan joins for pairs of rels where there is - * a suitable join clause, in order to avoid unreasonable growth of + * We only consider bushy-plan joins for pairs of rels where there is a + * suitable join clause, in order to avoid unreasonable growth of * planning time. */ for (; r != NIL; r = lnext(r)) @@ -115,8 +120,9 @@ make_rels_by_joins(Query *root, int level) int old_level = length(old_rel->relids); List *r2; - /* We can quit once past the halfway point (make_join_rel took care - * of making the opposite-direction joins) + /* + * We can quit once past the halfway point (make_join_rel took + * care of making the opposite-direction joins) */ if (old_level * 2 < level) break; @@ -137,8 +143,10 @@ make_rels_by_joins(Query *root, int level) { List *i; - /* OK, we can build a rel of the right level from this pair of - * rels. Do so if there is at least one usable join clause. + /* + * OK, we can build a rel of the right level from this + * pair of rels. Do so if there is at least one usable + * join clause. */ foreach(i, old_rel->joininfo) { @@ -192,7 +200,7 @@ make_rels_by_clause_joins(Query *root, foreach(j, other_rels) { - RelOptInfo *other_rel = (RelOptInfo *) lfirst(j); + RelOptInfo *other_rel = (RelOptInfo *) lfirst(j); if (is_subseti(unjoined_relids, other_rel->relids)) result = make_join_rel(root, old_rel, other_rel); @@ -251,8 +259,8 @@ make_rels_by_clauseless_joins(Query *root, static RelOptInfo * make_join_rel(Query *root, RelOptInfo *rel1, RelOptInfo *rel2) { - RelOptInfo *joinrel; - List *restrictlist; + RelOptInfo *joinrel; + List *restrictlist; /* * Find or build the join RelOptInfo, and compute the restrictlist diff --git a/src/backend/optimizer/path/orindxpath.c b/src/backend/optimizer/path/orindxpath.c index e2ae3f0577..85e96d6b86 100644 --- a/src/backend/optimizer/path/orindxpath.c +++ b/src/backend/optimizer/path/orindxpath.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/orindxpath.c,v 1.38 2000/03/22 22:08:33 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/orindxpath.c,v 1.39 2000/04/12 17:15:20 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -27,14 +27,14 @@ static void best_or_subclause_indices(Query *root, RelOptInfo *rel, - List *subclauses, List *indices, - IndexPath *pathnode); + List *subclauses, List *indices, + IndexPath *pathnode); static void best_or_subclause_index(Query *root, RelOptInfo *rel, - Expr *subclause, List *indices, - List **retIndexQual, - Oid *retIndexid, - Cost *retStartupCost, - Cost *retTotalCost); + Expr *subclause, List *indices, + List **retIndexQual, + Oid *retIndexid, + Cost *retStartupCost, + Cost *retTotalCost); /* @@ -61,8 +61,8 @@ create_or_index_paths(Query *root, /* * Check to see if this clause is an 'or' clause, and, if so, * whether or not each of the subclauses within the 'or' clause - * has been matched by an index. The information used was - * saved by create_index_paths(). + * has been matched by an index. The information used was saved + * by create_index_paths(). */ if (restriction_is_or_clause(clausenode) && clausenode->subclauseindices) @@ -80,6 +80,7 @@ create_or_index_paths(Query *root, } if (all_indexable) { + /* * OK, build an IndexPath for this OR clause, using the * best available index for each subclause. @@ -88,19 +89,23 @@ create_or_index_paths(Query *root, pathnode->path.pathtype = T_IndexScan; pathnode->path.parent = rel; + /* - * 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. + * 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; - /* We don't actually care what order the index scans in ... */ + /* + * We don't actually care what order the index scans in + * ... + */ pathnode->indexscandir = NoMovementScanDirection; /* This isn't a nestloop innerjoin, so: */ - pathnode->joinrelids = NIL; /* no join clauses here */ + pathnode->joinrelids = NIL; /* no join clauses here */ pathnode->rows = rel->rows; best_or_subclause_indices(root, @@ -125,7 +130,7 @@ create_or_index_paths(Query *root, * This routine also creates the indexqual and indexid lists 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 + * 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). The indexid * list gives the OID of the index to be used in each scan. @@ -181,7 +186,7 @@ best_or_subclause_indices(Query *root, pathnode->indexqual = lappend(pathnode->indexqual, best_indexqual); pathnode->indexid = lappendi(pathnode->indexid, best_indexid); - if (slist == subclauses) /* first scan? */ + if (slist == subclauses)/* first scan? */ pathnode->path.startup_cost = best_startup_cost; pathnode->path.total_cost += best_total_cost; diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index d5fbf82eb5..580675a85b 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.20 2000/02/18 23:47:19 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.21 2000/04/12 17:15:20 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -28,7 +28,7 @@ static PathKeyItem *makePathKeyItem(Node *key, Oid sortop); static List *make_canonical_pathkey(Query *root, PathKeyItem *item); static Var *find_indexkey_var(Query *root, RelOptInfo *rel, - AttrNumber varattno); + AttrNumber varattno); /*-------------------- @@ -42,8 +42,8 @@ static Var *find_indexkey_var(Query *root, RelOptInfo *rel, * of scanning the relation and the resulting ordering of the tuples. * Sequential scan Paths have NIL pathkeys, indicating no known ordering. * Index scans have Path.pathkeys that represent the chosen index's ordering, - * if any. A single-key index would create a pathkey with a single sublist, - * e.g. ( (tab1.indexkey1/sortop1) ). A multi-key index generates a sublist + * if any. A single-key index would create a pathkey with a single sublist, + * e.g. ( (tab1.indexkey1/sortop1) ). A multi-key index generates a sublist * per key, e.g. ( (tab1.indexkey1/sortop1) (tab1.indexkey2/sortop2) ) which * shows major sort by indexkey1 (ordering by sortop1) and minor sort by * indexkey2 with sortop2. @@ -56,10 +56,10 @@ static Var *find_indexkey_var(Query *root, RelOptInfo *rel, * ordering operators used. * * Things get more interesting when we consider joins. Suppose we do a - * mergejoin between A and B using the mergeclause A.X = B.Y. The output + * mergejoin between A and B using the mergeclause A.X = B.Y. The output * of the mergejoin is sorted by X --- but it is also sorted by Y. We * represent this fact by listing both keys in a single pathkey sublist: - * ( (A.X/xsortop B.Y/ysortop) ). This pathkey asserts that the major + * ( (A.X/xsortop B.Y/ysortop) ). This pathkey asserts that the major * sort order of the Path can be taken to be *either* A.X or B.Y. * They are equal, so they are both primary sort keys. By doing this, * we allow future joins to use either var as a pre-sorted key, so upper @@ -120,12 +120,12 @@ static Var *find_indexkey_var(Query *root, RelOptInfo *rel, * We did implement pathkeys just as described above, and found that the * planner spent a huge amount of time comparing pathkeys, because the * representation of pathkeys as unordered lists made it expensive to decide - * whether two were equal or not. So, we've modified the representation + * whether two were equal or not. So, we've modified the representation * as described next. * * If we scan the WHERE clause for equijoin clauses (mergejoinable clauses) * during planner startup, we can construct lists of equivalent pathkey items - * for the query. There could be more than two items per equivalence set; + * for the query. There could be more than two items per equivalence set; * for example, WHERE A.X = B.Y AND B.Y = C.Z AND D.R = E.S creates the * equivalence sets { A.X B.Y C.Z } and { D.R E.S } (plus associated sortops). * Any pathkey item that belongs to an equivalence set implies that all the @@ -147,20 +147,20 @@ static Var *find_indexkey_var(Query *root, RelOptInfo *rel, * equivalence set, we instantly add all the other vars equivalenced to it, * whether they appear yet in the pathkey's relation or not. And we also * mandate that the pathkey sublist appear in the same order as the - * equivalence set it comes from. (In practice, we simply return a pointer + * equivalence set it comes from. (In practice, we simply return a pointer * to the relevant equivalence set without building any new sublist at all.) * This makes comparing pathkeys very simple and fast, and saves a lot of * work and memory space for pathkey construction as well. * * Note that pathkey sublists having just one item still exist, and are - * not expected to be equal() to any equivalence set. This occurs when + * not expected to be equal() to any equivalence set. This occurs when * we describe a sort order that involves a var that's not mentioned in * any equijoin clause of the WHERE. We could add singleton sets containing * such vars to the query's list of equivalence sets, but there's little * point in doing so. * * By the way, it's OK and even useful for us to build equivalence sets - * that mention multiple vars from the same relation. For example, if + * that mention multiple vars from the same relation. For example, if * we have WHERE A.X = A.Y and we are scanning A using an index on X, * we can legitimately conclude that the path is sorted by Y as well; * and this could be handy if Y is the variable used in other join clauses @@ -179,7 +179,7 @@ static Var *find_indexkey_var(Query *root, RelOptInfo *rel, static PathKeyItem * makePathKeyItem(Node *key, Oid sortop) { - PathKeyItem *item = makeNode(PathKeyItem); + PathKeyItem *item = makeNode(PathKeyItem); item->key = key; item->sortop = sortop; @@ -219,11 +219,13 @@ add_equijoined_keys(Query *root, RestrictInfo *restrictinfo) /* We might see a clause X=X; don't make a single-element list from it */ if (equal(item1, item2)) return; + /* - * Our plan is to make a two-element set, then sweep through the existing - * equijoin sets looking for matches to item1 or item2. When we find one, - * we remove that set from equi_key_list and union it into our new set. - * When done, we add the new set to the front of equi_key_list. + * Our plan is to make a two-element set, then sweep through the + * existing equijoin sets looking for matches to item1 or item2. When + * we find one, we remove that set from equi_key_list and union it + * into our new set. When done, we add the new set to the front of + * equi_key_list. * * This is a standard UNION-FIND problem, for which there exist better * data structures than simple lists. If this code ever proves to be @@ -240,8 +242,11 @@ add_equijoined_keys(Query *root, RestrictInfo *restrictinfo) { /* Found a set to merge into our new set */ newset = LispUnion(newset, curset); - /* Remove old set from equi_key_list. NOTE this does not change - * lnext(cursetlink), so the outer foreach doesn't break. + + /* + * Remove old set from equi_key_list. NOTE this does not + * change lnext(cursetlink), so the outer foreach doesn't + * break. */ root->equi_key_list = lremove(curset, root->equi_key_list); freeList(curset); /* might as well recycle old cons cells */ @@ -256,7 +261,7 @@ add_equijoined_keys(Query *root, RestrictInfo *restrictinfo) * Given a PathKeyItem, find the equi_key_list subset it is a member of, * if any. If so, return a pointer to that sublist, which is the * canonical representation (for this query) of that PathKeyItem's - * equivalence set. If it is not found, return a single-element list + * equivalence set. If it is not found, return a single-element list * containing the PathKeyItem (when the item has no equivalence peers, * we just allow it to be a standalone list). * @@ -293,13 +298,13 @@ canonicalize_pathkeys(Query *root, List *pathkeys) foreach(i, pathkeys) { - List *pathkey = (List *) lfirst(i); - PathKeyItem *item; + List *pathkey = (List *) lfirst(i); + PathKeyItem *item; /* - * It's sufficient to look at the first entry in the sublist; - * if there are more entries, they're already part of an - * equivalence set by definition. + * It's sufficient to look at the first entry in the sublist; if + * there are more entries, they're already part of an equivalence + * set by definition. */ Assert(pathkey != NIL); item = (PathKeyItem *) lfirst(pathkey); @@ -319,12 +324,12 @@ canonicalize_pathkeys(Query *root, List *pathkeys) * one is "better" than the other. * * A pathkey can be considered better than another if it is a superset: - * it contains all the keys of the other plus more. For example, either + * it contains all the keys of the other plus more. For example, either * ((A) (B)) or ((A B)) is better than ((A)). * * Because we actually only expect to see canonicalized pathkey sublists, * we don't have to do the full two-way-subset-inclusion test on each - * pair of sublists that is implied by the above statement. Instead we + * pair of sublists that is implied by the above statement. Instead we * just do an equal(). In the normal case where multi-element sublists * are pointers into the root's equi_key_list, equal() will be very fast: * it will recognize pointer equality when the sublists are the same, @@ -345,23 +350,25 @@ compare_pathkeys(List *keys1, List *keys2) List *subkey1 = lfirst(key1); List *subkey2 = lfirst(key2); - /* We will never have two subkeys where one is a subset of the other, - * because of the canonicalization explained above. Either they are - * equal or they ain't. + /* + * We will never have two subkeys where one is a subset of the + * other, because of the canonicalization explained above. Either + * they are equal or they ain't. */ - if (! equal(subkey1, subkey2)) - return PATHKEYS_DIFFERENT; /* no need to keep looking */ + if (!equal(subkey1, subkey2)) + return PATHKEYS_DIFFERENT; /* no need to keep looking */ } - /* If we reached the end of only one list, the other is longer and - * therefore not a subset. (We assume the additional sublist(s) - * of the other list are not NIL --- no pathkey list should ever have - * a NIL sublist.) + /* + * If we reached the end of only one list, the other is longer and + * therefore not a subset. (We assume the additional sublist(s) of + * the other list are not NIL --- no pathkey list should ever have a + * NIL sublist.) */ if (key1 == NIL && key2 == NIL) return PATHKEYS_EQUAL; if (key1 != NIL) - return PATHKEYS_BETTER1; /* key1 is longer */ + return PATHKEYS_BETTER1;/* key1 is longer */ return PATHKEYS_BETTER2; /* key2 is longer */ } @@ -375,8 +382,8 @@ pathkeys_contained_in(List *keys1, List *keys2) { switch (compare_pathkeys(keys1, keys2)) { - case PATHKEYS_EQUAL: - case PATHKEYS_BETTER2: + case PATHKEYS_EQUAL: + case PATHKEYS_BETTER2: return true; default: break; @@ -448,7 +455,7 @@ get_cheapest_fractional_path_for_pathkeys(List *paths, * do that first. */ if (matched_path != NULL && - compare_fractional_path_costs(matched_path, path, fraction) <= 0) + compare_fractional_path_costs(matched_path, path, fraction) <= 0) continue; if (pathkeys_contained_in(pathkeys, path->pathkeys)) @@ -469,7 +476,7 @@ get_cheapest_fractional_path_for_pathkeys(List *paths, * its "ordering" field, and we will return NIL.) * * If 'scandir' is BackwardScanDirection, attempt to build pathkeys - * representing a backwards scan of the index. Return NIL if can't do it. + * representing a backwards scan of the index. Return NIL if can't do it. */ List * build_index_pathkeys(Query *root, @@ -527,7 +534,7 @@ build_index_pathkeys(Query *root, /* Normal non-functional index */ while (*indexkeys != 0 && *ordering != InvalidOid) { - Var *relvar = find_indexkey_var(root, rel, *indexkeys); + Var *relvar = find_indexkey_var(root, rel, *indexkeys); sortop = *ordering; if (ScanDirectionIsBackward(scandir)) @@ -569,9 +576,9 @@ find_indexkey_var(Query *root, RelOptInfo *rel, AttrNumber varattno) foreach(temp, rel->targetlist) { - Var *tle_var = get_expr(lfirst(temp)); + Var *tle_var = get_expr(lfirst(temp)); - if (IsA(tle_var, Var) && tle_var->varattno == varattno) + if (IsA(tle_var, Var) &&tle_var->varattno == varattno) return tle_var; } @@ -606,11 +613,12 @@ build_join_pathkeys(List *outer_pathkeys, List *join_rel_tlist, List *equi_key_list) { + /* * This used to be quite a complex bit of code, but now that all - * pathkey sublists start out life canonicalized, we don't have to - * do a darn thing here! The inner-rel vars we used to need to add - * are *already* part of the outer pathkey! + * pathkey sublists start out life canonicalized, we don't have to do + * a darn thing here! The inner-rel vars we used to need to add are + * *already* part of the outer pathkey! * * I'd remove the routine entirely, but maybe someday we'll need it... */ @@ -644,16 +652,17 @@ make_pathkeys_for_sortclauses(List *sortclauses, foreach(i, sortclauses) { - SortClause *sortcl = (SortClause *) lfirst(i); - Node *sortkey; - PathKeyItem *pathkey; + SortClause *sortcl = (SortClause *) lfirst(i); + Node *sortkey; + PathKeyItem *pathkey; sortkey = get_sortgroupclause_expr(sortcl, tlist); pathkey = makePathKeyItem(sortkey, sortcl->sortop); + /* * The pathkey becomes a one-element sublist, for now; - * canonicalize_pathkeys() might replace it with a longer - * sublist later. + * canonicalize_pathkeys() might replace it with a longer sublist + * later. */ pathkeys = lappend(pathkeys, lcons(pathkey, NIL)); } @@ -691,28 +700,28 @@ find_mergeclauses_for_pathkeys(List *pathkeys, List *restrictinfos) foreach(i, pathkeys) { - List *pathkey = lfirst(i); - RestrictInfo *matched_restrictinfo = NULL; - List *j; + List *pathkey = lfirst(i); + RestrictInfo *matched_restrictinfo = NULL; + List *j; /* - * We can match any of the keys in this pathkey sublist, - * since they're all equivalent. And we can match against - * either left or right side of any mergejoin clause we haven't - * used yet. For the moment we use a dumb "greedy" algorithm - * with no backtracking. Is it worth being any smarter to - * make a longer list of usable mergeclauses? Probably not. + * We can match any of the keys in this pathkey sublist, since + * they're all equivalent. And we can match against either left + * or right side of any mergejoin clause we haven't used yet. For + * the moment we use a dumb "greedy" algorithm with no + * backtracking. Is it worth being any smarter to make a longer + * list of usable mergeclauses? Probably not. */ foreach(j, pathkey) { - PathKeyItem *keyitem = lfirst(j); - Node *key = keyitem->key; - Oid keyop = keyitem->sortop; - List *k; + PathKeyItem *keyitem = lfirst(j); + Node *key = keyitem->key; + Oid keyop = keyitem->sortop; + List *k; foreach(k, restrictinfos) { - RestrictInfo *restrictinfo = lfirst(k); + RestrictInfo *restrictinfo = lfirst(k); Assert(restrictinfo->mergejoinoperator != InvalidOid); @@ -720,7 +729,7 @@ find_mergeclauses_for_pathkeys(List *pathkeys, List *restrictinfos) equal(key, get_leftop(restrictinfo->clause))) || (keyop == restrictinfo->right_sortop && equal(key, get_rightop(restrictinfo->clause)))) && - ! member(restrictinfo, mergeclauses)) + !member(restrictinfo, mergeclauses)) { matched_restrictinfo = restrictinfo; break; @@ -732,11 +741,12 @@ find_mergeclauses_for_pathkeys(List *pathkeys, List *restrictinfos) /* * If we didn't find a mergeclause, we're done --- any additional - * sort-key positions in the pathkeys are useless. (But we can + * sort-key positions in the pathkeys are useless. (But we can * still mergejoin if we found at least one mergeclause.) */ - if (! matched_restrictinfo) + if (!matched_restrictinfo) break; + /* * If we did find a usable mergeclause for this sort-key position, * add it to result list. @@ -756,7 +766,7 @@ find_mergeclauses_for_pathkeys(List *pathkeys, List *restrictinfos) * 'mergeclauses' is a list of RestrictInfos for mergejoin clauses * that will be used in a merge join. * 'tlist' is a relation target list for either the inner or outer - * side of the proposed join rel. (Not actually needed anymore) + * side of the proposed join rel. (Not actually needed anymore) * * Returns a pathkeys list that can be applied to the indicated relation. * @@ -785,24 +795,26 @@ make_pathkeys_for_mergeclauses(Query *root, /* * Find the key and sortop needed for this mergeclause. * - * Both sides of the mergeclause should appear in one of the - * query's pathkey equivalence classes, so it doesn't matter - * which one we use here. + * Both sides of the mergeclause should appear in one of the query's + * pathkey equivalence classes, so it doesn't matter which one we + * use here. */ key = (Node *) get_leftop(restrictinfo->clause); sortop = restrictinfo->left_sortop; + /* - * Find pathkey sublist for this sort item. We expect to find - * the canonical set including the mergeclause's left and right - * sides; if we get back just the one item, something is rotten. + * Find pathkey sublist for this sort item. We expect to find the + * canonical set including the mergeclause's left and right sides; + * if we get back just the one item, something is rotten. */ item = makePathKeyItem(key, sortop); pathkey = make_canonical_pathkey(root, item); Assert(length(pathkey) > 1); + /* - * Since the item we just made is not in the returned canonical set, - * we can free it --- this saves a useful amount of storage in a - * big join tree. + * Since the item we just made is not in the returned canonical + * set, we can free it --- this saves a useful amount of storage + * in a big join tree. */ pfree(item); diff --git a/src/backend/optimizer/path/tidpath.c b/src/backend/optimizer/path/tidpath.c index 1e7dc43473..7824e0e3d2 100644 --- a/src/backend/optimizer/path/tidpath.c +++ b/src/backend/optimizer/path/tidpath.c @@ -9,7 +9,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/tidpath.c,v 1.5 2000/02/15 20:49:17 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/tidpath.c,v 1.6 2000/04/12 17:15:20 momjian Exp $ * *------------------------------------------------------------------------- */ @@ -37,30 +37,34 @@ #include "utils/lsyscache.h" static void create_tidscan_joinpaths(RelOptInfo *rel); -static List *TidqualFromRestrictinfo(List *relids, List *restrictinfo); -static bool isEvaluable(int varno, Node *node); -static Node *TidequalClause(int varno, Expr *node); -static List *TidqualFromExpr(int varno, Expr *expr); +static List *TidqualFromRestrictinfo(List *relids, List *restrictinfo); +static bool isEvaluable(int varno, Node *node); +static Node *TidequalClause(int varno, Expr *node); +static List *TidqualFromExpr(int varno, Expr *expr); static -bool isEvaluable(int varno, Node *node) +bool +isEvaluable(int varno, Node *node) { - List *lst; - Expr *expr; + List *lst; + Expr *expr; - if (IsA(node, Const)) return true; - if (IsA(node, Param)) return true; + if (IsA(node, Const)) + return true; + if (IsA(node, Param)) + return true; if (IsA(node, Var)) { - Var *var = (Var *)node; + Var *var = (Var *) node; if (var->varno == varno) return false; return true; } - if (!is_funcclause(node)) return false; - expr = (Expr *)node; - foreach (lst, expr->args) + if (!is_funcclause(node)) + return false; + expr = (Expr *) node; + foreach(lst, expr->args) { if (!isEvaluable(varno, lfirst(lst))) return false; @@ -72,53 +76,60 @@ bool isEvaluable(int varno, Node *node) /* * The 2nd parameter should be an opclause * Extract the right node if the opclause is CTID= .... - * or the left node if the opclause is ....=CTID + * or the left node if the opclause is ....=CTID */ static -Node *TidequalClause(int varno, Expr *node) +Node * +TidequalClause(int varno, Expr *node) { - Node *rnode = 0, *arg1, *arg2, *arg; - Oper *oper; - Var *var; - Const *aconst; - Param *param; - Expr *expr; + Node *rnode = 0, + *arg1, + *arg2, + *arg; + Oper *oper; + Var *var; + Const *aconst; + Param *param; + Expr *expr; - if (!node->oper) return rnode; - if (!node->args) return rnode; - if (length(node->args) != 2) return rnode; - oper = (Oper *) node->oper; + if (!node->oper) + return rnode; + if (!node->args) + return rnode; + if (length(node->args) != 2) + return rnode; + oper = (Oper *) node->oper; if (oper->opno != TIDEqualOperator) return rnode; arg1 = lfirst(node->args); arg2 = lsecond(node->args); - arg = (Node *)0; + arg = (Node *) 0; if (IsA(arg1, Var)) { var = (Var *) arg1; if (var->varno == varno && - var->varattno == SelfItemPointerAttributeNumber && - var->vartype == TIDOID) + var->varattno == SelfItemPointerAttributeNumber && + var->vartype == TIDOID) arg = arg2; else if (var->varnoold == varno && - var->varoattno == SelfItemPointerAttributeNumber && - var->vartype == TIDOID) + var->varoattno == SelfItemPointerAttributeNumber && + var->vartype == TIDOID) arg = arg2; } if ((!arg) && IsA(arg2, Var)) { var = (Var *) arg2; if (var->varno == varno && - var->varattno == SelfItemPointerAttributeNumber && - var->vartype == TIDOID) + var->varattno == SelfItemPointerAttributeNumber && + var->vartype == TIDOID) arg = arg1; } if (!arg) return rnode; switch (nodeTag(arg)) { - case T_Const: + case T_Const: aconst = (Const *) arg; if (aconst->consttype != TIDOID) return rnode; @@ -126,27 +137,29 @@ Node *TidequalClause(int varno, Expr *node) return rnode; rnode = arg; break; - case T_Param: + case T_Param: param = (Param *) arg; if (param->paramtype != TIDOID) return rnode; rnode = arg; break; - case T_Var: + case T_Var: var = (Var *) arg; if (var->varno == varno || - var->vartype != TIDOID) + var->vartype != TIDOID) return rnode; rnode = arg; break; - case T_Expr: + case T_Expr: expr = (Expr *) arg; - if (expr->typeOid != TIDOID) return rnode; - if (expr->opType != FUNC_EXPR) return rnode; - if (isEvaluable(varno, (Node *)expr)) + if (expr->typeOid != TIDOID) + return rnode; + if (expr->opType != FUNC_EXPR) + return rnode; + if (isEvaluable(varno, (Node *) expr)) rnode = arg; break; - default: + default: break; } return rnode; @@ -160,43 +173,43 @@ Node *TidequalClause(int varno, Expr *node) * When the expr node is an and_clause,we return the list of * CTID values if we could extract the CTID values from a member * node. - */ + */ static -List *TidqualFromExpr(int varno, Expr *expr) +List * +TidqualFromExpr(int varno, Expr *expr) { - List *rlst = NIL, *lst, *frtn; - Node *node = (Node *) expr, *rnode; + List *rlst = NIL, + *lst, + *frtn; + Node *node = (Node *) expr, + *rnode; if (is_opclause(node)) { rnode = TidequalClause(varno, expr); if (rnode) - { rlst = lcons(rnode, rlst); - } } else if (and_clause(node)) { - foreach (lst, expr->args) + foreach(lst, expr->args) { node = lfirst(lst); - if (!IsA(node, Expr)) + if (!IsA(node, Expr)) continue; - rlst = TidqualFromExpr(varno, (Expr *)node); + rlst = TidqualFromExpr(varno, (Expr *) node); if (rlst) break; } } else if (or_clause(node)) { - foreach (lst, expr->args) + foreach(lst, expr->args) { node = lfirst(lst); if (IsA(node, Expr) && - (frtn = TidqualFromExpr(varno, (Expr *)node)) ) - { + (frtn = TidqualFromExpr(varno, (Expr *) node))) rlst = nconc(rlst, frtn); - } else { if (rlst) @@ -207,24 +220,26 @@ List *TidqualFromExpr(int varno, Expr *expr) } } return rlst; -} +} static List * TidqualFromRestrictinfo(List *relids, List *restrictinfo) { - List *lst, *rlst = NIL; - int varno; - Node *node; - Expr *expr; + List *lst, + *rlst = NIL; + int varno; + Node *node; + Expr *expr; if (length(relids) != 1) return NIL; varno = lfirsti(relids); - foreach (lst, restrictinfo) + foreach(lst, restrictinfo) { node = lfirst(lst); - if (!IsA(node, RestrictInfo)) continue; - expr = ((RestrictInfo *)node)->clause; + if (!IsA(node, RestrictInfo)) + continue; + expr = ((RestrictInfo *) node)->clause; rlst = TidqualFromExpr(varno, expr); if (rlst) break; @@ -241,20 +256,20 @@ TidqualFromRestrictinfo(List *relids, List *restrictinfo) static void create_tidscan_joinpaths(RelOptInfo *rel) { - List *rlst = NIL, - *lst; + List *rlst = NIL, + *lst; - foreach (lst, rel->joininfo) + foreach(lst, rel->joininfo) { JoinInfo *joininfo = (JoinInfo *) lfirst(lst); - List *restinfo, - *tideval; + List *restinfo, + *tideval; restinfo = joininfo->jinfo_restrictinfo; tideval = TidqualFromRestrictinfo(rel->relids, restinfo); if (length(tideval) == 1) { - TidPath *pathnode = makeNode(TidPath); + TidPath *pathnode = makeNode(TidPath); pathnode->path.pathtype = T_TidScan; pathnode->path.parent = rel; @@ -278,9 +293,9 @@ create_tidscan_joinpaths(RelOptInfo *rel) void create_tidscan_paths(Query *root, RelOptInfo *rel) { - List *tideval = TidqualFromRestrictinfo(rel->relids, - rel->baserestrictinfo); - + List *tideval = TidqualFromRestrictinfo(rel->relids, + rel->baserestrictinfo); + if (tideval) add_path(rel, (Path *) create_tidscan_path(rel, tideval)); create_tidscan_joinpaths(rel); |