granicus.if.org Git - postgresql/blob - 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 is also some code here to support planning of queries that use
   8  * inheritance (SELECT FROM foo*).      This no longer has much connection
   9  * to the processing of UNION queries, but it's still here.
  10  *
  11  *
  12  * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
  13  * Portions Copyright (c) 1994, Regents of the University of California
  14  *
  15  *
  16  * IDENTIFICATION
  17  *        $PostgreSQL: pgsql/src/backend/optimizer/prep/prepunion.c,v 1.124 2005/06/10 02:21:05 tgl Exp $
  18  *
  19  *-------------------------------------------------------------------------
  20  */
  21 #include "postgres.h"
  22
  23
  24 #include "access/heapam.h"
  25 #include "catalog/pg_type.h"
  26 #include "nodes/makefuncs.h"
  27 #include "optimizer/clauses.h"
  28 #include "optimizer/plancat.h"
  29 #include "optimizer/planmain.h"
  30 #include "optimizer/planner.h"
  31 #include "optimizer/prep.h"
  32 #include "optimizer/tlist.h"
  33 #include "parser/parse_clause.h"
  34 #include "parser/parse_coerce.h"
  35 #include "parser/parse_expr.h"
  36 #include "parser/parsetree.h"
  37 #include "utils/lsyscache.h"
  38
  39
  40 typedef struct
  41 {
  42         Index           old_rt_index;
  43         Index           new_rt_index;
  44         Oid                     old_rel_type;
  45         Oid                     new_rel_type;
  46         TupleDesc       old_tupdesc;
  47         TupleDesc       new_tupdesc;
  48         char       *old_rel_name;
  49         char       *new_rel_name;
  50 } adjust_inherited_attrs_context;
  51
  52 static Plan *recurse_set_operations(Node *setOp, PlannerInfo *root,
  53                                                                         double tuple_fraction,
  54                                                                         List *colTypes, bool junkOK,
  55                                                                         int flag, List *refnames_tlist,
  56                                                                         List **sortClauses);
  57 static Plan *generate_union_plan(SetOperationStmt *op, PlannerInfo *root,
  58                                                                  double tuple_fraction,
  59                                                                  List *refnames_tlist, List **sortClauses);
  60 static Plan *generate_nonunion_plan(SetOperationStmt *op, PlannerInfo *root,
  61                                            List *refnames_tlist, List **sortClauses);
  62 static List *recurse_union_children(Node *setOp, PlannerInfo *root,
  63                                                                         double tuple_fraction,
  64                                                                         SetOperationStmt *top_union,
  65                                                                         List *refnames_tlist);
  66 static List *generate_setop_tlist(List *colTypes, int flag,
  67                                          Index varno,
  68                                          bool hack_constants,
  69                                          List *input_tlist,
  70                                          List *refnames_tlist);
  71 static List *generate_append_tlist(List *colTypes, bool flag,
  72                                           List *input_plans,
  73                                           List *refnames_tlist);
  74 static bool tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK);
  75 static Node *adjust_inherited_attrs_mutator(Node *node,
  76                                                            adjust_inherited_attrs_context *context);
  77 static Relids adjust_relid_set(Relids relids, Index oldrelid, Index newrelid);
  78 static List *adjust_inherited_tlist(List *tlist,
  79                                            adjust_inherited_attrs_context *context);
  80
  81
  82 /*
  83  * plan_set_operations
  84  *
  85  *        Plans the queries for a tree of set operations (UNION/INTERSECT/EXCEPT)
  86  *
  87  * This routine only deals with the setOperations tree of the given query.
  88  * Any top-level ORDER BY requested in root->parse->sortClause will be added
  89  * when we return to grouping_planner.
  90  *
  91  * tuple_fraction is the fraction of tuples we expect will be retrieved.
  92  * tuple_fraction is interpreted as for grouping_planner(); in particular,
  93  * zero means "all the tuples will be fetched".  Any LIMIT present at the
  94  * top level has already been factored into tuple_fraction.
  95  *
  96  * *sortClauses is an output argument: it is set to a list of SortClauses
  97  * representing the result ordering of the topmost set operation.
  98  */
  99 Plan *
 100 plan_set_operations(PlannerInfo *root, double tuple_fraction,
 101                                         List **sortClauses)
 102 {
 103         Query      *parse = root->parse;
 104         SetOperationStmt *topop = (SetOperationStmt *) parse->setOperations;
 105         Node       *node;
 106         Query      *leftmostQuery;
 107
 108         Assert(topop && IsA(topop, SetOperationStmt));
 109
 110         /* check for unsupported stuff */
 111         Assert(parse->utilityStmt == NULL);
 112         Assert(parse->jointree->fromlist == NIL);
 113         Assert(parse->jointree->quals == NULL);
 114         Assert(parse->groupClause == NIL);
 115         Assert(parse->havingQual == NULL);
 116         Assert(parse->distinctClause == NIL);
 117
 118         /*
 119          * Find the leftmost component Query.  We need to use its column names
 120          * for all generated tlists (else SELECT INTO won't work right).
 121          */
 122         node = topop->larg;
 123         while (node && IsA(node, SetOperationStmt))
 124                 node = ((SetOperationStmt *) node)->larg;
 125         Assert(node && IsA(node, RangeTblRef));
 126         leftmostQuery = rt_fetch(((RangeTblRef *) node)->rtindex,
 127                                                          parse->rtable)->subquery;
 128         Assert(leftmostQuery != NULL);
 129
 130         /*
 131          * Recurse on setOperations tree to generate plans for set ops. The
 132          * final output plan should have just the column types shown as the
 133          * output from the top-level node, plus possibly resjunk working
 134          * columns (we can rely on upper-level nodes to deal with that).
 135          */
 136         return recurse_set_operations((Node *) topop, root, tuple_fraction,
 137                                                                   topop->colTypes, true, -1,
 138                                                                   leftmostQuery->targetList,
 139                                                                   sortClauses);
 140 }
 141
 142 /*
 143  * recurse_set_operations
 144  *        Recursively handle one step in a tree of set operations
 145  *
 146  * tuple_fraction: fraction of tuples we expect to retrieve from node
 147  * colTypes: list of type OIDs of expected output columns
 148  * junkOK: if true, child resjunk columns may be left in the result
 149  * flag: if >= 0, add a resjunk output column indicating value of flag
 150  * refnames_tlist: targetlist to take column names from
 151  * *sortClauses: receives list of SortClauses for result plan, if any
 152  */
 153 static Plan *
 154 recurse_set_operations(Node *setOp, PlannerInfo *root,
 155                                            double tuple_fraction,
 156                                            List *colTypes, bool junkOK,
 157                                            int flag, List *refnames_tlist,
 158                                            List **sortClauses)
 159 {
 160         if (IsA(setOp, RangeTblRef))
 161         {
 162                 RangeTblRef *rtr = (RangeTblRef *) setOp;
 163                 RangeTblEntry *rte = rt_fetch(rtr->rtindex, root->parse->rtable);
 164                 Query      *subquery = rte->subquery;
 165                 Plan       *subplan,
 166                                    *plan;
 167
 168                 Assert(subquery != NULL);
 169
 170                 /*
 171                  * Generate plan for primitive subquery
 172                  */
 173                 subplan = subquery_planner(subquery, tuple_fraction, NULL);
 174
 175                 /*
 176                  * Add a SubqueryScan with the caller-requested targetlist
 177                  */
 178                 plan = (Plan *)
 179                         make_subqueryscan(generate_setop_tlist(colTypes, flag,
 180                                                                                                    rtr->rtindex,
 181                                                                                                    true,
 182                                                                                                    subplan->targetlist,
 183                                                                                                    refnames_tlist),
 184                                                           NIL,
 185                                                           rtr->rtindex,
 186                                                           subplan);
 187
 188                 /*
 189                  * We don't bother to determine the subquery's output ordering
 190                  * since it won't be reflected in the set-op result anyhow.
 191                  */
 192                 *sortClauses = NIL;
 193
 194                 return plan;
 195         }
 196         else if (IsA(setOp, SetOperationStmt))
 197         {
 198                 SetOperationStmt *op = (SetOperationStmt *) setOp;
 199                 Plan       *plan;
 200
 201                 /* UNIONs are much different from INTERSECT/EXCEPT */
 202                 if (op->op == SETOP_UNION)
 203                         plan = generate_union_plan(op, root, tuple_fraction,
 204                                                                            refnames_tlist,
 205                                                                            sortClauses);
 206                 else
 207                         plan = generate_nonunion_plan(op, root,
 208                                                                                   refnames_tlist,
 209                                                                                   sortClauses);
 210
 211                 /*
 212                  * If necessary, add a Result node to project the caller-requested
 213                  * output columns.
 214                  *
 215                  * XXX you don't really want to know about this: setrefs.c will apply
 216                  * replace_vars_with_subplan_refs() to the Result node's tlist.
 217                  * This would fail if the Vars generated by generate_setop_tlist()
 218                  * were not exactly equal() to the corresponding tlist entries of
 219                  * the subplan.  However, since the subplan was generated by
 220                  * generate_union_plan() or generate_nonunion_plan(), and hence
 221                  * its tlist was generated by generate_append_tlist(), this will
 222                  * work.  We just tell generate_setop_tlist() to use varno 0.
 223                  */
 224                 if (flag >= 0 ||
 225                         !tlist_same_datatypes(plan->targetlist, colTypes, junkOK))
 226                 {
 227                         plan = (Plan *)
 228                                 make_result(generate_setop_tlist(colTypes, flag,
 229                                                                                                  0,
 230                                                                                                  false,
 231                                                                                                  plan->targetlist,
 232                                                                                                  refnames_tlist),
 233                                                         NULL,
 234                                                         plan);
 235                 }
 236                 return plan;
 237         }
 238         else
 239         {
 240                 elog(ERROR, "unrecognized node type: %d",
 241                          (int) nodeTag(setOp));
 242                 return NULL;                    /* keep compiler quiet */
 243         }
 244 }
 245
 246 /*
 247  * Generate plan for a UNION or UNION ALL node
 248  */
 249 static Plan *
 250 generate_union_plan(SetOperationStmt *op, PlannerInfo *root,
 251                                         double tuple_fraction,
 252                                         List *refnames_tlist,
 253                                         List **sortClauses)
 254 {
 255         List       *planlist;
 256         List       *tlist;
 257         Plan       *plan;
 258
 259         /*
 260          * If plain UNION, tell children to fetch all tuples.
 261          *
 262          * Note: in UNION ALL, we pass the top-level tuple_fraction unmodified
 263          * to each arm of the UNION ALL.  One could make a case for reducing
 264          * the tuple fraction for later arms (discounting by the expected size
 265          * of the earlier arms' results) but it seems not worth the trouble.
 266          * The normal case where tuple_fraction isn't already zero is a LIMIT
 267          * at top level, and passing it down as-is is usually enough to get the
 268          * desired result of preferring fast-start plans.
 269          */
 270         if (!op->all)
 271                 tuple_fraction = 0.0;
 272
 273         /*
 274          * If any of my children are identical UNION nodes (same op, all-flag,
 275          * and colTypes) then they can be merged into this node so that we
 276          * generate only one Append and Sort for the lot.  Recurse to find
 277          * such nodes and compute their children's plans.
 278          */
 279         planlist = list_concat(recurse_union_children(op->larg, root,
 280                                                                                                   tuple_fraction,
 281                                                                                                   op, refnames_tlist),
 282                                                    recurse_union_children(op->rarg, root,
 283                                                                                                   tuple_fraction,
 284                                                                                                   op, refnames_tlist));
 285
 286         /*
 287          * Generate tlist for Append plan node.
 288          *
 289          * The tlist for an Append plan isn't important as far as the Append is
 290          * concerned, but we must make it look real anyway for the benefit of
 291          * the next plan level up.
 292          */
 293         tlist = generate_append_tlist(op->colTypes, false,
 294                                                                   planlist, refnames_tlist);
 295
 296         /*
 297          * Append the child results together.
 298          */
 299         plan = (Plan *) make_append(planlist, false, tlist);
 300
 301         /*
 302          * For UNION ALL, we just need the Append plan.  For UNION, need to
 303          * add Sort and Unique nodes to produce unique output.
 304          */
 305         if (!op->all)
 306         {
 307                 List       *sortList;
 308
 309                 sortList = addAllTargetsToSortList(NULL, NIL, tlist, false);
 310                 if (sortList)
 311                 {
 312                         plan = (Plan *) make_sort_from_sortclauses(root, sortList, plan);
 313                         plan = (Plan *) make_unique(plan, sortList);
 314                 }
 315                 *sortClauses = sortList;
 316         }
 317         else
 318                 *sortClauses = NIL;
 319
 320         return plan;
 321 }
 322
 323 /*
 324  * Generate plan for an INTERSECT, INTERSECT ALL, EXCEPT, or EXCEPT ALL node
 325  */
 326 static Plan *
 327 generate_nonunion_plan(SetOperationStmt *op, PlannerInfo *root,
 328                                            List *refnames_tlist,
 329                                            List **sortClauses)
 330 {
 331         Plan       *lplan,
 332                            *rplan,
 333                            *plan;
 334         List       *tlist,
 335                            *sortList,
 336                            *planlist,
 337                            *child_sortclauses;
 338         SetOpCmd        cmd;
 339
 340         /* Recurse on children, ensuring their outputs are marked */
 341         lplan = recurse_set_operations(op->larg, root,
 342                                                                    0.0 /* all tuples needed */,
 343                                                                    op->colTypes, false, 0,
 344                                                                    refnames_tlist,
 345                                                                    &child_sortclauses);
 346         rplan = recurse_set_operations(op->rarg, root,
 347                                                                    0.0 /* all tuples needed */,
 348                                                                    op->colTypes, false, 1,
 349                                                                    refnames_tlist,
 350                                                                    &child_sortclauses);
 351         planlist = list_make2(lplan, rplan);
 352
 353         /*
 354          * Generate tlist for Append plan node.
 355          *
 356          * The tlist for an Append plan isn't important as far as the Append is
 357          * concerned, but we must make it look real anyway for the benefit of
 358          * the next plan level up.      In fact, it has to be real enough that the
 359          * flag column is shown as a variable not a constant, else setrefs.c
 360          * will get confused.
 361          */
 362         tlist = generate_append_tlist(op->colTypes, true,
 363                                                                   planlist, refnames_tlist);
 364
 365         /*
 366          * Append the child results together.
 367          */
 368         plan = (Plan *) make_append(planlist, false, tlist);
 369
 370         /*
 371          * Sort the child results, then add a SetOp plan node to generate the
 372          * correct output.
 373          */
 374         sortList = addAllTargetsToSortList(NULL, NIL, tlist, false);
 375
 376         if (sortList == NIL)            /* nothing to sort on? */
 377         {
 378                 *sortClauses = NIL;
 379                 return plan;
 380         }
 381
 382         plan = (Plan *) make_sort_from_sortclauses(root, sortList, plan);
 383         switch (op->op)
 384         {
 385                 case SETOP_INTERSECT:
 386                         cmd = op->all ? SETOPCMD_INTERSECT_ALL : SETOPCMD_INTERSECT;
 387                         break;
 388                 case SETOP_EXCEPT:
 389                         cmd = op->all ? SETOPCMD_EXCEPT_ALL : SETOPCMD_EXCEPT;
 390                         break;
 391                 default:
 392                         elog(ERROR, "unrecognized set op: %d",
 393                                  (int) op->op);
 394                         cmd = SETOPCMD_INTERSECT;       /* keep compiler quiet */
 395                         break;
 396         }
 397         plan = (Plan *) make_setop(cmd, plan, sortList, list_length(op->colTypes) + 1);
 398
 399         *sortClauses = sortList;
 400
 401         return plan;
 402 }
 403
 404 /*
 405  * Pull up children of a UNION node that are identically-propertied UNIONs.
 406  *
 407  * NOTE: we can also pull a UNION ALL up into a UNION, since the distinct
 408  * output rows will be lost anyway.
 409  */
 410 static List *
 411 recurse_union_children(Node *setOp, PlannerInfo *root,
 412                                            double tuple_fraction,
 413                                            SetOperationStmt *top_union,
 414                                            List *refnames_tlist)
 415 {
 416         List       *child_sortclauses;
 417
 418         if (IsA(setOp, SetOperationStmt))
 419         {
 420                 SetOperationStmt *op = (SetOperationStmt *) setOp;
 421
 422                 if (op->op == top_union->op &&
 423                         (op->all == top_union->all || op->all) &&
 424                         equal(op->colTypes, top_union->colTypes))
 425                 {
 426                         /* Same UNION, so fold children into parent's subplan list */
 427                         return list_concat(recurse_union_children(op->larg, root,
 428                                                                                                           tuple_fraction,
 429                                                                                                           top_union,
 430                                                                                                           refnames_tlist),
 431                                                            recurse_union_children(op->rarg, root,
 432                                                                                                           tuple_fraction,
 433                                                                                                           top_union,
 434                                                                                                           refnames_tlist));
 435                 }
 436         }
 437
 438         /*
 439          * Not same, so plan this child separately.
 440          *
 441          * Note we disallow any resjunk columns in child results.  This is
 442          * necessary since the Append node that implements the union won't do
 443          * any projection, and upper levels will get confused if some of our
 444          * output tuples have junk and some don't.  This case only arises when
 445          * we have an EXCEPT or INTERSECT as child, else there won't be
 446          * resjunk anyway.
 447          */
 448         return list_make1(recurse_set_operations(setOp, root,
 449                                                                                          tuple_fraction,
 450                                                                                          top_union->colTypes, false,
 451                                                                                          -1, refnames_tlist,
 452                                                                                          &child_sortclauses));
 453 }
 454
 455 /*
 456  * Generate targetlist for a set-operation plan node
 457  *
 458  * colTypes: column datatypes for non-junk columns
 459  * flag: -1 if no flag column needed, 0 or 1 to create a const flag column
 460  * varno: varno to use in generated Vars
 461  * hack_constants: true to copy up constants (see comments in code)
 462  * input_tlist: targetlist of this node's input node
 463  * refnames_tlist: targetlist to take column names from
 464  */
 465 static List *
 466 generate_setop_tlist(List *colTypes, int flag,
 467                                          Index varno,
 468                                          bool hack_constants,
 469                                          List *input_tlist,
 470                                          List *refnames_tlist)
 471 {
 472         List       *tlist = NIL;
 473         int                     resno = 1;
 474         ListCell   *i,
 475                            *j,
 476                            *k;
 477         TargetEntry *tle;
 478         Node       *expr;
 479
 480         j = list_head(input_tlist);
 481         k = list_head(refnames_tlist);
 482         foreach(i, colTypes)
 483         {
 484                 Oid                     colType = lfirst_oid(i);
 485                 TargetEntry *inputtle = (TargetEntry *) lfirst(j);
 486                 TargetEntry *reftle = (TargetEntry *) lfirst(k);
 487
 488                 Assert(inputtle->resno == resno);
 489                 Assert(reftle->resno == resno);
 490                 Assert(!inputtle->resjunk);
 491                 Assert(!reftle->resjunk);
 492
 493                 /*
 494                  * Generate columns referencing input columns and having
 495                  * appropriate data types and column names.  Insert datatype
 496                  * coercions where necessary.
 497                  *
 498                  * HACK: constants in the input's targetlist are copied up as-is
 499                  * rather than being referenced as subquery outputs.  This is
 500                  * mainly to ensure that when we try to coerce them to the output
 501                  * column's datatype, the right things happen for UNKNOWN
 502                  * constants.  But do this only at the first level of
 503                  * subquery-scan plans; we don't want phony constants appearing in
 504                  * the output tlists of upper-level nodes!
 505                  */
 506                 if (hack_constants && inputtle->expr && IsA(inputtle->expr, Const))
 507                         expr = (Node *) inputtle->expr;
 508                 else
 509                         expr = (Node *) makeVar(varno,
 510                                                                         inputtle->resno,
 511                                                                         exprType((Node *) inputtle->expr),
 512                                                                         exprTypmod((Node *) inputtle->expr),
 513                                                                         0);
 514                 if (exprType(expr) != colType)
 515                 {
 516                         expr = coerce_to_common_type(NULL,      /* no UNKNOWNs here */
 517                                                                                  expr,
 518                                                                                  colType,
 519                                                                                  "UNION/INTERSECT/EXCEPT");
 520                 }
 521                 tle = makeTargetEntry((Expr *) expr,
 522                                                           (AttrNumber) resno++,
 523                                                           pstrdup(reftle->resname),
 524                                                           false);
 525                 tlist = lappend(tlist, tle);
 526
 527                 j = lnext(j);
 528                 k = lnext(k);
 529         }
 530
 531         if (flag >= 0)
 532         {
 533                 /* Add a resjunk flag column */
 534                 /* flag value is the given constant */
 535                 expr = (Node *) makeConst(INT4OID,
 536                                                                   sizeof(int4),
 537                                                                   Int32GetDatum(flag),
 538                                                                   false,
 539                                                                   true);
 540                 tle = makeTargetEntry((Expr *) expr,
 541                                                           (AttrNumber) resno++,
 542                                                           pstrdup("flag"),
 543                                                           true);
 544                 tlist = lappend(tlist, tle);
 545         }
 546
 547         return tlist;
 548 }
 549
 550 /*
 551  * Generate targetlist for a set-operation Append node
 552  *
 553  * colTypes: column datatypes for non-junk columns
 554  * flag: true to create a flag column copied up from subplans
 555  * input_plans: list of sub-plans of the Append
 556  * refnames_tlist: targetlist to take column names from
 557  *
 558  * The entries in the Append's targetlist should always be simple Vars;
 559  * we just have to make sure they have the right datatypes and typmods.
 560  * The Vars are always generated with varno 0.
 561  */
 562 static List *
 563 generate_append_tlist(List *colTypes, bool flag,
 564                                           List *input_plans,
 565                                           List *refnames_tlist)
 566 {
 567         List       *tlist = NIL;
 568         int                     resno = 1;
 569         ListCell   *curColType;
 570         ListCell   *ref_tl_item;
 571         int                     colindex;
 572         TargetEntry *tle;
 573         Node       *expr;
 574         ListCell   *planl;
 575         int32      *colTypmods;
 576
 577         /*
 578          * First extract typmods to use.
 579          *
 580          * If the inputs all agree on type and typmod of a particular column, use
 581          * that typmod; else use -1.
 582          */
 583         colTypmods = (int32 *) palloc(list_length(colTypes) * sizeof(int32));
 584
 585         foreach(planl, input_plans)
 586         {
 587                 Plan       *subplan = (Plan *) lfirst(planl);
 588                 ListCell   *subtlist;
 589
 590                 curColType = list_head(colTypes);
 591                 colindex = 0;
 592                 foreach(subtlist, subplan->targetlist)
 593                 {
 594                         TargetEntry *subtle = (TargetEntry *) lfirst(subtlist);
 595
 596                         if (subtle->resjunk)
 597                                 continue;
 598                         Assert(curColType != NULL);
 599                         if (exprType((Node *) subtle->expr) == lfirst_oid(curColType))
 600                         {
 601                                 /* If first subplan, copy the typmod; else compare */
 602                                 int32           subtypmod = exprTypmod((Node *) subtle->expr);
 603
 604                                 if (planl == list_head(input_plans))
 605                                         colTypmods[colindex] = subtypmod;
 606                                 else if (subtypmod != colTypmods[colindex])
 607                                         colTypmods[colindex] = -1;
 608                         }
 609                         else
 610                         {
 611                                 /* types disagree, so force typmod to -1 */
 612                                 colTypmods[colindex] = -1;
 613                         }
 614                         curColType = lnext(curColType);
 615                         colindex++;
 616                 }
 617                 Assert(curColType == NULL);
 618         }
 619
 620         /*
 621          * Now we can build the tlist for the Append.
 622          */
 623         colindex = 0;
 624         forboth(curColType, colTypes, ref_tl_item, refnames_tlist)
 625         {
 626                 Oid                     colType = lfirst_oid(curColType);
 627                 int32           colTypmod = colTypmods[colindex++];
 628                 TargetEntry *reftle = (TargetEntry *) lfirst(ref_tl_item);
 629
 630                 Assert(reftle->resno == resno);
 631                 Assert(!reftle->resjunk);
 632                 expr = (Node *) makeVar(0,
 633                                                                 resno,
 634                                                                 colType,
 635                                                                 colTypmod,
 636                                                                 0);
 637                 tle = makeTargetEntry((Expr *) expr,
 638                                                           (AttrNumber) resno++,
 639                                                           pstrdup(reftle->resname),
 640                                                           false);
 641                 tlist = lappend(tlist, tle);
 642         }
 643
 644         if (flag)
 645         {
 646                 /* Add a resjunk flag column */
 647                 /* flag value is shown as copied up from subplan */
 648                 expr = (Node *) makeVar(0,
 649                                                                 resno,
 650                                                                 INT4OID,
 651                                                                 -1,
 652                                                                 0);
 653                 tle = makeTargetEntry((Expr *) expr,
 654                                                           (AttrNumber) resno++,
 655                                                           pstrdup("flag"),
 656                                                           true);
 657                 tlist = lappend(tlist, tle);
 658         }
 659
 660         pfree(colTypmods);
 661
 662         return tlist;
 663 }
 664
 665 /*
 666  * Does tlist have same datatypes as requested colTypes?
 667  *
 668  * Resjunk columns are ignored if junkOK is true; otherwise presence of
 669  * a resjunk column will always cause a 'false' result.
 670  */
 671 static bool
 672 tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK)
 673 {
 674         ListCell   *l;
 675         ListCell   *curColType = list_head(colTypes);
 676
 677         foreach(l, tlist)
 678         {
 679                 TargetEntry *tle = (TargetEntry *) lfirst(l);
 680
 681                 if (tle->resjunk)
 682                 {
 683                         if (!junkOK)
 684                                 return false;
 685                 }
 686                 else
 687                 {
 688                         if (curColType == NULL)
 689                                 return false;
 690                         if (exprType((Node *) tle->expr) != lfirst_oid(curColType))
 691                                 return false;
 692                         curColType = lnext(curColType);
 693                 }
 694         }
 695         if (curColType != NULL)
 696                 return false;
 697         return true;
 698 }
 699
 700
 701 /*
 702  * find_all_inheritors -
 703  *              Returns a list of relation OIDs including the given rel plus
 704  *              all relations that inherit from it, directly or indirectly.
 705  */
 706 List *
 707 find_all_inheritors(Oid parentrel)
 708 {
 709         List       *examined_relids = NIL;
 710         List       *unexamined_relids = list_make1_oid(parentrel);
 711
 712         /*
 713          * While the queue of unexamined relids is nonempty, remove the first
 714          * element, mark it examined, and find its direct descendants. NB:
 715          * cannot use foreach(), since we modify the queue inside loop.
 716          */
 717         while (unexamined_relids != NIL)
 718         {
 719                 Oid                     currentrel = linitial_oid(unexamined_relids);
 720                 List       *currentchildren;
 721
 722                 unexamined_relids = list_delete_first(unexamined_relids);
 723                 examined_relids = lappend_oid(examined_relids, currentrel);
 724                 currentchildren = find_inheritance_children(currentrel);
 725
 726                 /*
 727                  * Add to the queue only those children not already seen. This
 728                  * avoids making duplicate entries in case of multiple inheritance
 729                  * paths from the same parent.  (It'll also keep us from getting
 730                  * into an infinite loop, though theoretically there can't be any
 731                  * cycles in the inheritance graph anyway.)
 732                  */
 733                 currentchildren = list_difference_oid(currentchildren, examined_relids);
 734                 unexamined_relids = list_union_oid(unexamined_relids, currentchildren);
 735         }
 736
 737         return examined_relids;
 738 }
 739
 740 /*
 741  * expand_inherited_rtentry
 742  *              Check whether a rangetable entry represents an inheritance set.
 743  *              If so, add entries for all the child tables to the query's
 744  *              rangetable, and return an integer list of RT indexes for the
 745  *              whole inheritance set (parent and children).
 746  *              If not, return NIL.
 747  *
 748  * Note that the original RTE is considered to represent the whole
 749  * inheritance set.  The first member of the returned list is an RTE
 750  * for the same table, but with inh = false, to represent the parent table
 751  * in its role as a simple member of the set.  The original RT index is
 752  * never a member of the returned list.
 753  *
 754  * A childless table is never considered to be an inheritance set; therefore
 755  * the result will never be a one-element list.  It'll be either empty
 756  * or have two or more elements.
 757  *
 758  * Note: there are cases in which this routine will be invoked multiple
 759  * times on the same RTE.  We will generate a separate set of child RTEs
 760  * for each invocation.  This is somewhat wasteful but seems not worth
 761  * trying to avoid.
 762  */
 763 List *
 764 expand_inherited_rtentry(PlannerInfo *root, Index rti)
 765 {
 766         Query      *parse = root->parse;
 767         RangeTblEntry *rte = rt_fetch(rti, parse->rtable);
 768         Oid                     parentOID;
 769         List       *inhOIDs;
 770         List       *inhRTIs;
 771         ListCell   *l;
 772
 773         /* Does RT entry allow inheritance? */
 774         if (!rte->inh)
 775                 return NIL;
 776         Assert(rte->rtekind == RTE_RELATION);
 777         /* Fast path for common case of childless table */
 778         parentOID = rte->relid;
 779         if (!has_subclass(parentOID))
 780         {
 781                 /* Clear flag to save repeated tests if called again */
 782                 rte->inh = false;
 783                 return NIL;
 784         }
 785         /* Scan for all members of inheritance set */
 786         inhOIDs = find_all_inheritors(parentOID);
 787
 788         /*
 789          * Check that there's at least one descendant, else treat as no-child
 790          * case.  This could happen despite above has_subclass() check, if
 791          * table once had a child but no longer does.
 792          */
 793         if (list_length(inhOIDs) < 2)
 794         {
 795                 /* Clear flag to save repeated tests if called again */
 796                 rte->inh = false;
 797                 return NIL;
 798         }
 799
 800         /* OK, it's an inheritance set; expand it */
 801         inhRTIs = NIL;
 802         foreach(l, inhOIDs)
 803         {
 804                 Oid                     childOID = lfirst_oid(l);
 805                 RangeTblEntry *childrte;
 806                 Index           childRTindex;
 807
 808                 /*
 809                  * Build an RTE for the child, and attach to query's rangetable
 810                  * list. We copy most fields of the parent's RTE, but replace
 811                  * relation OID, and set inh = false.
 812                  */
 813                 childrte = copyObject(rte);
 814                 childrte->relid = childOID;
 815                 childrte->inh = false;
 816                 parse->rtable = lappend(parse->rtable, childrte);
 817                 childRTindex = list_length(parse->rtable);
 818                 inhRTIs = lappend_int(inhRTIs, childRTindex);
 819         }
 820
 821         /*
 822          * The executor will check the parent table's access permissions when
 823          * it examines the parent's inheritlist entry.  There's no need to
 824          * check twice, so turn off access check bits in the original RTE.
 825          * (If we are invoked more than once, extra copies of the child RTEs
 826          * will also not cause duplicate permission checks.)
 827          */
 828         rte->requiredPerms = 0;
 829
 830         return inhRTIs;
 831 }
 832
 833 /*
 834  * adjust_inherited_attrs
 835  *        Copy the specified query or expression and translate Vars referring
 836  *        to old_rt_index to refer to new_rt_index.
 837  *
 838  * We also adjust varattno to match the new table by column name, rather
 839  * than column number.  This hack makes it possible for child tables to have
 840  * different column positions for the "same" attribute as a parent, which
 841  * is necessary for ALTER TABLE ADD COLUMN.
 842  */
 843 Node *
 844 adjust_inherited_attrs(Node *node,
 845                                            Index old_rt_index, Oid old_relid,
 846                                            Index new_rt_index, Oid new_relid)
 847 {
 848         Node       *result;
 849         adjust_inherited_attrs_context context;
 850         Relation        oldrelation;
 851         Relation        newrelation;
 852
 853         /* Handle simple case simply... */
 854         if (old_rt_index == new_rt_index)
 855         {
 856                 Assert(old_relid == new_relid);
 857                 return copyObject(node);
 858         }
 859
 860         /*
 861          * We assume that by now the planner has acquired at least
 862          * AccessShareLock on both rels, and so we need no additional lock
 863          * now.
 864          */
 865         oldrelation = heap_open(old_relid, NoLock);
 866         newrelation = heap_open(new_relid, NoLock);
 867
 868         context.old_rt_index = old_rt_index;
 869         context.new_rt_index = new_rt_index;
 870         context.old_rel_type = oldrelation->rd_rel->reltype;
 871         context.new_rel_type = newrelation->rd_rel->reltype;
 872         context.old_tupdesc = RelationGetDescr(oldrelation);
 873         context.new_tupdesc = RelationGetDescr(newrelation);
 874         context.old_rel_name = RelationGetRelationName(oldrelation);
 875         context.new_rel_name = RelationGetRelationName(newrelation);
 876
 877         /*
 878          * Must be prepared to start with a Query or a bare expression tree.
 879          */
 880         if (node && IsA(node, Query))
 881         {
 882                 Query      *newnode;
 883
 884                 newnode = query_tree_mutator((Query *) node,
 885                                                                          adjust_inherited_attrs_mutator,
 886                                                                          (void *) &context,
 887                                                                          QTW_IGNORE_RT_SUBQUERIES);
 888                 if (newnode->resultRelation == old_rt_index)
 889                 {
 890                         newnode->resultRelation = new_rt_index;
 891                         /* Fix tlist resnos too, if it's inherited UPDATE */
 892                         if (newnode->commandType == CMD_UPDATE)
 893                                 newnode->targetList =
 894                                         adjust_inherited_tlist(newnode->targetList,
 895                                                                                    &context);
 896                 }
 897                 result = (Node *) newnode;
 898         }
 899         else
 900                 result = adjust_inherited_attrs_mutator(node, &context);
 901
 902         heap_close(oldrelation, NoLock);
 903         heap_close(newrelation, NoLock);
 904
 905         return result;
 906 }
 907
 908 /*
 909  * Translate parent's attribute number into child's.
 910  *
 911  * For paranoia's sake, we match type as well as attribute name.
 912  */
 913 static AttrNumber
 914 translate_inherited_attnum(AttrNumber old_attno,
 915                                                    adjust_inherited_attrs_context *context)
 916 {
 917         Form_pg_attribute att;
 918         char       *attname;
 919         Oid                     atttypid;
 920         int32           atttypmod;
 921         int                     newnatts;
 922         int                     i;
 923
 924         if (old_attno <= 0 || old_attno > context->old_tupdesc->natts)
 925                 elog(ERROR, "attribute %d of relation \"%s\" does not exist",
 926                          (int) old_attno, context->old_rel_name);
 927         att = context->old_tupdesc->attrs[old_attno - 1];
 928         if (att->attisdropped)
 929                 elog(ERROR, "attribute %d of relation \"%s\" does not exist",
 930                          (int) old_attno, context->old_rel_name);
 931         attname = NameStr(att->attname);
 932         atttypid = att->atttypid;
 933         atttypmod = att->atttypmod;
 934
 935         newnatts = context->new_tupdesc->natts;
 936         for (i = 0; i < newnatts; i++)
 937         {
 938                 att = context->new_tupdesc->attrs[i];
 939                 if (att->attisdropped)
 940                         continue;
 941                 if (strcmp(attname, NameStr(att->attname)) == 0)
 942                 {
 943                         /* Found it, check type */
 944                         if (atttypid != att->atttypid || atttypmod != att->atttypmod)
 945                                 elog(ERROR, "attribute \"%s\" of relation \"%s\" does not match parent's type",
 946                                          attname, context->new_rel_name);
 947                         return (AttrNumber) (i + 1);
 948                 }
 949         }
 950
 951         elog(ERROR, "attribute \"%s\" of relation \"%s\" does not exist",
 952                  attname, context->new_rel_name);
 953         return 0;                                       /* keep compiler quiet */
 954 }
 955
 956 static Node *
 957 adjust_inherited_attrs_mutator(Node *node,
 958                                                            adjust_inherited_attrs_context *context)
 959 {
 960         if (node == NULL)
 961                 return NULL;
 962         if (IsA(node, Var))
 963         {
 964                 Var                *var = (Var *) copyObject(node);
 965
 966                 if (var->varlevelsup == 0 &&
 967                         var->varno == context->old_rt_index)
 968                 {
 969                         var->varno = context->new_rt_index;
 970                         var->varnoold = context->new_rt_index;
 971                         if (var->varattno > 0)
 972                         {
 973                                 var->varattno = translate_inherited_attnum(var->varattno,
 974                                                                                                                    context);
 975                                 var->varoattno = var->varattno;
 976                         }
 977                         else if (var->varattno == 0)
 978                         {
 979                                 /*
 980                                  * Whole-row Var: we need to insert a coercion step to convert
 981                                  * the tuple layout to the parent's rowtype.
 982                                  */
 983                                 if (context->old_rel_type != context->new_rel_type)
 984                                 {
 985                                         ConvertRowtypeExpr *r = makeNode(ConvertRowtypeExpr);
 986
 987                                         r->arg = (Expr *) var;
 988                                         r->resulttype = context->old_rel_type;
 989                                         r->convertformat = COERCE_IMPLICIT_CAST;
 990                                         /* Make sure the Var node has the right type ID, too */
 991                                         Assert(var->vartype == context->old_rel_type);
 992                                         var->vartype = context->new_rel_type;
 993                                         return (Node *) r;
 994                                 }
 995                         }
 996                         /* system attributes don't need any translation */
 997                 }
 998                 return (Node *) var;
 999         }
1000         if (IsA(node, RangeTblRef))
1001         {
1002                 RangeTblRef *rtr = (RangeTblRef *) copyObject(node);
1003
1004                 if (rtr->rtindex == context->old_rt_index)
1005                         rtr->rtindex = context->new_rt_index;
1006                 return (Node *) rtr;
1007         }
1008         if (IsA(node, JoinExpr))
1009         {
1010                 /* Copy the JoinExpr node with correct mutation of subnodes */
1011                 JoinExpr   *j;
1012
1013                 j = (JoinExpr *) expression_tree_mutator(node,
1014                                                                                   adjust_inherited_attrs_mutator,
1015                                                                                                  (void *) context);
1016                 /* now fix JoinExpr's rtindex */
1017                 if (j->rtindex == context->old_rt_index)
1018                         j->rtindex = context->new_rt_index;
1019                 return (Node *) j;
1020         }
1021         if (IsA(node, InClauseInfo))
1022         {
1023                 /* Copy the InClauseInfo node with correct mutation of subnodes */
1024                 InClauseInfo *ininfo;
1025
1026                 ininfo = (InClauseInfo *) expression_tree_mutator(node,
1027                                                                                   adjust_inherited_attrs_mutator,
1028                                                                                                            (void *) context);
1029                 /* now fix InClauseInfo's relid sets */
1030                 ininfo->lefthand = adjust_relid_set(ininfo->lefthand,
1031                                                                                         context->old_rt_index,
1032                                                                                         context->new_rt_index);
1033                 ininfo->righthand = adjust_relid_set(ininfo->righthand,
1034                                                                                          context->old_rt_index,
1035                                                                                          context->new_rt_index);
1036                 return (Node *) ininfo;
1037         }
1038
1039         /*
1040          * We have to process RestrictInfo nodes specially.
1041          */
1042         if (IsA(node, RestrictInfo))
1043         {
1044                 RestrictInfo *oldinfo = (RestrictInfo *) node;
1045                 RestrictInfo *newinfo = makeNode(RestrictInfo);
1046
1047                 /* Copy all flat-copiable fields */
1048                 memcpy(newinfo, oldinfo, sizeof(RestrictInfo));
1049
1050                 /* Recursively fix the clause itself */
1051                 newinfo->clause = (Expr *)
1052                         adjust_inherited_attrs_mutator((Node *) oldinfo->clause, context);
1053
1054                 /* and the modified version, if an OR clause */
1055                 newinfo->orclause = (Expr *)
1056                         adjust_inherited_attrs_mutator((Node *) oldinfo->orclause, context);
1057
1058                 /* adjust relid sets too */
1059                 newinfo->clause_relids = adjust_relid_set(oldinfo->clause_relids,
1060                                                                                                   context->old_rt_index,
1061                                                                                                   context->new_rt_index);
1062                 newinfo->required_relids = adjust_relid_set(oldinfo->required_relids,
1063                                                                                                         context->old_rt_index,
1064                                                                                                         context->new_rt_index);
1065                 newinfo->left_relids = adjust_relid_set(oldinfo->left_relids,
1066                                                                                                 context->old_rt_index,
1067                                                                                                 context->new_rt_index);
1068                 newinfo->right_relids = adjust_relid_set(oldinfo->right_relids,
1069                                                                                                  context->old_rt_index,
1070                                                                                                  context->new_rt_index);
1071
1072                 /*
1073                  * Reset cached derivative fields, since these might need to have
1074                  * different values when considering the child relation.
1075                  */
1076                 newinfo->eval_cost.startup = -1;
1077                 newinfo->this_selec = -1;
1078                 newinfo->left_pathkey = NIL;
1079                 newinfo->right_pathkey = NIL;
1080                 newinfo->left_mergescansel = -1;
1081                 newinfo->right_mergescansel = -1;
1082                 newinfo->left_bucketsize = -1;
1083                 newinfo->right_bucketsize = -1;
1084
1085                 return (Node *) newinfo;
1086         }
1087
1088         /*
1089          * NOTE: we do not need to recurse into sublinks, because they should
1090          * already have been converted to subplans before we see them.
1091          */
1092         Assert(!IsA(node, SubLink));
1093         Assert(!IsA(node, Query));
1094
1095         /*
1096          * BUT: although we don't need to recurse into subplans, we do need to
1097          * make sure that they are copied, not just referenced as
1098          * expression_tree_mutator will do by default.  Otherwise we'll have
1099          * the same subplan node referenced from each arm of the inheritance
1100          * APPEND plan, which will cause trouble in the executor.  This is a
1101          * kluge that should go away when we redesign querytrees.
1102          */
1103         if (is_subplan(node))
1104         {
1105                 SubPlan    *subplan;
1106
1107                 /* Copy the node and process subplan args */
1108                 node = expression_tree_mutator(node, adjust_inherited_attrs_mutator,
1109                                                                            (void *) context);
1110                 /* Make sure we have separate copies of subplan and its rtable */
1111                 subplan = (SubPlan *) node;
1112                 subplan->plan = copyObject(subplan->plan);
1113                 subplan->rtable = copyObject(subplan->rtable);
1114                 return node;
1115         }
1116
1117         return expression_tree_mutator(node, adjust_inherited_attrs_mutator,
1118                                                                    (void *) context);
1119 }
1120
1121 /*
1122  * Substitute newrelid for oldrelid in a Relid set
1123  */
1124 static Relids
1125 adjust_relid_set(Relids relids, Index oldrelid, Index newrelid)
1126 {
1127         if (bms_is_member(oldrelid, relids))
1128         {
1129                 /* Ensure we have a modifiable copy */
1130                 relids = bms_copy(relids);
1131                 /* Remove old, add new */
1132                 relids = bms_del_member(relids, oldrelid);
1133                 relids = bms_add_member(relids, newrelid);
1134         }
1135         return relids;
1136 }
1137
1138 /*
1139  * Adjust the targetlist entries of an inherited UPDATE operation
1140  *
1141  * The expressions have already been fixed, but we have to make sure that
1142  * the target resnos match the child table (they may not, in the case of
1143  * a column that was added after-the-fact by ALTER TABLE).      In some cases
1144  * this can force us to re-order the tlist to preserve resno ordering.
1145  * (We do all this work in special cases so that preptlist.c is fast for
1146  * the typical case.)
1147  *
1148  * The given tlist has already been through expression_tree_mutator;
1149  * therefore the TargetEntry nodes are fresh copies that it's okay to
1150  * scribble on.
1151  *
1152  * Note that this is not needed for INSERT because INSERT isn't inheritable.
1153  */
1154 static List *
1155 adjust_inherited_tlist(List *tlist,
1156                                            adjust_inherited_attrs_context *context)
1157 {
1158         bool            changed_it = false;
1159         ListCell   *tl;
1160         List       *new_tlist;
1161         bool            more;
1162         int                     attrno;
1163
1164         /* Scan tlist and update resnos to match attnums of new_relid */
1165         foreach(tl, tlist)
1166         {
1167                 TargetEntry *tle = (TargetEntry *) lfirst(tl);
1168
1169                 if (tle->resjunk)
1170                         continue;                       /* ignore junk items */
1171
1172                 attrno = translate_inherited_attnum(tle->resno, context);
1173
1174                 if (tle->resno != attrno)
1175                 {
1176                         tle->resno = attrno;
1177                         changed_it = true;
1178                 }
1179         }
1180
1181         /*
1182          * If we changed anything, re-sort the tlist by resno, and make sure
1183          * resjunk entries have resnos above the last real resno.  The sort
1184          * algorithm is a bit stupid, but for such a seldom-taken path, small
1185          * is probably better than fast.
1186          */
1187         if (!changed_it)
1188                 return tlist;
1189
1190         new_tlist = NIL;
1191         more = true;
1192         for (attrno = 1; more; attrno++)
1193         {
1194                 more = false;
1195                 foreach(tl, tlist)
1196                 {
1197                         TargetEntry *tle = (TargetEntry *) lfirst(tl);
1198
1199                         if (tle->resjunk)
1200                                 continue;               /* ignore junk items */
1201
1202                         if (tle->resno == attrno)
1203                                 new_tlist = lappend(new_tlist, tle);
1204                         else if (tle->resno > attrno)
1205                                 more = true;
1206                 }
1207         }
1208
1209         foreach(tl, tlist)
1210         {
1211                 TargetEntry *tle = (TargetEntry *) lfirst(tl);
1212
1213                 if (!tle->resjunk)
1214                         continue;                       /* here, ignore non-junk items */
1215
1216                 tle->resno = attrno;
1217                 new_tlist = lappend(new_tlist, tle);
1218                 attrno++;
1219         }
1220
1221         return new_tlist;
1222 }