granicus.if.org Git - postgresql/blob - src/backend/optimizer/plan/subselect.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * subselect.c
   4  *        Planning routines for subselects and parameters.
   5  *
   6  * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  * IDENTIFICATION
  10  *        $PostgreSQL: pgsql/src/backend/optimizer/plan/subselect.c,v 1.131 2008/07/10 01:17:29 tgl Exp $
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #include "postgres.h"
  15
  16 #include "catalog/pg_operator.h"
  17 #include "catalog/pg_type.h"
  18 #include "miscadmin.h"
  19 #include "nodes/makefuncs.h"
  20 #include "optimizer/clauses.h"
  21 #include "optimizer/cost.h"
  22 #include "optimizer/planmain.h"
  23 #include "optimizer/planner.h"
  24 #include "optimizer/subselect.h"
  25 #include "optimizer/var.h"
  26 #include "parser/parse_expr.h"
  27 #include "parser/parse_relation.h"
  28 #include "parser/parsetree.h"
  29 #include "rewrite/rewriteManip.h"
  30 #include "utils/builtins.h"
  31 #include "utils/lsyscache.h"
  32 #include "utils/syscache.h"
  33
  34
  35 typedef struct convert_testexpr_context
  36 {
  37         PlannerInfo *root;
  38         List       *subst_nodes;        /* Nodes to substitute for Params */
  39 } convert_testexpr_context;
  40
  41 typedef struct process_sublinks_context
  42 {
  43         PlannerInfo *root;
  44         bool            isTopQual;
  45 } process_sublinks_context;
  46
  47 typedef struct finalize_primnode_context
  48 {
  49         PlannerInfo *root;
  50         Bitmapset  *paramids;           /* Non-local PARAM_EXEC paramids found */
  51 } finalize_primnode_context;
  52
  53
  54 static List *generate_subquery_params(PlannerInfo *root, List *tlist,
  55                                                                           List **paramIds);
  56 static List *generate_subquery_vars(PlannerInfo *root, List *tlist,
  57                                                                         Index varno);
  58 static Node *convert_testexpr(PlannerInfo *root,
  59                                  Node *testexpr,
  60                                  List *subst_nodes);
  61 static Node *convert_testexpr_mutator(Node *node,
  62                                                  convert_testexpr_context *context);
  63 static bool subplan_is_hashable(SubLink *slink, SubPlan *node, Plan *plan);
  64 static bool hash_ok_operator(OpExpr *expr);
  65 static Node *replace_correlation_vars_mutator(Node *node, PlannerInfo *root);
  66 static Node *process_sublinks_mutator(Node *node,
  67                                                  process_sublinks_context *context);
  68 static Bitmapset *finalize_plan(PlannerInfo *root,
  69                           Plan *plan,
  70                           Bitmapset *valid_params);
  71 static bool finalize_primnode(Node *node, finalize_primnode_context *context);
  72
  73
  74 /*
  75  * Generate a Param node to replace the given Var,
  76  * which is expected to have varlevelsup > 0 (ie, it is not local).
  77  */
  78 static Param *
  79 replace_outer_var(PlannerInfo *root, Var *var)
  80 {
  81         Param      *retval;
  82         ListCell   *ppl;
  83         PlannerParamItem *pitem;
  84         Index           abslevel;
  85         int                     i;
  86
  87         Assert(var->varlevelsup > 0 && var->varlevelsup < root->query_level);
  88         abslevel = root->query_level - var->varlevelsup;
  89
  90         /*
  91          * If there's already a paramlist entry for this same Var, just use it.
  92          * NOTE: in sufficiently complex querytrees, it is possible for the same
  93          * varno/abslevel to refer to different RTEs in different parts of the
  94          * parsetree, so that different fields might end up sharing the same Param
  95          * number.      As long as we check the vartype as well, I believe that this
  96          * sort of aliasing will cause no trouble. The correct field should get
  97          * stored into the Param slot at execution in each part of the tree.
  98          *
  99          * We also need to demand a match on vartypmod.  This does not matter for
 100          * the Param itself, since those are not typmod-dependent, but it does
 101          * matter when make_subplan() instantiates a modified copy of the Var for
 102          * a subplan's args list.
 103          */
 104         i = 0;
 105         foreach(ppl, root->glob->paramlist)
 106         {
 107                 pitem = (PlannerParamItem *) lfirst(ppl);
 108                 if (pitem->abslevel == abslevel && IsA(pitem->item, Var))
 109                 {
 110                         Var                *pvar = (Var *) pitem->item;
 111
 112                         if (pvar->varno == var->varno &&
 113                                 pvar->varattno == var->varattno &&
 114                                 pvar->vartype == var->vartype &&
 115                                 pvar->vartypmod == var->vartypmod)
 116                                 break;
 117                 }
 118                 i++;
 119         }
 120
 121         if (!ppl)
 122         {
 123                 /* Nope, so make a new one */
 124                 var = (Var *) copyObject(var);
 125                 var->varlevelsup = 0;
 126
 127                 pitem = makeNode(PlannerParamItem);
 128                 pitem->item = (Node *) var;
 129                 pitem->abslevel = abslevel;
 130
 131                 root->glob->paramlist = lappend(root->glob->paramlist, pitem);
 132                 /* i is already the correct index for the new item */
 133         }
 134
 135         retval = makeNode(Param);
 136         retval->paramkind = PARAM_EXEC;
 137         retval->paramid = i;
 138         retval->paramtype = var->vartype;
 139         retval->paramtypmod = var->vartypmod;
 140
 141         return retval;
 142 }
 143
 144 /*
 145  * Generate a Param node to replace the given Aggref
 146  * which is expected to have agglevelsup > 0 (ie, it is not local).
 147  */
 148 static Param *
 149 replace_outer_agg(PlannerInfo *root, Aggref *agg)
 150 {
 151         Param      *retval;
 152         PlannerParamItem *pitem;
 153         Index           abslevel;
 154         int                     i;
 155
 156         Assert(agg->agglevelsup > 0 && agg->agglevelsup < root->query_level);
 157         abslevel = root->query_level - agg->agglevelsup;
 158
 159         /*
 160          * It does not seem worthwhile to try to match duplicate outer aggs. Just
 161          * make a new slot every time.
 162          */
 163         agg = (Aggref *) copyObject(agg);
 164         IncrementVarSublevelsUp((Node *) agg, -((int) agg->agglevelsup), 0);
 165         Assert(agg->agglevelsup == 0);
 166
 167         pitem = makeNode(PlannerParamItem);
 168         pitem->item = (Node *) agg;
 169         pitem->abslevel = abslevel;
 170
 171         root->glob->paramlist = lappend(root->glob->paramlist, pitem);
 172         i = list_length(root->glob->paramlist) - 1;
 173
 174         retval = makeNode(Param);
 175         retval->paramkind = PARAM_EXEC;
 176         retval->paramid = i;
 177         retval->paramtype = agg->aggtype;
 178         retval->paramtypmod = -1;
 179
 180         return retval;
 181 }
 182
 183 /*
 184  * Generate a new Param node that will not conflict with any other.
 185  *
 186  * This is used to allocate PARAM_EXEC slots for subplan outputs.
 187  */
 188 static Param *
 189 generate_new_param(PlannerInfo *root, Oid paramtype, int32 paramtypmod)
 190 {
 191         Param      *retval;
 192         PlannerParamItem *pitem;
 193
 194         retval = makeNode(Param);
 195         retval->paramkind = PARAM_EXEC;
 196         retval->paramid = list_length(root->glob->paramlist);
 197         retval->paramtype = paramtype;
 198         retval->paramtypmod = paramtypmod;
 199
 200         pitem = makeNode(PlannerParamItem);
 201         pitem->item = (Node *) retval;
 202         pitem->abslevel = root->query_level;
 203
 204         root->glob->paramlist = lappend(root->glob->paramlist, pitem);
 205
 206         return retval;
 207 }
 208
 209 /*
 210  * Get the datatype of the first column of the plan's output.
 211  *
 212  * This is stored for ARRAY_SUBLINK and for exprType(), which doesn't have any
 213  * way to get at the plan associated with a SubPlan node.  We really only need
 214  * the value for EXPR_SUBLINK and ARRAY_SUBLINK subplans, but for consistency
 215  * we set it always.
 216  */
 217 static Oid
 218 get_first_col_type(Plan *plan)
 219 {
 220         TargetEntry *tent = (TargetEntry *) linitial(plan->targetlist);
 221
 222         Assert(IsA(tent, TargetEntry));
 223         Assert(!tent->resjunk);
 224         return exprType((Node *) tent->expr);
 225 }
 226
 227 /*
 228  * Convert a SubLink (as created by the parser) into a SubPlan.
 229  *
 230  * We are given the original SubLink and the already-processed testexpr
 231  * (use this instead of the SubLink's own field).  We are also told if
 232  * this expression appears at top level of a WHERE/HAVING qual.
 233  *
 234  * The result is whatever we need to substitute in place of the SubLink
 235  * node in the executable expression.  This will be either the SubPlan
 236  * node (if we have to do the subplan as a subplan), or a Param node
 237  * representing the result of an InitPlan, or a row comparison expression
 238  * tree containing InitPlan Param nodes.
 239  */
 240 static Node *
 241 make_subplan(PlannerInfo *root, SubLink *slink, Node *testexpr, bool isTopQual)
 242 {
 243         Query      *subquery = (Query *) (slink->subselect);
 244         double          tuple_fraction;
 245         SubPlan    *splan;
 246         Plan       *plan;
 247         PlannerInfo *subroot;
 248         bool            isInitPlan;
 249         Bitmapset  *tmpset;
 250         int                     paramid;
 251         Node       *result;
 252
 253         /*
 254          * Copy the source Query node.  This is a quick and dirty kluge to resolve
 255          * the fact that the parser can generate trees with multiple links to the
 256          * same sub-Query node, but the planner wants to scribble on the Query.
 257          * Try to clean this up when we do querytree redesign...
 258          */
 259         subquery = (Query *) copyObject(subquery);
 260
 261         /*
 262          * For an EXISTS subplan, tell lower-level planner to expect that only the
 263          * first tuple will be retrieved.  For ALL and ANY subplans, we will be
 264          * able to stop evaluating if the test condition fails, so very often not
 265          * all the tuples will be retrieved; for lack of a better idea, specify
 266          * 50% retrieval.  For EXPR and ROWCOMPARE subplans, use default behavior
 267          * (we're only expecting one row out, anyway).
 268          *
 269          * NOTE: if you change these numbers, also change cost_qual_eval_walker()
 270          * and get_initplan_cost() in path/costsize.c.
 271          *
 272          * XXX If an ALL/ANY subplan is uncorrelated, we may decide to hash or
 273          * materialize its result below.  In that case it would've been better to
 274          * specify full retrieval.      At present, however, we can only detect
 275          * correlation or lack of it after we've made the subplan :-(. Perhaps
 276          * detection of correlation should be done as a separate step. Meanwhile,
 277          * we don't want to be too optimistic about the percentage of tuples
 278          * retrieved, for fear of selecting a plan that's bad for the
 279          * materialization case.
 280          */
 281         if (slink->subLinkType == EXISTS_SUBLINK)
 282                 tuple_fraction = 1.0;   /* just like a LIMIT 1 */
 283         else if (slink->subLinkType == ALL_SUBLINK ||
 284                          slink->subLinkType == ANY_SUBLINK)
 285                 tuple_fraction = 0.5;   /* 50% */
 286         else
 287                 tuple_fraction = 0.0;   /* default behavior */
 288
 289         /*
 290          * Generate the plan for the subquery.
 291          */
 292         plan = subquery_planner(root->glob, subquery,
 293                                                         root->query_level + 1,
 294                                                         tuple_fraction,
 295                                                         &subroot);
 296
 297         /*
 298          * Initialize the SubPlan node.  Note plan_id isn't set yet.
 299          */
 300         splan = makeNode(SubPlan);
 301         splan->subLinkType = slink->subLinkType;
 302         splan->testexpr = NULL;
 303         splan->paramIds = NIL;
 304         splan->firstColType = get_first_col_type(plan);
 305         splan->useHashTable = false;
 306         /* At top level of a qual, can treat UNKNOWN the same as FALSE */
 307         splan->unknownEqFalse = isTopQual;
 308         splan->setParam = NIL;
 309         splan->parParam = NIL;
 310         splan->args = NIL;
 311
 312         /*
 313          * Make parParam list of params that current query level will pass to this
 314          * child plan.
 315          */
 316         tmpset = bms_copy(plan->extParam);
 317         while ((paramid = bms_first_member(tmpset)) >= 0)
 318         {
 319                 PlannerParamItem *pitem = list_nth(root->glob->paramlist, paramid);
 320
 321                 if (pitem->abslevel == root->query_level)
 322                         splan->parParam = lappend_int(splan->parParam, paramid);
 323         }
 324         bms_free(tmpset);
 325
 326         /*
 327          * Un-correlated or undirect correlated plans of EXISTS, EXPR, ARRAY, or
 328          * ROWCOMPARE types can be used as initPlans.  For EXISTS, EXPR, or ARRAY,
 329          * we just produce a Param referring to the result of evaluating the
 330          * initPlan.  For ROWCOMPARE, we must modify the testexpr tree to contain
 331          * PARAM_EXEC Params instead of the PARAM_SUBLINK Params emitted by the
 332          * parser.
 333          */
 334         if (splan->parParam == NIL && slink->subLinkType == EXISTS_SUBLINK)
 335         {
 336                 Param      *prm;
 337
 338                 prm = generate_new_param(root, BOOLOID, -1);
 339                 splan->setParam = list_make1_int(prm->paramid);
 340                 isInitPlan = true;
 341                 result = (Node *) prm;
 342         }
 343         else if (splan->parParam == NIL && slink->subLinkType == EXPR_SUBLINK)
 344         {
 345                 TargetEntry *te = linitial(plan->targetlist);
 346                 Param      *prm;
 347
 348                 Assert(!te->resjunk);
 349                 prm = generate_new_param(root,
 350                                                                  exprType((Node *) te->expr),
 351                                                                  exprTypmod((Node *) te->expr));
 352                 splan->setParam = list_make1_int(prm->paramid);
 353                 isInitPlan = true;
 354                 result = (Node *) prm;
 355         }
 356         else if (splan->parParam == NIL && slink->subLinkType == ARRAY_SUBLINK)
 357         {
 358                 TargetEntry *te = linitial(plan->targetlist);
 359                 Oid                     arraytype;
 360                 Param      *prm;
 361
 362                 Assert(!te->resjunk);
 363                 arraytype = get_array_type(exprType((Node *) te->expr));
 364                 if (!OidIsValid(arraytype))
 365                         elog(ERROR, "could not find array type for datatype %s",
 366                                  format_type_be(exprType((Node *) te->expr)));
 367                 prm = generate_new_param(root,
 368                                                                  arraytype,
 369                                                                  exprTypmod((Node *) te->expr));
 370                 splan->setParam = list_make1_int(prm->paramid);
 371                 isInitPlan = true;
 372                 result = (Node *) prm;
 373         }
 374         else if (splan->parParam == NIL && slink->subLinkType == ROWCOMPARE_SUBLINK)
 375         {
 376                 /* Adjust the Params */
 377                 List       *params;
 378
 379                 params = generate_subquery_params(root,
 380                                                                                   plan->targetlist,
 381                                                                                   &splan->paramIds);
 382                 result = convert_testexpr(root,
 383                                                                   testexpr,
 384                                                                   params);
 385                 splan->setParam = list_copy(splan->paramIds);
 386                 isInitPlan = true;
 387
 388                 /*
 389                  * The executable expression is returned to become part of the outer
 390                  * plan's expression tree; it is not kept in the initplan node.
 391                  */
 392         }
 393         else
 394         {
 395                 List       *args;
 396                 ListCell   *l;
 397
 398                 if (testexpr)
 399                 {
 400                         List       *params;
 401
 402                         /* Adjust the Params in the testexpr */
 403                         params = generate_subquery_params(root,
 404                                                                                           plan->targetlist,
 405                                                                                           &splan->paramIds);
 406                         splan->testexpr = convert_testexpr(root,
 407                                                                                            testexpr,
 408                                                                                            params);
 409                 }
 410
 411                 /*
 412                  * We can't convert subplans of ALL_SUBLINK or ANY_SUBLINK types to
 413                  * initPlans, even when they are uncorrelated or undirect correlated,
 414                  * because we need to scan the output of the subplan for each outer
 415                  * tuple.  But if it's an IN (= ANY) test, we might be able to use a
 416                  * hashtable to avoid comparing all the tuples.
 417                  */
 418                 if (subplan_is_hashable(slink, splan, plan))
 419                         splan->useHashTable = true;
 420
 421                 /*
 422                  * Otherwise, we have the option to tack a MATERIAL node onto the top
 423                  * of the subplan, to reduce the cost of reading it repeatedly.  This
 424                  * is pointless for a direct-correlated subplan, since we'd have to
 425                  * recompute its results each time anyway.      For uncorrelated/undirect
 426                  * correlated subplans, we add MATERIAL unless the subplan's top plan
 427                  * node would materialize its output anyway.
 428                  */
 429                 else if (splan->parParam == NIL)
 430                 {
 431                         bool            use_material;
 432
 433                         switch (nodeTag(plan))
 434                         {
 435                                 case T_Material:
 436                                 case T_FunctionScan:
 437                                 case T_Sort:
 438                                         use_material = false;
 439                                         break;
 440                                 default:
 441                                         use_material = true;
 442                                         break;
 443                         }
 444                         if (use_material)
 445                                 plan = materialize_finished_plan(plan);
 446                 }
 447
 448                 /*
 449                  * Make splan->args from parParam.
 450                  */
 451                 args = NIL;
 452                 foreach(l, splan->parParam)
 453                 {
 454                         PlannerParamItem *pitem = list_nth(root->glob->paramlist,
 455                                                                                            lfirst_int(l));
 456
 457                         /*
 458                          * The Var or Aggref has already been adjusted to have the correct
 459                          * varlevelsup or agglevelsup.  We probably don't even need to
 460                          * copy it again, but be safe.
 461                          */
 462                         args = lappend(args, copyObject(pitem->item));
 463                 }
 464                 splan->args = args;
 465
 466                 result = (Node *) splan;
 467                 isInitPlan = false;
 468         }
 469
 470         /*
 471          * Add the subplan and its rtable to the global lists.
 472          */
 473         root->glob->subplans = lappend(root->glob->subplans,
 474                                                                    plan);
 475         root->glob->subrtables = lappend(root->glob->subrtables,
 476                                                                          subroot->parse->rtable);
 477         splan->plan_id = list_length(root->glob->subplans);
 478
 479         if (isInitPlan)
 480                 root->init_plans = lappend(root->init_plans, splan);
 481
 482         /*
 483          * A parameterless subplan (not initplan) should be prepared to handle
 484          * REWIND efficiently.  If it has direct parameters then there's no point
 485          * since it'll be reset on each scan anyway; and if it's an initplan then
 486          * there's no point since it won't get re-run without parameter changes
 487          * anyway.      The input of a hashed subplan doesn't need REWIND either.
 488          */
 489         if (splan->parParam == NIL && !isInitPlan && !splan->useHashTable)
 490                 root->glob->rewindPlanIDs = bms_add_member(root->glob->rewindPlanIDs,
 491                                                                                                    splan->plan_id);
 492
 493         return result;
 494 }
 495
 496 /*
 497  * generate_subquery_params: build a list of Params representing the output
 498  * columns of a sublink's sub-select, given the sub-select's targetlist.
 499  *
 500  * We also return an integer list of the paramids of the Params.
 501  */
 502 static List *
 503 generate_subquery_params(PlannerInfo *root, List *tlist, List **paramIds)
 504 {
 505         List       *result;
 506         List       *ids;
 507         ListCell   *lc;
 508
 509         result = ids = NIL;
 510         foreach(lc, tlist)
 511         {
 512                 TargetEntry *tent = (TargetEntry *) lfirst(lc);
 513                 Param      *param;
 514
 515                 if (tent->resjunk)
 516                         continue;
 517
 518                 param = generate_new_param(root,
 519                                                                    exprType((Node *) tent->expr),
 520                                                                    exprTypmod((Node *) tent->expr));
 521                 result = lappend(result, param);
 522                 ids = lappend_int(ids, param->paramid);
 523         }
 524
 525         *paramIds = ids;
 526         return result;
 527 }
 528
 529 /*
 530  * generate_subquery_vars: build a list of Vars representing the output
 531  * columns of a sublink's sub-select, given the sub-select's targetlist.
 532  * The Vars have the specified varno (RTE index).
 533  */
 534 static List *
 535 generate_subquery_vars(PlannerInfo *root, List *tlist, Index varno)
 536 {
 537         List       *result;
 538         ListCell   *lc;
 539
 540         result = NIL;
 541         foreach(lc, tlist)
 542         {
 543                 TargetEntry *tent = (TargetEntry *) lfirst(lc);
 544                 Var                *var;
 545
 546                 if (tent->resjunk)
 547                         continue;
 548
 549                 var = makeVar(varno,
 550                                           tent->resno,
 551                                           exprType((Node *) tent->expr),
 552                                           exprTypmod((Node *) tent->expr),
 553                                           0);
 554                 result = lappend(result, var);
 555         }
 556
 557         return result;
 558 }
 559
 560 /*
 561  * convert_testexpr: convert the testexpr given by the parser into
 562  * actually executable form.  This entails replacing PARAM_SUBLINK Params
 563  * with Params or Vars representing the results of the sub-select.  The
 564  * nodes to be substituted are passed in as the List result from
 565  * generate_subquery_params or generate_subquery_vars.
 566  *
 567  * The given testexpr has already been recursively processed by
 568  * process_sublinks_mutator.  Hence it can no longer contain any
 569  * PARAM_SUBLINK Params for lower SubLink nodes; we can safely assume that
 570  * any we find are for our own level of SubLink.
 571  */
 572 static Node *
 573 convert_testexpr(PlannerInfo *root,
 574                                  Node *testexpr,
 575                                  List *subst_nodes)
 576 {
 577         convert_testexpr_context context;
 578
 579         context.root = root;
 580         context.subst_nodes = subst_nodes;
 581         return convert_testexpr_mutator(testexpr, &context);
 582 }
 583
 584 static Node *
 585 convert_testexpr_mutator(Node *node,
 586                                                  convert_testexpr_context *context)
 587 {
 588         if (node == NULL)
 589                 return NULL;
 590         if (IsA(node, Param))
 591         {
 592                 Param      *param = (Param *) node;
 593
 594                 if (param->paramkind == PARAM_SUBLINK)
 595                 {
 596                         if (param->paramid <= 0 ||
 597                                 param->paramid > list_length(context->subst_nodes))
 598                                 elog(ERROR, "unexpected PARAM_SUBLINK ID: %d", param->paramid);
 599
 600                         /*
 601                          * We copy the list item to avoid having doubly-linked
 602                          * substructure in the modified parse tree.  This is probably
 603                          * unnecessary when it's a Param, but be safe.
 604                          */
 605                         return (Node *) copyObject(list_nth(context->subst_nodes,
 606                                                                                                 param->paramid - 1));
 607                 }
 608         }
 609         return expression_tree_mutator(node,
 610                                                                    convert_testexpr_mutator,
 611                                                                    (void *) context);
 612 }
 613
 614 /*
 615  * subplan_is_hashable: decide whether we can implement a subplan by hashing
 616  *
 617  * Caution: the SubPlan node is not completely filled in yet.  We can rely
 618  * on its plan and parParam fields, however.
 619  */
 620 static bool
 621 subplan_is_hashable(SubLink *slink, SubPlan *node, Plan *plan)
 622 {
 623         double          subquery_size;
 624         ListCell   *l;
 625
 626         /*
 627          * The sublink type must be "= ANY" --- that is, an IN operator.  We
 628          * expect that the test expression will be either a single OpExpr, or an
 629          * AND-clause containing OpExprs.  (If it's anything else then the parser
 630          * must have determined that the operators have non-equality-like
 631          * semantics.  In the OpExpr case we can't be sure what the operator's
 632          * semantics are like, but the test below for hashability will reject
 633          * anything that's not equality.)
 634          */
 635         if (slink->subLinkType != ANY_SUBLINK)
 636                 return false;
 637         if (slink->testexpr == NULL ||
 638                 (!IsA(slink->testexpr, OpExpr) &&
 639                  !and_clause(slink->testexpr)))
 640                 return false;
 641
 642         /*
 643          * The subplan must not have any direct correlation vars --- else we'd
 644          * have to recompute its output each time, so that the hashtable wouldn't
 645          * gain anything.
 646          */
 647         if (node->parParam != NIL)
 648                 return false;
 649
 650         /*
 651          * The estimated size of the subquery result must fit in work_mem. (Note:
 652          * we use sizeof(HeapTupleHeaderData) here even though the tuples will
 653          * actually be stored as MinimalTuples; this provides some fudge factor
 654          * for hashtable overhead.)
 655          */
 656         subquery_size = plan->plan_rows *
 657                 (MAXALIGN(plan->plan_width) + MAXALIGN(sizeof(HeapTupleHeaderData)));
 658         if (subquery_size > work_mem * 1024L)
 659                 return false;
 660
 661         /*
 662          * The combining operators must be hashable and strict. The need for
 663          * hashability is obvious, since we want to use hashing. Without
 664          * strictness, behavior in the presence of nulls is too unpredictable.  We
 665          * actually must assume even more than plain strictness: they can't yield
 666          * NULL for non-null inputs, either (see nodeSubplan.c).  However, hash
 667          * indexes and hash joins assume that too.
 668          */
 669         if (IsA(slink->testexpr, OpExpr))
 670         {
 671                 if (!hash_ok_operator((OpExpr *) slink->testexpr))
 672                         return false;
 673         }
 674         else
 675         {
 676                 foreach(l, ((BoolExpr *) slink->testexpr)->args)
 677                 {
 678                         Node       *andarg = (Node *) lfirst(l);
 679
 680                         if (!IsA(andarg, OpExpr))
 681                                 return false;   /* probably can't happen */
 682                         if (!hash_ok_operator((OpExpr *) andarg))
 683                                 return false;
 684                 }
 685         }
 686
 687         return true;
 688 }
 689
 690 static bool
 691 hash_ok_operator(OpExpr *expr)
 692 {
 693         Oid                     opid = expr->opno;
 694         HeapTuple       tup;
 695         Form_pg_operator optup;
 696
 697         tup = SearchSysCache(OPEROID,
 698                                                  ObjectIdGetDatum(opid),
 699                                                  0, 0, 0);
 700         if (!HeapTupleIsValid(tup))
 701                 elog(ERROR, "cache lookup failed for operator %u", opid);
 702         optup = (Form_pg_operator) GETSTRUCT(tup);
 703         if (!optup->oprcanhash || !func_strict(optup->oprcode))
 704         {
 705                 ReleaseSysCache(tup);
 706                 return false;
 707         }
 708         ReleaseSysCache(tup);
 709         return true;
 710 }
 711
 712 /*
 713  * convert_IN_to_join: can we convert an IN SubLink to join style?
 714  *
 715  * The caller has found a SubLink at the top level of WHERE, but has not
 716  * checked the properties of the SubLink at all.  Decide whether it is
 717  * appropriate to process this SubLink in join style.  If not, return NULL.
 718  * If so, build the qual clause(s) to replace the SubLink, and return them.
 719  *
 720  * Side effects of a successful conversion include adding the SubLink's
 721  * subselect to the query's rangetable and adding an InClauseInfo node to
 722  * its in_info_list.
 723  */
 724 Node *
 725 convert_IN_to_join(PlannerInfo *root, SubLink *sublink)
 726 {
 727         Query      *parse = root->parse;
 728         Query      *subselect = (Query *) sublink->subselect;
 729         List       *in_operators;
 730         List       *left_exprs;
 731         List       *right_exprs;
 732         Relids          left_varnos;
 733         int                     rtindex;
 734         RangeTblEntry *rte;
 735         RangeTblRef *rtr;
 736         List       *subquery_vars;
 737         InClauseInfo *ininfo;
 738         Node       *result;
 739
 740         /*
 741          * The sublink type must be "= ANY" --- that is, an IN operator.  We
 742          * expect that the test expression will be either a single OpExpr, or an
 743          * AND-clause containing OpExprs.  (If it's anything else then the parser
 744          * must have determined that the operators have non-equality-like
 745          * semantics.  In the OpExpr case we can't be sure what the operator's
 746          * semantics are like, and must check for ourselves.)
 747          */
 748         if (sublink->subLinkType != ANY_SUBLINK)
 749                 return NULL;
 750         if (sublink->testexpr && IsA(sublink->testexpr, OpExpr))
 751         {
 752                 OpExpr     *op = (OpExpr *) sublink->testexpr;
 753                 Oid                     opno = op->opno;
 754                 List       *opfamilies;
 755                 List       *opstrats;
 756
 757                 if (list_length(op->args) != 2)
 758                         return NULL;                            /* not binary operator? */
 759                 get_op_btree_interpretation(opno, &opfamilies, &opstrats);
 760                 if (!list_member_int(opstrats, ROWCOMPARE_EQ))
 761                         return NULL;
 762                 in_operators = list_make1_oid(opno);
 763                 left_exprs = list_make1(linitial(op->args));
 764                 right_exprs = list_make1(lsecond(op->args));
 765         }
 766         else if (and_clause(sublink->testexpr))
 767         {
 768                 ListCell   *lc;
 769
 770                 /* OK, but we need to extract the per-column info */
 771                 in_operators = left_exprs = right_exprs = NIL;
 772                 foreach(lc, ((BoolExpr *) sublink->testexpr)->args)
 773                 {
 774                         OpExpr     *op = (OpExpr *) lfirst(lc);
 775
 776                         if (!IsA(op, OpExpr))           /* probably shouldn't happen */
 777                                 return NULL;
 778                         if (list_length(op->args) != 2)
 779                                 return NULL;                    /* not binary operator? */
 780                         in_operators = lappend_oid(in_operators, op->opno);
 781                         left_exprs = lappend(left_exprs, linitial(op->args));
 782                         right_exprs = lappend(right_exprs, lsecond(op->args));
 783                 }
 784         }
 785         else
 786                 return NULL;
 787
 788         /*
 789          * The sub-select must not refer to any Vars of the parent query. (Vars of
 790          * higher levels should be okay, though.)
 791          */
 792         if (contain_vars_of_level((Node *) subselect, 1))
 793                 return NULL;
 794
 795         /*
 796          * The left-hand expressions must contain some Vars of the current query,
 797          * else it's not gonna be a join.
 798          */
 799         left_varnos = pull_varnos((Node *) left_exprs);
 800         if (bms_is_empty(left_varnos))
 801                 return NULL;
 802
 803         /* ... and the right-hand expressions better not contain Vars at all */
 804         Assert(!contain_var_clause((Node *) right_exprs));
 805
 806         /*
 807          * The combining operators and left-hand expressions mustn't be volatile.
 808          */
 809         if (contain_volatile_functions(sublink->testexpr))
 810                 return NULL;
 811
 812         /*
 813          * Okay, pull up the sub-select into top range table and jointree.
 814          *
 815          * We rely here on the assumption that the outer query has no references
 816          * to the inner (necessarily true, other than the Vars that we build
 817          * below). Therefore this is a lot easier than what pull_up_subqueries has
 818          * to go through.
 819          */
 820         rte = addRangeTableEntryForSubquery(NULL,
 821                                                                                 subselect,
 822                                                                                 makeAlias("IN_subquery", NIL),
 823                                                                                 false);
 824         parse->rtable = lappend(parse->rtable, rte);
 825         rtindex = list_length(parse->rtable);
 826         rtr = makeNode(RangeTblRef);
 827         rtr->rtindex = rtindex;
 828         parse->jointree->fromlist = lappend(parse->jointree->fromlist, rtr);
 829
 830         /*
 831          * Build a list of Vars representing the subselect outputs.
 832          */
 833         subquery_vars = generate_subquery_vars(root,
 834                                                                                    subselect->targetList,
 835                                                                                    rtindex);
 836
 837         /*
 838          * Build the result qual expression, replacing Params with these Vars.
 839          */
 840         result = convert_testexpr(root,
 841                                                           sublink->testexpr,
 842                                                           subquery_vars);
 843
 844         /*
 845          * Now build the InClauseInfo node.
 846          */
 847         ininfo = makeNode(InClauseInfo);
 848         ininfo->lefthand = left_varnos;
 849         ininfo->righthand = bms_make_singleton(rtindex);
 850         ininfo->in_operators = in_operators;
 851
 852         /*
 853          * ininfo->sub_targetlist must be filled with a list of expressions that
 854          * would need to be unique-ified if we try to implement the IN using a
 855          * regular join to unique-ified subquery output.  This is most easily done
 856          * by applying convert_testexpr to just the RHS inputs of the testexpr
 857          * operators.  That handles cases like type coercions of the subquery
 858          * outputs, clauses dropped due to const-simplification, etc.
 859          */
 860         ininfo->sub_targetlist = (List *) convert_testexpr(root,
 861                                                                                                            (Node *) right_exprs,
 862                                                                                                            subquery_vars);
 863
 864         /* Add the completed node to the query's list */
 865         root->in_info_list = lappend(root->in_info_list, ininfo);
 866
 867         return result;
 868 }
 869
 870 /*
 871  * Replace correlation vars (uplevel vars) with Params.
 872  *
 873  * Uplevel aggregates are replaced, too.
 874  *
 875  * Note: it is critical that this runs immediately after SS_process_sublinks.
 876  * Since we do not recurse into the arguments of uplevel aggregates, they will
 877  * get copied to the appropriate subplan args list in the parent query with
 878  * uplevel vars not replaced by Params, but only adjusted in level (see
 879  * replace_outer_agg).  That's exactly what we want for the vars of the parent
 880  * level --- but if an aggregate's argument contains any further-up variables,
 881  * they have to be replaced with Params in their turn.  That will happen when
 882  * the parent level runs SS_replace_correlation_vars.  Therefore it must do
 883  * so after expanding its sublinks to subplans.  And we don't want any steps
 884  * in between, else those steps would never get applied to the aggregate
 885  * argument expressions, either in the parent or the child level.
 886  */
 887 Node *
 888 SS_replace_correlation_vars(PlannerInfo *root, Node *expr)
 889 {
 890         /* No setup needed for tree walk, so away we go */
 891         return replace_correlation_vars_mutator(expr, root);
 892 }
 893
 894 static Node *
 895 replace_correlation_vars_mutator(Node *node, PlannerInfo *root)
 896 {
 897         if (node == NULL)
 898                 return NULL;
 899         if (IsA(node, Var))
 900         {
 901                 if (((Var *) node)->varlevelsup > 0)
 902                         return (Node *) replace_outer_var(root, (Var *) node);
 903         }
 904         if (IsA(node, Aggref))
 905         {
 906                 if (((Aggref *) node)->agglevelsup > 0)
 907                         return (Node *) replace_outer_agg(root, (Aggref *) node);
 908         }
 909         return expression_tree_mutator(node,
 910                                                                    replace_correlation_vars_mutator,
 911                                                                    (void *) root);
 912 }
 913
 914 /*
 915  * Expand SubLinks to SubPlans in the given expression.
 916  *
 917  * The isQual argument tells whether or not this expression is a WHERE/HAVING
 918  * qualifier expression.  If it is, any sublinks appearing at top level need
 919  * not distinguish FALSE from UNKNOWN return values.
 920  */
 921 Node *
 922 SS_process_sublinks(PlannerInfo *root, Node *expr, bool isQual)
 923 {
 924         process_sublinks_context context;
 925
 926         context.root = root;
 927         context.isTopQual = isQual;
 928         return process_sublinks_mutator(expr, &context);
 929 }
 930
 931 static Node *
 932 process_sublinks_mutator(Node *node, process_sublinks_context *context)
 933 {
 934         process_sublinks_context locContext;
 935
 936         locContext.root = context->root;
 937
 938         if (node == NULL)
 939                 return NULL;
 940         if (IsA(node, SubLink))
 941         {
 942                 SubLink    *sublink = (SubLink *) node;
 943                 Node       *testexpr;
 944
 945                 /*
 946                  * First, recursively process the lefthand-side expressions, if any.
 947                  * They're not top-level anymore.
 948                  */
 949                 locContext.isTopQual = false;
 950                 testexpr = process_sublinks_mutator(sublink->testexpr, &locContext);
 951
 952                 /*
 953                  * Now build the SubPlan node and make the expr to return.
 954                  */
 955                 return make_subplan(context->root,
 956                                                         sublink,
 957                                                         testexpr,
 958                                                         context->isTopQual);
 959         }
 960
 961         /*
 962          * We should never see a SubPlan expression in the input (since this is
 963          * the very routine that creates 'em to begin with).  We shouldn't find
 964          * ourselves invoked directly on a Query, either.
 965          */
 966         Assert(!is_subplan(node));
 967         Assert(!IsA(node, Query));
 968
 969         /*
 970          * Because make_subplan() could return an AND or OR clause, we have to
 971          * take steps to preserve AND/OR flatness of a qual.  We assume the input
 972          * has been AND/OR flattened and so we need no recursion here.
 973          *
 974          * If we recurse down through anything other than an AND node, we are
 975          * definitely not at top qual level anymore.  (Due to the coding here, we
 976          * will not get called on the List subnodes of an AND, so no check is
 977          * needed for List.)
 978          */
 979         if (and_clause(node))
 980         {
 981                 List       *newargs = NIL;
 982                 ListCell   *l;
 983
 984                 /* Still at qual top-level */
 985                 locContext.isTopQual = context->isTopQual;
 986
 987                 foreach(l, ((BoolExpr *) node)->args)
 988                 {
 989                         Node       *newarg;
 990
 991                         newarg = process_sublinks_mutator(lfirst(l), &locContext);
 992                         if (and_clause(newarg))
 993                                 newargs = list_concat(newargs, ((BoolExpr *) newarg)->args);
 994                         else
 995                                 newargs = lappend(newargs, newarg);
 996                 }
 997                 return (Node *) make_andclause(newargs);
 998         }
 999
1000         /* otherwise not at qual top-level */
1001         locContext.isTopQual = false;
1002
1003         if (or_clause(node))
1004         {
1005                 List       *newargs = NIL;
1006                 ListCell   *l;
1007
1008                 foreach(l, ((BoolExpr *) node)->args)
1009                 {
1010                         Node       *newarg;
1011
1012                         newarg = process_sublinks_mutator(lfirst(l), &locContext);
1013                         if (or_clause(newarg))
1014                                 newargs = list_concat(newargs, ((BoolExpr *) newarg)->args);
1015                         else
1016                                 newargs = lappend(newargs, newarg);
1017                 }
1018                 return (Node *) make_orclause(newargs);
1019         }
1020
1021         return expression_tree_mutator(node,
1022                                                                    process_sublinks_mutator,
1023                                                                    (void *) &locContext);
1024 }
1025
1026 /*
1027  * SS_finalize_plan - do final sublink processing for a completed Plan.
1028  *
1029  * This recursively computes the extParam and allParam sets for every Plan
1030  * node in the given plan tree.  It also attaches any generated InitPlans
1031  * to the top plan node.
1032  */
1033 void
1034 SS_finalize_plan(PlannerInfo *root, Plan *plan)
1035 {
1036         Bitmapset  *valid_params,
1037                            *initExtParam,
1038                            *initSetParam;
1039         Cost            initplan_cost;
1040         int                     paramid;
1041         ListCell   *l;
1042
1043         /*
1044          * First, scan the param list to discover the sets of params that are
1045          * available from outer query levels and my own query level. We do this
1046          * once to save time in the per-plan recursion steps.  (This calculation
1047          * is overly generous: it can include a lot of params that actually
1048          * shouldn't be referenced here.  However, valid_params is just used as
1049          * a debugging crosscheck, so it's not worth trying to be exact.)
1050          */
1051         valid_params = NULL;
1052         paramid = 0;
1053         foreach(l, root->glob->paramlist)
1054         {
1055                 PlannerParamItem *pitem = (PlannerParamItem *) lfirst(l);
1056
1057                 if (pitem->abslevel < root->query_level)
1058                 {
1059                         /* valid outer-level parameter */
1060                         valid_params = bms_add_member(valid_params, paramid);
1061                 }
1062                 else if (pitem->abslevel == root->query_level &&
1063                                  IsA(pitem->item, Param))
1064                 {
1065                         /* valid local parameter (i.e., a setParam of my child) */
1066                         valid_params = bms_add_member(valid_params, paramid);
1067                 }
1068
1069                 paramid++;
1070         }
1071
1072         /*
1073          * Now recurse through plan tree.
1074          */
1075         (void) finalize_plan(root, plan, valid_params);
1076
1077         bms_free(valid_params);
1078
1079         /*
1080          * Finally, attach any initPlans to the topmost plan node, and add their
1081          * extParams to the topmost node's, too.  However, any setParams of the
1082          * initPlans should not be present in the topmost node's extParams, only
1083          * in its allParams.  (As of PG 8.1, it's possible that some initPlans
1084          * have extParams that are setParams of other initPlans, so we have to
1085          * take care of this situation explicitly.)
1086          *
1087          * We also add the eval cost of each initPlan to the startup cost of the
1088          * top node.  This is a conservative overestimate, since in fact each
1089          * initPlan might be executed later than plan startup, or even not at all.
1090          */
1091         plan->initPlan = root->init_plans;
1092         root->init_plans = NIL;         /* make sure they're not attached twice */
1093
1094         initExtParam = initSetParam = NULL;
1095         initplan_cost = 0;
1096         foreach(l, plan->initPlan)
1097         {
1098                 SubPlan    *initsubplan = (SubPlan *) lfirst(l);
1099                 Plan       *initplan = planner_subplan_get_plan(root, initsubplan);
1100                 ListCell   *l2;
1101
1102                 initExtParam = bms_add_members(initExtParam, initplan->extParam);
1103                 foreach(l2, initsubplan->setParam)
1104                 {
1105                         initSetParam = bms_add_member(initSetParam, lfirst_int(l2));
1106                 }
1107                 initplan_cost += get_initplan_cost(root, initsubplan);
1108         }
1109         /* allParam must include all these params */
1110         plan->allParam = bms_add_members(plan->allParam, initExtParam);
1111         plan->allParam = bms_add_members(plan->allParam, initSetParam);
1112         /* extParam must include any child extParam */
1113         plan->extParam = bms_add_members(plan->extParam, initExtParam);
1114         /* but extParam shouldn't include any setParams */
1115         plan->extParam = bms_del_members(plan->extParam, initSetParam);
1116         /* ensure extParam is exactly NULL if it's empty */
1117         if (bms_is_empty(plan->extParam))
1118                 plan->extParam = NULL;
1119
1120         plan->startup_cost += initplan_cost;
1121         plan->total_cost += initplan_cost;
1122 }
1123
1124 /*
1125  * Recursive processing of all nodes in the plan tree
1126  *
1127  * The return value is the computed allParam set for the given Plan node.
1128  * This is just an internal notational convenience.
1129  */
1130 static Bitmapset *
1131 finalize_plan(PlannerInfo *root, Plan *plan, Bitmapset *valid_params)
1132 {
1133         finalize_primnode_context context;
1134
1135         if (plan == NULL)
1136                 return NULL;
1137
1138         context.root = root;
1139         context.paramids = NULL;        /* initialize set to empty */
1140
1141         /*
1142          * When we call finalize_primnode, context.paramids sets are automatically
1143          * merged together.  But when recursing to self, we have to do it the hard
1144          * way.  We want the paramids set to include params in subplans as well as
1145          * at this level.
1146          */
1147
1148         /* Find params in targetlist and qual */
1149         finalize_primnode((Node *) plan->targetlist, &context);
1150         finalize_primnode((Node *) plan->qual, &context);
1151
1152         /* Check additional node-type-specific fields */
1153         switch (nodeTag(plan))
1154         {
1155                 case T_Result:
1156                         finalize_primnode(((Result *) plan)->resconstantqual,
1157                                                           &context);
1158                         break;
1159
1160                 case T_IndexScan:
1161                         finalize_primnode((Node *) ((IndexScan *) plan)->indexqual,
1162                                                           &context);
1163
1164                         /*
1165                          * we need not look at indexqualorig, since it will have the same
1166                          * param references as indexqual.
1167                          */
1168                         break;
1169
1170                 case T_BitmapIndexScan:
1171                         finalize_primnode((Node *) ((BitmapIndexScan *) plan)->indexqual,
1172                                                           &context);
1173
1174                         /*
1175                          * we need not look at indexqualorig, since it will have the same
1176                          * param references as indexqual.
1177                          */
1178                         break;
1179
1180                 case T_BitmapHeapScan:
1181                         finalize_primnode((Node *) ((BitmapHeapScan *) plan)->bitmapqualorig,
1182                                                           &context);
1183                         break;
1184
1185                 case T_TidScan:
1186                         finalize_primnode((Node *) ((TidScan *) plan)->tidquals,
1187                                                           &context);
1188                         break;
1189
1190                 case T_SubqueryScan:
1191
1192                         /*
1193                          * In a SubqueryScan, SS_finalize_plan has already been run on the
1194                          * subplan by the inner invocation of subquery_planner, so there's
1195                          * no need to do it again.      Instead, just pull out the subplan's
1196                          * extParams list, which represents the params it needs from my
1197                          * level and higher levels.
1198                          */
1199                         context.paramids = bms_add_members(context.paramids,
1200                                                                  ((SubqueryScan *) plan)->subplan->extParam);
1201                         break;
1202
1203                 case T_FunctionScan:
1204                         finalize_primnode(((FunctionScan *) plan)->funcexpr,
1205                                                           &context);
1206                         break;
1207
1208                 case T_ValuesScan:
1209                         finalize_primnode((Node *) ((ValuesScan *) plan)->values_lists,
1210                                                           &context);
1211                         break;
1212
1213                 case T_Append:
1214                         {
1215                                 ListCell   *l;
1216
1217                                 foreach(l, ((Append *) plan)->appendplans)
1218                                 {
1219                                         context.paramids =
1220                                                 bms_add_members(context.paramids,
1221                                                                                 finalize_plan(root,
1222                                                                                                           (Plan *) lfirst(l),
1223                                                                                                           valid_params));
1224                                 }
1225                         }
1226                         break;
1227
1228                 case T_BitmapAnd:
1229                         {
1230                                 ListCell   *l;
1231
1232                                 foreach(l, ((BitmapAnd *) plan)->bitmapplans)
1233                                 {
1234                                         context.paramids =
1235                                                 bms_add_members(context.paramids,
1236                                                                                 finalize_plan(root,
1237                                                                                                           (Plan *) lfirst(l),
1238                                                                                                           valid_params));
1239                                 }
1240                         }
1241                         break;
1242
1243                 case T_BitmapOr:
1244                         {
1245                                 ListCell   *l;
1246
1247                                 foreach(l, ((BitmapOr *) plan)->bitmapplans)
1248                                 {
1249                                         context.paramids =
1250                                                 bms_add_members(context.paramids,
1251                                                                                 finalize_plan(root,
1252                                                                                                           (Plan *) lfirst(l),
1253                                                                                                           valid_params));
1254                                 }
1255                         }
1256                         break;
1257
1258                 case T_NestLoop:
1259                         finalize_primnode((Node *) ((Join *) plan)->joinqual,
1260                                                           &context);
1261                         break;
1262
1263                 case T_MergeJoin:
1264                         finalize_primnode((Node *) ((Join *) plan)->joinqual,
1265                                                           &context);
1266                         finalize_primnode((Node *) ((MergeJoin *) plan)->mergeclauses,
1267                                                           &context);
1268                         break;
1269
1270                 case T_HashJoin:
1271                         finalize_primnode((Node *) ((Join *) plan)->joinqual,
1272                                                           &context);
1273                         finalize_primnode((Node *) ((HashJoin *) plan)->hashclauses,
1274                                                           &context);
1275                         break;
1276
1277                 case T_Limit:
1278                         finalize_primnode(((Limit *) plan)->limitOffset,
1279                                                           &context);
1280                         finalize_primnode(((Limit *) plan)->limitCount,
1281                                                           &context);
1282                         break;
1283
1284                 case T_Hash:
1285                 case T_Agg:
1286                 case T_SeqScan:
1287                 case T_Material:
1288                 case T_Sort:
1289                 case T_Unique:
1290                 case T_SetOp:
1291                 case T_Group:
1292                         break;
1293
1294                 default:
1295                         elog(ERROR, "unrecognized node type: %d",
1296                                  (int) nodeTag(plan));
1297         }
1298
1299         /* Process left and right child plans, if any */
1300         context.paramids = bms_add_members(context.paramids,
1301                                                                            finalize_plan(root,
1302                                                                                                          plan->lefttree,
1303                                                                                                          valid_params));
1304
1305         context.paramids = bms_add_members(context.paramids,
1306                                                                            finalize_plan(root,
1307                                                                                                          plan->righttree,
1308                                                                                                          valid_params));
1309
1310         /* Now we have all the paramids */
1311
1312         if (!bms_is_subset(context.paramids, valid_params))
1313                 elog(ERROR, "plan should not reference subplan's variable");
1314
1315         /*
1316          * Note: by definition, extParam and allParam should have the same value
1317          * in any plan node that doesn't have child initPlans.  We set them
1318          * equal here, and later SS_finalize_plan will update them properly
1319          * in node(s) that it attaches initPlans to.
1320          *
1321          * For speed at execution time, make sure extParam/allParam are actually
1322          * NULL if they are empty sets.
1323          */
1324         if (bms_is_empty(context.paramids))
1325         {
1326                 plan->extParam = NULL;
1327                 plan->allParam = NULL;
1328         }
1329         else
1330         {
1331                 plan->extParam = context.paramids;
1332                 plan->allParam = bms_copy(context.paramids);
1333         }
1334
1335         return plan->allParam;
1336 }
1337
1338 /*
1339  * finalize_primnode: add IDs of all PARAM_EXEC params appearing in the given
1340  * expression tree to the result set.
1341  */
1342 static bool
1343 finalize_primnode(Node *node, finalize_primnode_context *context)
1344 {
1345         if (node == NULL)
1346                 return false;
1347         if (IsA(node, Param))
1348         {
1349                 if (((Param *) node)->paramkind == PARAM_EXEC)
1350                 {
1351                         int                     paramid = ((Param *) node)->paramid;
1352
1353                         context->paramids = bms_add_member(context->paramids, paramid);
1354                 }
1355                 return false;                   /* no more to do here */
1356         }
1357         if (is_subplan(node))
1358         {
1359                 SubPlan    *subplan = (SubPlan *) node;
1360                 Plan       *plan = planner_subplan_get_plan(context->root, subplan);
1361                 ListCell   *lc;
1362                 Bitmapset  *subparamids;
1363
1364                 /* Recurse into the testexpr, but not into the Plan */
1365                 finalize_primnode(subplan->testexpr, context);
1366
1367                 /*
1368                  * Remove any param IDs of output parameters of the subplan that were
1369                  * referenced in the testexpr.  These are not interesting for
1370                  * parameter change signaling since we always re-evaluate the subplan.
1371                  * Note that this wouldn't work too well if there might be uses of the
1372                  * same param IDs elsewhere in the plan, but that can't happen because
1373                  * generate_new_param never tries to merge params.
1374                  */
1375                 foreach(lc, subplan->paramIds)
1376                 {
1377                         context->paramids = bms_del_member(context->paramids,
1378                                                                                            lfirst_int(lc));
1379                 }
1380
1381                 /* Also examine args list */
1382                 finalize_primnode((Node *) subplan->args, context);
1383
1384                 /*
1385                  * Add params needed by the subplan to paramids, but excluding those
1386                  * we will pass down to it.
1387                  */
1388                 subparamids = bms_copy(plan->extParam);
1389                 foreach(lc, subplan->parParam)
1390                 {
1391                         subparamids = bms_del_member(subparamids, lfirst_int(lc));
1392                 }
1393                 context->paramids = bms_join(context->paramids, subparamids);
1394
1395                 return false;                   /* no more to do here */
1396         }
1397         return expression_tree_walker(node, finalize_primnode,
1398                                                                   (void *) context);
1399 }
1400
1401 /*
1402  * SS_make_initplan_from_plan - given a plan tree, make it an InitPlan
1403  *
1404  * The plan is expected to return a scalar value of the indicated type.
1405  * We build an EXPR_SUBLINK SubPlan node and put it into the initplan
1406  * list for the current query level.  A Param that represents the initplan's
1407  * output is returned.
1408  *
1409  * We assume the plan hasn't been put through SS_finalize_plan.
1410  */
1411 Param *
1412 SS_make_initplan_from_plan(PlannerInfo *root, Plan *plan,
1413                                                    Oid resulttype, int32 resulttypmod)
1414 {
1415         List       *saved_init_plans;
1416         SubPlan    *node;
1417         Param      *prm;
1418
1419         /*
1420          * We must run SS_finalize_plan(), since that's normally done before a
1421          * subplan gets put into the initplan list.  However it will try to attach
1422          * any pre-existing initplans to this one, which we don't want (they are
1423          * siblings not children of this initplan).  So, a quick kluge to hide
1424          * them.  (This is something else that could perhaps be cleaner if we did
1425          * extParam/allParam processing in setrefs.c instead of here?  See notes
1426          * for materialize_finished_plan.)
1427          */
1428         saved_init_plans = root->init_plans;
1429         root->init_plans = NIL;
1430
1431         /*
1432          * Build extParam/allParam sets for plan nodes.
1433          */
1434         SS_finalize_plan(root, plan);
1435
1436         /* Restore outer initplan list */
1437         root->init_plans = saved_init_plans;
1438
1439         /*
1440          * Add the subplan and its rtable to the global lists.
1441          */
1442         root->glob->subplans = lappend(root->glob->subplans,
1443                                                                    plan);
1444         root->glob->subrtables = lappend(root->glob->subrtables,
1445                                                                          root->parse->rtable);
1446
1447         /*
1448          * Create a SubPlan node and add it to the outer list of InitPlans.
1449          */
1450         node = makeNode(SubPlan);
1451         node->subLinkType = EXPR_SUBLINK;
1452         node->firstColType = get_first_col_type(plan);
1453         node->plan_id = list_length(root->glob->subplans);
1454
1455         root->init_plans = lappend(root->init_plans, node);
1456
1457         /*
1458          * The node can't have any inputs (since it's an initplan), so the
1459          * parParam and args lists remain empty.
1460          */
1461
1462         /*
1463          * Make a Param that will be the subplan's output.
1464          */
1465         prm = generate_new_param(root, resulttype, resulttypmod);
1466         node->setParam = list_make1_int(prm->paramid);
1467
1468         return prm;
1469 }