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-2012, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  * IDENTIFICATION
  10  *        src/backend/optimizer/plan/subselect.c
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #include "postgres.h"
  15
  16 #include "access/htup_details.h"
  17 #include "catalog/pg_operator.h"
  18 #include "catalog/pg_type.h"
  19 #include "executor/executor.h"
  20 #include "miscadmin.h"
  21 #include "nodes/makefuncs.h"
  22 #include "nodes/nodeFuncs.h"
  23 #include "optimizer/clauses.h"
  24 #include "optimizer/cost.h"
  25 #include "optimizer/planmain.h"
  26 #include "optimizer/planner.h"
  27 #include "optimizer/prep.h"
  28 #include "optimizer/subselect.h"
  29 #include "optimizer/var.h"
  30 #include "parser/parse_relation.h"
  31 #include "rewrite/rewriteManip.h"
  32 #include "utils/builtins.h"
  33 #include "utils/lsyscache.h"
  34 #include "utils/syscache.h"
  35
  36
  37 typedef struct convert_testexpr_context
  38 {
  39         PlannerInfo *root;
  40         List       *subst_nodes;        /* Nodes to substitute for Params */
  41 } convert_testexpr_context;
  42
  43 typedef struct process_sublinks_context
  44 {
  45         PlannerInfo *root;
  46         bool            isTopQual;
  47 } process_sublinks_context;
  48
  49 typedef struct finalize_primnode_context
  50 {
  51         PlannerInfo *root;
  52         Bitmapset  *paramids;           /* Non-local PARAM_EXEC paramids found */
  53 } finalize_primnode_context;
  54
  55
  56 static Node *build_subplan(PlannerInfo *root, Plan *plan, PlannerInfo *subroot,
  57                           List *plan_params,
  58                           SubLinkType subLinkType, Node *testexpr,
  59                           bool adjust_testexpr, bool unknownEqFalse);
  60 static List *generate_subquery_params(PlannerInfo *root, List *tlist,
  61                                                  List **paramIds);
  62 static List *generate_subquery_vars(PlannerInfo *root, List *tlist,
  63                                            Index varno);
  64 static Node *convert_testexpr(PlannerInfo *root,
  65                                  Node *testexpr,
  66                                  List *subst_nodes);
  67 static Node *convert_testexpr_mutator(Node *node,
  68                                                  convert_testexpr_context *context);
  69 static bool subplan_is_hashable(Plan *plan);
  70 static bool testexpr_is_hashable(Node *testexpr);
  71 static bool hash_ok_operator(OpExpr *expr);
  72 static bool simplify_EXISTS_query(Query *query);
  73 static Query *convert_EXISTS_to_ANY(PlannerInfo *root, Query *subselect,
  74                                           Node **testexpr, List **paramIds);
  75 static Node *replace_correlation_vars_mutator(Node *node, PlannerInfo *root);
  76 static Node *process_sublinks_mutator(Node *node,
  77                                                  process_sublinks_context *context);
  78 static Bitmapset *finalize_plan(PlannerInfo *root,
  79                           Plan *plan,
  80                           Bitmapset *valid_params,
  81                           Bitmapset *scan_params);
  82 static bool finalize_primnode(Node *node, finalize_primnode_context *context);
  83
  84
  85 /*
  86  * Select a PARAM_EXEC number to identify the given Var as a parameter for
  87  * the current subquery, or for a nestloop's inner scan.
  88  * If the Var already has a param in the current context, return that one.
  89  */
  90 static int
  91 assign_param_for_var(PlannerInfo *root, Var *var)
  92 {
  93         ListCell   *ppl;
  94         PlannerParamItem *pitem;
  95         Index           levelsup;
  96
  97         /* Find the query level the Var belongs to */
  98         for (levelsup = var->varlevelsup; levelsup > 0; levelsup--)
  99                 root = root->parent_root;
 100
 101         /* If there's already a matching PlannerParamItem there, just use it */
 102         foreach(ppl, root->plan_params)
 103         {
 104                 pitem = (PlannerParamItem *) lfirst(ppl);
 105                 if (IsA(pitem->item, Var))
 106                 {
 107                         Var                *pvar = (Var *) pitem->item;
 108
 109                         /*
 110                          * This comparison must match _equalVar(), except for ignoring
 111                          * varlevelsup.  Note that _equalVar() ignores the location.
 112                          */
 113                         if (pvar->varno == var->varno &&
 114                                 pvar->varattno == var->varattno &&
 115                                 pvar->vartype == var->vartype &&
 116                                 pvar->vartypmod == var->vartypmod &&
 117                                 pvar->varcollid == var->varcollid &&
 118                                 pvar->varnoold == var->varnoold &&
 119                                 pvar->varoattno == var->varoattno)
 120                                 return pitem->paramId;
 121                 }
 122         }
 123
 124         /* Nope, so make a new one */
 125         var = (Var *) copyObject(var);
 126         var->varlevelsup = 0;
 127
 128         pitem = makeNode(PlannerParamItem);
 129         pitem->item = (Node *) var;
 130         pitem->paramId = root->glob->nParamExec++;
 131
 132         root->plan_params = lappend(root->plan_params, pitem);
 133
 134         return pitem->paramId;
 135 }
 136
 137 /*
 138  * Generate a Param node to replace the given Var,
 139  * which is expected to have varlevelsup > 0 (ie, it is not local).
 140  */
 141 static Param *
 142 replace_outer_var(PlannerInfo *root, Var *var)
 143 {
 144         Param      *retval;
 145         int                     i;
 146
 147         Assert(var->varlevelsup > 0 && var->varlevelsup < root->query_level);
 148
 149         /* Find the Var in the appropriate plan_params, or add it if not present */
 150         i = assign_param_for_var(root, var);
 151
 152         retval = makeNode(Param);
 153         retval->paramkind = PARAM_EXEC;
 154         retval->paramid = i;
 155         retval->paramtype = var->vartype;
 156         retval->paramtypmod = var->vartypmod;
 157         retval->paramcollid = var->varcollid;
 158         retval->location = var->location;
 159
 160         return retval;
 161 }
 162
 163 /*
 164  * Generate a Param node to replace the given Var, which will be supplied
 165  * from an upper NestLoop join node.
 166  *
 167  * This is effectively the same as replace_outer_var, except that we expect
 168  * the Var to be local to the current query level.
 169  */
 170 Param *
 171 assign_nestloop_param_var(PlannerInfo *root, Var *var)
 172 {
 173         Param      *retval;
 174         int                     i;
 175
 176         Assert(var->varlevelsup == 0);
 177
 178         i = assign_param_for_var(root, var);
 179
 180         retval = makeNode(Param);
 181         retval->paramkind = PARAM_EXEC;
 182         retval->paramid = i;
 183         retval->paramtype = var->vartype;
 184         retval->paramtypmod = var->vartypmod;
 185         retval->paramcollid = var->varcollid;
 186         retval->location = var->location;
 187
 188         return retval;
 189 }
 190
 191 /*
 192  * Select a PARAM_EXEC number to identify the given PlaceHolderVar as a
 193  * parameter for the current subquery, or for a nestloop's inner scan.
 194  * If the PHV already has a param in the current context, return that one.
 195  *
 196  * This is just like assign_param_for_var, except for PlaceHolderVars.
 197  */
 198 static int
 199 assign_param_for_placeholdervar(PlannerInfo *root, PlaceHolderVar *phv)
 200 {
 201         ListCell   *ppl;
 202         PlannerParamItem *pitem;
 203         Index           levelsup;
 204
 205         /* Find the query level the PHV belongs to */
 206         for (levelsup = phv->phlevelsup; levelsup > 0; levelsup--)
 207                 root = root->parent_root;
 208
 209         /* If there's already a matching PlannerParamItem there, just use it */
 210         foreach(ppl, root->plan_params)
 211         {
 212                 pitem = (PlannerParamItem *) lfirst(ppl);
 213                 if (IsA(pitem->item, PlaceHolderVar))
 214                 {
 215                         PlaceHolderVar *pphv = (PlaceHolderVar *) pitem->item;
 216
 217                         /* We assume comparing the PHIDs is sufficient */
 218                         if (pphv->phid == phv->phid)
 219                                 return pitem->paramId;
 220                 }
 221         }
 222
 223         /* Nope, so make a new one */
 224         phv = (PlaceHolderVar *) copyObject(phv);
 225         if (phv->phlevelsup != 0)
 226         {
 227                 IncrementVarSublevelsUp((Node *) phv, -((int) phv->phlevelsup), 0);
 228                 Assert(phv->phlevelsup == 0);
 229         }
 230
 231         pitem = makeNode(PlannerParamItem);
 232         pitem->item = (Node *) phv;
 233         pitem->paramId = root->glob->nParamExec++;
 234
 235         root->plan_params = lappend(root->plan_params, pitem);
 236
 237         return pitem->paramId;
 238 }
 239
 240 /*
 241  * Generate a Param node to replace the given PlaceHolderVar,
 242  * which is expected to have phlevelsup > 0 (ie, it is not local).
 243  *
 244  * This is just like replace_outer_var, except for PlaceHolderVars.
 245  */
 246 static Param *
 247 replace_outer_placeholdervar(PlannerInfo *root, PlaceHolderVar *phv)
 248 {
 249         Param      *retval;
 250         int                     i;
 251
 252         Assert(phv->phlevelsup > 0 && phv->phlevelsup < root->query_level);
 253
 254         /* Find the PHV in the appropriate plan_params, or add it if not present */
 255         i = assign_param_for_placeholdervar(root, phv);
 256
 257         retval = makeNode(Param);
 258         retval->paramkind = PARAM_EXEC;
 259         retval->paramid = i;
 260         retval->paramtype = exprType((Node *) phv->phexpr);
 261         retval->paramtypmod = exprTypmod((Node *) phv->phexpr);
 262         retval->paramcollid = exprCollation((Node *) phv->phexpr);
 263         retval->location = -1;
 264
 265         return retval;
 266 }
 267
 268 /*
 269  * Generate a Param node to replace the given PlaceHolderVar, which will be
 270  * supplied from an upper NestLoop join node.
 271  *
 272  * This is just like assign_nestloop_param_var, except for PlaceHolderVars.
 273  */
 274 Param *
 275 assign_nestloop_param_placeholdervar(PlannerInfo *root, PlaceHolderVar *phv)
 276 {
 277         Param      *retval;
 278         int                     i;
 279
 280         Assert(phv->phlevelsup == 0);
 281
 282         i = assign_param_for_placeholdervar(root, phv);
 283
 284         retval = makeNode(Param);
 285         retval->paramkind = PARAM_EXEC;
 286         retval->paramid = i;
 287         retval->paramtype = exprType((Node *) phv->phexpr);
 288         retval->paramtypmod = exprTypmod((Node *) phv->phexpr);
 289         retval->paramcollid = exprCollation((Node *) phv->phexpr);
 290         retval->location = -1;
 291
 292         return retval;
 293 }
 294
 295 /*
 296  * Generate a Param node to replace the given Aggref
 297  * which is expected to have agglevelsup > 0 (ie, it is not local).
 298  */
 299 static Param *
 300 replace_outer_agg(PlannerInfo *root, Aggref *agg)
 301 {
 302         Param      *retval;
 303         PlannerParamItem *pitem;
 304         Index           levelsup;
 305
 306         Assert(agg->agglevelsup > 0 && agg->agglevelsup < root->query_level);
 307
 308         /* Find the query level the Aggref belongs to */
 309         for (levelsup = agg->agglevelsup; levelsup > 0; levelsup--)
 310                 root = root->parent_root;
 311
 312         /*
 313          * It does not seem worthwhile to try to match duplicate outer aggs. Just
 314          * make a new slot every time.
 315          */
 316         agg = (Aggref *) copyObject(agg);
 317         IncrementVarSublevelsUp((Node *) agg, -((int) agg->agglevelsup), 0);
 318         Assert(agg->agglevelsup == 0);
 319
 320         pitem = makeNode(PlannerParamItem);
 321         pitem->item = (Node *) agg;
 322         pitem->paramId = root->glob->nParamExec++;
 323
 324         root->plan_params = lappend(root->plan_params, pitem);
 325
 326         retval = makeNode(Param);
 327         retval->paramkind = PARAM_EXEC;
 328         retval->paramid = pitem->paramId;
 329         retval->paramtype = agg->aggtype;
 330         retval->paramtypmod = -1;
 331         retval->paramcollid = agg->aggcollid;
 332         retval->location = agg->location;
 333
 334         return retval;
 335 }
 336
 337 /*
 338  * Generate a new Param node that will not conflict with any other.
 339  *
 340  * This is used to create Params representing subplan outputs.
 341  * We don't need to build a PlannerParamItem for such a Param, but we do
 342  * need to record the PARAM_EXEC slot number as being allocated.
 343  */
 344 static Param *
 345 generate_new_param(PlannerInfo *root, Oid paramtype, int32 paramtypmod,
 346                                    Oid paramcollation)
 347 {
 348         Param      *retval;
 349
 350         retval = makeNode(Param);
 351         retval->paramkind = PARAM_EXEC;
 352         retval->paramid = root->glob->nParamExec++;
 353         retval->paramtype = paramtype;
 354         retval->paramtypmod = paramtypmod;
 355         retval->paramcollid = paramcollation;
 356         retval->location = -1;
 357
 358         return retval;
 359 }
 360
 361 /*
 362  * Assign a (nonnegative) PARAM_EXEC ID for a special parameter (one that
 363  * is not actually used to carry a value at runtime).  Such parameters are
 364  * used for special runtime signaling purposes, such as connecting a
 365  * recursive union node to its worktable scan node or forcing plan
 366  * re-evaluation within the EvalPlanQual mechanism.  No actual Param node
 367  * exists with this ID, however.
 368  */
 369 int
 370 SS_assign_special_param(PlannerInfo *root)
 371 {
 372         return root->glob->nParamExec++;
 373 }
 374
 375 /*
 376  * Get the datatype/typmod/collation of the first column of the plan's output.
 377  *
 378  * This information is stored for ARRAY_SUBLINK execution and for
 379  * exprType()/exprTypmod()/exprCollation(), which have no way to get at the
 380  * plan associated with a SubPlan node.  We really only need the info for
 381  * EXPR_SUBLINK and ARRAY_SUBLINK subplans, but for consistency we save it
 382  * always.
 383  */
 384 static void
 385 get_first_col_type(Plan *plan, Oid *coltype, int32 *coltypmod,
 386                                    Oid *colcollation)
 387 {
 388         /* In cases such as EXISTS, tlist might be empty; arbitrarily use VOID */
 389         if (plan->targetlist)
 390         {
 391                 TargetEntry *tent = (TargetEntry *) linitial(plan->targetlist);
 392
 393                 Assert(IsA(tent, TargetEntry));
 394                 if (!tent->resjunk)
 395                 {
 396                         *coltype = exprType((Node *) tent->expr);
 397                         *coltypmod = exprTypmod((Node *) tent->expr);
 398                         *colcollation = exprCollation((Node *) tent->expr);
 399                         return;
 400                 }
 401         }
 402         *coltype = VOIDOID;
 403         *coltypmod = -1;
 404         *colcollation = InvalidOid;
 405 }
 406
 407 /*
 408  * Convert a SubLink (as created by the parser) into a SubPlan.
 409  *
 410  * We are given the SubLink's contained query, type, and testexpr.  We are
 411  * also told if this expression appears at top level of a WHERE/HAVING qual.
 412  *
 413  * Note: we assume that the testexpr has been AND/OR flattened (actually,
 414  * it's been through eval_const_expressions), but not converted to
 415  * implicit-AND form; and any SubLinks in it should already have been
 416  * converted to SubPlans.  The subquery is as yet untouched, however.
 417  *
 418  * The result is whatever we need to substitute in place of the SubLink
 419  * node in the executable expression.  This will be either the SubPlan
 420  * node (if we have to do the subplan as a subplan), or a Param node
 421  * representing the result of an InitPlan, or a row comparison expression
 422  * tree containing InitPlan Param nodes.
 423  */
 424 static Node *
 425 make_subplan(PlannerInfo *root, Query *orig_subquery, SubLinkType subLinkType,
 426                          Node *testexpr, bool isTopQual)
 427 {
 428         Query      *subquery;
 429         bool            simple_exists = false;
 430         double          tuple_fraction;
 431         Plan       *plan;
 432         PlannerInfo *subroot;
 433         List       *plan_params;
 434         Node       *result;
 435
 436         /*
 437          * Copy the source Query node.  This is a quick and dirty kluge to resolve
 438          * the fact that the parser can generate trees with multiple links to the
 439          * same sub-Query node, but the planner wants to scribble on the Query.
 440          * Try to clean this up when we do querytree redesign...
 441          */
 442         subquery = (Query *) copyObject(orig_subquery);
 443
 444         /*
 445          * If it's an EXISTS subplan, we might be able to simplify it.
 446          */
 447         if (subLinkType == EXISTS_SUBLINK)
 448                 simple_exists = simplify_EXISTS_query(subquery);
 449
 450         /*
 451          * For an EXISTS subplan, tell lower-level planner to expect that only the
 452          * first tuple will be retrieved.  For ALL and ANY subplans, we will be
 453          * able to stop evaluating if the test condition fails or matches, so very
 454          * often not all the tuples will be retrieved; for lack of a better idea,
 455          * specify 50% retrieval.  For EXPR and ROWCOMPARE subplans, use default
 456          * behavior (we're only expecting one row out, anyway).
 457          *
 458          * NOTE: if you change these numbers, also change cost_subplan() in
 459          * path/costsize.c.
 460          *
 461          * XXX If an ANY subplan is uncorrelated, build_subplan may decide to hash
 462          * its output.  In that case it would've been better to specify full
 463          * retrieval.  At present, however, we can only check hashability after
 464          * we've made the subplan :-(.  (Determining whether it'll fit in work_mem
 465          * is the really hard part.)  Therefore, we don't want to be too
 466          * optimistic about the percentage of tuples retrieved, for fear of
 467          * selecting a plan that's bad for the materialization case.
 468          */
 469         if (subLinkType == EXISTS_SUBLINK)
 470                 tuple_fraction = 1.0;   /* just like a LIMIT 1 */
 471         else if (subLinkType == ALL_SUBLINK ||
 472                          subLinkType == ANY_SUBLINK)
 473                 tuple_fraction = 0.5;   /* 50% */
 474         else
 475                 tuple_fraction = 0.0;   /* default behavior */
 476
 477         /* plan_params should not be in use in current query level */
 478         Assert(root->plan_params == NIL);
 479
 480         /*
 481          * Generate the plan for the subquery.
 482          */
 483         plan = subquery_planner(root->glob, subquery,
 484                                                         root,
 485                                                         false, tuple_fraction,
 486                                                         &subroot);
 487
 488         /* Isolate the params needed by this specific subplan */
 489         plan_params = root->plan_params;
 490         root->plan_params = NIL;
 491
 492         /* And convert to SubPlan or InitPlan format. */
 493         result = build_subplan(root, plan, subroot, plan_params,
 494                                                    subLinkType, testexpr, true, isTopQual);
 495
 496         /*
 497          * If it's a correlated EXISTS with an unimportant targetlist, we might be
 498          * able to transform it to the equivalent of an IN and then implement it
 499          * by hashing.  We don't have enough information yet to tell which way is
 500          * likely to be better (it depends on the expected number of executions of
 501          * the EXISTS qual, and we are much too early in planning the outer query
 502          * to be able to guess that).  So we generate both plans, if possible, and
 503          * leave it to the executor to decide which to use.
 504          */
 505         if (simple_exists && IsA(result, SubPlan))
 506         {
 507                 Node       *newtestexpr;
 508                 List       *paramIds;
 509
 510                 /* Make a second copy of the original subquery */
 511                 subquery = (Query *) copyObject(orig_subquery);
 512                 /* and re-simplify */
 513                 simple_exists = simplify_EXISTS_query(subquery);
 514                 Assert(simple_exists);
 515                 /* See if it can be converted to an ANY query */
 516                 subquery = convert_EXISTS_to_ANY(root, subquery,
 517                                                                                  &newtestexpr, &paramIds);
 518                 if (subquery)
 519                 {
 520                         /* Generate the plan for the ANY subquery; we'll need all rows */
 521                         plan = subquery_planner(root->glob, subquery,
 522                                                                         root,
 523                                                                         false, 0.0,
 524                                                                         &subroot);
 525
 526                         /* Isolate the params needed by this specific subplan */
 527                         plan_params = root->plan_params;
 528                         root->plan_params = NIL;
 529
 530                         /* Now we can check if it'll fit in work_mem */
 531                         if (subplan_is_hashable(plan))
 532                         {
 533                                 SubPlan    *hashplan;
 534                                 AlternativeSubPlan *asplan;
 535
 536                                 /* OK, convert to SubPlan format. */
 537                                 hashplan = (SubPlan *) build_subplan(root, plan, subroot,
 538                                                                                                          plan_params,
 539                                                                                                          ANY_SUBLINK, newtestexpr,
 540                                                                                                          false, true);
 541                                 /* Check we got what we expected */
 542                                 Assert(IsA(hashplan, SubPlan));
 543                                 Assert(hashplan->parParam == NIL);
 544                                 Assert(hashplan->useHashTable);
 545                                 /* build_subplan won't have filled in paramIds */
 546                                 hashplan->paramIds = paramIds;
 547
 548                                 /* Leave it to the executor to decide which plan to use */
 549                                 asplan = makeNode(AlternativeSubPlan);
 550                                 asplan->subplans = list_make2(result, hashplan);
 551                                 result = (Node *) asplan;
 552                         }
 553                 }
 554         }
 555
 556         return result;
 557 }
 558
 559 /*
 560  * Build a SubPlan node given the raw inputs --- subroutine for make_subplan
 561  *
 562  * Returns either the SubPlan, or an expression using initplan output Params,
 563  * as explained in the comments for make_subplan.
 564  */
 565 static Node *
 566 build_subplan(PlannerInfo *root, Plan *plan, PlannerInfo *subroot,
 567                           List *plan_params,
 568                           SubLinkType subLinkType, Node *testexpr,
 569                           bool adjust_testexpr, bool unknownEqFalse)
 570 {
 571         Node       *result;
 572         SubPlan    *splan;
 573         bool            isInitPlan;
 574         ListCell   *lc;
 575
 576         /*
 577          * Initialize the SubPlan node.  Note plan_id, plan_name, and cost fields
 578          * are set further down.
 579          */
 580         splan = makeNode(SubPlan);
 581         splan->subLinkType = subLinkType;
 582         splan->testexpr = NULL;
 583         splan->paramIds = NIL;
 584         get_first_col_type(plan, &splan->firstColType, &splan->firstColTypmod,
 585                                            &splan->firstColCollation);
 586         splan->useHashTable = false;
 587         splan->unknownEqFalse = unknownEqFalse;
 588         splan->setParam = NIL;
 589         splan->parParam = NIL;
 590         splan->args = NIL;
 591
 592         /*
 593          * Make parParam and args lists of param IDs and expressions that current
 594          * query level will pass to this child plan.
 595          */
 596         foreach(lc, plan_params)
 597         {
 598                 PlannerParamItem *pitem = (PlannerParamItem *) lfirst(lc);
 599                 Node       *arg = pitem->item;
 600
 601                 /*
 602                  * The Var, PlaceHolderVar, or Aggref has already been adjusted to
 603                  * have the correct varlevelsup, phlevelsup, or agglevelsup.
 604                  *
 605                  * If it's a PlaceHolderVar or Aggref, its arguments might contain
 606                  * SubLinks, which have not yet been processed (see the comments for
 607                  * SS_replace_correlation_vars).  Do that now.
 608                  */
 609                 if (IsA(arg, PlaceHolderVar) ||
 610                         IsA(arg, Aggref))
 611                         arg = SS_process_sublinks(root, arg, false);
 612
 613                 splan->parParam = lappend_int(splan->parParam, pitem->paramId);
 614                 splan->args = lappend(splan->args, arg);
 615         }
 616
 617         /*
 618          * Un-correlated or undirect correlated plans of EXISTS, EXPR, ARRAY, or
 619          * ROWCOMPARE types can be used as initPlans.  For EXISTS, EXPR, or ARRAY,
 620          * we just produce a Param referring to the result of evaluating the
 621          * initPlan.  For ROWCOMPARE, we must modify the testexpr tree to contain
 622          * PARAM_EXEC Params instead of the PARAM_SUBLINK Params emitted by the
 623          * parser.
 624          */
 625         if (splan->parParam == NIL && subLinkType == EXISTS_SUBLINK)
 626         {
 627                 Param      *prm;
 628
 629                 Assert(testexpr == NULL);
 630                 prm = generate_new_param(root, BOOLOID, -1, InvalidOid);
 631                 splan->setParam = list_make1_int(prm->paramid);
 632                 isInitPlan = true;
 633                 result = (Node *) prm;
 634         }
 635         else if (splan->parParam == NIL && subLinkType == EXPR_SUBLINK)
 636         {
 637                 TargetEntry *te = linitial(plan->targetlist);
 638                 Param      *prm;
 639
 640                 Assert(!te->resjunk);
 641                 Assert(testexpr == NULL);
 642                 prm = generate_new_param(root,
 643                                                                  exprType((Node *) te->expr),
 644                                                                  exprTypmod((Node *) te->expr),
 645                                                                  exprCollation((Node *) te->expr));
 646                 splan->setParam = list_make1_int(prm->paramid);
 647                 isInitPlan = true;
 648                 result = (Node *) prm;
 649         }
 650         else if (splan->parParam == NIL && subLinkType == ARRAY_SUBLINK)
 651         {
 652                 TargetEntry *te = linitial(plan->targetlist);
 653                 Oid                     arraytype;
 654                 Param      *prm;
 655
 656                 Assert(!te->resjunk);
 657                 Assert(testexpr == NULL);
 658                 arraytype = get_array_type(exprType((Node *) te->expr));
 659                 if (!OidIsValid(arraytype))
 660                         elog(ERROR, "could not find array type for datatype %s",
 661                                  format_type_be(exprType((Node *) te->expr)));
 662                 prm = generate_new_param(root,
 663                                                                  arraytype,
 664                                                                  exprTypmod((Node *) te->expr),
 665                                                                  exprCollation((Node *) te->expr));
 666                 splan->setParam = list_make1_int(prm->paramid);
 667                 isInitPlan = true;
 668                 result = (Node *) prm;
 669         }
 670         else if (splan->parParam == NIL && subLinkType == ROWCOMPARE_SUBLINK)
 671         {
 672                 /* Adjust the Params */
 673                 List       *params;
 674
 675                 Assert(testexpr != NULL);
 676                 params = generate_subquery_params(root,
 677                                                                                   plan->targetlist,
 678                                                                                   &splan->paramIds);
 679                 result = convert_testexpr(root,
 680                                                                   testexpr,
 681                                                                   params);
 682                 splan->setParam = list_copy(splan->paramIds);
 683                 isInitPlan = true;
 684
 685                 /*
 686                  * The executable expression is returned to become part of the outer
 687                  * plan's expression tree; it is not kept in the initplan node.
 688                  */
 689         }
 690         else
 691         {
 692                 /*
 693                  * Adjust the Params in the testexpr, unless caller said it's not
 694                  * needed.
 695                  */
 696                 if (testexpr && adjust_testexpr)
 697                 {
 698                         List       *params;
 699
 700                         params = generate_subquery_params(root,
 701                                                                                           plan->targetlist,
 702                                                                                           &splan->paramIds);
 703                         splan->testexpr = convert_testexpr(root,
 704                                                                                            testexpr,
 705                                                                                            params);
 706                 }
 707                 else
 708                         splan->testexpr = testexpr;
 709
 710                 /*
 711                  * We can't convert subplans of ALL_SUBLINK or ANY_SUBLINK types to
 712                  * initPlans, even when they are uncorrelated or undirect correlated,
 713                  * because we need to scan the output of the subplan for each outer
 714                  * tuple.  But if it's a not-direct-correlated IN (= ANY) test, we
 715                  * might be able to use a hashtable to avoid comparing all the tuples.
 716                  */
 717                 if (subLinkType == ANY_SUBLINK &&
 718                         splan->parParam == NIL &&
 719                         subplan_is_hashable(plan) &&
 720                         testexpr_is_hashable(splan->testexpr))
 721                         splan->useHashTable = true;
 722
 723                 /*
 724                  * Otherwise, we have the option to tack a Material node onto the top
 725                  * of the subplan, to reduce the cost of reading it repeatedly.  This
 726                  * is pointless for a direct-correlated subplan, since we'd have to
 727                  * recompute its results each time anyway.      For uncorrelated/undirect
 728                  * correlated subplans, we add Material unless the subplan's top plan
 729                  * node would materialize its output anyway.  Also, if enable_material
 730                  * is false, then the user does not want us to materialize anything
 731                  * unnecessarily, so we don't.
 732                  */
 733                 else if (splan->parParam == NIL && enable_material &&
 734                                  !ExecMaterializesOutput(nodeTag(plan)))
 735                         plan = materialize_finished_plan(plan);
 736
 737                 result = (Node *) splan;
 738                 isInitPlan = false;
 739         }
 740
 741         /*
 742          * Add the subplan and its PlannerInfo to the global lists.
 743          */
 744         root->glob->subplans = lappend(root->glob->subplans, plan);
 745         root->glob->subroots = lappend(root->glob->subroots, subroot);
 746         splan->plan_id = list_length(root->glob->subplans);
 747
 748         if (isInitPlan)
 749                 root->init_plans = lappend(root->init_plans, splan);
 750
 751         /*
 752          * A parameterless subplan (not initplan) should be prepared to handle
 753          * REWIND efficiently.  If it has direct parameters then there's no point
 754          * since it'll be reset on each scan anyway; and if it's an initplan then
 755          * there's no point since it won't get re-run without parameter changes
 756          * anyway.      The input of a hashed subplan doesn't need REWIND either.
 757          */
 758         if (splan->parParam == NIL && !isInitPlan && !splan->useHashTable)
 759                 root->glob->rewindPlanIDs = bms_add_member(root->glob->rewindPlanIDs,
 760                                                                                                    splan->plan_id);
 761
 762         /* Label the subplan for EXPLAIN purposes */
 763         if (isInitPlan)
 764         {
 765                 ListCell   *lc;
 766                 int                     offset;
 767
 768                 splan->plan_name = palloc(32 + 12 * list_length(splan->setParam));
 769                 sprintf(splan->plan_name, "InitPlan %d (returns ", splan->plan_id);
 770                 offset = strlen(splan->plan_name);
 771                 foreach(lc, splan->setParam)
 772                 {
 773                         sprintf(splan->plan_name + offset, "$%d%s",
 774                                         lfirst_int(lc),
 775                                         lnext(lc) ? "," : "");
 776                         offset += strlen(splan->plan_name + offset);
 777                 }
 778                 sprintf(splan->plan_name + offset, ")");
 779         }
 780         else
 781         {
 782                 splan->plan_name = palloc(32);
 783                 sprintf(splan->plan_name, "SubPlan %d", splan->plan_id);
 784         }
 785
 786         /* Lastly, fill in the cost estimates for use later */
 787         cost_subplan(root, splan, plan);
 788
 789         return result;
 790 }
 791
 792 /*
 793  * generate_subquery_params: build a list of Params representing the output
 794  * columns of a sublink's sub-select, given the sub-select's targetlist.
 795  *
 796  * We also return an integer list of the paramids of the Params.
 797  */
 798 static List *
 799 generate_subquery_params(PlannerInfo *root, List *tlist, List **paramIds)
 800 {
 801         List       *result;
 802         List       *ids;
 803         ListCell   *lc;
 804
 805         result = ids = NIL;
 806         foreach(lc, tlist)
 807         {
 808                 TargetEntry *tent = (TargetEntry *) lfirst(lc);
 809                 Param      *param;
 810
 811                 if (tent->resjunk)
 812                         continue;
 813
 814                 param = generate_new_param(root,
 815                                                                    exprType((Node *) tent->expr),
 816                                                                    exprTypmod((Node *) tent->expr),
 817                                                                    exprCollation((Node *) tent->expr));
 818                 result = lappend(result, param);
 819                 ids = lappend_int(ids, param->paramid);
 820         }
 821
 822         *paramIds = ids;
 823         return result;
 824 }
 825
 826 /*
 827  * generate_subquery_vars: build a list of Vars representing the output
 828  * columns of a sublink's sub-select, given the sub-select's targetlist.
 829  * The Vars have the specified varno (RTE index).
 830  */
 831 static List *
 832 generate_subquery_vars(PlannerInfo *root, List *tlist, Index varno)
 833 {
 834         List       *result;
 835         ListCell   *lc;
 836
 837         result = NIL;
 838         foreach(lc, tlist)
 839         {
 840                 TargetEntry *tent = (TargetEntry *) lfirst(lc);
 841                 Var                *var;
 842
 843                 if (tent->resjunk)
 844                         continue;
 845
 846                 var = makeVarFromTargetEntry(varno, tent);
 847                 result = lappend(result, var);
 848         }
 849
 850         return result;
 851 }
 852
 853 /*
 854  * convert_testexpr: convert the testexpr given by the parser into
 855  * actually executable form.  This entails replacing PARAM_SUBLINK Params
 856  * with Params or Vars representing the results of the sub-select.      The
 857  * nodes to be substituted are passed in as the List result from
 858  * generate_subquery_params or generate_subquery_vars.
 859  *
 860  * The given testexpr has already been recursively processed by
 861  * process_sublinks_mutator.  Hence it can no longer contain any
 862  * PARAM_SUBLINK Params for lower SubLink nodes; we can safely assume that
 863  * any we find are for our own level of SubLink.
 864  */
 865 static Node *
 866 convert_testexpr(PlannerInfo *root,
 867                                  Node *testexpr,
 868                                  List *subst_nodes)
 869 {
 870         convert_testexpr_context context;
 871
 872         context.root = root;
 873         context.subst_nodes = subst_nodes;
 874         return convert_testexpr_mutator(testexpr, &context);
 875 }
 876
 877 static Node *
 878 convert_testexpr_mutator(Node *node,
 879                                                  convert_testexpr_context *context)
 880 {
 881         if (node == NULL)
 882                 return NULL;
 883         if (IsA(node, Param))
 884         {
 885                 Param      *param = (Param *) node;
 886
 887                 if (param->paramkind == PARAM_SUBLINK)
 888                 {
 889                         if (param->paramid <= 0 ||
 890                                 param->paramid > list_length(context->subst_nodes))
 891                                 elog(ERROR, "unexpected PARAM_SUBLINK ID: %d", param->paramid);
 892
 893                         /*
 894                          * We copy the list item to avoid having doubly-linked
 895                          * substructure in the modified parse tree.  This is probably
 896                          * unnecessary when it's a Param, but be safe.
 897                          */
 898                         return (Node *) copyObject(list_nth(context->subst_nodes,
 899                                                                                                 param->paramid - 1));
 900                 }
 901         }
 902         return expression_tree_mutator(node,
 903                                                                    convert_testexpr_mutator,
 904                                                                    (void *) context);
 905 }
 906
 907 /*
 908  * subplan_is_hashable: can we implement an ANY subplan by hashing?
 909  */
 910 static bool
 911 subplan_is_hashable(Plan *plan)
 912 {
 913         double          subquery_size;
 914
 915         /*
 916          * The estimated size of the subquery result must fit in work_mem. (Note:
 917          * we use sizeof(HeapTupleHeaderData) here even though the tuples will
 918          * actually be stored as MinimalTuples; this provides some fudge factor
 919          * for hashtable overhead.)
 920          */
 921         subquery_size = plan->plan_rows *
 922                 (MAXALIGN(plan->plan_width) + MAXALIGN(sizeof(HeapTupleHeaderData)));
 923         if (subquery_size > work_mem * 1024L)
 924                 return false;
 925
 926         return true;
 927 }
 928
 929 /*
 930  * testexpr_is_hashable: is an ANY SubLink's test expression hashable?
 931  */
 932 static bool
 933 testexpr_is_hashable(Node *testexpr)
 934 {
 935         /*
 936          * The testexpr must be a single OpExpr, or an AND-clause containing only
 937          * OpExprs.
 938          *
 939          * The combining operators must be hashable and strict. The need for
 940          * hashability is obvious, since we want to use hashing. Without
 941          * strictness, behavior in the presence of nulls is too unpredictable.  We
 942          * actually must assume even more than plain strictness: they can't yield
 943          * NULL for non-null inputs, either (see nodeSubplan.c).  However, hash
 944          * indexes and hash joins assume that too.
 945          */
 946         if (testexpr && IsA(testexpr, OpExpr))
 947         {
 948                 if (hash_ok_operator((OpExpr *) testexpr))
 949                         return true;
 950         }
 951         else if (and_clause(testexpr))
 952         {
 953                 ListCell   *l;
 954
 955                 foreach(l, ((BoolExpr *) testexpr)->args)
 956                 {
 957                         Node       *andarg = (Node *) lfirst(l);
 958
 959                         if (!IsA(andarg, OpExpr))
 960                                 return false;
 961                         if (!hash_ok_operator((OpExpr *) andarg))
 962                                 return false;
 963                 }
 964                 return true;
 965         }
 966
 967         return false;
 968 }
 969
 970 /*
 971  * Check expression is hashable + strict
 972  *
 973  * We could use op_hashjoinable() and op_strict(), but do it like this to
 974  * avoid a redundant cache lookup.
 975  */
 976 static bool
 977 hash_ok_operator(OpExpr *expr)
 978 {
 979         Oid                     opid = expr->opno;
 980
 981         /* quick out if not a binary operator */
 982         if (list_length(expr->args) != 2)
 983                 return false;
 984         if (opid == ARRAY_EQ_OP)
 985         {
 986                 /* array_eq is strict, but must check input type to ensure hashable */
 987                 /* XXX record_eq will need same treatment when it becomes hashable */
 988                 Node       *leftarg = linitial(expr->args);
 989
 990                 return op_hashjoinable(opid, exprType(leftarg));
 991         }
 992         else
 993         {
 994                 /* else must look up the operator properties */
 995                 HeapTuple       tup;
 996                 Form_pg_operator optup;
 997
 998                 tup = SearchSysCache1(OPEROID, ObjectIdGetDatum(opid));
 999                 if (!HeapTupleIsValid(tup))
1000                         elog(ERROR, "cache lookup failed for operator %u", opid);
1001                 optup = (Form_pg_operator) GETSTRUCT(tup);
1002                 if (!optup->oprcanhash || !func_strict(optup->oprcode))
1003                 {
1004                         ReleaseSysCache(tup);
1005                         return false;
1006                 }
1007                 ReleaseSysCache(tup);
1008                 return true;
1009         }
1010 }
1011
1012
1013 /*
1014  * SS_process_ctes: process a query's WITH list
1015  *
1016  * We plan each interesting WITH item and convert it to an initplan.
1017  * A side effect is to fill in root->cte_plan_ids with a list that
1018  * parallels root->parse->cteList and provides the subplan ID for
1019  * each CTE's initplan.
1020  */
1021 void
1022 SS_process_ctes(PlannerInfo *root)
1023 {
1024         ListCell   *lc;
1025
1026         Assert(root->cte_plan_ids == NIL);
1027
1028         foreach(lc, root->parse->cteList)
1029         {
1030                 CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
1031                 CmdType         cmdType = ((Query *) cte->ctequery)->commandType;
1032                 Query      *subquery;
1033                 Plan       *plan;
1034                 PlannerInfo *subroot;
1035                 SubPlan    *splan;
1036                 int                     paramid;
1037
1038                 /*
1039                  * Ignore SELECT CTEs that are not actually referenced anywhere.
1040                  */
1041                 if (cte->cterefcount == 0 && cmdType == CMD_SELECT)
1042                 {
1043                         /* Make a dummy entry in cte_plan_ids */
1044                         root->cte_plan_ids = lappend_int(root->cte_plan_ids, -1);
1045                         continue;
1046                 }
1047
1048                 /*
1049                  * Copy the source Query node.  Probably not necessary, but let's keep
1050                  * this similar to make_subplan.
1051                  */
1052                 subquery = (Query *) copyObject(cte->ctequery);
1053
1054                 /* plan_params should not be in use in current query level */
1055                 Assert(root->plan_params == NIL);
1056
1057                 /*
1058                  * Generate the plan for the CTE query.  Always plan for full
1059                  * retrieval --- we don't have enough info to predict otherwise.
1060                  */
1061                 plan = subquery_planner(root->glob, subquery,
1062                                                                 root,
1063                                                                 cte->cterecursive, 0.0,
1064                                                                 &subroot);
1065
1066                 /*
1067                  * Since the current query level doesn't yet contain any RTEs, it
1068                  * should not be possible for the CTE to have requested parameters of
1069                  * this level.
1070                  */
1071                 if (root->plan_params)
1072                         elog(ERROR, "unexpected outer reference in CTE query");
1073
1074                 /*
1075                  * Make a SubPlan node for it.  This is just enough unlike
1076                  * build_subplan that we can't share code.
1077                  *
1078                  * Note plan_id, plan_name, and cost fields are set further down.
1079                  */
1080                 splan = makeNode(SubPlan);
1081                 splan->subLinkType = CTE_SUBLINK;
1082                 splan->testexpr = NULL;
1083                 splan->paramIds = NIL;
1084                 get_first_col_type(plan, &splan->firstColType, &splan->firstColTypmod,
1085                                                    &splan->firstColCollation);
1086                 splan->useHashTable = false;
1087                 splan->unknownEqFalse = false;
1088                 splan->setParam = NIL;
1089                 splan->parParam = NIL;
1090                 splan->args = NIL;
1091
1092                 /*
1093                  * The node can't have any inputs (since it's an initplan), so the
1094                  * parParam and args lists remain empty.  (It could contain references
1095                  * to earlier CTEs' output param IDs, but CTE outputs are not
1096                  * propagated via the args list.)
1097                  */
1098
1099                 /*
1100                  * Assign a param ID to represent the CTE's output.  No ordinary
1101                  * "evaluation" of this param slot ever happens, but we use the param
1102                  * ID for setParam/chgParam signaling just as if the CTE plan were
1103                  * returning a simple scalar output.  (Also, the executor abuses the
1104                  * ParamExecData slot for this param ID for communication among
1105                  * multiple CteScan nodes that might be scanning this CTE.)
1106                  */
1107                 paramid = SS_assign_special_param(root);
1108                 splan->setParam = list_make1_int(paramid);
1109
1110                 /*
1111                  * Add the subplan and its PlannerInfo to the global lists.
1112                  */
1113                 root->glob->subplans = lappend(root->glob->subplans, plan);
1114                 root->glob->subroots = lappend(root->glob->subroots, subroot);
1115                 splan->plan_id = list_length(root->glob->subplans);
1116
1117                 root->init_plans = lappend(root->init_plans, splan);
1118
1119                 root->cte_plan_ids = lappend_int(root->cte_plan_ids, splan->plan_id);
1120
1121                 /* Label the subplan for EXPLAIN purposes */
1122                 splan->plan_name = palloc(4 + strlen(cte->ctename) + 1);
1123                 sprintf(splan->plan_name, "CTE %s", cte->ctename);
1124
1125                 /* Lastly, fill in the cost estimates for use later */
1126                 cost_subplan(root, splan, plan);
1127         }
1128 }
1129
1130 /*
1131  * convert_ANY_sublink_to_join: try to convert an ANY SubLink to a join
1132  *
1133  * The caller has found an ANY SubLink at the top level of one of the query's
1134  * qual clauses, but has not checked the properties of the SubLink further.
1135  * Decide whether it is appropriate to process this SubLink in join style.
1136  * If so, form a JoinExpr and return it.  Return NULL if the SubLink cannot
1137  * be converted to a join.
1138  *
1139  * The only non-obvious input parameter is available_rels: this is the set
1140  * of query rels that can safely be referenced in the sublink expression.
1141  * (We must restrict this to avoid changing the semantics when a sublink
1142  * is present in an outer join's ON qual.)  The conversion must fail if
1143  * the converted qual would reference any but these parent-query relids.
1144  *
1145  * On success, the returned JoinExpr has larg = NULL and rarg = the jointree
1146  * item representing the pulled-up subquery.  The caller must set larg to
1147  * represent the relation(s) on the lefthand side of the new join, and insert
1148  * the JoinExpr into the upper query's jointree at an appropriate place
1149  * (typically, where the lefthand relation(s) had been).  Note that the
1150  * passed-in SubLink must also be removed from its original position in the
1151  * query quals, since the quals of the returned JoinExpr replace it.
1152  * (Notionally, we replace the SubLink with a constant TRUE, then elide the
1153  * redundant constant from the qual.)
1154  *
1155  * On success, the caller is also responsible for recursively applying
1156  * pull_up_sublinks processing to the rarg and quals of the returned JoinExpr.
1157  * (On failure, there is no need to do anything, since pull_up_sublinks will
1158  * be applied when we recursively plan the sub-select.)
1159  *
1160  * Side effects of a successful conversion include adding the SubLink's
1161  * subselect to the query's rangetable, so that it can be referenced in
1162  * the JoinExpr's rarg.
1163  */
1164 JoinExpr *
1165 convert_ANY_sublink_to_join(PlannerInfo *root, SubLink *sublink,
1166                                                         Relids available_rels)
1167 {
1168         JoinExpr   *result;
1169         Query      *parse = root->parse;
1170         Query      *subselect = (Query *) sublink->subselect;
1171         Relids          upper_varnos;
1172         int                     rtindex;
1173         RangeTblEntry *rte;
1174         RangeTblRef *rtr;
1175         List       *subquery_vars;
1176         Node       *quals;
1177
1178         Assert(sublink->subLinkType == ANY_SUBLINK);
1179
1180         /*
1181          * The sub-select must not refer to any Vars of the parent query. (Vars of
1182          * higher levels should be okay, though.)
1183          */
1184         if (contain_vars_of_level((Node *) subselect, 1))
1185                 return NULL;
1186
1187         /*
1188          * The test expression must contain some Vars of the parent query, else
1189          * it's not gonna be a join.  (Note that it won't have Vars referring to
1190          * the subquery, rather Params.)
1191          */
1192         upper_varnos = pull_varnos(sublink->testexpr);
1193         if (bms_is_empty(upper_varnos))
1194                 return NULL;
1195
1196         /*
1197          * However, it can't refer to anything outside available_rels.
1198          */
1199         if (!bms_is_subset(upper_varnos, available_rels))
1200                 return NULL;
1201
1202         /*
1203          * The combining operators and left-hand expressions mustn't be volatile.
1204          */
1205         if (contain_volatile_functions(sublink->testexpr))
1206                 return NULL;
1207
1208         /*
1209          * Okay, pull up the sub-select into upper range table.
1210          *
1211          * We rely here on the assumption that the outer query has no references
1212          * to the inner (necessarily true, other than the Vars that we build
1213          * below). Therefore this is a lot easier than what pull_up_subqueries has
1214          * to go through.
1215          */
1216         rte = addRangeTableEntryForSubquery(NULL,
1217                                                                                 subselect,
1218                                                                                 makeAlias("ANY_subquery", NIL),
1219                                                                                 false,
1220                                                                                 false);
1221         parse->rtable = lappend(parse->rtable, rte);
1222         rtindex = list_length(parse->rtable);
1223
1224         /*
1225          * Form a RangeTblRef for the pulled-up sub-select.
1226          */
1227         rtr = makeNode(RangeTblRef);
1228         rtr->rtindex = rtindex;
1229
1230         /*
1231          * Build a list of Vars representing the subselect outputs.
1232          */
1233         subquery_vars = generate_subquery_vars(root,
1234                                                                                    subselect->targetList,
1235                                                                                    rtindex);
1236
1237         /*
1238          * Build the new join's qual expression, replacing Params with these Vars.
1239          */
1240         quals = convert_testexpr(root, sublink->testexpr, subquery_vars);
1241
1242         /*
1243          * And finally, build the JoinExpr node.
1244          */
1245         result = makeNode(JoinExpr);
1246         result->jointype = JOIN_SEMI;
1247         result->isNatural = false;
1248         result->larg = NULL;            /* caller must fill this in */
1249         result->rarg = (Node *) rtr;
1250         result->usingClause = NIL;
1251         result->quals = quals;
1252         result->alias = NULL;
1253         result->rtindex = 0;            /* we don't need an RTE for it */
1254
1255         return result;
1256 }
1257
1258 /*
1259  * convert_EXISTS_sublink_to_join: try to convert an EXISTS SubLink to a join
1260  *
1261  * The API of this function is identical to convert_ANY_sublink_to_join's,
1262  * except that we also support the case where the caller has found NOT EXISTS,
1263  * so we need an additional input parameter "under_not".
1264  */
1265 JoinExpr *
1266 convert_EXISTS_sublink_to_join(PlannerInfo *root, SubLink *sublink,
1267                                                            bool under_not, Relids available_rels)
1268 {
1269         JoinExpr   *result;
1270         Query      *parse = root->parse;
1271         Query      *subselect = (Query *) sublink->subselect;
1272         Node       *whereClause;
1273         int                     rtoffset;
1274         int                     varno;
1275         Relids          clause_varnos;
1276         Relids          upper_varnos;
1277
1278         Assert(sublink->subLinkType == EXISTS_SUBLINK);
1279
1280         /*
1281          * Can't flatten if it contains WITH.  (We could arrange to pull up the
1282          * WITH into the parent query's cteList, but that risks changing the
1283          * semantics, since a WITH ought to be executed once per associated query
1284          * call.)  Note that convert_ANY_sublink_to_join doesn't have to reject
1285          * this case, since it just produces a subquery RTE that doesn't have to
1286          * get flattened into the parent query.
1287          */
1288         if (subselect->cteList)
1289                 return NULL;
1290
1291         /*
1292          * Copy the subquery so we can modify it safely (see comments in
1293          * make_subplan).
1294          */
1295         subselect = (Query *) copyObject(subselect);
1296
1297         /*
1298          * See if the subquery can be simplified based on the knowledge that it's
1299          * being used in EXISTS().      If we aren't able to get rid of its
1300          * targetlist, we have to fail, because the pullup operation leaves us
1301          * with noplace to evaluate the targetlist.
1302          */
1303         if (!simplify_EXISTS_query(subselect))
1304                 return NULL;
1305
1306         /*
1307          * The subquery must have a nonempty jointree, else we won't have a join.
1308          */
1309         if (subselect->jointree->fromlist == NIL)
1310                 return NULL;
1311
1312         /*
1313          * Separate out the WHERE clause.  (We could theoretically also remove
1314          * top-level plain JOIN/ON clauses, but it's probably not worth the
1315          * trouble.)
1316          */
1317         whereClause = subselect->jointree->quals;
1318         subselect->jointree->quals = NULL;
1319
1320         /*
1321          * The rest of the sub-select must not refer to any Vars of the parent
1322          * query.  (Vars of higher levels should be okay, though.)
1323          */
1324         if (contain_vars_of_level((Node *) subselect, 1))
1325                 return NULL;
1326
1327         /*
1328          * On the other hand, the WHERE clause must contain some Vars of the
1329          * parent query, else it's not gonna be a join.
1330          */
1331         if (!contain_vars_of_level(whereClause, 1))
1332                 return NULL;
1333
1334         /*
1335          * We don't risk optimizing if the WHERE clause is volatile, either.
1336          */
1337         if (contain_volatile_functions(whereClause))
1338                 return NULL;
1339
1340         /*
1341          * Prepare to pull up the sub-select into top range table.
1342          *
1343          * We rely here on the assumption that the outer query has no references
1344          * to the inner (necessarily true). Therefore this is a lot easier than
1345          * what pull_up_subqueries has to go through.
1346          *
1347          * In fact, it's even easier than what convert_ANY_sublink_to_join has to
1348          * do.  The machinations of simplify_EXISTS_query ensured that there is
1349          * nothing interesting in the subquery except an rtable and jointree, and
1350          * even the jointree FromExpr no longer has quals.      So we can just append
1351          * the rtable to our own and use the FromExpr in our jointree. But first,
1352          * adjust all level-zero varnos in the subquery to account for the rtable
1353          * merger.
1354          */
1355         rtoffset = list_length(parse->rtable);
1356         OffsetVarNodes((Node *) subselect, rtoffset, 0);
1357         OffsetVarNodes(whereClause, rtoffset, 0);
1358
1359         /*
1360          * Upper-level vars in subquery will now be one level closer to their
1361          * parent than before; in particular, anything that had been level 1
1362          * becomes level zero.
1363          */
1364         IncrementVarSublevelsUp((Node *) subselect, -1, 1);
1365         IncrementVarSublevelsUp(whereClause, -1, 1);
1366
1367         /*
1368          * Now that the WHERE clause is adjusted to match the parent query
1369          * environment, we can easily identify all the level-zero rels it uses.
1370          * The ones <= rtoffset belong to the upper query; the ones > rtoffset do
1371          * not.
1372          */
1373         clause_varnos = pull_varnos(whereClause);
1374         upper_varnos = NULL;
1375         while ((varno = bms_first_member(clause_varnos)) >= 0)
1376         {
1377                 if (varno <= rtoffset)
1378                         upper_varnos = bms_add_member(upper_varnos, varno);
1379         }
1380         bms_free(clause_varnos);
1381         Assert(!bms_is_empty(upper_varnos));
1382
1383         /*
1384          * Now that we've got the set of upper-level varnos, we can make the last
1385          * check: only available_rels can be referenced.
1386          */
1387         if (!bms_is_subset(upper_varnos, available_rels))
1388                 return NULL;
1389
1390         /* Now we can attach the modified subquery rtable to the parent */
1391         parse->rtable = list_concat(parse->rtable, subselect->rtable);
1392
1393         /*
1394          * And finally, build the JoinExpr node.
1395          */
1396         result = makeNode(JoinExpr);
1397         result->jointype = under_not ? JOIN_ANTI : JOIN_SEMI;
1398         result->isNatural = false;
1399         result->larg = NULL;            /* caller must fill this in */
1400         /* flatten out the FromExpr node if it's useless */
1401         if (list_length(subselect->jointree->fromlist) == 1)
1402                 result->rarg = (Node *) linitial(subselect->jointree->fromlist);
1403         else
1404                 result->rarg = (Node *) subselect->jointree;
1405         result->usingClause = NIL;
1406         result->quals = whereClause;
1407         result->alias = NULL;
1408         result->rtindex = 0;            /* we don't need an RTE for it */
1409
1410         return result;
1411 }
1412
1413 /*
1414  * simplify_EXISTS_query: remove any useless stuff in an EXISTS's subquery
1415  *
1416  * The only thing that matters about an EXISTS query is whether it returns
1417  * zero or more than zero rows.  Therefore, we can remove certain SQL features
1418  * that won't affect that.  The only part that is really likely to matter in
1419  * typical usage is simplifying the targetlist: it's a common habit to write
1420  * "SELECT * FROM" even though there is no need to evaluate any columns.
1421  *
1422  * Note: by suppressing the targetlist we could cause an observable behavioral
1423  * change, namely that any errors that might occur in evaluating the tlist
1424  * won't occur, nor will other side-effects of volatile functions.  This seems
1425  * unlikely to bother anyone in practice.
1426  *
1427  * Returns TRUE if was able to discard the targetlist, else FALSE.
1428  */
1429 static bool
1430 simplify_EXISTS_query(Query *query)
1431 {
1432         /*
1433          * We don't try to simplify at all if the query uses set operations,
1434          * aggregates, modifying CTEs, HAVING, LIMIT/OFFSET, or FOR UPDATE/SHARE;
1435          * none of these seem likely in normal usage and their possible effects
1436          * are complex.
1437          */
1438         if (query->commandType != CMD_SELECT ||
1439                 query->setOperations ||
1440                 query->hasAggs ||
1441                 query->hasWindowFuncs ||
1442                 query->hasModifyingCTE ||
1443                 query->havingQual ||
1444                 query->limitOffset ||
1445                 query->limitCount ||
1446                 query->rowMarks)
1447                 return false;
1448
1449         /*
1450          * Mustn't throw away the targetlist if it contains set-returning
1451          * functions; those could affect whether zero rows are returned!
1452          */
1453         if (expression_returns_set((Node *) query->targetList))
1454                 return false;
1455
1456         /*
1457          * Otherwise, we can throw away the targetlist, as well as any GROUP,
1458          * WINDOW, DISTINCT, and ORDER BY clauses; none of those clauses will
1459          * change a nonzero-rows result to zero rows or vice versa.  (Furthermore,
1460          * since our parsetree representation of these clauses depends on the
1461          * targetlist, we'd better throw them away if we drop the targetlist.)
1462          */
1463         query->targetList = NIL;
1464         query->groupClause = NIL;
1465         query->windowClause = NIL;
1466         query->distinctClause = NIL;
1467         query->sortClause = NIL;
1468         query->hasDistinctOn = false;
1469
1470         return true;
1471 }
1472
1473 /*
1474  * convert_EXISTS_to_ANY: try to convert EXISTS to a hashable ANY sublink
1475  *
1476  * The subselect is expected to be a fresh copy that we can munge up,
1477  * and to have been successfully passed through simplify_EXISTS_query.
1478  *
1479  * On success, the modified subselect is returned, and we store a suitable
1480  * upper-level test expression at *testexpr, plus a list of the subselect's
1481  * output Params at *paramIds.  (The test expression is already Param-ified
1482  * and hence need not go through convert_testexpr, which is why we have to
1483  * deal with the Param IDs specially.)
1484  *
1485  * On failure, returns NULL.
1486  */
1487 static Query *
1488 convert_EXISTS_to_ANY(PlannerInfo *root, Query *subselect,
1489                                           Node **testexpr, List **paramIds)
1490 {
1491         Node       *whereClause;
1492         List       *leftargs,
1493                            *rightargs,
1494                            *opids,
1495                            *opcollations,
1496                            *newWhere,
1497                            *tlist,
1498                            *testlist,
1499                            *paramids;
1500         ListCell   *lc,
1501                            *rc,
1502                            *oc,
1503                            *cc;
1504         AttrNumber      resno;
1505
1506         /*
1507          * Query must not require a targetlist, since we have to insert a new one.
1508          * Caller should have dealt with the case already.
1509          */
1510         Assert(subselect->targetList == NIL);
1511
1512         /*
1513          * Separate out the WHERE clause.  (We could theoretically also remove
1514          * top-level plain JOIN/ON clauses, but it's probably not worth the
1515          * trouble.)
1516          */
1517         whereClause = subselect->jointree->quals;
1518         subselect->jointree->quals = NULL;
1519
1520         /*
1521          * The rest of the sub-select must not refer to any Vars of the parent
1522          * query.  (Vars of higher levels should be okay, though.)
1523          *
1524          * Note: we need not check for Aggrefs separately because we know the
1525          * sub-select is as yet unoptimized; any uplevel Aggref must therefore
1526          * contain an uplevel Var reference.  This is not the case below ...
1527          */
1528         if (contain_vars_of_level((Node *) subselect, 1))
1529                 return NULL;
1530
1531         /*
1532          * We don't risk optimizing if the WHERE clause is volatile, either.
1533          */
1534         if (contain_volatile_functions(whereClause))
1535                 return NULL;
1536
1537         /*
1538          * Clean up the WHERE clause by doing const-simplification etc on it.
1539          * Aside from simplifying the processing we're about to do, this is
1540          * important for being able to pull chunks of the WHERE clause up into the
1541          * parent query.  Since we are invoked partway through the parent's
1542          * preprocess_expression() work, earlier steps of preprocess_expression()
1543          * wouldn't get applied to the pulled-up stuff unless we do them here. For
1544          * the parts of the WHERE clause that get put back into the child query,
1545          * this work is partially duplicative, but it shouldn't hurt.
1546          *
1547          * Note: we do not run flatten_join_alias_vars.  This is OK because any
1548          * parent aliases were flattened already, and we're not going to pull any
1549          * child Vars (of any description) into the parent.
1550          *
1551          * Note: passing the parent's root to eval_const_expressions is
1552          * technically wrong, but we can get away with it since only the
1553          * boundParams (if any) are used, and those would be the same in a
1554          * subroot.
1555          */
1556         whereClause = eval_const_expressions(root, whereClause);
1557         whereClause = (Node *) canonicalize_qual((Expr *) whereClause);
1558         whereClause = (Node *) make_ands_implicit((Expr *) whereClause);
1559
1560         /*
1561          * We now have a flattened implicit-AND list of clauses, which we try to
1562          * break apart into "outervar = innervar" hash clauses. Anything that
1563          * can't be broken apart just goes back into the newWhere list.  Note that
1564          * we aren't trying hard yet to ensure that we have only outer or only
1565          * inner on each side; we'll check that if we get to the end.
1566          */
1567         leftargs = rightargs = opids = opcollations = newWhere = NIL;
1568         foreach(lc, (List *) whereClause)
1569         {
1570                 OpExpr     *expr = (OpExpr *) lfirst(lc);
1571
1572                 if (IsA(expr, OpExpr) &&
1573                         hash_ok_operator(expr))
1574                 {
1575                         Node       *leftarg = (Node *) linitial(expr->args);
1576                         Node       *rightarg = (Node *) lsecond(expr->args);
1577
1578                         if (contain_vars_of_level(leftarg, 1))
1579                         {
1580                                 leftargs = lappend(leftargs, leftarg);
1581                                 rightargs = lappend(rightargs, rightarg);
1582                                 opids = lappend_oid(opids, expr->opno);
1583                                 opcollations = lappend_oid(opcollations, expr->inputcollid);
1584                                 continue;
1585                         }
1586                         if (contain_vars_of_level(rightarg, 1))
1587                         {
1588                                 /*
1589                                  * We must commute the clause to put the outer var on the
1590                                  * left, because the hashing code in nodeSubplan.c expects
1591                                  * that.  This probably shouldn't ever fail, since hashable
1592                                  * operators ought to have commutators, but be paranoid.
1593                                  */
1594                                 expr->opno = get_commutator(expr->opno);
1595                                 if (OidIsValid(expr->opno) && hash_ok_operator(expr))
1596                                 {
1597                                         leftargs = lappend(leftargs, rightarg);
1598                                         rightargs = lappend(rightargs, leftarg);
1599                                         opids = lappend_oid(opids, expr->opno);
1600                                         opcollations = lappend_oid(opcollations, expr->inputcollid);
1601                                         continue;
1602                                 }
1603                                 /* If no commutator, no chance to optimize the WHERE clause */
1604                                 return NULL;
1605                         }
1606                 }
1607                 /* Couldn't handle it as a hash clause */
1608                 newWhere = lappend(newWhere, expr);
1609         }
1610
1611         /*
1612          * If we didn't find anything we could convert, fail.
1613          */
1614         if (leftargs == NIL)
1615                 return NULL;
1616
1617         /*
1618          * There mustn't be any parent Vars or Aggs in the stuff that we intend to
1619          * put back into the child query.  Note: you might think we don't need to
1620          * check for Aggs separately, because an uplevel Agg must contain an
1621          * uplevel Var in its argument.  But it is possible that the uplevel Var
1622          * got optimized away by eval_const_expressions.  Consider
1623          *
1624          * SUM(CASE WHEN false THEN uplevelvar ELSE 0 END)
1625          */
1626         if (contain_vars_of_level((Node *) newWhere, 1) ||
1627                 contain_vars_of_level((Node *) rightargs, 1))
1628                 return NULL;
1629         if (root->parse->hasAggs &&
1630                 (contain_aggs_of_level((Node *) newWhere, 1) ||
1631                  contain_aggs_of_level((Node *) rightargs, 1)))
1632                 return NULL;
1633
1634         /*
1635          * And there can't be any child Vars in the stuff we intend to pull up.
1636          * (Note: we'd need to check for child Aggs too, except we know the child
1637          * has no aggs at all because of simplify_EXISTS_query's check. The same
1638          * goes for window functions.)
1639          */
1640         if (contain_vars_of_level((Node *) leftargs, 0))
1641                 return NULL;
1642
1643         /*
1644          * Also reject sublinks in the stuff we intend to pull up.      (It might be
1645          * possible to support this, but doesn't seem worth the complication.)
1646          */
1647         if (contain_subplans((Node *) leftargs))
1648                 return NULL;
1649
1650         /*
1651          * Okay, adjust the sublevelsup in the stuff we're pulling up.
1652          */
1653         IncrementVarSublevelsUp((Node *) leftargs, -1, 1);
1654
1655         /*
1656          * Put back any child-level-only WHERE clauses.
1657          */
1658         if (newWhere)
1659                 subselect->jointree->quals = (Node *) make_ands_explicit(newWhere);
1660
1661         /*
1662          * Build a new targetlist for the child that emits the expressions we
1663          * need.  Concurrently, build a testexpr for the parent using Params to
1664          * reference the child outputs.  (Since we generate Params directly here,
1665          * there will be no need to convert the testexpr in build_subplan.)
1666          */
1667         tlist = testlist = paramids = NIL;
1668         resno = 1;
1669         /* there's no "forfour" so we have to chase one of the lists manually */
1670         cc = list_head(opcollations);
1671         forthree(lc, leftargs, rc, rightargs, oc, opids)
1672         {
1673                 Node       *leftarg = (Node *) lfirst(lc);
1674                 Node       *rightarg = (Node *) lfirst(rc);
1675                 Oid                     opid = lfirst_oid(oc);
1676                 Oid                     opcollation = lfirst_oid(cc);
1677                 Param      *param;
1678
1679                 cc = lnext(cc);
1680                 param = generate_new_param(root,
1681                                                                    exprType(rightarg),
1682                                                                    exprTypmod(rightarg),
1683                                                                    exprCollation(rightarg));
1684                 tlist = lappend(tlist,
1685                                                 makeTargetEntry((Expr *) rightarg,
1686                                                                                 resno++,
1687                                                                                 NULL,
1688                                                                                 false));
1689                 testlist = lappend(testlist,
1690                                                    make_opclause(opid, BOOLOID, false,
1691                                                                                  (Expr *) leftarg, (Expr *) param,
1692                                                                                  InvalidOid, opcollation));
1693                 paramids = lappend_int(paramids, param->paramid);
1694         }
1695
1696         /* Put everything where it should go, and we're done */
1697         subselect->targetList = tlist;
1698         *testexpr = (Node *) make_ands_explicit(testlist);
1699         *paramIds = paramids;
1700
1701         return subselect;
1702 }
1703
1704
1705 /*
1706  * Replace correlation vars (uplevel vars) with Params.
1707  *
1708  * Uplevel PlaceHolderVars and aggregates are replaced, too.
1709  *
1710  * Note: it is critical that this runs immediately after SS_process_sublinks.
1711  * Since we do not recurse into the arguments of uplevel PHVs and aggregates,
1712  * they will get copied to the appropriate subplan args list in the parent
1713  * query with uplevel vars not replaced by Params, but only adjusted in level
1714  * (see replace_outer_placeholdervar and replace_outer_agg).  That's exactly
1715  * what we want for the vars of the parent level --- but if a PHV's or
1716  * aggregate's argument contains any further-up variables, they have to be
1717  * replaced with Params in their turn. That will happen when the parent level
1718  * runs SS_replace_correlation_vars.  Therefore it must do so after expanding
1719  * its sublinks to subplans.  And we don't want any steps in between, else
1720  * those steps would never get applied to the argument expressions, either in
1721  * the parent or the child level.
1722  *
1723  * Another fairly tricky thing going on here is the handling of SubLinks in
1724  * the arguments of uplevel PHVs/aggregates.  Those are not touched inside the
1725  * intermediate query level, either.  Instead, SS_process_sublinks recurses on
1726  * them after copying the PHV or Aggref expression into the parent plan level
1727  * (this is actually taken care of in build_subplan).
1728  */
1729 Node *
1730 SS_replace_correlation_vars(PlannerInfo *root, Node *expr)
1731 {
1732         /* No setup needed for tree walk, so away we go */
1733         return replace_correlation_vars_mutator(expr, root);
1734 }
1735
1736 static Node *
1737 replace_correlation_vars_mutator(Node *node, PlannerInfo *root)
1738 {
1739         if (node == NULL)
1740                 return NULL;
1741         if (IsA(node, Var))
1742         {
1743                 if (((Var *) node)->varlevelsup > 0)
1744                         return (Node *) replace_outer_var(root, (Var *) node);
1745         }
1746         if (IsA(node, PlaceHolderVar))
1747         {
1748                 if (((PlaceHolderVar *) node)->phlevelsup > 0)
1749                         return (Node *) replace_outer_placeholdervar(root,
1750                                                                                                         (PlaceHolderVar *) node);
1751         }
1752         if (IsA(node, Aggref))
1753         {
1754                 if (((Aggref *) node)->agglevelsup > 0)
1755                         return (Node *) replace_outer_agg(root, (Aggref *) node);
1756         }
1757         return expression_tree_mutator(node,
1758                                                                    replace_correlation_vars_mutator,
1759                                                                    (void *) root);
1760 }
1761
1762 /*
1763  * Expand SubLinks to SubPlans in the given expression.
1764  *
1765  * The isQual argument tells whether or not this expression is a WHERE/HAVING
1766  * qualifier expression.  If it is, any sublinks appearing at top level need
1767  * not distinguish FALSE from UNKNOWN return values.
1768  */
1769 Node *
1770 SS_process_sublinks(PlannerInfo *root, Node *expr, bool isQual)
1771 {
1772         process_sublinks_context context;
1773
1774         context.root = root;
1775         context.isTopQual = isQual;
1776         return process_sublinks_mutator(expr, &context);
1777 }
1778
1779 static Node *
1780 process_sublinks_mutator(Node *node, process_sublinks_context *context)
1781 {
1782         process_sublinks_context locContext;
1783
1784         locContext.root = context->root;
1785
1786         if (node == NULL)
1787                 return NULL;
1788         if (IsA(node, SubLink))
1789         {
1790                 SubLink    *sublink = (SubLink *) node;
1791                 Node       *testexpr;
1792
1793                 /*
1794                  * First, recursively process the lefthand-side expressions, if any.
1795                  * They're not top-level anymore.
1796                  */
1797                 locContext.isTopQual = false;
1798                 testexpr = process_sublinks_mutator(sublink->testexpr, &locContext);
1799
1800                 /*
1801                  * Now build the SubPlan node and make the expr to return.
1802                  */
1803                 return make_subplan(context->root,
1804                                                         (Query *) sublink->subselect,
1805                                                         sublink->subLinkType,
1806                                                         testexpr,
1807                                                         context->isTopQual);
1808         }
1809
1810         /*
1811          * Don't recurse into the arguments of an outer PHV or aggregate here. Any
1812          * SubLinks in the arguments have to be dealt with at the outer query
1813          * level; they'll be handled when build_subplan collects the PHV or Aggref
1814          * into the arguments to be passed down to the current subplan.
1815          */
1816         if (IsA(node, PlaceHolderVar))
1817         {
1818                 if (((PlaceHolderVar *) node)->phlevelsup > 0)
1819                         return node;
1820         }
1821         else if (IsA(node, Aggref))
1822         {
1823                 if (((Aggref *) node)->agglevelsup > 0)
1824                         return node;
1825         }
1826
1827         /*
1828          * We should never see a SubPlan expression in the input (since this is
1829          * the very routine that creates 'em to begin with).  We shouldn't find
1830          * ourselves invoked directly on a Query, either.
1831          */
1832         Assert(!IsA(node, SubPlan));
1833         Assert(!IsA(node, AlternativeSubPlan));
1834         Assert(!IsA(node, Query));
1835
1836         /*
1837          * Because make_subplan() could return an AND or OR clause, we have to
1838          * take steps to preserve AND/OR flatness of a qual.  We assume the input
1839          * has been AND/OR flattened and so we need no recursion here.
1840          *
1841          * (Due to the coding here, we will not get called on the List subnodes of
1842          * an AND; and the input is *not* yet in implicit-AND format.  So no check
1843          * is needed for a bare List.)
1844          *
1845          * Anywhere within the top-level AND/OR clause structure, we can tell
1846          * make_subplan() that NULL and FALSE are interchangeable.      So isTopQual
1847          * propagates down in both cases.  (Note that this is unlike the meaning
1848          * of "top level qual" used in most other places in Postgres.)
1849          */
1850         if (and_clause(node))
1851         {
1852                 List       *newargs = NIL;
1853                 ListCell   *l;
1854
1855                 /* Still at qual top-level */
1856                 locContext.isTopQual = context->isTopQual;
1857
1858                 foreach(l, ((BoolExpr *) node)->args)
1859                 {
1860                         Node       *newarg;
1861
1862                         newarg = process_sublinks_mutator(lfirst(l), &locContext);
1863                         if (and_clause(newarg))
1864                                 newargs = list_concat(newargs, ((BoolExpr *) newarg)->args);
1865                         else
1866                                 newargs = lappend(newargs, newarg);
1867                 }
1868                 return (Node *) make_andclause(newargs);
1869         }
1870
1871         if (or_clause(node))
1872         {
1873                 List       *newargs = NIL;
1874                 ListCell   *l;
1875
1876                 /* Still at qual top-level */
1877                 locContext.isTopQual = context->isTopQual;
1878
1879                 foreach(l, ((BoolExpr *) node)->args)
1880                 {
1881                         Node       *newarg;
1882
1883                         newarg = process_sublinks_mutator(lfirst(l), &locContext);
1884                         if (or_clause(newarg))
1885                                 newargs = list_concat(newargs, ((BoolExpr *) newarg)->args);
1886                         else
1887                                 newargs = lappend(newargs, newarg);
1888                 }
1889                 return (Node *) make_orclause(newargs);
1890         }
1891
1892         /*
1893          * If we recurse down through anything other than an AND or OR node, we
1894          * are definitely not at top qual level anymore.
1895          */
1896         locContext.isTopQual = false;
1897
1898         return expression_tree_mutator(node,
1899                                                                    process_sublinks_mutator,
1900                                                                    (void *) &locContext);
1901 }
1902
1903 /*
1904  * SS_finalize_plan - do final sublink and parameter processing for a
1905  * completed Plan.
1906  *
1907  * This recursively computes the extParam and allParam sets for every Plan
1908  * node in the given plan tree.  It also optionally attaches any previously
1909  * generated InitPlans to the top plan node.  (Any InitPlans should already
1910  * have been put through SS_finalize_plan.)
1911  */
1912 void
1913 SS_finalize_plan(PlannerInfo *root, Plan *plan, bool attach_initplans)
1914 {
1915         Bitmapset  *valid_params,
1916                            *initExtParam,
1917                            *initSetParam;
1918         Cost            initplan_cost;
1919         PlannerInfo *proot;
1920         ListCell   *l;
1921
1922         /*
1923          * Examine any initPlans to determine the set of external params they
1924          * reference, the set of output params they supply, and their total cost.
1925          * We'll use at least some of this info below.  (Note we are assuming that
1926          * finalize_plan doesn't touch the initPlans.)
1927          *
1928          * In the case where attach_initplans is false, we are assuming that the
1929          * existing initPlans are siblings that might supply params needed by the
1930          * current plan.
1931          */
1932         initExtParam = initSetParam = NULL;
1933         initplan_cost = 0;
1934         foreach(l, root->init_plans)
1935         {
1936                 SubPlan    *initsubplan = (SubPlan *) lfirst(l);
1937                 Plan       *initplan = planner_subplan_get_plan(root, initsubplan);
1938                 ListCell   *l2;
1939
1940                 initExtParam = bms_add_members(initExtParam, initplan->extParam);
1941                 foreach(l2, initsubplan->setParam)
1942                 {
1943                         initSetParam = bms_add_member(initSetParam, lfirst_int(l2));
1944                 }
1945                 initplan_cost += initsubplan->startup_cost + initsubplan->per_call_cost;
1946         }
1947
1948         /*
1949          * Now determine the set of params that are validly referenceable in this
1950          * query level; to wit, those available from outer query levels plus the
1951          * output parameters of any local initPlans.  (We do not include output
1952          * parameters of regular subplans.      Those should only appear within the
1953          * testexpr of SubPlan nodes, and are taken care of locally within
1954          * finalize_primnode.  Likewise, special parameters that are generated by
1955          * nodes such as ModifyTable are handled within finalize_plan.)
1956          */
1957         valid_params = bms_copy(initSetParam);
1958         for (proot = root->parent_root; proot != NULL; proot = proot->parent_root)
1959         {
1960                 /* Include ordinary Var/PHV/Aggref params */
1961                 foreach(l, proot->plan_params)
1962                 {
1963                         PlannerParamItem *pitem = (PlannerParamItem *) lfirst(l);
1964
1965                         valid_params = bms_add_member(valid_params, pitem->paramId);
1966                 }
1967                 /* Include any outputs of outer-level initPlans */
1968                 foreach(l, proot->init_plans)
1969                 {
1970                         SubPlan    *initsubplan = (SubPlan *) lfirst(l);
1971                         ListCell   *l2;
1972
1973                         foreach(l2, initsubplan->setParam)
1974                         {
1975                                 valid_params = bms_add_member(valid_params, lfirst_int(l2));
1976                         }
1977                 }
1978                 /* Include worktable ID, if a recursive query is being planned */
1979                 if (proot->wt_param_id >= 0)
1980                         valid_params = bms_add_member(valid_params, proot->wt_param_id);
1981         }
1982
1983         /*
1984          * Now recurse through plan tree.
1985          */
1986         (void) finalize_plan(root, plan, valid_params, NULL);
1987
1988         bms_free(valid_params);
1989
1990         /*
1991          * Finally, attach any initPlans to the topmost plan node, and add their
1992          * extParams to the topmost node's, too.  However, any setParams of the
1993          * initPlans should not be present in the topmost node's extParams, only
1994          * in its allParams.  (As of PG 8.1, it's possible that some initPlans
1995          * have extParams that are setParams of other initPlans, so we have to
1996          * take care of this situation explicitly.)
1997          *
1998          * We also add the eval cost of each initPlan to the startup cost of the
1999          * top node.  This is a conservative overestimate, since in fact each
2000          * initPlan might be executed later than plan startup, or even not at all.
2001          */
2002         if (attach_initplans)
2003         {
2004                 plan->initPlan = root->init_plans;
2005                 root->init_plans = NIL; /* make sure they're not attached twice */
2006
2007                 /* allParam must include all these params */
2008                 plan->allParam = bms_add_members(plan->allParam, initExtParam);
2009                 plan->allParam = bms_add_members(plan->allParam, initSetParam);
2010                 /* extParam must include any child extParam */
2011                 plan->extParam = bms_add_members(plan->extParam, initExtParam);
2012                 /* but extParam shouldn't include any setParams */
2013                 plan->extParam = bms_del_members(plan->extParam, initSetParam);
2014                 /* ensure extParam is exactly NULL if it's empty */
2015                 if (bms_is_empty(plan->extParam))
2016                         plan->extParam = NULL;
2017
2018                 plan->startup_cost += initplan_cost;
2019                 plan->total_cost += initplan_cost;
2020         }
2021 }
2022
2023 /*
2024  * Recursive processing of all nodes in the plan tree
2025  *
2026  * valid_params is the set of param IDs considered valid to reference in
2027  * this plan node or its children.
2028  * scan_params is a set of param IDs to force scan plan nodes to reference.
2029  * This is for EvalPlanQual support, and is always NULL at the top of the
2030  * recursion.
2031  *
2032  * The return value is the computed allParam set for the given Plan node.
2033  * This is just an internal notational convenience.
2034  */
2035 static Bitmapset *
2036 finalize_plan(PlannerInfo *root, Plan *plan, Bitmapset *valid_params,
2037                           Bitmapset *scan_params)
2038 {
2039         finalize_primnode_context context;
2040         int                     locally_added_param;
2041         Bitmapset  *nestloop_params;
2042         Bitmapset  *child_params;
2043
2044         if (plan == NULL)
2045                 return NULL;
2046
2047         context.root = root;
2048         context.paramids = NULL;        /* initialize set to empty */
2049         locally_added_param = -1;       /* there isn't one */
2050         nestloop_params = NULL;         /* there aren't any */
2051
2052         /*
2053          * When we call finalize_primnode, context.paramids sets are automatically
2054          * merged together.  But when recursing to self, we have to do it the hard
2055          * way.  We want the paramids set to include params in subplans as well as
2056          * at this level.
2057          */
2058
2059         /* Find params in targetlist and qual */
2060         finalize_primnode((Node *) plan->targetlist, &context);
2061         finalize_primnode((Node *) plan->qual, &context);
2062
2063         /* Check additional node-type-specific fields */
2064         switch (nodeTag(plan))
2065         {
2066                 case T_Result:
2067                         finalize_primnode(((Result *) plan)->resconstantqual,
2068                                                           &context);
2069                         break;
2070
2071                 case T_SeqScan:
2072                         context.paramids = bms_add_members(context.paramids, scan_params);
2073                         break;
2074
2075                 case T_IndexScan:
2076                         finalize_primnode((Node *) ((IndexScan *) plan)->indexqual,
2077                                                           &context);
2078                         finalize_primnode((Node *) ((IndexScan *) plan)->indexorderby,
2079                                                           &context);
2080
2081                         /*
2082                          * we need not look at indexqualorig, since it will have the same
2083                          * param references as indexqual.  Likewise, we can ignore
2084                          * indexorderbyorig.
2085                          */
2086                         context.paramids = bms_add_members(context.paramids, scan_params);
2087                         break;
2088
2089                 case T_IndexOnlyScan:
2090                         finalize_primnode((Node *) ((IndexOnlyScan *) plan)->indexqual,
2091                                                           &context);
2092                         finalize_primnode((Node *) ((IndexOnlyScan *) plan)->indexorderby,
2093                                                           &context);
2094
2095                         /*
2096                          * we need not look at indextlist, since it cannot contain Params.
2097                          */
2098                         context.paramids = bms_add_members(context.paramids, scan_params);
2099                         break;
2100
2101                 case T_BitmapIndexScan:
2102                         finalize_primnode((Node *) ((BitmapIndexScan *) plan)->indexqual,
2103                                                           &context);
2104
2105                         /*
2106                          * we need not look at indexqualorig, since it will have the same
2107                          * param references as indexqual.
2108                          */
2109                         break;
2110
2111                 case T_BitmapHeapScan:
2112                         finalize_primnode((Node *) ((BitmapHeapScan *) plan)->bitmapqualorig,
2113                                                           &context);
2114                         context.paramids = bms_add_members(context.paramids, scan_params);
2115                         break;
2116
2117                 case T_TidScan:
2118                         finalize_primnode((Node *) ((TidScan *) plan)->tidquals,
2119                                                           &context);
2120                         context.paramids = bms_add_members(context.paramids, scan_params);
2121                         break;
2122
2123                 case T_SubqueryScan:
2124
2125                         /*
2126                          * In a SubqueryScan, SS_finalize_plan has already been run on the
2127                          * subplan by the inner invocation of subquery_planner, so there's
2128                          * no need to do it again.      Instead, just pull out the subplan's
2129                          * extParams list, which represents the params it needs from my
2130                          * level and higher levels.
2131                          */
2132                         context.paramids = bms_add_members(context.paramids,
2133                                                                  ((SubqueryScan *) plan)->subplan->extParam);
2134                         /* We need scan_params too, though */
2135                         context.paramids = bms_add_members(context.paramids, scan_params);
2136                         break;
2137
2138                 case T_FunctionScan:
2139                         finalize_primnode(((FunctionScan *) plan)->funcexpr,
2140                                                           &context);
2141                         context.paramids = bms_add_members(context.paramids, scan_params);
2142                         break;
2143
2144                 case T_ValuesScan:
2145                         finalize_primnode((Node *) ((ValuesScan *) plan)->values_lists,
2146                                                           &context);
2147                         context.paramids = bms_add_members(context.paramids, scan_params);
2148                         break;
2149
2150                 case T_CteScan:
2151                         {
2152                                 /*
2153                                  * You might think we should add the node's cteParam to
2154                                  * paramids, but we shouldn't because that param is just a
2155                                  * linkage mechanism for multiple CteScan nodes for the same
2156                                  * CTE; it is never used for changed-param signaling.  What we
2157                                  * have to do instead is to find the referenced CTE plan and
2158                                  * incorporate its external paramids, so that the correct
2159                                  * things will happen if the CTE references outer-level
2160                                  * variables.  See test cases for bug #4902.
2161                                  */
2162                                 int                     plan_id = ((CteScan *) plan)->ctePlanId;
2163                                 Plan       *cteplan;
2164
2165                                 /* so, do this ... */
2166                                 if (plan_id < 1 || plan_id > list_length(root->glob->subplans))
2167                                         elog(ERROR, "could not find plan for CteScan referencing plan ID %d",
2168                                                  plan_id);
2169                                 cteplan = (Plan *) list_nth(root->glob->subplans, plan_id - 1);
2170                                 context.paramids =
2171                                         bms_add_members(context.paramids, cteplan->extParam);
2172
2173 #ifdef NOT_USED
2174                                 /* ... but not this */
2175                                 context.paramids =
2176                                         bms_add_member(context.paramids,
2177                                                                    ((CteScan *) plan)->cteParam);
2178 #endif
2179
2180                                 context.paramids = bms_add_members(context.paramids,
2181                                                                                                    scan_params);
2182                         }
2183                         break;
2184
2185                 case T_WorkTableScan:
2186                         context.paramids =
2187                                 bms_add_member(context.paramids,
2188                                                            ((WorkTableScan *) plan)->wtParam);
2189                         context.paramids = bms_add_members(context.paramids, scan_params);
2190                         break;
2191
2192                 case T_ForeignScan:
2193                         finalize_primnode((Node *) ((ForeignScan *) plan)->fdw_exprs,
2194                                                           &context);
2195                         context.paramids = bms_add_members(context.paramids, scan_params);
2196                         break;
2197
2198                 case T_ModifyTable:
2199                         {
2200                                 ModifyTable *mtplan = (ModifyTable *) plan;
2201                                 ListCell   *l;
2202
2203                                 /* Force descendant scan nodes to reference epqParam */
2204                                 locally_added_param = mtplan->epqParam;
2205                                 valid_params = bms_add_member(bms_copy(valid_params),
2206                                                                                           locally_added_param);
2207                                 scan_params = bms_add_member(bms_copy(scan_params),
2208                                                                                          locally_added_param);
2209                                 finalize_primnode((Node *) mtplan->returningLists,
2210                                                                   &context);
2211                                 foreach(l, mtplan->plans)
2212                                 {
2213                                         context.paramids =
2214                                                 bms_add_members(context.paramids,
2215                                                                                 finalize_plan(root,
2216                                                                                                           (Plan *) lfirst(l),
2217                                                                                                           valid_params,
2218                                                                                                           scan_params));
2219                                 }
2220                         }
2221                         break;
2222
2223                 case T_Append:
2224                         {
2225                                 ListCell   *l;
2226
2227                                 foreach(l, ((Append *) plan)->appendplans)
2228                                 {
2229                                         context.paramids =
2230                                                 bms_add_members(context.paramids,
2231                                                                                 finalize_plan(root,
2232                                                                                                           (Plan *) lfirst(l),
2233                                                                                                           valid_params,
2234                                                                                                           scan_params));
2235                                 }
2236                         }
2237                         break;
2238
2239                 case T_MergeAppend:
2240                         {
2241                                 ListCell   *l;
2242
2243                                 foreach(l, ((MergeAppend *) plan)->mergeplans)
2244                                 {
2245                                         context.paramids =
2246                                                 bms_add_members(context.paramids,
2247                                                                                 finalize_plan(root,
2248                                                                                                           (Plan *) lfirst(l),
2249                                                                                                           valid_params,
2250                                                                                                           scan_params));
2251                                 }
2252                         }
2253                         break;
2254
2255                 case T_BitmapAnd:
2256                         {
2257                                 ListCell   *l;
2258
2259                                 foreach(l, ((BitmapAnd *) plan)->bitmapplans)
2260                                 {
2261                                         context.paramids =
2262                                                 bms_add_members(context.paramids,
2263                                                                                 finalize_plan(root,
2264                                                                                                           (Plan *) lfirst(l),
2265                                                                                                           valid_params,
2266                                                                                                           scan_params));
2267                                 }
2268                         }
2269                         break;
2270
2271                 case T_BitmapOr:
2272                         {
2273                                 ListCell   *l;
2274
2275                                 foreach(l, ((BitmapOr *) plan)->bitmapplans)
2276                                 {
2277                                         context.paramids =
2278                                                 bms_add_members(context.paramids,
2279                                                                                 finalize_plan(root,
2280                                                                                                           (Plan *) lfirst(l),
2281                                                                                                           valid_params,
2282                                                                                                           scan_params));
2283                                 }
2284                         }
2285                         break;
2286
2287                 case T_NestLoop:
2288                         {
2289                                 ListCell   *l;
2290
2291                                 finalize_primnode((Node *) ((Join *) plan)->joinqual,
2292                                                                   &context);
2293                                 /* collect set of params that will be passed to right child */
2294                                 foreach(l, ((NestLoop *) plan)->nestParams)
2295                                 {
2296                                         NestLoopParam *nlp = (NestLoopParam *) lfirst(l);
2297
2298                                         nestloop_params = bms_add_member(nestloop_params,
2299                                                                                                          nlp->paramno);
2300                                 }
2301                         }
2302                         break;
2303
2304                 case T_MergeJoin:
2305                         finalize_primnode((Node *) ((Join *) plan)->joinqual,
2306                                                           &context);
2307                         finalize_primnode((Node *) ((MergeJoin *) plan)->mergeclauses,
2308                                                           &context);
2309                         break;
2310
2311                 case T_HashJoin:
2312                         finalize_primnode((Node *) ((Join *) plan)->joinqual,
2313                                                           &context);
2314                         finalize_primnode((Node *) ((HashJoin *) plan)->hashclauses,
2315                                                           &context);
2316                         break;
2317
2318                 case T_Limit:
2319                         finalize_primnode(((Limit *) plan)->limitOffset,
2320                                                           &context);
2321                         finalize_primnode(((Limit *) plan)->limitCount,
2322                                                           &context);
2323                         break;
2324
2325                 case T_RecursiveUnion:
2326                         /* child nodes are allowed to reference wtParam */
2327                         locally_added_param = ((RecursiveUnion *) plan)->wtParam;
2328                         valid_params = bms_add_member(bms_copy(valid_params),
2329                                                                                   locally_added_param);
2330                         /* wtParam does *not* get added to scan_params */
2331                         break;
2332
2333                 case T_LockRows:
2334                         /* Force descendant scan nodes to reference epqParam */
2335                         locally_added_param = ((LockRows *) plan)->epqParam;
2336                         valid_params = bms_add_member(bms_copy(valid_params),
2337                                                                                   locally_added_param);
2338                         scan_params = bms_add_member(bms_copy(scan_params),
2339                                                                                  locally_added_param);
2340                         break;
2341
2342                 case T_WindowAgg:
2343                         finalize_primnode(((WindowAgg *) plan)->startOffset,
2344                                                           &context);
2345                         finalize_primnode(((WindowAgg *) plan)->endOffset,
2346                                                           &context);
2347                         break;
2348
2349                 case T_Hash:
2350                 case T_Agg:
2351                 case T_Material:
2352                 case T_Sort:
2353                 case T_Unique:
2354                 case T_SetOp:
2355                 case T_Group:
2356                         break;
2357
2358                 default:
2359                         elog(ERROR, "unrecognized node type: %d",
2360                                  (int) nodeTag(plan));
2361         }
2362
2363         /* Process left and right child plans, if any */
2364         child_params = finalize_plan(root,
2365                                                                  plan->lefttree,
2366                                                                  valid_params,
2367                                                                  scan_params);
2368         context.paramids = bms_add_members(context.paramids, child_params);
2369
2370         if (nestloop_params)
2371         {
2372                 /* right child can reference nestloop_params as well as valid_params */
2373                 child_params = finalize_plan(root,
2374                                                                          plan->righttree,
2375                                                                          bms_union(nestloop_params, valid_params),
2376                                                                          scan_params);
2377                 /* ... and they don't count as parameters used at my level */
2378                 child_params = bms_difference(child_params, nestloop_params);
2379                 bms_free(nestloop_params);
2380         }
2381         else
2382         {
2383                 /* easy case */
2384                 child_params = finalize_plan(root,
2385                                                                          plan->righttree,
2386                                                                          valid_params,
2387                                                                          scan_params);
2388         }
2389         context.paramids = bms_add_members(context.paramids, child_params);
2390
2391         /*
2392          * Any locally generated parameter doesn't count towards its generating
2393          * plan node's external dependencies.  (Note: if we changed valid_params
2394          * and/or scan_params, we leak those bitmapsets; not worth the notational
2395          * trouble to clean them up.)
2396          */
2397         if (locally_added_param >= 0)
2398         {
2399                 context.paramids = bms_del_member(context.paramids,
2400                                                                                   locally_added_param);
2401         }
2402
2403         /* Now we have all the paramids */
2404
2405         if (!bms_is_subset(context.paramids, valid_params))
2406                 elog(ERROR, "plan should not reference subplan's variable");
2407
2408         /*
2409          * Note: by definition, extParam and allParam should have the same value
2410          * in any plan node that doesn't have child initPlans.  We set them equal
2411          * here, and later SS_finalize_plan will update them properly in node(s)
2412          * that it attaches initPlans to.
2413          *
2414          * For speed at execution time, make sure extParam/allParam are actually
2415          * NULL if they are empty sets.
2416          */
2417         if (bms_is_empty(context.paramids))
2418         {
2419                 plan->extParam = NULL;
2420                 plan->allParam = NULL;
2421         }
2422         else
2423         {
2424                 plan->extParam = context.paramids;
2425                 plan->allParam = bms_copy(context.paramids);
2426         }
2427
2428         return plan->allParam;
2429 }
2430
2431 /*
2432  * finalize_primnode: add IDs of all PARAM_EXEC params appearing in the given
2433  * expression tree to the result set.
2434  */
2435 static bool
2436 finalize_primnode(Node *node, finalize_primnode_context *context)
2437 {
2438         if (node == NULL)
2439                 return false;
2440         if (IsA(node, Param))
2441         {
2442                 if (((Param *) node)->paramkind == PARAM_EXEC)
2443                 {
2444                         int                     paramid = ((Param *) node)->paramid;
2445
2446                         context->paramids = bms_add_member(context->paramids, paramid);
2447                 }
2448                 return false;                   /* no more to do here */
2449         }
2450         if (IsA(node, SubPlan))
2451         {
2452                 SubPlan    *subplan = (SubPlan *) node;
2453                 Plan       *plan = planner_subplan_get_plan(context->root, subplan);
2454                 ListCell   *lc;
2455                 Bitmapset  *subparamids;
2456
2457                 /* Recurse into the testexpr, but not into the Plan */
2458                 finalize_primnode(subplan->testexpr, context);
2459
2460                 /*
2461                  * Remove any param IDs of output parameters of the subplan that were
2462                  * referenced in the testexpr.  These are not interesting for
2463                  * parameter change signaling since we always re-evaluate the subplan.
2464                  * Note that this wouldn't work too well if there might be uses of the
2465                  * same param IDs elsewhere in the plan, but that can't happen because
2466                  * generate_new_param never tries to merge params.
2467                  */
2468                 foreach(lc, subplan->paramIds)
2469                 {
2470                         context->paramids = bms_del_member(context->paramids,
2471                                                                                            lfirst_int(lc));
2472                 }
2473
2474                 /* Also examine args list */
2475                 finalize_primnode((Node *) subplan->args, context);
2476
2477                 /*
2478                  * Add params needed by the subplan to paramids, but excluding those
2479                  * we will pass down to it.
2480                  */
2481                 subparamids = bms_copy(plan->extParam);
2482                 foreach(lc, subplan->parParam)
2483                 {
2484                         subparamids = bms_del_member(subparamids, lfirst_int(lc));
2485                 }
2486                 context->paramids = bms_join(context->paramids, subparamids);
2487
2488                 return false;                   /* no more to do here */
2489         }
2490         return expression_tree_walker(node, finalize_primnode,
2491                                                                   (void *) context);
2492 }
2493
2494 /*
2495  * SS_make_initplan_from_plan - given a plan tree, make it an InitPlan
2496  *
2497  * The plan is expected to return a scalar value of the given type/collation.
2498  * We build an EXPR_SUBLINK SubPlan node and put it into the initplan
2499  * list for the current query level.  A Param that represents the initplan's
2500  * output is returned.
2501  *
2502  * We assume the plan hasn't been put through SS_finalize_plan.
2503  */
2504 Param *
2505 SS_make_initplan_from_plan(PlannerInfo *root, Plan *plan,
2506                                                    Oid resulttype, int32 resulttypmod,
2507                                                    Oid resultcollation)
2508 {
2509         SubPlan    *node;
2510         Param      *prm;
2511
2512         /*
2513          * We must run SS_finalize_plan(), since that's normally done before a
2514          * subplan gets put into the initplan list.  Tell it not to attach any
2515          * pre-existing initplans to this one, since they are siblings not
2516          * children of this initplan.  (This is something else that could perhaps
2517          * be cleaner if we did extParam/allParam processing in setrefs.c instead
2518          * of here?  See notes for materialize_finished_plan.)
2519          */
2520
2521         /*
2522          * Build extParam/allParam sets for plan nodes.
2523          */
2524         SS_finalize_plan(root, plan, false);
2525
2526         /*
2527          * Add the subplan and its PlannerInfo to the global lists.
2528          */
2529         root->glob->subplans = lappend(root->glob->subplans, plan);
2530         root->glob->subroots = lappend(root->glob->subroots, root);
2531
2532         /*
2533          * Create a SubPlan node and add it to the outer list of InitPlans. Note
2534          * it has to appear after any other InitPlans it might depend on (see
2535          * comments in ExecReScan).
2536          */
2537         node = makeNode(SubPlan);
2538         node->subLinkType = EXPR_SUBLINK;
2539         get_first_col_type(plan, &node->firstColType, &node->firstColTypmod,
2540                                            &node->firstColCollation);
2541         node->plan_id = list_length(root->glob->subplans);
2542
2543         root->init_plans = lappend(root->init_plans, node);
2544
2545         /*
2546          * The node can't have any inputs (since it's an initplan), so the
2547          * parParam and args lists remain empty.
2548          */
2549
2550         cost_subplan(root, node, plan);
2551
2552         /*
2553          * Make a Param that will be the subplan's output.
2554          */
2555         prm = generate_new_param(root, resulttype, resulttypmod, resultcollation);
2556         node->setParam = list_make1_int(prm->paramid);
2557
2558         /* Label the subplan for EXPLAIN purposes */
2559         node->plan_name = palloc(64);
2560         sprintf(node->plan_name, "InitPlan %d (returns $%d)",
2561                         node->plan_id, prm->paramid);
2562
2563         return prm;
2564 }