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-2005, 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.99 2005/06/05 22:32:56 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         ListCell   *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 for
 123          * the Param itself, since those are not typmod-dependent, but it does
 124          * matter when make_subplan() instantiates a modified copy of the Var
 125          * 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 = list_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) list_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         Node       *result;
 254
 255         /*
 256          * Copy the source Query node.  This is a quick and dirty kluge to
 257          * resolve the fact that the parser can generate trees with multiple
 258          * links to the same sub-Query node, but the planner wants to scribble
 259          * on the Query. Try to clean this up when we do querytree redesign...
 260          */
 261         subquery = (Query *) copyObject(subquery);
 262
 263         /*
 264          * For an EXISTS subplan, tell lower-level planner to expect that only
 265          * the first tuple will be retrieved.  For ALL and ANY subplans, we
 266          * will be able to stop evaluating if the test condition fails, so
 267          * very often not all the tuples will be retrieved; for lack of a
 268          * better idea, specify 50% retrieval.  For EXPR and MULTIEXPR
 269          * subplans, use default behavior (we're only expecting one row out,
 270          * anyway).
 271          *
 272          * NOTE: if you change these numbers, also change cost_qual_eval_walker()
 273          * in path/costsize.c.
 274          *
 275          * XXX If an ALL/ANY subplan is uncorrelated, we may decide to hash or
 276          * materialize its result below.  In that case it would've been better
 277          * to specify full retrieval.  At present, however, we can only detect
 278          * correlation or lack of it after we've made the subplan :-(. Perhaps
 279          * detection of correlation should be done as a separate step.
 280          * Meanwhile, we don't want to be too optimistic about the percentage
 281          * of tuples retrieved, for fear of selecting a plan that's bad for
 282          * the materialization case.
 283          */
 284         if (slink->subLinkType == EXISTS_SUBLINK)
 285                 tuple_fraction = 1.0;   /* just like a LIMIT 1 */
 286         else if (slink->subLinkType == ALL_SUBLINK ||
 287                          slink->subLinkType == ANY_SUBLINK)
 288                 tuple_fraction = 0.5;   /* 50% */
 289         else
 290                 tuple_fraction = 0.0;   /* default behavior */
 291
 292         /*
 293          * Generate the plan for the subquery.
 294          */
 295         node->plan = plan = subquery_planner(subquery, tuple_fraction, NULL);
 296
 297         node->plan_id = PlannerPlanId++;        /* Assign unique ID to this
 298                                                                                  * SubPlan */
 299
 300         node->rtable = subquery->rtable;
 301
 302         /*
 303          * Initialize other fields of the SubPlan node.
 304          */
 305         node->subLinkType = slink->subLinkType;
 306         node->useOr = slink->useOr;
 307         node->exprs = NIL;
 308         node->paramIds = NIL;
 309         node->useHashTable = false;
 310         /* At top level of a qual, can treat UNKNOWN the same as FALSE */
 311         node->unknownEqFalse = isTopQual;
 312         node->setParam = NIL;
 313         node->parParam = NIL;
 314         node->args = NIL;
 315
 316         /*
 317          * Make parParam list of params that current query level will pass to
 318          * this child plan.
 319          */
 320         tmpset = bms_copy(plan->extParam);
 321         while ((paramid = bms_first_member(tmpset)) >= 0)
 322         {
 323                 PlannerParamItem *pitem = list_nth(PlannerParamList, paramid);
 324
 325                 if (pitem->abslevel == PlannerQueryLevel)
 326                         node->parParam = lappend_int(node->parParam, paramid);
 327         }
 328         bms_free(tmpset);
 329
 330         /*
 331          * Un-correlated or undirect correlated plans of EXISTS, EXPR, ARRAY,
 332          * or MULTIEXPR types can be used as initPlans.  For EXISTS, EXPR, or
 333          * ARRAY, we just produce a Param referring to the result of
 334          * evaluating the initPlan.  For MULTIEXPR, we must build an AND or
 335          * OR-clause of the individual comparison operators, using the
 336          * appropriate lefthand side expressions and Params for the initPlan's
 337          * target items.
 338          */
 339         if (node->parParam == NIL && slink->subLinkType == EXISTS_SUBLINK)
 340         {
 341                 Param      *prm;
 342
 343                 prm = generate_new_param(BOOLOID, -1);
 344                 node->setParam = list_make1_int(prm->paramid);
 345                 PlannerInitPlan = lappend(PlannerInitPlan, node);
 346                 result = (Node *) prm;
 347         }
 348         else if (node->parParam == NIL && slink->subLinkType == EXPR_SUBLINK)
 349         {
 350                 TargetEntry *te = linitial(plan->targetlist);
 351                 Param      *prm;
 352
 353                 Assert(!te->resjunk);
 354                 prm = generate_new_param(exprType((Node *) te->expr),
 355                                                                  exprTypmod((Node *) te->expr));
 356                 node->setParam = list_make1_int(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 = linitial(plan->targetlist);
 363                 Oid                     arraytype;
 364                 Param      *prm;
 365
 366                 Assert(!te->resjunk);
 367                 arraytype = get_array_type(exprType((Node *) te->expr));
 368                 if (!OidIsValid(arraytype))
 369                         elog(ERROR, "could not find array type for datatype %s",
 370                                  format_type_be(exprType((Node *) te->expr)));
 371                 prm = generate_new_param(arraytype, -1);
 372                 node->setParam = list_make1_int(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 = list_copy(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 (list_length(exprs) > 1)
 395                         result = (Node *) (node->useOr ? make_orclause(exprs) :
 396                                                            make_andclause(exprs));
 397                 else
 398                         result = (Node *) linitial(exprs);
 399         }
 400         else
 401         {
 402                 List       *args;
 403                 ListCell   *l;
 404
 405                 /*
 406                  * We can't convert subplans of ALL_SUBLINK or ANY_SUBLINK types
 407                  * to initPlans, even when they are uncorrelated or undirect
 408                  * correlated, because we need to scan the output of the subplan
 409                  * for each outer tuple.  But if it's an IN (= ANY) test, we might
 410                  * be able to use a hashtable to avoid comparing all the tuples.
 411                  */
 412                 if (subplan_is_hashable(slink, node))
 413                         node->useHashTable = true;
 414
 415                 /*
 416                  * Otherwise, we have the option to tack a MATERIAL node onto the
 417                  * top of the subplan, to reduce the cost of reading it
 418                  * repeatedly.  This is pointless for a direct-correlated subplan,
 419                  * since we'd have to recompute its results each time anyway.  For
 420                  * uncorrelated/undirect correlated subplans, we add MATERIAL unless
 421                  * the subplan's top plan node would materialize its output anyway.
 422                  */
 423                 else if (node->parParam == NIL)
 424                 {
 425                         bool            use_material;
 426
 427                         switch (nodeTag(plan))
 428                         {
 429                                 case T_Material:
 430                                 case T_FunctionScan:
 431                                 case T_Sort:
 432                                         use_material = false;
 433                                         break;
 434                                 default:
 435                                         use_material = true;
 436                                         break;
 437                         }
 438                         if (use_material)
 439                                 node->plan = plan = materialize_finished_plan(plan);
 440                 }
 441
 442                 /* Convert the lefthand exprs and oper OIDs into executable exprs */
 443                 node->exprs = convert_sublink_opers(lefthand,
 444                                                                                         slink->operOids,
 445                                                                                         plan->targetlist,
 446                                                                                         0,
 447                                                                                         &node->paramIds);
 448
 449                 /*
 450                  * Make node->args from parParam.
 451                  */
 452                 args = NIL;
 453                 foreach(l, node->parParam)
 454                 {
 455                         PlannerParamItem *pitem = list_nth(PlannerParamList, lfirst_int(l));
 456
 457                         /*
 458                          * The Var or Aggref has already been adjusted to have the
 459                          * correct varlevelsup or agglevelsup.  We probably don't even
 460                          * need to copy it again, but be safe.
 461                          */
 462                         args = lappend(args, copyObject(pitem->item));
 463                 }
 464                 node->args = args;
 465
 466                 result = (Node *) node;
 467         }
 468
 469         return result;
 470 }
 471
 472 /*
 473  * convert_sublink_opers: given a lefthand-expressions list and a list of
 474  * operator OIDs, build a list of actually executable expressions.      The
 475  * righthand sides of the expressions are Params or Vars representing the
 476  * results of the sub-select.
 477  *
 478  * If rtindex is 0, we build Params to represent the sub-select outputs.
 479  * The paramids of the Params created are returned in the *righthandIds list.
 480  *
 481  * If rtindex is not 0, we build Vars using that rtindex as varno.      Copies
 482  * of the Var nodes are returned in *righthandIds (this is a bit of a type
 483  * cheat, but we can get away with it).
 484  */
 485 static List *
 486 convert_sublink_opers(List *lefthand, List *operOids,
 487                                           List *targetlist, int rtindex,
 488                                           List **righthandIds)
 489 {
 490         List       *result = NIL;
 491         ListCell   *l,
 492                            *lefthand_item,
 493                            *tlist_item;
 494
 495         *righthandIds = NIL;
 496         lefthand_item = list_head(lefthand);
 497         tlist_item = list_head(targetlist);
 498
 499         foreach(l, operOids)
 500         {
 501                 Oid                     opid = lfirst_oid(l);
 502                 Node       *leftop = (Node *) lfirst(lefthand_item);
 503                 TargetEntry *te = (TargetEntry *) lfirst(tlist_item);
 504                 Node       *rightop;
 505                 Operator        tup;
 506
 507                 Assert(!te->resjunk);
 508
 509                 if (rtindex)
 510                 {
 511                         /* Make the Var node representing the subplan's result */
 512                         rightop = (Node *) makeVar(rtindex,
 513                                                                            te->resno,
 514                                                                            exprType((Node *) te->expr),
 515                                                                            exprTypmod((Node *) te->expr),
 516                                                                            0);
 517
 518                         /*
 519                          * Copy it for caller.  NB: we need a copy to avoid having
 520                          * doubly-linked substructure in the modified parse tree.
 521                          */
 522                         *righthandIds = lappend(*righthandIds, copyObject(rightop));
 523                 }
 524                 else
 525                 {
 526                         /* Make the Param node representing the subplan's result */
 527                         Param      *prm;
 528
 529                         prm = generate_new_param(exprType((Node *) te->expr),
 530                                                                          exprTypmod((Node *) te->expr));
 531                         /* Record its ID */
 532                         *righthandIds = lappend_int(*righthandIds, prm->paramid);
 533                         rightop = (Node *) prm;
 534                 }
 535
 536                 /* Look up the operator to pass to make_op_expr */
 537                 tup = SearchSysCache(OPEROID,
 538                                                          ObjectIdGetDatum(opid),
 539                                                          0, 0, 0);
 540                 if (!HeapTupleIsValid(tup))
 541                         elog(ERROR, "cache lookup failed for operator %u", opid);
 542
 543                 /*
 544                  * Make the expression node.
 545                  *
 546                  * Note: we use make_op_expr in case runtime type conversion function
 547                  * calls must be inserted for this operator!  (But we are not
 548                  * expecting to have to resolve unknown Params, so it's okay to
 549                  * pass a null pstate.)
 550                  */
 551                 result = lappend(result,
 552                                                  make_op_expr(NULL,
 553                                                                           tup,
 554                                                                           leftop,
 555                                                                           rightop,
 556                                                                           exprType(leftop),
 557                                                                           exprType((Node *) te->expr)));
 558
 559                 ReleaseSysCache(tup);
 560
 561                 lefthand_item = lnext(lefthand_item);
 562                 tlist_item = lnext(tlist_item);
 563         }
 564
 565         return result;
 566 }
 567
 568 /*
 569  * subplan_is_hashable: decide whether we can implement a subplan by hashing
 570  *
 571  * Caution: the SubPlan node is not completely filled in yet.  We can rely
 572  * on its plan and parParam fields, however.
 573  */
 574 static bool
 575 subplan_is_hashable(SubLink *slink, SubPlan *node)
 576 {
 577         double          subquery_size;
 578         ListCell   *l;
 579
 580         /*
 581          * The sublink type must be "= ANY" --- that is, an IN operator. (We
 582          * require the operator name to be unqualified, which may be overly
 583          * paranoid, or may not be.)  XXX since we also check that the
 584          * operators are hashable, the test on operator name may be redundant?
 585          */
 586         if (slink->subLinkType != ANY_SUBLINK)
 587                 return false;
 588         if (list_length(slink->operName) != 1 ||
 589                 strcmp(strVal(linitial(slink->operName)), "=") != 0)
 590                 return false;
 591
 592         /*
 593          * The subplan must not have any direct correlation vars --- else we'd
 594          * have to recompute its output each time, so that the hashtable
 595          * wouldn't gain anything.
 596          */
 597         if (node->parParam != NIL)
 598                 return false;
 599
 600         /*
 601          * The estimated size of the subquery result must fit in work_mem.
 602          * (XXX what about hashtable overhead?)
 603          */
 604         subquery_size = node->plan->plan_rows *
 605                 (MAXALIGN(node->plan->plan_width) + MAXALIGN(sizeof(HeapTupleData)));
 606         if (subquery_size > work_mem * 1024L)
 607                 return false;
 608
 609         /*
 610          * The combining operators must be hashable, strict, and
 611          * self-commutative. The need for hashability is obvious, since we
 612          * want to use hashing. Without strictness, behavior in the presence
 613          * of nulls is too unpredictable.  (We actually must assume even more
 614          * than plain strictness, see nodeSubplan.c for details.)  And
 615          * commutativity ensures that the left and right datatypes are the
 616          * same; this allows us to assume that the combining operators are
 617          * equality for the righthand datatype, so that they can be used to
 618          * compare righthand tuples as well as comparing lefthand to righthand
 619          * tuples.      (This last restriction could be relaxed by using two
 620          * different sets of operators with the hash table, but there is no
 621          * obvious usefulness to that at present.)
 622          */
 623         foreach(l, slink->operOids)
 624         {
 625                 Oid                     opid = lfirst_oid(l);
 626                 HeapTuple       tup;
 627                 Form_pg_operator optup;
 628
 629                 tup = SearchSysCache(OPEROID,
 630                                                          ObjectIdGetDatum(opid),
 631                                                          0, 0, 0);
 632                 if (!HeapTupleIsValid(tup))
 633                         elog(ERROR, "cache lookup failed for operator %u", opid);
 634                 optup = (Form_pg_operator) GETSTRUCT(tup);
 635                 if (!optup->oprcanhash || optup->oprcom != opid ||
 636                         !func_strict(optup->oprcode))
 637                 {
 638                         ReleaseSysCache(tup);
 639                         return false;
 640                 }
 641                 ReleaseSysCache(tup);
 642         }
 643         return true;
 644 }
 645
 646 /*
 647  * convert_IN_to_join: can we convert an IN SubLink to join style?
 648  *
 649  * The caller has found a SubLink at the top level of WHERE, but has not
 650  * checked the properties of the SubLink at all.  Decide whether it is
 651  * appropriate to process this SubLink in join style.  If not, return NULL.
 652  * If so, build the qual clause(s) to replace the SubLink, and return them.
 653  *
 654  * Side effects of a successful conversion include adding the SubLink's
 655  * subselect to the query's rangetable and adding an InClauseInfo node to
 656  * its in_info_list.
 657  */
 658 Node *
 659 convert_IN_to_join(PlannerInfo *root, SubLink *sublink)
 660 {
 661         Query      *parse = root->parse;
 662         Query      *subselect = (Query *) sublink->subselect;
 663         Relids          left_varnos;
 664         int                     rtindex;
 665         RangeTblEntry *rte;
 666         RangeTblRef *rtr;
 667         InClauseInfo *ininfo;
 668         List       *exprs;
 669
 670         /*
 671          * The sublink type must be "= ANY" --- that is, an IN operator. (We
 672          * require the operator name to be unqualified, which may be overly
 673          * paranoid, or may not be.)
 674          */
 675         if (sublink->subLinkType != ANY_SUBLINK)
 676                 return NULL;
 677         if (list_length(sublink->operName) != 1 ||
 678                 strcmp(strVal(linitial(sublink->operName)), "=") != 0)
 679                 return NULL;
 680
 681         /*
 682          * The sub-select must not refer to any Vars of the parent query.
 683          * (Vars of higher levels should be okay, though.)
 684          */
 685         if (contain_vars_of_level((Node *) subselect, 1))
 686                 return NULL;
 687
 688         /*
 689          * The left-hand expressions must contain some Vars of the current
 690          * query, else it's not gonna be a join.
 691          */
 692         left_varnos = pull_varnos((Node *) sublink->lefthand);
 693         if (bms_is_empty(left_varnos))
 694                 return NULL;
 695
 696         /*
 697          * The left-hand expressions mustn't be volatile.  (Perhaps we should
 698          * test the combining operators, too?  We'd only need to point the
 699          * function directly at the sublink ...)
 700          */
 701         if (contain_volatile_functions((Node *) sublink->lefthand))
 702                 return NULL;
 703
 704         /*
 705          * Okay, pull up the sub-select into top range table and jointree.
 706          *
 707          * We rely here on the assumption that the outer query has no references
 708          * to the inner (necessarily true, other than the Vars that we build
 709          * below).      Therefore this is a lot easier than what
 710          * pull_up_subqueries has to go through.
 711          */
 712         rte = addRangeTableEntryForSubquery(NULL,
 713                                                                                 subselect,
 714                                                                                 makeAlias("IN_subquery", NIL),
 715                                                                                 false);
 716         parse->rtable = lappend(parse->rtable, rte);
 717         rtindex = list_length(parse->rtable);
 718         rtr = makeNode(RangeTblRef);
 719         rtr->rtindex = rtindex;
 720         parse->jointree->fromlist = lappend(parse->jointree->fromlist, rtr);
 721
 722         /*
 723          * Now build the InClauseInfo node.
 724          */
 725         ininfo = makeNode(InClauseInfo);
 726         ininfo->lefthand = left_varnos;
 727         ininfo->righthand = bms_make_singleton(rtindex);
 728         root->in_info_list = lappend(root->in_info_list, ininfo);
 729
 730         /*
 731          * Build the result qual expressions.  As a side effect,
 732          * ininfo->sub_targetlist is filled with a list of Vars representing
 733          * the subselect outputs.
 734          */
 735         exprs = convert_sublink_opers(sublink->lefthand,
 736                                                                   sublink->operOids,
 737                                                                   subselect->targetList,
 738                                                                   rtindex,
 739                                                                   &ininfo->sub_targetlist);
 740         return (Node *) make_ands_explicit(exprs);
 741 }
 742
 743 /*
 744  * Replace correlation vars (uplevel vars) with Params.
 745  *
 746  * Uplevel aggregates are replaced, too.
 747  *
 748  * Note: it is critical that this runs immediately after SS_process_sublinks.
 749  * Since we do not recurse into the arguments of uplevel aggregates, they will
 750  * get copied to the appropriate subplan args list in the parent query with
 751  * uplevel vars not replaced by Params, but only adjusted in level (see
 752  * replace_outer_agg).  That's exactly what we want for the vars of the parent
 753  * level --- but if an aggregate's argument contains any further-up variables,
 754  * they have to be replaced with Params in their turn.  That will happen when
 755  * the parent level runs SS_replace_correlation_vars.  Therefore it must do
 756  * so after expanding its sublinks to subplans.  And we don't want any steps
 757  * in between, else those steps would never get applied to the aggregate
 758  * argument expressions, either in the parent or the child level.
 759  */
 760 Node *
 761 SS_replace_correlation_vars(Node *expr)
 762 {
 763         /* No setup needed for tree walk, so away we go */
 764         return replace_correlation_vars_mutator(expr, NULL);
 765 }
 766
 767 static Node *
 768 replace_correlation_vars_mutator(Node *node, void *context)
 769 {
 770         if (node == NULL)
 771                 return NULL;
 772         if (IsA(node, Var))
 773         {
 774                 if (((Var *) node)->varlevelsup > 0)
 775                         return (Node *) replace_outer_var((Var *) node);
 776         }
 777         if (IsA(node, Aggref))
 778         {
 779                 if (((Aggref *) node)->agglevelsup > 0)
 780                         return (Node *) replace_outer_agg((Aggref *) node);
 781         }
 782         return expression_tree_mutator(node,
 783                                                                    replace_correlation_vars_mutator,
 784                                                                    context);
 785 }
 786
 787 /*
 788  * Expand SubLinks to SubPlans in the given expression.
 789  *
 790  * The isQual argument tells whether or not this expression is a WHERE/HAVING
 791  * qualifier expression.  If it is, any sublinks appearing at top level need
 792  * not distinguish FALSE from UNKNOWN return values.
 793  */
 794 Node *
 795 SS_process_sublinks(Node *expr, bool isQual)
 796 {
 797         /* The only context needed is the initial are-we-in-a-qual flag */
 798         return process_sublinks_mutator(expr, &isQual);
 799 }
 800
 801 static Node *
 802 process_sublinks_mutator(Node *node, bool *isTopQual)
 803 {
 804         bool            locTopQual;
 805
 806         if (node == NULL)
 807                 return NULL;
 808         if (IsA(node, SubLink))
 809         {
 810                 SubLink    *sublink = (SubLink *) node;
 811                 List       *lefthand;
 812
 813                 /*
 814                  * First, recursively process the lefthand-side expressions, if
 815                  * any.
 816                  */
 817                 locTopQual = false;
 818                 lefthand = (List *)
 819                         process_sublinks_mutator((Node *) sublink->lefthand, &locTopQual);
 820
 821                 /*
 822                  * Now build the SubPlan node and make the expr to return.
 823                  */
 824                 return make_subplan(sublink, lefthand, *isTopQual);
 825         }
 826
 827         /*
 828          * We should never see a SubPlan expression in the input (since this
 829          * is the very routine that creates 'em to begin with).  We shouldn't
 830          * find ourselves invoked directly on a Query, either.
 831          */
 832         Assert(!is_subplan(node));
 833         Assert(!IsA(node, Query));
 834
 835         /*
 836          * Because make_subplan() could return an AND or OR clause, we have to
 837          * take steps to preserve AND/OR flatness of a qual.  We assume the
 838          * input has been AND/OR flattened and so we need no recursion here.
 839          *
 840          * If we recurse down through anything other than an AND node, we are
 841          * definitely not at top qual level anymore.  (Due to the coding here,
 842          * we will not get called on the List subnodes of an AND, so no check
 843          * is needed for List.)
 844          */
 845         if (and_clause(node))
 846         {
 847                 List       *newargs = NIL;
 848                 ListCell   *l;
 849
 850                 /* Still at qual top-level */
 851                 locTopQual = *isTopQual;
 852
 853                 foreach(l, ((BoolExpr *) node)->args)
 854                 {
 855                         Node       *newarg;
 856
 857                         newarg = process_sublinks_mutator(lfirst(l),
 858                                                                                           (void *) &locTopQual);
 859                         if (and_clause(newarg))
 860                                 newargs = list_concat(newargs, ((BoolExpr *) newarg)->args);
 861                         else
 862                                 newargs = lappend(newargs, newarg);
 863                 }
 864                 return (Node *) make_andclause(newargs);
 865         }
 866
 867         /* otherwise not at qual top-level */
 868         locTopQual = false;
 869
 870         if (or_clause(node))
 871         {
 872                 List       *newargs = NIL;
 873                 ListCell   *l;
 874
 875                 foreach(l, ((BoolExpr *) node)->args)
 876                 {
 877                         Node       *newarg;
 878
 879                         newarg = process_sublinks_mutator(lfirst(l),
 880                                                                                           (void *) &locTopQual);
 881                         if (or_clause(newarg))
 882                                 newargs = list_concat(newargs, ((BoolExpr *) newarg)->args);
 883                         else
 884                                 newargs = lappend(newargs, newarg);
 885                 }
 886                 return (Node *) make_orclause(newargs);
 887         }
 888
 889         return expression_tree_mutator(node,
 890                                                                    process_sublinks_mutator,
 891                                                                    (void *) &locTopQual);
 892 }
 893
 894 /*
 895  * SS_finalize_plan - do final sublink processing for a completed Plan.
 896  *
 897  * This recursively computes the extParam and allParam sets for every Plan
 898  * node in the given plan tree.  It also attaches any generated InitPlans
 899  * to the top plan node.
 900  */
 901 void
 902 SS_finalize_plan(Plan *plan, List *rtable)
 903 {
 904         Bitmapset  *outer_params = NULL;
 905         Bitmapset  *valid_params = NULL;
 906         Cost            initplan_cost = 0;
 907         int                     paramid;
 908         ListCell   *l;
 909
 910         /*
 911          * First, scan the param list to discover the sets of params that are
 912          * available from outer query levels and my own query level. We do
 913          * this once to save time in the per-plan recursion steps.
 914          */
 915         paramid = 0;
 916         foreach(l, PlannerParamList)
 917         {
 918                 PlannerParamItem *pitem = (PlannerParamItem *) lfirst(l);
 919
 920                 if (pitem->abslevel < PlannerQueryLevel)
 921                 {
 922                         /* valid outer-level parameter */
 923                         outer_params = bms_add_member(outer_params, paramid);
 924                         valid_params = bms_add_member(valid_params, paramid);
 925                 }
 926                 else if (pitem->abslevel == PlannerQueryLevel &&
 927                                  IsA(pitem->item, Param))
 928                 {
 929                         /* valid local parameter (i.e., a setParam of my child) */
 930                         valid_params = bms_add_member(valid_params, paramid);
 931                 }
 932
 933                 paramid++;
 934         }
 935
 936         /*
 937          * Now recurse through plan tree.
 938          */
 939         (void) finalize_plan(plan, rtable, outer_params, valid_params);
 940
 941         bms_free(outer_params);
 942         bms_free(valid_params);
 943
 944         /*
 945          * Finally, attach any initPlans to the topmost plan node,
 946          * and add their extParams to the topmost node's, too.
 947          *
 948          * We also add the total_cost of each initPlan to the startup cost of
 949          * the top node.  This is a conservative overestimate, since in
 950          * fact each initPlan might be executed later than plan startup,
 951          * or even not at all.
 952          */
 953         plan->initPlan = PlannerInitPlan;
 954         PlannerInitPlan = NIL;          /* make sure they're not attached twice */
 955
 956         foreach(l, plan->initPlan)
 957         {
 958                 SubPlan    *initplan = (SubPlan *) lfirst(l);
 959
 960                 plan->extParam = bms_add_members(plan->extParam,
 961                                                                                  initplan->plan->extParam);
 962                 /* allParam must include all members of extParam */
 963                 plan->allParam = bms_add_members(plan->allParam,
 964                                                                                  plan->extParam);
 965                 initplan_cost += initplan->plan->total_cost;
 966         }
 967
 968         plan->startup_cost += initplan_cost;
 969         plan->total_cost += initplan_cost;
 970 }
 971
 972 /*
 973  * Recursive processing of all nodes in the plan tree
 974  *
 975  * The return value is the computed allParam set for the given Plan node.
 976  * This is just an internal notational convenience.
 977  */
 978 static Bitmapset *
 979 finalize_plan(Plan *plan, List *rtable,
 980                           Bitmapset *outer_params, Bitmapset *valid_params)
 981 {
 982         finalize_primnode_context context;
 983
 984         if (plan == NULL)
 985                 return NULL;
 986
 987         context.paramids = NULL;        /* initialize set to empty */
 988         context.outer_params = outer_params;
 989
 990         /*
 991          * When we call finalize_primnode, context.paramids sets are
 992          * automatically merged together.  But when recursing to self, we have
 993          * to do it the hard way.  We want the paramids set to include params
 994          * in subplans as well as at this level.
 995          */
 996
 997         /* Find params in targetlist and qual */
 998         finalize_primnode((Node *) plan->targetlist, &context);
 999         finalize_primnode((Node *) plan->qual, &context);
1000
1001         /* Check additional node-type-specific fields */
1002         switch (nodeTag(plan))
1003         {
1004                 case T_Result:
1005                         finalize_primnode(((Result *) plan)->resconstantqual,
1006                                                           &context);
1007                         break;
1008
1009                 case T_IndexScan:
1010                         finalize_primnode((Node *) ((IndexScan *) plan)->indexqual,
1011                                                           &context);
1012
1013                         /*
1014                          * we need not look at indexqualorig, since it will have the
1015                          * same param references as indexqual.
1016                          */
1017                         break;
1018
1019                 case T_BitmapIndexScan:
1020                         finalize_primnode((Node *) ((BitmapIndexScan *) plan)->indexqual,
1021                                                           &context);
1022                         /*
1023                          * we need not look at indexqualorig, since it will have the
1024                          * same param references as indexqual.
1025                          */
1026                         break;
1027
1028                 case T_BitmapHeapScan:
1029                         finalize_primnode((Node *) ((BitmapHeapScan *) plan)->bitmapqualorig,
1030                                                           &context);
1031                         break;
1032
1033                 case T_TidScan:
1034                         finalize_primnode((Node *) ((TidScan *) plan)->tideval,
1035                                                           &context);
1036                         break;
1037
1038                 case T_SubqueryScan:
1039
1040                         /*
1041                          * In a SubqueryScan, SS_finalize_plan has already been run on
1042                          * the subplan by the inner invocation of subquery_planner, so
1043                          * there's no need to do it again.  Instead, just pull out the
1044                          * subplan's extParams list, which represents the params it
1045                          * needs from my level and higher levels.
1046                          */
1047                         context.paramids = bms_add_members(context.paramids,
1048                                                          ((SubqueryScan *) plan)->subplan->extParam);
1049                         break;
1050
1051                 case T_FunctionScan:
1052                         {
1053                                 RangeTblEntry *rte;
1054
1055                                 rte = rt_fetch(((FunctionScan *) plan)->scan.scanrelid,
1056                                                            rtable);
1057                                 Assert(rte->rtekind == RTE_FUNCTION);
1058                                 finalize_primnode(rte->funcexpr, &context);
1059                         }
1060                         break;
1061
1062                 case T_Append:
1063                         {
1064                                 ListCell   *l;
1065
1066                                 foreach(l, ((Append *) plan)->appendplans)
1067                                 {
1068                                         context.paramids =
1069                                                 bms_add_members(context.paramids,
1070                                                                                 finalize_plan((Plan *) lfirst(l),
1071                                                                                                           rtable,
1072                                                                                                           outer_params,
1073                                                                                                           valid_params));
1074                                 }
1075                         }
1076                         break;
1077
1078                 case T_BitmapAnd:
1079                         {
1080                                 ListCell   *l;
1081
1082                                 foreach(l, ((BitmapAnd *) plan)->bitmapplans)
1083                                 {
1084                                         context.paramids =
1085                                                 bms_add_members(context.paramids,
1086                                                                                 finalize_plan((Plan *) lfirst(l),
1087                                                                                                           rtable,
1088                                                                                                           outer_params,
1089                                                                                                           valid_params));
1090                                 }
1091                         }
1092                         break;
1093
1094                 case T_BitmapOr:
1095                         {
1096                                 ListCell   *l;
1097
1098                                 foreach(l, ((BitmapOr *) plan)->bitmapplans)
1099                                 {
1100                                         context.paramids =
1101                                                 bms_add_members(context.paramids,
1102                                                                                 finalize_plan((Plan *) lfirst(l),
1103                                                                                                           rtable,
1104                                                                                                           outer_params,
1105                                                                                                           valid_params));
1106                                 }
1107                         }
1108                         break;
1109
1110                 case T_NestLoop:
1111                         finalize_primnode((Node *) ((Join *) plan)->joinqual,
1112                                                           &context);
1113                         break;
1114
1115                 case T_MergeJoin:
1116                         finalize_primnode((Node *) ((Join *) plan)->joinqual,
1117                                                           &context);
1118                         finalize_primnode((Node *) ((MergeJoin *) plan)->mergeclauses,
1119                                                           &context);
1120                         break;
1121
1122                 case T_HashJoin:
1123                         finalize_primnode((Node *) ((Join *) plan)->joinqual,
1124                                                           &context);
1125                         finalize_primnode((Node *) ((HashJoin *) plan)->hashclauses,
1126                                                           &context);
1127                         break;
1128
1129                 case T_Limit:
1130                         finalize_primnode(((Limit *) plan)->limitOffset,
1131                                                           &context);
1132                         finalize_primnode(((Limit *) plan)->limitCount,
1133                                                           &context);
1134                         break;
1135
1136                 case T_Hash:
1137                 case T_Agg:
1138                 case T_SeqScan:
1139                 case T_Material:
1140                 case T_Sort:
1141                 case T_Unique:
1142                 case T_SetOp:
1143                 case T_Group:
1144                         break;
1145
1146                 default:
1147                         elog(ERROR, "unrecognized node type: %d",
1148                                  (int) nodeTag(plan));
1149         }
1150
1151         /* Process left and right child plans, if any */
1152         context.paramids = bms_add_members(context.paramids,
1153                                                                            finalize_plan(plan->lefttree,
1154                                                                                                          rtable,
1155                                                                                                          outer_params,
1156                                                                                                          valid_params));
1157
1158         context.paramids = bms_add_members(context.paramids,
1159                                                                            finalize_plan(plan->righttree,
1160                                                                                                          rtable,
1161                                                                                                          outer_params,
1162                                                                                                          valid_params));
1163
1164         /* Now we have all the paramids */
1165
1166         if (!bms_is_subset(context.paramids, valid_params))
1167                 elog(ERROR, "plan should not reference subplan's variable");
1168
1169         plan->extParam = bms_intersect(context.paramids, outer_params);
1170         plan->allParam = context.paramids;
1171
1172         /*
1173          * For speed at execution time, make sure extParam/allParam are
1174          * actually NULL if they are empty sets.
1175          */
1176         if (bms_is_empty(plan->extParam))
1177         {
1178                 bms_free(plan->extParam);
1179                 plan->extParam = NULL;
1180         }
1181         if (bms_is_empty(plan->allParam))
1182         {
1183                 bms_free(plan->allParam);
1184                 plan->allParam = NULL;
1185         }
1186
1187         return plan->allParam;
1188 }
1189
1190 /*
1191  * finalize_primnode: add IDs of all PARAM_EXEC params appearing in the given
1192  * expression tree to the result set.
1193  */
1194 static bool
1195 finalize_primnode(Node *node, finalize_primnode_context *context)
1196 {
1197         if (node == NULL)
1198                 return false;
1199         if (IsA(node, Param))
1200         {
1201                 if (((Param *) node)->paramkind == PARAM_EXEC)
1202                 {
1203                         int                     paramid = (int) ((Param *) node)->paramid;
1204
1205                         context->paramids = bms_add_member(context->paramids, paramid);
1206                 }
1207                 return false;                   /* no more to do here */
1208         }
1209         if (is_subplan(node))
1210         {
1211                 SubPlan    *subplan = (SubPlan *) node;
1212
1213                 /* Add outer-level params needed by the subplan to paramids */
1214                 context->paramids = bms_join(context->paramids,
1215                                                                    bms_intersect(subplan->plan->extParam,
1216                                                                                                  context->outer_params));
1217                 /* fall through to recurse into subplan args */
1218         }
1219         return expression_tree_walker(node, finalize_primnode,
1220                                                                   (void *) context);
1221 }
1222
1223 /*
1224  * SS_make_initplan_from_plan - given a plan tree, make it an InitPlan
1225  *
1226  * The plan is expected to return a scalar value of the indicated type.
1227  * We build an EXPR_SUBLINK SubPlan node and put it into the initplan
1228  * list for the current query level.  A Param that represents the initplan's
1229  * output is returned.
1230  *
1231  * We assume the plan hasn't been put through SS_finalize_plan.
1232  */
1233 Param *
1234 SS_make_initplan_from_plan(PlannerInfo *root, Plan *plan,
1235                                                    Oid resulttype, int32 resulttypmod)
1236 {
1237         List       *saved_initplan = PlannerInitPlan;
1238         SubPlan    *node;
1239         Param      *prm;
1240         Bitmapset  *tmpset;
1241         int                     paramid;
1242
1243         /*
1244          * Set up for a new level of subquery.  This is just to keep
1245          * SS_finalize_plan from becoming confused.
1246          */
1247         PlannerQueryLevel++;
1248         PlannerInitPlan = NIL;
1249
1250         /*
1251          * Build extParam/allParam sets for plan nodes.
1252          */
1253         SS_finalize_plan(plan, root->parse->rtable);
1254
1255         /* Return to outer subquery context */
1256         PlannerQueryLevel--;
1257         PlannerInitPlan = saved_initplan;
1258
1259         /*
1260          * Create a SubPlan node and add it to the outer list of InitPlans.
1261          */
1262         node = makeNode(SubPlan);
1263         node->subLinkType = EXPR_SUBLINK;
1264         node->plan = plan;
1265         node->plan_id = PlannerPlanId++;        /* Assign unique ID to this
1266                                                                                  * SubPlan */
1267
1268         node->rtable = root->parse->rtable;
1269
1270         PlannerInitPlan = lappend(PlannerInitPlan, node);
1271
1272         /*
1273          * Make parParam list of params that current query level will pass to
1274          * this child plan.  (In current usage there probably aren't any.)
1275          */
1276         tmpset = bms_copy(plan->extParam);
1277         while ((paramid = bms_first_member(tmpset)) >= 0)
1278         {
1279                 PlannerParamItem *pitem = list_nth(PlannerParamList, paramid);
1280
1281                 if (pitem->abslevel == PlannerQueryLevel)
1282                         node->parParam = lappend_int(node->parParam, paramid);
1283         }
1284         bms_free(tmpset);
1285
1286         /*
1287          * Make a Param that will be the subplan's output.
1288          */
1289         prm = generate_new_param(resulttype, resulttypmod);
1290         node->setParam = list_make1_int(prm->paramid);
1291
1292         return prm;
1293 }