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