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-2003, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  * IDENTIFICATION
  10  *        $PostgreSQL: pgsql/src/backend/optimizer/plan/subselect.c,v 1.87 2004/01/12 22:20:28 tgl Exp $
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #include "postgres.h"
  15
  16 #include "catalog/pg_operator.h"
  17 #include "catalog/pg_type.h"
  18 #include "miscadmin.h"
  19 #include "nodes/makefuncs.h"
  20 #include "nodes/params.h"
  21 #include "optimizer/clauses.h"
  22 #include "optimizer/cost.h"
  23 #include "optimizer/planmain.h"
  24 #include "optimizer/planner.h"
  25 #include "optimizer/subselect.h"
  26 #include "optimizer/var.h"
  27 #include "parser/parsetree.h"
  28 #include "parser/parse_expr.h"
  29 #include "parser/parse_oper.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 Index           PlannerQueryLevel;      /* level of current query */
  38 List       *PlannerInitPlan;    /* init subplans for current query */
  39 List       *PlannerParamList;   /* to keep track of cross-level Params */
  40
  41 int                     PlannerPlanId = 0;      /* to assign unique ID to subquery plans */
  42
  43 /*
  44  * PlannerParamList keeps track of the PARAM_EXEC slots that we have decided
  45  * we need for the query.  At runtime these slots are used to pass values
  46  * either down into subqueries (for outer references in subqueries) or up out
  47  * of subqueries (for the results of a subplan).  The n'th entry in the list
  48  * (n counts from 0) corresponds to Param->paramid = n.
  49  *
  50  * Each ParamList item shows the absolute query level it is associated with,
  51  * where the outermost query is level 1 and nested subqueries have higher
  52  * numbers.  The item the parameter slot represents can be one of three kinds:
  53  *
  54  * A Var: the slot represents a variable of that level that must be passed
  55  * down because subqueries have outer references to it.  The varlevelsup
  56  * value in the Var will always be zero.
  57  *
  58  * An Aggref (with an expression tree representing its argument): the slot
  59  * represents an aggregate expression that is an outer reference for some
  60  * subquery.  The Aggref itself has agglevelsup = 0, and its argument tree
  61  * is adjusted to match in level.
  62  *
  63  * A Param: the slot holds the result of a subplan (it is a setParam item
  64  * for that subplan).  The absolute level shown for such items corresponds
  65  * to the parent query of the subplan.
  66  *
  67  * Note: we detect duplicate Var parameters and coalesce them into one slot,
  68  * but we do not do this for Aggref or Param slots.
  69  */
  70 typedef struct PlannerParamItem
  71 {
  72         Node       *item;                       /* the Var, Aggref, or Param */
  73         Index           abslevel;               /* its absolute query level */
  74 } PlannerParamItem;
  75
  76
  77 typedef struct finalize_primnode_context
  78 {
  79         Bitmapset  *paramids;           /* Set of PARAM_EXEC paramids found */
  80         Bitmapset  *outer_params;       /* Set of accessible outer paramids */
  81 } finalize_primnode_context;
  82
  83
  84 static List *convert_sublink_opers(List *lefthand, List *operOids,
  85                                           List *targetlist, int rtindex,
  86                                           List **righthandIds);
  87 static bool subplan_is_hashable(SubLink *slink, SubPlan *node);
  88 static Node *replace_correlation_vars_mutator(Node *node, void *context);
  89 static Node *process_sublinks_mutator(Node *node, bool *isTopQual);
  90 static Bitmapset *finalize_plan(Plan *plan, List *rtable,
  91                           Bitmapset *outer_params,
  92                           Bitmapset *valid_params);
  93 static bool finalize_primnode(Node *node, finalize_primnode_context *context);
  94
  95
  96 /*
  97  * Generate a Param node to replace the given Var,
  98  * which is expected to have varlevelsup > 0 (ie, it is not local).
  99  */
 100 static Param *
 101 replace_outer_var(Var *var)
 102 {
 103         Param      *retval;
 104         List       *ppl;
 105         PlannerParamItem *pitem;
 106         Index           abslevel;
 107         int                     i;
 108
 109         Assert(var->varlevelsup > 0 && var->varlevelsup < PlannerQueryLevel);
 110         abslevel = PlannerQueryLevel - var->varlevelsup;
 111
 112         /*
 113          * If there's already a PlannerParamList entry for this same Var, just
 114          * use it.      NOTE: in sufficiently complex querytrees, it is possible
 115          * for the same varno/abslevel to refer to different RTEs in different
 116          * parts of the parsetree, so that different fields might end up
 117          * sharing the same Param number.  As long as we check the vartype as
 118          * well, I believe that this sort of aliasing will cause no trouble.
 119          * The correct field should get stored into the Param slot at
 120          * execution in each part of the tree.
 121          *
 122          * We also need to demand a match on vartypmod.  This does not matter
 123          * for the Param itself, since those are not typmod-dependent, but it
 124          * does matter when make_subplan() instantiates a modified copy of the
 125          * Var for a subplan's args list.
 126          */
 127         i = 0;
 128         foreach(ppl, PlannerParamList)
 129         {
 130                 pitem = (PlannerParamItem *) lfirst(ppl);
 131                 if (pitem->abslevel == abslevel && IsA(pitem->item, Var))
 132                 {
 133                         Var                *pvar = (Var *) pitem->item;
 134
 135                         if (pvar->varno == var->varno &&
 136                                 pvar->varattno == var->varattno &&
 137                                 pvar->vartype == var->vartype &&
 138                                 pvar->vartypmod == var->vartypmod)
 139                                 break;
 140                 }
 141                 i++;
 142         }
 143
 144         if (!ppl)
 145         {
 146                 /* Nope, so make a new one */
 147                 var = (Var *) copyObject(var);
 148                 var->varlevelsup = 0;
 149
 150                 pitem = (PlannerParamItem *) palloc(sizeof(PlannerParamItem));
 151                 pitem->item = (Node *) var;
 152                 pitem->abslevel = abslevel;
 153
 154                 PlannerParamList = lappend(PlannerParamList, pitem);
 155                 /* i is already the correct index for the new item */
 156         }
 157
 158         retval = makeNode(Param);
 159         retval->paramkind = PARAM_EXEC;
 160         retval->paramid = (AttrNumber) i;
 161         retval->paramtype = var->vartype;
 162
 163         return retval;
 164 }
 165
 166 /*
 167  * Generate a Param node to replace the given Aggref
 168  * which is expected to have agglevelsup > 0 (ie, it is not local).
 169  */
 170 static Param *
 171 replace_outer_agg(Aggref *agg)
 172 {
 173         Param      *retval;
 174         PlannerParamItem *pitem;
 175         Index           abslevel;
 176         int                     i;
 177
 178         Assert(agg->agglevelsup > 0 && agg->agglevelsup < PlannerQueryLevel);
 179         abslevel = PlannerQueryLevel - agg->agglevelsup;
 180
 181         /*
 182          * It does not seem worthwhile to try to match duplicate outer aggs.
 183          * Just make a new slot every time.
 184          */
 185         agg = (Aggref *) copyObject(agg);
 186         IncrementVarSublevelsUp((Node *) agg, -((int) agg->agglevelsup), 0);
 187         Assert(agg->agglevelsup == 0);
 188
 189         pitem = (PlannerParamItem *) palloc(sizeof(PlannerParamItem));
 190         pitem->item = (Node *) agg;
 191         pitem->abslevel = abslevel;
 192
 193         PlannerParamList = lappend(PlannerParamList, pitem);
 194         i = length(PlannerParamList) - 1;
 195
 196         retval = makeNode(Param);
 197         retval->paramkind = PARAM_EXEC;
 198         retval->paramid = (AttrNumber) i;
 199         retval->paramtype = agg->aggtype;
 200
 201         return retval;
 202 }
 203
 204 /*
 205  * Generate a new Param node that will not conflict with any other.
 206  *
 207  * This is used to allocate PARAM_EXEC slots for subplan outputs.
 208  *
 209  * paramtypmod is currently unused but might be wanted someday.
 210  */
 211 static Param *
 212 generate_new_param(Oid paramtype, int32 paramtypmod)
 213 {
 214         Param      *retval;
 215         PlannerParamItem *pitem;
 216
 217         retval = makeNode(Param);
 218         retval->paramkind = PARAM_EXEC;
 219         retval->paramid = (AttrNumber) length(PlannerParamList);
 220         retval->paramtype = paramtype;
 221
 222         pitem = (PlannerParamItem *) palloc(sizeof(PlannerParamItem));
 223         pitem->item = (Node *) retval;
 224         pitem->abslevel = PlannerQueryLevel;
 225
 226         PlannerParamList = lappend(PlannerParamList, pitem);
 227
 228         return retval;
 229 }
 230
 231 /*
 232  * Convert a bare SubLink (as created by the parser) into a SubPlan.
 233  *
 234  * We are given the raw SubLink and the already-processed lefthand argument
 235  * list (use this instead of the SubLink's own field).  We are also told if
 236  * this expression appears at top level of a WHERE/HAVING qual.
 237  *
 238  * The result is whatever we need to substitute in place of the SubLink
 239  * node in the executable expression.  This will be either the SubPlan
 240  * node (if we have to do the subplan as a subplan), or a Param node
 241  * representing the result of an InitPlan, or possibly an AND or OR tree
 242  * containing InitPlan Param nodes.
 243  */
 244 static Node *
 245 make_subplan(SubLink *slink, List *lefthand, bool isTopQual)
 246 {
 247         SubPlan    *node = makeNode(SubPlan);
 248         Query      *subquery = (Query *) (slink->subselect);
 249         double          tuple_fraction;
 250         Plan       *plan;
 251         Bitmapset  *tmpset;
 252         int                     paramid;
 253         List       *lst;
 254         Node       *result;
 255
 256         /*
 257          * Copy the source Query node.  This is a quick and dirty kluge to
 258          * resolve the fact that the parser can generate trees with multiple
 259          * links to the same sub-Query node, but the planner wants to scribble
 260          * on the Query. Try to clean this up when we do querytree redesign...
 261          */
 262         subquery = (Query *) copyObject(subquery);
 263
 264         /*
 265          * For an EXISTS subplan, tell lower-level planner to expect that only
 266          * the first tuple will be retrieved.  For ALL and ANY subplans, we
 267          * will be able to stop evaluating if the test condition fails, so
 268          * very often not all the tuples will be retrieved; for lack of a
 269          * better idea, specify 50% retrieval.  For EXPR and MULTIEXPR
 270          * subplans, use default behavior (we're only expecting one row out,
 271          * anyway).
 272          *
 273          * NOTE: if you change these numbers, also change cost_qual_eval_walker()
 274          * in path/costsize.c.
 275          *
 276          * XXX If an ALL/ANY subplan is uncorrelated, we may decide to hash or
 277          * materialize its result below.  In that case it would've been better
 278          * to specify full retrieval.  At present, however, we can only detect
 279          * correlation or lack of it after we've made the subplan :-(. Perhaps
 280          * detection of correlation should be done as a separate step.
 281          * Meanwhile, we don't want to be too optimistic about the percentage
 282          * of tuples retrieved, for fear of selecting a plan that's bad for
 283          * the materialization case.
 284          */
 285         if (slink->subLinkType == EXISTS_SUBLINK)
 286                 tuple_fraction = 1.0;   /* just like a LIMIT 1 */
 287         else if (slink->subLinkType == ALL_SUBLINK ||
 288                          slink->subLinkType == ANY_SUBLINK)
 289                 tuple_fraction = 0.5;   /* 50% */
 290         else
 291                 tuple_fraction = 0.0;   /* default behavior */
 292
 293         /*
 294          * Generate the plan for the subquery.
 295          */
 296         node->plan = plan = subquery_planner(subquery, tuple_fraction);
 297
 298         node->plan_id = PlannerPlanId++;        /* Assign unique ID to this
 299                                                                                  * SubPlan */
 300
 301         node->rtable = subquery->rtable;
 302
 303         /*
 304          * Initialize other fields of the SubPlan node.
 305          */
 306         node->subLinkType = slink->subLinkType;
 307         node->useOr = slink->useOr;
 308         node->exprs = NIL;
 309         node->paramIds = NIL;
 310         node->useHashTable = false;
 311         /* At top level of a qual, can treat UNKNOWN the same as FALSE */
 312         node->unknownEqFalse = isTopQual;
 313         node->setParam = NIL;
 314         node->parParam = NIL;
 315         node->args = NIL;
 316
 317         /*
 318          * Make parParam list of params that current query level will pass to
 319          * this child plan.
 320          */
 321         tmpset = bms_copy(plan->extParam);
 322         while ((paramid = bms_first_member(tmpset)) >= 0)
 323         {
 324                 PlannerParamItem *pitem = nth(paramid, PlannerParamList);
 325
 326                 if (pitem->abslevel == PlannerQueryLevel)
 327                         node->parParam = lappendi(node->parParam, paramid);
 328         }
 329         bms_free(tmpset);
 330
 331         /*
 332          * Un-correlated or undirect correlated plans of EXISTS, EXPR, ARRAY,
 333          * or MULTIEXPR types can be used as initPlans.  For EXISTS, EXPR, or
 334          * ARRAY, we just produce a Param referring to the result of
 335          * evaluating the initPlan.  For MULTIEXPR, we must build an AND or
 336          * OR-clause of the individual comparison operators, using the
 337          * appropriate lefthand side expressions and Params for the initPlan's
 338          * target items.
 339          */
 340         if (node->parParam == NIL && slink->subLinkType == EXISTS_SUBLINK)
 341         {
 342                 Param      *prm;
 343
 344                 prm = generate_new_param(BOOLOID, -1);
 345                 node->setParam = makeListi1(prm->paramid);
 346                 PlannerInitPlan = lappend(PlannerInitPlan, node);
 347                 result = (Node *) prm;
 348         }
 349         else if (node->parParam == NIL && slink->subLinkType == EXPR_SUBLINK)
 350         {
 351                 TargetEntry *te = lfirst(plan->targetlist);
 352                 Param      *prm;
 353
 354                 Assert(!te->resdom->resjunk);
 355                 prm = generate_new_param(te->resdom->restype, te->resdom->restypmod);
 356                 node->setParam = makeListi1(prm->paramid);
 357                 PlannerInitPlan = lappend(PlannerInitPlan, node);
 358                 result = (Node *) prm;
 359         }
 360         else if (node->parParam == NIL && slink->subLinkType == ARRAY_SUBLINK)
 361         {
 362                 TargetEntry *te = lfirst(plan->targetlist);
 363                 Oid                     arraytype;
 364                 Param      *prm;
 365
 366                 Assert(!te->resdom->resjunk);
 367                 arraytype = get_array_type(te->resdom->restype);
 368                 if (!OidIsValid(arraytype))
 369                         elog(ERROR, "could not find array type for datatype %s",
 370                                  format_type_be(te->resdom->restype));
 371                 prm = generate_new_param(arraytype, -1);
 372                 node->setParam = makeListi1(prm->paramid);
 373                 PlannerInitPlan = lappend(PlannerInitPlan, node);
 374                 result = (Node *) prm;
 375         }
 376         else if (node->parParam == NIL && slink->subLinkType == MULTIEXPR_SUBLINK)
 377         {
 378                 List       *exprs;
 379
 380                 /* Convert the lefthand exprs and oper OIDs into executable exprs */
 381                 exprs = convert_sublink_opers(lefthand,
 382                                                                           slink->operOids,
 383                                                                           plan->targetlist,
 384                                                                           0,
 385                                                                           &node->paramIds);
 386                 node->setParam = listCopy(node->paramIds);
 387                 PlannerInitPlan = lappend(PlannerInitPlan, node);
 388
 389                 /*
 390                  * The executable expressions are returned to become part of the
 391                  * outer plan's expression tree; they are not kept in the initplan
 392                  * node.
 393                  */
 394                 if (length(exprs) > 1)
 395                         result = (Node *) (node->useOr ? make_orclause(exprs) :
 396                                                            make_andclause(exprs));
 397                 else
 398                         result = (Node *) lfirst(exprs);
 399         }
 400         else
 401         {
 402                 List       *args;
 403
 404                 /*
 405                  * We can't convert subplans of ALL_SUBLINK or ANY_SUBLINK types
 406                  * to initPlans, even when they are uncorrelated or undirect
 407                  * correlated, because we need to scan the output of the subplan
 408                  * for each outer tuple.  But if it's an IN (= ANY) test, we might
 409                  * be able to use a hashtable to avoid comparing all the tuples.
 410                  */
 411                 if (subplan_is_hashable(slink, node))
 412                         node->useHashTable = true;
 413
 414                 /*
 415                  * Otherwise, we have the option to tack a MATERIAL node onto the
 416                  * top of the subplan, to reduce the cost of reading it
 417                  * repeatedly.  This is pointless for a direct-correlated subplan,
 418                  * since we'd have to recompute its results each time anyway.  For
 419                  * uncorrelated/undirect correlated subplans, we add MATERIAL if
 420                  * the subplan's top plan node is anything more complicated than a
 421                  * plain sequential scan, and we do it even for seqscan if the
 422                  * qual appears selective enough to eliminate many tuples.
 423                  */
 424                 else if (node->parParam == NIL)
 425                 {
 426                         bool            use_material;
 427
 428                         switch (nodeTag(plan))
 429                         {
 430                                 case T_SeqScan:
 431                                         if (plan->initPlan)
 432                                                 use_material = true;
 433                                         else
 434                                         {
 435                                                 Selectivity qualsel;
 436
 437                                                 qualsel = clauselist_selectivity(subquery,
 438                                                                                                                  plan->qual,
 439                                                                                                                  0, JOIN_INNER);
 440                                                 /* Is 10% selectivity a good threshold?? */
 441                                                 use_material = qualsel < 0.10;
 442                                         }
 443                                         break;
 444                                 case T_Material:
 445                                 case T_FunctionScan:
 446                                 case T_Sort:
 447
 448                                         /*
 449                                          * Don't add another Material node if there's one
 450                                          * already, nor if the top node is any other type that
 451                                          * materializes its output anyway.
 452                                          */
 453                                         use_material = false;
 454                                         break;
 455                                 default:
 456                                         use_material = true;
 457                                         break;
 458                         }
 459                         if (use_material)
 460                                 node->plan = plan = materialize_finished_plan(plan);
 461                 }
 462
 463                 /* Convert the lefthand exprs and oper OIDs into executable exprs */
 464                 node->exprs = convert_sublink_opers(lefthand,
 465                                                                                         slink->operOids,
 466                                                                                         plan->targetlist,
 467                                                                                         0,
 468                                                                                         &node->paramIds);
 469
 470                 /*
 471                  * Make node->args from parParam.
 472                  */
 473                 args = NIL;
 474                 foreach(lst, node->parParam)
 475                 {
 476                         PlannerParamItem *pitem = nth(lfirsti(lst), PlannerParamList);
 477
 478                         /*
 479                          * The Var or Aggref has already been adjusted to have the
 480                          * correct varlevelsup or agglevelsup.  We probably don't even
 481                          * need to copy it again, but be safe.
 482                          */
 483                         args = lappend(args, copyObject(pitem->item));
 484                 }
 485                 node->args = args;
 486
 487                 result = (Node *) node;
 488         }
 489
 490         return result;
 491 }
 492
 493 /*
 494  * convert_sublink_opers: given a lefthand-expressions list and a list of
 495  * operator OIDs, build a list of actually executable expressions.      The
 496  * righthand sides of the expressions are Params or Vars representing the
 497  * results of the sub-select.
 498  *
 499  * If rtindex is 0, we build Params to represent the sub-select outputs.
 500  * The paramids of the Params created are returned in the *righthandIds list.
 501  *
 502  * If rtindex is not 0, we build Vars using that rtindex as varno.      Copies
 503  * of the Var nodes are returned in *righthandIds (this is a bit of a type
 504  * cheat, but we can get away with it).
 505  */
 506 static List *
 507 convert_sublink_opers(List *lefthand, List *operOids,
 508                                           List *targetlist, int rtindex,
 509                                           List **righthandIds)
 510 {
 511         List       *result = NIL;
 512         List       *lst;
 513
 514         *righthandIds = NIL;
 515
 516         foreach(lst, operOids)
 517         {
 518                 Oid                     opid = lfirsto(lst);
 519                 Node       *leftop = lfirst(lefthand);
 520                 TargetEntry *te = lfirst(targetlist);
 521                 Node       *rightop;
 522                 Operator        tup;
 523
 524                 Assert(!te->resdom->resjunk);
 525
 526                 if (rtindex)
 527                 {
 528                         /* Make the Var node representing the subplan's result */
 529                         rightop = (Node *) makeVar(rtindex,
 530                                                                            te->resdom->resno,
 531                                                                            te->resdom->restype,
 532                                                                            te->resdom->restypmod,
 533                                                                            0);
 534                         /*
 535                          * Copy it for caller.  NB: we need a copy to avoid having
 536                          * doubly-linked substructure in the modified parse tree.
 537                          */
 538                         *righthandIds = lappend(*righthandIds, copyObject(rightop));
 539                 }
 540                 else
 541                 {
 542                         /* Make the Param node representing the subplan's result */
 543                         Param      *prm;
 544
 545                         prm = generate_new_param(te->resdom->restype,
 546                                                                          te->resdom->restypmod);
 547                         /* Record its ID */
 548                         *righthandIds = lappendi(*righthandIds, prm->paramid);
 549                         rightop = (Node *) prm;
 550                 }
 551
 552                 /* Look up the operator to pass to make_op_expr */
 553                 tup = SearchSysCache(OPEROID,
 554                                                          ObjectIdGetDatum(opid),
 555                                                          0, 0, 0);
 556                 if (!HeapTupleIsValid(tup))
 557                         elog(ERROR, "cache lookup failed for operator %u", opid);
 558
 559                 /*
 560                  * Make the expression node.
 561                  *
 562                  * Note: we use make_op_expr in case runtime type conversion function
 563                  * calls must be inserted for this operator!  (But we are not
 564                  * expecting to have to resolve unknown Params, so it's okay to
 565                  * pass a null pstate.)
 566                  */
 567                 result = lappend(result,
 568                                                  make_op_expr(NULL,
 569                                                                           tup,
 570                                                                           leftop,
 571                                                                           rightop,
 572                                                                           exprType(leftop),
 573                                                                           te->resdom->restype));
 574
 575                 ReleaseSysCache(tup);
 576
 577                 lefthand = lnext(lefthand);
 578                 targetlist = lnext(targetlist);
 579         }
 580
 581         return result;
 582 }
 583
 584 /*
 585  * subplan_is_hashable: decide whether we can implement a subplan by hashing
 586  *
 587  * Caution: the SubPlan node is not completely filled in yet.  We can rely
 588  * on its plan and parParam fields, however.
 589  */
 590 static bool
 591 subplan_is_hashable(SubLink *slink, SubPlan *node)
 592 {
 593         double          subquery_size;
 594         List       *opids;
 595
 596         /*
 597          * The sublink type must be "= ANY" --- that is, an IN operator. (We
 598          * require the operator name to be unqualified, which may be overly
 599          * paranoid, or may not be.)  XXX since we also check that the
 600          * operators are hashable, the test on operator name may be redundant?
 601          */
 602         if (slink->subLinkType != ANY_SUBLINK)
 603                 return false;
 604         if (length(slink->operName) != 1 ||
 605                 strcmp(strVal(lfirst(slink->operName)), "=") != 0)
 606                 return false;
 607
 608         /*
 609          * The subplan must not have any direct correlation vars --- else we'd
 610          * have to recompute its output each time, so that the hashtable
 611          * wouldn't gain anything.
 612          */
 613         if (node->parParam != NIL)
 614                 return false;
 615
 616         /*
 617          * The estimated size of the subquery result must fit in SortMem. (XXX
 618          * what about hashtable overhead?)
 619          */
 620         subquery_size = node->plan->plan_rows *
 621                 (MAXALIGN(node->plan->plan_width) + MAXALIGN(sizeof(HeapTupleData)));
 622         if (subquery_size > SortMem * 1024L)
 623                 return false;
 624
 625         /*
 626          * The combining operators must be hashable, strict, and
 627          * self-commutative. The need for hashability is obvious, since we
 628          * want to use hashing. Without strictness, behavior in the presence
 629          * of nulls is too unpredictable.  (We actually must assume even more
 630          * than plain strictness, see nodeSubplan.c for details.)  And
 631          * commutativity ensures that the left and right datatypes are the
 632          * same; this allows us to assume that the combining operators are
 633          * equality for the righthand datatype, so that they can be used to
 634          * compare righthand tuples as well as comparing lefthand to righthand
 635          * tuples.      (This last restriction could be relaxed by using two
 636          * different sets of operators with the hash table, but there is no
 637          * obvious usefulness to that at present.)
 638          */
 639         foreach(opids, slink->operOids)
 640         {
 641                 Oid                     opid = lfirsto(opids);
 642                 HeapTuple       tup;
 643                 Form_pg_operator optup;
 644
 645                 tup = SearchSysCache(OPEROID,
 646                                                          ObjectIdGetDatum(opid),
 647                                                          0, 0, 0);
 648                 if (!HeapTupleIsValid(tup))
 649                         elog(ERROR, "cache lookup failed for operator %u", opid);
 650                 optup = (Form_pg_operator) GETSTRUCT(tup);
 651                 if (!optup->oprcanhash || optup->oprcom != opid ||
 652                         !func_strict(optup->oprcode))
 653                 {
 654                         ReleaseSysCache(tup);
 655                         return false;
 656                 }
 657                 ReleaseSysCache(tup);
 658         }
 659         return true;
 660 }
 661
 662 /*
 663  * convert_IN_to_join: can we convert an IN SubLink to join style?
 664  *
 665  * The caller has found a SubLink at the top level of WHERE, but has not
 666  * checked the properties of the SubLink at all.  Decide whether it is
 667  * appropriate to process this SubLink in join style.  If not, return NULL.
 668  * If so, build the qual clause(s) to replace the SubLink, and return them.
 669  *
 670  * Side effects of a successful conversion include adding the SubLink's
 671  * subselect to the query's rangetable and adding an InClauseInfo node to
 672  * its in_info_list.
 673  */
 674 Node *
 675 convert_IN_to_join(Query *parse, SubLink *sublink)
 676 {
 677         Query      *subselect = (Query *) sublink->subselect;
 678         Relids          left_varnos;
 679         int                     rtindex;
 680         RangeTblEntry *rte;
 681         RangeTblRef *rtr;
 682         InClauseInfo *ininfo;
 683         List       *exprs;
 684
 685         /*
 686          * The sublink type must be "= ANY" --- that is, an IN operator. (We
 687          * require the operator name to be unqualified, which may be overly
 688          * paranoid, or may not be.)
 689          */
 690         if (sublink->subLinkType != ANY_SUBLINK)
 691                 return NULL;
 692         if (length(sublink->operName) != 1 ||
 693                 strcmp(strVal(lfirst(sublink->operName)), "=") != 0)
 694                 return NULL;
 695
 696         /*
 697          * The sub-select must not refer to any Vars of the parent query.
 698          * (Vars of higher levels should be okay, though.)
 699          */
 700         if (contain_vars_of_level((Node *) subselect, 1))
 701                 return NULL;
 702
 703         /*
 704          * The left-hand expressions must contain some Vars of the current
 705          * query, else it's not gonna be a join.
 706          */
 707         left_varnos = pull_varnos((Node *) sublink->lefthand);
 708         if (bms_is_empty(left_varnos))
 709                 return NULL;
 710
 711         /*
 712          * The left-hand expressions mustn't be volatile.  (Perhaps we should
 713          * test the combining operators, too?  We'd only need to point the
 714          * function directly at the sublink ...)
 715          */
 716         if (contain_volatile_functions((Node *) sublink->lefthand))
 717                 return NULL;
 718
 719         /*
 720          * Okay, pull up the sub-select into top range table and jointree.
 721          *
 722          * We rely here on the assumption that the outer query has no references
 723          * to the inner (necessarily true, other than the Vars that we build
 724          * below).      Therefore this is a lot easier than what
 725          * pull_up_subqueries has to go through.
 726          */
 727         rte = addRangeTableEntryForSubquery(NULL,
 728                                                                                 subselect,
 729                                                                                 makeAlias("IN_subquery", NIL),
 730                                                                                 false);
 731         parse->rtable = lappend(parse->rtable, rte);
 732         rtindex = length(parse->rtable);
 733         rtr = makeNode(RangeTblRef);
 734         rtr->rtindex = rtindex;
 735         parse->jointree->fromlist = lappend(parse->jointree->fromlist, rtr);
 736
 737         /*
 738          * Now build the InClauseInfo node.
 739          */
 740         ininfo = makeNode(InClauseInfo);
 741         ininfo->lefthand = left_varnos;
 742         ininfo->righthand = bms_make_singleton(rtindex);
 743         parse->in_info_list = lcons(ininfo, parse->in_info_list);
 744
 745         /*
 746          * Build the result qual expressions.  As a side effect,
 747          * ininfo->sub_targetlist is filled with a list of Vars
 748          * representing the subselect outputs.
 749          */
 750         exprs = convert_sublink_opers(sublink->lefthand,
 751                                                                   sublink->operOids,
 752                                                                   subselect->targetList,
 753                                                                   rtindex,
 754                                                                   &ininfo->sub_targetlist);
 755         return (Node *) make_ands_explicit(exprs);
 756 }
 757
 758 /*
 759  * Replace correlation vars (uplevel vars) with Params.
 760  *
 761  * Uplevel aggregates are replaced, too.
 762  *
 763  * Note: it is critical that this runs immediately after SS_process_sublinks.
 764  * Since we do not recurse into the arguments of uplevel aggregates, they will
 765  * get copied to the appropriate subplan args list in the parent query with
 766  * uplevel vars not replaced by Params, but only adjusted in level (see
 767  * replace_outer_agg).  That's exactly what we want for the vars of the parent
 768  * level --- but if an aggregate's argument contains any further-up variables,
 769  * they have to be replaced with Params in their turn.  That will happen when
 770  * the parent level runs SS_replace_correlation_vars.  Therefore it must do
 771  * so after expanding its sublinks to subplans.  And we don't want any steps
 772  * in between, else those steps would never get applied to the aggregate
 773  * argument expressions, either in the parent or the child level.
 774  */
 775 Node *
 776 SS_replace_correlation_vars(Node *expr)
 777 {
 778         /* No setup needed for tree walk, so away we go */
 779         return replace_correlation_vars_mutator(expr, NULL);
 780 }
 781
 782 static Node *
 783 replace_correlation_vars_mutator(Node *node, void *context)
 784 {
 785         if (node == NULL)
 786                 return NULL;
 787         if (IsA(node, Var))
 788         {
 789                 if (((Var *) node)->varlevelsup > 0)
 790                         return (Node *) replace_outer_var((Var *) node);
 791         }
 792         if (IsA(node, Aggref))
 793         {
 794                 if (((Aggref *) node)->agglevelsup > 0)
 795                         return (Node *) replace_outer_agg((Aggref *) node);
 796         }
 797         return expression_tree_mutator(node,
 798                                                                    replace_correlation_vars_mutator,
 799                                                                    context);
 800 }
 801
 802 /*
 803  * Expand SubLinks to SubPlans in the given expression.
 804  *
 805  * The isQual argument tells whether or not this expression is a WHERE/HAVING
 806  * qualifier expression.  If it is, any sublinks appearing at top level need
 807  * not distinguish FALSE from UNKNOWN return values.
 808  */
 809 Node *
 810 SS_process_sublinks(Node *expr, bool isQual)
 811 {
 812         /* The only context needed is the initial are-we-in-a-qual flag */
 813         return process_sublinks_mutator(expr, &isQual);
 814 }
 815
 816 static Node *
 817 process_sublinks_mutator(Node *node, bool *isTopQual)
 818 {
 819         bool            locTopQual;
 820
 821         if (node == NULL)
 822                 return NULL;
 823         if (IsA(node, SubLink))
 824         {
 825                 SubLink    *sublink = (SubLink *) node;
 826                 List       *lefthand;
 827
 828                 /*
 829                  * First, recursively process the lefthand-side expressions, if
 830                  * any.
 831                  */
 832                 locTopQual = false;
 833                 lefthand = (List *)
 834                         process_sublinks_mutator((Node *) sublink->lefthand, &locTopQual);
 835
 836                 /*
 837                  * Now build the SubPlan node and make the expr to return.
 838                  */
 839                 return make_subplan(sublink, lefthand, *isTopQual);
 840         }
 841
 842         /*
 843          * We should never see a SubPlan expression in the input (since this
 844          * is the very routine that creates 'em to begin with).  We shouldn't
 845          * find ourselves invoked directly on a Query, either.
 846          */
 847         Assert(!is_subplan(node));
 848         Assert(!IsA(node, Query));
 849
 850         /*
 851          * Because make_subplan() could return an AND or OR clause, we have to
 852          * take steps to preserve AND/OR flatness of a qual.  We assume the input
 853          * has been AND/OR flattened and so we need no recursion here.
 854          *
 855          * If we recurse down through anything other than an AND node,
 856          * we are definitely not at top qual level anymore.  (Due to the coding
 857          * here, we will not get called on the List subnodes of an AND, so no
 858          * check is needed for List.)
 859          */
 860         if (and_clause(node))
 861         {
 862                 List   *newargs = NIL;
 863                 List   *l;
 864
 865                 /* Still at qual top-level */
 866                 locTopQual = *isTopQual;
 867
 868                 foreach(l, ((BoolExpr *) node)->args)
 869                 {
 870                         Node *newarg;
 871
 872                         newarg = process_sublinks_mutator(lfirst(l),
 873                                                                                           (void *) &locTopQual);
 874                         if (and_clause(newarg))
 875                                 newargs = nconc(newargs, ((BoolExpr *) newarg)->args);
 876                         else
 877                                 newargs = lappend(newargs, newarg);
 878                 }
 879                 return (Node *) make_andclause(newargs);
 880         }
 881
 882         /* otherwise not at qual top-level */
 883         locTopQual = false;
 884
 885         if (or_clause(node))
 886         {
 887                 List   *newargs = NIL;
 888                 List   *l;
 889
 890                 foreach(l, ((BoolExpr *) node)->args)
 891                 {
 892                         Node *newarg;
 893
 894                         newarg = process_sublinks_mutator(lfirst(l),
 895                                                                                           (void *) &locTopQual);
 896                         if (or_clause(newarg))
 897                                 newargs = nconc(newargs, ((BoolExpr *) newarg)->args);
 898                         else
 899                                 newargs = lappend(newargs, newarg);
 900                 }
 901                 return (Node *) make_orclause(newargs);
 902         }
 903
 904         return expression_tree_mutator(node,
 905                                                                    process_sublinks_mutator,
 906                                                                    (void *) &locTopQual);
 907 }
 908
 909 /*
 910  * SS_finalize_plan - do final sublink processing for a completed Plan.
 911  *
 912  * This recursively computes the extParam and allParam sets
 913  * for every Plan node in the given plan tree.
 914  */
 915 void
 916 SS_finalize_plan(Plan *plan, List *rtable)
 917 {
 918         Bitmapset  *outer_params = NULL;
 919         Bitmapset  *valid_params = NULL;
 920         int                     paramid;
 921         List       *lst;
 922
 923         /*
 924          * First, scan the param list to discover the sets of params that are
 925          * available from outer query levels and my own query level. We do
 926          * this once to save time in the per-plan recursion steps.
 927          */
 928         paramid = 0;
 929         foreach(lst, PlannerParamList)
 930         {
 931                 PlannerParamItem *pitem = (PlannerParamItem *) lfirst(lst);
 932
 933                 if (pitem->abslevel < PlannerQueryLevel)
 934                 {
 935                         /* valid outer-level parameter */
 936                         outer_params = bms_add_member(outer_params, paramid);
 937                         valid_params = bms_add_member(valid_params, paramid);
 938                 }
 939                 else if (pitem->abslevel == PlannerQueryLevel &&
 940                                  IsA(pitem->item, Param))
 941                 {
 942                         /* valid local parameter (i.e., a setParam of my child) */
 943                         valid_params = bms_add_member(valid_params, paramid);
 944                 }
 945
 946                 paramid++;
 947         }
 948
 949         /*
 950          * Now recurse through plan tree.
 951          */
 952         (void) finalize_plan(plan, rtable, outer_params, valid_params);
 953
 954         bms_free(outer_params);
 955         bms_free(valid_params);
 956 }
 957
 958 /*
 959  * Recursive processing of all nodes in the plan tree
 960  *
 961  * The return value is the computed allParam set for the given Plan node.
 962  * This is just an internal notational convenience.
 963  */
 964 static Bitmapset *
 965 finalize_plan(Plan *plan, List *rtable,
 966                           Bitmapset *outer_params, Bitmapset *valid_params)
 967 {
 968         finalize_primnode_context context;
 969         List       *lst;
 970
 971         if (plan == NULL)
 972                 return NULL;
 973
 974         context.paramids = NULL;        /* initialize set to empty */
 975         context.outer_params = outer_params;
 976
 977         /*
 978          * When we call finalize_primnode, context.paramids sets are
 979          * automatically merged together.  But when recursing to self, we have
 980          * to do it the hard way.  We want the paramids set to include params
 981          * in subplans as well as at this level.
 982          */
 983
 984         /* Find params in targetlist and qual */
 985         finalize_primnode((Node *) plan->targetlist, &context);
 986         finalize_primnode((Node *) plan->qual, &context);
 987
 988         /* Check additional node-type-specific fields */
 989         switch (nodeTag(plan))
 990         {
 991                 case T_Result:
 992                         finalize_primnode(((Result *) plan)->resconstantqual,
 993                                                           &context);
 994                         break;
 995
 996                 case T_IndexScan:
 997                         finalize_primnode((Node *) ((IndexScan *) plan)->indxqual,
 998                                                           &context);
 999
1000                         /*
1001                          * we need not look at indxqualorig, since it will have the
1002                          * same param references as indxqual.
1003                          */
1004                         break;
1005
1006                 case T_TidScan:
1007                         finalize_primnode((Node *) ((TidScan *) plan)->tideval,
1008                                                           &context);
1009                         break;
1010
1011                 case T_SubqueryScan:
1012
1013                         /*
1014                          * In a SubqueryScan, SS_finalize_plan has already been run on
1015                          * the subplan by the inner invocation of subquery_planner, so
1016                          * there's no need to do it again.  Instead, just pull out the
1017                          * subplan's extParams list, which represents the params it
1018                          * needs from my level and higher levels.
1019                          */
1020                         context.paramids = bms_add_members(context.paramids,
1021                                                          ((SubqueryScan *) plan)->subplan->extParam);
1022                         break;
1023
1024                 case T_FunctionScan:
1025                         {
1026                                 RangeTblEntry *rte;
1027
1028                                 rte = rt_fetch(((FunctionScan *) plan)->scan.scanrelid,
1029                                                            rtable);
1030                                 Assert(rte->rtekind == RTE_FUNCTION);
1031                                 finalize_primnode(rte->funcexpr, &context);
1032                         }
1033                         break;
1034
1035                 case T_Append:
1036                         foreach(lst, ((Append *) plan)->appendplans)
1037                         {
1038                                 context.paramids =
1039                                         bms_add_members(context.paramids,
1040                                                                         finalize_plan((Plan *) lfirst(lst),
1041                                                                                                   rtable,
1042                                                                                                   outer_params,
1043                                                                                                   valid_params));
1044                         }
1045                         break;
1046
1047                 case T_NestLoop:
1048                         finalize_primnode((Node *) ((Join *) plan)->joinqual,
1049                                                           &context);
1050                         break;
1051
1052                 case T_MergeJoin:
1053                         finalize_primnode((Node *) ((Join *) plan)->joinqual,
1054                                                           &context);
1055                         finalize_primnode((Node *) ((MergeJoin *) plan)->mergeclauses,
1056                                                           &context);
1057                         break;
1058
1059                 case T_HashJoin:
1060                         finalize_primnode((Node *) ((Join *) plan)->joinqual,
1061                                                           &context);
1062                         finalize_primnode((Node *) ((HashJoin *) plan)->hashclauses,
1063                                                           &context);
1064                         break;
1065
1066                 case T_Hash:
1067                 case T_Agg:
1068                 case T_SeqScan:
1069                 case T_Material:
1070                 case T_Sort:
1071                 case T_Unique:
1072                 case T_SetOp:
1073                 case T_Limit:
1074                 case T_Group:
1075                         break;
1076
1077                 default:
1078                         elog(ERROR, "unrecognized node type: %d",
1079                                  (int) nodeTag(plan));
1080         }
1081
1082         /* Process left and right child plans, if any */
1083         context.paramids = bms_add_members(context.paramids,
1084                                                                            finalize_plan(plan->lefttree,
1085                                                                                                          rtable,
1086                                                                                                          outer_params,
1087                                                                                                          valid_params));
1088
1089         context.paramids = bms_add_members(context.paramids,
1090                                                                            finalize_plan(plan->righttree,
1091                                                                                                          rtable,
1092                                                                                                          outer_params,
1093                                                                                                          valid_params));
1094
1095         /* Now we have all the paramids */
1096
1097         if (!bms_is_subset(context.paramids, valid_params))
1098                 elog(ERROR, "plan should not reference subplan's variable");
1099
1100         plan->extParam = bms_intersect(context.paramids, outer_params);
1101         plan->allParam = context.paramids;
1102
1103         /*
1104          * For speed at execution time, make sure extParam/allParam are
1105          * actually NULL if they are empty sets.
1106          */
1107         if (bms_is_empty(plan->extParam))
1108         {
1109                 bms_free(plan->extParam);
1110                 plan->extParam = NULL;
1111         }
1112         if (bms_is_empty(plan->allParam))
1113         {
1114                 bms_free(plan->allParam);
1115                 plan->allParam = NULL;
1116         }
1117
1118         return plan->allParam;
1119 }
1120
1121 /*
1122  * finalize_primnode: add IDs of all PARAM_EXEC params appearing in the given
1123  * expression tree to the result set.
1124  */
1125 static bool
1126 finalize_primnode(Node *node, finalize_primnode_context *context)
1127 {
1128         if (node == NULL)
1129                 return false;
1130         if (IsA(node, Param))
1131         {
1132                 if (((Param *) node)->paramkind == PARAM_EXEC)
1133                 {
1134                         int                     paramid = (int) ((Param *) node)->paramid;
1135
1136                         context->paramids = bms_add_member(context->paramids, paramid);
1137                 }
1138                 return false;                   /* no more to do here */
1139         }
1140         if (is_subplan(node))
1141         {
1142                 SubPlan    *subplan = (SubPlan *) node;
1143
1144                 /* Add outer-level params needed by the subplan to paramids */
1145                 context->paramids = bms_join(context->paramids,
1146                                                                    bms_intersect(subplan->plan->extParam,
1147                                                                                                  context->outer_params));
1148                 /* fall through to recurse into subplan args */
1149         }
1150         return expression_tree_walker(node, finalize_primnode,
1151                                                                   (void *) context);
1152 }