1 /*-------------------------------------------------------------------------
2 *
3 * execAmi.c
4 * miscellaneous executor access method routines
5 *
6 * Portions Copyright (c) 1996-2021, 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
ExecReScan(PlanState * node)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
ExecMarkPos(PlanState * node)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
ExecRestrPos(PlanState * node)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
ExecSupportsMarkRestore(Path * pathnode)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 {
442 CustomPath *customPath = castNode(CustomPath, pathnode);
443
444 if (customPath->flags & CUSTOMPATH_SUPPORT_MARK_RESTORE)
445 return true;
446 return false;
447 }
448 case T_Result:
449
450 /*
451 * Result supports mark/restore iff it has a child plan that does.
452 *
453 * We have to be careful here because there is more than one Path
454 * type that can produce a Result plan node.
455 */
456 if (IsA(pathnode, ProjectionPath))
457 return ExecSupportsMarkRestore(((ProjectionPath *) pathnode)->subpath);
458 else if (IsA(pathnode, MinMaxAggPath))
459 return false; /* childless Result */
460 else if (IsA(pathnode, GroupResultPath))
461 return false; /* childless Result */
462 else
463 {
464 /* Simple RTE_RESULT base relation */
465 Assert(IsA(pathnode, Path));
466 return false; /* childless Result */
467 }
468
469 case T_Append:
470 {
471 AppendPath *appendPath = castNode(AppendPath, pathnode);
472
473 /*
474 * If there's exactly one child, then there will be no Append
475 * in the final plan, so we can handle mark/restore if the
476 * child plan node can.
477 */
478 if (list_length(appendPath->subpaths) == 1)
479 return ExecSupportsMarkRestore((Path *) linitial(appendPath->subpaths));
480 /* Otherwise, Append can't handle it */
481 return false;
482 }
483
484 case T_MergeAppend:
485 {
486 MergeAppendPath *mapath = castNode(MergeAppendPath, pathnode);
487
488 /*
489 * Like the Append case above, single-subpath MergeAppends
490 * won't be in the final plan, so just return the child's
491 * mark/restore ability.
492 */
493 if (list_length(mapath->subpaths) == 1)
494 return ExecSupportsMarkRestore((Path *) linitial(mapath->subpaths));
495 /* Otherwise, MergeAppend can't handle it */
496 return false;
497 }
498
499 default:
500 break;
501 }
502
503 return false;
504 }
505
506 /*
507 * ExecSupportsBackwardScan - does a plan type support backwards scanning?
508 *
509 * Ideally, all plan types would support backwards scan, but that seems
510 * unlikely to happen soon. In some cases, a plan node passes the backwards
511 * scan down to its children, and so supports backwards scan only if its
512 * children do. Therefore, this routine must be passed a complete plan tree.
513 */
514 bool
ExecSupportsBackwardScan(Plan * node)515 ExecSupportsBackwardScan(Plan *node)
516 {
517 if (node == NULL)
518 return false;
519
520 /*
521 * Parallel-aware nodes return a subset of the tuples in each worker, and
522 * in general we can't expect to have enough bookkeeping state to know
523 * which ones we returned in this worker as opposed to some other worker.
524 */
525 if (node->parallel_aware)
526 return false;
527
528 switch (nodeTag(node))
529 {
530 case T_Result:
531 if (outerPlan(node) != NULL)
532 return ExecSupportsBackwardScan(outerPlan(node));
533 else
534 return false;
535
536 case T_Append:
537 {
538 ListCell *l;
539
540 /* With async, tuples may be interleaved, so can't back up. */
541 if (((Append *) node)->nasyncplans > 0)
542 return false;
543
544 foreach(l, ((Append *) node)->appendplans)
545 {
546 if (!ExecSupportsBackwardScan((Plan *) lfirst(l)))
547 return false;
548 }
549 /* need not check tlist because Append doesn't evaluate it */
550 return true;
551 }
552
553 case T_SampleScan:
554 /* Simplify life for tablesample methods by disallowing this */
555 return false;
556
557 case T_Gather:
558 return false;
559
560 case T_IndexScan:
561 return IndexSupportsBackwardScan(((IndexScan *) node)->indexid);
562
563 case T_IndexOnlyScan:
564 return IndexSupportsBackwardScan(((IndexOnlyScan *) node)->indexid);
565
566 case T_SubqueryScan:
567 return ExecSupportsBackwardScan(((SubqueryScan *) node)->subplan);
568
569 case T_CustomScan:
570 {
571 uint32 flags = ((CustomScan *) node)->flags;
572
573 if (flags & CUSTOMPATH_SUPPORT_BACKWARD_SCAN)
574 return true;
575 }
576 return false;
577
578 case T_SeqScan:
579 case T_TidScan:
580 case T_TidRangeScan:
581 case T_FunctionScan:
582 case T_ValuesScan:
583 case T_CteScan:
584 case T_Material:
585 case T_Sort:
586 /* these don't evaluate tlist */
587 return true;
588
589 case T_IncrementalSort:
590
591 /*
592 * Unlike full sort, incremental sort keeps only a single group of
593 * tuples in memory, so it can't scan backwards.
594 */
595 return false;
596
597 case T_LockRows:
598 case T_Limit:
599 return ExecSupportsBackwardScan(outerPlan(node));
600
601 default:
602 return false;
603 }
604 }
605
606 /*
607 * An IndexScan or IndexOnlyScan node supports backward scan only if the
608 * index's AM does.
609 */
610 static bool
IndexSupportsBackwardScan(Oid indexid)611 IndexSupportsBackwardScan(Oid indexid)
612 {
613 bool result;
614 HeapTuple ht_idxrel;
615 Form_pg_class idxrelrec;
616 IndexAmRoutine *amroutine;
617
618 /* Fetch the pg_class tuple of the index relation */
619 ht_idxrel = SearchSysCache1(RELOID, ObjectIdGetDatum(indexid));
620 if (!HeapTupleIsValid(ht_idxrel))
621 elog(ERROR, "cache lookup failed for relation %u", indexid);
622 idxrelrec = (Form_pg_class) GETSTRUCT(ht_idxrel);
623
624 /* Fetch the index AM's API struct */
625 amroutine = GetIndexAmRoutineByAmId(idxrelrec->relam, false);
626
627 result = amroutine->amcanbackward;
628
629 pfree(amroutine);
630 ReleaseSysCache(ht_idxrel);
631
632 return result;
633 }
634
635 /*
636 * ExecMaterializesOutput - does a plan type materialize its output?
637 *
638 * Returns true if the plan node type is one that automatically materializes
639 * its output (typically by keeping it in a tuplestore). For such plans,
640 * a rescan without any parameter change will have zero startup cost and
641 * very low per-tuple cost.
642 */
643 bool
ExecMaterializesOutput(NodeTag plantype)644 ExecMaterializesOutput(NodeTag plantype)
645 {
646 switch (plantype)
647 {
648 case T_Material:
649 case T_FunctionScan:
650 case T_TableFuncScan:
651 case T_CteScan:
652 case T_NamedTuplestoreScan:
653 case T_WorkTableScan:
654 case T_Sort:
655 return true;
656
657 default:
658 break;
659 }
660
661 return false;
662 }
663