PostgreSQL Source Code  git master
prepunion.c File Reference
#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"
Include dependency graph for prepunion.c:

Go to the source code of this file.

Functions

static RelOptInforecurse_set_operations (Node *setOp, PlannerInfo *root, List *colTypes, List *colCollations, bool junkOK, int flag, List *refnames_tlist, List **pTargetList, double *pNumGroups)
 
static RelOptInfogenerate_recursion_path (SetOperationStmt *setOp, PlannerInfo *root, List *refnames_tlist, List **pTargetList)
 
static RelOptInfogenerate_union_paths (SetOperationStmt *op, PlannerInfo *root, List *refnames_tlist, List **pTargetList)
 
static RelOptInfogenerate_nonunion_paths (SetOperationStmt *op, PlannerInfo *root, List *refnames_tlist, List **pTargetList)
 
static Listplan_union_children (PlannerInfo *root, SetOperationStmt *top_union, List *refnames_tlist, List **tlist_list)
 
static Pathmake_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 Listgenerate_setop_tlist (List *colTypes, List *colCollations, int flag, Index varno, bool hack_constants, List *input_tlist, List *refnames_tlist, bool *trivial_tlist)
 
static Listgenerate_append_tlist (List *colTypes, List *colCollations, bool flag, List *input_tlists, List *refnames_tlist)
 
static Listgenerate_setop_grouplist (SetOperationStmt *op, List *targetlist)
 
RelOptInfoplan_set_operations (PlannerInfo *root)
 

Function Documentation

◆ choose_hashed_setop()

static bool choose_hashed_setop ( PlannerInfo root,
List groupClauses,
Path input_path,
double  dNumGroups,
double  dNumOutputRows,
const char *  construct 
)
static

Definition at line 1023 of file prepunion.c.

1027 {
1028  int numGroupCols = list_length(groupClauses);
1029  Size hash_mem_limit = get_hash_memory_limit();
1030  bool can_sort;
1031  bool can_hash;
1032  Size hashentrysize;
1033  Path hashed_p;
1034  Path sorted_p;
1035  double tuple_fraction;
1036 
1037  /* Check whether the operators support sorting or hashing */
1038  can_sort = grouping_is_sortable(groupClauses);
1039  can_hash = grouping_is_hashable(groupClauses);
1040  if (can_hash && can_sort)
1041  {
1042  /* we have a meaningful choice to make, continue ... */
1043  }
1044  else if (can_hash)
1045  return true;
1046  else if (can_sort)
1047  return false;
1048  else
1049  ereport(ERROR,
1050  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1051  /* translator: %s is UNION, INTERSECT, or EXCEPT */
1052  errmsg("could not implement %s", construct),
1053  errdetail("Some of the datatypes only support hashing, while others only support sorting.")));
1054 
1055  /* Prefer sorting when enable_hashagg is off */
1056  if (!enable_hashagg)
1057  return false;
1058 
1059  /*
1060  * Don't do it if it doesn't look like the hashtable will fit into
1061  * hash_mem.
1062  */
1063  hashentrysize = MAXALIGN(input_path->pathtarget->width) + MAXALIGN(SizeofMinimalTupleHeader);
1064 
1065  if (hashentrysize * dNumGroups > hash_mem_limit)
1066  return false;
1067 
1068  /*
1069  * See if the estimated cost is no more than doing it the other way.
1070  *
1071  * We need to consider input_plan + hashagg versus input_plan + sort +
1072  * group. Note that the actual result plan might involve a SetOp or
1073  * Unique node, not Agg or Group, but the cost estimates for Agg and Group
1074  * should be close enough for our purposes here.
1075  *
1076  * These path variables are dummies that just hold cost fields; we don't
1077  * make actual Paths for these steps.
1078  */
1079  cost_agg(&hashed_p, root, AGG_HASHED, NULL,
1080  numGroupCols, dNumGroups,
1081  NIL,
1082  input_path->startup_cost, input_path->total_cost,
1083  input_path->rows, input_path->pathtarget->width);
1084 
1085  /*
1086  * Now for the sorted case. Note that the input is *always* unsorted,
1087  * since it was made by appending unrelated sub-relations together.
1088  */
1089  sorted_p.startup_cost = input_path->startup_cost;
1090  sorted_p.total_cost = input_path->total_cost;
1091  /* XXX cost_sort doesn't actually look at pathkeys, so just pass NIL */
1092  cost_sort(&sorted_p, root, NIL, sorted_p.total_cost,
1093  input_path->rows, input_path->pathtarget->width,
1094  0.0, work_mem, -1.0);
1095  cost_group(&sorted_p, root, numGroupCols, dNumGroups,
1096  NIL,
1097  sorted_p.startup_cost, sorted_p.total_cost,
1098  input_path->rows);
1099 
1100  /*
1101  * Now make the decision using the top-level tuple fraction. First we
1102  * have to convert an absolute count (LIMIT) into fractional form.
1103  */
1104  tuple_fraction = root->tuple_fraction;
1105  if (tuple_fraction >= 1.0)
1106  tuple_fraction /= dNumOutputRows;
1107 
1108  if (compare_fractional_path_costs(&hashed_p, &sorted_p,
1109  tuple_fraction) < 0)
1110  {
1111  /* Hashed is cheaper, so use it */
1112  return true;
1113  }
1114  return false;
1115 }
#define MAXALIGN(LEN)
Definition: c.h:747
size_t Size
Definition: c.h:541
void cost_agg(Path *path, PlannerInfo *root, AggStrategy aggstrategy, const AggClauseCosts *aggcosts, int numGroupCols, double numGroups, List *quals, Cost input_startup_cost, Cost input_total_cost, double input_tuples, double input_width)
Definition: costsize.c:2620
bool enable_hashagg
Definition: costsize.c:142
void cost_sort(Path *path, PlannerInfo *root, List *pathkeys, Cost input_cost, double tuples, int width, Cost comparison_cost, int sort_mem, double limit_tuples)
Definition: costsize.c:2096
void cost_group(Path *path, PlannerInfo *root, int numGroupCols, double numGroups, List *quals, Cost input_startup_cost, Cost input_total_cost, double input_tuples)
Definition: costsize.c:2892
int errdetail(const char *fmt,...)
Definition: elog.c:1039
int errcode(int sqlerrcode)
Definition: elog.c:695
int errmsg(const char *fmt,...)
Definition: elog.c:906
#define ERROR
Definition: elog.h:35
#define ereport(elevel,...)
Definition: elog.h:145
int work_mem
Definition: globals.c:125
#define SizeofMinimalTupleHeader
Definition: htup_details.h:643
size_t get_hash_memory_limit(void)
Definition: nodeHash.c:3390
@ AGG_HASHED
Definition: nodes.h:353
int compare_fractional_path_costs(Path *path1, Path *path2, double fraction)
Definition: pathnode.c:117
static int list_length(const List *l)
Definition: pg_list.h:150
#define NIL
Definition: pg_list.h:66
Cardinality rows
Definition: pathnodes.h:1544
Cost startup_cost
Definition: pathnodes.h:1545
Cost total_cost
Definition: pathnodes.h:1546
Selectivity tuple_fraction
Definition: pathnodes.h:440
bool grouping_is_sortable(List *groupClause)
Definition: tlist.c:540
bool grouping_is_hashable(List *groupClause)
Definition: tlist.c:560

References AGG_HASHED, compare_fractional_path_costs(), cost_agg(), cost_group(), cost_sort(), enable_hashagg, ereport, errcode(), errdetail(), errmsg(), ERROR, get_hash_memory_limit(), grouping_is_hashable(), grouping_is_sortable(), list_length(), MAXALIGN, NIL, Path::rows, SizeofMinimalTupleHeader, Path::startup_cost, Path::total_cost, PlannerInfo::tuple_fraction, and work_mem.

Referenced by generate_nonunion_paths(), and make_union_unique().

◆ generate_append_tlist()

static List * generate_append_tlist ( List colTypes,
List colCollations,
bool  flag,
List input_tlists,
List refnames_tlist 
)
static

Definition at line 1279 of file prepunion.c.

1283 {
1284  List *tlist = NIL;
1285  int resno = 1;
1286  ListCell *curColType;
1287  ListCell *curColCollation;
1288  ListCell *ref_tl_item;
1289  int colindex;
1290  TargetEntry *tle;
1291  Node *expr;
1292  ListCell *tlistl;
1293  int32 *colTypmods;
1294 
1295  /*
1296  * First extract typmods to use.
1297  *
1298  * If the inputs all agree on type and typmod of a particular column, use
1299  * that typmod; else use -1.
1300  */
1301  colTypmods = (int32 *) palloc(list_length(colTypes) * sizeof(int32));
1302 
1303  foreach(tlistl, input_tlists)
1304  {
1305  List *subtlist = (List *) lfirst(tlistl);
1306  ListCell *subtlistl;
1307 
1308  curColType = list_head(colTypes);
1309  colindex = 0;
1310  foreach(subtlistl, subtlist)
1311  {
1312  TargetEntry *subtle = (TargetEntry *) lfirst(subtlistl);
1313 
1314  if (subtle->resjunk)
1315  continue;
1316  Assert(curColType != NULL);
1317  if (exprType((Node *) subtle->expr) == lfirst_oid(curColType))
1318  {
1319  /* If first subplan, copy the typmod; else compare */
1320  int32 subtypmod = exprTypmod((Node *) subtle->expr);
1321 
1322  if (tlistl == list_head(input_tlists))
1323  colTypmods[colindex] = subtypmod;
1324  else if (subtypmod != colTypmods[colindex])
1325  colTypmods[colindex] = -1;
1326  }
1327  else
1328  {
1329  /* types disagree, so force typmod to -1 */
1330  colTypmods[colindex] = -1;
1331  }
1332  curColType = lnext(colTypes, curColType);
1333  colindex++;
1334  }
1335  Assert(curColType == NULL);
1336  }
1337 
1338  /*
1339  * Now we can build the tlist for the Append.
1340  */
1341  colindex = 0;
1342  forthree(curColType, colTypes, curColCollation, colCollations,
1343  ref_tl_item, refnames_tlist)
1344  {
1345  Oid colType = lfirst_oid(curColType);
1346  int32 colTypmod = colTypmods[colindex++];
1347  Oid colColl = lfirst_oid(curColCollation);
1348  TargetEntry *reftle = (TargetEntry *) lfirst(ref_tl_item);
1349 
1350  Assert(reftle->resno == resno);
1351  Assert(!reftle->resjunk);
1352  expr = (Node *) makeVar(0,
1353  resno,
1354  colType,
1355  colTypmod,
1356  colColl,
1357  0);
1358  tle = makeTargetEntry((Expr *) expr,
1359  (AttrNumber) resno++,
1360  pstrdup(reftle->resname),
1361  false);
1362 
1363  /*
1364  * By convention, all non-resjunk columns in a setop tree have
1365  * ressortgroupref equal to their resno. In some cases the ref isn't
1366  * needed, but this is a cleaner way than modifying the tlist later.
1367  */
1368  tle->ressortgroupref = tle->resno;
1369 
1370  tlist = lappend(tlist, tle);
1371  }
1372 
1373  if (flag)
1374  {
1375  /* Add a resjunk flag column */
1376  /* flag value is shown as copied up from subplan */
1377  expr = (Node *) makeVar(0,
1378  resno,
1379  INT4OID,
1380  -1,
1381  InvalidOid,
1382  0);
1383  tle = makeTargetEntry((Expr *) expr,
1384  (AttrNumber) resno++,
1385  pstrdup("flag"),
1386  true);
1387  tlist = lappend(tlist, tle);
1388  }
1389 
1390  pfree(colTypmods);
1391 
1392  return tlist;
1393 }
int16 AttrNumber
Definition: attnum.h:21
signed int int32
Definition: c.h:430
Assert(fmt[strlen(fmt) - 1] !='\n')
List * lappend(List *list, void *datum)
Definition: list.c:338
TargetEntry * makeTargetEntry(Expr *expr, AttrNumber resno, char *resname, bool resjunk)
Definition: makefuncs.c:238
Var * makeVar(int varno, AttrNumber varattno, Oid vartype, int32 vartypmod, Oid varcollid, Index varlevelsup)
Definition: makefuncs.c:66
char * pstrdup(const char *in)
Definition: mcxt.c:1483
void pfree(void *pointer)
Definition: mcxt.c:1306
void * palloc(Size size)
Definition: mcxt.c:1199
Oid exprType(const Node *expr)
Definition: nodeFuncs.c:43
int32 exprTypmod(const Node *expr)
Definition: nodeFuncs.c:266
#define lfirst(lc)
Definition: pg_list.h:170
#define forthree(cell1, list1, cell2, list2, cell3, list3)
Definition: pg_list.h:510
static ListCell * list_head(const List *l)
Definition: pg_list.h:126
static ListCell * lnext(const List *l, const ListCell *c)
Definition: pg_list.h:341
#define lfirst_oid(lc)
Definition: pg_list.h:172
#define InvalidOid
Definition: postgres_ext.h:36
unsigned int Oid
Definition: postgres_ext.h:31
Definition: pg_list.h:52
Definition: nodes.h:118
Expr * expr
Definition: primnodes.h:1555
char * resname
Definition: primnodes.h:1557
AttrNumber resno
Definition: primnodes.h:1556
bool resjunk
Definition: primnodes.h:1562
Index ressortgroupref
Definition: primnodes.h:1558
char * flag(int b)
Definition: test-ctype.c:33

References Assert(), TargetEntry::expr, exprType(), exprTypmod(), flag(), forthree, InvalidOid, lappend(), lfirst, lfirst_oid, list_head(), list_length(), lnext(), makeTargetEntry(), makeVar(), NIL, palloc(), pfree(), pstrdup(), TargetEntry::resjunk, TargetEntry::resname, TargetEntry::resno, and TargetEntry::ressortgroupref.

Referenced by generate_nonunion_paths(), generate_recursion_path(), and generate_union_paths().

◆ generate_nonunion_paths()

static RelOptInfo * generate_nonunion_paths ( SetOperationStmt op,
PlannerInfo root,
List refnames_tlist,
List **  pTargetList 
)
static

Definition at line 707 of file prepunion.c.

710 {
711  RelOptInfo *result_rel;
712  RelOptInfo *lrel,
713  *rrel;
714  double save_fraction = root->tuple_fraction;
715  Path *lpath,
716  *rpath,
717  *path;
718  List *lpath_tlist,
719  *rpath_tlist,
720  *tlist_list,
721  *tlist,
722  *groupList,
723  *pathlist;
724  double dLeftGroups,
725  dRightGroups,
726  dNumGroups,
727  dNumOutputRows;
728  bool use_hash;
729  SetOpCmd cmd;
730  int firstFlag;
731 
732  /*
733  * Tell children to fetch all tuples.
734  */
735  root->tuple_fraction = 0.0;
736 
737  /* Recurse on children, ensuring their outputs are marked */
738  lrel = recurse_set_operations(op->larg, root,
739  op->colTypes, op->colCollations,
740  false, 0,
741  refnames_tlist,
742  &lpath_tlist,
743  &dLeftGroups);
744  lpath = lrel->cheapest_total_path;
745  rrel = recurse_set_operations(op->rarg, root,
746  op->colTypes, op->colCollations,
747  false, 1,
748  refnames_tlist,
749  &rpath_tlist,
750  &dRightGroups);
751  rpath = rrel->cheapest_total_path;
752 
753  /* Undo effects of forcing tuple_fraction to 0 */
754  root->tuple_fraction = save_fraction;
755 
756  /*
757  * For EXCEPT, we must put the left input first. For INTERSECT, either
758  * order should give the same results, and we prefer to put the smaller
759  * input first in order to minimize the size of the hash table in the
760  * hashing case. "Smaller" means the one with the fewer groups.
761  */
762  if (op->op == SETOP_EXCEPT || dLeftGroups <= dRightGroups)
763  {
764  pathlist = list_make2(lpath, rpath);
765  tlist_list = list_make2(lpath_tlist, rpath_tlist);
766  firstFlag = 0;
767  }
768  else
769  {
770  pathlist = list_make2(rpath, lpath);
771  tlist_list = list_make2(rpath_tlist, lpath_tlist);
772  firstFlag = 1;
773  }
774 
775  /*
776  * Generate tlist for Append plan node.
777  *
778  * The tlist for an Append plan isn't important as far as the Append is
779  * concerned, but we must make it look real anyway for the benefit of the
780  * next plan level up. In fact, it has to be real enough that the flag
781  * column is shown as a variable not a constant, else setrefs.c will get
782  * confused.
783  */
784  tlist = generate_append_tlist(op->colTypes, op->colCollations, true,
785  tlist_list, refnames_tlist);
786 
787  *pTargetList = tlist;
788 
789  /* Build result relation. */
790  result_rel = fetch_upper_rel(root, UPPERREL_SETOP,
791  bms_union(lrel->relids, rrel->relids));
792  result_rel->reltarget = create_pathtarget(root, tlist);
793 
794  /*
795  * Append the child results together.
796  */
797  path = (Path *) create_append_path(root, result_rel, pathlist, NIL,
798  NIL, NULL, 0, false, -1);
799 
800  /* Identify the grouping semantics */
801  groupList = generate_setop_grouplist(op, tlist);
802 
803  /*
804  * Estimate number of distinct groups that we'll need hashtable entries
805  * for; this is the size of the left-hand input for EXCEPT, or the smaller
806  * input for INTERSECT. Also estimate the number of eventual output rows.
807  * In non-ALL cases, we estimate each group produces one output row; in
808  * ALL cases use the relevant relation size. These are worst-case
809  * estimates, of course, but we need to be conservative.
810  */
811  if (op->op == SETOP_EXCEPT)
812  {
813  dNumGroups = dLeftGroups;
814  dNumOutputRows = op->all ? lpath->rows : dNumGroups;
815  }
816  else
817  {
818  dNumGroups = Min(dLeftGroups, dRightGroups);
819  dNumOutputRows = op->all ? Min(lpath->rows, rpath->rows) : dNumGroups;
820  }
821 
822  /*
823  * Decide whether to hash or sort, and add a sort node if needed.
824  */
825  use_hash = choose_hashed_setop(root, groupList, path,
826  dNumGroups, dNumOutputRows,
827  (op->op == SETOP_INTERSECT) ? "INTERSECT" : "EXCEPT");
828 
829  if (groupList && !use_hash)
830  path = (Path *) create_sort_path(root,
831  result_rel,
832  path,
834  groupList,
835  tlist),
836  -1.0);
837 
838  /*
839  * Finally, add a SetOp path node to generate the correct output.
840  */
841  switch (op->op)
842  {
843  case SETOP_INTERSECT:
845  break;
846  case SETOP_EXCEPT:
848  break;
849  default:
850  elog(ERROR, "unrecognized set op: %d", (int) op->op);
851  cmd = SETOPCMD_INTERSECT; /* keep compiler quiet */
852  break;
853  }
854  path = (Path *) create_setop_path(root,
855  result_rel,
856  path,
857  cmd,
858  use_hash ? SETOP_HASHED : SETOP_SORTED,
859  groupList,
860  list_length(op->colTypes) + 1,
861  use_hash ? firstFlag : -1,
862  dNumGroups,
863  dNumOutputRows);
864 
865  result_rel->rows = path->rows;
866  add_path(result_rel, path);
867  return result_rel;
868 }
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:226
#define Min(x, y)
Definition: c.h:937
SetOpCmd
Definition: nodes.h:394
@ SETOPCMD_EXCEPT
Definition: nodes.h:397
@ SETOPCMD_EXCEPT_ALL
Definition: nodes.h:398
@ SETOPCMD_INTERSECT_ALL
Definition: nodes.h:396
@ SETOPCMD_INTERSECT
Definition: nodes.h:395
@ SETOP_HASHED
Definition: nodes.h:404
@ SETOP_SORTED
Definition: nodes.h:403
@ SETOP_INTERSECT
Definition: parsenodes.h:1720
@ SETOP_EXCEPT
Definition: parsenodes.h:1721
List * make_pathkeys_for_sortclauses(PlannerInfo *root, List *sortclauses, List *tlist)
Definition: pathkeys.c:1152
AppendPath * create_append_path(PlannerInfo *root, RelOptInfo *rel, List *subpaths, List *partial_subpaths, List *pathkeys, Relids required_outer, int parallel_workers, bool parallel_aware, double rows)
Definition: pathnode.c:1244
SortPath * create_sort_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, List *pathkeys, double limit_tuples)
Definition: pathnode.c:2961
SetOpPath * create_setop_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, SetOpCmd cmd, SetOpStrategy strategy, List *distinctList, AttrNumber flagColIdx, int firstFlag, double numGroups, double outputRows)
Definition: pathnode.c:3486
void add_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:422
@ UPPERREL_SETOP
Definition: pathnodes.h:71
#define list_make2(x1, x2)
Definition: pg_list.h:212
static List * generate_setop_grouplist(SetOperationStmt *op, List *targetlist)
Definition: prepunion.c:1407
static bool choose_hashed_setop(PlannerInfo *root, List *groupClauses, Path *input_path, double dNumGroups, double dNumOutputRows, const char *construct)
Definition: prepunion.c:1023
static List * generate_append_tlist(List *colTypes, List *colCollations, bool flag, List *input_tlists, List *refnames_tlist)
Definition: prepunion.c:1279
static RelOptInfo * recurse_set_operations(Node *setOp, PlannerInfo *root, List *colTypes, List *colCollations, bool junkOK, int flag, List *refnames_tlist, List **pTargetList, double *pNumGroups)
Definition: prepunion.c:208
RelOptInfo * fetch_upper_rel(PlannerInfo *root, UpperRelationKind kind, Relids relids)
Definition: relnode.c:1211
Relids relids
Definition: pathnodes.h:821
struct PathTarget * reltarget
Definition: pathnodes.h:843
struct Path * cheapest_total_path
Definition: pathnodes.h:852
Cardinality rows
Definition: pathnodes.h:827
List * colCollations
Definition: parsenodes.h:1805
SetOperation op
Definition: parsenodes.h:1796
#define create_pathtarget(root, tlist)
Definition: tlist.h:53

References add_path(), SetOperationStmt::all, bms_union(), RelOptInfo::cheapest_total_path, choose_hashed_setop(), SetOperationStmt::colCollations, SetOperationStmt::colTypes, create_append_path(), create_pathtarget, create_setop_path(), create_sort_path(), elog(), ERROR, fetch_upper_rel(), generate_append_tlist(), generate_setop_grouplist(), SetOperationStmt::larg, list_length(), list_make2, make_pathkeys_for_sortclauses(), Min, NIL, SetOperationStmt::op, SetOperationStmt::rarg, recurse_set_operations(), RelOptInfo::relids, RelOptInfo::reltarget, RelOptInfo::rows, Path::rows, SETOP_EXCEPT, SETOP_HASHED, SETOP_INTERSECT, SETOP_SORTED, SETOPCMD_EXCEPT, SETOPCMD_EXCEPT_ALL, SETOPCMD_INTERSECT, SETOPCMD_INTERSECT_ALL, PlannerInfo::tuple_fraction, and UPPERREL_SETOP.

Referenced by recurse_set_operations().

◆ generate_recursion_path()

static RelOptInfo * generate_recursion_path ( SetOperationStmt setOp,
PlannerInfo root,
List refnames_tlist,
List **  pTargetList 
)
static

Definition at line 441 of file prepunion.c.

444 {
445  RelOptInfo *result_rel;
446  Path *path;
447  RelOptInfo *lrel,
448  *rrel;
449  Path *lpath;
450  Path *rpath;
451  List *lpath_tlist;
452  List *rpath_tlist;
453  List *tlist;
454  List *groupList;
455  double dNumGroups;
456 
457  /* Parser should have rejected other cases */
458  if (setOp->op != SETOP_UNION)
459  elog(ERROR, "only UNION queries can be recursive");
460  /* Worktable ID should be assigned */
461  Assert(root->wt_param_id >= 0);
462 
463  /*
464  * Unlike a regular UNION node, process the left and right inputs
465  * separately without any intention of combining them into one Append.
466  */
467  lrel = recurse_set_operations(setOp->larg, root,
468  setOp->colTypes, setOp->colCollations,
469  false, -1,
470  refnames_tlist,
471  &lpath_tlist,
472  NULL);
473  lpath = lrel->cheapest_total_path;
474  /* The right path will want to look at the left one ... */
475  root->non_recursive_path = lpath;
476  rrel = recurse_set_operations(setOp->rarg, root,
477  setOp->colTypes, setOp->colCollations,
478  false, -1,
479  refnames_tlist,
480  &rpath_tlist,
481  NULL);
482  rpath = rrel->cheapest_total_path;
483  root->non_recursive_path = NULL;
484 
485  /*
486  * Generate tlist for RecursiveUnion path node --- same as in Append cases
487  */
488  tlist = generate_append_tlist(setOp->colTypes, setOp->colCollations, false,
489  list_make2(lpath_tlist, rpath_tlist),
490  refnames_tlist);
491 
492  *pTargetList = tlist;
493 
494  /* Build result relation. */
495  result_rel = fetch_upper_rel(root, UPPERREL_SETOP,
496  bms_union(lrel->relids, rrel->relids));
497  result_rel->reltarget = create_pathtarget(root, tlist);
498 
499  /*
500  * If UNION, identify the grouping operators
501  */
502  if (setOp->all)
503  {
504  groupList = NIL;
505  dNumGroups = 0;
506  }
507  else
508  {
509  /* Identify the grouping semantics */
510  groupList = generate_setop_grouplist(setOp, tlist);
511 
512  /* We only support hashing here */
513  if (!grouping_is_hashable(groupList))
514  ereport(ERROR,
515  (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
516  errmsg("could not implement recursive UNION"),
517  errdetail("All column datatypes must be hashable.")));
518 
519  /*
520  * For the moment, take the number of distinct groups as equal to the
521  * total input size, ie, the worst case.
522  */
523  dNumGroups = lpath->rows + rpath->rows * 10;
524  }
525 
526  /*
527  * And make the path node.
528  */
529  path = (Path *) create_recursiveunion_path(root,
530  result_rel,
531  lpath,
532  rpath,
533  result_rel->reltarget,
534  groupList,
535  root->wt_param_id,
536  dNumGroups);
537 
538  add_path(result_rel, path);
539  postprocess_setop_rel(root, result_rel);
540  return result_rel;
541 }
@ SETOP_UNION
Definition: parsenodes.h:1719
RecursiveUnionPath * create_recursiveunion_path(PlannerInfo *root, RelOptInfo *rel, Path *leftpath, Path *rightpath, PathTarget *target, List *distinctList, int wtParam, double numGroups)
Definition: pathnode.c:3548
static void postprocess_setop_rel(PlannerInfo *root, RelOptInfo *rel)
Definition: prepunion.c:1005
struct Path * non_recursive_path
Definition: pathnodes.h:485
int wt_param_id
Definition: pathnodes.h:483

References add_path(), SetOperationStmt::all, Assert(), bms_union(), RelOptInfo::cheapest_total_path, SetOperationStmt::colCollations, SetOperationStmt::colTypes, create_pathtarget, create_recursiveunion_path(), elog(), ereport, errcode(), errdetail(), errmsg(), ERROR, fetch_upper_rel(), generate_append_tlist(), generate_setop_grouplist(), grouping_is_hashable(), SetOperationStmt::larg, list_make2, NIL, PlannerInfo::non_recursive_path, SetOperationStmt::op, postprocess_setop_rel(), SetOperationStmt::rarg, recurse_set_operations(), RelOptInfo::relids, RelOptInfo::reltarget, Path::rows, SETOP_UNION, UPPERREL_SETOP, and PlannerInfo::wt_param_id.

Referenced by plan_set_operations().

◆ generate_setop_grouplist()

static List * generate_setop_grouplist ( SetOperationStmt op,
List targetlist 
)
static

Definition at line 1407 of file prepunion.c.

1408 {
1409  List *grouplist = copyObject(op->groupClauses);
1410  ListCell *lg;
1411  ListCell *lt;
1412 
1413  lg = list_head(grouplist);
1414  foreach(lt, targetlist)
1415  {
1416  TargetEntry *tle = (TargetEntry *) lfirst(lt);
1417  SortGroupClause *sgc;
1418 
1419  if (tle->resjunk)
1420  {
1421  /* resjunk columns should not have sortgrouprefs */
1422  Assert(tle->ressortgroupref == 0);
1423  continue; /* ignore resjunk columns */
1424  }
1425 
1426  /* non-resjunk columns should have sortgroupref = resno */
1427  Assert(tle->ressortgroupref == tle->resno);
1428 
1429  /* non-resjunk columns should have grouping clauses */
1430  Assert(lg != NULL);
1431  sgc = (SortGroupClause *) lfirst(lg);
1432  lg = lnext(grouplist, lg);
1433  Assert(sgc->tleSortGroupRef == 0);
1434 
1435  sgc->tleSortGroupRef = tle->ressortgroupref;
1436  }
1437  Assert(lg == NULL);
1438  return grouplist;
1439 }
#define copyObject(obj)
Definition: nodes.h:233
Index tleSortGroupRef
Definition: parsenodes.h:1320

References Assert(), copyObject, SetOperationStmt::groupClauses, lfirst, list_head(), lnext(), TargetEntry::resjunk, TargetEntry::resno, TargetEntry::ressortgroupref, and SortGroupClause::tleSortGroupRef.

Referenced by generate_nonunion_paths(), generate_recursion_path(), and make_union_unique().

◆ generate_setop_tlist()

static List * generate_setop_tlist ( List colTypes,
List colCollations,
int  flag,
Index  varno,
bool  hack_constants,
List input_tlist,
List refnames_tlist,
bool trivial_tlist 
)
static

Definition at line 1130 of file prepunion.c.

1137 {
1138  List *tlist = NIL;
1139  int resno = 1;
1140  ListCell *ctlc,
1141  *cclc,
1142  *itlc,
1143  *rtlc;
1144  TargetEntry *tle;
1145  Node *expr;
1146 
1147  *trivial_tlist = true; /* until proven differently */
1148 
1149  forfour(ctlc, colTypes, cclc, colCollations,
1150  itlc, input_tlist, rtlc, refnames_tlist)
1151  {
1152  Oid colType = lfirst_oid(ctlc);
1153  Oid colColl = lfirst_oid(cclc);
1154  TargetEntry *inputtle = (TargetEntry *) lfirst(itlc);
1155  TargetEntry *reftle = (TargetEntry *) lfirst(rtlc);
1156 
1157  Assert(inputtle->resno == resno);
1158  Assert(reftle->resno == resno);
1159  Assert(!inputtle->resjunk);
1160  Assert(!reftle->resjunk);
1161 
1162  /*
1163  * Generate columns referencing input columns and having appropriate
1164  * data types and column names. Insert datatype coercions where
1165  * necessary.
1166  *
1167  * HACK: constants in the input's targetlist are copied up as-is
1168  * rather than being referenced as subquery outputs. This is mainly
1169  * to ensure that when we try to coerce them to the output column's
1170  * datatype, the right things happen for UNKNOWN constants. But do
1171  * this only at the first level of subquery-scan plans; we don't want
1172  * phony constants appearing in the output tlists of upper-level
1173  * nodes!
1174  *
1175  * Note that copying a constant doesn't in itself require us to mark
1176  * the tlist nontrivial; see trivial_subqueryscan() in setrefs.c.
1177  */
1178  if (hack_constants && inputtle->expr && IsA(inputtle->expr, Const))
1179  expr = (Node *) inputtle->expr;
1180  else
1181  expr = (Node *) makeVar(varno,
1182  inputtle->resno,
1183  exprType((Node *) inputtle->expr),
1184  exprTypmod((Node *) inputtle->expr),
1185  exprCollation((Node *) inputtle->expr),
1186  0);
1187 
1188  if (exprType(expr) != colType)
1189  {
1190  /*
1191  * Note: it's not really cool to be applying coerce_to_common_type
1192  * here; one notable point is that assign_expr_collations never
1193  * gets run on any generated nodes. For the moment that's not a
1194  * problem because we force the correct exposed collation below.
1195  * It would likely be best to make the parser generate the correct
1196  * output tlist for every set-op to begin with, though.
1197  */
1198  expr = coerce_to_common_type(NULL, /* no UNKNOWNs here */
1199  expr,
1200  colType,
1201  "UNION/INTERSECT/EXCEPT");
1202  *trivial_tlist = false; /* the coercion makes it not trivial */
1203  }
1204 
1205  /*
1206  * Ensure the tlist entry's exposed collation matches the set-op. This
1207  * is necessary because plan_set_operations() reports the result
1208  * ordering as a list of SortGroupClauses, which don't carry collation
1209  * themselves but just refer to tlist entries. If we don't show the
1210  * right collation then planner.c might do the wrong thing in
1211  * higher-level queries.
1212  *
1213  * Note we use RelabelType, not CollateExpr, since this expression
1214  * will reach the executor without any further processing.
1215  */
1216  if (exprCollation(expr) != colColl)
1217  {
1218  expr = applyRelabelType(expr,
1219  exprType(expr), exprTypmod(expr), colColl,
1220  COERCE_IMPLICIT_CAST, -1, false);
1221  *trivial_tlist = false; /* the relabel makes it not trivial */
1222  }
1223 
1224  tle = makeTargetEntry((Expr *) expr,
1225  (AttrNumber) resno++,
1226  pstrdup(reftle->resname),
1227  false);
1228 
1229  /*
1230  * By convention, all non-resjunk columns in a setop tree have
1231  * ressortgroupref equal to their resno. In some cases the ref isn't
1232  * needed, but this is a cleaner way than modifying the tlist later.
1233  */
1234  tle->ressortgroupref = tle->resno;
1235 
1236  tlist = lappend(tlist, tle);
1237  }
1238 
1239  if (flag >= 0)
1240  {
1241  /* Add a resjunk flag column */
1242  /* flag value is the given constant */
1243  expr = (Node *) makeConst(INT4OID,
1244  -1,
1245  InvalidOid,
1246  sizeof(int32),
1248  false,
1249  true);
1250  tle = makeTargetEntry((Expr *) expr,
1251  (AttrNumber) resno++,
1252  pstrdup("flag"),
1253  true);
1254  tlist = lappend(tlist, tle);
1255  *trivial_tlist = false; /* the extra entry makes it not trivial */
1256  }
1257 
1258  return tlist;
1259 }
Const * makeConst(Oid consttype, int32 consttypmod, Oid constcollid, int constlen, Datum constvalue, bool constisnull, bool constbyval)
Definition: makefuncs.c:299
Oid exprCollation(const Node *expr)
Definition: nodeFuncs.c:764
Node * applyRelabelType(Node *arg, Oid rtype, int32 rtypmod, Oid rcollid, CoercionForm rformat, int rlocation, bool overwrite_ok)
Definition: nodeFuncs.c:579
#define IsA(nodeptr, _type_)
Definition: nodes.h:168
Node * coerce_to_common_type(ParseState *pstate, Node *node, Oid targetTypeId, const char *context)
#define forfour(cell1, list1, cell2, list2, cell3, list3, cell4, list4)
Definition: pg_list.h:522
static Datum Int32GetDatum(int32 X)
Definition: postgres.h:560
@ COERCE_IMPLICIT_CAST
Definition: primnodes.h:588

References applyRelabelType(), Assert(), COERCE_IMPLICIT_CAST, coerce_to_common_type(), TargetEntry::expr, exprCollation(), exprType(), exprTypmod(), flag(), forfour, Int32GetDatum(), InvalidOid, IsA, lappend(), lfirst, lfirst_oid, makeConst(), makeTargetEntry(), makeVar(), NIL, pstrdup(), TargetEntry::resjunk, TargetEntry::resname, TargetEntry::resno, and TargetEntry::ressortgroupref.

Referenced by recurse_set_operations().

◆ generate_union_paths()

static RelOptInfo * generate_union_paths ( SetOperationStmt op,
PlannerInfo root,
List refnames_tlist,
List **  pTargetList 
)
static

Definition at line 547 of file prepunion.c.

550 {
551  Relids relids = NULL;
552  RelOptInfo *result_rel;
553  double save_fraction = root->tuple_fraction;
554  ListCell *lc;
555  List *pathlist = NIL;
556  List *partial_pathlist = NIL;
557  bool partial_paths_valid = true;
558  bool consider_parallel = true;
559  List *rellist;
560  List *tlist_list;
561  List *tlist;
562  Path *path;
563 
564  /*
565  * If plain UNION, tell children to fetch all tuples.
566  *
567  * Note: in UNION ALL, we pass the top-level tuple_fraction unmodified to
568  * each arm of the UNION ALL. One could make a case for reducing the
569  * tuple fraction for later arms (discounting by the expected size of the
570  * earlier arms' results) but it seems not worth the trouble. The normal
571  * case where tuple_fraction isn't already zero is a LIMIT at top level,
572  * and passing it down as-is is usually enough to get the desired result
573  * of preferring fast-start plans.
574  */
575  if (!op->all)
576  root->tuple_fraction = 0.0;
577 
578  /*
579  * If any of my children are identical UNION nodes (same op, all-flag, and
580  * colTypes) then they can be merged into this node so that we generate
581  * only one Append and unique-ification for the lot. Recurse to find such
582  * nodes and compute their children's paths.
583  */
584  rellist = plan_union_children(root, op, refnames_tlist, &tlist_list);
585 
586  /*
587  * Generate tlist for Append plan node.
588  *
589  * The tlist for an Append plan isn't important as far as the Append is
590  * concerned, but we must make it look real anyway for the benefit of the
591  * next plan level up.
592  */
593  tlist = generate_append_tlist(op->colTypes, op->colCollations, false,
594  tlist_list, refnames_tlist);
595 
596  *pTargetList = tlist;
597 
598  /* Build path lists and relid set. */
599  foreach(lc, rellist)
600  {
601  RelOptInfo *rel = lfirst(lc);
602 
603  pathlist = lappend(pathlist, rel->cheapest_total_path);
604 
605  if (consider_parallel)
606  {
607  if (!rel->consider_parallel)
608  {
609  consider_parallel = false;
610  partial_paths_valid = false;
611  }
612  else if (rel->partial_pathlist == NIL)
613  partial_paths_valid = false;
614  else
615  partial_pathlist = lappend(partial_pathlist,
616  linitial(rel->partial_pathlist));
617  }
618 
619  relids = bms_union(relids, rel->relids);
620  }
621 
622  /* Build result relation. */
623  result_rel = fetch_upper_rel(root, UPPERREL_SETOP, relids);
624  result_rel->reltarget = create_pathtarget(root, tlist);
625  result_rel->consider_parallel = consider_parallel;
626 
627  /*
628  * Append the child results together.
629  */
630  path = (Path *) create_append_path(root, result_rel, pathlist, NIL,
631  NIL, NULL, 0, false, -1);
632 
633  /*
634  * For UNION ALL, we just need the Append path. For UNION, need to add
635  * node(s) to remove duplicates.
636  */
637  if (!op->all)
638  path = make_union_unique(op, path, tlist, root);
639 
640  add_path(result_rel, path);
641 
642  /*
643  * Estimate number of groups. For now we just assume the output is unique
644  * --- this is certainly true for the UNION case, and we want worst-case
645  * estimates anyway.
646  */
647  result_rel->rows = path->rows;
648 
649  /*
650  * Now consider doing the same thing using the partial paths plus Append
651  * plus Gather.
652  */
653  if (partial_paths_valid)
654  {
655  Path *ppath;
656  int parallel_workers = 0;
657 
658  /* Find the highest number of workers requested for any subpath. */
659  foreach(lc, partial_pathlist)
660  {
661  Path *subpath = lfirst(lc);
662 
663  parallel_workers = Max(parallel_workers,
664  subpath->parallel_workers);
665  }
666  Assert(parallel_workers > 0);
667 
668  /*
669  * If the use of parallel append is permitted, always request at least
670  * log2(# of children) paths. We assume it can be useful to have
671  * extra workers in this case because they will be spread out across
672  * the children. The precise formula is just a guess; see
673  * add_paths_to_append_rel.
674  */
676  {
677  parallel_workers = Max(parallel_workers,
678  pg_leftmost_one_pos32(list_length(partial_pathlist)) + 1);
679  parallel_workers = Min(parallel_workers,
681  }
682  Assert(parallel_workers > 0);
683 
684  ppath = (Path *)
685  create_append_path(root, result_rel, NIL, partial_pathlist,
686  NIL, NULL,
687  parallel_workers, enable_parallel_append,
688  -1);
689  ppath = (Path *)
690  create_gather_path(root, result_rel, ppath,
691  result_rel->reltarget, NULL, NULL);
692  if (!op->all)
693  ppath = make_union_unique(op, ppath, tlist, root);
694  add_path(result_rel, ppath);
695  }
696 
697  /* Undo effects of possibly forcing tuple_fraction to 0 */
698  root->tuple_fraction = save_fraction;
699 
700  return result_rel;
701 }
#define Max(x, y)
Definition: c.h:931
int max_parallel_workers_per_gather
Definition: costsize.c:133
bool enable_parallel_append
Definition: costsize.c:151
Datum subpath(PG_FUNCTION_ARGS)
Definition: ltree_op.c:241
GatherPath * create_gather_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, Relids required_outer, double *rows)
Definition: pathnode.c:1964
static int pg_leftmost_one_pos32(uint32 word)
Definition: pg_bitutils.h:26
#define linitial(l)
Definition: pg_list.h:176
static Path * make_union_unique(SetOperationStmt *op, Path *path, List *tlist, PlannerInfo *root)
Definition: prepunion.c:943
static List * plan_union_children(PlannerInfo *root, SetOperationStmt *top_union, List *refnames_tlist, List **tlist_list)
Definition: prepunion.c:884
bool consider_parallel
Definition: pathnodes.h:837
List * partial_pathlist
Definition: pathnodes.h:850

References add_path(), SetOperationStmt::all, Assert(), bms_union(), RelOptInfo::cheapest_total_path, SetOperationStmt::colCollations, SetOperationStmt::colTypes, RelOptInfo::consider_parallel, create_append_path(), create_gather_path(), create_pathtarget, enable_parallel_append, fetch_upper_rel(), generate_append_tlist(), lappend(), lfirst, linitial, list_length(), make_union_unique(), Max, max_parallel_workers_per_gather, Min, NIL, RelOptInfo::partial_pathlist, pg_leftmost_one_pos32(), plan_union_children(), RelOptInfo::relids, RelOptInfo::reltarget, RelOptInfo::rows, Path::rows, subpath(), PlannerInfo::tuple_fraction, and UPPERREL_SETOP.

Referenced by recurse_set_operations().

◆ make_union_unique()

static Path * make_union_unique ( SetOperationStmt op,
Path path,
List tlist,
PlannerInfo root 
)
static

Definition at line 943 of file prepunion.c.

945 {
946  RelOptInfo *result_rel = fetch_upper_rel(root, UPPERREL_SETOP, NULL);
947  List *groupList;
948  double dNumGroups;
949 
950  /* Identify the grouping semantics */
951  groupList = generate_setop_grouplist(op, tlist);
952 
953  /*
954  * XXX for the moment, take the number of distinct groups as equal to the
955  * total input size, ie, the worst case. This is too conservative, but
956  * it's not clear how to get a decent estimate of the true size. One
957  * should note as well the propensity of novices to write UNION rather
958  * than UNION ALL even when they don't expect any duplicates...
959  */
960  dNumGroups = path->rows;
961 
962  /* Decide whether to hash or sort */
963  if (choose_hashed_setop(root, groupList, path,
964  dNumGroups, dNumGroups,
965  "UNION"))
966  {
967  /* Hashed aggregate plan --- no sort needed */
968  path = (Path *) create_agg_path(root,
969  result_rel,
970  path,
971  create_pathtarget(root, tlist),
972  AGG_HASHED,
974  groupList,
975  NIL,
976  NULL,
977  dNumGroups);
978  }
979  else
980  {
981  /* Sort and Unique */
982  if (groupList)
983  path = (Path *)
984  create_sort_path(root,
985  result_rel,
986  path,
988  groupList,
989  tlist),
990  -1.0);
991  path = (Path *) create_upper_unique_path(root,
992  result_rel,
993  path,
994  list_length(path->pathkeys),
995  dNumGroups);
996  }
997 
998  return path;
999 }
@ AGGSPLIT_SIMPLE
Definition: nodes.h:374
UpperUniquePath * create_upper_unique_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, int numCols, double numGroups)
Definition: pathnode.c:3064
AggPath * create_agg_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target, AggStrategy aggstrategy, AggSplit aggsplit, List *groupClause, List *qual, const AggClauseCosts *aggcosts, double numGroups)
Definition: pathnode.c:3116
List * pathkeys
Definition: pathnodes.h:1549

References AGG_HASHED, AGGSPLIT_SIMPLE, choose_hashed_setop(), create_agg_path(), create_pathtarget, create_sort_path(), create_upper_unique_path(), fetch_upper_rel(), generate_setop_grouplist(), list_length(), make_pathkeys_for_sortclauses(), NIL, Path::pathkeys, Path::rows, and UPPERREL_SETOP.

Referenced by generate_union_paths().

◆ plan_set_operations()

RelOptInfo* plan_set_operations ( PlannerInfo root)

Definition at line 104 of file prepunion.c.

105 {
106  Query *parse = root->parse;
107  SetOperationStmt *topop = castNode(SetOperationStmt, parse->setOperations);
108  Node *node;
109  RangeTblEntry *leftmostRTE;
110  Query *leftmostQuery;
111  RelOptInfo *setop_rel;
112  List *top_tlist;
113 
114  Assert(topop);
115 
116  /* check for unsupported stuff */
117  Assert(parse->jointree->fromlist == NIL);
118  Assert(parse->jointree->quals == NULL);
119  Assert(parse->groupClause == NIL);
120  Assert(parse->havingQual == NULL);
121  Assert(parse->windowClause == NIL);
122  Assert(parse->distinctClause == NIL);
123 
124  /*
125  * In the outer query level, we won't have any true equivalences to deal
126  * with; but we do want to be able to make pathkeys, which will require
127  * single-member EquivalenceClasses. Indicate that EC merging is complete
128  * so that pathkeys.c won't complain.
129  */
130  Assert(root->eq_classes == NIL);
131  root->ec_merging_done = true;
132 
133  /*
134  * We'll need to build RelOptInfos for each of the leaf subqueries, which
135  * are RTE_SUBQUERY rangetable entries in this Query. Prepare the index
136  * arrays for those, and for AppendRelInfos in case they're needed.
137  */
139 
140  /*
141  * Find the leftmost component Query. We need to use its column names for
142  * all generated tlists (else SELECT INTO won't work right).
143  */
144  node = topop->larg;
145  while (node && IsA(node, SetOperationStmt))
146  node = ((SetOperationStmt *) node)->larg;
147  Assert(node && IsA(node, RangeTblRef));
148  leftmostRTE = root->simple_rte_array[((RangeTblRef *) node)->rtindex];
149  leftmostQuery = leftmostRTE->subquery;
150  Assert(leftmostQuery != NULL);
151 
152  /*
153  * If the topmost node is a recursive union, it needs special processing.
154  */
155  if (root->hasRecursion)
156  {
157  setop_rel = generate_recursion_path(topop, root,
158  leftmostQuery->targetList,
159  &top_tlist);
160  }
161  else
162  {
163  /*
164  * Recurse on setOperations tree to generate paths for set ops. The
165  * final output paths should have just the column types shown as the
166  * output from the top-level node, plus possibly resjunk working
167  * columns (we can rely on upper-level nodes to deal with that).
168  */
169  setop_rel = recurse_set_operations((Node *) topop, root,
170  topop->colTypes, topop->colCollations,
171  true, -1,
172  leftmostQuery->targetList,
173  &top_tlist,
174  NULL);
175  }
176 
177  /* Must return the built tlist into root->processed_tlist. */
178  root->processed_tlist = top_tlist;
179 
180  return setop_rel;
181 }
#define castNode(_type_, nodeptr)
Definition: nodes.h:186
static RelOptInfo * generate_recursion_path(SetOperationStmt *setOp, PlannerInfo *root, List *refnames_tlist, List **pTargetList)
Definition: prepunion.c:441
static struct subre * parse(struct vars *v, int stopper, int type, struct state *init, struct state *final)
Definition: regcomp.c:717
void setup_simple_rel_arrays(PlannerInfo *root)
Definition: relnode.c:83
List * processed_tlist
Definition: pathnodes.h:415
bool hasRecursion
Definition: pathnodes.h:463
bool ec_merging_done
Definition: pathnodes.h:307
List * eq_classes
Definition: pathnodes.h:304
Query * parse
Definition: pathnodes.h:199
List * targetList
Definition: parsenodes.h:162
Query * subquery
Definition: parsenodes.h:1065

References Assert(), castNode, PlannerInfo::ec_merging_done, PlannerInfo::eq_classes, generate_recursion_path(), PlannerInfo::hasRecursion, IsA, SetOperationStmt::larg, NIL, parse(), PlannerInfo::parse, PlannerInfo::processed_tlist, recurse_set_operations(), setup_simple_rel_arrays(), RangeTblEntry::subquery, and Query::targetList.

Referenced by grouping_planner().

◆ plan_union_children()

static List * plan_union_children ( PlannerInfo root,
SetOperationStmt top_union,
List refnames_tlist,
List **  tlist_list 
)
static

Definition at line 884 of file prepunion.c.

888 {
889  List *pending_rels = list_make1(top_union);
890  List *result = NIL;
891  List *child_tlist;
892 
893  *tlist_list = NIL;
894 
895  while (pending_rels != NIL)
896  {
897  Node *setOp = linitial(pending_rels);
898 
899  pending_rels = list_delete_first(pending_rels);
900 
901  if (IsA(setOp, SetOperationStmt))
902  {
903  SetOperationStmt *op = (SetOperationStmt *) setOp;
904 
905  if (op->op == top_union->op &&
906  (op->all == top_union->all || op->all) &&
907  equal(op->colTypes, top_union->colTypes))
908  {
909  /* Same UNION, so fold children into parent */
910  pending_rels = lcons(op->rarg, pending_rels);
911  pending_rels = lcons(op->larg, pending_rels);
912  continue;
913  }
914  }
915 
916  /*
917  * Not same, so plan this child separately.
918  *
919  * Note we disallow any resjunk columns in child results. This is
920  * necessary since the Append node that implements the union won't do
921  * any projection, and upper levels will get confused if some of our
922  * output tuples have junk and some don't. This case only arises when
923  * we have an EXCEPT or INTERSECT as child, else there won't be
924  * resjunk anyway.
925  */
926  result = lappend(result, recurse_set_operations(setOp, root,
927  top_union->colTypes,
928  top_union->colCollations,
929  false, -1,
930  refnames_tlist,
931  &child_tlist,
932  NULL));
933  *tlist_list = lappend(*tlist_list, child_tlist);
934  }
935 
936  return result;
937 }
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:225
List * list_delete_first(List *list)
Definition: list.c:942
List * lcons(void *datum, List *list)
Definition: list.c:494
#define list_make1(x1)
Definition: pg_list.h:210

References SetOperationStmt::all, SetOperationStmt::colCollations, SetOperationStmt::colTypes, equal(), IsA, lappend(), SetOperationStmt::larg, lcons(), linitial, list_delete_first(), list_make1, NIL, SetOperationStmt::op, SetOperationStmt::rarg, and recurse_set_operations().

Referenced by generate_union_paths().

◆ postprocess_setop_rel()

static void postprocess_setop_rel ( PlannerInfo root,
RelOptInfo rel 
)
static

Definition at line 1005 of file prepunion.c.

1006 {
1007  /*
1008  * We don't currently worry about allowing FDWs to contribute paths to
1009  * this relation, but give extensions a chance.
1010  */
1012  (*create_upper_paths_hook) (root, UPPERREL_SETOP,
1013  NULL, rel, NULL);
1014 
1015  /* Select cheapest path */
1016  set_cheapest(rel);
1017 }
void set_cheapest(RelOptInfo *parent_rel)
Definition: pathnode.c:244
create_upper_paths_hook_type create_upper_paths_hook
Definition: planner.c:78

References create_upper_paths_hook, set_cheapest(), and UPPERREL_SETOP.

Referenced by generate_recursion_path(), and recurse_set_operations().

◆ recurse_set_operations()

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

Definition at line 208 of file prepunion.c.

214 {
215  RelOptInfo *rel = NULL; /* keep compiler quiet */
216 
217  /* Guard against stack overflow due to overly complex setop nests */
219 
220  if (IsA(setOp, RangeTblRef))
221  {
222  RangeTblRef *rtr = (RangeTblRef *) setOp;
223  RangeTblEntry *rte = root->simple_rte_array[rtr->rtindex];
224  Query *subquery = rte->subquery;
225  PlannerInfo *subroot;
226  RelOptInfo *final_rel;
227  Path *subpath;
228  Path *path;
229  List *tlist;
230  bool trivial_tlist;
231 
232  Assert(subquery != NULL);
233 
234  /* Build a RelOptInfo for this leaf subquery. */
235  rel = build_simple_rel(root, rtr->rtindex, NULL);
236 
237  /* plan_params should not be in use in current query level */
238  Assert(root->plan_params == NIL);
239 
240  /* Generate a subroot and Paths for the subquery */
241  subroot = rel->subroot = subquery_planner(root->glob, subquery,
242  root,
243  false,
244  root->tuple_fraction);
245 
246  /*
247  * It should not be possible for the primitive query to contain any
248  * cross-references to other primitive queries in the setop tree.
249  */
250  if (root->plan_params)
251  elog(ERROR, "unexpected outer reference in set operation subquery");
252 
253  /* Figure out the appropriate target list for this subquery. */
254  tlist = generate_setop_tlist(colTypes, colCollations,
255  flag,
256  rtr->rtindex,
257  true,
258  subroot->processed_tlist,
259  refnames_tlist,
260  &trivial_tlist);
261  rel->reltarget = create_pathtarget(root, tlist);
262 
263  /* Return the fully-fledged tlist to caller, too */
264  *pTargetList = tlist;
265 
266  /*
267  * Mark rel with estimated output rows, width, etc. Note that we have
268  * to do this before generating outer-query paths, else
269  * cost_subqueryscan is not happy.
270  */
271  set_subquery_size_estimates(root, rel);
272 
273  /*
274  * Since we may want to add a partial path to this relation, we must
275  * set its consider_parallel flag correctly.
276  */
277  final_rel = fetch_upper_rel(subroot, UPPERREL_FINAL, NULL);
278  rel->consider_parallel = final_rel->consider_parallel;
279 
280  /*
281  * For the moment, we consider only a single Path for the subquery.
282  * This should change soon (make it look more like
283  * set_subquery_pathlist).
284  */
286  root->tuple_fraction);
287 
288  /*
289  * Stick a SubqueryScanPath atop that.
290  *
291  * We don't bother to determine the subquery's output ordering since
292  * it won't be reflected in the set-op result anyhow; so just label
293  * the SubqueryScanPath with nil pathkeys. (XXX that should change
294  * soon too, likely.)
295  */
296  path = (Path *) create_subqueryscan_path(root, rel, subpath,
297  trivial_tlist,
298  NIL, NULL);
299 
300  add_path(rel, path);
301 
302  /*
303  * If we have a partial path for the child relation, we can use that
304  * to build a partial path for this relation. But there's no point in
305  * considering any path but the cheapest.
306  */
307  if (rel->consider_parallel && bms_is_empty(rel->lateral_relids) &&
308  final_rel->partial_pathlist != NIL)
309  {
310  Path *partial_subpath;
311  Path *partial_path;
312 
313  partial_subpath = linitial(final_rel->partial_pathlist);
314  partial_path = (Path *)
315  create_subqueryscan_path(root, rel, partial_subpath,
316  trivial_tlist,
317  NIL, NULL);
318  add_partial_path(rel, partial_path);
319  }
320 
321  /*
322  * Estimate number of groups if caller wants it. If the subquery used
323  * grouping or aggregation, its output is probably mostly unique
324  * anyway; otherwise do statistical estimation.
325  *
326  * XXX you don't really want to know about this: we do the estimation
327  * using the subquery's original targetlist expressions, not the
328  * subroot->processed_tlist which might seem more appropriate. The
329  * reason is that if the subquery is itself a setop, it may return a
330  * processed_tlist containing "varno 0" Vars generated by
331  * generate_append_tlist, and those would confuse estimate_num_groups
332  * mightily. We ought to get rid of the "varno 0" hack, but that
333  * requires a redesign of the parsetree representation of setops, so
334  * that there can be an RTE corresponding to each setop's output.
335  */
336  if (pNumGroups)
337  {
338  if (subquery->groupClause || subquery->groupingSets ||
339  subquery->distinctClause ||
340  subroot->hasHavingQual || subquery->hasAggs)
341  *pNumGroups = subpath->rows;
342  else
343  *pNumGroups = estimate_num_groups(subroot,
344  get_tlist_exprs(subquery->targetList, false),
345  subpath->rows,
346  NULL,
347  NULL);
348  }
349  }
350  else if (IsA(setOp, SetOperationStmt))
351  {
352  SetOperationStmt *op = (SetOperationStmt *) setOp;
353 
354  /* UNIONs are much different from INTERSECT/EXCEPT */
355  if (op->op == SETOP_UNION)
356  rel = generate_union_paths(op, root,
357  refnames_tlist,
358  pTargetList);
359  else
360  rel = generate_nonunion_paths(op, root,
361  refnames_tlist,
362  pTargetList);
363  if (pNumGroups)
364  *pNumGroups = rel->rows;
365 
366  /*
367  * If necessary, add a Result node to project the caller-requested
368  * output columns.
369  *
370  * XXX you don't really want to know about this: setrefs.c will apply
371  * fix_upper_expr() to the Result node's tlist. This would fail if the
372  * Vars generated by generate_setop_tlist() were not exactly equal()
373  * to the corresponding tlist entries of the subplan. However, since
374  * the subplan was generated by generate_union_paths() or
375  * generate_nonunion_paths(), and hence its tlist was generated by
376  * generate_append_tlist(), this will work. We just tell
377  * generate_setop_tlist() to use varno 0.
378  */
379  if (flag >= 0 ||
380  !tlist_same_datatypes(*pTargetList, colTypes, junkOK) ||
381  !tlist_same_collations(*pTargetList, colCollations, junkOK))
382  {
383  PathTarget *target;
384  bool trivial_tlist;
385  ListCell *lc;
386 
387  *pTargetList = generate_setop_tlist(colTypes, colCollations,
388  flag,
389  0,
390  false,
391  *pTargetList,
392  refnames_tlist,
393  &trivial_tlist);
394  target = create_pathtarget(root, *pTargetList);
395 
396  /* Apply projection to each path */
397  foreach(lc, rel->pathlist)
398  {
399  Path *subpath = (Path *) lfirst(lc);
400  Path *path;
401 
402  Assert(subpath->param_info == NULL);
403  path = apply_projection_to_path(root, subpath->parent,
404  subpath, target);
405  /* If we had to add a Result, path is different from subpath */
406  if (path != subpath)
407  lfirst(lc) = path;
408  }
409 
410  /* Apply projection to each partial path */
411  foreach(lc, rel->partial_pathlist)
412  {
413  Path *subpath = (Path *) lfirst(lc);
414  Path *path;
415 
416  Assert(subpath->param_info == NULL);
417 
418  /* avoid apply_projection_to_path, in case of multiple refs */
419  path = (Path *) create_projection_path(root, subpath->parent,
420  subpath, target);
421  lfirst(lc) = path;
422  }
423  }
424  }
425  else
426  {
427  elog(ERROR, "unrecognized node type: %d",
428  (int) nodeTag(setOp));
429  *pTargetList = NIL;
430  }
431 
432  postprocess_setop_rel(root, rel);
433 
434  return rel;
435 }
bool bms_is_empty(const Bitmapset *a)
Definition: bitmapset.c:704
void set_subquery_size_estimates(PlannerInfo *root, RelOptInfo *rel)
Definition: costsize.c:5541
#define nodeTag(nodeptr)
Definition: nodes.h:122
ProjectionPath * create_projection_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, PathTarget *target)
Definition: pathnode.c:2646
SubqueryScanPath * create_subqueryscan_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath, bool trivial_pathtarget, List *pathkeys, Relids required_outer)
Definition: pathnode.c:2008
void add_partial_path(RelOptInfo *parent_rel, Path *new_path)
Definition: pathnode.c:749
Path * apply_projection_to_path(PlannerInfo *root, RelOptInfo *rel, Path *path, PathTarget *target)
Definition: pathnode.c:2754
@ UPPERREL_FINAL
Definition: pathnodes.h:79
PlannerInfo * subquery_planner(PlannerGlobal *glob, Query *parse, PlannerInfo *parent_root, bool hasRecursion, double tuple_fraction)
Definition: planner.c:598
Path * get_cheapest_fractional_path(RelOptInfo *rel, double tuple_fraction)
Definition: planner.c:5988
void check_stack_depth(void)
Definition: postgres.c:3440
static List * generate_setop_tlist(List *colTypes, List *colCollations, int flag, Index varno, bool hack_constants, List *input_tlist, List *refnames_tlist, bool *trivial_tlist)
Definition: prepunion.c:1130
static RelOptInfo * generate_union_paths(SetOperationStmt *op, PlannerInfo *root, List *refnames_tlist, List **pTargetList)
Definition: prepunion.c:547
static RelOptInfo * generate_nonunion_paths(SetOperationStmt *op, PlannerInfo *root, List *refnames_tlist, List **pTargetList)
Definition: prepunion.c:707
RelOptInfo * build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent)
Definition: relnode.c:181
double estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows, List **pgset, EstimationInfo *estinfo)
Definition: selfuncs.c:3385
bool hasHavingQual
Definition: pathnodes.h:455
PlannerGlobal * glob
Definition: pathnodes.h:202
List * plan_params
Definition: pathnodes.h:217
List * groupClause
Definition: parsenodes.h:170
bool hasAggs
Definition: parsenodes.h:141
List * groupingSets
Definition: parsenodes.h:173
List * distinctClause
Definition: parsenodes.h:179
Relids lateral_relids
Definition: pathnodes.h:863
List * pathlist
Definition: pathnodes.h:848
PlannerInfo * subroot
Definition: pathnodes.h:898
bool tlist_same_collations(List *tlist, List *colCollations, bool junkOK)
Definition: tlist.c:282
List * get_tlist_exprs(List *tlist, bool includeJunk)
Definition: tlist.c:163
bool tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK)
Definition: tlist.c:248

References add_partial_path(), add_path(), apply_projection_to_path(), Assert(), bms_is_empty(), build_simple_rel(), check_stack_depth(), RelOptInfo::consider_parallel, create_pathtarget, create_projection_path(), create_subqueryscan_path(), Query::distinctClause, elog(), ERROR, estimate_num_groups(), fetch_upper_rel(), flag(), generate_nonunion_paths(), generate_setop_tlist(), generate_union_paths(), get_cheapest_fractional_path(), get_tlist_exprs(), PlannerInfo::glob, Query::groupClause, Query::groupingSets, Query::hasAggs, PlannerInfo::hasHavingQual, IsA, RelOptInfo::lateral_relids, lfirst, linitial, NIL, nodeTag, SetOperationStmt::op, RelOptInfo::partial_pathlist, RelOptInfo::pathlist, PlannerInfo::plan_params, postprocess_setop_rel(), PlannerInfo::processed_tlist, RelOptInfo::reltarget, RelOptInfo::rows, RangeTblRef::rtindex, set_subquery_size_estimates(), SETOP_UNION, subpath(), RangeTblEntry::subquery, subquery_planner(), RelOptInfo::subroot, Query::targetList, tlist_same_collations(), tlist_same_datatypes(), PlannerInfo::tuple_fraction, and UPPERREL_FINAL.

Referenced by generate_nonunion_paths(), generate_recursion_path(), plan_set_operations(), and plan_union_children().