diff options
Diffstat (limited to 'src/backend/optimizer/plan')
| -rw-r--r-- | src/backend/optimizer/plan/createplan.c | 279 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/initsplan.c | 317 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/planmain.c | 51 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/planner.c | 60 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/setrefs.c | 17 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/subselect.c | 12 |
6 files changed, 575 insertions, 161 deletions
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index c049f5d86b6..96dc3327b7f 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -10,7 +10,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.95 2000/08/13 02:50:06 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.96 2000/09/12 21:06:53 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -42,36 +42,47 @@ static IndexScan *create_indexscan_node(Query *root, IndexPath *best_path, static TidScan *create_tidscan_node(TidPath *best_path, List *tlist, List *scan_clauses); static NestLoop *create_nestloop_node(NestPath *best_path, List *tlist, - List *clauses, Plan *outer_node, List *outer_tlist, - Plan *inner_node, List *inner_tlist); + List *joinclauses, List *otherclauses, + Plan *outer_node, List *outer_tlist, + Plan *inner_node, List *inner_tlist); static MergeJoin *create_mergejoin_node(MergePath *best_path, List *tlist, - List *clauses, Plan *outer_node, List *outer_tlist, - Plan *inner_node, List *inner_tlist); + List *joinclauses, List *otherclauses, + Plan *outer_node, List *outer_tlist, + Plan *inner_node, List *inner_tlist); static HashJoin *create_hashjoin_node(HashPath *best_path, List *tlist, - List *clauses, Plan *outer_node, List *outer_tlist, - Plan *inner_node, List *inner_tlist); + List *joinclauses, List *otherclauses, + Plan *outer_node, List *outer_tlist, + Plan *inner_node, List *inner_tlist); static List *fix_indxqual_references(List *indexquals, IndexPath *index_path); static List *fix_indxqual_sublist(List *indexqual, int baserelid, Oid relam, Form_pg_index index); static Node *fix_indxqual_operand(Node *node, int baserelid, Form_pg_index index, Oid *opclass); +static SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid); static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid, List *indxid, List *indxqual, List *indxqualorig, ScanDirection indexscandir); static TidScan *make_tidscan(List *qptlist, List *qpqual, Index scanrelid, List *tideval); -static NestLoop *make_nestloop(List *qptlist, List *qpqual, Plan *lefttree, - Plan *righttree); -static HashJoin *make_hashjoin(List *tlist, List *qpqual, - List *hashclauses, Plan *lefttree, Plan *righttree); +static NestLoop *make_nestloop(List *tlist, + List *joinclauses, List *otherclauses, + Plan *lefttree, Plan *righttree, + JoinType jointype); +static HashJoin *make_hashjoin(List *tlist, + List *joinclauses, List *otherclauses, + List *hashclauses, + Plan *lefttree, Plan *righttree, + JoinType jointype); static Hash *make_hash(List *tlist, Node *hashkey, Plan *lefttree); -static MergeJoin *make_mergejoin(List *tlist, List *qpqual, - List *mergeclauses, Plan *righttree, Plan *lefttree); +static MergeJoin *make_mergejoin(List *tlist, + List *joinclauses, List *otherclauses, + List *mergeclauses, + Plan *lefttree, Plan *righttree, + JoinType jointype); static void copy_path_costsize(Plan *dest, Path *src); static void copy_plan_costsize(Plan *dest, Plan *src); -static SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid); /* * create_plan @@ -195,7 +206,8 @@ create_join_node(Query *root, JoinPath *best_path, List *tlist) List *outer_tlist; Plan *inner_node; List *inner_tlist; - List *clauses; + List *joinclauses; + List *otherclauses; Join *retval = NULL; outer_node = create_plan(root, best_path->outerjoinpath); @@ -204,14 +216,25 @@ create_join_node(Query *root, JoinPath *best_path, List *tlist) inner_node = create_plan(root, best_path->innerjoinpath); inner_tlist = inner_node->targetlist; - clauses = get_actual_clauses(best_path->joinrestrictinfo); + if (IS_OUTER_JOIN(best_path->jointype)) + { + get_actual_join_clauses(best_path->joinrestrictinfo, + &joinclauses, &otherclauses); + } + else + { + /* We can treat all clauses alike for an inner join */ + joinclauses = get_actual_clauses(best_path->joinrestrictinfo); + otherclauses = NIL; + } switch (best_path->path.pathtype) { case T_MergeJoin: retval = (Join *) create_mergejoin_node((MergePath *) best_path, tlist, - clauses, + joinclauses, + otherclauses, outer_node, outer_tlist, inner_node, @@ -220,7 +243,8 @@ create_join_node(Query *root, JoinPath *best_path, List *tlist) case T_HashJoin: retval = (Join *) create_hashjoin_node((HashPath *) best_path, tlist, - clauses, + joinclauses, + otherclauses, outer_node, outer_tlist, inner_node, @@ -229,7 +253,8 @@ create_join_node(Query *root, JoinPath *best_path, List *tlist) case T_NestLoop: retval = (Join *) create_nestloop_node((NestPath *) best_path, tlist, - clauses, + joinclauses, + otherclauses, outer_node, outer_tlist, inner_node, @@ -411,30 +436,6 @@ create_indexscan_node(Query *root, return scan_node; } -static TidScan * -make_tidscan(List *qptlist, - List *qpqual, - Index scanrelid, - List *tideval) -{ - TidScan *node = makeNode(TidScan); - Plan *plan = &node->scan.plan; - - /* cost should be inserted by caller */ - plan->state = (EState *) NULL; - plan->targetlist = qptlist; - plan->qual = qpqual; - plan->lefttree = NULL; - plan->righttree = NULL; - node->scan.scanrelid = scanrelid; - node->tideval = copyObject(tideval); /* XXX do we really need a - * copy? */ - node->needRescan = false; - node->scan.scanstate = (CommonScanState *) NULL; - - return node; -} - /* * create_tidscan_node * Returns a tidscan node for the base relation scanned by 'best_path' @@ -488,7 +489,8 @@ create_tidscan_node(TidPath *best_path, List *tlist, List *scan_clauses) static NestLoop * create_nestloop_node(NestPath *best_path, List *tlist, - List *clauses, + List *joinclauses, + List *otherclauses, Plan *outer_node, List *outer_tlist, Plan *inner_node, @@ -535,7 +537,8 @@ create_nestloop_node(NestPath *best_path, * attnos, and may have been commuted as well). */ if (length(indxqualorig) == 1) /* single indexscan? */ - clauses = set_difference(clauses, lfirst(indxqualorig)); + joinclauses = set_difference(joinclauses, + lfirst(indxqualorig)); /* only refs to outer vars get changed in the inner indexqual */ innerscan->indxqualorig = join_references(indxqualorig, @@ -577,15 +580,26 @@ create_nestloop_node(NestPath *best_path, inner_node); } + /* + * Set quals to contain INNER/OUTER var references. + */ + joinclauses = join_references(joinclauses, + outer_tlist, + inner_tlist, + (Index) 0); + otherclauses = join_references(otherclauses, + outer_tlist, + inner_tlist, + (Index) 0); + join_node = make_nestloop(tlist, - join_references(clauses, - outer_tlist, - inner_tlist, - (Index) 0), + joinclauses, + otherclauses, outer_node, - inner_node); + inner_node, + best_path->jointype); - copy_path_costsize(&join_node->join, &best_path->path); + copy_path_costsize(&join_node->join.plan, &best_path->path); return join_node; } @@ -593,14 +607,14 @@ create_nestloop_node(NestPath *best_path, static MergeJoin * create_mergejoin_node(MergePath *best_path, List *tlist, - List *clauses, + List *joinclauses, + List *otherclauses, Plan *outer_node, List *outer_tlist, Plan *inner_node, List *inner_tlist) { - List *qpqual, - *mergeclauses; + List *mergeclauses; MergeJoin *join_node; mergeclauses = get_actual_clauses(best_path->path_mergeclauses); @@ -610,10 +624,18 @@ create_mergejoin_node(MergePath *best_path, * the list of quals that must be checked as qpquals. Set those * clauses to contain INNER/OUTER var references. */ - qpqual = join_references(set_difference(clauses, mergeclauses), - outer_tlist, - inner_tlist, - (Index) 0); + joinclauses = join_references(set_difference(joinclauses, mergeclauses), + outer_tlist, + inner_tlist, + (Index) 0); + + /* + * Fix the additional qpquals too. + */ + otherclauses = join_references(otherclauses, + outer_tlist, + inner_tlist, + (Index) 0); /* * Now set the references in the mergeclauses and rearrange them so @@ -640,13 +662,54 @@ create_mergejoin_node(MergePath *best_path, inner_node, best_path->innersortkeys); + /* + * The executor requires the inner side of a mergejoin to support "mark" + * and "restore" operations. Not all plan types do, so we must be careful + * not to generate an invalid plan. If necessary, an invalid inner plan + * can be handled by inserting a Materialize node. + * + * Since the inner side must be ordered, and only Sorts and IndexScans can + * create order to begin with, you might think there's no problem --- but + * you'd be wrong. Nestloop and merge joins can *preserve* the order of + * their inputs, so they can be selected as the input of a mergejoin, + * and that won't work in the present executor. + * + * Doing this here is a bit of a kluge since the cost of the Materialize + * wasn't taken into account in our earlier decisions. But Materialize + * is hard to estimate a cost for, and the above consideration shows that + * this is a rare case anyway, so this seems an acceptable way to proceed. + * + * This check must agree with ExecMarkPos/ExecRestrPos in + * executor/execAmi.c! + */ + switch (nodeTag(inner_node)) + { + case T_SeqScan: + case T_IndexScan: + case T_Material: + case T_Sort: + /* OK, these inner plans support mark/restore */ + break; + + default: + /* Ooops, need to materialize the inner plan */ + inner_node = (Plan *) make_material(inner_tlist, + inner_node); + break; + } + + /* + * Now we can build the mergejoin node. + */ join_node = make_mergejoin(tlist, - qpqual, + joinclauses, + otherclauses, mergeclauses, + outer_node, inner_node, - outer_node); + best_path->jpath.jointype); - copy_path_costsize(&join_node->join, &best_path->jpath.path); + copy_path_costsize(&join_node->join.plan, &best_path->jpath.path); return join_node; } @@ -654,13 +717,13 @@ create_mergejoin_node(MergePath *best_path, static HashJoin * create_hashjoin_node(HashPath *best_path, List *tlist, - List *clauses, + List *joinclauses, + List *otherclauses, Plan *outer_node, List *outer_tlist, Plan *inner_node, List *inner_tlist) { - List *qpqual; List *hashclauses; HashJoin *join_node; Hash *hash_node; @@ -679,10 +742,18 @@ create_hashjoin_node(HashPath *best_path, * the list of quals that must be checked as qpquals. Set those * clauses to contain INNER/OUTER var references. */ - qpqual = join_references(set_difference(clauses, hashclauses), - outer_tlist, - inner_tlist, - (Index) 0); + joinclauses = join_references(set_difference(joinclauses, hashclauses), + outer_tlist, + inner_tlist, + (Index) 0); + + /* + * Fix the additional qpquals too. + */ + otherclauses = join_references(otherclauses, + outer_tlist, + inner_tlist, + (Index) 0); /* * Now set the references in the hashclauses and rearrange them so @@ -701,12 +772,14 @@ create_hashjoin_node(HashPath *best_path, */ hash_node = make_hash(inner_tlist, innerhashkey, inner_node); join_node = make_hashjoin(tlist, - qpqual, + joinclauses, + otherclauses, hashclauses, outer_node, - (Plan *) hash_node); + (Plan *) hash_node, + best_path->jpath.jointype); - copy_path_costsize(&join_node->join, &best_path->jpath.path); + copy_path_costsize(&join_node->join.plan, &best_path->jpath.path); return join_node; } @@ -1065,45 +1138,75 @@ make_indexscan(List *qptlist, return node; } +static TidScan * +make_tidscan(List *qptlist, + List *qpqual, + Index scanrelid, + List *tideval) +{ + TidScan *node = makeNode(TidScan); + Plan *plan = &node->scan.plan; + + /* cost should be inserted by caller */ + plan->state = (EState *) NULL; + plan->targetlist = qptlist; + plan->qual = qpqual; + plan->lefttree = NULL; + plan->righttree = NULL; + node->scan.scanrelid = scanrelid; + node->tideval = copyObject(tideval); /* XXX do we really need a + * copy? */ + node->needRescan = false; + node->scan.scanstate = (CommonScanState *) NULL; + + return node; +} + static NestLoop * -make_nestloop(List *qptlist, - List *qpqual, +make_nestloop(List *tlist, + List *joinclauses, + List *otherclauses, Plan *lefttree, - Plan *righttree) + Plan *righttree, + JoinType jointype) { NestLoop *node = makeNode(NestLoop); - Plan *plan = &node->join; + Plan *plan = &node->join.plan; /* cost should be inserted by caller */ plan->state = (EState *) NULL; - plan->targetlist = qptlist; - plan->qual = qpqual; + plan->targetlist = tlist; + plan->qual = otherclauses; plan->lefttree = lefttree; plan->righttree = righttree; - node->nlstate = (NestLoopState *) NULL; + node->join.jointype = jointype; + node->join.joinqual = joinclauses; return node; } static HashJoin * make_hashjoin(List *tlist, - List *qpqual, + List *joinclauses, + List *otherclauses, List *hashclauses, Plan *lefttree, - Plan *righttree) + Plan *righttree, + JoinType jointype) { HashJoin *node = makeNode(HashJoin); - Plan *plan = &node->join; + Plan *plan = &node->join.plan; /* cost should be inserted by caller */ plan->state = (EState *) NULL; plan->targetlist = tlist; - plan->qual = qpqual; + plan->qual = otherclauses; plan->lefttree = lefttree; plan->righttree = righttree; node->hashclauses = hashclauses; - node->hashdone = false; + node->join.jointype = jointype; + node->join.joinqual = joinclauses; return node; } @@ -1133,21 +1236,25 @@ make_hash(List *tlist, Node *hashkey, Plan *lefttree) static MergeJoin * make_mergejoin(List *tlist, - List *qpqual, + List *joinclauses, + List *otherclauses, List *mergeclauses, + Plan *lefttree, Plan *righttree, - Plan *lefttree) + JoinType jointype) { MergeJoin *node = makeNode(MergeJoin); - Plan *plan = &node->join; + Plan *plan = &node->join.plan; /* cost should be inserted by caller */ plan->state = (EState *) NULL; plan->targetlist = tlist; - plan->qual = qpqual; + plan->qual = otherclauses; plan->lefttree = lefttree; plan->righttree = righttree; node->mergeclauses = mergeclauses; + node->join.jointype = jointype; + node->join.joinqual = joinclauses; return node; } diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c index 8ffd35c9bb0..bf728ca1bdc 100644 --- a/src/backend/optimizer/plan/initsplan.c +++ b/src/backend/optimizer/plan/initsplan.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/initsplan.c,v 1.49 2000/08/13 02:50:07 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/initsplan.c,v 1.50 2000/09/12 21:06:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -26,13 +26,18 @@ #include "optimizer/planmain.h" #include "optimizer/tlist.h" #include "optimizer/var.h" +#include "parser/parsetree.h" #include "parser/parse_expr.h" #include "parser/parse_oper.h" #include "parser/parse_type.h" #include "utils/lsyscache.h" -static void add_restrict_and_join_to_rel(Query *root, Node *clause); +static void mark_baserels_for_outer_join(Query *root, Relids rels, + Relids outerrels); +static void add_restrict_and_join_to_rel(Query *root, Node *clause, + bool isjoinqual, + Relids outerjoinrelids); static void add_join_info_to_rels(Query *root, RestrictInfo *restrictinfo, Relids join_relids); static void add_vars_to_targetlist(Query *root, List *vars); @@ -47,14 +52,14 @@ static void check_hashjoinable(RestrictInfo *restrictinfo); *****************************************************************************/ /* - * make_var_only_tlist + * build_base_rel_tlists * Creates rel nodes for every relation mentioned in the target list * 'tlist' (if a node hasn't already been created) and adds them to - * *query_relation_list*. Creates targetlist entries for each member of - * 'tlist' and adds them to the tlist field of the appropriate rel node. + * root->base_rel_list. Creates targetlist entries for each var seen + * in 'tlist' and adds them to the tlist of the appropriate rel node. */ void -make_var_only_tlist(Query *root, List *tlist) +build_base_rel_tlists(Query *root, List *tlist) { List *tlist_vars = pull_var_clause((Node *) tlist, false); @@ -82,48 +87,75 @@ add_vars_to_targetlist(Query *root, List *vars) } } -/* +/*---------- * add_missing_rels_to_query * - * If we have a range variable in the FROM clause that does not appear + * If we have a relation listed in the join tree that does not appear * in the target list nor qualifications, we must add it to the base - * relation list so that it will be joined. For instance, "select f.x - * from foo f, foo f2" is a join of f and f2. Note that if we have - * "select foo.x from foo f", it also gets turned into a join (between - * foo as foo and foo as f). + * relation list so that it can be processed. For instance, + * select f.x from foo f, foo f2 + * is a join of f and f2. Note that if we have + * select foo.x from foo f + * this also gets turned into a join (between foo as foo and foo as f). * * To avoid putting useless entries into the per-relation targetlists, * this should only be called after all the variables in the targetlist * and quals have been processed by the routines above. + * + * Returns a list of all the base relations (RelOptInfo nodes) that appear + * in the join tree. This list can be used for cross-checking in the + * reverse direction, ie, that we have a join tree entry for every + * relation used in the query. + *---------- */ -void -add_missing_rels_to_query(Query *root) +List * +add_missing_rels_to_query(Query *root, Node *jtnode) { - int varno = 1; - List *l; + List *result = NIL; - foreach(l, root->rtable) + if (jtnode == NULL) + return NIL; + if (IsA(jtnode, List)) { - RangeTblEntry *rte = (RangeTblEntry *) lfirst(l); + List *l; - if (rte->inJoinSet) + foreach(l, (List *) jtnode) { - RelOptInfo *rel = get_base_rel(root, varno); + result = nconc(result, + add_missing_rels_to_query(root, lfirst(l))); + } + } + else if (IsA(jtnode, RangeTblRef)) + { + int varno = ((RangeTblRef *) jtnode)->rtindex; + RelOptInfo *rel = get_base_rel(root, varno); - /* - * If the rel isn't otherwise referenced, give it a dummy - * targetlist consisting of its own OID. - */ - if (rel->targetlist == NIL) - { - Var *var = makeVar(varno, ObjectIdAttributeNumber, - OIDOID, -1, 0); + /* + * If the rel isn't otherwise referenced, give it a dummy + * targetlist consisting of its own OID. + */ + if (rel->targetlist == NIL) + { + Var *var = makeVar(varno, ObjectIdAttributeNumber, + OIDOID, -1, 0); - add_var_to_tlist(rel, var); - } + add_var_to_tlist(rel, var); } - varno++; + + result = lcons(rel, NIL); } + else if (IsA(jtnode, JoinExpr)) + { + JoinExpr *j = (JoinExpr *) jtnode; + + result = add_missing_rels_to_query(root, j->larg); + result = nconc(result, + add_missing_rels_to_query(root, j->rarg)); + } + else + elog(ERROR, "add_missing_rels_to_query: unexpected node type %d", + nodeTag(jtnode)); + return result; } @@ -135,10 +167,144 @@ add_missing_rels_to_query(Query *root) /* + * add_join_quals_to_rels + * Recursively scan the join tree for JOIN/ON (and JOIN/USING) qual + * clauses, and add these to the appropriate JoinInfo lists. Also, + * mark base RelOptInfos with outerjoinset information, which will + * be needed for proper placement of WHERE clauses during + * add_restrict_and_join_to_rels(). + * + * NOTE: when dealing with inner joins, it is appropriate to let a qual clause + * be evaluated at the lowest level where all the variables it mentions are + * available. However, we cannot do this within an outer join since the qual + * might eliminate matching rows and cause a NULL row to be added improperly. + * Therefore, rels appearing within (the nullable side of) an outer join + * are marked with outerjoinset = list of Relids used at the outer join node. + * This list will be added to the list of rels referenced by quals using + * such a rel, thereby forcing them up the join tree to the right level. + * + * To ease the calculation of these values, add_join_quals_to_rels() returns + * the list of Relids involved in its own level of join. This is just an + * internal convenience; no outside callers pay attention to the result. + */ +Relids +add_join_quals_to_rels(Query *root, Node *jtnode) +{ + Relids result = NIL; + + if (jtnode == NULL) + return result; + if (IsA(jtnode, List)) + { + List *l; + + /* + * Note: we assume it's impossible to see same RT index from more + * than one subtree, so nconc() is OK rather than LispUnioni(). + */ + foreach(l, (List *) jtnode) + result = nconc(result, + add_join_quals_to_rels(root, lfirst(l))); + } + else if (IsA(jtnode, RangeTblRef)) + { + int varno = ((RangeTblRef *) jtnode)->rtindex; + + /* No quals to deal with, just return correct result */ + result = lconsi(varno, NIL); + } + else if (IsA(jtnode, JoinExpr)) + { + JoinExpr *j = (JoinExpr *) jtnode; + Relids leftids, + rightids, + outerjoinids; + List *qual; + + /* + * Order of operations here is subtle and critical. First we recurse + * to handle sub-JOINs. Their join quals will be placed without + * regard for whether this level is an outer join, which is correct. + * Then, if we are an outer join, we mark baserels contained within + * the nullable side(s) with our own rel list; this will restrict + * placement of subsequent quals using those rels, including our own + * quals, quals above us in the join tree, and WHERE quals. + * Finally we place our own join quals. + */ + leftids = add_join_quals_to_rels(root, j->larg); + rightids = add_join_quals_to_rels(root, j->rarg); + + result = nconc(listCopy(leftids), rightids); + + outerjoinids = NIL; + switch (j->jointype) + { + case JOIN_INNER: + /* Inner join adds no restrictions for quals */ + break; + case JOIN_LEFT: + mark_baserels_for_outer_join(root, rightids, result); + outerjoinids = result; + break; + case JOIN_FULL: + mark_baserels_for_outer_join(root, result, result); + outerjoinids = result; + break; + case JOIN_RIGHT: + mark_baserels_for_outer_join(root, leftids, result); + outerjoinids = result; + break; + case JOIN_UNION: + /* + * This is where we fail if upper levels of planner haven't + * rewritten UNION JOIN as an Append ... + */ + elog(ERROR, "UNION JOIN is not implemented yet"); + break; + default: + elog(ERROR, "add_join_quals_to_rels: unsupported join type %d", + (int) j->jointype); + break; + } + + foreach(qual, (List *) j->quals) + add_restrict_and_join_to_rel(root, (Node *) lfirst(qual), + true, outerjoinids); + } + else + elog(ERROR, "add_join_quals_to_rels: unexpected node type %d", + nodeTag(jtnode)); + return result; +} + +/* + * mark_baserels_for_outer_join + * Mark all base rels listed in 'rels' as having the given outerjoinset. + */ +static void +mark_baserels_for_outer_join(Query *root, Relids rels, Relids outerrels) +{ + List *relid; + + foreach(relid, rels) + { + RelOptInfo *rel = get_base_rel(root, lfirsti(relid)); + + /* + * Since we do this bottom-up, any outer-rels previously marked + * should be within the new outer join set. + */ + Assert(is_subseti(rel->outerjoinset, outerrels)); + + rel->outerjoinset = outerrels; + } +} + +/* * add_restrict_and_join_to_rels * Fill RestrictInfo and JoinInfo lists of relation entries for all * relations appearing within clauses. Creates new relation entries if - * necessary, adding them to *query_relation_list*. + * necessary, adding them to root->base_rel_list. * * 'clauses': the list of clauses in the cnfify'd query qualification. */ @@ -148,7 +314,8 @@ add_restrict_and_join_to_rels(Query *root, List *clauses) List *clause; foreach(clause, clauses) - add_restrict_and_join_to_rel(root, (Node *) lfirst(clause)); + add_restrict_and_join_to_rel(root, (Node *) lfirst(clause), + false, NIL); } /* @@ -157,17 +324,31 @@ add_restrict_and_join_to_rels(Query *root, List *clauses) * (depending on whether the clause is a join) of each base relation * mentioned in the clause. A RestrictInfo node is created and added to * the appropriate list for each rel. Also, if the clause uses a - * mergejoinable operator, enter the left- and right-side expressions - * into the query's lists of equijoined vars. + * mergejoinable operator and is not an outer-join qual, enter the left- + * and right-side expressions into the query's lists of equijoined vars. + * + * isjoinqual is true if the clause came from JOIN/ON or JOIN/USING; + * we have to mark the created RestrictInfo accordingly. If the JOIN + * is an OUTER join, the caller must set outerjoinrelids = all relids of join, + * which will override the joinrel identifiers extracted from the clause + * itself. For inner join quals and WHERE clauses, set outerjoinrelids = NIL. + * (Passing the whole list, and not just an "isouterjoin" boolean, is simply + * a speed optimization: we could extract the same list from the base rels' + * outerjoinsets, but since add_join_quals_to_rels() already knows what we + * should use, might as well pass it in instead of recalculating it.) */ static void -add_restrict_and_join_to_rel(Query *root, Node *clause) +add_restrict_and_join_to_rel(Query *root, Node *clause, + bool isjoinqual, + Relids outerjoinrelids) { RestrictInfo *restrictinfo = makeNode(RestrictInfo); Relids relids; List *vars; + bool can_be_equijoin; restrictinfo->clause = (Expr *) clause; + restrictinfo->isjoinqual = isjoinqual; restrictinfo->subclauseindices = NIL; restrictinfo->mergejoinoperator = InvalidOid; restrictinfo->left_sortop = InvalidOid; @@ -179,6 +360,44 @@ add_restrict_and_join_to_rel(Query *root, Node *clause) */ clause_get_relids_vars(clause, &relids, &vars); + /* + * If caller has given us a join relid list, use it; otherwise, we must + * scan the referenced base rels and add in any outer-join rel lists. + * This prevents the clause from being applied at a lower level of joining + * than any OUTER JOIN that should be evaluated before it. + */ + if (outerjoinrelids) + { + /* Safety check: parser should have enforced this to start with */ + if (! is_subseti(relids, outerjoinrelids)) + elog(ERROR, "JOIN qualification may not refer to other relations"); + relids = outerjoinrelids; + can_be_equijoin = false; + } + else + { + Relids newrelids = relids; + List *relid; + + /* We rely on LispUnioni to be nondestructive of its input lists... */ + can_be_equijoin = true; + foreach(relid, relids) + { + RelOptInfo *rel = get_base_rel(root, lfirsti(relid)); + + if (rel->outerjoinset) + { + newrelids = LispUnioni(newrelids, rel->outerjoinset); + /* + * Because application of the qual will be delayed by outer + * join, we mustn't assume its vars are equal everywhere. + */ + can_be_equijoin = false; + } + } + relids = newrelids; + } + if (length(relids) == 1) { @@ -199,7 +418,8 @@ add_restrict_and_join_to_rel(Query *root, Node *clause) * that "a.x = a.y AND a.x = b.z AND a.y = c.q" allows us to * consider z and q equal after their rels are joined. */ - check_mergejoinable(restrictinfo); + if (can_be_equijoin) + check_mergejoinable(restrictinfo); } else if (relids != NIL) { @@ -209,11 +429,11 @@ add_restrict_and_join_to_rel(Query *root, Node *clause) * the relid list. Set additional RestrictInfo fields for * joining. * - * We need the merge info whether or not mergejoin is enabled (for - * constructing equijoined-var lists), but we don't bother setting - * hash info if hashjoin is disabled. + * We don't bother setting the merge/hashjoin info if we're not + * going to need it. */ - check_mergejoinable(restrictinfo); + if (enable_mergejoin || can_be_equijoin) + check_mergejoinable(restrictinfo); if (enable_hashjoin) check_hashjoinable(restrictinfo); @@ -223,7 +443,7 @@ add_restrict_and_join_to_rel(Query *root, Node *clause) add_join_info_to_rels(root, restrictinfo, relids); /* - * Add vars used in the join clause to targetlists of member + * Add vars used in the join clause to targetlists of their * relations, so that they will be emitted by the plan nodes that * scan those relations (else they won't be available at the join * node!). @@ -241,12 +461,14 @@ add_restrict_and_join_to_rel(Query *root, Node *clause) } /* - * If the clause has a mergejoinable operator, then the two sides + * If the clause has a mergejoinable operator, and is not an outer-join + * qualification nor bubbled up due to an outer join, then the two sides * represent equivalent PathKeyItems for path keys: any path that is - * sorted by one side will also be sorted by the other (after joining, - * that is). Record the key equivalence for future use. + * sorted by one side will also be sorted by the other (as soon as the + * two rels are joined, that is). Record the key equivalence for future + * use. */ - if (restrictinfo->mergejoinoperator != InvalidOid) + if (can_be_equijoin && restrictinfo->mergejoinoperator != InvalidOid) add_equijoined_keys(root, restrictinfo); } @@ -392,7 +614,8 @@ process_implied_equality(Query *root, Node *item1, Node *item2, BOOLOID); /* operator result type */ clause->args = lcons(item1, lcons(item2, NIL)); - add_restrict_and_join_to_rel(root, (Node *) clause); + add_restrict_and_join_to_rel(root, (Node *) clause, + false, NIL); } diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c index abb468aa8d1..1fcbe64e888 100644 --- a/src/backend/optimizer/plan/planmain.c +++ b/src/backend/optimizer/plan/planmain.c @@ -14,7 +14,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planmain.c,v 1.58 2000/08/13 02:50:07 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planmain.c,v 1.59 2000/09/12 21:06:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -28,6 +28,7 @@ #include "optimizer/paths.h" #include "optimizer/planmain.h" #include "optimizer/tlist.h" +#include "parser/parsetree.h" #include "utils/memutils.h" @@ -41,11 +42,8 @@ static Plan *subplanner(Query *root, List *flat_tlist, List *qual, * not any fancier features. * * tlist is the target list the query should produce (NOT root->targetList!) - * qual is the qualification of the query (likewise!) * tuple_fraction is the fraction of tuples we expect will be retrieved * - * qual must already have been converted to implicit-AND form. - * * Note: the Query node now also includes a query_pathkeys field, which * is both an input and an output of query_planner(). The input value * signals query_planner that the indicated sort order is wanted in the @@ -75,9 +73,9 @@ static Plan *subplanner(Query *root, List *flat_tlist, List *qual, Plan * query_planner(Query *root, List *tlist, - List *qual, double tuple_fraction) { + List *normal_qual; List *noncachable_qual; List *constant_qual; List *var_only_tlist; @@ -96,7 +94,7 @@ query_planner(Query *root, root->query_pathkeys = NIL; /* signal unordered result */ /* Make childless Result node to evaluate given tlist. */ - return (Plan *) make_result(tlist, (Node *) qual, (Plan *) NULL); + return (Plan *) make_result(tlist, root->qual, (Plan *) NULL); } /* @@ -111,10 +109,12 @@ query_planner(Query *root, * noncachable functions but no vars, such as "WHERE random() < 0.5". * These cannot be treated as normal restriction or join quals, but * they're not constants either. Instead, attach them to the qpqual - * of the top-level plan, so that they get evaluated once per potential + * of the top plan, so that they get evaluated once per potential * output tuple. */ - qual = pull_constant_clauses(qual, &noncachable_qual, &constant_qual); + normal_qual = pull_constant_clauses((List *) root->qual, + &noncachable_qual, + &constant_qual); /* * Create a target list that consists solely of (resdom var) target @@ -132,7 +132,7 @@ query_planner(Query *root, /* * Choose the best access path and build a plan for it. */ - subplan = subplanner(root, var_only_tlist, qual, tuple_fraction); + subplan = subplanner(root, var_only_tlist, normal_qual, tuple_fraction); /* * Handle the noncachable quals. @@ -188,6 +188,8 @@ subplanner(Query *root, List *qual, double tuple_fraction) { + List *joined_rels; + List *brel; RelOptInfo *final_rel; Plan *resultplan; MemoryContext mycontext; @@ -196,7 +198,7 @@ subplanner(Query *root, Path *presortedpath; /* - * Initialize the targetlist and qualification, adding entries to + * Examine the targetlist and qualifications, adding entries to * base_rel_list as relation references are found (e.g., in the * qualification, the targetlist, etc.). Restrict and join clauses * are added to appropriate lists belonging to the mentioned @@ -207,13 +209,29 @@ subplanner(Query *root, root->join_rel_list = NIL; root->equi_key_list = NIL; - make_var_only_tlist(root, flat_tlist); + build_base_rel_tlists(root, flat_tlist); + (void) add_join_quals_to_rels(root, (Node *) root->jointree); + /* this must happen after add_join_quals_to_rels: */ add_restrict_and_join_to_rels(root, qual); /* - * Make sure we have RelOptInfo nodes for all relations used. + * Make sure we have RelOptInfo nodes for all relations to be joined. + */ + joined_rels = add_missing_rels_to_query(root, (Node *) root->jointree); + + /* + * Check that the join tree includes all the base relations used in + * the query --- otherwise, the parser or rewriter messed up. */ - add_missing_rels_to_query(root); + foreach(brel, root->base_rel_list) + { + RelOptInfo *baserel = (RelOptInfo *) lfirst(brel); + int relid = lfirsti(baserel->relids); + + if (! ptrMember(baserel, joined_rels)) + elog(ERROR, "Internal error: no jointree entry for rel %s (%d)", + rt_fetch(relid, root->rtable)->eref->relname, relid); + } /* * Use the completed lists of equijoined keys to deduce any implied @@ -258,12 +276,11 @@ subplanner(Query *root, * We expect to end up here for a trivial INSERT ... VALUES query * (which will have a target relation, so it gets past * query_planner's check for empty range table; but the target rel - * is unreferenced and not marked inJoinSet, so we find there is - * nothing to join). + * is not in the join tree, so we find there is nothing to join). * * It's also possible to get here if the query was rewritten by the - * rule processor (creating rangetable entries not marked - * inJoinSet) but the rules either did nothing or were simplified + * rule processor (creating dummy rangetable entries that are not in + * the join tree) but the rules either did nothing or were simplified * to nothing by constant-expression folding. So, don't complain. */ root->query_pathkeys = NIL; /* signal unordered result */ diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index 4be9b05bb90..7ffbb4666d9 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planner.c,v 1.88 2000/08/21 20:55:29 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planner.c,v 1.89 2000/09/12 21:06:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -29,6 +29,7 @@ #include "utils/lsyscache.h" +static void preprocess_join_conditions(Query *parse, Node *jtnode); static List *make_subplanTargetList(Query *parse, List *tlist, AttrNumber **groupColIdx); static Plan *make_groupplan(List *group_tlist, bool tuplePerGroup, @@ -163,6 +164,7 @@ subquery_planner(Query *parse, double tuple_fraction) * canonicalize_qual? */ parse->qual = (Node *) canonicalize_qual((Expr *) parse->qual, true); + #ifdef OPTIMIZER_DEBUG printf("After canonicalize_qual()\n"); pprint(parse->qual); @@ -211,6 +213,9 @@ subquery_planner(Query *parse, double tuple_fraction) parse->havingQual = SS_replace_correlation_vars(parse->havingQual); } + /* Do all the above for each qual condition (ON clause) in the join tree */ + preprocess_join_conditions(parse, (Node *) parse->jointree); + /* Do the main planning (potentially recursive) */ return union_planner(parse, tuple_fraction); @@ -224,6 +229,58 @@ subquery_planner(Query *parse, double tuple_fraction) */ } +/* + * preprocess_join_conditions + * Recursively scan the query's jointree and do subquery_planner's + * qual preprocessing work on each ON condition found therein. + */ +static void +preprocess_join_conditions(Query *parse, Node *jtnode) +{ + if (jtnode == NULL) + return; + if (IsA(jtnode, List)) + { + List *l; + + foreach(l, (List *) jtnode) + preprocess_join_conditions(parse, lfirst(l)); + } + else if (IsA(jtnode, RangeTblRef)) + { + /* nothing to do here */ + } + else if (IsA(jtnode, JoinExpr)) + { + JoinExpr *j = (JoinExpr *) jtnode; + + preprocess_join_conditions(parse, j->larg); + preprocess_join_conditions(parse, j->rarg); + + /* Simplify constant expressions */ + j->quals = eval_const_expressions(j->quals); + + /* Canonicalize the qual, and convert it to implicit-AND format */ + j->quals = (Node *) canonicalize_qual((Expr *) j->quals, true); + + /* Expand SubLinks to SubPlans */ + if (parse->hasSubLinks) + { + j->quals = SS_process_sublinks(j->quals); + /* + * ON conditions, like WHERE clauses, are evaluated pre-GROUP; + * so we allow ungrouped vars in them. + */ + } + + /* Replace uplevel vars with Param nodes */ + if (PlannerQueryLevel > 1) + j->quals = SS_replace_correlation_vars(j->quals); + } + else + elog(ERROR, "preprocess_join_conditions: unexpected node type %d", + nodeTag(jtnode)); +} /*-------------------- * union_planner @@ -542,7 +599,6 @@ union_planner(Query *parse, /* Generate the (sub) plan */ result_plan = query_planner(parse, sub_tlist, - (List *) parse->qual, tuple_fraction); /* diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c index d8a09c017dd..d30636c185e 100644 --- a/src/backend/optimizer/plan/setrefs.c +++ b/src/backend/optimizer/plan/setrefs.c @@ -9,7 +9,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/setrefs.c,v 1.64 2000/06/04 20:50:50 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/setrefs.c,v 1.65 2000/09/12 21:06:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -106,11 +106,13 @@ set_plan_references(Plan *plan) set_join_references((Join *) plan); fix_expr_references(plan, (Node *) plan->targetlist); fix_expr_references(plan, (Node *) plan->qual); + fix_expr_references(plan, (Node *) ((Join *) plan)->joinqual); break; case T_MergeJoin: set_join_references((Join *) plan); fix_expr_references(plan, (Node *) plan->targetlist); fix_expr_references(plan, (Node *) plan->qual); + fix_expr_references(plan, (Node *) ((Join *) plan)->joinqual); fix_expr_references(plan, (Node *) ((MergeJoin *) plan)->mergeclauses); break; @@ -118,6 +120,7 @@ set_plan_references(Plan *plan) set_join_references((Join *) plan); fix_expr_references(plan, (Node *) plan->targetlist); fix_expr_references(plan, (Node *) plan->qual); + fix_expr_references(plan, (Node *) ((Join *) plan)->joinqual); fix_expr_references(plan, (Node *) ((HashJoin *) plan)->hashclauses); break; @@ -236,15 +239,15 @@ fix_expr_references(Plan *plan, Node *node) static void set_join_references(Join *join) { - Plan *outer = join->lefttree; - Plan *inner = join->righttree; + Plan *outer = join->plan.lefttree; + Plan *inner = join->plan.righttree; List *outer_tlist = ((outer == NULL) ? NIL : outer->targetlist); List *inner_tlist = ((inner == NULL) ? NIL : inner->targetlist); - join->targetlist = join_references(join->targetlist, - outer_tlist, - inner_tlist, - (Index) 0); + join->plan.targetlist = join_references(join->plan.targetlist, + outer_tlist, + inner_tlist, + (Index) 0); } /* diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c index b0772b83f1c..24a0aae55cd 100644 --- a/src/backend/optimizer/plan/subselect.c +++ b/src/backend/optimizer/plan/subselect.c @@ -7,7 +7,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/subselect.c,v 1.40 2000/08/06 04:13:22 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/subselect.c,v 1.41 2000/09/12 21:06:54 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -649,12 +649,21 @@ SS_finalize_plan(Plan *plan) */ break; + case T_NestLoop: + finalize_primnode((Node *) ((Join *) plan)->joinqual, + &results); + break; + case T_MergeJoin: + finalize_primnode((Node *) ((Join *) plan)->joinqual, + &results); finalize_primnode((Node *) ((MergeJoin *) plan)->mergeclauses, &results); break; case T_HashJoin: + finalize_primnode((Node *) ((Join *) plan)->joinqual, + &results); finalize_primnode((Node *) ((HashJoin *) plan)->hashclauses, &results); break; @@ -671,7 +680,6 @@ SS_finalize_plan(Plan *plan) case T_Agg: case T_SeqScan: - case T_NestLoop: case T_Material: case T_Sort: case T_Unique: |