1 /*-------------------------------------------------------------------------
2 *
3 * execAmi.c
4 * miscellaneous executor access method routines
5 *
6 * Portions Copyright (c) 1996-2020, 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"
is_null_expression(const char * start,const char * finish)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/nodeMergeAppend.h"
40 #include "executor/nodeMergejoin.h"
41 #include "executor/nodeModifyTable.h"
42 #include "executor/nodeNamedtuplestorescan.h"
43 #include "executor/nodeNestloop.h"
44 #include "executor/nodeProjectSet.h"
45 #include "executor/nodeRecursiveunion.h"
46 #include "executor/nodeResult.h"
47 #include "executor/nodeSamplescan.h"
48 #include "executor/nodeSeqscan.h"
49 #include "executor/nodeSetOp.h"
50 #include "executor/nodeSort.h"
51 #include "executor/nodeSubplan.h"
52 #include "executor/nodeSubqueryscan.h"
53 #include "executor/nodeTableFuncscan.h"
54 #include "executor/nodeTidscan.h"
55 #include "executor/nodeUnique.h"
56 #include "executor/nodeValuesscan.h"
57 #include "executor/nodeWindowAgg.h"
58 #include "executor/nodeWorktablescan.h"
59 #include "nodes/extensible.h"
60 #include "nodes/nodeFuncs.h"
61 #include "nodes/pathnodes.h"
62 #include "utils/rel.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 left/right trees. */
119 if (node->lefttree != NULL)
120 UpdateChangedParamSet(node->lefttree, node->chgParam);
121 if (node->righttree != NULL)
122 UpdateChangedParamSet(node->righttree, 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_SubqueryScanState:
201 ExecReScanSubqueryScan((SubqueryScanState *) node);
202 break;
203
204 case T_FunctionScanState:
205 ExecReScanFunctionScan((FunctionScanState *) node);
206 break;
207
208 case T_TableFuncScanState:
209 ExecReScanTableFuncScan((TableFuncScanState *) node);
210 break;
211
212 case T_ValuesScanState:
213 ExecReScanValuesScan((ValuesScanState *) node);
214 break;
215
216 case T_CteScanState:
217 ExecReScanCteScan((CteScanState *) node);
218 break;
219
220 case T_NamedTuplestoreScanState:
221 ExecReScanNamedTuplestoreScan((NamedTuplestoreScanState *) node);
222 break;
223
224 case T_WorkTableScanState:
225 ExecReScanWorkTableScan((WorkTableScanState *) node);
226 break;
227
228 case T_ForeignScanState:
229 ExecReScanForeignScan((ForeignScanState *) node);
230 break;
231
232 case T_CustomScanState:
233 ExecReScanCustomScan((CustomScanState *) node);
234 break;
235
236 case T_NestLoopState:
237 ExecReScanNestLoop((NestLoopState *) node);
238 break;
239
240 case T_MergeJoinState:
241 ExecReScanMergeJoin((MergeJoinState *) node);
242 break;
243
244 case T_HashJoinState:
245 ExecReScanHashJoin((HashJoinState *) node);
246 break;
247
248 case T_MaterialState:
249 ExecReScanMaterial((MaterialState *) node);
250 break;
251
252 case T_SortState:
253 ExecReScanSort((SortState *) node);
254 break;
255
256 case T_IncrementalSortState:
257 ExecReScanIncrementalSort((IncrementalSortState *) node);
258 break;
259
260 case T_GroupState:
261 ExecReScanGroup((GroupState *) node);
262 break;
263
264 case T_AggState:
265 ExecReScanAgg((AggState *) node);
266 break;
267
268 case T_WindowAggState:
269 ExecReScanWindowAgg((WindowAggState *) node);
270 break;
271
272 case T_UniqueState:
273 ExecReScanUnique((UniqueState *) node);
274 break;
275
276 case T_HashState:
277 ExecReScanHash((HashState *) node);
278 break;
279
280 case T_SetOpState:
281 ExecReScanSetOp((SetOpState *) node);
282 break;
283
284 case T_LockRowsState:
285 ExecReScanLockRows((LockRowsState *) node);
286 break;
287
288 case T_LimitState:
289 ExecReScanLimit((LimitState *) node);
290 break;
291
292 default:
293 elog(ERROR, "unrecognized node type: %d", (int) nodeTag(node));
294 break;
295 }
296
297 if (node->chgParam != NULL)
298 {
299 bms_free(node->chgParam);
300 node->chgParam = NULL;
301 }
302 }
303
304 /*
305 * ExecMarkPos
306 *
307 * Marks the current scan position.
308 *
309 * NOTE: mark/restore capability is currently needed only for plan nodes
310 * that are the immediate inner child of a MergeJoin node. Since MergeJoin
311 * requires sorted input, there is never any need to support mark/restore in
312 * node types that cannot produce sorted output. There are some cases in
313 * which a node can pass through sorted data from its child; if we don't
314 * implement mark/restore for such a node type, the planner compensates by
315 * inserting a Material node above that node.
316 */
317 void
318 ExecMarkPos(PlanState *node)
319 {
320 switch (nodeTag(node))
321 {
322 case T_IndexScanState:
323 ExecIndexMarkPos((IndexScanState *) node);
324 break;
325
326 case T_IndexOnlyScanState:
327 ExecIndexOnlyMarkPos((IndexOnlyScanState *) node);
328 break;
329
330 case T_CustomScanState:
331 ExecCustomMarkPos((CustomScanState *) node);
332 break;
333
334 case T_MaterialState:
335 ExecMaterialMarkPos((MaterialState *) node);
336 break;
337
338 case T_SortState:
339 ExecSortMarkPos((SortState *) node);
340 break;
341
342 case T_ResultState:
343 ExecResultMarkPos((ResultState *) node);
344 break;
345
346 default:
347 /* don't make hard error unless caller asks to restore... */
348 elog(DEBUG2, "unrecognized node type: %d", (int) nodeTag(node));
349 break;
350 }
351 }
352
353 /*
354 * ExecRestrPos
355 *
356 * restores the scan position previously saved with ExecMarkPos()
357 *
358 * NOTE: the semantics of this are that the first ExecProcNode following
359 * the restore operation will yield the same tuple as the first one following
360 * the mark operation. It is unspecified what happens to the plan node's
361 * result TupleTableSlot. (In most cases the result slot is unchanged by
362 * a restore, but the node may choose to clear it or to load it with the
363 * restored-to tuple.) Hence the caller should discard any previously
364 * returned TupleTableSlot after doing a restore.
365 */
366 void
367 ExecRestrPos(PlanState *node)
368 {
369 switch (nodeTag(node))
370 {
371 case T_IndexScanState:
372 ExecIndexRestrPos((IndexScanState *) node);
373 break;
374
375 case T_IndexOnlyScanState:
376 ExecIndexOnlyRestrPos((IndexOnlyScanState *) node);
377 break;
378
379 case T_CustomScanState:
380 ExecCustomRestrPos((CustomScanState *) node);
381 break;
382
383 case T_MaterialState:
384 ExecMaterialRestrPos((MaterialState *) node);
385 break;
386
387 case T_SortState:
388 ExecSortRestrPos((SortState *) node);
389 break;
390
391 case T_ResultState:
392 ExecResultRestrPos((ResultState *) node);
393 break;
394
395 default:
396 elog(ERROR, "unrecognized node type: %d", (int) nodeTag(node));
397 break;
398 }
399 }
400
401 /*
402 * ExecSupportsMarkRestore - does a Path support mark/restore?
403 *
404 * This is used during planning and so must accept a Path, not a Plan.
405 * We keep it here to be adjacent to the routines above, which also must
406 * know which plan types support mark/restore.
407 */
408 bool
409 ExecSupportsMarkRestore(Path *pathnode)
410 {
411 /*
412 * For consistency with the routines above, we do not examine the nodeTag
413 * but rather the pathtype, which is the Plan node type the Path would
414 * produce.
415 */
416 switch (pathnode->pathtype)
417 {
418 case T_IndexScan:
419 case T_IndexOnlyScan:
420 /*
421 * Not all index types support mark/restore.
422 */
423 return castNode(IndexPath, pathnode)->indexinfo->amcanmarkpos;
424
425 case T_Material:
426 case T_Sort:
427 return true;
428
429 case T_CustomScan:
430 {
431 CustomPath *customPath = castNode(CustomPath, pathnode);
432
433 if (customPath->flags & CUSTOMPATH_SUPPORT_MARK_RESTORE)
434 return true;
435 return false;
436 }
437 case T_Result:
438
439 /*
440 * Result supports mark/restore iff it has a child plan that does.
441 *
442 * We have to be careful here because there is more than one Path
443 * type that can produce a Result plan node.
444 */
445 if (IsA(pathnode, ProjectionPath))
446 return ExecSupportsMarkRestore(((ProjectionPath *) pathnode)->subpath);
447 else if (IsA(pathnode, MinMaxAggPath))
448 return false; /* childless Result */
449 else if (IsA(pathnode, GroupResultPath))
450 return false; /* childless Result */
451 else
452 {
453 /* Simple RTE_RESULT base relation */
454 Assert(IsA(pathnode, Path));
455 return false; /* childless Result */
456 }
457
458 case T_Append:
459 {
460 AppendPath *appendPath = castNode(AppendPath, pathnode);
461
462 /*
463 * If there's exactly one child, then there will be no Append
464 * in the final plan, so we can handle mark/restore if the
465 * child plan node can.
466 */
467 if (list_length(appendPath->subpaths) == 1)
468 return ExecSupportsMarkRestore((Path *) linitial(appendPath->subpaths));
469 /* Otherwise, Append can't handle it */
470 return false;
471 }
472
473 case T_MergeAppend:
474 {
475 MergeAppendPath *mapath = castNode(MergeAppendPath, pathnode);
476
477 /*
478 * Like the Append case above, single-subpath MergeAppends
479 * won't be in the final plan, so just return the child's
480 * mark/restore ability.
481 */
482 if (list_length(mapath->subpaths) == 1)
483 return ExecSupportsMarkRestore((Path *) linitial(mapath->subpaths));
484 /* Otherwise, MergeAppend can't handle it */
485 return false;
486 }
487
488 default:
489 break;
490 }
491
492 return false;
493 }
494
495 /*
496 * ExecSupportsBackwardScan - does a plan type support backwards scanning?
497 *
498 * Ideally, all plan types would support backwards scan, but that seems
499 * unlikely to happen soon. In some cases, a plan node passes the backwards
500 * scan down to its children, and so supports backwards scan only if its
501 * children do. Therefore, this routine must be passed a complete plan tree.
502 */
503 bool
504 ExecSupportsBackwardScan(Plan *node)
505 {
506 if (node == NULL)
507 return false;
508
509 /*
510 * Parallel-aware nodes return a subset of the tuples in each worker, and
511 * in general we can't expect to have enough bookkeeping state to know
512 * which ones we returned in this worker as opposed to some other worker.
513 */
514 if (node->parallel_aware)
515 return false;
516
517 switch (nodeTag(node))
518 {
519 case T_Result:
520 if (outerPlan(node) != NULL)
521 return ExecSupportsBackwardScan(outerPlan(node));
522 else
523 return false;
524
525 case T_Append:
526 {
527 ListCell *l;
528
529 foreach(l, ((Append *) node)->appendplans)
530 {
531 if (!ExecSupportsBackwardScan((Plan *) lfirst(l)))
532 return false;
533 }
534 /* need not check tlist because Append doesn't evaluate it */
535 return true;
536 }
537
538 case T_SampleScan:
539 /* Simplify life for tablesample methods by disallowing this */
540 return false;
541
542 case T_Gather:
543 return false;
544
545 case T_IndexScan:
546 return IndexSupportsBackwardScan(((IndexScan *) node)->indexid);
547
548 case T_IndexOnlyScan:
549 return IndexSupportsBackwardScan(((IndexOnlyScan *) node)->indexid);
550
551 case T_SubqueryScan:
552 return ExecSupportsBackwardScan(((SubqueryScan *) node)->subplan);
553
554 case T_CustomScan:
555 {
556 uint32 flags = ((CustomScan *) node)->flags;
557
558 if (flags & CUSTOMPATH_SUPPORT_BACKWARD_SCAN)
559 return true;
560 }
561 return false;
562
563 case T_SeqScan:
564 case T_TidScan:
565 case T_FunctionScan:
566 case T_ValuesScan:
567 case T_CteScan:
568 case T_Material:
569 case T_Sort:
570 /* these don't evaluate tlist */
571 return true;
572
573 case T_IncrementalSort:
574
575 /*
576 * Unlike full sort, incremental sort keeps only a single group of
577 * tuples in memory, so it can't scan backwards.
578 */
579 return false;
580
581 case T_LockRows:
582 case T_Limit:
583 return ExecSupportsBackwardScan(outerPlan(node));
584
585 default:
586 return false;
587 }
588 }
589
590 /*
591 * An IndexScan or IndexOnlyScan node supports backward scan only if the
592 * index's AM does.
593 */
594 static bool
595 IndexSupportsBackwardScan(Oid indexid)
596 {
597 bool result;
598 HeapTuple ht_idxrel;
599 Form_pg_class idxrelrec;
600 IndexAmRoutine *amroutine;
601
602 /* Fetch the pg_class tuple of the index relation */
603 ht_idxrel = SearchSysCache1(RELOID, ObjectIdGetDatum(indexid));
604 if (!HeapTupleIsValid(ht_idxrel))
605 elog(ERROR, "cache lookup failed for relation %u", indexid);
606 idxrelrec = (Form_pg_class) GETSTRUCT(ht_idxrel);
607
608 /* Fetch the index AM's API struct */
609 amroutine = GetIndexAmRoutineByAmId(idxrelrec->relam, false);
610
611 result = amroutine->amcanbackward;
612
613 pfree(amroutine);
614 ReleaseSysCache(ht_idxrel);
615
616 return result;
617 }
618
619 /*
620 * ExecMaterializesOutput - does a plan type materialize its output?
621 *
622 * Returns true if the plan node type is one that automatically materializes
623 * its output (typically by keeping it in a tuplestore). For such plans,
624 * a rescan without any parameter change will have zero startup cost and
625 * very low per-tuple cost.
626 */
627 bool
628 ExecMaterializesOutput(NodeTag plantype)
629 {
630 switch (plantype)
631 {
632 case T_Material:
633 case T_FunctionScan:
634 case T_TableFuncScan:
635 case T_CteScan:
636 case T_NamedTuplestoreScan:
637 case T_WorkTableScan:
638 case T_Sort:
639 return true;
640
641 default:
642 break;
643 }
644
645 return false;
646 }
647