granicus.if.org Git - postgresql/blob - src/backend/executor/nodeSubplan.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * nodeSubplan.c
   4  *        routines to support subselects
   5  *
   6  * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  * IDENTIFICATION
  10  *        src/backend/executor/nodeSubplan.c
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 /*
  15  *       INTERFACE ROUTINES
  16  *              ExecSubPlan  - process a subselect
  17  *              ExecInitSubPlan - initialize a subselect
  18  */
  19 #include "postgres.h"
  20
  21 #include <math.h>
  22
  23 #include "executor/executor.h"
  24 #include "executor/nodeSubplan.h"
  25 #include "nodes/makefuncs.h"
  26 #include "optimizer/clauses.h"
  27 #include "utils/lsyscache.h"
  28 #include "utils/memutils.h"
  29
  30
  31 static Datum ExecSubPlan(SubPlanState *node,
  32                         ExprContext *econtext,
  33                         bool *isNull,
  34                         ExprDoneCond *isDone);
  35 static Datum ExecAlternativeSubPlan(AlternativeSubPlanState *node,
  36                                            ExprContext *econtext,
  37                                            bool *isNull,
  38                                            ExprDoneCond *isDone);
  39 static Datum ExecHashSubPlan(SubPlanState *node,
  40                                 ExprContext *econtext,
  41                                 bool *isNull);
  42 static Datum ExecScanSubPlan(SubPlanState *node,
  43                                 ExprContext *econtext,
  44                                 bool *isNull);
  45 static void buildSubPlanHash(SubPlanState *node, ExprContext *econtext);
  46 static bool findPartialMatch(TupleHashTable hashtable, TupleTableSlot *slot);
  47 static bool slotAllNulls(TupleTableSlot *slot);
  48 static bool slotNoNulls(TupleTableSlot *slot);
  49
  50
  51 /* ----------------------------------------------------------------
  52  *              ExecSubPlan
  53  * ----------------------------------------------------------------
  54  */
  55 static Datum
  56 ExecSubPlan(SubPlanState *node,
  57                         ExprContext *econtext,
  58                         bool *isNull,
  59                         ExprDoneCond *isDone)
  60 {
  61         SubPlan    *subplan = (SubPlan *) node->xprstate.expr;
  62
  63         /* Set default values for result flags: non-null, not a set result */
  64         *isNull = false;
  65         if (isDone)
  66                 *isDone = ExprSingleResult;
  67
  68         /* Sanity checks */
  69         if (subplan->subLinkType == CTE_SUBLINK)
  70                 elog(ERROR, "CTE subplans should not be executed via ExecSubPlan");
  71         if (subplan->setParam != NIL)
  72                 elog(ERROR, "cannot set parent params from subquery");
  73
  74         /* Select appropriate evaluation strategy */
  75         if (subplan->useHashTable)
  76                 return ExecHashSubPlan(node, econtext, isNull);
  77         else
  78                 return ExecScanSubPlan(node, econtext, isNull);
  79 }
  80
  81 /*
  82  * ExecHashSubPlan: store subselect result in an in-memory hash table
  83  */
  84 static Datum
  85 ExecHashSubPlan(SubPlanState *node,
  86                                 ExprContext *econtext,
  87                                 bool *isNull)
  88 {
  89         SubPlan    *subplan = (SubPlan *) node->xprstate.expr;
  90         PlanState  *planstate = node->planstate;
  91         TupleTableSlot *slot;
  92
  93         /* Shouldn't have any direct correlation Vars */
  94         if (subplan->parParam != NIL || node->args != NIL)
  95                 elog(ERROR, "hashed subplan with direct correlation not supported");
  96
  97         /*
  98          * If first time through or we need to rescan the subplan, build the hash
  99          * table.
 100          */
 101         if (node->hashtable == NULL || planstate->chgParam != NULL)
 102                 buildSubPlanHash(node, econtext);
 103
 104         /*
 105          * The result for an empty subplan is always FALSE; no need to evaluate
 106          * lefthand side.
 107          */
 108         *isNull = false;
 109         if (!node->havehashrows && !node->havenullrows)
 110                 return BoolGetDatum(false);
 111
 112         /*
 113          * Evaluate lefthand expressions and form a projection tuple. First we
 114          * have to set the econtext to use (hack alert!).
 115          */
 116         node->projLeft->pi_exprContext = econtext;
 117         slot = ExecProject(node->projLeft, NULL);
 118
 119         /*
 120          * Note: because we are typically called in a per-tuple context, we have
 121          * to explicitly clear the projected tuple before returning. Otherwise,
 122          * we'll have a double-free situation: the per-tuple context will probably
 123          * be reset before we're called again, and then the tuple slot will think
 124          * it still needs to free the tuple.
 125          */
 126
 127         /*
 128          * If the LHS is all non-null, probe for an exact match in the main hash
 129          * table.  If we find one, the result is TRUE. Otherwise, scan the
 130          * partly-null table to see if there are any rows that aren't provably
 131          * unequal to the LHS; if so, the result is UNKNOWN.  (We skip that part
 132          * if we don't care about UNKNOWN.) Otherwise, the result is FALSE.
 133          *
 134          * Note: the reason we can avoid a full scan of the main hash table is
 135          * that the combining operators are assumed never to yield NULL when both
 136          * inputs are non-null.  If they were to do so, we might need to produce
 137          * UNKNOWN instead of FALSE because of an UNKNOWN result in comparing the
 138          * LHS to some main-table entry --- which is a comparison we will not even
 139          * make, unless there's a chance match of hash keys.
 140          */
 141         if (slotNoNulls(slot))
 142         {
 143                 if (node->havehashrows &&
 144                         FindTupleHashEntry(node->hashtable,
 145                                                            slot,
 146                                                            node->cur_eq_funcs,
 147                                                            node->lhs_hash_funcs) != NULL)
 148                 {
 149                         ExecClearTuple(slot);
 150                         return BoolGetDatum(true);
 151                 }
 152                 if (node->havenullrows &&
 153                         findPartialMatch(node->hashnulls, slot))
 154                 {
 155                         ExecClearTuple(slot);
 156                         *isNull = true;
 157                         return BoolGetDatum(false);
 158                 }
 159                 ExecClearTuple(slot);
 160                 return BoolGetDatum(false);
 161         }
 162
 163         /*
 164          * When the LHS is partly or wholly NULL, we can never return TRUE. If we
 165          * don't care about UNKNOWN, just return FALSE.  Otherwise, if the LHS is
 166          * wholly NULL, immediately return UNKNOWN.  (Since the combining
 167          * operators are strict, the result could only be FALSE if the sub-select
 168          * were empty, but we already handled that case.) Otherwise, we must scan
 169          * both the main and partly-null tables to see if there are any rows that
 170          * aren't provably unequal to the LHS; if so, the result is UNKNOWN.
 171          * Otherwise, the result is FALSE.
 172          */
 173         if (node->hashnulls == NULL)
 174         {
 175                 ExecClearTuple(slot);
 176                 return BoolGetDatum(false);
 177         }
 178         if (slotAllNulls(slot))
 179         {
 180                 ExecClearTuple(slot);
 181                 *isNull = true;
 182                 return BoolGetDatum(false);
 183         }
 184         /* Scan partly-null table first, since more likely to get a match */
 185         if (node->havenullrows &&
 186                 findPartialMatch(node->hashnulls, slot))
 187         {
 188                 ExecClearTuple(slot);
 189                 *isNull = true;
 190                 return BoolGetDatum(false);
 191         }
 192         if (node->havehashrows &&
 193                 findPartialMatch(node->hashtable, slot))
 194         {
 195                 ExecClearTuple(slot);
 196                 *isNull = true;
 197                 return BoolGetDatum(false);
 198         }
 199         ExecClearTuple(slot);
 200         return BoolGetDatum(false);
 201 }
 202
 203 /*
 204  * ExecScanSubPlan: default case where we have to rescan subplan each time
 205  */
 206 static Datum
 207 ExecScanSubPlan(SubPlanState *node,
 208                                 ExprContext *econtext,
 209                                 bool *isNull)
 210 {
 211         SubPlan    *subplan = (SubPlan *) node->xprstate.expr;
 212         PlanState  *planstate = node->planstate;
 213         SubLinkType subLinkType = subplan->subLinkType;
 214         MemoryContext oldcontext;
 215         TupleTableSlot *slot;
 216         Datum           result;
 217         bool            found = false;  /* TRUE if got at least one subplan tuple */
 218         ListCell   *pvar;
 219         ListCell   *l;
 220         ArrayBuildState *astate = NULL;
 221
 222         /*
 223          * We are probably in a short-lived expression-evaluation context. Switch
 224          * to the per-query context for manipulating the child plan's chgParam,
 225          * calling ExecProcNode on it, etc.
 226          */
 227         oldcontext = MemoryContextSwitchTo(econtext->ecxt_per_query_memory);
 228
 229         /*
 230          * Set Params of this plan from parent plan correlation values. (Any
 231          * calculation we have to do is done in the parent econtext, since the
 232          * Param values don't need to have per-query lifetime.)
 233          */
 234         Assert(list_length(subplan->parParam) == list_length(node->args));
 235
 236         forboth(l, subplan->parParam, pvar, node->args)
 237         {
 238                 int                     paramid = lfirst_int(l);
 239                 ParamExecData *prm = &(econtext->ecxt_param_exec_vals[paramid]);
 240
 241                 prm->value = ExecEvalExprSwitchContext((ExprState *) lfirst(pvar),
 242                                                                                            econtext,
 243                                                                                            &(prm->isnull),
 244                                                                                            NULL);
 245                 planstate->chgParam = bms_add_member(planstate->chgParam, paramid);
 246         }
 247
 248         /*
 249          * Now that we've set up its parameters, we can reset the subplan.
 250          */
 251         ExecReScan(planstate);
 252
 253         /*
 254          * For all sublink types except EXPR_SUBLINK and ARRAY_SUBLINK, the result
 255          * is boolean as are the results of the combining operators. We combine
 256          * results across tuples (if the subplan produces more than one) using OR
 257          * semantics for ANY_SUBLINK or AND semantics for ALL_SUBLINK.
 258          * (ROWCOMPARE_SUBLINK doesn't allow multiple tuples from the subplan.)
 259          * NULL results from the combining operators are handled according to the
 260          * usual SQL semantics for OR and AND.  The result for no input tuples is
 261          * FALSE for ANY_SUBLINK, TRUE for ALL_SUBLINK, NULL for
 262          * ROWCOMPARE_SUBLINK.
 263          *
 264          * For EXPR_SUBLINK we require the subplan to produce no more than one
 265          * tuple, else an error is raised.      If zero tuples are produced, we return
 266          * NULL.  Assuming we get a tuple, we just use its first column (there can
 267          * be only one non-junk column in this case).
 268          *
 269          * For ARRAY_SUBLINK we allow the subplan to produce any number of tuples,
 270          * and form an array of the first column's values.  Note in particular
 271          * that we produce a zero-element array if no tuples are produced (this is
 272          * a change from pre-8.3 behavior of returning NULL).
 273          */
 274         result = BoolGetDatum(subLinkType == ALL_SUBLINK);
 275         *isNull = false;
 276
 277         for (slot = ExecProcNode(planstate);
 278                  !TupIsNull(slot);
 279                  slot = ExecProcNode(planstate))
 280         {
 281                 TupleDesc       tdesc = slot->tts_tupleDescriptor;
 282                 Datum           rowresult;
 283                 bool            rownull;
 284                 int                     col;
 285                 ListCell   *plst;
 286
 287                 if (subLinkType == EXISTS_SUBLINK)
 288                 {
 289                         found = true;
 290                         result = BoolGetDatum(true);
 291                         break;
 292                 }
 293
 294                 if (subLinkType == EXPR_SUBLINK)
 295                 {
 296                         /* cannot allow multiple input tuples for EXPR sublink */
 297                         if (found)
 298                                 ereport(ERROR,
 299                                                 (errcode(ERRCODE_CARDINALITY_VIOLATION),
 300                                                  errmsg("more than one row returned by a subquery used as an expression")));
 301                         found = true;
 302
 303                         /*
 304                          * We need to copy the subplan's tuple in case the result is of
 305                          * pass-by-ref type --- our return value will point into this
 306                          * copied tuple!  Can't use the subplan's instance of the tuple
 307                          * since it won't still be valid after next ExecProcNode() call.
 308                          * node->curTuple keeps track of the copied tuple for eventual
 309                          * freeing.
 310                          */
 311                         if (node->curTuple)
 312                                 heap_freetuple(node->curTuple);
 313                         node->curTuple = ExecCopySlotTuple(slot);
 314
 315                         result = heap_getattr(node->curTuple, 1, tdesc, isNull);
 316                         /* keep scanning subplan to make sure there's only one tuple */
 317                         continue;
 318                 }
 319
 320                 if (subLinkType == ARRAY_SUBLINK)
 321                 {
 322                         Datum           dvalue;
 323                         bool            disnull;
 324
 325                         found = true;
 326                         /* stash away current value */
 327                         Assert(subplan->firstColType == tdesc->attrs[0]->atttypid);
 328                         dvalue = slot_getattr(slot, 1, &disnull);
 329                         astate = accumArrayResult(astate, dvalue, disnull,
 330                                                                           subplan->firstColType, oldcontext);
 331                         /* keep scanning subplan to collect all values */
 332                         continue;
 333                 }
 334
 335                 /* cannot allow multiple input tuples for ROWCOMPARE sublink either */
 336                 if (subLinkType == ROWCOMPARE_SUBLINK && found)
 337                         ereport(ERROR,
 338                                         (errcode(ERRCODE_CARDINALITY_VIOLATION),
 339                                          errmsg("more than one row returned by a subquery used as an expression")));
 340
 341                 found = true;
 342
 343                 /*
 344                  * For ALL, ANY, and ROWCOMPARE sublinks, load up the Params
 345                  * representing the columns of the sub-select, and then evaluate the
 346                  * combining expression.
 347                  */
 348                 col = 1;
 349                 foreach(plst, subplan->paramIds)
 350                 {
 351                         int                     paramid = lfirst_int(plst);
 352                         ParamExecData *prmdata;
 353
 354                         prmdata = &(econtext->ecxt_param_exec_vals[paramid]);
 355                         Assert(prmdata->execPlan == NULL);
 356                         prmdata->value = slot_getattr(slot, col, &(prmdata->isnull));
 357                         col++;
 358                 }
 359
 360                 rowresult = ExecEvalExprSwitchContext(node->testexpr, econtext,
 361                                                                                           &rownull, NULL);
 362
 363                 if (subLinkType == ANY_SUBLINK)
 364                 {
 365                         /* combine across rows per OR semantics */
 366                         if (rownull)
 367                                 *isNull = true;
 368                         else if (DatumGetBool(rowresult))
 369                         {
 370                                 result = BoolGetDatum(true);
 371                                 *isNull = false;
 372                                 break;                  /* needn't look at any more rows */
 373                         }
 374                 }
 375                 else if (subLinkType == ALL_SUBLINK)
 376                 {
 377                         /* combine across rows per AND semantics */
 378                         if (rownull)
 379                                 *isNull = true;
 380                         else if (!DatumGetBool(rowresult))
 381                         {
 382                                 result = BoolGetDatum(false);
 383                                 *isNull = false;
 384                                 break;                  /* needn't look at any more rows */
 385                         }
 386                 }
 387                 else
 388                 {
 389                         /* must be ROWCOMPARE_SUBLINK */
 390                         result = rowresult;
 391                         *isNull = rownull;
 392                 }
 393         }
 394
 395         MemoryContextSwitchTo(oldcontext);
 396
 397         if (subLinkType == ARRAY_SUBLINK)
 398         {
 399                 /* We return the result in the caller's context */
 400                 if (astate != NULL)
 401                         result = makeArrayResult(astate, oldcontext);
 402                 else
 403                         result = PointerGetDatum(construct_empty_array(subplan->firstColType));
 404         }
 405         else if (!found)
 406         {
 407                 /*
 408                  * deal with empty subplan result.      result/isNull were previously
 409                  * initialized correctly for all sublink types except EXPR and
 410                  * ROWCOMPARE; for those, return NULL.
 411                  */
 412                 if (subLinkType == EXPR_SUBLINK ||
 413                         subLinkType == ROWCOMPARE_SUBLINK)
 414                 {
 415                         result = (Datum) 0;
 416                         *isNull = true;
 417                 }
 418         }
 419
 420         return result;
 421 }
 422
 423 /*
 424  * buildSubPlanHash: load hash table by scanning subplan output.
 425  */
 426 static void
 427 buildSubPlanHash(SubPlanState *node, ExprContext *econtext)
 428 {
 429         SubPlan    *subplan = (SubPlan *) node->xprstate.expr;
 430         PlanState  *planstate = node->planstate;
 431         int                     ncols = list_length(subplan->paramIds);
 432         ExprContext *innerecontext = node->innerecontext;
 433         MemoryContext oldcontext;
 434         long            nbuckets;
 435         TupleTableSlot *slot;
 436
 437         Assert(subplan->subLinkType == ANY_SUBLINK);
 438
 439         /*
 440          * If we already had any hash tables, destroy 'em; then create empty hash
 441          * table(s).
 442          *
 443          * If we need to distinguish accurately between FALSE and UNKNOWN (i.e.,
 444          * NULL) results of the IN operation, then we have to store subplan output
 445          * rows that are partly or wholly NULL.  We store such rows in a separate
 446          * hash table that we expect will be much smaller than the main table. (We
 447          * can use hashing to eliminate partly-null rows that are not distinct. We
 448          * keep them separate to minimize the cost of the inevitable full-table
 449          * searches; see findPartialMatch.)
 450          *
 451          * If it's not necessary to distinguish FALSE and UNKNOWN, then we don't
 452          * need to store subplan output rows that contain NULL.
 453          */
 454         MemoryContextReset(node->hashtablecxt);
 455         node->hashtable = NULL;
 456         node->hashnulls = NULL;
 457         node->havehashrows = false;
 458         node->havenullrows = false;
 459
 460         nbuckets = (long) Min(planstate->plan->plan_rows, (double) LONG_MAX);
 461         if (nbuckets < 1)
 462                 nbuckets = 1;
 463
 464         node->hashtable = BuildTupleHashTable(ncols,
 465                                                                                   node->keyColIdx,
 466                                                                                   node->tab_eq_funcs,
 467                                                                                   node->tab_hash_funcs,
 468                                                                                   nbuckets,
 469                                                                                   sizeof(TupleHashEntryData),
 470                                                                                   node->hashtablecxt,
 471                                                                                   node->hashtempcxt);
 472
 473         if (!subplan->unknownEqFalse)
 474         {
 475                 if (ncols == 1)
 476                         nbuckets = 1;           /* there can only be one entry */
 477                 else
 478                 {
 479                         nbuckets /= 16;
 480                         if (nbuckets < 1)
 481                                 nbuckets = 1;
 482                 }
 483                 node->hashnulls = BuildTupleHashTable(ncols,
 484                                                                                           node->keyColIdx,
 485                                                                                           node->tab_eq_funcs,
 486                                                                                           node->tab_hash_funcs,
 487                                                                                           nbuckets,
 488                                                                                           sizeof(TupleHashEntryData),
 489                                                                                           node->hashtablecxt,
 490                                                                                           node->hashtempcxt);
 491         }
 492
 493         /*
 494          * We are probably in a short-lived expression-evaluation context. Switch
 495          * to the per-query context for manipulating the child plan.
 496          */
 497         oldcontext = MemoryContextSwitchTo(econtext->ecxt_per_query_memory);
 498
 499         /*
 500          * Reset subplan to start.
 501          */
 502         ExecReScan(planstate);
 503
 504         /*
 505          * Scan the subplan and load the hash table(s).  Note that when there are
 506          * duplicate rows coming out of the sub-select, only one copy is stored.
 507          */
 508         for (slot = ExecProcNode(planstate);
 509                  !TupIsNull(slot);
 510                  slot = ExecProcNode(planstate))
 511         {
 512                 int                     col = 1;
 513                 ListCell   *plst;
 514                 bool            isnew;
 515
 516                 /*
 517                  * Load up the Params representing the raw sub-select outputs, then
 518                  * form the projection tuple to store in the hashtable.
 519                  */
 520                 foreach(plst, subplan->paramIds)
 521                 {
 522                         int                     paramid = lfirst_int(plst);
 523                         ParamExecData *prmdata;
 524
 525                         prmdata = &(innerecontext->ecxt_param_exec_vals[paramid]);
 526                         Assert(prmdata->execPlan == NULL);
 527                         prmdata->value = slot_getattr(slot, col,
 528                                                                                   &(prmdata->isnull));
 529                         col++;
 530                 }
 531                 slot = ExecProject(node->projRight, NULL);
 532
 533                 /*
 534                  * If result contains any nulls, store separately or not at all.
 535                  */
 536                 if (slotNoNulls(slot))
 537                 {
 538                         (void) LookupTupleHashEntry(node->hashtable, slot, &isnew);
 539                         node->havehashrows = true;
 540                 }
 541                 else if (node->hashnulls)
 542                 {
 543                         (void) LookupTupleHashEntry(node->hashnulls, slot, &isnew);
 544                         node->havenullrows = true;
 545                 }
 546
 547                 /*
 548                  * Reset innerecontext after each inner tuple to free any memory used
 549                  * during ExecProject.
 550                  */
 551                 ResetExprContext(innerecontext);
 552         }
 553
 554         /*
 555          * Since the projected tuples are in the sub-query's context and not the
 556          * main context, we'd better clear the tuple slot before there's any
 557          * chance of a reset of the sub-query's context.  Else we will have the
 558          * potential for a double free attempt.  (XXX possibly no longer needed,
 559          * but can't hurt.)
 560          */
 561         ExecClearTuple(node->projRight->pi_slot);
 562
 563         MemoryContextSwitchTo(oldcontext);
 564 }
 565
 566 /*
 567  * findPartialMatch: does the hashtable contain an entry that is not
 568  * provably distinct from the tuple?
 569  *
 570  * We have to scan the whole hashtable; we can't usefully use hashkeys
 571  * to guide probing, since we might get partial matches on tuples with
 572  * hashkeys quite unrelated to what we'd get from the given tuple.
 573  */
 574 static bool
 575 findPartialMatch(TupleHashTable hashtable, TupleTableSlot *slot)
 576 {
 577         int                     numCols = hashtable->numCols;
 578         AttrNumber *keyColIdx = hashtable->keyColIdx;
 579         TupleHashIterator hashiter;
 580         TupleHashEntry entry;
 581
 582         InitTupleHashIterator(hashtable, &hashiter);
 583         while ((entry = ScanTupleHashTable(&hashiter)) != NULL)
 584         {
 585                 ExecStoreMinimalTuple(entry->firstTuple, hashtable->tableslot, false);
 586                 if (!execTuplesUnequal(slot, hashtable->tableslot,
 587                                                            numCols, keyColIdx,
 588                                                            hashtable->cur_eq_funcs,
 589                                                            hashtable->tempcxt))
 590                 {
 591                         TermTupleHashIterator(&hashiter);
 592                         return true;
 593                 }
 594         }
 595         /* No TermTupleHashIterator call needed here */
 596         return false;
 597 }
 598
 599 /*
 600  * slotAllNulls: is the slot completely NULL?
 601  *
 602  * This does not test for dropped columns, which is OK because we only
 603  * use it on projected tuples.
 604  */
 605 static bool
 606 slotAllNulls(TupleTableSlot *slot)
 607 {
 608         int                     ncols = slot->tts_tupleDescriptor->natts;
 609         int                     i;
 610
 611         for (i = 1; i <= ncols; i++)
 612         {
 613                 if (!slot_attisnull(slot, i))
 614                         return false;
 615         }
 616         return true;
 617 }
 618
 619 /*
 620  * slotNoNulls: is the slot entirely not NULL?
 621  *
 622  * This does not test for dropped columns, which is OK because we only
 623  * use it on projected tuples.
 624  */
 625 static bool
 626 slotNoNulls(TupleTableSlot *slot)
 627 {
 628         int                     ncols = slot->tts_tupleDescriptor->natts;
 629         int                     i;
 630
 631         for (i = 1; i <= ncols; i++)
 632         {
 633                 if (slot_attisnull(slot, i))
 634                         return false;
 635         }
 636         return true;
 637 }
 638
 639 /* ----------------------------------------------------------------
 640  *              ExecInitSubPlan
 641  *
 642  * Create a SubPlanState for a SubPlan; this is the SubPlan-specific part
 643  * of ExecInitExpr().  We split it out so that it can be used for InitPlans
 644  * as well as regular SubPlans.  Note that we don't link the SubPlan into
 645  * the parent's subPlan list, because that shouldn't happen for InitPlans.
 646  * Instead, ExecInitExpr() does that one part.
 647  * ----------------------------------------------------------------
 648  */
 649 SubPlanState *
 650 ExecInitSubPlan(SubPlan *subplan, PlanState *parent)
 651 {
 652         SubPlanState *sstate = makeNode(SubPlanState);
 653         EState     *estate = parent->state;
 654
 655         sstate->xprstate.evalfunc = (ExprStateEvalFunc) ExecSubPlan;
 656         sstate->xprstate.expr = (Expr *) subplan;
 657
 658         /* Link the SubPlanState to already-initialized subplan */
 659         sstate->planstate = (PlanState *) list_nth(estate->es_subplanstates,
 660                                                                                            subplan->plan_id - 1);
 661
 662         /* Initialize subexpressions */
 663         sstate->testexpr = ExecInitExpr((Expr *) subplan->testexpr, parent);
 664         sstate->args = (List *) ExecInitExpr((Expr *) subplan->args, parent);
 665
 666         /*
 667          * initialize my state
 668          */
 669         sstate->curTuple = NULL;
 670         sstate->projLeft = NULL;
 671         sstate->projRight = NULL;
 672         sstate->hashtable = NULL;
 673         sstate->hashnulls = NULL;
 674         sstate->hashtablecxt = NULL;
 675         sstate->hashtempcxt = NULL;
 676         sstate->innerecontext = NULL;
 677         sstate->keyColIdx = NULL;
 678         sstate->tab_hash_funcs = NULL;
 679         sstate->tab_eq_funcs = NULL;
 680         sstate->lhs_hash_funcs = NULL;
 681         sstate->cur_eq_funcs = NULL;
 682
 683         /*
 684          * If this plan is un-correlated or undirect correlated one and want to
 685          * set params for parent plan then mark parameters as needing evaluation.
 686          *
 687          * A CTE subplan's output parameter is never to be evaluated in the normal
 688          * way, so skip this in that case.
 689          *
 690          * Note that in the case of un-correlated subqueries we don't care about
 691          * setting parent->chgParam here: indices take care about it, for others -
 692          * it doesn't matter...
 693          */
 694         if (subplan->setParam != NIL && subplan->subLinkType != CTE_SUBLINK)
 695         {
 696                 ListCell   *lst;
 697
 698                 foreach(lst, subplan->setParam)
 699                 {
 700                         int                     paramid = lfirst_int(lst);
 701                         ParamExecData *prm = &(estate->es_param_exec_vals[paramid]);
 702
 703                         prm->execPlan = sstate;
 704                 }
 705         }
 706
 707         /*
 708          * If we are going to hash the subquery output, initialize relevant stuff.
 709          * (We don't create the hashtable until needed, though.)
 710          */
 711         if (subplan->useHashTable)
 712         {
 713                 int                     ncols,
 714                                         i;
 715                 TupleDesc       tupDesc;
 716                 TupleTableSlot *slot;
 717                 List       *oplist,
 718                                    *lefttlist,
 719                                    *righttlist,
 720                                    *leftptlist,
 721                                    *rightptlist;
 722                 ListCell   *l;
 723
 724                 /* We need a memory context to hold the hash table(s) */
 725                 sstate->hashtablecxt =
 726                         AllocSetContextCreate(CurrentMemoryContext,
 727                                                                   "Subplan HashTable Context",
 728                                                                   ALLOCSET_DEFAULT_MINSIZE,
 729                                                                   ALLOCSET_DEFAULT_INITSIZE,
 730                                                                   ALLOCSET_DEFAULT_MAXSIZE);
 731                 /* and a small one for the hash tables to use as temp storage */
 732                 sstate->hashtempcxt =
 733                         AllocSetContextCreate(CurrentMemoryContext,
 734                                                                   "Subplan HashTable Temp Context",
 735                                                                   ALLOCSET_SMALL_MINSIZE,
 736                                                                   ALLOCSET_SMALL_INITSIZE,
 737                                                                   ALLOCSET_SMALL_MAXSIZE);
 738                 /* and a short-lived exprcontext for function evaluation */
 739                 sstate->innerecontext = CreateExprContext(estate);
 740                 /* Silly little array of column numbers 1..n */
 741                 ncols = list_length(subplan->paramIds);
 742                 sstate->keyColIdx = (AttrNumber *) palloc(ncols * sizeof(AttrNumber));
 743                 for (i = 0; i < ncols; i++)
 744                         sstate->keyColIdx[i] = i + 1;
 745
 746                 /*
 747                  * We use ExecProject to evaluate the lefthand and righthand
 748                  * expression lists and form tuples.  (You might think that we could
 749                  * use the sub-select's output tuples directly, but that is not the
 750                  * case if we had to insert any run-time coercions of the sub-select's
 751                  * output datatypes; anyway this avoids storing any resjunk columns
 752                  * that might be in the sub-select's output.) Run through the
 753                  * combining expressions to build tlists for the lefthand and
 754                  * righthand sides.  We need both the ExprState list (for ExecProject)
 755                  * and the underlying parse Exprs (for ExecTypeFromTL).
 756                  *
 757                  * We also extract the combining operators themselves to initialize
 758                  * the equality and hashing functions for the hash tables.
 759                  */
 760                 if (IsA(sstate->testexpr->expr, OpExpr))
 761                 {
 762                         /* single combining operator */
 763                         oplist = list_make1(sstate->testexpr);
 764                 }
 765                 else if (and_clause((Node *) sstate->testexpr->expr))
 766                 {
 767                         /* multiple combining operators */
 768                         Assert(IsA(sstate->testexpr, BoolExprState));
 769                         oplist = ((BoolExprState *) sstate->testexpr)->args;
 770                 }
 771                 else
 772                 {
 773                         /* shouldn't see anything else in a hashable subplan */
 774                         elog(ERROR, "unrecognized testexpr type: %d",
 775                                  (int) nodeTag(sstate->testexpr->expr));
 776                         oplist = NIL;           /* keep compiler quiet */
 777                 }
 778                 Assert(list_length(oplist) == ncols);
 779
 780                 lefttlist = righttlist = NIL;
 781                 leftptlist = rightptlist = NIL;
 782                 sstate->tab_hash_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
 783                 sstate->tab_eq_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
 784                 sstate->lhs_hash_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
 785                 sstate->cur_eq_funcs = (FmgrInfo *) palloc(ncols * sizeof(FmgrInfo));
 786                 i = 1;
 787                 foreach(l, oplist)
 788                 {
 789                         FuncExprState *fstate = (FuncExprState *) lfirst(l);
 790                         OpExpr     *opexpr = (OpExpr *) fstate->xprstate.expr;
 791                         ExprState  *exstate;
 792                         Expr       *expr;
 793                         TargetEntry *tle;
 794                         GenericExprState *tlestate;
 795                         Oid                     rhs_eq_oper;
 796                         Oid                     left_hashfn;
 797                         Oid                     right_hashfn;
 798
 799                         Assert(IsA(fstate, FuncExprState));
 800                         Assert(IsA(opexpr, OpExpr));
 801                         Assert(list_length(fstate->args) == 2);
 802
 803                         /* Process lefthand argument */
 804                         exstate = (ExprState *) linitial(fstate->args);
 805                         expr = exstate->expr;
 806                         tle = makeTargetEntry(expr,
 807                                                                   i,
 808                                                                   NULL,
 809                                                                   false);
 810                         tlestate = makeNode(GenericExprState);
 811                         tlestate->xprstate.expr = (Expr *) tle;
 812                         tlestate->xprstate.evalfunc = NULL;
 813                         tlestate->arg = exstate;
 814                         lefttlist = lappend(lefttlist, tlestate);
 815                         leftptlist = lappend(leftptlist, tle);
 816
 817                         /* Process righthand argument */
 818                         exstate = (ExprState *) lsecond(fstate->args);
 819                         expr = exstate->expr;
 820                         tle = makeTargetEntry(expr,
 821                                                                   i,
 822                                                                   NULL,
 823                                                                   false);
 824                         tlestate = makeNode(GenericExprState);
 825                         tlestate->xprstate.expr = (Expr *) tle;
 826                         tlestate->xprstate.evalfunc = NULL;
 827                         tlestate->arg = exstate;
 828                         righttlist = lappend(righttlist, tlestate);
 829                         rightptlist = lappend(rightptlist, tle);
 830
 831                         /* Lookup the equality function (potentially cross-type) */
 832                         fmgr_info(opexpr->opfuncid, &sstate->cur_eq_funcs[i - 1]);
 833                         fmgr_info_set_expr((Node *) opexpr, &sstate->cur_eq_funcs[i - 1]);
 834
 835                         /* Look up the equality function for the RHS type */
 836                         if (!get_compatible_hash_operators(opexpr->opno,
 837                                                                                            NULL, &rhs_eq_oper))
 838                                 elog(ERROR, "could not find compatible hash operator for operator %u",
 839                                          opexpr->opno);
 840                         fmgr_info(get_opcode(rhs_eq_oper), &sstate->tab_eq_funcs[i - 1]);
 841
 842                         /* Lookup the associated hash functions */
 843                         if (!get_op_hash_functions(opexpr->opno,
 844                                                                            &left_hashfn, &right_hashfn))
 845                                 elog(ERROR, "could not find hash function for hash operator %u",
 846                                          opexpr->opno);
 847                         fmgr_info(left_hashfn, &sstate->lhs_hash_funcs[i - 1]);
 848                         fmgr_info(right_hashfn, &sstate->tab_hash_funcs[i - 1]);
 849
 850                         i++;
 851                 }
 852
 853                 /*
 854                  * Construct tupdescs, slots and projection nodes for left and right
 855                  * sides.  The lefthand expressions will be evaluated in the parent
 856                  * plan node's exprcontext, which we don't have access to here.
 857                  * Fortunately we can just pass NULL for now and fill it in later
 858                  * (hack alert!).  The righthand expressions will be evaluated in our
 859                  * own innerecontext.
 860                  */
 861                 tupDesc = ExecTypeFromTL(leftptlist, false);
 862                 slot = ExecInitExtraTupleSlot(estate);
 863                 ExecSetSlotDescriptor(slot, tupDesc);
 864                 sstate->projLeft = ExecBuildProjectionInfo(lefttlist,
 865                                                                                                    NULL,
 866                                                                                                    slot,
 867                                                                                                    NULL);
 868
 869                 tupDesc = ExecTypeFromTL(rightptlist, false);
 870                 slot = ExecInitExtraTupleSlot(estate);
 871                 ExecSetSlotDescriptor(slot, tupDesc);
 872                 sstate->projRight = ExecBuildProjectionInfo(righttlist,
 873                                                                                                         sstate->innerecontext,
 874                                                                                                         slot,
 875                                                                                                         NULL);
 876         }
 877
 878         return sstate;
 879 }
 880
 881 /* ----------------------------------------------------------------
 882  *              ExecSetParamPlan
 883  *
 884  *              Executes an InitPlan subplan and sets its output parameters.
 885  *
 886  * This is called from ExecEvalParamExec() when the value of a PARAM_EXEC
 887  * parameter is requested and the param's execPlan field is set (indicating
 888  * that the param has not yet been evaluated).  This allows lazy evaluation
 889  * of initplans: we don't run the subplan until/unless we need its output.
 890  * Note that this routine MUST clear the execPlan fields of the plan's
 891  * output parameters after evaluating them!
 892  * ----------------------------------------------------------------
 893  */
 894 void
 895 ExecSetParamPlan(SubPlanState *node, ExprContext *econtext)
 896 {
 897         SubPlan    *subplan = (SubPlan *) node->xprstate.expr;
 898         PlanState  *planstate = node->planstate;
 899         SubLinkType subLinkType = subplan->subLinkType;
 900         MemoryContext oldcontext;
 901         TupleTableSlot *slot;
 902         ListCell   *l;
 903         bool            found = false;
 904         ArrayBuildState *astate = NULL;
 905
 906         if (subLinkType == ANY_SUBLINK ||
 907                 subLinkType == ALL_SUBLINK)
 908                 elog(ERROR, "ANY/ALL subselect unsupported as initplan");
 909         if (subLinkType == CTE_SUBLINK)
 910                 elog(ERROR, "CTE subplans should not be executed via ExecSetParamPlan");
 911
 912         /*
 913          * Must switch to per-query memory context.
 914          */
 915         oldcontext = MemoryContextSwitchTo(econtext->ecxt_per_query_memory);
 916
 917         /*
 918          * Run the plan.  (If it needs to be rescanned, the first ExecProcNode
 919          * call will take care of that.)
 920          */
 921         for (slot = ExecProcNode(planstate);
 922                  !TupIsNull(slot);
 923                  slot = ExecProcNode(planstate))
 924         {
 925                 TupleDesc       tdesc = slot->tts_tupleDescriptor;
 926                 int                     i = 1;
 927
 928                 if (subLinkType == EXISTS_SUBLINK)
 929                 {
 930                         /* There can be only one setParam... */
 931                         int                     paramid = linitial_int(subplan->setParam);
 932                         ParamExecData *prm = &(econtext->ecxt_param_exec_vals[paramid]);
 933
 934                         prm->execPlan = NULL;
 935                         prm->value = BoolGetDatum(true);
 936                         prm->isnull = false;
 937                         found = true;
 938                         break;
 939                 }
 940
 941                 if (subLinkType == ARRAY_SUBLINK)
 942                 {
 943                         Datum           dvalue;
 944                         bool            disnull;
 945
 946                         found = true;
 947                         /* stash away current value */
 948                         Assert(subplan->firstColType == tdesc->attrs[0]->atttypid);
 949                         dvalue = slot_getattr(slot, 1, &disnull);
 950                         astate = accumArrayResult(astate, dvalue, disnull,
 951                                                                           subplan->firstColType, oldcontext);
 952                         /* keep scanning subplan to collect all values */
 953                         continue;
 954                 }
 955
 956                 if (found &&
 957                         (subLinkType == EXPR_SUBLINK ||
 958                          subLinkType == ROWCOMPARE_SUBLINK))
 959                         ereport(ERROR,
 960                                         (errcode(ERRCODE_CARDINALITY_VIOLATION),
 961                                          errmsg("more than one row returned by a subquery used as an expression")));
 962
 963                 found = true;
 964
 965                 /*
 966                  * We need to copy the subplan's tuple into our own context, in case
 967                  * any of the params are pass-by-ref type --- the pointers stored in
 968                  * the param structs will point at this copied tuple! node->curTuple
 969                  * keeps track of the copied tuple for eventual freeing.
 970                  */
 971                 if (node->curTuple)
 972                         heap_freetuple(node->curTuple);
 973                 node->curTuple = ExecCopySlotTuple(slot);
 974
 975                 /*
 976                  * Now set all the setParam params from the columns of the tuple
 977                  */
 978                 foreach(l, subplan->setParam)
 979                 {
 980                         int                     paramid = lfirst_int(l);
 981                         ParamExecData *prm = &(econtext->ecxt_param_exec_vals[paramid]);
 982
 983                         prm->execPlan = NULL;
 984                         prm->value = heap_getattr(node->curTuple, i, tdesc,
 985                                                                           &(prm->isnull));
 986                         i++;
 987                 }
 988         }
 989
 990         if (subLinkType == ARRAY_SUBLINK)
 991         {
 992                 /* There can be only one setParam... */
 993                 int                     paramid = linitial_int(subplan->setParam);
 994                 ParamExecData *prm = &(econtext->ecxt_param_exec_vals[paramid]);
 995
 996                 prm->execPlan = NULL;
 997                 /* We build the result in query context so it won't disappear */
 998                 if (astate != NULL)
 999                         prm->value = makeArrayResult(astate,
1000                                                                                  econtext->ecxt_per_query_memory);
1001                 else
1002                 {
1003                         MemoryContextSwitchTo(econtext->ecxt_per_query_memory);
1004                         prm->value = PointerGetDatum(construct_empty_array(subplan->firstColType));
1005                 }
1006                 prm->isnull = false;
1007         }
1008         else if (!found)
1009         {
1010                 if (subLinkType == EXISTS_SUBLINK)
1011                 {
1012                         /* There can be only one setParam... */
1013                         int                     paramid = linitial_int(subplan->setParam);
1014                         ParamExecData *prm = &(econtext->ecxt_param_exec_vals[paramid]);
1015
1016                         prm->execPlan = NULL;
1017                         prm->value = BoolGetDatum(false);
1018                         prm->isnull = false;
1019                 }
1020                 else
1021                 {
1022                         foreach(l, subplan->setParam)
1023                         {
1024                                 int                     paramid = lfirst_int(l);
1025                                 ParamExecData *prm = &(econtext->ecxt_param_exec_vals[paramid]);
1026
1027                                 prm->execPlan = NULL;
1028                                 prm->value = (Datum) 0;
1029                                 prm->isnull = true;
1030                         }
1031                 }
1032         }
1033
1034         MemoryContextSwitchTo(oldcontext);
1035 }
1036
1037 /*
1038  * Mark an initplan as needing recalculation
1039  */
1040 void
1041 ExecReScanSetParamPlan(SubPlanState *node, PlanState *parent)
1042 {
1043         PlanState  *planstate = node->planstate;
1044         SubPlan    *subplan = (SubPlan *) node->xprstate.expr;
1045         EState     *estate = parent->state;
1046         ListCell   *l;
1047
1048         /* sanity checks */
1049         if (subplan->parParam != NIL)
1050                 elog(ERROR, "direct correlated subquery unsupported as initplan");
1051         if (subplan->setParam == NIL)
1052                 elog(ERROR, "setParam list of initplan is empty");
1053         if (bms_is_empty(planstate->plan->extParam))
1054                 elog(ERROR, "extParam set of initplan is empty");
1055
1056         /*
1057          * Don't actually re-scan: it'll happen inside ExecSetParamPlan if needed.
1058          */
1059
1060         /*
1061          * Mark this subplan's output parameters as needing recalculation.
1062          *
1063          * CTE subplans are never executed via parameter recalculation; instead
1064          * they get run when called by nodeCtescan.c.  So don't mark the output
1065          * parameter of a CTE subplan as dirty, but do set the chgParam bit for it
1066          * so that dependent plan nodes will get told to rescan.
1067          */
1068         foreach(l, subplan->setParam)
1069         {
1070                 int                     paramid = lfirst_int(l);
1071                 ParamExecData *prm = &(estate->es_param_exec_vals[paramid]);
1072
1073                 if (subplan->subLinkType != CTE_SUBLINK)
1074                         prm->execPlan = node;
1075
1076                 parent->chgParam = bms_add_member(parent->chgParam, paramid);
1077         }
1078 }
1079
1080
1081 /*
1082  * ExecInitAlternativeSubPlan
1083  *
1084  * Initialize for execution of one of a set of alternative subplans.
1085  */
1086 AlternativeSubPlanState *
1087 ExecInitAlternativeSubPlan(AlternativeSubPlan *asplan, PlanState *parent)
1088 {
1089         AlternativeSubPlanState *asstate = makeNode(AlternativeSubPlanState);
1090         double          num_calls;
1091         SubPlan    *subplan1;
1092         SubPlan    *subplan2;
1093         Cost            cost1;
1094         Cost            cost2;
1095
1096         asstate->xprstate.evalfunc = (ExprStateEvalFunc) ExecAlternativeSubPlan;
1097         asstate->xprstate.expr = (Expr *) asplan;
1098
1099         /*
1100          * Initialize subplans.  (Can we get away with only initializing the one
1101          * we're going to use?)
1102          */
1103         asstate->subplans = (List *) ExecInitExpr((Expr *) asplan->subplans,
1104                                                                                           parent);
1105
1106         /*
1107          * Select the one to be used.  For this, we need an estimate of the number
1108          * of executions of the subplan.  We use the number of output rows
1109          * expected from the parent plan node.  This is a good estimate if we are
1110          * in the parent's targetlist, and an underestimate (but probably not by
1111          * more than a factor of 2) if we are in the qual.
1112          */
1113         num_calls = parent->plan->plan_rows;
1114
1115         /*
1116          * The planner saved enough info so that we don't have to work very hard
1117          * to estimate the total cost, given the number-of-calls estimate.
1118          */
1119         Assert(list_length(asplan->subplans) == 2);
1120         subplan1 = (SubPlan *) linitial(asplan->subplans);
1121         subplan2 = (SubPlan *) lsecond(asplan->subplans);
1122
1123         cost1 = subplan1->startup_cost + num_calls * subplan1->per_call_cost;
1124         cost2 = subplan2->startup_cost + num_calls * subplan2->per_call_cost;
1125
1126         if (cost1 < cost2)
1127                 asstate->active = 0;
1128         else
1129                 asstate->active = 1;
1130
1131         return asstate;
1132 }
1133
1134 /*
1135  * ExecAlternativeSubPlan
1136  *
1137  * Execute one of a set of alternative subplans.
1138  *
1139  * Note: in future we might consider changing to different subplans on the
1140  * fly, in case the original rowcount estimate turns out to be way off.
1141  */
1142 static Datum
1143 ExecAlternativeSubPlan(AlternativeSubPlanState *node,
1144                                            ExprContext *econtext,
1145                                            bool *isNull,
1146                                            ExprDoneCond *isDone)
1147 {
1148         /* Just pass control to the active subplan */
1149         SubPlanState *activesp = (SubPlanState *) list_nth(node->subplans,
1150                                                                                                            node->active);
1151
1152         Assert(IsA(activesp, SubPlanState));
1153
1154         return ExecSubPlan(activesp,
1155                                            econtext,
1156                                            isNull,
1157                                            isDone);
1158 }