src/backend/executor/execAmi.c

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