src/backend/optimizer/prep/prepunion.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * prepunion.c
   4  *        Routines to plan set-operation queries.  The filename is a leftover
   5  *        from a time when only UNIONs were implemented.
   6  *
   7  * There are two code paths in the planner for set-operation queries.
   8  * If a subquery consists entirely of simple UNION ALL operations, it
   9  * is converted into an "append relation".      Otherwise, it is handled
  10  * by the general code in this module (plan_set_operations and its
  11  * subroutines).  There is some support code here for the append-relation
  12  * case, but most of the heavy lifting for that is done elsewhere,
  13  * notably in prepjointree.c and allpaths.c.
  14  *
  15  * There is also some code here to support planning of queries that use
  16  * inheritance (SELECT FROM foo*).      Inheritance trees are converted into
  17  * append relations, and thenceforth share code with the UNION ALL case.
  18  *
  19  *
  20  * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
  21  * Portions Copyright (c) 1994, Regents of the University of California
  22  *
  23  *
  24  * IDENTIFICATION
  25  *        $PostgreSQL$
  26  *
  27  *-------------------------------------------------------------------------
  28  */
  29 #include "postgres.h"
  30
  31
  32 #include "access/heapam.h"
  33 #include "access/sysattr.h"
  34 #include "catalog/namespace.h"
  35 #include "catalog/pg_inherits_fn.h"
  36 #include "catalog/pg_type.h"
  37 #include "miscadmin.h"
  38 #include "nodes/makefuncs.h"
  39 #include "nodes/nodeFuncs.h"
  40 #include "optimizer/cost.h"
  41 #include "optimizer/pathnode.h"
  42 #include "optimizer/paths.h"
  43 #include "optimizer/planmain.h"
  44 #include "optimizer/planner.h"
  45 #include "optimizer/prep.h"
  46 #include "optimizer/tlist.h"
  47 #include "parser/parse_clause.h"
  48 #include "parser/parse_coerce.h"
  49 #include "parser/parsetree.h"
  50 #include "utils/lsyscache.h"
  51 #include "utils/rel.h"
  52 #include "utils/selfuncs.h"
  53
  54
  55 static Plan *recurse_set_operations(Node *setOp, PlannerInfo *root,
  56                                            double tuple_fraction,
  57                                            List *colTypes, bool junkOK,
  58                                            int flag, List *refnames_tlist,
  59                                            List **sortClauses, double *pNumGroups);
  60 static Plan *generate_recursion_plan(SetOperationStmt *setOp,
  61                                                 PlannerInfo *root, double tuple_fraction,
  62                                                 List *refnames_tlist,
  63                                                 List **sortClauses);
  64 static Plan *generate_union_plan(SetOperationStmt *op, PlannerInfo *root,
  65                                         double tuple_fraction,
  66                                         List *refnames_tlist,
  67                                         List **sortClauses, double *pNumGroups);
  68 static Plan *generate_nonunion_plan(SetOperationStmt *op, PlannerInfo *root,
  69                                            double tuple_fraction,
  70                                            List *refnames_tlist,
  71                                            List **sortClauses, double *pNumGroups);
  72 static List *recurse_union_children(Node *setOp, PlannerInfo *root,
  73                                            double tuple_fraction,
  74                                            SetOperationStmt *top_union,
  75                                            List *refnames_tlist);
  76 static Plan *make_union_unique(SetOperationStmt *op, Plan *plan,
  77                                   PlannerInfo *root, double tuple_fraction,
  78                                   List **sortClauses);
  79 static bool choose_hashed_setop(PlannerInfo *root, List *groupClauses,
  80                                         Plan *input_plan,
  81                                         double dNumGroups, double dNumOutputRows,
  82                                         double tuple_fraction,
  83                                         const char *construct);
  84 static List *generate_setop_tlist(List *colTypes, int flag,
  85                                          Index varno,
  86                                          bool hack_constants,
  87                                          List *input_tlist,
  88                                          List *refnames_tlist);
  89 static List *generate_append_tlist(List *colTypes, bool flag,
  90                                           List *input_plans,
  91                                           List *refnames_tlist);
  92 static List *generate_setop_grouplist(SetOperationStmt *op, List *targetlist);
  93 static void expand_inherited_rtentry(PlannerInfo *root, RangeTblEntry *rte,
  94                                                  Index rti);
  95 static void make_inh_translation_list(Relation oldrelation,
  96                                                   Relation newrelation,
  97                                                   Index newvarno,
  98                                                   List **translated_vars);
  99 static Bitmapset *translate_col_privs(const Bitmapset *parent_privs,
 100                                         List *translated_vars);
 101 static Node *adjust_appendrel_attrs_mutator(Node *node,
 102                                                            AppendRelInfo *context);
 103 static Relids adjust_relid_set(Relids relids, Index oldrelid, Index newrelid);
 104 static List *adjust_inherited_tlist(List *tlist,
 105                                            AppendRelInfo *context);
 106
 107
 108 /*
 109  * plan_set_operations
 110  *
 111  *        Plans the queries for a tree of set operations (UNION/INTERSECT/EXCEPT)
 112  *
 113  * This routine only deals with the setOperations tree of the given query.
 114  * Any top-level ORDER BY requested in root->parse->sortClause will be added
 115  * when we return to grouping_planner.
 116  *
 117  * tuple_fraction is the fraction of tuples we expect will be retrieved.
 118  * tuple_fraction is interpreted as for grouping_planner(); in particular,
 119  * zero means "all the tuples will be fetched".  Any LIMIT present at the
 120  * top level has already been factored into tuple_fraction.
 121  *
 122  * *sortClauses is an output argument: it is set to a list of SortGroupClauses
 123  * representing the result ordering of the topmost set operation.  (This will
 124  * be NIL if the output isn't ordered.)
 125  */
 126 Plan *
 127 plan_set_operations(PlannerInfo *root, double tuple_fraction,
 128                                         List **sortClauses)
 129 {
 130         Query      *parse = root->parse;
 131         SetOperationStmt *topop = (SetOperationStmt *) parse->setOperations;
 132         Node       *node;
 133         Query      *leftmostQuery;
 134
 135         Assert(topop && IsA(topop, SetOperationStmt));
 136
 137         /* check for unsupported stuff */
 138         Assert(parse->jointree->fromlist == NIL);
 139         Assert(parse->jointree->quals == NULL);
 140         Assert(parse->groupClause == NIL);
 141         Assert(parse->havingQual == NULL);
 142         Assert(parse->windowClause == NIL);
 143         Assert(parse->distinctClause == NIL);
 144
 145         /*
 146          * Find the leftmost component Query.  We need to use its column names for
 147          * all generated tlists (else SELECT INTO won't work right).
 148          */
 149         node = topop->larg;
 150         while (node && IsA(node, SetOperationStmt))
 151                 node = ((SetOperationStmt *) node)->larg;
 152         Assert(node && IsA(node, RangeTblRef));
 153         leftmostQuery = rt_fetch(((RangeTblRef *) node)->rtindex,
 154                                                          parse->rtable)->subquery;
 155         Assert(leftmostQuery != NULL);
 156
 157         /*
 158          * If the topmost node is a recursive union, it needs special processing.
 159          */
 160         if (root->hasRecursion)
 161                 return generate_recursion_plan(topop, root, tuple_fraction,
 162                                                                            leftmostQuery->targetList,
 163                                                                            sortClauses);
 164
 165         /*
 166          * Recurse on setOperations tree to generate plans for set ops. The final
 167          * output plan should have just the column types shown as the output from
 168          * the top-level node, plus possibly resjunk working columns (we can rely
 169          * on upper-level nodes to deal with that).
 170          */
 171         return recurse_set_operations((Node *) topop, root, tuple_fraction,
 172                                                                   topop->colTypes, true, -1,
 173                                                                   leftmostQuery->targetList,
 174                                                                   sortClauses, NULL);
 175 }
 176
 177 /*
 178  * recurse_set_operations
 179  *        Recursively handle one step in a tree of set operations
 180  *
 181  * tuple_fraction: fraction of tuples we expect to retrieve from node
 182  * colTypes: list of type OIDs of expected output columns
 183  * junkOK: if true, child resjunk columns may be left in the result
 184  * flag: if >= 0, add a resjunk output column indicating value of flag
 185  * refnames_tlist: targetlist to take column names from
 186  *
 187  * Returns a plan for the subtree, as well as these output parameters:
 188  * *sortClauses: receives list of SortGroupClauses for result plan, if any
 189  * *pNumGroups: if not NULL, we estimate the number of distinct groups
 190  *              in the result, and store it there
 191  *
 192  * We don't have to care about typmods here: the only allowed difference
 193  * between set-op input and output typmods is input is a specific typmod
 194  * and output is -1, and that does not require a coercion.
 195  */
 196 static Plan *
 197 recurse_set_operations(Node *setOp, PlannerInfo *root,
 198                                            double tuple_fraction,
 199                                            List *colTypes, bool junkOK,
 200                                            int flag, List *refnames_tlist,
 201                                            List **sortClauses, double *pNumGroups)
 202 {
 203         if (IsA(setOp, RangeTblRef))
 204         {
 205                 RangeTblRef *rtr = (RangeTblRef *) setOp;
 206                 RangeTblEntry *rte = rt_fetch(rtr->rtindex, root->parse->rtable);
 207                 Query      *subquery = rte->subquery;
 208                 PlannerInfo *subroot;
 209                 Plan       *subplan,
 210                                    *plan;
 211
 212                 Assert(subquery != NULL);
 213
 214                 /*
 215                  * Generate plan for primitive subquery
 216                  */
 217                 subplan = subquery_planner(root->glob, subquery,
 218                                                                    root,
 219                                                                    false, tuple_fraction,
 220                                                                    &subroot);
 221
 222                 /*
 223                  * Estimate number of groups if caller wants it.  If the subquery used
 224                  * grouping or aggregation, its output is probably mostly unique
 225                  * anyway; otherwise do statistical estimation.
 226                  */
 227                 if (pNumGroups)
 228                 {
 229                         if (subquery->groupClause || subquery->distinctClause ||
 230                                 subroot->hasHavingQual || subquery->hasAggs)
 231                                 *pNumGroups = subplan->plan_rows;
 232                         else
 233                                 *pNumGroups = estimate_num_groups(subroot,
 234                                                                 get_tlist_exprs(subquery->targetList, false),
 235                                                                                                   subplan->plan_rows);
 236                 }
 237
 238                 /*
 239                  * Add a SubqueryScan with the caller-requested targetlist
 240                  */
 241                 plan = (Plan *)
 242                         make_subqueryscan(generate_setop_tlist(colTypes, flag,
 243                                                                                                    rtr->rtindex,
 244                                                                                                    true,
 245                                                                                                    subplan->targetlist,
 246                                                                                                    refnames_tlist),
 247                                                           NIL,
 248                                                           rtr->rtindex,
 249                                                           subplan,
 250                                                           subroot->parse->rtable);
 251
 252                 /*
 253                  * We don't bother to determine the subquery's output ordering since
 254                  * it won't be reflected in the set-op result anyhow.
 255                  */
 256                 *sortClauses = NIL;
 257
 258                 return plan;
 259         }
 260         else if (IsA(setOp, SetOperationStmt))
 261         {
 262                 SetOperationStmt *op = (SetOperationStmt *) setOp;
 263                 Plan       *plan;
 264
 265                 /* UNIONs are much different from INTERSECT/EXCEPT */
 266                 if (op->op == SETOP_UNION)
 267                         plan = generate_union_plan(op, root, tuple_fraction,
 268                                                                            refnames_tlist,
 269                                                                            sortClauses, pNumGroups);
 270                 else
 271                         plan = generate_nonunion_plan(op, root, tuple_fraction,
 272                                                                                   refnames_tlist,
 273                                                                                   sortClauses, pNumGroups);
 274
 275                 /*
 276                  * If necessary, add a Result node to project the caller-requested
 277                  * output columns.
 278                  *
 279                  * XXX you don't really want to know about this: setrefs.c will apply
 280                  * fix_upper_expr() to the Result node's tlist. This would fail if the
 281                  * Vars generated by generate_setop_tlist() were not exactly equal()
 282                  * to the corresponding tlist entries of the subplan. However, since
 283                  * the subplan was generated by generate_union_plan() or
 284                  * generate_nonunion_plan(), and hence its tlist was generated by
 285                  * generate_append_tlist(), this will work.  We just tell
 286                  * generate_setop_tlist() to use varno 0.
 287                  */
 288                 if (flag >= 0 ||
 289                         !tlist_same_datatypes(plan->targetlist, colTypes, junkOK))
 290                 {
 291                         plan = (Plan *)
 292                                 make_result(root,
 293                                                         generate_setop_tlist(colTypes, flag,
 294                                                                                                  0,
 295                                                                                                  false,
 296                                                                                                  plan->targetlist,
 297                                                                                                  refnames_tlist),
 298                                                         NULL,
 299                                                         plan);
 300                 }
 301                 return plan;
 302         }
 303         else
 304         {
 305                 elog(ERROR, "unrecognized node type: %d",
 306                          (int) nodeTag(setOp));
 307                 return NULL;                    /* keep compiler quiet */
 308         }
 309 }
 310
 311 /*
 312  * Generate plan for a recursive UNION node
 313  */
 314 static Plan *
 315 generate_recursion_plan(SetOperationStmt *setOp, PlannerInfo *root,
 316                                                 double tuple_fraction,
 317                                                 List *refnames_tlist,
 318                                                 List **sortClauses)
 319 {
 320         Plan       *plan;
 321         Plan       *lplan;
 322         Plan       *rplan;
 323         List       *tlist;
 324         List       *groupList;
 325         long            numGroups;
 326
 327         /* Parser should have rejected other cases */
 328         if (setOp->op != SETOP_UNION)
 329                 elog(ERROR, "only UNION queries can be recursive");
 330         /* Worktable ID should be assigned */
 331         Assert(root->wt_param_id >= 0);
 332
 333         /*
 334          * Unlike a regular UNION node, process the left and right inputs
 335          * separately without any intention of combining them into one Append.
 336          */
 337         lplan = recurse_set_operations(setOp->larg, root, tuple_fraction,
 338                                                                    setOp->colTypes, false, -1,
 339                                                                    refnames_tlist, sortClauses, NULL);
 340         /* The right plan will want to look at the left one ... */
 341         root->non_recursive_plan = lplan;
 342         rplan = recurse_set_operations(setOp->rarg, root, tuple_fraction,
 343                                                                    setOp->colTypes, false, -1,
 344                                                                    refnames_tlist, sortClauses, NULL);
 345         root->non_recursive_plan = NULL;
 346
 347         /*
 348          * Generate tlist for RecursiveUnion plan node --- same as in Append cases
 349          */
 350         tlist = generate_append_tlist(setOp->colTypes, false,
 351                                                                   list_make2(lplan, rplan),
 352                                                                   refnames_tlist);
 353
 354         /*
 355          * If UNION, identify the grouping operators
 356          */
 357         if (setOp->all)
 358         {
 359                 groupList = NIL;
 360                 numGroups = 0;
 361         }
 362         else
 363         {
 364                 double          dNumGroups;
 365
 366                 /* Identify the grouping semantics */
 367                 groupList = generate_setop_grouplist(setOp, tlist);
 368
 369                 /* We only support hashing here */
 370                 if (!grouping_is_hashable(groupList))
 371                         ereport(ERROR,
 372                                         (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 373                                          errmsg("could not implement recursive UNION"),
 374                                          errdetail("All column datatypes must be hashable.")));
 375
 376                 /*
 377                  * For the moment, take the number of distinct groups as equal to the
 378                  * total input size, ie, the worst case.
 379                  */
 380                 dNumGroups = lplan->plan_rows + rplan->plan_rows * 10;
 381
 382                 /* Also convert to long int --- but 'ware overflow! */
 383                 numGroups = (long) Min(dNumGroups, (double) LONG_MAX);
 384         }
 385
 386         /*
 387          * And make the plan node.
 388          */
 389         plan = (Plan *) make_recursive_union(tlist, lplan, rplan,
 390                                                                                  root->wt_param_id,
 391                                                                                  groupList, numGroups);
 392
 393         *sortClauses = NIL;                     /* RecursiveUnion result is always unsorted */
 394
 395         return plan;
 396 }
 397
 398 /*
 399  * Generate plan for a UNION or UNION ALL node
 400  */
 401 static Plan *
 402 generate_union_plan(SetOperationStmt *op, PlannerInfo *root,
 403                                         double tuple_fraction,
 404                                         List *refnames_tlist,
 405                                         List **sortClauses, double *pNumGroups)
 406 {
 407         List       *planlist;
 408         List       *tlist;
 409         Plan       *plan;
 410
 411         /*
 412          * If plain UNION, tell children to fetch all tuples.
 413          *
 414          * Note: in UNION ALL, we pass the top-level tuple_fraction unmodified to
 415          * each arm of the UNION ALL.  One could make a case for reducing the
 416          * tuple fraction for later arms (discounting by the expected size of the
 417          * earlier arms' results) but it seems not worth the trouble. The normal
 418          * case where tuple_fraction isn't already zero is a LIMIT at top level,
 419          * and passing it down as-is is usually enough to get the desired result
 420          * of preferring fast-start plans.
 421          */
 422         if (!op->all)
 423                 tuple_fraction = 0.0;
 424
 425         /*
 426          * If any of my children are identical UNION nodes (same op, all-flag, and
 427          * colTypes) then they can be merged into this node so that we generate
 428          * only one Append and unique-ification for the lot.  Recurse to find such
 429          * nodes and compute their children's plans.
 430          */
 431         planlist = list_concat(recurse_union_children(op->larg, root,
 432                                                                                                   tuple_fraction,
 433                                                                                                   op, refnames_tlist),
 434                                                    recurse_union_children(op->rarg, root,
 435                                                                                                   tuple_fraction,
 436                                                                                                   op, refnames_tlist));
 437
 438         /*
 439          * Generate tlist for Append plan node.
 440          *
 441          * The tlist for an Append plan isn't important as far as the Append is
 442          * concerned, but we must make it look real anyway for the benefit of the
 443          * next plan level up.
 444          */
 445         tlist = generate_append_tlist(op->colTypes, false,
 446                                                                   planlist, refnames_tlist);
 447
 448         /*
 449          * Append the child results together.
 450          */
 451         plan = (Plan *) make_append(planlist, false, tlist);
 452
 453         /*
 454          * For UNION ALL, we just need the Append plan.  For UNION, need to add
 455          * node(s) to remove duplicates.
 456          */
 457         if (op->all)
 458                 *sortClauses = NIL;             /* result of UNION ALL is always unsorted */
 459         else
 460                 plan = make_union_unique(op, plan, root, tuple_fraction, sortClauses);
 461
 462         /*
 463          * Estimate number of groups if caller wants it.  For now we just assume
 464          * the output is unique --- this is certainly true for the UNION case, and
 465          * we want worst-case estimates anyway.
 466          */
 467         if (pNumGroups)
 468                 *pNumGroups = plan->plan_rows;
 469
 470         return plan;
 471 }
 472
 473 /*
 474  * Generate plan for an INTERSECT, INTERSECT ALL, EXCEPT, or EXCEPT ALL node
 475  */
 476 static Plan *
 477 generate_nonunion_plan(SetOperationStmt *op, PlannerInfo *root,
 478                                            double tuple_fraction,
 479                                            List *refnames_tlist,
 480                                            List **sortClauses, double *pNumGroups)
 481 {
 482         Plan       *lplan,
 483                            *rplan,
 484                            *plan;
 485         List       *tlist,
 486                            *groupList,
 487                            *planlist,
 488                            *child_sortclauses;
 489         double          dLeftGroups,
 490                                 dRightGroups,
 491                                 dNumGroups,
 492                                 dNumOutputRows;
 493         long            numGroups;
 494         bool            use_hash;
 495         SetOpCmd        cmd;
 496         int                     firstFlag;
 497
 498         /* Recurse on children, ensuring their outputs are marked */
 499         lplan = recurse_set_operations(op->larg, root,
 500                                                                    0.0 /* all tuples needed */ ,
 501                                                                    op->colTypes, false, 0,
 502                                                                    refnames_tlist,
 503                                                                    &child_sortclauses, &dLeftGroups);
 504         rplan = recurse_set_operations(op->rarg, root,
 505                                                                    0.0 /* all tuples needed */ ,
 506                                                                    op->colTypes, false, 1,
 507                                                                    refnames_tlist,
 508                                                                    &child_sortclauses, &dRightGroups);
 509
 510         /*
 511          * For EXCEPT, we must put the left input first.  For INTERSECT, either
 512          * order should give the same results, and we prefer to put the smaller
 513          * input first in order to minimize the size of the hash table in the
 514          * hashing case.  "Smaller" means the one with the fewer groups.
 515          */
 516         if (op->op == SETOP_EXCEPT || dLeftGroups <= dRightGroups)
 517         {
 518                 planlist = list_make2(lplan, rplan);
 519                 firstFlag = 0;
 520         }
 521         else
 522         {
 523                 planlist = list_make2(rplan, lplan);
 524                 firstFlag = 1;
 525         }
 526
 527         /*
 528          * Generate tlist for Append plan node.
 529          *
 530          * The tlist for an Append plan isn't important as far as the Append is
 531          * concerned, but we must make it look real anyway for the benefit of the
 532          * next plan level up.  In fact, it has to be real enough that the flag
 533          * column is shown as a variable not a constant, else setrefs.c will get
 534          * confused.
 535          */
 536         tlist = generate_append_tlist(op->colTypes, true,
 537                                                                   planlist, refnames_tlist);
 538
 539         /*
 540          * Append the child results together.
 541          */
 542         plan = (Plan *) make_append(planlist, false, tlist);
 543
 544         /* Identify the grouping semantics */
 545         groupList = generate_setop_grouplist(op, tlist);
 546
 547         /* punt if nothing to group on (can this happen?) */
 548         if (groupList == NIL)
 549         {
 550                 *sortClauses = NIL;
 551                 return plan;
 552         }
 553
 554         /*
 555          * Estimate number of distinct groups that we'll need hashtable entries
 556          * for; this is the size of the left-hand input for EXCEPT, or the smaller
 557          * input for INTERSECT.  Also estimate the number of eventual output rows.
 558          * In non-ALL cases, we estimate each group produces one output row; in
 559          * ALL cases use the relevant relation size.  These are worst-case
 560          * estimates, of course, but we need to be conservative.
 561          */
 562         if (op->op == SETOP_EXCEPT)
 563         {
 564                 dNumGroups = dLeftGroups;
 565                 dNumOutputRows = op->all ? lplan->plan_rows : dNumGroups;
 566         }
 567         else
 568         {
 569                 dNumGroups = Min(dLeftGroups, dRightGroups);
 570                 dNumOutputRows = op->all ? Min(lplan->plan_rows, rplan->plan_rows) : dNumGroups;
 571         }
 572
 573         /* Also convert to long int --- but 'ware overflow! */
 574         numGroups = (long) Min(dNumGroups, (double) LONG_MAX);
 575
 576         /*
 577          * Decide whether to hash or sort, and add a sort node if needed.
 578          */
 579         use_hash = choose_hashed_setop(root, groupList, plan,
 580                                                                    dNumGroups, dNumOutputRows, tuple_fraction,
 581                                            (op->op == SETOP_INTERSECT) ? "INTERSECT" : "EXCEPT");
 582
 583         if (!use_hash)
 584                 plan = (Plan *) make_sort_from_sortclauses(root, groupList, plan);
 585
 586         /*
 587          * Finally, add a SetOp plan node to generate the correct output.
 588          */
 589         switch (op->op)
 590         {
 591                 case SETOP_INTERSECT:
 592                         cmd = op->all ? SETOPCMD_INTERSECT_ALL : SETOPCMD_INTERSECT;
 593                         break;
 594                 case SETOP_EXCEPT:
 595                         cmd = op->all ? SETOPCMD_EXCEPT_ALL : SETOPCMD_EXCEPT;
 596                         break;
 597                 default:
 598                         elog(ERROR, "unrecognized set op: %d", (int) op->op);
 599                         cmd = SETOPCMD_INTERSECT;       /* keep compiler quiet */
 600                         break;
 601         }
 602         plan = (Plan *) make_setop(cmd, use_hash ? SETOP_HASHED : SETOP_SORTED,
 603                                                            plan, groupList,
 604                                                            list_length(op->colTypes) + 1,
 605                                                            use_hash ? firstFlag : -1,
 606                                                            numGroups, dNumOutputRows);
 607
 608         /* Result is sorted only if we're not hashing */
 609         *sortClauses = use_hash ? NIL : groupList;
 610
 611         if (pNumGroups)
 612                 *pNumGroups = dNumGroups;
 613
 614         return plan;
 615 }
 616
 617 /*
 618  * Pull up children of a UNION node that are identically-propertied UNIONs.
 619  *
 620  * NOTE: we can also pull a UNION ALL up into a UNION, since the distinct
 621  * output rows will be lost anyway.
 622  */
 623 static List *
 624 recurse_union_children(Node *setOp, PlannerInfo *root,
 625                                            double tuple_fraction,
 626                                            SetOperationStmt *top_union,
 627                                            List *refnames_tlist)
 628 {
 629         List       *child_sortclauses;
 630
 631         if (IsA(setOp, SetOperationStmt))
 632         {
 633                 SetOperationStmt *op = (SetOperationStmt *) setOp;
 634
 635                 if (op->op == top_union->op &&
 636                         (op->all == top_union->all || op->all) &&
 637                         equal(op->colTypes, top_union->colTypes))
 638                 {
 639                         /* Same UNION, so fold children into parent's subplan list */
 640                         return list_concat(recurse_union_children(op->larg, root,
 641                                                                                                           tuple_fraction,
 642                                                                                                           top_union,
 643                                                                                                           refnames_tlist),
 644                                                            recurse_union_children(op->rarg, root,
 645                                                                                                           tuple_fraction,
 646                                                                                                           top_union,
 647                                                                                                           refnames_tlist));
 648                 }
 649         }
 650
 651         /*
 652          * Not same, so plan this child separately.
 653          *
 654          * Note we disallow any resjunk columns in child results.  This is
 655          * necessary since the Append node that implements the union won't do any
 656          * projection, and upper levels will get confused if some of our output
 657          * tuples have junk and some don't.  This case only arises when we have an
 658          * EXCEPT or INTERSECT as child, else there won't be resjunk anyway.
 659          */
 660         return list_make1(recurse_set_operations(setOp, root,
 661                                                                                          tuple_fraction,
 662                                                                                          top_union->colTypes, false,
 663                                                                                          -1, refnames_tlist,
 664                                                                                          &child_sortclauses, NULL));
 665 }
 666
 667 /*
 668  * Add nodes to the given plan tree to unique-ify the result of a UNION.
 669  */
 670 static Plan *
 671 make_union_unique(SetOperationStmt *op, Plan *plan,
 672                                   PlannerInfo *root, double tuple_fraction,
 673                                   List **sortClauses)
 674 {
 675         List       *groupList;
 676         double          dNumGroups;
 677         long            numGroups;
 678
 679         /* Identify the grouping semantics */
 680         groupList = generate_setop_grouplist(op, plan->targetlist);
 681
 682         /* punt if nothing to group on (can this happen?) */
 683         if (groupList == NIL)
 684         {
 685                 *sortClauses = NIL;
 686                 return plan;
 687         }
 688
 689         /*
 690          * XXX for the moment, take the number of distinct groups as equal to the
 691          * total input size, ie, the worst case.  This is too conservative, but we
 692          * don't want to risk having the hashtable overrun memory; also, it's not
 693          * clear how to get a decent estimate of the true size.  One should note
 694          * as well the propensity of novices to write UNION rather than UNION ALL
 695          * even when they don't expect any duplicates...
 696          */
 697         dNumGroups = plan->plan_rows;
 698
 699         /* Also convert to long int --- but 'ware overflow! */
 700         numGroups = (long) Min(dNumGroups, (double) LONG_MAX);
 701
 702         /* Decide whether to hash or sort */
 703         if (choose_hashed_setop(root, groupList, plan,
 704                                                         dNumGroups, dNumGroups, tuple_fraction,
 705                                                         "UNION"))
 706         {
 707                 /* Hashed aggregate plan --- no sort needed */
 708                 plan = (Plan *) make_agg(root,
 709                                                                  plan->targetlist,
 710                                                                  NIL,
 711                                                                  AGG_HASHED,
 712                                                                  list_length(groupList),
 713                                                                  extract_grouping_cols(groupList,
 714                                                                                                            plan->targetlist),
 715                                                                  extract_grouping_ops(groupList),
 716                                                                  numGroups,
 717                                                                  0,
 718                                                                  plan);
 719                 /* Hashed aggregation produces randomly-ordered results */
 720                 *sortClauses = NIL;
 721         }
 722         else
 723         {
 724                 /* Sort and Unique */
 725                 plan = (Plan *) make_sort_from_sortclauses(root, groupList, plan);
 726                 plan = (Plan *) make_unique(plan, groupList);
 727                 plan->plan_rows = dNumGroups;
 728                 /* We know the sort order of the result */
 729                 *sortClauses = groupList;
 730         }
 731
 732         return plan;
 733 }
 734
 735 /*
 736  * choose_hashed_setop - should we use hashing for a set operation?
 737  */
 738 static bool
 739 choose_hashed_setop(PlannerInfo *root, List *groupClauses,
 740                                         Plan *input_plan,
 741                                         double dNumGroups, double dNumOutputRows,
 742                                         double tuple_fraction,
 743                                         const char *construct)
 744 {
 745         int                     numGroupCols = list_length(groupClauses);
 746         bool            can_sort;
 747         bool            can_hash;
 748         Size            hashentrysize;
 749         Path            hashed_p;
 750         Path            sorted_p;
 751
 752         /* Check whether the operators support sorting or hashing */
 753         can_sort = grouping_is_sortable(groupClauses);
 754         can_hash = grouping_is_hashable(groupClauses);
 755         if (can_hash && can_sort)
 756         {
 757                 /* we have a meaningful choice to make, continue ... */
 758         }
 759         else if (can_hash)
 760                 return true;
 761         else if (can_sort)
 762                 return false;
 763         else
 764                 ereport(ERROR,
 765                                 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
 766                 /* translator: %s is UNION, INTERSECT, or EXCEPT */
 767                                  errmsg("could not implement %s", construct),
 768                                  errdetail("Some of the datatypes only support hashing, while others only support sorting.")));
 769
 770         /* Prefer sorting when enable_hashagg is off */
 771         if (!enable_hashagg)
 772                 return false;
 773
 774         /*
 775          * Don't do it if it doesn't look like the hashtable will fit into
 776          * work_mem.
 777          */
 778         hashentrysize = MAXALIGN(input_plan->plan_width) + MAXALIGN(sizeof(MinimalTupleData));
 779
 780         if (hashentrysize * dNumGroups > work_mem * 1024L)
 781                 return false;
 782
 783         /*
 784          * See if the estimated cost is no more than doing it the other way.
 785          *
 786          * We need to consider input_plan + hashagg versus input_plan + sort +
 787          * group.  Note that the actual result plan might involve a SetOp or
 788          * Unique node, not Agg or Group, but the cost estimates for Agg and Group
 789          * should be close enough for our purposes here.
 790          *
 791          * These path variables are dummies that just hold cost fields; we don't
 792          * make actual Paths for these steps.
 793          */
 794         cost_agg(&hashed_p, root, AGG_HASHED, 0,
 795                          numGroupCols, dNumGroups,
 796                          input_plan->startup_cost, input_plan->total_cost,
 797                          input_plan->plan_rows);
 798
 799         /*
 800          * Now for the sorted case.  Note that the input is *always* unsorted,
 801          * since it was made by appending unrelated sub-relations together.
 802          */
 803         sorted_p.startup_cost = input_plan->startup_cost;
 804         sorted_p.total_cost = input_plan->total_cost;
 805         /* XXX cost_sort doesn't actually look at pathkeys, so just pass NIL */
 806         cost_sort(&sorted_p, root, NIL, sorted_p.total_cost,
 807                           input_plan->plan_rows, input_plan->plan_width, -1.0);
 808         cost_group(&sorted_p, root, numGroupCols, dNumGroups,
 809                            sorted_p.startup_cost, sorted_p.total_cost,
 810                            input_plan->plan_rows);
 811
 812         /*
 813          * Now make the decision using the top-level tuple fraction.  First we
 814          * have to convert an absolute count (LIMIT) into fractional form.
 815          */
 816         if (tuple_fraction >= 1.0)
 817                 tuple_fraction /= dNumOutputRows;
 818
 819         if (compare_fractional_path_costs(&hashed_p, &sorted_p,
 820                                                                           tuple_fraction) < 0)
 821         {
 822                 /* Hashed is cheaper, so use it */
 823                 return true;
 824         }
 825         return false;
 826 }
 827
 828 /*
 829  * Generate targetlist for a set-operation plan node
 830  *
 831  * colTypes: column datatypes for non-junk columns
 832  * flag: -1 if no flag column needed, 0 or 1 to create a const flag column
 833  * varno: varno to use in generated Vars
 834  * hack_constants: true to copy up constants (see comments in code)
 835  * input_tlist: targetlist of this node's input node
 836  * refnames_tlist: targetlist to take column names from
 837  */
 838 static List *
 839 generate_setop_tlist(List *colTypes, int flag,
 840                                          Index varno,
 841                                          bool hack_constants,
 842                                          List *input_tlist,
 843                                          List *refnames_tlist)
 844 {
 845         List       *tlist = NIL;
 846         int                     resno = 1;
 847         ListCell   *i,
 848                            *j,
 849                            *k;
 850         TargetEntry *tle;
 851         Node       *expr;
 852
 853         j = list_head(input_tlist);
 854         k = list_head(refnames_tlist);
 855         foreach(i, colTypes)
 856         {
 857                 Oid                     colType = lfirst_oid(i);
 858                 TargetEntry *inputtle = (TargetEntry *) lfirst(j);
 859                 TargetEntry *reftle = (TargetEntry *) lfirst(k);
 860
 861                 Assert(inputtle->resno == resno);
 862                 Assert(reftle->resno == resno);
 863                 Assert(!inputtle->resjunk);
 864                 Assert(!reftle->resjunk);
 865
 866                 /*
 867                  * Generate columns referencing input columns and having appropriate
 868                  * data types and column names.  Insert datatype coercions where
 869                  * necessary.
 870                  *
 871                  * HACK: constants in the input's targetlist are copied up as-is
 872                  * rather than being referenced as subquery outputs.  This is mainly
 873                  * to ensure that when we try to coerce them to the output column's
 874                  * datatype, the right things happen for UNKNOWN constants.  But do
 875                  * this only at the first level of subquery-scan plans; we don't want
 876                  * phony constants appearing in the output tlists of upper-level
 877                  * nodes!
 878                  */
 879                 if (hack_constants && inputtle->expr && IsA(inputtle->expr, Const))
 880                         expr = (Node *) inputtle->expr;
 881                 else
 882                         expr = (Node *) makeVar(varno,
 883                                                                         inputtle->resno,
 884                                                                         exprType((Node *) inputtle->expr),
 885                                                                         exprTypmod((Node *) inputtle->expr),
 886                                                                         0);
 887                 if (exprType(expr) != colType)
 888                 {
 889                         expr = coerce_to_common_type(NULL,      /* no UNKNOWNs here */
 890                                                                                  expr,
 891                                                                                  colType,
 892                                                                                  "UNION/INTERSECT/EXCEPT");
 893                 }
 894                 tle = makeTargetEntry((Expr *) expr,
 895                                                           (AttrNumber) resno++,
 896                                                           pstrdup(reftle->resname),
 897                                                           false);
 898                 tlist = lappend(tlist, tle);
 899
 900                 j = lnext(j);
 901                 k = lnext(k);
 902         }
 903
 904         if (flag >= 0)
 905         {
 906                 /* Add a resjunk flag column */
 907                 /* flag value is the given constant */
 908                 expr = (Node *) makeConst(INT4OID,
 909                                                                   -1,
 910                                                                   sizeof(int4),
 911                                                                   Int32GetDatum(flag),
 912                                                                   false,
 913                                                                   true);
 914                 tle = makeTargetEntry((Expr *) expr,
 915                                                           (AttrNumber) resno++,
 916                                                           pstrdup("flag"),
 917                                                           true);
 918                 tlist = lappend(tlist, tle);
 919         }
 920
 921         return tlist;
 922 }
 923
 924 /*
 925  * Generate targetlist for a set-operation Append node
 926  *
 927  * colTypes: column datatypes for non-junk columns
 928  * flag: true to create a flag column copied up from subplans
 929  * input_plans: list of sub-plans of the Append
 930  * refnames_tlist: targetlist to take column names from
 931  *
 932  * The entries in the Append's targetlist should always be simple Vars;
 933  * we just have to make sure they have the right datatypes and typmods.
 934  * The Vars are always generated with varno 0.
 935  */
 936 static List *
 937 generate_append_tlist(List *colTypes, bool flag,
 938                                           List *input_plans,
 939                                           List *refnames_tlist)
 940 {
 941         List       *tlist = NIL;
 942         int                     resno = 1;
 943         ListCell   *curColType;
 944         ListCell   *ref_tl_item;
 945         int                     colindex;
 946         TargetEntry *tle;
 947         Node       *expr;
 948         ListCell   *planl;
 949         int32      *colTypmods;
 950
 951         /*
 952          * First extract typmods to use.
 953          *
 954          * If the inputs all agree on type and typmod of a particular column, use
 955          * that typmod; else use -1.
 956          */
 957         colTypmods = (int32 *) palloc(list_length(colTypes) * sizeof(int32));
 958
 959         foreach(planl, input_plans)
 960         {
 961                 Plan       *subplan = (Plan *) lfirst(planl);
 962                 ListCell   *subtlist;
 963
 964                 curColType = list_head(colTypes);
 965                 colindex = 0;
 966                 foreach(subtlist, subplan->targetlist)
 967                 {
 968                         TargetEntry *subtle = (TargetEntry *) lfirst(subtlist);
 969
 970                         if (subtle->resjunk)
 971                                 continue;
 972                         Assert(curColType != NULL);
 973                         if (exprType((Node *) subtle->expr) == lfirst_oid(curColType))
 974                         {
 975                                 /* If first subplan, copy the typmod; else compare */
 976                                 int32           subtypmod = exprTypmod((Node *) subtle->expr);
 977
 978                                 if (planl == list_head(input_plans))
 979                                         colTypmods[colindex] = subtypmod;
 980                                 else if (subtypmod != colTypmods[colindex])
 981                                         colTypmods[colindex] = -1;
 982                         }
 983                         else
 984                         {
 985                                 /* types disagree, so force typmod to -1 */
 986                                 colTypmods[colindex] = -1;
 987                         }
 988                         curColType = lnext(curColType);
 989                         colindex++;
 990                 }
 991                 Assert(curColType == NULL);
 992         }
 993
 994         /*
 995          * Now we can build the tlist for the Append.
 996          */
 997         colindex = 0;
 998         forboth(curColType, colTypes, ref_tl_item, refnames_tlist)
 999         {
1000                 Oid                     colType = lfirst_oid(curColType);
1001                 int32           colTypmod = colTypmods[colindex++];
1002                 TargetEntry *reftle = (TargetEntry *) lfirst(ref_tl_item);
1003
1004                 Assert(reftle->resno == resno);
1005                 Assert(!reftle->resjunk);
1006                 expr = (Node *) makeVar(0,
1007                                                                 resno,
1008                                                                 colType,
1009                                                                 colTypmod,
1010                                                                 0);
1011                 tle = makeTargetEntry((Expr *) expr,
1012                                                           (AttrNumber) resno++,
1013                                                           pstrdup(reftle->resname),
1014                                                           false);
1015                 tlist = lappend(tlist, tle);
1016         }
1017
1018         if (flag)
1019         {
1020                 /* Add a resjunk flag column */
1021                 /* flag value is shown as copied up from subplan */
1022                 expr = (Node *) makeVar(0,
1023                                                                 resno,
1024                                                                 INT4OID,
1025                                                                 -1,
1026                                                                 0);
1027                 tle = makeTargetEntry((Expr *) expr,
1028                                                           (AttrNumber) resno++,
1029                                                           pstrdup("flag"),
1030                                                           true);
1031                 tlist = lappend(tlist, tle);
1032         }
1033
1034         pfree(colTypmods);
1035
1036         return tlist;
1037 }
1038
1039 /*
1040  * generate_setop_grouplist
1041  *              Build a SortGroupClause list defining the sort/grouping properties
1042  *              of the setop's output columns.
1043  *
1044  * Parse analysis already determined the properties and built a suitable
1045  * list, except that the entries do not have sortgrouprefs set because
1046  * the parser output representation doesn't include a tlist for each
1047  * setop.  So what we need to do here is copy that list and install
1048  * proper sortgrouprefs into it and into the targetlist.
1049  */
1050 static List *
1051 generate_setop_grouplist(SetOperationStmt *op, List *targetlist)
1052 {
1053         List       *grouplist = (List *) copyObject(op->groupClauses);
1054         ListCell   *lg;
1055         ListCell   *lt;
1056         Index           refno = 1;
1057
1058         lg = list_head(grouplist);
1059         foreach(lt, targetlist)
1060         {
1061                 TargetEntry *tle = (TargetEntry *) lfirst(lt);
1062                 SortGroupClause *sgc;
1063
1064                 /* tlist shouldn't have any sortgrouprefs yet */
1065                 Assert(tle->ressortgroupref == 0);
1066
1067                 if (tle->resjunk)
1068                         continue;                       /* ignore resjunk columns */
1069
1070                 /* non-resjunk columns should have grouping clauses */
1071                 Assert(lg != NULL);
1072                 sgc = (SortGroupClause *) lfirst(lg);
1073                 lg = lnext(lg);
1074                 Assert(sgc->tleSortGroupRef == 0);
1075
1076                 /* we could use assignSortGroupRef here, but seems a bit silly */
1077                 sgc->tleSortGroupRef = tle->ressortgroupref = refno++;
1078         }
1079         Assert(lg == NULL);
1080         return grouplist;
1081 }
1082
1083
1084 /*
1085  * expand_inherited_tables
1086  *              Expand each rangetable entry that represents an inheritance set
1087  *              into an "append relation".      At the conclusion of this process,
1088  *              the "inh" flag is set in all and only those RTEs that are append
1089  *              relation parents.
1090  */
1091 void
1092 expand_inherited_tables(PlannerInfo *root)
1093 {
1094         Index           nrtes;
1095         Index           rti;
1096         ListCell   *rl;
1097
1098         /*
1099          * expand_inherited_rtentry may add RTEs to parse->rtable; there is no
1100          * need to scan them since they can't have inh=true.  So just scan as far
1101          * as the original end of the rtable list.
1102          */
1103         nrtes = list_length(root->parse->rtable);
1104         rl = list_head(root->parse->rtable);
1105         for (rti = 1; rti <= nrtes; rti++)
1106         {
1107                 RangeTblEntry *rte = (RangeTblEntry *) lfirst(rl);
1108
1109                 expand_inherited_rtentry(root, rte, rti);
1110                 rl = lnext(rl);
1111         }
1112 }
1113
1114 /*
1115  * expand_inherited_rtentry
1116  *              Check whether a rangetable entry represents an inheritance set.
1117  *              If so, add entries for all the child tables to the query's
1118  *              rangetable, and build AppendRelInfo nodes for all the child tables
1119  *              and add them to root->append_rel_list.  If not, clear the entry's
1120  *              "inh" flag to prevent later code from looking for AppendRelInfos.
1121  *
1122  * Note that the original RTE is considered to represent the whole
1123  * inheritance set.  The first of the generated RTEs is an RTE for the same
1124  * table, but with inh = false, to represent the parent table in its role
1125  * as a simple member of the inheritance set.
1126  *
1127  * A childless table is never considered to be an inheritance set; therefore
1128  * a parent RTE must always have at least two associated AppendRelInfos.
1129  */
1130 static void
1131 expand_inherited_rtentry(PlannerInfo *root, RangeTblEntry *rte, Index rti)
1132 {
1133         Query      *parse = root->parse;
1134         Oid                     parentOID;
1135         RowMarkClause *oldrc;
1136         Relation        oldrelation;
1137         LOCKMODE        lockmode;
1138         List       *inhOIDs;
1139         List       *appinfos;
1140         ListCell   *l;
1141
1142         /* Does RT entry allow inheritance? */
1143         if (!rte->inh)
1144                 return;
1145         /* Ignore any already-expanded UNION ALL nodes */
1146         if (rte->rtekind != RTE_RELATION)
1147         {
1148                 Assert(rte->rtekind == RTE_SUBQUERY);
1149                 return;
1150         }
1151         /* Fast path for common case of childless table */
1152         parentOID = rte->relid;
1153         if (!has_subclass(parentOID))
1154         {
1155                 /* Clear flag before returning */
1156                 rte->inh = false;
1157                 return;
1158         }
1159
1160         /*
1161          * The rewriter should already have obtained an appropriate lock on each
1162          * relation named in the query.  However, for each child relation we add
1163          * to the query, we must obtain an appropriate lock, because this will be
1164          * the first use of those relations in the parse/rewrite/plan pipeline.
1165          *
1166          * If the parent relation is the query's result relation, then we need
1167          * RowExclusiveLock.  Otherwise, if it's accessed FOR UPDATE/SHARE, we
1168          * need RowShareLock; otherwise AccessShareLock.  We can't just grab
1169          * AccessShareLock because then the executor would be trying to upgrade
1170          * the lock, leading to possible deadlocks.  (This code should match the
1171          * parser and rewriter.)
1172          */
1173         oldrc = get_rowmark(parse, rti);
1174         if (rti == parse->resultRelation)
1175                 lockmode = RowExclusiveLock;
1176         else if (oldrc)
1177                 lockmode = RowShareLock;
1178         else
1179                 lockmode = AccessShareLock;
1180
1181         /* Scan for all members of inheritance set, acquire needed locks */
1182         inhOIDs = find_all_inheritors(parentOID, lockmode);
1183
1184         /*
1185          * Check that there's at least one descendant, else treat as no-child
1186          * case.  This could happen despite above has_subclass() check, if table
1187          * once had a child but no longer does.
1188          */
1189         if (list_length(inhOIDs) < 2)
1190         {
1191                 /* Clear flag before returning */
1192                 rte->inh = false;
1193                 return;
1194         }
1195
1196         /*
1197          * If parent relation is selected FOR UPDATE/SHARE, we need to mark its
1198          * RowMarkClause as isParent = true, and generate a new RowMarkClause for
1199          * each child.
1200          */
1201         if (oldrc)
1202                 oldrc->isParent = true;
1203
1204         /*
1205          * Must open the parent relation to examine its tupdesc.  We need not lock
1206          * it; we assume the rewriter already did.
1207          */
1208         oldrelation = heap_open(parentOID, NoLock);
1209
1210         /* Scan the inheritance set and expand it */
1211         appinfos = NIL;
1212         foreach(l, inhOIDs)
1213         {
1214                 Oid                     childOID = lfirst_oid(l);
1215                 Relation        newrelation;
1216                 RangeTblEntry *childrte;
1217                 Index           childRTindex;
1218                 AppendRelInfo *appinfo;
1219
1220                 /* Open rel if needed; we already have required locks */
1221                 if (childOID != parentOID)
1222                         newrelation = heap_open(childOID, NoLock);
1223                 else
1224                         newrelation = oldrelation;
1225
1226                 /*
1227                  * It is possible that the parent table has children that are temp
1228                  * tables of other backends.  We cannot safely access such tables
1229                  * (because of buffering issues), and the best thing to do seems to be
1230                  * to silently ignore them.
1231                  */
1232                 if (childOID != parentOID && RELATION_IS_OTHER_TEMP(newrelation))
1233                 {
1234                         heap_close(newrelation, lockmode);
1235                         continue;
1236                 }
1237
1238                 /*
1239                  * Build an RTE for the child, and attach to query's rangetable list.
1240                  * We copy most fields of the parent's RTE, but replace relation OID,
1241                  * and set inh = false.
1242                  */
1243                 childrte = copyObject(rte);
1244                 childrte->relid = childOID;
1245                 childrte->inh = false;
1246                 parse->rtable = lappend(parse->rtable, childrte);
1247                 childRTindex = list_length(parse->rtable);
1248
1249                 /*
1250                  * Build an AppendRelInfo for this parent and child.
1251                  */
1252                 appinfo = makeNode(AppendRelInfo);
1253                 appinfo->parent_relid = rti;
1254                 appinfo->child_relid = childRTindex;
1255                 appinfo->parent_reltype = oldrelation->rd_rel->reltype;
1256                 appinfo->child_reltype = newrelation->rd_rel->reltype;
1257                 make_inh_translation_list(oldrelation, newrelation, childRTindex,
1258                                                                   &appinfo->translated_vars);
1259                 appinfo->parent_reloid = parentOID;
1260                 appinfos = lappend(appinfos, appinfo);
1261
1262                 /*
1263                  * Translate the column permissions bitmaps to the child's attnums (we
1264                  * have to build the translated_vars list before we can do this). But
1265                  * if this is the parent table, leave copyObject's result alone.
1266                  */
1267                 if (childOID != parentOID)
1268                 {
1269                         childrte->selectedCols = translate_col_privs(rte->selectedCols,
1270                                                                                                    appinfo->translated_vars);
1271                         childrte->modifiedCols = translate_col_privs(rte->modifiedCols,
1272                                                                                                    appinfo->translated_vars);
1273                 }
1274
1275                 /*
1276                  * Build a RowMarkClause if parent is marked FOR UPDATE/SHARE.
1277                  */
1278                 if (oldrc)
1279                 {
1280                         RowMarkClause *newrc = makeNode(RowMarkClause);
1281
1282                         newrc->rti = childRTindex;
1283                         newrc->prti = rti;
1284                         newrc->forUpdate = oldrc->forUpdate;
1285                         newrc->noWait = oldrc->noWait;
1286                         newrc->isParent = false;
1287
1288                         parse->rowMarks = lappend(parse->rowMarks, newrc);
1289                 }
1290
1291                 /* Close child relations, but keep locks */
1292                 if (childOID != parentOID)
1293                         heap_close(newrelation, NoLock);
1294         }
1295
1296         heap_close(oldrelation, NoLock);
1297
1298         /*
1299          * If all the children were temp tables, pretend it's a non-inheritance
1300          * situation.  The duplicate RTE we added for the parent table is
1301          * harmless, so we don't bother to get rid of it.
1302          */
1303         if (list_length(appinfos) < 2)
1304         {
1305                 /* Clear flag before returning */
1306                 rte->inh = false;
1307                 return;
1308         }
1309
1310         /* Otherwise, OK to add to root->append_rel_list */
1311         root->append_rel_list = list_concat(root->append_rel_list, appinfos);
1312
1313         /*
1314          * The executor will check the parent table's access permissions when it
1315          * examines the parent's added RTE entry.  There's no need to check twice,
1316          * so turn off access check bits in the original RTE.
1317          */
1318         rte->requiredPerms = 0;
1319 }
1320
1321 /*
1322  * make_inh_translation_list
1323  *        Build the list of translations from parent Vars to child Vars for
1324  *        an inheritance child.
1325  *
1326  * For paranoia's sake, we match type as well as attribute name.
1327  */
1328 static void
1329 make_inh_translation_list(Relation oldrelation, Relation newrelation,
1330                                                   Index newvarno,
1331                                                   List **translated_vars)
1332 {
1333         List       *vars = NIL;
1334         TupleDesc       old_tupdesc = RelationGetDescr(oldrelation);
1335         TupleDesc       new_tupdesc = RelationGetDescr(newrelation);
1336         int                     oldnatts = old_tupdesc->natts;
1337         int                     newnatts = new_tupdesc->natts;
1338         int                     old_attno;
1339
1340         for (old_attno = 0; old_attno < oldnatts; old_attno++)
1341         {
1342                 Form_pg_attribute att;
1343                 char       *attname;
1344                 Oid                     atttypid;
1345                 int32           atttypmod;
1346                 int                     new_attno;
1347
1348                 att = old_tupdesc->attrs[old_attno];
1349                 if (att->attisdropped)
1350                 {
1351                         /* Just put NULL into this list entry */
1352                         vars = lappend(vars, NULL);
1353                         continue;
1354                 }
1355                 attname = NameStr(att->attname);
1356                 atttypid = att->atttypid;
1357                 atttypmod = att->atttypmod;
1358
1359                 /*
1360                  * When we are generating the "translation list" for the parent table
1361                  * of an inheritance set, no need to search for matches.
1362                  */
1363                 if (oldrelation == newrelation)
1364                 {
1365                         vars = lappend(vars, makeVar(newvarno,
1366                                                                                  (AttrNumber) (old_attno + 1),
1367                                                                                  atttypid,
1368                                                                                  atttypmod,
1369                                                                                  0));
1370                         continue;
1371                 }
1372
1373                 /*
1374                  * Otherwise we have to search for the matching column by name.
1375                  * There's no guarantee it'll have the same column position, because
1376                  * of cases like ALTER TABLE ADD COLUMN and multiple inheritance.
1377                  * However, in simple cases it will be the same column number, so try
1378                  * that before we go groveling through all the columns.
1379                  *
1380                  * Note: the test for (att = ...) != NULL cannot fail, it's just a
1381                  * notational device to include the assignment into the if-clause.
1382                  */
1383                 if (old_attno < newnatts &&
1384                         (att = new_tupdesc->attrs[old_attno]) != NULL &&
1385                         !att->attisdropped && att->attinhcount != 0 &&
1386                         strcmp(attname, NameStr(att->attname)) == 0)
1387                         new_attno = old_attno;
1388                 else
1389                 {
1390                         for (new_attno = 0; new_attno < newnatts; new_attno++)
1391                         {
1392                                 att = new_tupdesc->attrs[new_attno];
1393                                 if (!att->attisdropped && att->attinhcount != 0 &&
1394                                         strcmp(attname, NameStr(att->attname)) == 0)
1395                                         break;
1396                         }
1397                         if (new_attno >= newnatts)
1398                                 elog(ERROR, "could not find inherited attribute \"%s\" of relation \"%s\"",
1399                                          attname, RelationGetRelationName(newrelation));
1400                 }
1401
1402                 /* Found it, check type */
1403                 if (atttypid != att->atttypid || atttypmod != att->atttypmod)
1404                         elog(ERROR, "attribute \"%s\" of relation \"%s\" does not match parent's type",
1405                                  attname, RelationGetRelationName(newrelation));
1406
1407                 vars = lappend(vars, makeVar(newvarno,
1408                                                                          (AttrNumber) (new_attno + 1),
1409                                                                          atttypid,
1410                                                                          atttypmod,
1411                                                                          0));
1412         }
1413
1414         *translated_vars = vars;
1415 }
1416
1417 /*
1418  * translate_col_privs
1419  *        Translate a bitmapset representing per-column privileges from the
1420  *        parent rel's attribute numbering to the child's.
1421  *
1422  * The only surprise here is that we don't translate a parent whole-row
1423  * reference into a child whole-row reference.  That would mean requiring
1424  * permissions on all child columns, which is overly strict, since the
1425  * query is really only going to reference the inherited columns.  Instead
1426  * we set the per-column bits for all inherited columns.
1427  */
1428 static Bitmapset *
1429 translate_col_privs(const Bitmapset *parent_privs,
1430                                         List *translated_vars)
1431 {
1432         Bitmapset  *child_privs = NULL;
1433         bool            whole_row;
1434         int                     attno;
1435         ListCell   *lc;
1436
1437         /* System attributes have the same numbers in all tables */
1438         for (attno = FirstLowInvalidHeapAttributeNumber + 1; attno < 0; attno++)
1439         {
1440                 if (bms_is_member(attno - FirstLowInvalidHeapAttributeNumber,
1441                                                   parent_privs))
1442                         child_privs = bms_add_member(child_privs,
1443                                                                  attno - FirstLowInvalidHeapAttributeNumber);
1444         }
1445
1446         /* Check if parent has whole-row reference */
1447         whole_row = bms_is_member(InvalidAttrNumber - FirstLowInvalidHeapAttributeNumber,
1448                                                           parent_privs);
1449
1450         /* And now translate the regular user attributes, using the vars list */
1451         attno = InvalidAttrNumber;
1452         foreach(lc, translated_vars)
1453         {
1454                 Var                *var = (Var *) lfirst(lc);
1455
1456                 attno++;
1457                 if (var == NULL)                /* ignore dropped columns */
1458                         continue;
1459                 Assert(IsA(var, Var));
1460                 if (whole_row ||
1461                         bms_is_member(attno - FirstLowInvalidHeapAttributeNumber,
1462                                                   parent_privs))
1463                         child_privs = bms_add_member(child_privs,
1464                                                  var->varattno - FirstLowInvalidHeapAttributeNumber);
1465         }
1466
1467         return child_privs;
1468 }
1469
1470 /*
1471  * adjust_appendrel_attrs
1472  *        Copy the specified query or expression and translate Vars referring
1473  *        to the parent rel of the specified AppendRelInfo to refer to the
1474  *        child rel instead.  We also update rtindexes appearing outside Vars,
1475  *        such as resultRelation and jointree relids.
1476  *
1477  * Note: this is only applied after conversion of sublinks to subplans,
1478  * so we don't need to cope with recursion into sub-queries.
1479  *
1480  * Note: this is not hugely different from what ResolveNew() does; maybe
1481  * we should try to fold the two routines together.
1482  */
1483 Node *
1484 adjust_appendrel_attrs(Node *node, AppendRelInfo *appinfo)
1485 {
1486         Node       *result;
1487
1488         /*
1489          * Must be prepared to start with a Query or a bare expression tree.
1490          */
1491         if (node && IsA(node, Query))
1492         {
1493                 Query      *newnode;
1494
1495                 newnode = query_tree_mutator((Query *) node,
1496                                                                          adjust_appendrel_attrs_mutator,
1497                                                                          (void *) appinfo,
1498                                                                          QTW_IGNORE_RC_SUBQUERIES);
1499                 if (newnode->resultRelation == appinfo->parent_relid)
1500                 {
1501                         newnode->resultRelation = appinfo->child_relid;
1502                         /* Fix tlist resnos too, if it's inherited UPDATE */
1503                         if (newnode->commandType == CMD_UPDATE)
1504                                 newnode->targetList =
1505                                         adjust_inherited_tlist(newnode->targetList,
1506                                                                                    appinfo);
1507                 }
1508                 result = (Node *) newnode;
1509         }
1510         else
1511                 result = adjust_appendrel_attrs_mutator(node, appinfo);
1512
1513         return result;
1514 }
1515
1516 static Node *
1517 adjust_appendrel_attrs_mutator(Node *node, AppendRelInfo *context)
1518 {
1519         if (node == NULL)
1520                 return NULL;
1521         if (IsA(node, Var))
1522         {
1523                 Var                *var = (Var *) copyObject(node);
1524
1525                 if (var->varlevelsup == 0 &&
1526                         var->varno == context->parent_relid)
1527                 {
1528                         var->varno = context->child_relid;
1529                         var->varnoold = context->child_relid;
1530                         if (var->varattno > 0)
1531                         {
1532                                 Node       *newnode;
1533
1534                                 if (var->varattno > list_length(context->translated_vars))
1535                                         elog(ERROR, "attribute %d of relation \"%s\" does not exist",
1536                                                  var->varattno, get_rel_name(context->parent_reloid));
1537                                 newnode = copyObject(list_nth(context->translated_vars,
1538                                                                                           var->varattno - 1));
1539                                 if (newnode == NULL)
1540                                         elog(ERROR, "attribute %d of relation \"%s\" does not exist",
1541                                                  var->varattno, get_rel_name(context->parent_reloid));
1542                                 return newnode;
1543                         }
1544                         else if (var->varattno == 0)
1545                         {
1546                                 /*
1547                                  * Whole-row Var: if we are dealing with named rowtypes, we
1548                                  * can use a whole-row Var for the child table plus a coercion
1549                                  * step to convert the tuple layout to the parent's rowtype.
1550                                  * Otherwise we have to generate a RowExpr.
1551                                  */
1552                                 if (OidIsValid(context->child_reltype))
1553                                 {
1554                                         Assert(var->vartype == context->parent_reltype);
1555                                         if (context->parent_reltype != context->child_reltype)
1556                                         {
1557                                                 ConvertRowtypeExpr *r = makeNode(ConvertRowtypeExpr);
1558
1559                                                 r->arg = (Expr *) var;
1560                                                 r->resulttype = context->parent_reltype;
1561                                                 r->convertformat = COERCE_IMPLICIT_CAST;
1562                                                 r->location = -1;
1563                                                 /* Make sure the Var node has the right type ID, too */
1564                                                 var->vartype = context->child_reltype;
1565                                                 return (Node *) r;
1566                                         }
1567                                 }
1568                                 else
1569                                 {
1570                                         /*
1571                                          * Build a RowExpr containing the translated variables.
1572                                          */
1573                                         RowExpr    *rowexpr;
1574                                         List       *fields;
1575
1576                                         fields = (List *) copyObject(context->translated_vars);
1577                                         rowexpr = makeNode(RowExpr);
1578                                         rowexpr->args = fields;
1579                                         rowexpr->row_typeid = var->vartype;
1580                                         rowexpr->row_format = COERCE_IMPLICIT_CAST;
1581                                         rowexpr->colnames = NIL;
1582                                         rowexpr->location = -1;
1583
1584                                         return (Node *) rowexpr;
1585                                 }
1586                         }
1587                         /* system attributes don't need any other translation */
1588                 }
1589                 return (Node *) var;
1590         }
1591         if (IsA(node, CurrentOfExpr))
1592         {
1593                 CurrentOfExpr *cexpr = (CurrentOfExpr *) copyObject(node);
1594
1595                 if (cexpr->cvarno == context->parent_relid)
1596                         cexpr->cvarno = context->child_relid;
1597                 return (Node *) cexpr;
1598         }
1599         if (IsA(node, RangeTblRef))
1600         {
1601                 RangeTblRef *rtr = (RangeTblRef *) copyObject(node);
1602
1603                 if (rtr->rtindex == context->parent_relid)
1604                         rtr->rtindex = context->child_relid;
1605                 return (Node *) rtr;
1606         }
1607         if (IsA(node, JoinExpr))
1608         {
1609                 /* Copy the JoinExpr node with correct mutation of subnodes */
1610                 JoinExpr   *j;
1611
1612                 j = (JoinExpr *) expression_tree_mutator(node,
1613                                                                                           adjust_appendrel_attrs_mutator,
1614                                                                                                  (void *) context);
1615                 /* now fix JoinExpr's rtindex (probably never happens) */
1616                 if (j->rtindex == context->parent_relid)
1617                         j->rtindex = context->child_relid;
1618                 return (Node *) j;
1619         }
1620         if (IsA(node, PlaceHolderVar))
1621         {
1622                 /* Copy the PlaceHolderVar node with correct mutation of subnodes */
1623                 PlaceHolderVar *phv;
1624
1625                 phv = (PlaceHolderVar *) expression_tree_mutator(node,
1626                                                                                           adjust_appendrel_attrs_mutator,
1627                                                                                                                  (void *) context);
1628                 /* now fix PlaceHolderVar's relid sets */
1629                 if (phv->phlevelsup == 0)
1630                         phv->phrels = adjust_relid_set(phv->phrels,
1631                                                                                    context->parent_relid,
1632                                                                                    context->child_relid);
1633                 return (Node *) phv;
1634         }
1635         /* Shouldn't need to handle planner auxiliary nodes here */
1636         Assert(!IsA(node, SpecialJoinInfo));
1637         Assert(!IsA(node, AppendRelInfo));
1638         Assert(!IsA(node, PlaceHolderInfo));
1639         Assert(!IsA(node, RestrictInfo));
1640
1641         /*
1642          * NOTE: we do not need to recurse into sublinks, because they should
1643          * already have been converted to subplans before we see them.
1644          */
1645         Assert(!IsA(node, SubLink));
1646         Assert(!IsA(node, Query));
1647
1648         return expression_tree_mutator(node, adjust_appendrel_attrs_mutator,
1649                                                                    (void *) context);
1650 }
1651
1652 /*
1653  * Substitute newrelid for oldrelid in a Relid set
1654  */
1655 static Relids
1656 adjust_relid_set(Relids relids, Index oldrelid, Index newrelid)
1657 {
1658         if (bms_is_member(oldrelid, relids))
1659         {
1660                 /* Ensure we have a modifiable copy */
1661                 relids = bms_copy(relids);
1662                 /* Remove old, add new */
1663                 relids = bms_del_member(relids, oldrelid);
1664                 relids = bms_add_member(relids, newrelid);
1665         }
1666         return relids;
1667 }
1668
1669 /*
1670  * Adjust the targetlist entries of an inherited UPDATE operation
1671  *
1672  * The expressions have already been fixed, but we have to make sure that
1673  * the target resnos match the child table (they may not, in the case of
1674  * a column that was added after-the-fact by ALTER TABLE).      In some cases
1675  * this can force us to re-order the tlist to preserve resno ordering.
1676  * (We do all this work in special cases so that preptlist.c is fast for
1677  * the typical case.)
1678  *
1679  * The given tlist has already been through expression_tree_mutator;
1680  * therefore the TargetEntry nodes are fresh copies that it's okay to
1681  * scribble on.
1682  *
1683  * Note that this is not needed for INSERT because INSERT isn't inheritable.
1684  */
1685 static List *
1686 adjust_inherited_tlist(List *tlist, AppendRelInfo *context)
1687 {
1688         bool            changed_it = false;
1689         ListCell   *tl;
1690         List       *new_tlist;
1691         bool            more;
1692         int                     attrno;
1693
1694         /* This should only happen for an inheritance case, not UNION ALL */
1695         Assert(OidIsValid(context->parent_reloid));
1696
1697         /* Scan tlist and update resnos to match attnums of child rel */
1698         foreach(tl, tlist)
1699         {
1700                 TargetEntry *tle = (TargetEntry *) lfirst(tl);
1701                 Var                *childvar;
1702
1703                 if (tle->resjunk)
1704                         continue;                       /* ignore junk items */
1705
1706                 /* Look up the translation of this column: it must be a Var */
1707                 if (tle->resno <= 0 ||
1708                         tle->resno > list_length(context->translated_vars))
1709                         elog(ERROR, "attribute %d of relation \"%s\" does not exist",
1710                                  tle->resno, get_rel_name(context->parent_reloid));
1711                 childvar = (Var *) list_nth(context->translated_vars, tle->resno - 1);
1712                 if (childvar == NULL || !IsA(childvar, Var))
1713                         elog(ERROR, "attribute %d of relation \"%s\" does not exist",
1714                                  tle->resno, get_rel_name(context->parent_reloid));
1715
1716                 if (tle->resno != childvar->varattno)
1717                 {
1718                         tle->resno = childvar->varattno;
1719                         changed_it = true;
1720                 }
1721         }
1722
1723         /*
1724          * If we changed anything, re-sort the tlist by resno, and make sure
1725          * resjunk entries have resnos above the last real resno.  The sort
1726          * algorithm is a bit stupid, but for such a seldom-taken path, small is
1727          * probably better than fast.
1728          */
1729         if (!changed_it)
1730                 return tlist;
1731
1732         new_tlist = NIL;
1733         more = true;
1734         for (attrno = 1; more; attrno++)
1735         {
1736                 more = false;
1737                 foreach(tl, tlist)
1738                 {
1739                         TargetEntry *tle = (TargetEntry *) lfirst(tl);
1740
1741                         if (tle->resjunk)
1742                                 continue;               /* ignore junk items */
1743
1744                         if (tle->resno == attrno)
1745                                 new_tlist = lappend(new_tlist, tle);
1746                         else if (tle->resno > attrno)
1747                                 more = true;
1748                 }
1749         }
1750
1751         foreach(tl, tlist)
1752         {
1753                 TargetEntry *tle = (TargetEntry *) lfirst(tl);
1754
1755                 if (!tle->resjunk)
1756                         continue;                       /* here, ignore non-junk items */
1757
1758                 tle->resno = attrno;
1759                 new_tlist = lappend(new_tlist, tle);
1760                 attrno++;
1761         }
1762
1763         return new_tlist;
1764 }