summaryrefslogtreecommitdiffstats
path: root/src/backend/optimizer/prep/prepunion.c
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-05-04 12:17:33 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-05-04 12:17:33 +0000
commit5e45211a64149b3c659b90ff2de6fa982a5a93ed (patch)
tree739caf8c461053357daa9f162bef34516c7bf452 /src/backend/optimizer/prep/prepunion.c
parentInitial commit. (diff)
downloadpostgresql-15-5e45211a64149b3c659b90ff2de6fa982a5a93ed.tar.xz
postgresql-15-5e45211a64149b3c659b90ff2de6fa982a5a93ed.zip
Adding upstream version 15.5.upstream/15.5
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'src/backend/optimizer/prep/prepunion.c')
-rw-r--r--src/backend/optimizer/prep/prepunion.c1420
1 files changed, 1420 insertions, 0 deletions
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
new file mode 100644
index 0000000..f004fad
--- /dev/null
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -0,0 +1,1420 @@
+/*-------------------------------------------------------------------------
+ *
+ * prepunion.c
+ * Routines to plan set-operation queries. The filename is a leftover
+ * from a time when only UNIONs were implemented.
+ *
+ * There are two code paths in the planner for set-operation queries.
+ * If a subquery consists entirely of simple UNION ALL operations, it
+ * is converted into an "append relation". Otherwise, it is handled
+ * by the general code in this module (plan_set_operations and its
+ * subroutines). There is some support code here for the append-relation
+ * case, but most of the heavy lifting for that is done elsewhere,
+ * notably in prepjointree.c and allpaths.c.
+ *
+ * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ * src/backend/optimizer/prep/prepunion.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "access/htup_details.h"
+#include "access/sysattr.h"
+#include "catalog/partition.h"
+#include "catalog/pg_inherits.h"
+#include "catalog/pg_type.h"
+#include "miscadmin.h"
+#include "nodes/makefuncs.h"
+#include "nodes/nodeFuncs.h"
+#include "optimizer/cost.h"
+#include "optimizer/pathnode.h"
+#include "optimizer/paths.h"
+#include "optimizer/planmain.h"
+#include "optimizer/planner.h"
+#include "optimizer/prep.h"
+#include "optimizer/tlist.h"
+#include "parser/parse_coerce.h"
+#include "parser/parsetree.h"
+#include "utils/lsyscache.h"
+#include "utils/rel.h"
+#include "utils/selfuncs.h"
+#include "utils/syscache.h"
+
+
+static RelOptInfo *recurse_set_operations(Node *setOp, PlannerInfo *root,
+ List *colTypes, List *colCollations,
+ bool junkOK,
+ int flag, List *refnames_tlist,
+ List **pTargetList,
+ double *pNumGroups);
+static RelOptInfo *generate_recursion_path(SetOperationStmt *setOp,
+ PlannerInfo *root,
+ List *refnames_tlist,
+ List **pTargetList);
+static RelOptInfo *generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
+ List *refnames_tlist,
+ List **pTargetList);
+static RelOptInfo *generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *root,
+ List *refnames_tlist,
+ List **pTargetList);
+static List *plan_union_children(PlannerInfo *root,
+ SetOperationStmt *top_union,
+ List *refnames_tlist,
+ List **tlist_list);
+static Path *make_union_unique(SetOperationStmt *op, Path *path, List *tlist,
+ PlannerInfo *root);
+static void postprocess_setop_rel(PlannerInfo *root, RelOptInfo *rel);
+static bool choose_hashed_setop(PlannerInfo *root, List *groupClauses,
+ Path *input_path,
+ double dNumGroups, double dNumOutputRows,
+ const char *construct);
+static List *generate_setop_tlist(List *colTypes, List *colCollations,
+ int flag,
+ Index varno,
+ bool hack_constants,
+ List *input_tlist,
+ List *refnames_tlist);
+static List *generate_append_tlist(List *colTypes, List *colCollations,
+ bool flag,
+ List *input_tlists,
+ List *refnames_tlist);
+static List *generate_setop_grouplist(SetOperationStmt *op, List *targetlist);
+
+
+/*
+ * plan_set_operations
+ *
+ * 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 root->parse->sortClause will be handled
+ * when we return to grouping_planner; likewise for LIMIT.
+ *
+ * What we return is an "upperrel" RelOptInfo containing at least one Path
+ * that implements the set-operation tree. In addition, root->processed_tlist
+ * receives a targetlist representing the output of the topmost setop node.
+ */
+RelOptInfo *
+plan_set_operations(PlannerInfo *root)
+{
+ Query *parse = root->parse;
+ SetOperationStmt *topop = castNode(SetOperationStmt, parse->setOperations);
+ Node *node;
+ RangeTblEntry *leftmostRTE;
+ Query *leftmostQuery;
+ RelOptInfo *setop_rel;
+ List *top_tlist;
+
+ Assert(topop);
+
+ /* check for unsupported stuff */
+ Assert(parse->jointree->fromlist == NIL);
+ Assert(parse->jointree->quals == NULL);
+ Assert(parse->groupClause == NIL);
+ Assert(parse->havingQual == NULL);
+ Assert(parse->windowClause == NIL);
+ Assert(parse->distinctClause == NIL);
+
+ /*
+ * In the outer query level, we won't have any true equivalences to deal
+ * with; but we do want to be able to make pathkeys, which will require
+ * single-member EquivalenceClasses. Indicate that EC merging is complete
+ * so that pathkeys.c won't complain.
+ */
+ Assert(root->eq_classes == NIL);
+ root->ec_merging_done = true;
+
+ /*
+ * We'll need to build RelOptInfos for each of the leaf subqueries, which
+ * are RTE_SUBQUERY rangetable entries in this Query. Prepare the index
+ * arrays for those, and for AppendRelInfos in case they're needed.
+ */
+ setup_simple_rel_arrays(root);
+
+ /*
+ * Find the leftmost component Query. We need to use its column names for
+ * all generated tlists (else SELECT INTO won't work right).
+ */
+ node = topop->larg;
+ while (node && IsA(node, SetOperationStmt))
+ node = ((SetOperationStmt *) node)->larg;
+ Assert(node && IsA(node, RangeTblRef));
+ leftmostRTE = root->simple_rte_array[((RangeTblRef *) node)->rtindex];
+ leftmostQuery = leftmostRTE->subquery;
+ Assert(leftmostQuery != NULL);
+
+ /*
+ * If the topmost node is a recursive union, it needs special processing.
+ */
+ if (root->hasRecursion)
+ {
+ setop_rel = generate_recursion_path(topop, root,
+ leftmostQuery->targetList,
+ &top_tlist);
+ }
+ else
+ {
+ /*
+ * Recurse on setOperations tree to generate paths for set ops. The
+ * final output paths should have just the column types shown as the
+ * output from the top-level node, plus possibly resjunk working
+ * columns (we can rely on upper-level nodes to deal with that).
+ */
+ setop_rel = recurse_set_operations((Node *) topop, root,
+ topop->colTypes, topop->colCollations,
+ true, -1,
+ leftmostQuery->targetList,
+ &top_tlist,
+ NULL);
+ }
+
+ /* Must return the built tlist into root->processed_tlist. */
+ root->processed_tlist = top_tlist;
+
+ return setop_rel;
+}
+
+/*
+ * recurse_set_operations
+ * Recursively handle one step in a tree of set operations
+ *
+ * colTypes: OID list of set-op's result column datatypes
+ * colCollations: OID list of set-op's result column collations
+ * junkOK: if true, child resjunk columns may be left in the result
+ * flag: if >= 0, add a resjunk output column indicating value of flag
+ * refnames_tlist: targetlist to take column names from
+ *
+ * Returns a RelOptInfo for the subtree, as well as these output parameters:
+ * *pTargetList: receives the fully-fledged tlist for the subtree's top plan
+ * *pNumGroups: if not NULL, we estimate the number of distinct groups
+ * in the result, and store it there
+ *
+ * The pTargetList output parameter is mostly redundant with the pathtarget
+ * of the returned RelOptInfo, but for the moment we need it because much of
+ * the logic in this file depends on flag columns being marked resjunk.
+ * Pending a redesign of how that works, this is the easy way out.
+ *
+ * We don't have to care about typmods here: the only allowed difference
+ * between set-op input and output typmods is input is a specific typmod
+ * and output is -1, and that does not require a coercion.
+ */
+static RelOptInfo *
+recurse_set_operations(Node *setOp, PlannerInfo *root,
+ List *colTypes, List *colCollations,
+ bool junkOK,
+ int flag, List *refnames_tlist,
+ List **pTargetList,
+ double *pNumGroups)
+{
+ RelOptInfo *rel = NULL; /* keep compiler quiet */
+
+ /* Guard against stack overflow due to overly complex setop nests */
+ check_stack_depth();
+
+ if (IsA(setOp, RangeTblRef))
+ {
+ RangeTblRef *rtr = (RangeTblRef *) setOp;
+ RangeTblEntry *rte = root->simple_rte_array[rtr->rtindex];
+ Query *subquery = rte->subquery;
+ PlannerInfo *subroot;
+ RelOptInfo *final_rel;
+ Path *subpath;
+ Path *path;
+ List *tlist;
+
+ Assert(subquery != NULL);
+
+ /* Build a RelOptInfo for this leaf subquery. */
+ rel = build_simple_rel(root, rtr->rtindex, NULL);
+
+ /* plan_params should not be in use in current query level */
+ Assert(root->plan_params == NIL);
+
+ /* Generate a subroot and Paths for the subquery */
+ subroot = rel->subroot = subquery_planner(root->glob, subquery,
+ root,
+ false,
+ root->tuple_fraction);
+
+ /*
+ * It should not be possible for the primitive query to contain any
+ * cross-references to other primitive queries in the setop tree.
+ */
+ if (root->plan_params)
+ elog(ERROR, "unexpected outer reference in set operation subquery");
+
+ /* Figure out the appropriate target list for this subquery. */
+ tlist = generate_setop_tlist(colTypes, colCollations,
+ flag,
+ rtr->rtindex,
+ true,
+ subroot->processed_tlist,
+ refnames_tlist);
+ rel->reltarget = create_pathtarget(root, tlist);
+
+ /* Return the fully-fledged tlist to caller, too */
+ *pTargetList = tlist;
+
+ /*
+ * Mark rel with estimated output rows, width, etc. Note that we have
+ * to do this before generating outer-query paths, else
+ * cost_subqueryscan is not happy.
+ */
+ set_subquery_size_estimates(root, rel);
+
+ /*
+ * Since we may want to add a partial path to this relation, we must
+ * set its consider_parallel flag correctly.
+ */
+ final_rel = fetch_upper_rel(subroot, UPPERREL_FINAL, NULL);
+ rel->consider_parallel = final_rel->consider_parallel;
+
+ /*
+ * For the moment, we consider only a single Path for the subquery.
+ * This should change soon (make it look more like
+ * set_subquery_pathlist).
+ */
+ subpath = get_cheapest_fractional_path(final_rel,
+ root->tuple_fraction);
+
+ /*
+ * Stick a SubqueryScanPath atop that.
+ *
+ * We don't bother to determine the subquery's output ordering since
+ * it won't be reflected in the set-op result anyhow; so just label
+ * the SubqueryScanPath with nil pathkeys. (XXX that should change
+ * soon too, likely.)
+ */
+ path = (Path *) create_subqueryscan_path(root, rel, subpath,
+ NIL, NULL);
+
+ add_path(rel, path);
+
+ /*
+ * If we have a partial path for the child relation, we can use that
+ * to build a partial path for this relation. But there's no point in
+ * considering any path but the cheapest.
+ */
+ if (rel->consider_parallel && bms_is_empty(rel->lateral_relids) &&
+ final_rel->partial_pathlist != NIL)
+ {
+ Path *partial_subpath;
+ Path *partial_path;
+
+ partial_subpath = linitial(final_rel->partial_pathlist);
+ partial_path = (Path *)
+ create_subqueryscan_path(root, rel, partial_subpath,
+ NIL, NULL);
+ add_partial_path(rel, partial_path);
+ }
+
+ /*
+ * Estimate number of groups if caller wants it. If the subquery used
+ * grouping or aggregation, its output is probably mostly unique
+ * anyway; otherwise do statistical estimation.
+ *
+ * XXX you don't really want to know about this: we do the estimation
+ * using the subquery's original targetlist expressions, not the
+ * subroot->processed_tlist which might seem more appropriate. The
+ * reason is that if the subquery is itself a setop, it may return a
+ * processed_tlist containing "varno 0" Vars generated by
+ * generate_append_tlist, and those would confuse estimate_num_groups
+ * mightily. We ought to get rid of the "varno 0" hack, but that
+ * requires a redesign of the parsetree representation of setops, so
+ * that there can be an RTE corresponding to each setop's output.
+ */
+ if (pNumGroups)
+ {
+ if (subquery->groupClause || subquery->groupingSets ||
+ subquery->distinctClause ||
+ subroot->hasHavingQual || subquery->hasAggs)
+ *pNumGroups = subpath->rows;
+ else
+ *pNumGroups = estimate_num_groups(subroot,
+ get_tlist_exprs(subquery->targetList, false),
+ subpath->rows,
+ NULL,
+ NULL);
+ }
+ }
+ else if (IsA(setOp, SetOperationStmt))
+ {
+ SetOperationStmt *op = (SetOperationStmt *) setOp;
+
+ /* UNIONs are much different from INTERSECT/EXCEPT */
+ if (op->op == SETOP_UNION)
+ rel = generate_union_paths(op, root,
+ refnames_tlist,
+ pTargetList);
+ else
+ rel = generate_nonunion_paths(op, root,
+ refnames_tlist,
+ pTargetList);
+ if (pNumGroups)
+ *pNumGroups = rel->rows;
+
+ /*
+ * If necessary, add a Result node to project the caller-requested
+ * output columns.
+ *
+ * XXX you don't really want to know about this: setrefs.c will apply
+ * fix_upper_expr() to the Result node's tlist. This would fail if the
+ * Vars generated by generate_setop_tlist() were not exactly equal()
+ * to the corresponding tlist entries of the subplan. However, since
+ * the subplan was generated by generate_union_paths() or
+ * generate_nonunion_paths(), and hence its tlist was generated by
+ * generate_append_tlist(), this will work. We just tell
+ * generate_setop_tlist() to use varno 0.
+ */
+ if (flag >= 0 ||
+ !tlist_same_datatypes(*pTargetList, colTypes, junkOK) ||
+ !tlist_same_collations(*pTargetList, colCollations, junkOK))
+ {
+ PathTarget *target;
+ ListCell *lc;
+
+ *pTargetList = generate_setop_tlist(colTypes, colCollations,
+ flag,
+ 0,
+ false,
+ *pTargetList,
+ refnames_tlist);
+ target = create_pathtarget(root, *pTargetList);
+
+ /* Apply projection to each path */
+ foreach(lc, rel->pathlist)
+ {
+ Path *subpath = (Path *) lfirst(lc);
+ Path *path;
+
+ Assert(subpath->param_info == NULL);
+ path = apply_projection_to_path(root, subpath->parent,
+ subpath, target);
+ /* If we had to add a Result, path is different from subpath */
+ if (path != subpath)
+ lfirst(lc) = path;
+ }
+
+ /* Apply projection to each partial path */
+ foreach(lc, rel->partial_pathlist)
+ {
+ Path *subpath = (Path *) lfirst(lc);
+ Path *path;
+
+ Assert(subpath->param_info == NULL);
+
+ /* avoid apply_projection_to_path, in case of multiple refs */
+ path = (Path *) create_projection_path(root, subpath->parent,
+ subpath, target);
+ lfirst(lc) = path;
+ }
+ }
+ }
+ else
+ {
+ elog(ERROR, "unrecognized node type: %d",
+ (int) nodeTag(setOp));
+ *pTargetList = NIL;
+ }
+
+ postprocess_setop_rel(root, rel);
+
+ return rel;
+}
+
+/*
+ * Generate paths for a recursive UNION node
+ */
+static RelOptInfo *
+generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root,
+ List *refnames_tlist,
+ List **pTargetList)
+{
+ RelOptInfo *result_rel;
+ Path *path;
+ RelOptInfo *lrel,
+ *rrel;
+ Path *lpath;
+ Path *rpath;
+ List *lpath_tlist;
+ List *rpath_tlist;
+ List *tlist;
+ List *groupList;
+ double dNumGroups;
+
+ /* Parser should have rejected other cases */
+ if (setOp->op != SETOP_UNION)
+ elog(ERROR, "only UNION queries can be recursive");
+ /* Worktable ID should be assigned */
+ Assert(root->wt_param_id >= 0);
+
+ /*
+ * Unlike a regular UNION node, process the left and right inputs
+ * separately without any intention of combining them into one Append.
+ */
+ lrel = recurse_set_operations(setOp->larg, root,
+ setOp->colTypes, setOp->colCollations,
+ false, -1,
+ refnames_tlist,
+ &lpath_tlist,
+ NULL);
+ lpath = lrel->cheapest_total_path;
+ /* The right path will want to look at the left one ... */
+ root->non_recursive_path = lpath;
+ rrel = recurse_set_operations(setOp->rarg, root,
+ setOp->colTypes, setOp->colCollations,
+ false, -1,
+ refnames_tlist,
+ &rpath_tlist,
+ NULL);
+ rpath = rrel->cheapest_total_path;
+ root->non_recursive_path = NULL;
+
+ /*
+ * Generate tlist for RecursiveUnion path node --- same as in Append cases
+ */
+ tlist = generate_append_tlist(setOp->colTypes, setOp->colCollations, false,
+ list_make2(lpath_tlist, rpath_tlist),
+ refnames_tlist);
+
+ *pTargetList = tlist;
+
+ /* Build result relation. */
+ result_rel = fetch_upper_rel(root, UPPERREL_SETOP,
+ bms_union(lrel->relids, rrel->relids));
+ result_rel->reltarget = create_pathtarget(root, tlist);
+
+ /*
+ * If UNION, identify the grouping operators
+ */
+ if (setOp->all)
+ {
+ groupList = NIL;
+ dNumGroups = 0;
+ }
+ else
+ {
+ /* Identify the grouping semantics */
+ groupList = generate_setop_grouplist(setOp, tlist);
+
+ /* We only support hashing here */
+ if (!grouping_is_hashable(groupList))
+ ereport(ERROR,
+ (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+ errmsg("could not implement recursive UNION"),
+ errdetail("All column datatypes must be hashable.")));
+
+ /*
+ * For the moment, take the number of distinct groups as equal to the
+ * total input size, ie, the worst case.
+ */
+ dNumGroups = lpath->rows + rpath->rows * 10;
+ }
+
+ /*
+ * And make the path node.
+ */
+ path = (Path *) create_recursiveunion_path(root,
+ result_rel,
+ lpath,
+ rpath,
+ result_rel->reltarget,
+ groupList,
+ root->wt_param_id,
+ dNumGroups);
+
+ add_path(result_rel, path);
+ postprocess_setop_rel(root, result_rel);
+ return result_rel;
+}
+
+/*
+ * Generate paths for a UNION or UNION ALL node
+ */
+static RelOptInfo *
+generate_union_paths(SetOperationStmt *op, PlannerInfo *root,
+ List *refnames_tlist,
+ List **pTargetList)
+{
+ Relids relids = NULL;
+ RelOptInfo *result_rel;
+ double save_fraction = root->tuple_fraction;
+ ListCell *lc;
+ List *pathlist = NIL;
+ List *partial_pathlist = NIL;
+ bool partial_paths_valid = true;
+ bool consider_parallel = true;
+ List *rellist;
+ List *tlist_list;
+ List *tlist;
+ Path *path;
+
+ /*
+ * If plain UNION, tell children to fetch all tuples.
+ *
+ * Note: in UNION ALL, we pass the top-level tuple_fraction unmodified to
+ * each arm of the UNION ALL. One could make a case for reducing the
+ * tuple fraction for later arms (discounting by the expected size of the
+ * earlier arms' results) but it seems not worth the trouble. The normal
+ * case where tuple_fraction isn't already zero is a LIMIT at top level,
+ * and passing it down as-is is usually enough to get the desired result
+ * of preferring fast-start plans.
+ */
+ if (!op->all)
+ root->tuple_fraction = 0.0;
+
+ /*
+ * If any of my children are identical UNION nodes (same op, all-flag, and
+ * colTypes) then they can be merged into this node so that we generate
+ * only one Append and unique-ification for the lot. Recurse to find such
+ * nodes and compute their children's paths.
+ */
+ rellist = plan_union_children(root, op, refnames_tlist, &tlist_list);
+
+ /*
+ * Generate tlist for Append plan node.
+ *
+ * The tlist for an Append plan isn't important as far as the Append is
+ * concerned, but we must make it look real anyway for the benefit of the
+ * next plan level up.
+ */
+ tlist = generate_append_tlist(op->colTypes, op->colCollations, false,
+ tlist_list, refnames_tlist);
+
+ *pTargetList = tlist;
+
+ /* Build path lists and relid set. */
+ foreach(lc, rellist)
+ {
+ RelOptInfo *rel = lfirst(lc);
+
+ pathlist = lappend(pathlist, rel->cheapest_total_path);
+
+ if (consider_parallel)
+ {
+ if (!rel->consider_parallel)
+ {
+ consider_parallel = false;
+ partial_paths_valid = false;
+ }
+ else if (rel->partial_pathlist == NIL)
+ partial_paths_valid = false;
+ else
+ partial_pathlist = lappend(partial_pathlist,
+ linitial(rel->partial_pathlist));
+ }
+
+ relids = bms_union(relids, rel->relids);
+ }
+
+ /* Build result relation. */
+ result_rel = fetch_upper_rel(root, UPPERREL_SETOP, relids);
+ result_rel->reltarget = create_pathtarget(root, tlist);
+ result_rel->consider_parallel = consider_parallel;
+
+ /*
+ * Append the child results together.
+ */
+ path = (Path *) create_append_path(root, result_rel, pathlist, NIL,
+ NIL, NULL, 0, false, -1);
+
+ /*
+ * For UNION ALL, we just need the Append path. For UNION, need to add
+ * node(s) to remove duplicates.
+ */
+ if (!op->all)
+ path = make_union_unique(op, path, tlist, root);
+
+ add_path(result_rel, path);
+
+ /*
+ * Estimate number of groups. For now we just assume the output is unique
+ * --- this is certainly true for the UNION case, and we want worst-case
+ * estimates anyway.
+ */
+ result_rel->rows = path->rows;
+
+ /*
+ * Now consider doing the same thing using the partial paths plus Append
+ * plus Gather.
+ */
+ if (partial_paths_valid)
+ {
+ Path *ppath;
+ ListCell *lc;
+ int parallel_workers = 0;
+
+ /* Find the highest number of workers requested for any subpath. */
+ foreach(lc, partial_pathlist)
+ {
+ Path *path = lfirst(lc);
+
+ parallel_workers = Max(parallel_workers, path->parallel_workers);
+ }
+ Assert(parallel_workers > 0);
+
+ /*
+ * If the use of parallel append is permitted, always request at least
+ * log2(# of children) paths. We assume it can be useful to have
+ * extra workers in this case because they will be spread out across
+ * the children. The precise formula is just a guess; see
+ * add_paths_to_append_rel.
+ */
+ if (enable_parallel_append)
+ {
+ parallel_workers = Max(parallel_workers,
+ fls(list_length(partial_pathlist)));
+ parallel_workers = Min(parallel_workers,
+ max_parallel_workers_per_gather);
+ }
+ Assert(parallel_workers > 0);
+
+ ppath = (Path *)
+ create_append_path(root, result_rel, NIL, partial_pathlist,
+ NIL, NULL,
+ parallel_workers, enable_parallel_append,
+ -1);
+ ppath = (Path *)
+ create_gather_path(root, result_rel, ppath,
+ result_rel->reltarget, NULL, NULL);
+ if (!op->all)
+ ppath = make_union_unique(op, ppath, tlist, root);
+ add_path(result_rel, ppath);
+ }
+
+ /* Undo effects of possibly forcing tuple_fraction to 0 */
+ root->tuple_fraction = save_fraction;
+
+ return result_rel;
+}
+
+/*
+ * Generate paths for an INTERSECT, INTERSECT ALL, EXCEPT, or EXCEPT ALL node
+ */
+static RelOptInfo *
+generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *root,
+ List *refnames_tlist,
+ List **pTargetList)
+{
+ RelOptInfo *result_rel;
+ RelOptInfo *lrel,
+ *rrel;
+ double save_fraction = root->tuple_fraction;
+ Path *lpath,
+ *rpath,
+ *path;
+ List *lpath_tlist,
+ *rpath_tlist,
+ *tlist_list,
+ *tlist,
+ *groupList,
+ *pathlist;
+ double dLeftGroups,
+ dRightGroups,
+ dNumGroups,
+ dNumOutputRows;
+ bool use_hash;
+ SetOpCmd cmd;
+ int firstFlag;
+
+ /*
+ * Tell children to fetch all tuples.
+ */
+ root->tuple_fraction = 0.0;
+
+ /* Recurse on children, ensuring their outputs are marked */
+ lrel = recurse_set_operations(op->larg, root,
+ op->colTypes, op->colCollations,
+ false, 0,
+ refnames_tlist,
+ &lpath_tlist,
+ &dLeftGroups);
+ lpath = lrel->cheapest_total_path;
+ rrel = recurse_set_operations(op->rarg, root,
+ op->colTypes, op->colCollations,
+ false, 1,
+ refnames_tlist,
+ &rpath_tlist,
+ &dRightGroups);
+ rpath = rrel->cheapest_total_path;
+
+ /* Undo effects of forcing tuple_fraction to 0 */
+ root->tuple_fraction = save_fraction;
+
+ /*
+ * For EXCEPT, we must put the left input first. For INTERSECT, either
+ * order should give the same results, and we prefer to put the smaller
+ * input first in order to minimize the size of the hash table in the
+ * hashing case. "Smaller" means the one with the fewer groups.
+ */
+ if (op->op == SETOP_EXCEPT || dLeftGroups <= dRightGroups)
+ {
+ pathlist = list_make2(lpath, rpath);
+ tlist_list = list_make2(lpath_tlist, rpath_tlist);
+ firstFlag = 0;
+ }
+ else
+ {
+ pathlist = list_make2(rpath, lpath);
+ tlist_list = list_make2(rpath_tlist, lpath_tlist);
+ firstFlag = 1;
+ }
+
+ /*
+ * Generate tlist for Append plan node.
+ *
+ * The tlist for an Append plan isn't important as far as the Append is
+ * concerned, but we must make it look real anyway for the benefit of the
+ * next plan level up. In fact, it has to be real enough that the flag
+ * column is shown as a variable not a constant, else setrefs.c will get
+ * confused.
+ */
+ tlist = generate_append_tlist(op->colTypes, op->colCollations, true,
+ tlist_list, refnames_tlist);
+
+ *pTargetList = tlist;
+
+ /* Build result relation. */
+ result_rel = fetch_upper_rel(root, UPPERREL_SETOP,
+ bms_union(lrel->relids, rrel->relids));
+ result_rel->reltarget = create_pathtarget(root, tlist);
+
+ /*
+ * Append the child results together.
+ */
+ path = (Path *) create_append_path(root, result_rel, pathlist, NIL,
+ NIL, NULL, 0, false, -1);
+
+ /* Identify the grouping semantics */
+ groupList = generate_setop_grouplist(op, tlist);
+
+ /*
+ * Estimate number of distinct groups that we'll need hashtable entries
+ * for; this is the size of the left-hand input for EXCEPT, or the smaller
+ * input for INTERSECT. Also estimate the number of eventual output rows.
+ * In non-ALL cases, we estimate each group produces one output row; in
+ * ALL cases use the relevant relation size. These are worst-case
+ * estimates, of course, but we need to be conservative.
+ */
+ if (op->op == SETOP_EXCEPT)
+ {
+ dNumGroups = dLeftGroups;
+ dNumOutputRows = op->all ? lpath->rows : dNumGroups;
+ }
+ else
+ {
+ dNumGroups = Min(dLeftGroups, dRightGroups);
+ dNumOutputRows = op->all ? Min(lpath->rows, rpath->rows) : dNumGroups;
+ }
+
+ /*
+ * Decide whether to hash or sort, and add a sort node if needed.
+ */
+ use_hash = choose_hashed_setop(root, groupList, path,
+ dNumGroups, dNumOutputRows,
+ (op->op == SETOP_INTERSECT) ? "INTERSECT" : "EXCEPT");
+
+ if (groupList && !use_hash)
+ path = (Path *) create_sort_path(root,
+ result_rel,
+ path,
+ make_pathkeys_for_sortclauses(root,
+ groupList,
+ tlist),
+ -1.0);
+
+ /*
+ * Finally, add a SetOp path node to generate the correct output.
+ */
+ switch (op->op)
+ {
+ case SETOP_INTERSECT:
+ cmd = op->all ? SETOPCMD_INTERSECT_ALL : SETOPCMD_INTERSECT;
+ break;
+ case SETOP_EXCEPT:
+ cmd = op->all ? SETOPCMD_EXCEPT_ALL : SETOPCMD_EXCEPT;
+ break;
+ default:
+ elog(ERROR, "unrecognized set op: %d", (int) op->op);
+ cmd = SETOPCMD_INTERSECT; /* keep compiler quiet */
+ break;
+ }
+ path = (Path *) create_setop_path(root,
+ result_rel,
+ path,
+ cmd,
+ use_hash ? SETOP_HASHED : SETOP_SORTED,
+ groupList,
+ list_length(op->colTypes) + 1,
+ use_hash ? firstFlag : -1,
+ dNumGroups,
+ dNumOutputRows);
+
+ result_rel->rows = path->rows;
+ add_path(result_rel, path);
+ return result_rel;
+}
+
+/*
+ * Pull up children of a UNION node that are identically-propertied UNIONs.
+ *
+ * NOTE: we can also pull a UNION ALL up into a UNION, since the distinct
+ * output rows will be lost anyway.
+ *
+ * NOTE: currently, we ignore collations while determining if a child has
+ * the same properties. This is semantically sound only so long as all
+ * collations have the same notion of equality. It is valid from an
+ * implementation standpoint because we don't care about the ordering of
+ * a UNION child's result: UNION ALL results are always unordered, and
+ * generate_union_paths will force a fresh sort if the top level is a UNION.
+ */
+static List *
+plan_union_children(PlannerInfo *root,
+ SetOperationStmt *top_union,
+ List *refnames_tlist,
+ List **tlist_list)
+{
+ List *pending_rels = list_make1(top_union);
+ List *result = NIL;
+ List *child_tlist;
+
+ *tlist_list = NIL;
+
+ while (pending_rels != NIL)
+ {
+ Node *setOp = linitial(pending_rels);
+
+ pending_rels = list_delete_first(pending_rels);
+
+ if (IsA(setOp, SetOperationStmt))
+ {
+ SetOperationStmt *op = (SetOperationStmt *) setOp;
+
+ if (op->op == top_union->op &&
+ (op->all == top_union->all || op->all) &&
+ equal(op->colTypes, top_union->colTypes))
+ {
+ /* Same UNION, so fold children into parent */
+ pending_rels = lcons(op->rarg, pending_rels);
+ pending_rels = lcons(op->larg, pending_rels);
+ continue;
+ }
+ }
+
+ /*
+ * Not same, so plan this child separately.
+ *
+ * Note we disallow any resjunk columns in child results. This is
+ * necessary since the Append node that implements the union won't do
+ * any projection, and upper levels will get confused if some of our
+ * output tuples have junk and some don't. This case only arises when
+ * we have an EXCEPT or INTERSECT as child, else there won't be
+ * resjunk anyway.
+ */
+ result = lappend(result, recurse_set_operations(setOp, root,
+ top_union->colTypes,
+ top_union->colCollations,
+ false, -1,
+ refnames_tlist,
+ &child_tlist,
+ NULL));
+ *tlist_list = lappend(*tlist_list, child_tlist);
+ }
+
+ return result;
+}
+
+/*
+ * Add nodes to the given path tree to unique-ify the result of a UNION.
+ */
+static Path *
+make_union_unique(SetOperationStmt *op, Path *path, List *tlist,
+ PlannerInfo *root)
+{
+ RelOptInfo *result_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
+ List *groupList;
+ double dNumGroups;
+
+ /* Identify the grouping semantics */
+ groupList = generate_setop_grouplist(op, tlist);
+
+ /*
+ * XXX for the moment, take the number of distinct groups as equal to the
+ * total input size, ie, the worst case. This is too conservative, but
+ * it's not clear how to get a decent estimate of the true size. One
+ * should note as well the propensity of novices to write UNION rather
+ * than UNION ALL even when they don't expect any duplicates...
+ */
+ dNumGroups = path->rows;
+
+ /* Decide whether to hash or sort */
+ if (choose_hashed_setop(root, groupList, path,
+ dNumGroups, dNumGroups,
+ "UNION"))
+ {
+ /* Hashed aggregate plan --- no sort needed */
+ path = (Path *) create_agg_path(root,
+ result_rel,
+ path,
+ create_pathtarget(root, tlist),
+ AGG_HASHED,
+ AGGSPLIT_SIMPLE,
+ groupList,
+ NIL,
+ NULL,
+ dNumGroups);
+ }
+ else
+ {
+ /* Sort and Unique */
+ if (groupList)
+ path = (Path *)
+ create_sort_path(root,
+ result_rel,
+ path,
+ make_pathkeys_for_sortclauses(root,
+ groupList,
+ tlist),
+ -1.0);
+ path = (Path *) create_upper_unique_path(root,
+ result_rel,
+ path,
+ list_length(path->pathkeys),
+ dNumGroups);
+ }
+
+ return path;
+}
+
+/*
+ * postprocess_setop_rel - perform steps required after adding paths
+ */
+static void
+postprocess_setop_rel(PlannerInfo *root, RelOptInfo *rel)
+{
+ /*
+ * We don't currently worry about allowing FDWs to contribute paths to
+ * this relation, but give extensions a chance.
+ */
+ if (create_upper_paths_hook)
+ (*create_upper_paths_hook) (root, UPPERREL_SETOP,
+ NULL, rel, NULL);
+
+ /* Select cheapest path */
+ set_cheapest(rel);
+}
+
+/*
+ * choose_hashed_setop - should we use hashing for a set operation?
+ */
+static bool
+choose_hashed_setop(PlannerInfo *root, List *groupClauses,
+ Path *input_path,
+ double dNumGroups, double dNumOutputRows,
+ const char *construct)
+{
+ int numGroupCols = list_length(groupClauses);
+ Size hash_mem_limit = get_hash_memory_limit();
+ bool can_sort;
+ bool can_hash;
+ Size hashentrysize;
+ Path hashed_p;
+ Path sorted_p;
+ double tuple_fraction;
+
+ /* Check whether the operators support sorting or hashing */
+ can_sort = grouping_is_sortable(groupClauses);
+ can_hash = grouping_is_hashable(groupClauses);
+ if (can_hash && can_sort)
+ {
+ /* we have a meaningful choice to make, continue ... */
+ }
+ else if (can_hash)
+ return true;
+ else if (can_sort)
+ return false;
+ else
+ ereport(ERROR,
+ (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+ /* translator: %s is UNION, INTERSECT, or EXCEPT */
+ errmsg("could not implement %s", construct),
+ errdetail("Some of the datatypes only support hashing, while others only support sorting.")));
+
+ /* Prefer sorting when enable_hashagg is off */
+ if (!enable_hashagg)
+ return false;
+
+ /*
+ * Don't do it if it doesn't look like the hashtable will fit into
+ * hash_mem.
+ */
+ hashentrysize = MAXALIGN(input_path->pathtarget->width) + MAXALIGN(SizeofMinimalTupleHeader);
+
+ if (hashentrysize * dNumGroups > hash_mem_limit)
+ return false;
+
+ /*
+ * See if the estimated cost is no more than doing it the other way.
+ *
+ * We need to consider input_plan + hashagg versus input_plan + sort +
+ * group. Note that the actual result plan might involve a SetOp or
+ * Unique node, not Agg or Group, but the cost estimates for Agg and Group
+ * should be close enough for our purposes here.
+ *
+ * These path variables are dummies that just hold cost fields; we don't
+ * make actual Paths for these steps.
+ */
+ cost_agg(&hashed_p, root, AGG_HASHED, NULL,
+ numGroupCols, dNumGroups,
+ NIL,
+ input_path->startup_cost, input_path->total_cost,
+ input_path->rows, input_path->pathtarget->width);
+
+ /*
+ * Now for the sorted case. Note that the input is *always* unsorted,
+ * since it was made by appending unrelated sub-relations together.
+ */
+ sorted_p.startup_cost = input_path->startup_cost;
+ sorted_p.total_cost = input_path->total_cost;
+ /* XXX cost_sort doesn't actually look at pathkeys, so just pass NIL */
+ cost_sort(&sorted_p, root, NIL, sorted_p.total_cost,
+ input_path->rows, input_path->pathtarget->width,
+ 0.0, work_mem, -1.0);
+ cost_group(&sorted_p, root, numGroupCols, dNumGroups,
+ NIL,
+ sorted_p.startup_cost, sorted_p.total_cost,
+ input_path->rows);
+
+ /*
+ * Now make the decision using the top-level tuple fraction. First we
+ * have to convert an absolute count (LIMIT) into fractional form.
+ */
+ tuple_fraction = root->tuple_fraction;
+ if (tuple_fraction >= 1.0)
+ tuple_fraction /= dNumOutputRows;
+
+ if (compare_fractional_path_costs(&hashed_p, &sorted_p,
+ tuple_fraction) < 0)
+ {
+ /* Hashed is cheaper, so use it */
+ return true;
+ }
+ return false;
+}
+
+/*
+ * Generate targetlist for a set-operation plan node
+ *
+ * colTypes: OID list of set-op's result column datatypes
+ * colCollations: OID list of set-op's result column collations
+ * flag: -1 if no flag column needed, 0 or 1 to create a const flag column
+ * varno: varno to use in generated Vars
+ * hack_constants: true to copy up constants (see comments in code)
+ * input_tlist: targetlist of this node's input node
+ * refnames_tlist: targetlist to take column names from
+ */
+static List *
+generate_setop_tlist(List *colTypes, List *colCollations,
+ int flag,
+ Index varno,
+ bool hack_constants,
+ List *input_tlist,
+ List *refnames_tlist)
+{
+ List *tlist = NIL;
+ int resno = 1;
+ ListCell *ctlc,
+ *cclc,
+ *itlc,
+ *rtlc;
+ TargetEntry *tle;
+ Node *expr;
+
+ forfour(ctlc, colTypes, cclc, colCollations,
+ itlc, input_tlist, rtlc, refnames_tlist)
+ {
+ Oid colType = lfirst_oid(ctlc);
+ Oid colColl = lfirst_oid(cclc);
+ TargetEntry *inputtle = (TargetEntry *) lfirst(itlc);
+ TargetEntry *reftle = (TargetEntry *) lfirst(rtlc);
+
+ Assert(inputtle->resno == resno);
+ Assert(reftle->resno == resno);
+ Assert(!inputtle->resjunk);
+ Assert(!reftle->resjunk);
+
+ /*
+ * Generate columns referencing input columns and having appropriate
+ * data types and column names. Insert datatype coercions where
+ * necessary.
+ *
+ * HACK: constants in the input's targetlist are copied up as-is
+ * rather than being referenced as subquery outputs. This is mainly
+ * to ensure that when we try to coerce them to the output column's
+ * datatype, the right things happen for UNKNOWN constants. But do
+ * this only at the first level of subquery-scan plans; we don't want
+ * phony constants appearing in the output tlists of upper-level
+ * nodes!
+ */
+ if (hack_constants && inputtle->expr && IsA(inputtle->expr, Const))
+ expr = (Node *) inputtle->expr;
+ else
+ expr = (Node *) makeVar(varno,
+ inputtle->resno,
+ exprType((Node *) inputtle->expr),
+ exprTypmod((Node *) inputtle->expr),
+ exprCollation((Node *) inputtle->expr),
+ 0);
+
+ if (exprType(expr) != colType)
+ {
+ /*
+ * Note: it's not really cool to be applying coerce_to_common_type
+ * here; one notable point is that assign_expr_collations never
+ * gets run on any generated nodes. For the moment that's not a
+ * problem because we force the correct exposed collation below.
+ * It would likely be best to make the parser generate the correct
+ * output tlist for every set-op to begin with, though.
+ */
+ expr = coerce_to_common_type(NULL, /* no UNKNOWNs here */
+ expr,
+ colType,
+ "UNION/INTERSECT/EXCEPT");
+ }
+
+ /*
+ * Ensure the tlist entry's exposed collation matches the set-op. This
+ * is necessary because plan_set_operations() reports the result
+ * ordering as a list of SortGroupClauses, which don't carry collation
+ * themselves but just refer to tlist entries. If we don't show the
+ * right collation then planner.c might do the wrong thing in
+ * higher-level queries.
+ *
+ * Note we use RelabelType, not CollateExpr, since this expression
+ * will reach the executor without any further processing.
+ */
+ if (exprCollation(expr) != colColl)
+ expr = applyRelabelType(expr,
+ exprType(expr), exprTypmod(expr), colColl,
+ COERCE_IMPLICIT_CAST, -1, false);
+
+ tle = makeTargetEntry((Expr *) expr,
+ (AttrNumber) resno++,
+ pstrdup(reftle->resname),
+ false);
+
+ /*
+ * By convention, all non-resjunk columns in a setop tree have
+ * ressortgroupref equal to their resno. In some cases the ref isn't
+ * needed, but this is a cleaner way than modifying the tlist later.
+ */
+ tle->ressortgroupref = tle->resno;
+
+ tlist = lappend(tlist, tle);
+ }
+
+ if (flag >= 0)
+ {
+ /* Add a resjunk flag column */
+ /* flag value is the given constant */
+ expr = (Node *) makeConst(INT4OID,
+ -1,
+ InvalidOid,
+ sizeof(int32),
+ Int32GetDatum(flag),
+ false,
+ true);
+ tle = makeTargetEntry((Expr *) expr,
+ (AttrNumber) resno++,
+ pstrdup("flag"),
+ true);
+ tlist = lappend(tlist, tle);
+ }
+
+ return tlist;
+}
+
+/*
+ * Generate targetlist for a set-operation Append node
+ *
+ * colTypes: OID list of set-op's result column datatypes
+ * colCollations: OID list of set-op's result column collations
+ * flag: true to create a flag column copied up from subplans
+ * input_tlists: list of tlists for sub-plans of the Append
+ * refnames_tlist: targetlist to take column names from
+ *
+ * The entries in the Append's targetlist should always be simple Vars;
+ * we just have to make sure they have the right datatypes/typmods/collations.
+ * The Vars are always generated with varno 0.
+ *
+ * XXX a problem with the varno-zero approach is that set_pathtarget_cost_width
+ * cannot figure out a realistic width for the tlist we make here. But we
+ * ought to refactor this code to produce a PathTarget directly, anyway.
+ */
+static List *
+generate_append_tlist(List *colTypes, List *colCollations,
+ bool flag,
+ List *input_tlists,
+ List *refnames_tlist)
+{
+ List *tlist = NIL;
+ int resno = 1;
+ ListCell *curColType;
+ ListCell *curColCollation;
+ ListCell *ref_tl_item;
+ int colindex;
+ TargetEntry *tle;
+ Node *expr;
+ ListCell *tlistl;
+ int32 *colTypmods;
+
+ /*
+ * First extract typmods to use.
+ *
+ * If the inputs all agree on type and typmod of a particular column, use
+ * that typmod; else use -1.
+ */
+ colTypmods = (int32 *) palloc(list_length(colTypes) * sizeof(int32));
+
+ foreach(tlistl, input_tlists)
+ {
+ List *subtlist = (List *) lfirst(tlistl);
+ ListCell *subtlistl;
+
+ curColType = list_head(colTypes);
+ colindex = 0;
+ foreach(subtlistl, subtlist)
+ {
+ TargetEntry *subtle = (TargetEntry *) lfirst(subtlistl);
+
+ if (subtle->resjunk)
+ continue;
+ Assert(curColType != NULL);
+ if (exprType((Node *) subtle->expr) == lfirst_oid(curColType))
+ {
+ /* If first subplan, copy the typmod; else compare */
+ int32 subtypmod = exprTypmod((Node *) subtle->expr);
+
+ if (tlistl == list_head(input_tlists))
+ colTypmods[colindex] = subtypmod;
+ else if (subtypmod != colTypmods[colindex])
+ colTypmods[colindex] = -1;
+ }
+ else
+ {
+ /* types disagree, so force typmod to -1 */
+ colTypmods[colindex] = -1;
+ }
+ curColType = lnext(colTypes, curColType);
+ colindex++;
+ }
+ Assert(curColType == NULL);
+ }
+
+ /*
+ * Now we can build the tlist for the Append.
+ */
+ colindex = 0;
+ forthree(curColType, colTypes, curColCollation, colCollations,
+ ref_tl_item, refnames_tlist)
+ {
+ Oid colType = lfirst_oid(curColType);
+ int32 colTypmod = colTypmods[colindex++];
+ Oid colColl = lfirst_oid(curColCollation);
+ TargetEntry *reftle = (TargetEntry *) lfirst(ref_tl_item);
+
+ Assert(reftle->resno == resno);
+ Assert(!reftle->resjunk);
+ expr = (Node *) makeVar(0,
+ resno,
+ colType,
+ colTypmod,
+ colColl,
+ 0);
+ tle = makeTargetEntry((Expr *) expr,
+ (AttrNumber) resno++,
+ pstrdup(reftle->resname),
+ false);
+
+ /*
+ * By convention, all non-resjunk columns in a setop tree have
+ * ressortgroupref equal to their resno. In some cases the ref isn't
+ * needed, but this is a cleaner way than modifying the tlist later.
+ */
+ tle->ressortgroupref = tle->resno;
+
+ tlist = lappend(tlist, tle);
+ }
+
+ if (flag)
+ {
+ /* Add a resjunk flag column */
+ /* flag value is shown as copied up from subplan */
+ expr = (Node *) makeVar(0,
+ resno,
+ INT4OID,
+ -1,
+ InvalidOid,
+ 0);
+ tle = makeTargetEntry((Expr *) expr,
+ (AttrNumber) resno++,
+ pstrdup("flag"),
+ true);
+ tlist = lappend(tlist, tle);
+ }
+
+ pfree(colTypmods);
+
+ return tlist;
+}
+
+/*
+ * generate_setop_grouplist
+ * Build a SortGroupClause list defining the sort/grouping properties
+ * of the setop's output columns.
+ *
+ * Parse analysis already determined the properties and built a suitable
+ * list, except that the entries do not have sortgrouprefs set because
+ * the parser output representation doesn't include a tlist for each
+ * setop. So what we need to do here is copy that list and install
+ * proper sortgrouprefs into it (copying those from the targetlist).
+ */
+static List *
+generate_setop_grouplist(SetOperationStmt *op, List *targetlist)
+{
+ List *grouplist = copyObject(op->groupClauses);
+ ListCell *lg;
+ ListCell *lt;
+
+ lg = list_head(grouplist);
+ foreach(lt, targetlist)
+ {
+ TargetEntry *tle = (TargetEntry *) lfirst(lt);
+ SortGroupClause *sgc;
+
+ if (tle->resjunk)
+ {
+ /* resjunk columns should not have sortgrouprefs */
+ Assert(tle->ressortgroupref == 0);
+ continue; /* ignore resjunk columns */
+ }
+
+ /* non-resjunk columns should have sortgroupref = resno */
+ Assert(tle->ressortgroupref == tle->resno);
+
+ /* non-resjunk columns should have grouping clauses */
+ Assert(lg != NULL);
+ sgc = (SortGroupClause *) lfirst(lg);
+ lg = lnext(grouplist, lg);
+ Assert(sgc->tleSortGroupRef == 0);
+
+ sgc->tleSortGroupRef = tle->ressortgroupref;
+ }
+ Assert(lg == NULL);
+ return grouplist;
+}