src/backend/executor/execAmi.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * execAmi.c
   4  *        miscellaneous executor access method routines
   5  *
   6  * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *      src/backend/executor/execAmi.c
  10  *
  11  *-------------------------------------------------------------------------
  12  */
  13 #include "postgres.h"
  14
  15 #include "access/amapi.h"
  16 #include "access/htup_details.h"
  17 #include "executor/execdebug.h"
  18 #include "executor/nodeAgg.h"
  19 #include "executor/nodeAppend.h"
  20 #include "executor/nodeBitmapAnd.h"
  21 #include "executor/nodeBitmapHeapscan.h"
  22 #include "executor/nodeBitmapIndexscan.h"
  23 #include "executor/nodeBitmapOr.h"
  24 #include "executor/nodeCtescan.h"
  25 #include "executor/nodeCustom.h"
  26 #include "executor/nodeForeignscan.h"
  27 #include "executor/nodeFunctionscan.h"
  28 #include "executor/nodeGather.h"
  29 #include "executor/nodeGatherMerge.h"
  30 #include "executor/nodeGroup.h"
  31 #include "executor/nodeHash.h"
  32 #include "executor/nodeHashjoin.h"
  33 #include "executor/nodeIncrementalSort.h"
  34 #include "executor/nodeIndexonlyscan.h"
  35 #include "executor/nodeIndexscan.h"
  36 #include "executor/nodeLimit.h"
  37 #include "executor/nodeLockRows.h"
  38 #include "executor/nodeMaterial.h"
  39 #include "executor/nodeMemoize.h"
  40 #include "executor/nodeMergeAppend.h"
  41 #include "executor/nodeMergejoin.h"
  42 #include "executor/nodeModifyTable.h"
  43 #include "executor/nodeNamedtuplestorescan.h"
  44 #include "executor/nodeNestloop.h"
  45 #include "executor/nodeProjectSet.h"
  46 #include "executor/nodeRecursiveunion.h"
  47 #include "executor/nodeResult.h"
  48 #include "executor/nodeSamplescan.h"
  49 #include "executor/nodeSeqscan.h"
  50 #include "executor/nodeSetOp.h"
  51 #include "executor/nodeSort.h"
  52 #include "executor/nodeSubplan.h"
  53 #include "executor/nodeSubqueryscan.h"
  54 #include "executor/nodeTableFuncscan.h"
  55 #include "executor/nodeTidrangescan.h"
  56 #include "executor/nodeTidscan.h"
  57 #include "executor/nodeUnique.h"
  58 #include "executor/nodeValuesscan.h"
  59 #include "executor/nodeWindowAgg.h"
  60 #include "executor/nodeWorktablescan.h"
  61 #include "nodes/extensible.h"
  62 #include "nodes/nodeFuncs.h"
  63 #include "nodes/pathnodes.h"
  64 #include "utils/rel.h"
  65 #include "utils/syscache.h"
  66
  67 static bool IndexSupportsBackwardScan(Oid indexid);
  68
  69
  70 /*
  71  * ExecReScan
  72  *              Reset a plan node so that its output can be re-scanned.
  73  *
  74  * Note that if the plan node has parameters that have changed value,
  75  * the output might be different from last time.
  76  */
  77 void
  78 ExecReScan(PlanState *node)
  79 {
  80         /* If collecting timing stats, update them */
  81         if (node->instrument)
  82                 InstrEndLoop(node->instrument);
  83
  84         /*
  85          * If we have changed parameters, propagate that info.
  86          *
  87          * Note: ExecReScanSetParamPlan() can add bits to node->chgParam,
  88          * corresponding to the output param(s) that the InitPlan will update.
  89          * Since we make only one pass over the list, that means that an InitPlan
  90          * can depend on the output param(s) of a sibling InitPlan only if that
  91          * sibling appears earlier in the list.  This is workable for now given
  92          * the limited ways in which one InitPlan could depend on another, but
  93          * eventually we might need to work harder (or else make the planner
  94          * enlarge the extParam/allParam sets to include the params of depended-on
  95          * InitPlans).
  96          */
  97         if (node->chgParam != NULL)
  98         {
  99                 ListCell   *l;
 100
 101                 foreach(l, node->initPlan)
 102                 {
 103                         SubPlanState *sstate = (SubPlanState *) lfirst(l);
 104                         PlanState  *splan = sstate->planstate;
 105
 106                         if (splan->plan->extParam != NULL)      /* don't care about child
 107                                                                                                  * local Params */
 108                                 UpdateChangedParamSet(splan, node->chgParam);
 109                         if (splan->chgParam != NULL)
 110                                 ExecReScanSetParamPlan(sstate, node);
 111                 }
 112                 foreach(l, node->subPlan)
 113                 {
 114                         SubPlanState *sstate = (SubPlanState *) lfirst(l);
 115                         PlanState  *splan = sstate->planstate;
 116
 117                         if (splan->plan->extParam != NULL)
 118                                 UpdateChangedParamSet(splan, node->chgParam);
 119                 }
 120                 /* Well. Now set chgParam for left/right trees. */
 121                 if (node->lefttree != NULL)
 122                         UpdateChangedParamSet(node->lefttree, node->chgParam);
 123                 if (node->righttree != NULL)
 124                         UpdateChangedParamSet(node->righttree, node->chgParam);
 125         }
 126
 127         /* Call expression callbacks */
 128         if (node->ps_ExprContext)
 129                 ReScanExprContext(node->ps_ExprContext);
 130
 131         /* And do node-type-specific processing */
 132         switch (nodeTag(node))
 133         {
 134                 case T_ResultState:
 135                         ExecReScanResult((ResultState *) node);
 136                         break;
 137
 138                 case T_ProjectSetState:
 139                         ExecReScanProjectSet((ProjectSetState *) node);
 140                         break;
 141
 142                 case T_ModifyTableState:
 143                         ExecReScanModifyTable((ModifyTableState *) node);
 144                         break;
 145
 146                 case T_AppendState:
 147                         ExecReScanAppend((AppendState *) node);
 148                         break;
 149
 150                 case T_MergeAppendState:
 151                         ExecReScanMergeAppend((MergeAppendState *) node);
 152                         break;
 153
 154                 case T_RecursiveUnionState:
 155                         ExecReScanRecursiveUnion((RecursiveUnionState *) node);
 156                         break;
 157
 158                 case T_BitmapAndState:
 159                         ExecReScanBitmapAnd((BitmapAndState *) node);
 160                         break;
 161
 162                 case T_BitmapOrState:
 163                         ExecReScanBitmapOr((BitmapOrState *) node);
 164                         break;
 165
 166                 case T_SeqScanState:
 167                         ExecReScanSeqScan((SeqScanState *) node);
 168                         break;
 169
 170                 case T_SampleScanState:
 171                         ExecReScanSampleScan((SampleScanState *) node);
 172                         break;
 173
 174                 case T_GatherState:
 175                         ExecReScanGather((GatherState *) node);
 176                         break;
 177
 178                 case T_GatherMergeState:
 179                         ExecReScanGatherMerge((GatherMergeState *) node);
 180                         break;
 181
 182                 case T_IndexScanState:
 183                         ExecReScanIndexScan((IndexScanState *) node);
 184                         break;
 185
 186                 case T_IndexOnlyScanState:
 187                         ExecReScanIndexOnlyScan((IndexOnlyScanState *) node);
 188                         break;
 189
 190                 case T_BitmapIndexScanState:
 191                         ExecReScanBitmapIndexScan((BitmapIndexScanState *) node);
 192                         break;
 193
 194                 case T_BitmapHeapScanState:
 195                         ExecReScanBitmapHeapScan((BitmapHeapScanState *) node);
 196                         break;
 197
 198                 case T_TidScanState:
 199                         ExecReScanTidScan((TidScanState *) node);
 200                         break;
 201
 202                 case T_TidRangeScanState:
 203                         ExecReScanTidRangeScan((TidRangeScanState *) node);
 204                         break;
 205
 206                 case T_SubqueryScanState:
 207                         ExecReScanSubqueryScan((SubqueryScanState *) node);
 208                         break;
 209
 210                 case T_FunctionScanState:
 211                         ExecReScanFunctionScan((FunctionScanState *) node);
 212                         break;
 213
 214                 case T_TableFuncScanState:
 215                         ExecReScanTableFuncScan((TableFuncScanState *) node);
 216                         break;
 217
 218                 case T_ValuesScanState:
 219                         ExecReScanValuesScan((ValuesScanState *) node);
 220                         break;
 221
 222                 case T_CteScanState:
 223                         ExecReScanCteScan((CteScanState *) node);
 224                         break;
 225
 226                 case T_NamedTuplestoreScanState:
 227                         ExecReScanNamedTuplestoreScan((NamedTuplestoreScanState *) node);
 228                         break;
 229
 230                 case T_WorkTableScanState:
 231                         ExecReScanWorkTableScan((WorkTableScanState *) node);
 232                         break;
 233
 234                 case T_ForeignScanState:
 235                         ExecReScanForeignScan((ForeignScanState *) node);
 236                         break;
 237
 238                 case T_CustomScanState:
 239                         ExecReScanCustomScan((CustomScanState *) node);
 240                         break;
 241
 242                 case T_NestLoopState:
 243                         ExecReScanNestLoop((NestLoopState *) node);
 244                         break;
 245
 246                 case T_MergeJoinState:
 247                         ExecReScanMergeJoin((MergeJoinState *) node);
 248                         break;
 249
 250                 case T_HashJoinState:
 251                         ExecReScanHashJoin((HashJoinState *) node);
 252                         break;
 253
 254                 case T_MaterialState:
 255                         ExecReScanMaterial((MaterialState *) node);
 256                         break;
 257
 258                 case T_MemoizeState:
 259                         ExecReScanMemoize((MemoizeState *) node);
 260                         break;
 261
 262                 case T_SortState:
 263                         ExecReScanSort((SortState *) node);
 264                         break;
 265
 266                 case T_IncrementalSortState:
 267                         ExecReScanIncrementalSort((IncrementalSortState *) node);
 268                         break;
 269
 270                 case T_GroupState:
 271                         ExecReScanGroup((GroupState *) node);
 272                         break;
 273
 274                 case T_AggState:
 275                         ExecReScanAgg((AggState *) node);
 276                         break;
 277
 278                 case T_WindowAggState:
 279                         ExecReScanWindowAgg((WindowAggState *) node);
 280                         break;
 281
 282                 case T_UniqueState:
 283                         ExecReScanUnique((UniqueState *) node);
 284                         break;
 285
 286                 case T_HashState:
 287                         ExecReScanHash((HashState *) node);
 288                         break;
 289
 290                 case T_SetOpState:
 291                         ExecReScanSetOp((SetOpState *) node);
 292                         break;
 293
 294                 case T_LockRowsState:
 295                         ExecReScanLockRows((LockRowsState *) node);
 296                         break;
 297
 298                 case T_LimitState:
 299                         ExecReScanLimit((LimitState *) node);
 300                         break;
 301
 302                 default:
 303                         elog(ERROR, "unrecognized node type: %d", (int) nodeTag(node));
 304                         break;
 305         }
 306
 307         if (node->chgParam != NULL)
 308         {
 309                 bms_free(node->chgParam);
 310                 node->chgParam = NULL;
 311         }
 312 }
 313
 314 /*
 315  * ExecMarkPos
 316  *
 317  * Marks the current scan position.
 318  *
 319  * NOTE: mark/restore capability is currently needed only for plan nodes
 320  * that are the immediate inner child of a MergeJoin node.  Since MergeJoin
 321  * requires sorted input, there is never any need to support mark/restore in
 322  * node types that cannot produce sorted output.  There are some cases in
 323  * which a node can pass through sorted data from its child; if we don't
 324  * implement mark/restore for such a node type, the planner compensates by
 325  * inserting a Material node above that node.
 326  */
 327 void
 328 ExecMarkPos(PlanState *node)
 329 {
 330         switch (nodeTag(node))
 331         {
 332                 case T_IndexScanState:
 333                         ExecIndexMarkPos((IndexScanState *) node);
 334                         break;
 335
 336                 case T_IndexOnlyScanState:
 337                         ExecIndexOnlyMarkPos((IndexOnlyScanState *) node);
 338                         break;
 339
 340                 case T_CustomScanState:
 341                         ExecCustomMarkPos((CustomScanState *) node);
 342                         break;
 343
 344                 case T_MaterialState:
 345                         ExecMaterialMarkPos((MaterialState *) node);
 346                         break;
 347
 348                 case T_SortState:
 349                         ExecSortMarkPos((SortState *) node);
 350                         break;
 351
 352                 case T_ResultState:
 353                         ExecResultMarkPos((ResultState *) node);
 354                         break;
 355
 356                 default:
 357                         /* don't make hard error unless caller asks to restore... */
 358                         elog(DEBUG2, "unrecognized node type: %d", (int) nodeTag(node));
 359                         break;
 360         }
 361 }
 362
 363 /*
 364  * ExecRestrPos
 365  *
 366  * restores the scan position previously saved with ExecMarkPos()
 367  *
 368  * NOTE: the semantics of this are that the first ExecProcNode following
 369  * the restore operation will yield the same tuple as the first one following
 370  * the mark operation.  It is unspecified what happens to the plan node's
 371  * result TupleTableSlot.  (In most cases the result slot is unchanged by
 372  * a restore, but the node may choose to clear it or to load it with the
 373  * restored-to tuple.)  Hence the caller should discard any previously
 374  * returned TupleTableSlot after doing a restore.
 375  */
 376 void
 377 ExecRestrPos(PlanState *node)
 378 {
 379         switch (nodeTag(node))
 380         {
 381                 case T_IndexScanState:
 382                         ExecIndexRestrPos((IndexScanState *) node);
 383                         break;
 384
 385                 case T_IndexOnlyScanState:
 386                         ExecIndexOnlyRestrPos((IndexOnlyScanState *) node);
 387                         break;
 388
 389                 case T_CustomScanState:
 390                         ExecCustomRestrPos((CustomScanState *) node);
 391                         break;
 392
 393                 case T_MaterialState:
 394                         ExecMaterialRestrPos((MaterialState *) node);
 395                         break;
 396
 397                 case T_SortState:
 398                         ExecSortRestrPos((SortState *) node);
 399                         break;
 400
 401                 case T_ResultState:
 402                         ExecResultRestrPos((ResultState *) node);
 403                         break;
 404
 405                 default:
 406                         elog(ERROR, "unrecognized node type: %d", (int) nodeTag(node));
 407                         break;
 408         }
 409 }
 410
 411 /*
 412  * ExecSupportsMarkRestore - does a Path support mark/restore?
 413  *
 414  * This is used during planning and so must accept a Path, not a Plan.
 415  * We keep it here to be adjacent to the routines above, which also must
 416  * know which plan types support mark/restore.
 417  */
 418 bool
 419 ExecSupportsMarkRestore(Path *pathnode)
 420 {
 421         /*
 422          * For consistency with the routines above, we do not examine the nodeTag
 423          * but rather the pathtype, which is the Plan node type the Path would
 424          * produce.
 425          */
 426         switch (pathnode->pathtype)
 427         {
 428                 case T_IndexScan:
 429                 case T_IndexOnlyScan:
 430
 431                         /*
 432                          * Not all index types support mark/restore.
 433                          */
 434                         return castNode(IndexPath, pathnode)->indexinfo->amcanmarkpos;
 435
 436                 case T_Material:
 437                 case T_Sort:
 438                         return true;
 439
 440                 case T_CustomScan:
 441                         if (castNode(CustomPath, pathnode)->flags & CUSTOMPATH_SUPPORT_MARK_RESTORE)
 442                                 return true;
 443                         return false;
 444
 445                 case T_Result:
 446
 447                         /*
 448                          * Result supports mark/restore iff it has a child plan that does.
 449                          *
 450                          * We have to be careful here because there is more than one Path
 451                          * type that can produce a Result plan node.
 452                          */
 453                         if (IsA(pathnode, ProjectionPath))
 454                                 return ExecSupportsMarkRestore(((ProjectionPath *) pathnode)->subpath);
 455                         else if (IsA(pathnode, MinMaxAggPath))
 456                                 return false;   /* childless Result */
 457                         else if (IsA(pathnode, GroupResultPath))
 458                                 return false;   /* childless Result */
 459                         else
 460                         {
 461                                 /* Simple RTE_RESULT base relation */
 462                                 Assert(IsA(pathnode, Path));
 463                                 return false;   /* childless Result */
 464                         }
 465
 466                 case T_Append:
 467                         {
 468                                 AppendPath *appendPath = castNode(AppendPath, pathnode);
 469
 470                                 /*
 471                                  * If there's exactly one child, then there will be no Append
 472                                  * in the final plan, so we can handle mark/restore if the
 473                                  * child plan node can.
 474                                  */
 475                                 if (list_length(appendPath->subpaths) == 1)
 476                                         return ExecSupportsMarkRestore((Path *) linitial(appendPath->subpaths));
 477                                 /* Otherwise, Append can't handle it */
 478                                 return false;
 479                         }
 480
 481                 case T_MergeAppend:
 482                         {
 483                                 MergeAppendPath *mapath = castNode(MergeAppendPath, pathnode);
 484
 485                                 /*
 486                                  * Like the Append case above, single-subpath MergeAppends
 487                                  * won't be in the final plan, so just return the child's
 488                                  * mark/restore ability.
 489                                  */
 490                                 if (list_length(mapath->subpaths) == 1)
 491                                         return ExecSupportsMarkRestore((Path *) linitial(mapath->subpaths));
 492                                 /* Otherwise, MergeAppend can't handle it */
 493                                 return false;
 494                         }
 495
 496                 default:
 497                         break;
 498         }
 499
 500         return false;
 501 }
 502
 503 /*
 504  * ExecSupportsBackwardScan - does a plan type support backwards scanning?
 505  *
 506  * Ideally, all plan types would support backwards scan, but that seems
 507  * unlikely to happen soon.  In some cases, a plan node passes the backwards
 508  * scan down to its children, and so supports backwards scan only if its
 509  * children do.  Therefore, this routine must be passed a complete plan tree.
 510  */
 511 bool
 512 ExecSupportsBackwardScan(Plan *node)
 513 {
 514         if (node == NULL)
 515                 return false;
 516
 517         /*
 518          * Parallel-aware nodes return a subset of the tuples in each worker, and
 519          * in general we can't expect to have enough bookkeeping state to know
 520          * which ones we returned in this worker as opposed to some other worker.
 521          */
 522         if (node->parallel_aware)
 523                 return false;
 524
 525         switch (nodeTag(node))
 526         {
 527                 case T_Result:
 528                         if (outerPlan(node) != NULL)
 529                                 return ExecSupportsBackwardScan(outerPlan(node));
 530                         else
 531                                 return false;
 532
 533                 case T_Append:
 534                         {
 535                                 ListCell   *l;
 536
 537                                 /* With async, tuples may be interleaved, so can't back up. */
 538                                 if (((Append *) node)->nasyncplans > 0)
 539                                         return false;
 540
 541                                 foreach(l, ((Append *) node)->appendplans)
 542                                 {
 543                                         if (!ExecSupportsBackwardScan((Plan *) lfirst(l)))
 544                                                 return false;
 545                                 }
 546                                 /* need not check tlist because Append doesn't evaluate it */
 547                                 return true;
 548                         }
 549
 550                 case T_SampleScan:
 551                         /* Simplify life for tablesample methods by disallowing this */
 552                         return false;
 553
 554                 case T_Gather:
 555                         return false;
 556
 557                 case T_IndexScan:
 558                         return IndexSupportsBackwardScan(((IndexScan *) node)->indexid);
 559
 560                 case T_IndexOnlyScan:
 561                         return IndexSupportsBackwardScan(((IndexOnlyScan *) node)->indexid);
 562
 563                 case T_SubqueryScan:
 564                         return ExecSupportsBackwardScan(((SubqueryScan *) node)->subplan);
 565
 566                 case T_CustomScan:
 567                         if (((CustomScan *) node)->flags & CUSTOMPATH_SUPPORT_BACKWARD_SCAN)
 568                                 return true;
 569                         return false;
 570
 571                 case T_SeqScan:
 572                 case T_TidScan:
 573                 case T_TidRangeScan:
 574                 case T_FunctionScan:
 575                 case T_ValuesScan:
 576                 case T_CteScan:
 577                 case T_Material:
 578                 case T_Sort:
 579                         /* these don't evaluate tlist */
 580                         return true;
 581
 582                 case T_IncrementalSort:
 583
 584                         /*
 585                          * Unlike full sort, incremental sort keeps only a single group of
 586                          * tuples in memory, so it can't scan backwards.
 587                          */
 588                         return false;
 589
 590                 case T_LockRows:
 591                 case T_Limit:
 592                         return ExecSupportsBackwardScan(outerPlan(node));
 593
 594                 default:
 595                         return false;
 596         }
 597 }
 598
 599 /*
 600  * An IndexScan or IndexOnlyScan node supports backward scan only if the
 601  * index's AM does.
 602  */
 603 static bool
 604 IndexSupportsBackwardScan(Oid indexid)
 605 {
 606         bool            result;
 607         HeapTuple       ht_idxrel;
 608         Form_pg_class idxrelrec;
 609         IndexAmRoutine *amroutine;
 610
 611         /* Fetch the pg_class tuple of the index relation */
 612         ht_idxrel = SearchSysCache1(RELOID, ObjectIdGetDatum(indexid));
 613         if (!HeapTupleIsValid(ht_idxrel))
 614                 elog(ERROR, "cache lookup failed for relation %u", indexid);
 615         idxrelrec = (Form_pg_class) GETSTRUCT(ht_idxrel);
 616
 617         /* Fetch the index AM's API struct */
 618         amroutine = GetIndexAmRoutineByAmId(idxrelrec->relam, false);
 619
 620         result = amroutine->amcanbackward;
 621
 622         pfree(amroutine);
 623         ReleaseSysCache(ht_idxrel);
 624
 625         return result;
 626 }
 627
 628 /*
 629  * ExecMaterializesOutput - does a plan type materialize its output?
 630  *
 631  * Returns true if the plan node type is one that automatically materializes
 632  * its output (typically by keeping it in a tuplestore).  For such plans,
 633  * a rescan without any parameter change will have zero startup cost and
 634  * very low per-tuple cost.
 635  */
 636 bool
 637 ExecMaterializesOutput(NodeTag plantype)
 638 {
 639         switch (plantype)
 640         {
 641                 case T_Material:
 642                 case T_FunctionScan:
 643                 case T_TableFuncScan:
 644                 case T_CteScan:
 645                 case T_NamedTuplestoreScan:
 646                 case T_WorkTableScan:
 647                 case T_Sort:
 648                         return true;
 649
 650                 default:
 651                         break;
 652         }
 653
 654         return false;
 655 }