diff options
Diffstat (limited to 'src/backend/optimizer')
-rw-r--r-- | src/backend/optimizer/plan/setrefs.c | 39 | ||||
-rw-r--r-- | src/backend/optimizer/plan/subselect.c | 203 | ||||
-rw-r--r-- | src/backend/optimizer/util/clauses.c | 66 | ||||
-rw-r--r-- | src/backend/optimizer/util/var.c | 10 |
4 files changed, 234 insertions, 84 deletions
diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c index 5081f9c3401..c76d67b93e5 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.86 2002/12/14 00:17:55 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/setrefs.c,v 1.87 2003/01/10 21:08:11 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -42,6 +42,7 @@ typedef struct static void fix_expr_references(Plan *plan, Node *node); static bool fix_expr_references_walker(Node *node, void *context); +static void mark_qual_expressions(List *quals); static void set_join_references(Join *join, List *rtable); static void set_uppernode_references(Plan *plan, Index subvarno); static Node *join_references_mutator(Node *node, @@ -88,10 +89,12 @@ set_plan_references(Plan *plan, List *rtable) case T_SeqScan: fix_expr_references(plan, (Node *) plan->targetlist); fix_expr_references(plan, (Node *) plan->qual); + mark_qual_expressions(plan->qual); break; case T_IndexScan: fix_expr_references(plan, (Node *) plan->targetlist); fix_expr_references(plan, (Node *) plan->qual); + mark_qual_expressions(plan->qual); fix_expr_references(plan, (Node *) ((IndexScan *) plan)->indxqual); fix_expr_references(plan, @@ -100,6 +103,7 @@ set_plan_references(Plan *plan, List *rtable) case T_TidScan: fix_expr_references(plan, (Node *) plan->targetlist); fix_expr_references(plan, (Node *) plan->qual); + mark_qual_expressions(plan->qual); fix_expr_references(plan, (Node *) ((TidScan *) plan)->tideval); break; @@ -114,6 +118,7 @@ set_plan_references(Plan *plan, List *rtable) */ fix_expr_references(plan, (Node *) plan->targetlist); fix_expr_references(plan, (Node *) plan->qual); + mark_qual_expressions(plan->qual); /* Recurse into subplan too */ rte = rt_fetch(((SubqueryScan *) plan)->scan.scanrelid, @@ -129,6 +134,7 @@ set_plan_references(Plan *plan, List *rtable) fix_expr_references(plan, (Node *) plan->targetlist); fix_expr_references(plan, (Node *) plan->qual); + mark_qual_expressions(plan->qual); rte = rt_fetch(((FunctionScan *) plan)->scan.scanrelid, rtable); Assert(rte->rtekind == RTE_FUNCTION); @@ -139,13 +145,17 @@ set_plan_references(Plan *plan, List *rtable) set_join_references((Join *) plan, rtable); fix_expr_references(plan, (Node *) plan->targetlist); fix_expr_references(plan, (Node *) plan->qual); + mark_qual_expressions(plan->qual); fix_expr_references(plan, (Node *) ((Join *) plan)->joinqual); + mark_qual_expressions(((Join *) plan)->joinqual); break; case T_MergeJoin: set_join_references((Join *) plan, rtable); fix_expr_references(plan, (Node *) plan->targetlist); fix_expr_references(plan, (Node *) plan->qual); + mark_qual_expressions(plan->qual); fix_expr_references(plan, (Node *) ((Join *) plan)->joinqual); + mark_qual_expressions(((Join *) plan)->joinqual); fix_expr_references(plan, (Node *) ((MergeJoin *) plan)->mergeclauses); break; @@ -153,7 +163,9 @@ set_plan_references(Plan *plan, List *rtable) set_join_references((Join *) plan, rtable); fix_expr_references(plan, (Node *) plan->targetlist); fix_expr_references(plan, (Node *) plan->qual); + mark_qual_expressions(plan->qual); fix_expr_references(plan, (Node *) ((Join *) plan)->joinqual); + mark_qual_expressions(((Join *) plan)->joinqual); fix_expr_references(plan, (Node *) ((HashJoin *) plan)->hashclauses); break; @@ -180,6 +192,7 @@ set_plan_references(Plan *plan, List *rtable) set_uppernode_references(plan, (Index) 0); fix_expr_references(plan, (Node *) plan->targetlist); fix_expr_references(plan, (Node *) plan->qual); + mark_qual_expressions(plan->qual); break; case T_Result: @@ -193,7 +206,9 @@ set_plan_references(Plan *plan, List *rtable) set_uppernode_references(plan, (Index) OUTER); fix_expr_references(plan, (Node *) plan->targetlist); fix_expr_references(plan, (Node *) plan->qual); + mark_qual_expressions(plan->qual); fix_expr_references(plan, ((Result *) plan)->resconstantqual); + mark_qual_expressions((List *) ((Result *) plan)->resconstantqual); break; case T_Append: @@ -269,6 +284,28 @@ fix_expr_references_walker(Node *node, void *context) } /* + * mark_qual_expressions + * Do final cleanup on qualifier expressions (not targetlists!) + * + * SubPlans appearing at the top level of a qual expression are marked + * to indicate that they need not distinguish UNKNOWN (null) from FALSE + * results; this can save processing time in some cases. + */ +static void +mark_qual_expressions(List *quals) +{ + List *qual; + + foreach(qual, quals) + { + Node *node = lfirst(qual); + + if (IsA(node, SubPlan)) + ((SubPlan *) node)->unknownEqFalse = true; + } +} + +/* * set_join_references * Modifies the target list of a join node to reference its subplans, * by setting the varnos to OUTER or INNER and setting attno values to the diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c index f8086d9ab6e..460d5c38835 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.62 2003/01/09 20:50:51 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/subselect.c,v 1.63 2003/01/10 21:08:11 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -15,6 +15,7 @@ #include "catalog/pg_operator.h" #include "catalog/pg_type.h" +#include "miscadmin.h" #include "nodes/makefuncs.h" #include "nodes/params.h" #include "optimizer/clauses.h" @@ -25,6 +26,7 @@ #include "parser/parsetree.h" #include "parser/parse_expr.h" #include "parser/parse_oper.h" +#include "utils/lsyscache.h" #include "utils/syscache.h" @@ -59,8 +61,9 @@ typedef struct finalize_primnode_results } finalize_primnode_results; -static List *convert_sublink_opers(List *operlist, List *lefthand, - List *targetlist, List **setParams); +static List *convert_sublink_opers(List *lefthand, List *operOids, + List *targetlist, List **paramIds); +static bool subplan_is_hashable(SubLink *slink, SubPlan *node); static Node *replace_correlation_vars_mutator(Node *node, void *context); static Node *process_sublinks_mutator(Node *node, void *context); static bool finalize_primnode(Node *node, finalize_primnode_results *results); @@ -222,11 +225,14 @@ make_subplan(SubLink *slink, List *lefthand) node->rtable = subquery->rtable; /* - * Fill in other fields of the SubPlan node. + * Initialize other fields of the SubPlan node. */ node->subLinkType = slink->subLinkType; node->useOr = slink->useOr; - node->oper = NIL; + node->exprs = NIL; + node->paramIds = NIL; + node->useHashTable = false; + node->unknownEqFalse = false; node->setParam = NIL; node->parParam = NIL; node->args = NIL; @@ -267,6 +273,7 @@ make_subplan(SubLink *slink, List *lefthand) TargetEntry *te = lfirst(plan->targetlist); Param *prm; + Assert(!te->resdom->resjunk); prm = generate_new_param(te->resdom->restype, te->resdom->restypmod); node->setParam = lappendi(node->setParam, prm->paramid); PlannerInitPlan = lappend(PlannerInitPlan, node); @@ -274,19 +281,25 @@ make_subplan(SubLink *slink, List *lefthand) } else if (node->parParam == NIL && slink->subLinkType == MULTIEXPR_SUBLINK) { - List *oper; - - /* Convert the oper list, but don't put it into the SubPlan node */ - oper = convert_sublink_opers(slink->oper, - lefthand, - plan->targetlist, - &node->setParam); + List *exprs; + + /* Convert the lefthand exprs and oper OIDs into executable exprs */ + exprs = convert_sublink_opers(lefthand, + slink->operOids, + plan->targetlist, + &node->paramIds); + node->setParam = nconc(node->setParam, listCopy(node->paramIds)); PlannerInitPlan = lappend(PlannerInitPlan, node); - if (length(oper) > 1) - result = (Node *) (node->useOr ? make_orclause(oper) : - make_andclause(oper)); + /* + * The executable expressions are returned to become part of the + * outer plan's expression tree; they are not kept in the initplan + * node. + */ + if (length(exprs) > 1) + result = (Node *) (node->useOr ? make_orclause(exprs) : + make_andclause(exprs)); else - result = (Node *) lfirst(oper); + result = (Node *) lfirst(exprs); } else { @@ -296,13 +309,20 @@ make_subplan(SubLink *slink, List *lefthand) * We can't convert subplans of ALL_SUBLINK or ANY_SUBLINK types * to initPlans, even when they are uncorrelated or undirect * correlated, because we need to scan the output of the subplan - * for each outer tuple. However, we have the option to tack a - * MATERIAL node onto the top of an uncorrelated/undirect - * correlated subplan, which lets us do the work of evaluating the - * subplan only once. We do this if the subplan's top plan node - * is anything more complicated than a plain sequential scan, and - * we do it even for seqscan if the qual appears selective enough - * to eliminate many tuples. + * for each outer tuple. But if it's an IN (= ANY) test, we might + * be able to use a hashtable to avoid comparing all the tuples. + */ + if (subplan_is_hashable(slink, node)) + node->useHashTable = true; + /* + * Otherwise, we have the option to tack a MATERIAL node onto the top + * of the subplan, to reduce the cost of reading it repeatedly. This + * is pointless for a direct-correlated subplan, since we'd have to + * recompute its results each time anyway. For uncorrelated/undirect + * correlated subplans, we add MATERIAL if the subplan's top plan node + * is anything more complicated than a plain sequential scan, and we + * do it even for seqscan if the qual appears selective enough to + * eliminate many tuples. * * XXX It's pretty ugly to be inserting a MATERIAL node at this * point. Since subquery_planner has already run SS_finalize_plan @@ -310,7 +330,7 @@ make_subplan(SubLink *slink, List *lefthand) * the MATERIAL node. Possibly this could be fixed by postponing * SS_finalize_plan processing until setrefs.c is run. */ - if (node->parParam == NIL) + else if (node->parParam == NIL) { bool use_material; @@ -365,11 +385,11 @@ make_subplan(SubLink *slink, List *lefthand) } } - /* Convert the SubLink's oper list into executable form */ - node->oper = convert_sublink_opers(slink->oper, - lefthand, - plan->targetlist, - NULL); + /* Convert the lefthand exprs and oper OIDs into executable exprs */ + node->exprs = convert_sublink_opers(lefthand, + slink->operOids, + plan->targetlist, + &node->paramIds); /* * Make node->args from parParam. @@ -398,29 +418,26 @@ make_subplan(SubLink *slink, List *lefthand) } /* - * convert_sublink_opers: convert a SubLink's oper list from the - * parser/rewriter format into the executor's format. + * convert_sublink_opers: given a lefthand-expressions list and a list of + * operator OIDs, build a list of actually executable expressions. The + * righthand sides of the expressions are Params representing the results + * of the sub-select. * - * The oper list is initially a list of OpExpr nodes with NIL args. We - * convert it to a list of actually executable expressions, in which the - * specified operators are applied to corresponding elements of the - * lefthand list and Params representing the results of the subplan. - * - * If setParams is not NULL, the paramids of the Params created are added - * to the *setParams list. + * The paramids of the Params created are returned in the *paramIds list. */ static List * -convert_sublink_opers(List *operlist, List *lefthand, - List *targetlist, List **setParams) +convert_sublink_opers(List *lefthand, List *operOids, + List *targetlist, List **paramIds) { - List *newoper = NIL; - List *leftlist = lefthand; + List *result = NIL; List *lst; - foreach(lst, operlist) + *paramIds = NIL; + + foreach(lst, operOids) { - OpExpr *oper = (OpExpr *) lfirst(lst); - Node *leftop = lfirst(leftlist); + Oid opid = (Oid) lfirsti(lst); + Node *leftop = lfirst(lefthand); TargetEntry *te = lfirst(targetlist); Param *prm; Operator tup; @@ -428,21 +445,21 @@ convert_sublink_opers(List *operlist, List *lefthand, Node *left, *right; + Assert(!te->resdom->resjunk); + /* Make the Param node representing the subplan's result */ prm = generate_new_param(te->resdom->restype, te->resdom->restypmod); - /* Record its ID if needed */ - if (setParams) - *setParams = lappendi(*setParams, prm->paramid); + /* Record its ID */ + *paramIds = lappendi(*paramIds, prm->paramid); - /* Look up the operator to check its declared input types */ - Assert(IsA(oper, OpExpr)); + /* Look up the operator to get its declared input types */ tup = SearchSysCache(OPEROID, - ObjectIdGetDatum(oper->opno), + ObjectIdGetDatum(opid), 0, 0, 0); if (!HeapTupleIsValid(tup)) - elog(ERROR, "cache lookup failed for operator %u", oper->opno); + elog(ERROR, "cache lookup failed for operator %u", opid); opform = (Form_pg_operator) GETSTRUCT(tup); /* @@ -453,20 +470,86 @@ convert_sublink_opers(List *operlist, List *lefthand, */ left = make_operand(leftop, exprType(leftop), opform->oprleft); right = make_operand((Node *) prm, prm->paramtype, opform->oprright); - newoper = lappend(newoper, - make_opclause(oper->opno, - oper->opresulttype, - oper->opretset, - (Expr *) left, - (Expr *) right)); + result = lappend(result, + make_opclause(opid, + opform->oprresult, + false, /* set-result not allowed */ + (Expr *) left, + (Expr *) right)); ReleaseSysCache(tup); - leftlist = lnext(leftlist); + lefthand = lnext(lefthand); targetlist = lnext(targetlist); } - return newoper; + return result; +} + +/* + * subplan_is_hashable: decide whether we can implement a subplan by hashing + * + * Caution: the SubPlan node is not completely filled in yet. We can rely + * on its plan and parParam fields, however. + */ +static bool +subplan_is_hashable(SubLink *slink, SubPlan *node) +{ + double subquery_size; + List *opids; + + /* + * The sublink type must be "= ANY" --- that is, an IN operator. + * (We require the operator name to be unqualified, which may be + * overly paranoid, or may not be.) XXX since we also check that the + * operators are hashable, the test on operator name may be redundant? + */ + if (slink->subLinkType != ANY_SUBLINK) + return false; + if (length(slink->operName) != 1 || + strcmp(strVal(lfirst(slink->operName)), "=") != 0) + return false; + /* + * The subplan must not have any direct correlation vars --- else we'd + * have to recompute its output each time, so that the hashtable wouldn't + * gain anything. + */ + if (node->parParam != NIL) + return false; + /* + * The estimated size of the subquery result must fit in SortMem. + * (XXX what about hashtable overhead?) + */ + subquery_size = node->plan->plan_rows * + (MAXALIGN(node->plan->plan_width) + MAXALIGN(sizeof(HeapTupleData))); + if (subquery_size > SortMem * 1024L) + return false; + /* + * The combining operators must be hashable and strict. (Without + * strictness, behavior in the presence of nulls is too unpredictable. + * We actually must assume even more than plain strictness, see + * nodeSubplan.c for details.) + */ + foreach(opids, slink->operOids) + { + Oid opid = (Oid) lfirsti(opids); + HeapTuple tup; + Form_pg_operator optup; + + tup = SearchSysCache(OPEROID, + ObjectIdGetDatum(opid), + 0, 0, 0); + if (!HeapTupleIsValid(tup)) + elog(ERROR, "cache lookup failed for operator %u", opid); + optup = (Form_pg_operator) GETSTRUCT(tup); + if (!optup->oprcanhash || !func_strict(optup->oprcode)) + { + ReleaseSysCache(tup); + return false; + } + ReleaseSysCache(tup); + } + return true; } /* diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c index 4c87a95c3b1..e38fc46821d 100644 --- a/src/backend/optimizer/util/clauses.c +++ b/src/backend/optimizer/util/clauses.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/clauses.c,v 1.120 2002/12/15 16:17:50 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/util/clauses.c,v 1.121 2003/01/10 21:08:13 tgl Exp $ * * HISTORY * AUTHOR DATE MAJOR EVENT @@ -721,7 +721,7 @@ check_subplans_for_ungrouped_vars_walker(Node *node, * mistakenly think that something like "WHERE random() < 0.5" can be treated * as a constant qualification. * - * XXX we do not examine sublinks/subplans to see if they contain uses of + * XXX we do not examine sub-selects to see if they contain uses of * mutable functions. It's not real clear if that is correct or not... */ bool @@ -759,6 +759,18 @@ contain_mutable_functions_walker(Node *node, void *context) return true; /* else fall through to check args */ } + if (IsA(node, SubLink)) + { + SubLink *sublink = (SubLink *) node; + List *opid; + + foreach(opid, sublink->operOids) + { + if (op_volatile((Oid) lfirsti(opid)) != PROVOLATILE_IMMUTABLE) + return true; + } + /* else fall through to check args */ + } return expression_tree_walker(node, contain_mutable_functions_walker, context); } @@ -776,7 +788,7 @@ contain_mutable_functions_walker(Node *node, void *context) * volatile function) is found. This test prevents invalid conversions * of volatile expressions into indexscan quals. * - * XXX we do not examine sublinks/subplans to see if they contain uses of + * XXX we do not examine sub-selects to see if they contain uses of * volatile functions. It's not real clear if that is correct or not... */ bool @@ -814,6 +826,18 @@ contain_volatile_functions_walker(Node *node, void *context) return true; /* else fall through to check args */ } + if (IsA(node, SubLink)) + { + SubLink *sublink = (SubLink *) node; + List *opid; + + foreach(opid, sublink->operOids) + { + if (op_volatile((Oid) lfirsti(opid)) == PROVOLATILE_VOLATILE) + return true; + } + /* else fall through to check args */ + } return expression_tree_walker(node, contain_volatile_functions_walker, context); } @@ -830,7 +854,7 @@ contain_volatile_functions_walker(Node *node, void *context) * Returns true if any nonstrict construct is found --- ie, anything that * could produce non-NULL output with a NULL input. * - * XXX we do not examine sublinks/subplans to see if they contain uses of + * XXX we do not examine sub-selects to see if they contain uses of * nonstrict functions. It's not real clear if that is correct or not... * for the current usage it does not matter, since inline_function() * rejects cases with sublinks. @@ -887,6 +911,18 @@ contain_nonstrict_functions_walker(Node *node, void *context) return true; if (IsA(node, BooleanTest)) return true; + if (IsA(node, SubLink)) + { + SubLink *sublink = (SubLink *) node; + List *opid; + + foreach(opid, sublink->operOids) + { + if (!op_strict((Oid) lfirsti(opid))) + return true; + } + /* else fall through to check args */ + } return expression_tree_walker(node, contain_nonstrict_functions_walker, context); } @@ -2130,8 +2166,8 @@ substitute_actual_parameters_mutator(Node *node, * walker on all the expression subtrees of the given Query node. * * expression_tree_walker will handle SubPlan nodes by recursing normally - * into the "oper" and "args" lists (which are expressions belonging to the - * outer plan). It will not touch the completed subplan, however. Since + * into the "exprs" and "args" lists (which are expressions belonging to + * the outer plan). It will not touch the completed subplan, however. Since * there is no link to the original Query, it is not possible to recurse into * subselects of an already-planned expression tree. This is OK for current * uses, but may need to be revisited in future. @@ -2224,11 +2260,6 @@ expression_tree_walker(Node *node, { SubLink *sublink = (SubLink *) node; - /* - * We only recurse into the lefthand list (the incomplete - * OpExpr nodes in the oper list are deemed uninteresting, - * perhaps even confusing). - */ if (expression_tree_walker((Node *) sublink->lefthand, walker, context)) return true; @@ -2243,8 +2274,8 @@ expression_tree_walker(Node *node, { SubPlan *subplan = (SubPlan *) node; - /* recurse into the oper list, but not into the Plan */ - if (expression_tree_walker((Node *) subplan->oper, + /* recurse into the exprs list, but not into the Plan */ + if (expression_tree_walker((Node *) subplan->exprs, walker, context)) return true; /* also examine args list */ @@ -2451,7 +2482,7 @@ query_tree_walker(Query *query, * and qualifier clauses during the planning stage. * * expression_tree_mutator will handle a SubPlan node by recursing into - * the "oper" and "args" lists (which belong to the outer plan), but it + * the "exprs" and "args" lists (which belong to the outer plan), but it * will simply copy the link to the inner plan, since that's typically what * expression tree mutators want. A mutator that wants to modify the subplan * can force appropriate behavior by recognizing SubPlan expression nodes @@ -2567,8 +2598,7 @@ expression_tree_mutator(Node *node, case T_SubLink: { /* - * We transform the lefthand side, but not the oper list nor - * the subquery. + * We transform the lefthand side, but not the subquery. */ SubLink *sublink = (SubLink *) node; SubLink *newnode; @@ -2584,10 +2614,10 @@ expression_tree_mutator(Node *node, SubPlan *newnode; FLATCOPY(newnode, subplan, SubPlan); + /* transform exprs list */ + MUTATE(newnode->exprs, subplan->exprs, List *); /* transform args list (params to be passed to subplan) */ MUTATE(newnode->args, subplan->args, List *); - /* transform oper list as well */ - MUTATE(newnode->oper, subplan->oper, List *); /* but not the sub-Plan itself, which is referenced as-is */ return (Node *) newnode; } diff --git a/src/backend/optimizer/util/var.c b/src/backend/optimizer/util/var.c index e4868af11cd..92ff0cd5b4c 100644 --- a/src/backend/optimizer/util/var.c +++ b/src/backend/optimizer/util/var.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/var.c,v 1.42 2002/12/14 00:17:59 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/util/var.c,v 1.43 2003/01/10 21:08:13 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -107,13 +107,13 @@ pull_varnos_walker(Node *node, pull_varnos_context *context) { /* * Already-planned subquery. Examine the args list (parameters to - * be passed to subquery), as well as the "oper" list which is + * be passed to subquery), as well as the exprs list which is * executed by the outer query. But short-circuit recursion into * the subquery itself, which would be a waste of effort. */ SubPlan *subplan = (SubPlan *) node; - if (pull_varnos_walker((Node *) subplan->oper, + if (pull_varnos_walker((Node *) subplan->exprs, context)) return true; if (pull_varnos_walker((Node *) subplan->args, @@ -190,13 +190,13 @@ contain_var_reference_walker(Node *node, { /* * Already-planned subquery. Examine the args list (parameters to - * be passed to subquery), as well as the "oper" list which is + * be passed to subquery), as well as the exprs list which is * executed by the outer query. But short-circuit recursion into * the subquery itself, which would be a waste of effort. */ SubPlan *subplan = (SubPlan *) node; - if (contain_var_reference_walker((Node *) subplan->oper, + if (contain_var_reference_walker((Node *) subplan->exprs, context)) return true; if (contain_var_reference_walker((Node *) subplan->args, |