diff options
Diffstat (limited to 'src/backend/optimizer')
| -rw-r--r-- | src/backend/optimizer/README | 21 | ||||
| -rw-r--r-- | src/backend/optimizer/path/allpaths.c | 191 | ||||
| -rw-r--r-- | src/backend/optimizer/path/pathkeys.c | 6 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/createplan.c | 392 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/planmain.c | 20 | ||||
| -rw-r--r-- | src/backend/optimizer/plan/planner.c | 169 | ||||
| -rw-r--r-- | src/backend/optimizer/prep/prepunion.c | 473 | ||||
| -rw-r--r-- | src/backend/optimizer/util/pathnode.c | 33 | ||||
| -rw-r--r-- | src/backend/optimizer/util/relnode.c | 30 |
9 files changed, 724 insertions, 611 deletions
diff --git a/src/backend/optimizer/README b/src/backend/optimizer/README index f0113dfaf50..e60f1457208 100644 --- a/src/backend/optimizer/README +++ b/src/backend/optimizer/README @@ -4,11 +4,11 @@ Summary These directories take the Query structure returned by the parser, and generate a plan used by the executor. The /plan directory generates the actual output plan, the /path code generates all possible ways to join the -tables, and /prep handles special cases like inheritance. /util is utility -stuff. /geqo is the separate "genetic optimization" planner --- it does -a semi-random search through the join tree space, rather than exhaustively -considering all possible join trees. (But each join considered by /geqo -is given to /path to create paths for, so we consider all possible +tables, and /prep handles various preprocessing steps for special cases. +/util is utility stuff. /geqo is the separate "genetic optimization" planner +--- it does a semi-random search through the join tree space, rather than +exhaustively considering all possible join trees. (But each join considered +by /geqo is given to /path to create paths for, so we consider all possible implementation paths for each specific join pair even in GEQO mode.) @@ -210,10 +210,10 @@ planner() thereby reducing the accuracy of selectivity estimates. process sublinks convert Vars of outer query levels into Params ---union_planner() - handle unions and inheritance by mutual recursion with prepunion.c routines - preprocess target list - handle GROUP BY, HAVING, aggregates, ORDER BY, DISTINCT +--grouping_planner() + preprocess target list for non-SELECT queries + handle UNION/INTERSECT/EXCEPT, GROUP BY, HAVING, aggregates, + ORDER BY, DISTINCT, LIMIT --query_planner() pull out constant quals, which can be used to gate execution of the whole plan (if any are found, we make a top-level Result node @@ -239,11 +239,12 @@ planner() Loop back if this wasn't the top join level. Back at query_planner: put back constant quals and non-simplified target list - Back at union_planner: + Back at grouping_planner: do grouping(GROUP) do aggregates make unique(DISTINCT) make sort(ORDER BY) + make limit(LIMIT/OFFSET) Optimizer Data Structures diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 7e017a746f1..12fc576612f 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.66 2000/10/05 19:11:28 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/allpaths.c,v 1.67 2000/11/12 00:36:58 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -21,6 +21,7 @@ #include "optimizer/paths.h" #include "optimizer/plancat.h" #include "optimizer/planner.h" +#include "optimizer/prep.h" #include "parser/parsetree.h" @@ -28,7 +29,12 @@ bool enable_geqo = true; int geqo_rels = DEFAULT_GEQO_RELS; -static void set_base_rel_pathlist(Query *root); +static void set_base_rel_pathlists(Query *root); +static void set_plain_rel_pathlist(Query *root, RelOptInfo *rel, + RangeTblEntry *rte); +static void set_inherited_rel_pathlist(Query *root, RelOptInfo *rel, + RangeTblEntry *rte, + List *inheritlist); static RelOptInfo *make_one_rel_by_joins(Query *root, int levels_needed, List *initial_rels); @@ -51,7 +57,7 @@ make_one_rel(Query *root) /* * Generate access paths for the base rels. */ - set_base_rel_pathlist(root); + set_base_rel_pathlists(root); /* * Generate access paths for the entire join tree. @@ -69,23 +75,26 @@ make_one_rel(Query *root) } /* - * set_base_rel_pathlist + * set_base_rel_pathlists * Finds all paths available for scanning each base-relation entry. * Sequential scan and any available indices are considered. * Each useful path is attached to its relation's 'pathlist' field. */ static void -set_base_rel_pathlist(Query *root) +set_base_rel_pathlists(Query *root) { List *rellist; foreach(rellist, root->base_rel_list) { RelOptInfo *rel = (RelOptInfo *) lfirst(rellist); + Index rti; RangeTblEntry *rte; + List *inheritlist; Assert(length(rel->relids) == 1); /* better be base rel */ - rte = rt_fetch(lfirsti(rel->relids), root->rtable); + rti = lfirsti(rel->relids); + rte = rt_fetch(rti, root->rtable); if (rel->issubquery) { @@ -109,47 +118,163 @@ set_base_rel_pathlist(Query *root) /* Generate appropriate path */ add_path(rel, create_subqueryscan_path(rel)); + + /* Select cheapest path (pretty easy in this case...) */ + set_cheapest(rel); + } + else if ((inheritlist = expand_inherted_rtentry(root, rti)) != NIL) + { + /* Relation is root of an inheritance tree, process specially */ + set_inherited_rel_pathlist(root, rel, rte, inheritlist); } else { /* Plain relation */ - List *indices = find_secondary_indexes(rte->relid); + set_plain_rel_pathlist(root, rel, rte); + } + } +} - /* Mark rel with estimated output rows, width, etc */ - set_baserel_size_estimates(root, rel); +/* + * set_plain_rel_pathlist + * Build access paths for a plain relation (no subquery, no inheritance) + */ +static void +set_plain_rel_pathlist(Query *root, RelOptInfo *rel, RangeTblEntry *rte) +{ + List *indices = find_secondary_indexes(rte->relid); - /* - * 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 - * superior along at least one dimension of cost or sortedness. - */ + /* Mark rel with estimated output rows, width, etc */ + set_baserel_size_estimates(root, rel); - /* Consider sequential scan */ - add_path(rel, create_seqscan_path(rel)); + /* + * 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 + * superior along at least one dimension of cost or sortedness. + */ - /* Consider TID scans */ - create_tidscan_paths(root, rel); + /* Consider sequential scan */ + add_path(rel, create_seqscan_path(rel)); - /* Consider index paths for both simple and OR index clauses */ - create_index_paths(root, rel, indices, - rel->baserestrictinfo, - rel->joininfo); + /* Consider TID scans */ + create_tidscan_paths(root, rel); - /* - * 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); - } + /* Consider index paths for both simple and OR index clauses */ + create_index_paths(root, rel, indices, + 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. + */ + create_or_index_paths(root, rel, rel->baserestrictinfo); + + /* Now find the cheapest of the paths for this rel */ + set_cheapest(rel); +} + +/* + * set_inherited_rel_pathlist + * Build access paths for a inheritance tree rooted at rel + * + * inheritlist is a list of RT indexes of all tables in the inheritance tree, + * including the parent itself. Note we will not come here unless there's + * at least one child in addition to the parent. + */ +static void +set_inherited_rel_pathlist(Query *root, RelOptInfo *rel, RangeTblEntry *rte, + List *inheritlist) +{ + int parentRTindex = lfirsti(rel->relids); + Oid parentOID = rte->relid; + List *subpaths = NIL; + List *il; + + /* + * XXX for now, can't handle inherited expansion of FOR UPDATE; + * can we do better? + */ + if (intMember(parentRTindex, root->rowMarks)) + elog(ERROR, "SELECT FOR UPDATE is not supported for inherit queries"); - /* Now find the cheapest of the paths for this rel */ - set_cheapest(rel); + /* + * Recompute size estimates for whole inheritance tree + */ + rel->rows = 0; + rel->width = 0; + + /* + * Generate access paths for each table in the tree (parent AND children), + * and pick the cheapest path for each table. + */ + foreach(il, inheritlist) + { + int childRTindex = lfirsti(il); + RangeTblEntry *childrte; + Oid childOID; + RelOptInfo *childrel; + + childrte = rt_fetch(childRTindex, root->rtable); + childOID = childrte->relid; + + /* + * Make a RelOptInfo for the child so we can do planning. Do NOT + * attach the RelOptInfo to the query's base_rel_list, however. + * + * NOTE: when childRTindex == parentRTindex, we create a second + * RelOptInfo for the same relation. This RelOptInfo will represent + * the parent table alone, whereas the original RelOptInfo represents + * the union of the inheritance tree members. + */ + childrel = make_base_rel(root, childRTindex); + + /* + * Copy the parent's targetlist and restriction quals to the child, + * with attribute-number adjustment if needed. We don't bother + * to copy the join quals, since we can't do any joining here. + */ + childrel->targetlist = (List *) + adjust_inherited_attrs((Node *) rel->targetlist, + parentRTindex, + parentOID, + childRTindex, + childOID); + childrel->baserestrictinfo = (List *) + adjust_inherited_attrs((Node *) rel->baserestrictinfo, + parentRTindex, + parentOID, + childRTindex, + childOID); + childrel->baserestrictcost = rel->baserestrictcost; + + /* + * Now compute child access paths, and save the cheapest. + */ + set_plain_rel_pathlist(root, childrel, childrte); + + subpaths = lappend(subpaths, childrel->cheapest_total_path); + + /* Also update total size estimates */ + rel->rows += childrel->rows; + if (childrel->width > rel->width) + rel->width = childrel->width; } + + /* + * Finally, build Append path and install it as the only access + * path for the parent rel. + */ + add_path(rel, (Path *) create_append_path(rel, subpaths)); + + /* Select cheapest path (pretty easy in this case...) */ + set_cheapest(rel); } + /* * make_fromexpr_rel * Build access paths for a FromExpr jointree node. diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index 820492bd186..f94d2e4037b 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -11,7 +11,7 @@ * Portions Copyright (c) 1994, Regents of the University of California * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.26 2000/09/29 18:21:32 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.27 2000/11/12 00:36:58 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -566,8 +566,8 @@ build_join_pathkeys(List *outer_pathkeys, * NB: the result is NOT in canonical form, but must be passed through * canonicalize_pathkeys() before it can be used for comparisons or * labeling relation sort orders. (We do things this way because - * union_planner needs to be able to construct requested pathkeys before - * the pathkey equivalence sets have been created for the query.) + * grouping_planner needs to be able to construct requested pathkeys + * before the pathkey equivalence sets have been created for the query.) * * 'sortclauses' is a list of SortClause or GroupClause nodes * 'tlist' is the targetlist to find the referenced tlist entries in diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index a865da61b92..4069ed66e58 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.99 2000/10/26 21:36:09 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.100 2000/11/12 00:36:58 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -32,35 +32,38 @@ #include "utils/syscache.h" -static List *switch_outer(List *clauses); -static Scan *create_scan_node(Query *root, Path *best_path, List *tlist); -static Join *create_join_node(Query *root, JoinPath *best_path, List *tlist); -static SeqScan *create_seqscan_node(Path *best_path, List *tlist, +static Scan *create_scan_plan(Query *root, Path *best_path); +static Join *create_join_plan(Query *root, JoinPath *best_path); +static Append *create_append_plan(Query *root, AppendPath *best_path); +static SeqScan *create_seqscan_plan(Path *best_path, List *tlist, List *scan_clauses); -static IndexScan *create_indexscan_node(Query *root, IndexPath *best_path, +static IndexScan *create_indexscan_plan(Query *root, IndexPath *best_path, List *tlist, List *scan_clauses); -static TidScan *create_tidscan_node(TidPath *best_path, List *tlist, +static TidScan *create_tidscan_plan(TidPath *best_path, List *tlist, List *scan_clauses); -static SubqueryScan *create_subqueryscan_node(Path *best_path, +static SubqueryScan *create_subqueryscan_plan(Path *best_path, List *tlist, List *scan_clauses); -static NestLoop *create_nestloop_node(NestPath *best_path, List *tlist, +static NestLoop *create_nestloop_plan(NestPath *best_path, List *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, + Plan *outer_plan, List *outer_tlist, + Plan *inner_plan, List *inner_tlist); +static MergeJoin *create_mergejoin_plan(MergePath *best_path, List *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, + Plan *outer_plan, List *outer_tlist, + Plan *inner_plan, List *inner_tlist); +static HashJoin *create_hashjoin_plan(HashPath *best_path, List *tlist, List *joinclauses, List *otherclauses, - Plan *outer_node, List *outer_tlist, - Plan *inner_node, List *inner_tlist); + Plan *outer_plan, List *outer_tlist, + Plan *inner_plan, 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 List *switch_outer(List *clauses); +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); static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid, List *indxid, List *indxqual, @@ -83,7 +86,6 @@ static MergeJoin *make_mergejoin(List *tlist, List *mergeclauses, Plan *lefttree, Plan *righttree, JoinType jointype); -static void copy_path_costsize(Plan *dest, Path *src); /* * create_plan @@ -98,13 +100,12 @@ static void copy_path_costsize(Plan *dest, Path *src); * * best_path is the best access path * - * Returns the access plan. + * Returns a Plan tree. */ Plan * create_plan(Query *root, Path *best_path) { - List *tlist = best_path->parent->targetlist; - Plan *plan_node = (Plan *) NULL; + Plan *plan; switch (best_path->pathtype) { @@ -112,18 +113,22 @@ create_plan(Query *root, Path *best_path) case T_SeqScan: case T_TidScan: case T_SubqueryScan: - plan_node = (Plan *) create_scan_node(root, best_path, tlist); + plan = (Plan *) create_scan_plan(root, best_path); break; case T_HashJoin: case T_MergeJoin: case T_NestLoop: - plan_node = (Plan *) create_join_node(root, - (JoinPath *) best_path, - tlist); + plan = (Plan *) create_join_plan(root, + (JoinPath *) best_path); + break; + case T_Append: + plan = (Plan *) create_append_plan(root, + (AppendPath *) best_path); break; default: elog(ERROR, "create_plan: unknown pathtype %d", best_path->pathtype); + plan = NULL; /* keep compiler quiet */ break; } @@ -131,30 +136,29 @@ create_plan(Query *root, Path *best_path) /* sort clauses by cost/(1-selectivity) -- JMH 2/26/92 */ if (XfuncMode != XFUNC_OFF) { - set_qpqual((Plan) plan_node, - lisp_qsort(get_qpqual((Plan) plan_node), + set_qpqual((Plan) plan, + lisp_qsort(get_qpqual((Plan) plan), xfunc_clause_compare)); if (XfuncMode != XFUNC_NOR) /* sort the disjuncts within each clause by cost -- JMH 3/4/92 */ - xfunc_disjunct_sort(plan_node->qpqual); + xfunc_disjunct_sort(plan->qpqual); } #endif - return plan_node; + return plan; } /* - * create_scan_node - * Create a scan path for the parent relation of 'best_path'. + * create_scan_plan + * Create a scan plan for the parent relation of 'best_path'. * - * tlist is the targetlist for the base relation scanned by 'best_path' - * - * Returns the scan node. + * Returns a Plan node. */ static Scan * -create_scan_node(Query *root, Path *best_path, List *tlist) +create_scan_plan(Query *root, Path *best_path) { - Scan *node = NULL; + Scan *plan; + List *tlist = best_path->parent->targetlist; List *scan_clauses; /* @@ -166,65 +170,64 @@ create_scan_node(Query *root, Path *best_path, List *tlist) switch (best_path->pathtype) { case T_SeqScan: - node = (Scan *) create_seqscan_node(best_path, + plan = (Scan *) create_seqscan_plan(best_path, tlist, scan_clauses); break; case T_IndexScan: - node = (Scan *) create_indexscan_node(root, + plan = (Scan *) create_indexscan_plan(root, (IndexPath *) best_path, tlist, scan_clauses); break; case T_TidScan: - node = (Scan *) create_tidscan_node((TidPath *) best_path, + plan = (Scan *) create_tidscan_plan((TidPath *) best_path, tlist, scan_clauses); break; case T_SubqueryScan: - node = (Scan *) create_subqueryscan_node(best_path, + plan = (Scan *) create_subqueryscan_plan(best_path, tlist, scan_clauses); break; default: - elog(ERROR, "create_scan_node: unknown node type: %d", + elog(ERROR, "create_scan_plan: unknown node type: %d", best_path->pathtype); + plan = NULL; /* keep compiler quiet */ break; } - return node; + return plan; } /* - * create_join_node - * Create a join path for 'best_path' and(recursively) paths for its + * create_join_plan + * Create a join plan for 'best_path' and (recursively) plans for its * inner and outer paths. * - * 'tlist' is the targetlist for the join relation corresponding to - * 'best_path' - * - * Returns the join node. + * Returns a Plan node. */ static Join * -create_join_node(Query *root, JoinPath *best_path, List *tlist) +create_join_plan(Query *root, JoinPath *best_path) { - Plan *outer_node; + List *join_tlist = best_path->path.parent->targetlist; + Plan *outer_plan; List *outer_tlist; - Plan *inner_node; + Plan *inner_plan; List *inner_tlist; List *joinclauses; List *otherclauses; - Join *retval = NULL; + Join *plan; - outer_node = create_plan(root, best_path->outerjoinpath); - outer_tlist = outer_node->targetlist; + outer_plan = create_plan(root, best_path->outerjoinpath); + outer_tlist = outer_plan->targetlist; - inner_node = create_plan(root, best_path->innerjoinpath); - inner_tlist = inner_node->targetlist; + inner_plan = create_plan(root, best_path->innerjoinpath); + inner_tlist = inner_plan->targetlist; if (IS_OUTER_JOIN(best_path->jointype)) { @@ -241,38 +244,40 @@ create_join_node(Query *root, JoinPath *best_path, List *tlist) switch (best_path->path.pathtype) { case T_MergeJoin: - retval = (Join *) create_mergejoin_node((MergePath *) best_path, - tlist, - joinclauses, - otherclauses, - outer_node, - outer_tlist, - inner_node, - inner_tlist); + plan = (Join *) create_mergejoin_plan((MergePath *) best_path, + join_tlist, + joinclauses, + otherclauses, + outer_plan, + outer_tlist, + inner_plan, + inner_tlist); break; case T_HashJoin: - retval = (Join *) create_hashjoin_node((HashPath *) best_path, - tlist, - joinclauses, - otherclauses, - outer_node, - outer_tlist, - inner_node, - inner_tlist); + plan = (Join *) create_hashjoin_plan((HashPath *) best_path, + join_tlist, + joinclauses, + otherclauses, + outer_plan, + outer_tlist, + inner_plan, + inner_tlist); break; case T_NestLoop: - retval = (Join *) create_nestloop_node((NestPath *) best_path, - tlist, - joinclauses, - otherclauses, - outer_node, - outer_tlist, - inner_node, - inner_tlist); + plan = (Join *) create_nestloop_plan((NestPath *) best_path, + join_tlist, + joinclauses, + otherclauses, + outer_plan, + outer_tlist, + inner_plan, + inner_tlist); break; default: - elog(ERROR, "create_join_node: unknown node type: %d", + elog(ERROR, "create_join_plan: unknown node type: %d", best_path->path.pathtype); + plan = NULL; /* keep compiler quiet */ + break; } #ifdef NOT_USED @@ -283,14 +288,42 @@ create_join_node(Query *root, JoinPath *best_path, List *tlist) * JMH, 6/15/92 */ if (get_loc_restrictinfo(best_path) != NIL) - set_qpqual((Plan) retval, - nconc(get_qpqual((Plan) retval), + set_qpqual((Plan) plan, + nconc(get_qpqual((Plan) plan), get_actual_clauses(get_loc_restrictinfo(best_path)))); #endif - return retval; + return plan; } +/* + * create_append_plan + * Create an Append plan for 'best_path' and (recursively) plans + * for its subpaths. + * + * Returns a Plan node. + */ +static Append * +create_append_plan(Query *root, AppendPath *best_path) +{ + Append *plan; + List *tlist = best_path->path.parent->targetlist; + List *subplans = NIL; + List *subpaths; + + foreach(subpaths, best_path->subpaths) + { + Path *subpath = (Path *) lfirst(subpaths); + + subplans = lappend(subplans, create_plan(root, subpath)); + } + + plan = make_append(subplans, false, tlist); + + return plan; +} + + /***************************************************************************** * * BASE-RELATION SCAN METHODS @@ -299,14 +332,14 @@ create_join_node(Query *root, JoinPath *best_path, List *tlist) /* - * create_seqscan_node - * Returns a seqscan node for the base relation scanned by 'best_path' + * create_seqscan_plan + * Returns a seqscan plan for the base relation scanned by 'best_path' * with restriction clauses 'scan_clauses' and targetlist 'tlist'. */ static SeqScan * -create_seqscan_node(Path *best_path, List *tlist, List *scan_clauses) +create_seqscan_plan(Path *best_path, List *tlist, List *scan_clauses) { - SeqScan *scan_node; + SeqScan *scan_plan; Index scan_relid; /* there should be exactly one base rel involved... */ @@ -315,18 +348,18 @@ create_seqscan_node(Path *best_path, List *tlist, List *scan_clauses) scan_relid = (Index) lfirsti(best_path->parent->relids); - scan_node = make_seqscan(tlist, + scan_plan = make_seqscan(tlist, scan_clauses, scan_relid); - copy_path_costsize(&scan_node->plan, best_path); + copy_path_costsize(&scan_plan->plan, best_path); - return scan_node; + return scan_plan; } /* - * create_indexscan_node - * Returns a indexscan node for the base relation scanned by 'best_path' + * create_indexscan_plan + * Returns a indexscan plan for the base relation scanned by 'best_path' * with restriction clauses 'scan_clauses' and targetlist 'tlist'. * * The indexqual of the path contains a sublist of implicitly-ANDed qual @@ -338,7 +371,7 @@ create_seqscan_node(Path *best_path, List *tlist, List *scan_clauses) * scan. */ static IndexScan * -create_indexscan_node(Query *root, +create_indexscan_plan(Query *root, IndexPath *best_path, List *tlist, List *scan_clauses) @@ -348,7 +381,7 @@ create_indexscan_node(Query *root, List *qpqual; List *fixed_indxqual; List *ixid; - IndexScan *scan_node; + IndexScan *scan_plan; bool lossy = false; /* there should be exactly one base rel involved... */ @@ -433,7 +466,7 @@ create_indexscan_node(Query *root, */ fixed_indxqual = fix_indxqual_references(indxqual, best_path); - scan_node = make_indexscan(tlist, + scan_plan = make_indexscan(tlist, qpqual, baserelid, best_path->indexid, @@ -441,22 +474,22 @@ create_indexscan_node(Query *root, indxqual, best_path->indexscandir); - copy_path_costsize(&scan_node->scan.plan, &best_path->path); + copy_path_costsize(&scan_plan->scan.plan, &best_path->path); /* use the indexscan-specific rows estimate, not the parent rel's */ - scan_node->scan.plan.plan_rows = best_path->rows; + scan_plan->scan.plan.plan_rows = best_path->rows; - return scan_node; + return scan_plan; } /* - * create_tidscan_node - * Returns a tidscan node for the base relation scanned by 'best_path' + * create_tidscan_plan + * Returns a tidscan plan for the base relation scanned by 'best_path' * with restriction clauses 'scan_clauses' and targetlist 'tlist'. */ static TidScan * -create_tidscan_node(TidPath *best_path, List *tlist, List *scan_clauses) +create_tidscan_plan(TidPath *best_path, List *tlist, List *scan_clauses) { - TidScan *scan_node; + TidScan *scan_plan; Index scan_relid; /* there should be exactly one base rel involved... */ @@ -465,28 +498,28 @@ create_tidscan_node(TidPath *best_path, List *tlist, List *scan_clauses) scan_relid = (Index) lfirsti(best_path->path.parent->relids); - scan_node = make_tidscan(tlist, + scan_plan = make_tidscan(tlist, scan_clauses, scan_relid, best_path->tideval); if (best_path->unjoined_relids) - scan_node->needRescan = true; + scan_plan->needRescan = true; - copy_path_costsize(&scan_node->scan.plan, &best_path->path); + copy_path_costsize(&scan_plan->scan.plan, &best_path->path); - return scan_node; + return scan_plan; } /* - * create_subqueryscan_node - * Returns a subqueryscan node for the base relation scanned by 'best_path' + * create_subqueryscan_plan + * Returns a subqueryscan plan for the base relation scanned by 'best_path' * with restriction clauses 'scan_clauses' and targetlist 'tlist'. */ static SubqueryScan * -create_subqueryscan_node(Path *best_path, List *tlist, List *scan_clauses) +create_subqueryscan_plan(Path *best_path, List *tlist, List *scan_clauses) { - SubqueryScan *scan_node; + SubqueryScan *scan_plan; Index scan_relid; /* there should be exactly one base rel involved... */ @@ -496,14 +529,12 @@ create_subqueryscan_node(Path *best_path, List *tlist, List *scan_clauses) scan_relid = (Index) lfirsti(best_path->parent->relids); - scan_node = make_subqueryscan(tlist, + scan_plan = make_subqueryscan(tlist, scan_clauses, scan_relid, best_path->parent->subplan); - copy_path_costsize(&scan_node->scan.plan, best_path); - - return scan_node; + return scan_plan; } /***************************************************************************** @@ -528,18 +559,18 @@ create_subqueryscan_node(Path *best_path, List *tlist, List *scan_clauses) *****************************************************************************/ static NestLoop * -create_nestloop_node(NestPath *best_path, +create_nestloop_plan(NestPath *best_path, List *tlist, List *joinclauses, List *otherclauses, - Plan *outer_node, + Plan *outer_plan, List *outer_tlist, - Plan *inner_node, + Plan *inner_plan, List *inner_tlist) { - NestLoop *join_node; + NestLoop *join_plan; - if (IsA(inner_node, IndexScan)) + if (IsA(inner_plan, IndexScan)) { /* @@ -563,7 +594,7 @@ create_nestloop_node(NestPath *best_path, * and therefore has not itself done join_references renumbering * of the vars in its quals. */ - IndexScan *innerscan = (IndexScan *) inner_node; + IndexScan *innerscan = (IndexScan *) inner_plan; List *indxqualorig = innerscan->indxqualorig; /* No work needed if indxqual refers only to its own relation... */ @@ -591,23 +622,23 @@ create_nestloop_node(NestPath *best_path, NIL, innerrel); /* fix the inner qpqual too, if it has join clauses */ - if (NumRelids((Node *) inner_node->qual) > 1) - inner_node->qual = join_references(inner_node->qual, + if (NumRelids((Node *) inner_plan->qual) > 1) + inner_plan->qual = join_references(inner_plan->qual, outer_tlist, NIL, innerrel); } } - else if (IsA(inner_node, TidScan)) + else if (IsA(inner_plan, TidScan)) { - TidScan *innerscan = (TidScan *) inner_node; + TidScan *innerscan = (TidScan *) inner_plan; innerscan->tideval = join_references(innerscan->tideval, outer_tlist, inner_tlist, innerscan->scan.scanrelid); } - else if (IsA_Join(inner_node)) + else if (IsA_Join(inner_plan)) { /* @@ -617,8 +648,8 @@ create_nestloop_node(NestPath *best_path, * join --- how can we estimate whether this is a good thing to * do? */ - inner_node = (Plan *) make_material(inner_tlist, - inner_node); + inner_plan = (Plan *) make_material(inner_tlist, + inner_plan); } /* @@ -633,30 +664,30 @@ create_nestloop_node(NestPath *best_path, inner_tlist, (Index) 0); - join_node = make_nestloop(tlist, + join_plan = make_nestloop(tlist, joinclauses, otherclauses, - outer_node, - inner_node, + outer_plan, + inner_plan, best_path->jointype); - copy_path_costsize(&join_node->join.plan, &best_path->path); + copy_path_costsize(&join_plan->join.plan, &best_path->path); - return join_node; + return join_plan; } static MergeJoin * -create_mergejoin_node(MergePath *best_path, +create_mergejoin_plan(MergePath *best_path, List *tlist, List *joinclauses, List *otherclauses, - Plan *outer_node, + Plan *outer_plan, List *outer_tlist, - Plan *inner_node, + Plan *inner_plan, List *inner_tlist) { List *mergeclauses; - MergeJoin *join_node; + MergeJoin *join_plan; mergeclauses = get_actual_clauses(best_path->path_mergeclauses); @@ -692,15 +723,15 @@ create_mergejoin_node(MergePath *best_path, * necessary. The sort cost was already accounted for in the path. */ if (best_path->outersortkeys) - outer_node = (Plan *) + outer_plan = (Plan *) make_sort_from_pathkeys(outer_tlist, - outer_node, + outer_plan, best_path->outersortkeys); if (best_path->innersortkeys) - inner_node = (Plan *) + inner_plan = (Plan *) make_sort_from_pathkeys(inner_tlist, - inner_node, + inner_plan, best_path->innersortkeys); /* @@ -723,7 +754,7 @@ create_mergejoin_node(MergePath *best_path, * This check must agree with ExecMarkPos/ExecRestrPos in * executor/execAmi.c! */ - switch (nodeTag(inner_node)) + switch (nodeTag(inner_plan)) { case T_SeqScan: case T_IndexScan: @@ -734,40 +765,40 @@ create_mergejoin_node(MergePath *best_path, default: /* Ooops, need to materialize the inner plan */ - inner_node = (Plan *) make_material(inner_tlist, - inner_node); + inner_plan = (Plan *) make_material(inner_tlist, + inner_plan); break; } /* * Now we can build the mergejoin node. */ - join_node = make_mergejoin(tlist, + join_plan = make_mergejoin(tlist, joinclauses, otherclauses, mergeclauses, - outer_node, - inner_node, + outer_plan, + inner_plan, best_path->jpath.jointype); - copy_path_costsize(&join_node->join.plan, &best_path->jpath.path); + copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path); - return join_node; + return join_plan; } static HashJoin * -create_hashjoin_node(HashPath *best_path, +create_hashjoin_plan(HashPath *best_path, List *tlist, List *joinclauses, List *otherclauses, - Plan *outer_node, + Plan *outer_plan, List *outer_tlist, - Plan *inner_node, + Plan *inner_plan, List *inner_tlist) { List *hashclauses; - HashJoin *join_node; - Hash *hash_node; + HashJoin *join_plan; + Hash *hash_plan; Node *innerhashkey; /* @@ -811,18 +842,18 @@ create_hashjoin_node(HashPath *best_path, /* * Build the hash node and hash join node. */ - hash_node = make_hash(inner_tlist, innerhashkey, inner_node); - join_node = make_hashjoin(tlist, + hash_plan = make_hash(inner_tlist, innerhashkey, inner_plan); + join_plan = make_hashjoin(tlist, joinclauses, otherclauses, hashclauses, - outer_node, - (Plan *) hash_node, + outer_plan, + (Plan *) hash_plan, best_path->jpath.jointype); - copy_path_costsize(&join_node->join.plan, &best_path->jpath.path); + copy_path_costsize(&join_plan->join.plan, &best_path->jpath.path); - return join_node; + return join_plan; } @@ -1106,7 +1137,7 @@ copy_path_costsize(Plan *dest, Path *src) * but it helps produce more reasonable-looking EXPLAIN output. * (Some callers alter the info after copying it.) */ -void +static void copy_plan_costsize(Plan *dest, Plan *src) { if (src) @@ -1128,6 +1159,10 @@ copy_plan_costsize(Plan *dest, Plan *src) /***************************************************************************** * + * PLAN NODE BUILDING ROUTINES + * + * Some of these are exported because they are called to build plan nodes + * in contexts where we're not deriving the plan node from a path node. * *****************************************************************************/ @@ -1212,7 +1247,7 @@ make_subqueryscan(List *qptlist, SubqueryScan *node = makeNode(SubqueryScan); Plan *plan = &node->scan.plan; - /* cost should be inserted by caller */ + copy_plan_costsize(plan, subplan); plan->state = (EState *) NULL; plan->targetlist = qptlist; plan->qual = qpqual; @@ -1225,6 +1260,39 @@ make_subqueryscan(List *qptlist, return node; } +Append * +make_append(List *appendplans, bool isTarget, List *tlist) +{ + Append *node = makeNode(Append); + Plan *plan = &node->plan; + List *subnode; + + /* compute costs from subplan costs */ + plan->startup_cost = 0; + plan->total_cost = 0; + plan->plan_rows = 0; + plan->plan_width = 0; + foreach(subnode, appendplans) + { + Plan *subplan = (Plan *) lfirst(subnode); + + if (subnode == appendplans) /* first node? */ + plan->startup_cost = subplan->startup_cost; + plan->total_cost += subplan->total_cost; + plan->plan_rows += subplan->plan_rows; + if (plan->plan_width < subplan->plan_width) + plan->plan_width = subplan->plan_width; + } + plan->state = (EState *) NULL; + plan->targetlist = tlist; + plan->qual = NIL; + plan->lefttree = NULL; + plan->righttree = NULL; + node->appendplans = appendplans; + node->isTarget = isTarget; + + return node; +} static NestLoop * make_nestloop(List *tlist, diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c index a9747b32799..1a923a506ff 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.61 2000/10/05 19:11:29 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planmain.c,v 1.62 2000/11/12 00:36:58 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -65,7 +65,8 @@ static Plan *subplanner(Query *root, List *flat_tlist, * tuple_fraction >= 1: tuple_fraction is the absolute number of tuples * expected to be retrieved (ie, a LIMIT specification) * Note that while this routine and its subroutines treat a negative - * tuple_fraction the same as 0, union_planner has a different interpretation. + * tuple_fraction the same as 0, grouping_planner has a different + * interpretation. * * Returns a query plan. *-------------------- @@ -125,9 +126,16 @@ query_planner(Query *root, subplan = subplanner(root, var_only_tlist, tuple_fraction); /* - * Build a result node to control the plan if we have constant quals. + * Build a result node to control the plan if we have constant quals, + * or if the top-level plan node is one that cannot do expression + * evaluation (it won't be able to evaluate the requested tlist). + * Currently, the only plan node we might see here that falls into + * that category is Append. + * + * XXX future improvement: if the given tlist is flat anyway, we don't + * really need a Result node. */ - if (constant_quals) + if (constant_quals || IsA(subplan, Append)) { /* @@ -325,8 +333,8 @@ subplanner(Query *root, /* * Nothing for it but to sort the cheapest-total-cost path --- but we - * let the caller do that. union_planner has to be able to add a sort - * node anyway, so no need for extra code here. (Furthermore, the + * let the caller do that. grouping_planner has to be able to add a + * sort node anyway, so no need for extra code here. (Furthermore, the * given pathkeys might involve something we can't compute here, such * as an aggregate function...) */ diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index 67089e68d29..7a1151f0c9a 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.95 2000/11/09 02:46:16 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planner.c,v 1.96 2000/11/12 00:36:58 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -43,6 +43,8 @@ static void resolvenew_in_jointree(Node *jtnode, int varno, List *subtlist); static Node *preprocess_jointree(Query *parse, Node *jtnode); static Node *preprocess_expression(Query *parse, Node *expr, int kind); static void preprocess_qual_conditions(Query *parse, Node *jtnode); +static Plan *inheritance_planner(Query *parse, List *inheritlist); +static Plan *grouping_planner(Query *parse, double tuple_fraction); static List *make_subplanTargetList(Query *parse, List *tlist, AttrNumber **groupColIdx); static Plan *make_groupplan(List *group_tlist, bool tuplePerGroup, @@ -65,7 +67,7 @@ planner(Query *parse) /* * The planner can be called recursively (an example is when - * eval_const_expressions tries to simplify an SQL function). + * eval_const_expressions tries to pre-evaluate an SQL function). * So, these global state variables must be saved and restored. * * These vars cannot be moved into the Query structure since their @@ -109,11 +111,14 @@ planner(Query *parse) * * parse is the querytree produced by the parser & rewriter. * tuple_fraction is the fraction of tuples we expect will be retrieved. - * tuple_fraction is interpreted as explained for union_planner, below. + * tuple_fraction is interpreted as explained for grouping_planner, below. * * Basically, this routine does the stuff that should only be done once - * per Query object. It then calls union_planner, which may be called - * recursively on the same Query node in order to handle inheritance. + * per Query object. It then calls grouping_planner. At one time, + * grouping_planner could be invoked recursively on the same Query object; + * that's not currently true, but we keep the separation between the two + * routines anyway, in case we need it again someday. + * * subquery_planner will be called recursively to handle sub-Query nodes * found within the query's expressions and rangetable. * @@ -164,7 +169,7 @@ subquery_planner(Query *parse, double tuple_fraction) } /* - * Do preprocessing on targetlist and quals. + * Do expression preprocessing on targetlist and quals. */ parse->targetList = (List *) preprocess_expression(parse, (Node *) parse->targetList, @@ -176,17 +181,14 @@ subquery_planner(Query *parse, double tuple_fraction) EXPRKIND_HAVING); /* - * Do the main planning (potentially recursive for inheritance) - */ - plan = union_planner(parse, tuple_fraction); - - /* - * XXX should any more of union_planner's activity be moved here? - * - * That would take careful study of the interactions with prepunion.c, - * but I suspect it would pay off in simplicity and avoidance of - * wasted cycles. + * Do the main planning. If we have an inherited target relation, + * that needs special processing, else go straight to grouping_planner. */ + if (parse->resultRelation && + (lst = expand_inherted_rtentry(parse, parse->resultRelation)) != NIL) + plan = inheritance_planner(parse, lst); + else + plan = grouping_planner(parse, tuple_fraction); /* * If any subplans were generated, or if we're inside a subplan, @@ -600,10 +602,65 @@ preprocess_qual_conditions(Query *parse, Node *jtnode) } /*-------------------- - * union_planner - * Invokes the planner on union-type queries (both set operations and - * appends produced by inheritance), recursing if necessary to get them - * all, then processes normal plans. + * inheritance_planner + * Generate a plan in the case where the result relation is an + * inheritance set. + * + * We have to handle this case differently from cases where a source + * relation is an inheritance set. Source inheritance is expanded at + * the bottom of the plan tree (see allpaths.c), but target inheritance + * has to be expanded at the top. The reason is that for UPDATE, each + * target relation needs a different targetlist matching its own column + * set. (This is not so critical for DELETE, but for simplicity we treat + * inherited DELETE the same way.) Fortunately, the UPDATE/DELETE target + * can never be the nullable side of an outer join, so it's OK to generate + * the plan this way. + * + * parse is the querytree produced by the parser & rewriter. + * inheritlist is an integer list of RT indexes for the result relation set. + * + * Returns a query plan. + *-------------------- + */ +static Plan * +inheritance_planner(Query *parse, List *inheritlist) +{ + int parentRTindex = parse->resultRelation; + Oid parentOID = getrelid(parentRTindex, parse->rtable); + List *subplans = NIL; + List *tlist = NIL; + List *l; + + foreach(l, inheritlist) + { + int childRTindex = lfirsti(l); + Oid childOID = getrelid(childRTindex, parse->rtable); + Query *subquery; + Plan *subplan; + + /* Generate modified query with this rel as target */ + subquery = (Query *) adjust_inherited_attrs((Node *) parse, + parentRTindex, parentOID, + childRTindex, childOID); + /* Generate plan */ + subplan = grouping_planner(subquery, 0.0 /* retrieve all tuples */); + subplans = lappend(subplans, subplan); + /* Save preprocessed tlist from first rel for use in Append */ + if (tlist == NIL) + tlist = subplan->targetlist; + } + + /* Save the target-relations list for the executor, too */ + parse->resultRelations = inheritlist; + + return (Plan *) make_append(subplans, true, tlist); +} + +/*-------------------- + * grouping_planner + * Perform planning steps related to grouping, aggregation, etc. + * This primarily means adding top-level processing to the basic + * query plan produced by query_planner. * * parse is the querytree produced by the parser & rewriter. * tuple_fraction is the fraction of tuples we expect will be retrieved @@ -621,18 +678,15 @@ preprocess_qual_conditions(Query *parse, Node *jtnode) * Returns a query plan. *-------------------- */ -Plan * -union_planner(Query *parse, - double tuple_fraction) +static Plan * +grouping_planner(Query *parse, double tuple_fraction) { List *tlist = parse->targetList; - Plan *result_plan = (Plan *) NULL; - AttrNumber *groupColIdx = NULL; - List *current_pathkeys = NIL; + Plan *result_plan; + List *current_pathkeys; List *group_pathkeys; List *sort_pathkeys; - Index rt_index; - List *inheritors; + AttrNumber *groupColIdx = NULL; if (parse->setOperations) { @@ -654,12 +708,13 @@ union_planner(Query *parse, tlist = postprocess_setop_tlist(result_plan->targetlist, tlist); /* - * We leave current_pathkeys NIL indicating we do not know sort + * We set current_pathkeys NIL indicating we do not know sort * order. This is correct when the top set operation is UNION ALL, * since the appended-together results are unsorted even if the * subplans were sorted. For other set operations we could be - * smarter --- future improvement! + * smarter --- room for future improvement! */ + current_pathkeys = NIL; /* * Calculate pathkeys that represent grouping/ordering @@ -670,54 +725,6 @@ union_planner(Query *parse, sort_pathkeys = make_pathkeys_for_sortclauses(parse->sortClause, tlist); } - else if (find_inheritable_rt_entry(parse->rtable, - &rt_index, &inheritors)) - { - List *sub_tlist; - - /* - * Generate appropriate target list for subplan; may be different - * from tlist if grouping or aggregation is needed. - */ - sub_tlist = make_subplanTargetList(parse, tlist, &groupColIdx); - - /* - * Recursively plan the subqueries needed for inheritance - */ - result_plan = plan_inherit_queries(parse, sub_tlist, - rt_index, inheritors); - - /* - * Fix up outer target list. NOTE: unlike the case for - * non-inherited query, we pass the unfixed tlist to subplans, - * which do their own fixing. But we still want to fix the outer - * target list afterwards. I *think* this is correct --- doing the - * fix before recursing is definitely wrong, because - * preprocess_targetlist() will do the wrong thing if invoked - * twice on the same list. Maybe that is a bug? tgl 6/6/99 - */ - tlist = preprocess_targetlist(tlist, - parse->commandType, - parse->resultRelation, - parse->rtable); - - if (parse->rowMarks) - elog(ERROR, "SELECT FOR UPDATE is not supported for inherit queries"); - - /* - * We leave current_pathkeys NIL indicating we do not know sort - * order of the Append-ed results. - */ - - /* - * Calculate pathkeys that represent grouping/ordering - * requirements - */ - group_pathkeys = make_pathkeys_for_sortclauses(parse->groupClause, - tlist); - sort_pathkeys = make_pathkeys_for_sortclauses(parse->sortClause, - tlist); - } else { List *sub_tlist; @@ -938,10 +945,6 @@ union_planner(Query *parse, current_pathkeys = parse->query_pathkeys; } - /* query_planner returns NULL if it thinks plan is bogus */ - if (!result_plan) - elog(ERROR, "union_planner: failed to create plan"); - /* * We couldn't canonicalize group_pathkeys and sort_pathkeys before * running query_planner(), so do it now. @@ -1057,7 +1060,7 @@ union_planner(Query *parse, * make_subplanTargetList * Generate appropriate target list when grouping is required. * - * When union_planner inserts Aggregate and/or Group plan nodes above + * When grouping_planner inserts Aggregate and/or Group plan nodes above * the result of query_planner, we typically want to pass a different * target list to query_planner than the outer plan nodes should have. * This routine generates the correct target list for the subplan. diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c index ea9b902bc5b..ebb09f59393 100644 --- a/src/backend/optimizer/prep/prepunion.c +++ b/src/backend/optimizer/prep/prepunion.c @@ -1,15 +1,20 @@ /*------------------------------------------------------------------------- * * prepunion.c - * Routines to plan set-operation and inheritance queries. The filename - * is a leftover from a time when only UNIONs were handled. + * Routines to plan set-operation queries. The filename is a leftover + * from a time when only UNIONs were implemented. + * + * There is also some code here to support planning of queries that use + * inheritance (SELECT FROM foo*). This no longer has much connection + * to the processing of UNION queries, but it's still here. + * * * Portions Copyright (c) 1996-2000, PostgreSQL, Inc * Portions Copyright (c) 1994, Regents of the University of California * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/prep/prepunion.c,v 1.55 2000/11/09 02:46:17 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/prep/prepunion.c,v 1.56 2000/11/12 00:36:59 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -30,13 +35,19 @@ #include "parser/parsetree.h" #include "utils/lsyscache.h" +/* macros borrowed from expression_tree_mutator */ + +#define FLATCOPY(newnode, node, nodetype) \ + ( (newnode) = makeNode(nodetype), \ + memcpy((newnode), (node), sizeof(nodetype)) ) + typedef struct { - Index rt_index; - int sublevels_up; + Index old_rt_index; + Index new_rt_index; Oid old_relid; Oid new_relid; -} fix_parsetree_attnums_context; +} adjust_inherited_attrs_context; static Plan *recurse_set_operations(Node *setOp, Query *parse, List *colTypes, bool junkOK, @@ -53,14 +64,8 @@ static List *generate_setop_tlist(List *colTypes, int flag, List *input_tlist, List *refnames_tlist); static bool tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK); -static void fix_parsetree_attnums(Index rt_index, Oid old_relid, - Oid new_relid, Query *parsetree); -static bool fix_parsetree_attnums_walker(Node *node, - fix_parsetree_attnums_context *context); -static RangeTblEntry *new_rangetable_entry(Oid new_relid, - RangeTblEntry *old_entry); -static Append *make_append(List *appendplans, Index rt_index, - List *inheritrtable, List *tlist); +static Node *adjust_inherited_attrs_mutator(Node *node, + adjust_inherited_attrs_context *context); /* @@ -69,8 +74,8 @@ static Append *make_append(List *appendplans, Index rt_index, * Plans the queries for a tree of set operations (UNION/INTERSECT/EXCEPT) * * This routine only deals with the setOperations tree of the given query. - * Any top-level ORDER BY requested in parse->sortClause will be added on - * back in union_planner. + * Any top-level ORDER BY requested in parse->sortClause will be added + * when we return to grouping_planner. */ Plan * plan_set_operations(Query *parse) @@ -142,7 +147,6 @@ recurse_set_operations(Node *setOp, Query *parse, NIL, rtr->rtindex, subplan); - copy_plan_costsize(plan, subplan); return plan; } else if (IsA(setOp, SetOperationStmt)) @@ -217,8 +221,7 @@ generate_union_plan(SetOperationStmt *op, Query *parse, */ plan = (Plan *) make_append(planlist, - 0, - NIL, + false, generate_setop_tlist(op->colTypes, -1, false, ((Plan *) lfirst(planlist))->targetlist, refnames_tlist)); @@ -269,8 +272,7 @@ generate_nonunion_plan(SetOperationStmt *op, Query *parse, */ plan = (Plan *) make_append(makeList2(lplan, rplan), - 0, - NIL, + false, generate_setop_tlist(op->colTypes, 0, false, lplan->targetlist, refnames_tlist)); @@ -457,132 +459,6 @@ tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK) /* - * plan_inherit_queries - * Plans the queries for an inheritance tree rooted at a parent relation. - * - * Inputs: - * root = parent parse tree - * tlist = target list for inheritance subqueries (not same as parent's!) - * rt_index = rangetable index for current inheritance item - * inheritors = list of OIDs of the target rel plus all its descendants - * - * Returns an APPEND node that forms the result of performing the given - * query for each member relation of the inheritance group. - * - * If grouping, aggregation, or sorting is specified in the parent plan, - * the subplans should not do any of those steps --- we must do those - * operations just once above the APPEND node. The given tlist has been - * modified appropriately to remove group/aggregate expressions, but the - * Query node still has the relevant fields set. We remove them in the - * copies used for subplans. - * - * NOTE: this can be invoked recursively if more than one inheritance wildcard - * is present. At each level of recursion, the first wildcard remaining in - * the rangetable is expanded. - * - * NOTE: don't bother optimizing this routine for the case that the target - * rel has no children. We won't get here unless find_inheritable_rt_entry - * found at least two members in the inheritance group, so an APPEND is - * certainly necessary. - */ -Plan * -plan_inherit_queries(Query *root, List *tlist, - Index rt_index, List *inheritors) -{ - RangeTblEntry *rt_entry = rt_fetch(rt_index, root->rtable); - List *union_plans = NIL; - List *union_rtentries = NIL; - List *save_tlist = root->targetList; - double tuple_fraction; - List *i; - - /* - * Avoid making copies of the root's tlist, which we aren't going to - * use anyway (we are going to make copies of the passed tlist, - * instead). This is purely a space-saving hack. Note we restore - * the root's tlist before exiting. - */ - root->targetList = NIL; - - /* - * If we are going to need sorting or grouping at the top level, force - * lower-level planners to assume that all tuples will be retrieved. - */ - if (root->distinctClause || root->sortClause || - root->groupClause || root->hasAggs) - tuple_fraction = 0.0; /* will need all tuples from each subplan */ - else - tuple_fraction = -1.0; /* default behavior is OK (I think) */ - - foreach(i, inheritors) - { - Oid relid = lfirsti(i); - - /* - * Make a modifiable copy of the original query, and replace the - * target rangetable entry in it with a new one identifying this - * child table. The new rtentry is marked inh = false --- this - * is essential to prevent infinite recursion when the subquery - * is rescanned by find_inheritable_rt_entry! - */ - Query *new_root = copyObject(root); - RangeTblEntry *new_rt_entry = new_rangetable_entry(relid, - rt_entry); - - new_rt_entry->inh = false; - rt_store(rt_index, new_root->rtable, new_rt_entry); - - /* - * Insert (a modifiable copy of) the desired simplified tlist into - * the subquery - */ - new_root->targetList = copyObject(tlist); - - /* - * Clear the sorting and grouping qualifications in the subquery, - * so that sorting will only be done once after append - */ - new_root->distinctClause = NIL; - new_root->sortClause = NIL; - new_root->groupClause = NIL; - new_root->havingQual = NULL; - new_root->limitOffset = NULL; /* LIMIT's probably unsafe too */ - new_root->limitCount = NULL; - new_root->hasAggs = false; /* shouldn't be any left ... */ - - /* - * Update attribute numbers in case child has different ordering - * of columns than parent (as can happen after ALTER TABLE). - * - * XXX This is a crock, and it doesn't really work. It'd be better - * to fix ALTER TABLE to preserve consistency of attribute - * numbering. - */ - fix_parsetree_attnums(rt_index, - rt_entry->relid, - relid, - new_root); - - /* - * Plan the subquery by recursively calling union_planner(). - * Add plan and child rtentry to lists for APPEND. - */ - union_plans = lappend(union_plans, - union_planner(new_root, tuple_fraction)); - union_rtentries = lappend(union_rtentries, new_rt_entry); - } - - /* Restore root's tlist */ - root->targetList = save_tlist; - - /* Construct the finished Append plan. */ - return (Plan *) make_append(union_plans, - rt_index, - union_rtentries, - ((Plan *) lfirst(union_plans))->targetlist); -} - -/* * find_all_inheritors - * Returns an integer list of relids including the given rel plus * all relations that inherit from it, directly or indirectly. @@ -622,200 +498,181 @@ find_all_inheritors(Oid parentrel) } /* - * find_inheritable_rt_entry - - * Given a rangetable, find the first rangetable entry that represents - * an inheritance set. - * - * If successful, set *rt_index to the index (1..n) of the entry, - * set *inheritors to a list of the relation OIDs of the set, - * and return TRUE. - * - * If there is no entry that requires inheritance processing, - * return FALSE. + * expand_inherted_rtentry + * Check whether a rangetable entry represents an inheritance set. + * If so, add entries for all the child tables to the query's + * rangetable, and return an integer list of RT indexes for the + * whole inheritance set (parent and children). + * If not, return NIL. * - * NOTE: We return the inheritors list so that plan_inherit_queries doesn't - * have to compute it again. + * A childless table is never considered to be an inheritance set; therefore + * the result will never be a one-element list. It'll be either empty + * or have two or more elements. * - * NOTE: We clear the inh flag in any entries that have it set but turn - * out not to have any actual inheritance children. This is an efficiency - * hack to avoid having to repeat the inheritance checks if the list is - * scanned again (as will happen during expansion of any subsequent entry - * that does have inheritance children). Although modifying the input - * rangetable in-place may seem uncool, there's no reason not to do it, - * since any re-examination of the entry would just come to the same - * conclusion that the table has no children. + * NOTE: after this routine executes, the specified RTE will always have + * its inh flag cleared, whether or not there were any children. This + * ensures we won't expand the same RTE twice, which would otherwise occur + * for the case of an inherited UPDATE/DELETE target relation. */ -bool -find_inheritable_rt_entry(List *rangetable, - Index *rt_index, - List **inheritors) +List * +expand_inherted_rtentry(Query *parse, Index rti) { - Index count = 0; - List *temp; - - foreach(temp, rangetable) + RangeTblEntry *rte = rt_fetch(rti, parse->rtable); + Oid parentOID = rte->relid; + List *inhOIDs; + List *inhRTIs; + List *l; + + /* Does RT entry allow inheritance? */ + if (! rte->inh) + return NIL; + Assert(parentOID != InvalidOid && rte->subquery == NULL); + /* Always clear the parent's inh flag, see above comments */ + rte->inh = false; + /* Fast path for common case of childless table */ + if (! has_subclass(parentOID)) + return NIL; + /* Scan for all members of inheritance set */ + inhOIDs = find_all_inheritors(parentOID); + /* + * Check that there's at least one descendant, else treat as + * no-child case. This could happen despite above has_subclass() + * check, if table once had a child but no longer does. + */ + if (lnext(inhOIDs) == NIL) + return NIL; + /* OK, it's an inheritance set; expand it */ + inhRTIs = makeListi1(rti); + foreach(l, inhOIDs) { - RangeTblEntry *rt_entry = (RangeTblEntry *) lfirst(temp); - List *inhs; + Oid childOID = (Oid) lfirsti(l); + RangeTblEntry *childrte; + Index childRTindex; - count++; - /* Ignore non-inheritable RT entries */ - if (! rt_entry->inh) - continue; - /* Fast path for common case of childless table */ - if (! has_subclass(rt_entry->relid)) - { - rt_entry->inh = false; + /* parent will be in the list too, so ignore it */ + if (childOID == parentOID) continue; - } - /* Scan for all members of inheritance set */ - inhs = find_all_inheritors(rt_entry->relid); + /* - * Check that there's at least one descendant, else treat as - * no-child case. This could happen despite above has_subclass() - * check, if table once had a child but no longer does. + * Build an RTE for the child, and attach to query's rangetable list. + * We copy most fields of the parent's RTE, but replace relation + * real name and OID. Note that inh will be false at this point. */ - if (lnext(inhs) == NIL) - { - rt_entry->inh = false; - continue; - } - /* OK, found our boy */ - *rt_index = count; - *inheritors = inhs; - return true; - } + childrte = copyObject(rte); + childrte->relname = get_rel_name(childOID); + childrte->relid = childOID; + parse->rtable = lappend(parse->rtable, childrte); + childRTindex = length(parse->rtable); - return false; -} - -/* - * new_rangetable_entry - - * Replaces the name and relid of 'old_entry' with the values for - * 'new_relid'. - * - * Returns a copy of 'old_entry' with the parameters substituted. - */ -static RangeTblEntry * -new_rangetable_entry(Oid new_relid, RangeTblEntry *old_entry) -{ - RangeTblEntry *new_entry = copyObject(old_entry); - - /* Replace relation real name and OID, but not the reference name */ - new_entry->relname = get_rel_name(new_relid); - new_entry->relid = new_relid; - return new_entry; + inhRTIs = lappendi(inhRTIs, childRTindex); + } + return inhRTIs; } /* - * fix_parsetree_attnums - * Replaces attribute numbers from the relation represented by - * 'old_relid' in 'parsetree' with the attribute numbers from - * 'new_relid'. + * adjust_inherited_attrs + * Copy the specified query or expression and translate Vars referring + * to old_rt_index to refer to new_rt_index. * - * The parsetree is MODIFIED IN PLACE. This is OK only because - * plan_inherit_queries made a copy of the tree for us to hack upon. + * We also adjust varattno to match the new table by column name, rather + * than column number. This hack makes it possible for child tables to have + * different column positions for the "same" attribute as a parent, which + * helps ALTER TABLE ADD COLUMN. Unfortunately this isn't nearly enough to + * make it work transparently; there are other places where things fall down + * if children and parents don't have the same column numbers for inherited + * attributes. It'd be better to rip this code out and fix ALTER TABLE... */ -static void -fix_parsetree_attnums(Index rt_index, - Oid old_relid, - Oid new_relid, - Query *parsetree) +Node * +adjust_inherited_attrs(Node *node, + Index old_rt_index, Oid old_relid, + Index new_rt_index, Oid new_relid) { - fix_parsetree_attnums_context context; + adjust_inherited_attrs_context context; - if (old_relid == new_relid) - return; /* no work needed for parent rel itself */ + /* Handle simple case simply... */ + if (old_rt_index == new_rt_index) + { + Assert(old_relid == new_relid); + return copyObject(node); + } - context.rt_index = rt_index; + context.old_rt_index = old_rt_index; + context.new_rt_index = new_rt_index; context.old_relid = old_relid; context.new_relid = new_relid; - context.sublevels_up = 0; - query_tree_walker(parsetree, - fix_parsetree_attnums_walker, - (void *) &context, - true); + /* + * Must be prepared to start with a Query or a bare expression tree. + */ + if (node && IsA(node, Query)) + { + Query *query = (Query *) node; + Query *newnode; + + FLATCOPY(newnode, query, Query); + if (newnode->resultRelation == old_rt_index) + newnode->resultRelation = new_rt_index; + query_tree_mutator(newnode, adjust_inherited_attrs_mutator, + (void *) &context, false); + return (Node *) newnode; + } + else + return adjust_inherited_attrs_mutator(node, &context); } -/* - * Adjust varnos for child tables. This routine makes it possible for - * child tables to have different column positions for the "same" attribute - * as a parent, which helps ALTER TABLE ADD COLUMN. Unfortunately this isn't - * nearly enough to make it work transparently; there are other places where - * things fall down if children and parents don't have the same column numbers - * for inherited attributes. It'd be better to rip this code out and fix - * ALTER TABLE... - */ -static bool -fix_parsetree_attnums_walker(Node *node, - fix_parsetree_attnums_context *context) +static Node * +adjust_inherited_attrs_mutator(Node *node, + adjust_inherited_attrs_context *context) { if (node == NULL) - return false; + return NULL; if (IsA(node, Var)) { - Var *var = (Var *) node; + Var *var = (Var *) copyObject(node); - if (var->varlevelsup == context->sublevels_up && - var->varno == context->rt_index && - var->varattno > 0) + if (var->varlevelsup == 0 && + var->varno == context->old_rt_index) { - var->varattno = get_attnum(context->new_relid, - get_attname(context->old_relid, - var->varattno)); + var->varno = context->new_rt_index; + if (var->varattno > 0) + var->varattno = get_attnum(context->new_relid, + get_attname(context->old_relid, + var->varattno)); } - return false; + return (Node *) var; } - if (IsA(node, Query)) + if (IsA(node, RangeTblRef)) { - /* Recurse into subselects */ - bool result; - - context->sublevels_up++; - result = query_tree_walker((Query *) node, - fix_parsetree_attnums_walker, - (void *) context, - true); - context->sublevels_up--; - return result; - } - return expression_tree_walker(node, fix_parsetree_attnums_walker, - (void *) context); -} + RangeTblRef *rtr = (RangeTblRef *) copyObject(node); -static Append * -make_append(List *appendplans, - Index rt_index, - List *inheritrtable, - List *tlist) -{ - Append *node = makeNode(Append); - List *subnode; - - node->appendplans = appendplans; - node->inheritrelid = rt_index; - node->inheritrtable = inheritrtable; - node->plan.startup_cost = 0; - node->plan.total_cost = 0; - node->plan.plan_rows = 0; - node->plan.plan_width = 0; - foreach(subnode, appendplans) - { - Plan *subplan = (Plan *) lfirst(subnode); - - if (subnode == appendplans) /* first node? */ - node->plan.startup_cost = subplan->startup_cost; - node->plan.total_cost += subplan->total_cost; - node->plan.plan_rows += subplan->plan_rows; - if (node->plan.plan_width < subplan->plan_width) - node->plan.plan_width = subplan->plan_width; + if (rtr->rtindex == context->old_rt_index) + rtr->rtindex = context->new_rt_index; + return (Node *) rtr; } - node->plan.state = (EState *) NULL; - node->plan.targetlist = tlist; - node->plan.qual = NIL; - node->plan.lefttree = (Plan *) NULL; - node->plan.righttree = (Plan *) NULL; + /* + * We have to process RestrictInfo nodes specially: we do NOT want to + * copy the original subclauseindices list, since the new rel may have + * different indices. The list will be rebuilt during planning anyway. + */ + if (IsA(node, RestrictInfo)) + { + RestrictInfo *oldinfo = (RestrictInfo *) node; + RestrictInfo *newinfo = makeNode(RestrictInfo); + + /* Copy all flat-copiable fields */ + memcpy(newinfo, oldinfo, sizeof(RestrictInfo)); + + newinfo->clause = (Expr *) + adjust_inherited_attrs_mutator((Node *) oldinfo->clause, context); - return node; + newinfo->subclauseindices = NIL; + + return (Node *) newinfo; + } + /* + * NOTE: we do not need to recurse into sublinks, because they should + * already have been converted to subplans before we see them. + */ + return expression_tree_mutator(node, adjust_inherited_attrs_mutator, + (void *) context); } diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index 36843f834da..b51ec089347 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.67 2000/10/05 19:48:27 momjian Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.68 2000/11/12 00:36:59 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -391,6 +391,37 @@ create_tidscan_path(RelOptInfo *rel, List *tideval) } /* + * create_append_path + * Creates a path corresponding to an Append plan, returning the + * pathnode. + * + */ +AppendPath * +create_append_path(RelOptInfo *rel, List *subpaths) +{ + AppendPath *pathnode = makeNode(AppendPath); + List *l; + + pathnode->path.pathtype = T_Append; + pathnode->path.parent = rel; + pathnode->path.pathkeys = NIL; /* result is always considered unsorted */ + pathnode->subpaths = subpaths; + + pathnode->path.startup_cost = 0; + pathnode->path.total_cost = 0; + foreach(l, subpaths) + { + Path *subpath = (Path *) lfirst(l); + + if (l == subpaths) /* first node? */ + pathnode->path.startup_cost = subpath->startup_cost; + pathnode->path.total_cost += subpath->total_cost; + } + + return pathnode; +} + +/* * create_subqueryscan_path * Creates a path corresponding to a sequential scan of a subquery, * returning the pathnode. diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c index 86258b0f644..64720944ce3 100644 --- a/src/backend/optimizer/util/relnode.c +++ b/src/backend/optimizer/util/relnode.c @@ -8,7 +8,7 @@ * * * IDENTIFICATION - * $Header: /cvsroot/pgsql/src/backend/optimizer/util/relnode.c,v 1.29 2000/09/29 18:21:23 tgl Exp $ + * $Header: /cvsroot/pgsql/src/backend/optimizer/util/relnode.c,v 1.30 2000/11/12 00:36:59 tgl Exp $ * *------------------------------------------------------------------------- */ @@ -45,7 +45,6 @@ get_base_rel(Query *root, int relid) { List *baserels; RelOptInfo *rel; - Oid relationObjectId; foreach(baserels, root->base_rel_list) { @@ -60,7 +59,30 @@ get_base_rel(Query *root, int relid) } /* No existing RelOptInfo for this base rel, so make a new one */ - rel = makeNode(RelOptInfo); + rel = make_base_rel(root, relid); + + /* and add it to the list */ + root->base_rel_list = lcons(rel, root->base_rel_list); + + return rel; +} + +/* + * make_base_rel + * Construct a base-relation RelOptInfo for the specified rangetable index. + * + * This is split out of get_base_rel so that inheritance-tree processing can + * construct baserel nodes for child tables. We need a RelOptInfo so we can + * plan a suitable access path for each child table, but we do NOT want to + * enter the child nodes into base_rel_list. In most contexts, get_base_rel + * should be called instead. + */ +RelOptInfo * +make_base_rel(Query *root, int relid) +{ + RelOptInfo *rel = makeNode(RelOptInfo); + Oid relationObjectId; + rel->relids = makeListi1(relid); rel->rows = 0; rel->width = 0; @@ -95,8 +117,6 @@ get_base_rel(Query *root, int relid) rel->issubquery = true; } - root->base_rel_list = lcons(rel, root->base_rel_list); - return rel; } |