PostgreSQL Source Code  git master
execAmi.c
Go to the documentation of this file.
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"
23 #include "executor/nodeBitmapOr.h"
24 #include "executor/nodeCtescan.h"
25 #include "executor/nodeCustom.h"
28 #include "executor/nodeGather.h"
30 #include "executor/nodeGroup.h"
31 #include "executor/nodeHash.h"
32 #include "executor/nodeHashjoin.h"
35 #include "executor/nodeIndexscan.h"
36 #include "executor/nodeLimit.h"
37 #include "executor/nodeLockRows.h"
38 #include "executor/nodeMaterial.h"
40 #include "executor/nodeMergejoin.h"
43 #include "executor/nodeNestloop.h"
46 #include "executor/nodeResult.h"
48 #include "executor/nodeSeqscan.h"
49 #include "executor/nodeSetOp.h"
50 #include "executor/nodeSort.h"
51 #include "executor/nodeSubplan.h"
54 #include "executor/nodeTidscan.h"
55 #include "executor/nodeUnique.h"
57 #include "executor/nodeWindowAgg.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
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)
121  if (node->righttree != NULL)
123  }
124 
125  /* Call expression callbacks */
126  if (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:
138  break;
139 
140  case T_ModifyTableState:
142  break;
143 
144  case T_AppendState:
145  ExecReScanAppend((AppendState *) node);
146  break;
147 
148  case T_MergeAppendState:
150  break;
151 
154  break;
155 
156  case T_BitmapAndState:
158  break;
159 
160  case T_BitmapOrState:
162  break;
163 
164  case T_SeqScanState:
166  break;
167 
168  case T_SampleScanState:
170  break;
171 
172  case T_GatherState:
173  ExecReScanGather((GatherState *) node);
174  break;
175 
176  case T_GatherMergeState:
178  break;
179 
180  case T_IndexScanState:
182  break;
183 
186  break;
187 
190  break;
191 
194  break;
195 
196  case T_TidScanState:
198  break;
199 
200  case T_SubqueryScanState:
202  break;
203 
204  case T_FunctionScanState:
206  break;
207 
210  break;
211 
212  case T_ValuesScanState:
214  break;
215 
216  case T_CteScanState:
218  break;
219 
222  break;
223 
226  break;
227 
228  case T_ForeignScanState:
230  break;
231 
232  case T_CustomScanState:
234  break;
235 
236  case T_NestLoopState:
238  break;
239 
240  case T_MergeJoinState:
242  break;
243 
244  case T_HashJoinState:
246  break;
247 
248  case T_MaterialState:
250  break;
251 
252  case T_SortState:
253  ExecReScanSort((SortState *) node);
254  break;
255 
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:
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:
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
319 {
320  switch (nodeTag(node))
321  {
322  case T_IndexScanState:
324  break;
325 
328  break;
329 
330  case T_CustomScanState:
332  break;
333 
334  case T_MaterialState:
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
368 {
369  switch (nodeTag(node))
370  {
371  case T_IndexScanState:
373  break;
374 
377  break;
378 
379  case T_CustomScanState:
381  break;
382 
383  case T_MaterialState:
385  break;
386 
387  case T_SortState:
388  ExecSortRestrPos((SortState *) node);
389  break;
390 
391  case T_ResultState:
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
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  case T_Material:
421  case T_Sort:
422  return true;
423 
424  case T_CustomScan:
425  {
426  CustomPath *customPath = castNode(CustomPath, pathnode);
427 
428  if (customPath->flags & CUSTOMPATH_SUPPORT_MARK_RESTORE)
429  return true;
430  return false;
431  }
432  case T_Result:
433 
434  /*
435  * Result supports mark/restore iff it has a child plan that does.
436  *
437  * We have to be careful here because there is more than one Path
438  * type that can produce a Result plan node.
439  */
440  if (IsA(pathnode, ProjectionPath))
441  return ExecSupportsMarkRestore(((ProjectionPath *) pathnode)->subpath);
442  else if (IsA(pathnode, MinMaxAggPath))
443  return false; /* childless Result */
444  else if (IsA(pathnode, GroupResultPath))
445  return false; /* childless Result */
446  else
447  {
448  /* Simple RTE_RESULT base relation */
449  Assert(IsA(pathnode, Path));
450  return false; /* childless Result */
451  }
452 
453  case T_Append:
454  {
455  AppendPath *appendPath = castNode(AppendPath, pathnode);
456 
457  /*
458  * If there's exactly one child, then there will be no Append
459  * in the final plan, so we can handle mark/restore if the
460  * child plan node can.
461  */
462  if (list_length(appendPath->subpaths) == 1)
463  return ExecSupportsMarkRestore((Path *) linitial(appendPath->subpaths));
464  /* Otherwise, Append can't handle it */
465  return false;
466  }
467 
468  case T_MergeAppend:
469  {
470  MergeAppendPath *mapath = castNode(MergeAppendPath, pathnode);
471 
472  /*
473  * Like the Append case above, single-subpath MergeAppends
474  * won't be in the final plan, so just return the child's
475  * mark/restore ability.
476  */
477  if (list_length(mapath->subpaths) == 1)
478  return ExecSupportsMarkRestore((Path *) linitial(mapath->subpaths));
479  /* Otherwise, MergeAppend can't handle it */
480  return false;
481  }
482 
483  default:
484  break;
485  }
486 
487  return false;
488 }
489 
490 /*
491  * ExecSupportsBackwardScan - does a plan type support backwards scanning?
492  *
493  * Ideally, all plan types would support backwards scan, but that seems
494  * unlikely to happen soon. In some cases, a plan node passes the backwards
495  * scan down to its children, and so supports backwards scan only if its
496  * children do. Therefore, this routine must be passed a complete plan tree.
497  */
498 bool
500 {
501  if (node == NULL)
502  return false;
503 
504  /*
505  * Parallel-aware nodes return a subset of the tuples in each worker, and
506  * in general we can't expect to have enough bookkeeping state to know
507  * which ones we returned in this worker as opposed to some other worker.
508  */
509  if (node->parallel_aware)
510  return false;
511 
512  switch (nodeTag(node))
513  {
514  case T_Result:
515  if (outerPlan(node) != NULL)
516  return ExecSupportsBackwardScan(outerPlan(node));
517  else
518  return false;
519 
520  case T_Append:
521  {
522  ListCell *l;
523 
524  foreach(l, ((Append *) node)->appendplans)
525  {
526  if (!ExecSupportsBackwardScan((Plan *) lfirst(l)))
527  return false;
528  }
529  /* need not check tlist because Append doesn't evaluate it */
530  return true;
531  }
532 
533  case T_SampleScan:
534  /* Simplify life for tablesample methods by disallowing this */
535  return false;
536 
537  case T_Gather:
538  return false;
539 
540  case T_IndexScan:
541  return IndexSupportsBackwardScan(((IndexScan *) node)->indexid);
542 
543  case T_IndexOnlyScan:
544  return IndexSupportsBackwardScan(((IndexOnlyScan *) node)->indexid);
545 
546  case T_SubqueryScan:
547  return ExecSupportsBackwardScan(((SubqueryScan *) node)->subplan);
548 
549  case T_CustomScan:
550  {
551  uint32 flags = ((CustomScan *) node)->flags;
552 
554  return true;
555  }
556  return false;
557 
558  case T_SeqScan:
559  case T_TidScan:
560  case T_FunctionScan:
561  case T_ValuesScan:
562  case T_CteScan:
563  case T_Material:
564  case T_Sort:
565  /* these don't evaluate tlist */
566  return true;
567 
568  case T_IncrementalSort:
569 
570  /*
571  * Unlike full sort, incremental sort keeps only a single group of
572  * tuples in memory, so it can't scan backwards.
573  */
574  return false;
575 
576  case T_LockRows:
577  case T_Limit:
578  return ExecSupportsBackwardScan(outerPlan(node));
579 
580  default:
581  return false;
582  }
583 }
584 
585 /*
586  * An IndexScan or IndexOnlyScan node supports backward scan only if the
587  * index's AM does.
588  */
589 static bool
591 {
592  bool result;
593  HeapTuple ht_idxrel;
594  Form_pg_class idxrelrec;
595  IndexAmRoutine *amroutine;
596 
597  /* Fetch the pg_class tuple of the index relation */
598  ht_idxrel = SearchSysCache1(RELOID, ObjectIdGetDatum(indexid));
599  if (!HeapTupleIsValid(ht_idxrel))
600  elog(ERROR, "cache lookup failed for relation %u", indexid);
601  idxrelrec = (Form_pg_class) GETSTRUCT(ht_idxrel);
602 
603  /* Fetch the index AM's API struct */
604  amroutine = GetIndexAmRoutineByAmId(idxrelrec->relam, false);
605 
606  result = amroutine->amcanbackward;
607 
608  pfree(amroutine);
609  ReleaseSysCache(ht_idxrel);
610 
611  return result;
612 }
613 
614 /*
615  * ExecMaterializesOutput - does a plan type materialize its output?
616  *
617  * Returns true if the plan node type is one that automatically materializes
618  * its output (typically by keeping it in a tuplestore). For such plans,
619  * a rescan without any parameter change will have zero startup cost and
620  * very low per-tuple cost.
621  */
622 bool
624 {
625  switch (plantype)
626  {
627  case T_Material:
628  case T_FunctionScan:
629  case T_TableFuncScan:
630  case T_CteScan:
632  case T_WorkTableScan:
633  case T_Sort:
634  return true;
635 
636  default:
637  break;
638  }
639 
640  return false;
641 }
void ExecReScanBitmapHeapScan(BitmapHeapScanState *node)
#define IsA(nodeptr, _type_)
Definition: nodes.h:580
void ExecReScanGroup(GroupState *node)
Definition: nodeGroup.c:241
bool ExecSupportsMarkRestore(Path *pathnode)
Definition: execAmi.c:409
void ExecMaterialRestrPos(MaterialState *node)
Definition: nodeMaterial.c:295
#define GETSTRUCT(TUP)
Definition: htup_details.h:655
#define CUSTOMPATH_SUPPORT_BACKWARD_SCAN
Definition: extensible.h:81
void ExecReScanModifyTable(ModifyTableState *node)
Instrumentation * instrument
Definition: execnodes.h:955
#define castNode(_type_, nodeptr)
Definition: nodes.h:598
#define CUSTOMPATH_SUPPORT_MARK_RESTORE
Definition: extensible.h:82
List * initPlan
Definition: execnodes.h:970
void ExecReScanMaterial(MaterialState *node)
Definition: nodeMaterial.c:318
void ExecIndexOnlyRestrPos(IndexOnlyScanState *node)
ExprContext * ps_ExprContext
Definition: execnodes.h:984
void ExecReScanLockRows(LockRowsState *node)
Definition: nodeLockRows.c:390
void ExecReScan(PlanState *node)
Definition: execAmi.c:76
void ExecReScanFunctionScan(FunctionScanState *node)
List * subPlan
Definition: execnodes.h:972
Definition: nodes.h:49
void ExecReScanIndexOnlyScan(IndexOnlyScanState *node)
uint32 flags
Definition: pathnodes.h:1377
Definition: nodes.h:76
void ExecReScanLimit(LimitState *node)
Definition: nodeLimit.c:543
void ExecReScanWorkTableScan(WorkTableScanState *node)
struct PlanState * righttree
Definition: execnodes.h:968
unsigned int Oid
Definition: postgres_ext.h:31
NodeTag
Definition: nodes.h:26
void ExecReScanResult(ResultState *node)
Definition: nodeResult.c:260
void ExecResultRestrPos(ResultState *node)
Definition: nodeResult.c:162
void ExecReScanSetOp(SetOpState *node)
Definition: nodeSetOp.c:598
static bool IndexSupportsBackwardScan(Oid indexid)
Definition: execAmi.c:590
void ExecReScanSort(SortState *node)
Definition: nodeSort.c:303
void ExecReScanForeignScan(ForeignScanState *node)
struct PlanState * lefttree
Definition: execnodes.h:967
void InstrEndLoop(Instrumentation *instr)
Definition: instrument.c:121
NodeTag pathtype
Definition: pathnodes.h:1142
List * subpaths
Definition: pathnodes.h:1404
void ExecCustomRestrPos(CustomScanState *node)
Definition: nodeCustom.c:151
void ExecRestrPos(PlanState *node)
Definition: execAmi.c:367
void ExecReScanHash(HashState *node)
Definition: nodeHash.c:2192
void pfree(void *pointer)
Definition: mcxt.c:1056
void ExecIndexOnlyMarkPos(IndexOnlyScanState *node)
#define linitial(l)
Definition: pg_list.h:195
void ExecReScanProjectSet(ProjectSetState *node)
Definition: nodes.h:46
#define ObjectIdGetDatum(X)
Definition: postgres.h:507
#define ERROR
Definition: elog.h:43
struct PlanState * planstate
Definition: execnodes.h:853
void ExecReScanSetParamPlan(SubPlanState *node, PlanState *parent)
Definition: nodeSubplan.c:1268
IndexAmRoutine * GetIndexAmRoutineByAmId(Oid amoid, bool noerror)
Definition: amapi.c:56
#define DEBUG2
Definition: elog.h:24
void ExecSortMarkPos(SortState *node)
Definition: nodeSort.c:270
void ExecReScanBitmapIndexScan(BitmapIndexScanState *node)
bool amcanbackward
Definition: amapi.h:181
void ExecIndexMarkPos(IndexScanState *node)
void ExecReScanUnique(UniqueState *node)
Definition: nodeUnique.c:181
void ExecReScanIndexScan(IndexScanState *node)
void ExecReScanGatherMerge(GatherMergeState *node)
bool parallel_aware
Definition: plannodes.h:135
void ExecReScanMergeAppend(MergeAppendState *node)
unsigned int uint32
Definition: c.h:367
void ExecReScanNestLoop(NestLoopState *node)
Definition: nodeNestloop.c:392
static SPIPlanPtr splan
Definition: regress.c:259
Bitmapset * chgParam
Definition: execnodes.h:977
#define outerPlan(node)
Definition: plannodes.h:172
void ExecReScanGather(GatherState *node)
Definition: nodeGather.c:443
void ExecReScanNamedTuplestoreScan(NamedTuplestoreScanState *node)
HeapTuple SearchSysCache1(int cacheId, Datum key1)
Definition: syscache.c:1116
void ExecReScanAppend(AppendState *node)
Definition: nodeAppend.c:314
void ReleaseSysCache(HeapTuple tuple)
Definition: syscache.c:1164
bool ExecSupportsBackwardScan(Plan *node)
Definition: execAmi.c:499
void ExecReScanSubqueryScan(SubqueryScanState *node)
void ExecReScanIncrementalSort(IncrementalSortState *node)
void ExecCustomMarkPos(CustomScanState *node)
Definition: nodeCustom.c:140
Plan * plan
Definition: execnodes.h:945
void ExecMarkPos(PlanState *node)
Definition: execAmi.c:318
void ExecReScanBitmapOr(BitmapOrState *node)
Definition: nodeBitmapOr.c:219
void ExecReScanRecursiveUnion(RecursiveUnionState *node)
void UpdateChangedParamSet(PlanState *node, Bitmapset *newchg)
Definition: execUtils.c:843
void bms_free(Bitmapset *a)
Definition: bitmapset.c:208
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
#define Assert(condition)
Definition: c.h:738
#define lfirst(lc)
Definition: pg_list.h:190
void ExecReScanBitmapAnd(BitmapAndState *node)
void ExecReScanAgg(AggState *node)
Definition: nodeAgg.c:4550
void ExecSortRestrPos(SortState *node)
Definition: nodeSort.c:288
void ExecResultMarkPos(ResultState *node)
Definition: nodeResult.c:147
static int list_length(const List *l)
Definition: pg_list.h:169
Bitmapset * extParam
Definition: plannodes.h:160
void ReScanExprContext(ExprContext *econtext)
Definition: execUtils.c:443
void ExecIndexRestrPos(IndexScanState *node)
#define nodeTag(nodeptr)
Definition: nodes.h:534
void ExecReScanValuesScan(ValuesScanState *node)
FormData_pg_class * Form_pg_class
Definition: pg_class.h:153
Definition: nodes.h:82
#define elog(elevel,...)
Definition: elog.h:214
void ExecReScanSampleScan(SampleScanState *node)
void ExecReScanCteScan(CteScanState *node)
Definition: nodeCtescan.c:319
void ExecMaterialMarkPos(MaterialState *node)
Definition: nodeMaterial.c:267
void ExecReScanWindowAgg(WindowAggState *node)
bool ExecMaterializesOutput(NodeTag plantype)
Definition: execAmi.c:623
void ExecReScanTidScan(TidScanState *node)
Definition: nodeTidscan.c:445
void ExecReScanMergeJoin(MergeJoinState *node)
void ExecReScanCustomScan(CustomScanState *node)
Definition: nodeCustom.c:133
void ExecReScanTableFuncScan(TableFuncScanState *node)
Datum subpath(PG_FUNCTION_ARGS)
Definition: ltree_op.c:241
void ExecReScanSeqScan(SeqScanState *node)
Definition: nodeSeqscan.c:224
Definition: nodes.h:87
void ExecReScanHashJoin(HashJoinState *node)