PostgreSQL Source Code  git master
nodeLimit.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * nodeLimit.c
4  * Routines to handle limiting of query results where appropriate
5  *
6  * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
7  * Portions Copyright (c) 1994, Regents of the University of California
8  *
9  *
10  * IDENTIFICATION
11  * src/backend/executor/nodeLimit.c
12  *
13  *-------------------------------------------------------------------------
14  */
15 /*
16  * INTERFACE ROUTINES
17  * ExecLimit - extract a limited range of tuples
18  * ExecInitLimit - initialize node and subnodes..
19  * ExecEndLimit - shutdown node and subnodes
20  */
21 
22 #include "postgres.h"
23 
24 #include "executor/executor.h"
25 #include "executor/nodeLimit.h"
26 #include "miscadmin.h"
27 #include "nodes/nodeFuncs.h"
28 
29 static void recompute_limits(LimitState *node);
30 static int64 compute_tuples_needed(LimitState *node);
31 
32 
33 /* ----------------------------------------------------------------
34  * ExecLimit
35  *
36  * This is a very simple node which just performs LIMIT/OFFSET
37  * filtering on the stream of tuples returned by a subplan.
38  * ----------------------------------------------------------------
39  */
40 static TupleTableSlot * /* return: a tuple or NULL */
42 {
43  LimitState *node = castNode(LimitState, pstate);
44  ScanDirection direction;
45  TupleTableSlot *slot;
47 
49 
50  /*
51  * get information from the node
52  */
53  direction = node->ps.state->es_direction;
54  outerPlan = outerPlanState(node);
55 
56  /*
57  * The main logic is a simple state machine.
58  */
59  switch (node->lstate)
60  {
61  case LIMIT_INITIAL:
62 
63  /*
64  * First call for this node, so compute limit/offset. (We can't do
65  * this any earlier, because parameters from upper nodes will not
66  * be set during ExecInitLimit.) This also sets position = 0 and
67  * changes the state to LIMIT_RESCAN.
68  */
69  recompute_limits(node);
70 
71  /* FALL THRU */
72 
73  case LIMIT_RESCAN:
74 
75  /*
76  * If backwards scan, just return NULL without changing state.
77  */
78  if (!ScanDirectionIsForward(direction))
79  return NULL;
80 
81  /*
82  * Check for empty window; if so, treat like empty subplan.
83  */
84  if (node->count <= 0 && !node->noCount)
85  {
86  node->lstate = LIMIT_EMPTY;
87  return NULL;
88  }
89 
90  /*
91  * Fetch rows from subplan until we reach position > offset.
92  */
93  for (;;)
94  {
95  slot = ExecProcNode(outerPlan);
96  if (TupIsNull(slot))
97  {
98  /*
99  * The subplan returns too few tuples for us to produce
100  * any output at all.
101  */
102  node->lstate = LIMIT_EMPTY;
103  return NULL;
104  }
105  node->subSlot = slot;
106  if (++node->position > node->offset)
107  break;
108  }
109 
110  /*
111  * Okay, we have the first tuple of the window.
112  */
113  node->lstate = LIMIT_INWINDOW;
114  break;
115 
116  case LIMIT_EMPTY:
117 
118  /*
119  * The subplan is known to return no tuples (or not more than
120  * OFFSET tuples, in general). So we return no tuples.
121  */
122  return NULL;
123 
124  case LIMIT_INWINDOW:
125  if (ScanDirectionIsForward(direction))
126  {
127  /*
128  * Forwards scan, so check for stepping off end of window. If
129  * we are at the end of the window, return NULL without
130  * advancing the subplan or the position variable; but change
131  * the state machine state to record having done so.
132  *
133  * Once at the end, ideally, we can shut down parallel
134  * resources but that would destroy the parallel context which
135  * would be required for rescans. To do that, we need to find
136  * a way to pass down more information about whether rescans
137  * are possible.
138  */
139  if (!node->noCount &&
140  node->position - node->offset >= node->count)
141  {
142  node->lstate = LIMIT_WINDOWEND;
143  return NULL;
144  }
145 
146  /*
147  * Get next tuple from subplan, if any.
148  */
149  slot = ExecProcNode(outerPlan);
150  if (TupIsNull(slot))
151  {
152  node->lstate = LIMIT_SUBPLANEOF;
153  return NULL;
154  }
155  node->subSlot = slot;
156  node->position++;
157  }
158  else
159  {
160  /*
161  * Backwards scan, so check for stepping off start of window.
162  * As above, change only state-machine status if so.
163  */
164  if (node->position <= node->offset + 1)
165  {
166  node->lstate = LIMIT_WINDOWSTART;
167  return NULL;
168  }
169 
170  /*
171  * Get previous tuple from subplan; there should be one!
172  */
173  slot = ExecProcNode(outerPlan);
174  if (TupIsNull(slot))
175  elog(ERROR, "LIMIT subplan failed to run backwards");
176  node->subSlot = slot;
177  node->position--;
178  }
179  break;
180 
181  case LIMIT_SUBPLANEOF:
182  if (ScanDirectionIsForward(direction))
183  return NULL;
184 
185  /*
186  * Backing up from subplan EOF, so re-fetch previous tuple; there
187  * should be one! Note previous tuple must be in window.
188  */
189  slot = ExecProcNode(outerPlan);
190  if (TupIsNull(slot))
191  elog(ERROR, "LIMIT subplan failed to run backwards");
192  node->subSlot = slot;
193  node->lstate = LIMIT_INWINDOW;
194  /* position does not change 'cause we didn't advance it before */
195  break;
196 
197  case LIMIT_WINDOWEND:
198  if (ScanDirectionIsForward(direction))
199  return NULL;
200 
201  /*
202  * Backing up from window end: simply re-return the last tuple
203  * fetched from the subplan.
204  */
205  slot = node->subSlot;
206  node->lstate = LIMIT_INWINDOW;
207  /* position does not change 'cause we didn't advance it before */
208  break;
209 
210  case LIMIT_WINDOWSTART:
211  if (!ScanDirectionIsForward(direction))
212  return NULL;
213 
214  /*
215  * Advancing after having backed off window start: simply
216  * re-return the last tuple fetched from the subplan.
217  */
218  slot = node->subSlot;
219  node->lstate = LIMIT_INWINDOW;
220  /* position does not change 'cause we didn't change it before */
221  break;
222 
223  default:
224  elog(ERROR, "impossible LIMIT state: %d",
225  (int) node->lstate);
226  slot = NULL; /* keep compiler quiet */
227  break;
228  }
229 
230  /* Return the current tuple */
231  Assert(!TupIsNull(slot));
232 
233  return slot;
234 }
235 
236 /*
237  * Evaluate the limit/offset expressions --- done at startup or rescan.
238  *
239  * This is also a handy place to reset the current-position state info.
240  */
241 static void
243 {
244  ExprContext *econtext = node->ps.ps_ExprContext;
245  Datum val;
246  bool isNull;
247 
248  if (node->limitOffset)
249  {
251  econtext,
252  &isNull);
253  /* Interpret NULL offset as no offset */
254  if (isNull)
255  node->offset = 0;
256  else
257  {
258  node->offset = DatumGetInt64(val);
259  if (node->offset < 0)
260  ereport(ERROR,
261  (errcode(ERRCODE_INVALID_ROW_COUNT_IN_RESULT_OFFSET_CLAUSE),
262  errmsg("OFFSET must not be negative")));
263  }
264  }
265  else
266  {
267  /* No OFFSET supplied */
268  node->offset = 0;
269  }
270 
271  if (node->limitCount)
272  {
274  econtext,
275  &isNull);
276  /* Interpret NULL count as no count (LIMIT ALL) */
277  if (isNull)
278  {
279  node->count = 0;
280  node->noCount = true;
281  }
282  else
283  {
284  node->count = DatumGetInt64(val);
285  if (node->count < 0)
286  ereport(ERROR,
287  (errcode(ERRCODE_INVALID_ROW_COUNT_IN_LIMIT_CLAUSE),
288  errmsg("LIMIT must not be negative")));
289  node->noCount = false;
290  }
291  }
292  else
293  {
294  /* No COUNT supplied */
295  node->count = 0;
296  node->noCount = true;
297  }
298 
299  /* Reset position to start-of-scan */
300  node->position = 0;
301  node->subSlot = NULL;
302 
303  /* Set state-machine state */
304  node->lstate = LIMIT_RESCAN;
305 
306  /*
307  * Notify child node about limit. Note: think not to "optimize" by
308  * skipping ExecSetTupleBound if compute_tuples_needed returns < 0. We
309  * must update the child node anyway, in case this is a rescan and the
310  * previous time we got a different result.
311  */
313 }
314 
315 /*
316  * Compute the maximum number of tuples needed to satisfy this Limit node.
317  * Return a negative value if there is not a determinable limit.
318  */
319 static int64
321 {
322  if (node->noCount)
323  return -1;
324  /* Note: if this overflows, we'll return a negative value, which is OK */
325  return node->count + node->offset;
326 }
327 
328 /* ----------------------------------------------------------------
329  * ExecInitLimit
330  *
331  * This initializes the limit node state structures and
332  * the node's subplan.
333  * ----------------------------------------------------------------
334  */
335 LimitState *
336 ExecInitLimit(Limit *node, EState *estate, int eflags)
337 {
338  LimitState *limitstate;
339  Plan *outerPlan;
340 
341  /* check for unsupported flags */
342  Assert(!(eflags & EXEC_FLAG_MARK));
343 
344  /*
345  * create state structure
346  */
347  limitstate = makeNode(LimitState);
348  limitstate->ps.plan = (Plan *) node;
349  limitstate->ps.state = estate;
350  limitstate->ps.ExecProcNode = ExecLimit;
351 
352  limitstate->lstate = LIMIT_INITIAL;
353 
354  /*
355  * Miscellaneous initialization
356  *
357  * Limit nodes never call ExecQual or ExecProject, but they need an
358  * exprcontext anyway to evaluate the limit/offset parameters in.
359  */
360  ExecAssignExprContext(estate, &limitstate->ps);
361 
362  /*
363  * initialize outer plan
364  */
365  outerPlan = outerPlan(node);
366  outerPlanState(limitstate) = ExecInitNode(outerPlan, estate, eflags);
367 
368  /*
369  * initialize child expressions
370  */
371  limitstate->limitOffset = ExecInitExpr((Expr *) node->limitOffset,
372  (PlanState *) limitstate);
373  limitstate->limitCount = ExecInitExpr((Expr *) node->limitCount,
374  (PlanState *) limitstate);
375 
376  /*
377  * Initialize result type.
378  */
379  ExecInitResultTypeTL(&limitstate->ps);
380 
381  limitstate->ps.resultopsset = true;
382  limitstate->ps.resultops = ExecGetResultSlotOps(outerPlanState(limitstate),
383  &limitstate->ps.resultopsfixed);
384 
385  /*
386  * limit nodes do no projections, so initialize projection info for this
387  * node appropriately
388  */
389  limitstate->ps.ps_ProjInfo = NULL;
390 
391  return limitstate;
392 }
393 
394 /* ----------------------------------------------------------------
395  * ExecEndLimit
396  *
397  * This shuts down the subplan and frees resources allocated
398  * to this node.
399  * ----------------------------------------------------------------
400  */
401 void
403 {
404  ExecFreeExprContext(&node->ps);
406 }
407 
408 
409 void
411 {
412  /*
413  * Recompute limit/offset in case parameters changed, and reset the state
414  * machine. We must do this before rescanning our child node, in case
415  * it's a Sort that we are passing the parameters down to.
416  */
417  recompute_limits(node);
418 
419  /*
420  * if chgParam of subnode is not null then plan will be re-scanned by
421  * first ExecProcNode.
422  */
423  if (node->ps.lefttree->chgParam == NULL)
424  ExecReScan(node->ps.lefttree);
425 }
static TupleTableSlot * ExecLimit(PlanState *pstate)
Definition: nodeLimit.c:41
static Datum ExecEvalExprSwitchContext(ExprState *state, ExprContext *econtext, bool *isNull)
Definition: executor.h:300
ProjectionInfo * ps_ProjInfo
Definition: execnodes.h:979
void ExecEndLimit(LimitState *node)
Definition: nodeLimit.c:402
const TupleTableSlotOps * ExecGetResultSlotOps(PlanState *planstate, bool *isfixed)
Definition: execUtils.c:463
#define ScanDirectionIsForward(direction)
Definition: sdir.h:55
bool noCount
Definition: execnodes.h:2350
#define castNode(_type_, nodeptr)
Definition: nodes.h:594
void ExecEndNode(PlanState *node)
Definition: execProcnode.c:537
ExprContext * ps_ExprContext
Definition: execnodes.h:978
void ExecReScan(PlanState *node)
Definition: execAmi.c:75
int errcode(int sqlerrcode)
Definition: elog.c:608
void ExecReScanLimit(LimitState *node)
Definition: nodeLimit.c:410
EState * state
Definition: execnodes.h:941
LimitStateCond lstate
Definition: execnodes.h:2351
ExprState * limitCount
Definition: execnodes.h:2347
Node * limitOffset
Definition: plannodes.h:972
int64 position
Definition: execnodes.h:2352
void ExecFreeExprContext(PlanState *planstate)
Definition: execUtils.c:614
ScanDirection es_direction
Definition: execnodes.h:501
const TupleTableSlotOps * resultops
Definition: execnodes.h:1014
void ExecSetTupleBound(int64 tuples_needed, PlanState *child_node)
Definition: execProcnode.c:811
int64 count
Definition: execnodes.h:2349
struct PlanState * lefttree
Definition: execnodes.h:961
#define ERROR
Definition: elog.h:43
int64 offset
Definition: execnodes.h:2348
Node * limitCount
Definition: plannodes.h:973
#define DatumGetInt64(X)
Definition: postgres.h:607
#define outerPlanState(node)
Definition: execnodes.h:1033
void ExecInitResultTypeTL(PlanState *planstate)
Definition: execTuples.c:1725
ScanDirection
Definition: sdir.h:22
ExprState * limitOffset
Definition: execnodes.h:2346
#define TupIsNull(slot)
Definition: tuptable.h:292
#define ereport(elevel, rest)
Definition: elog.h:141
bool resultopsset
Definition: execnodes.h:1022
Bitmapset * chgParam
Definition: execnodes.h:971
#define outerPlan(node)
Definition: plannodes.h:172
ExecProcNodeMtd ExecProcNode
Definition: execnodes.h:945
uintptr_t Datum
Definition: postgres.h:367
static TupleTableSlot * ExecProcNode(PlanState *node)
Definition: executor.h:235
Plan * plan
Definition: execnodes.h:939
#define makeNode(_type_)
Definition: nodes.h:573
#define Assert(condition)
Definition: c.h:739
#define EXEC_FLAG_MARK
Definition: executor.h:59
TupleTableSlot * subSlot
Definition: execnodes.h:2353
void ExecAssignExprContext(EState *estate, PlanState *planstate)
Definition: execUtils.c:444
bool resultopsfixed
Definition: execnodes.h:1018
int errmsg(const char *fmt,...)
Definition: elog.c:822
#define elog(elevel,...)
Definition: elog.h:228
LimitState * ExecInitLimit(Limit *node, EState *estate, int eflags)
Definition: nodeLimit.c:336
static void recompute_limits(LimitState *node)
Definition: nodeLimit.c:242
ExprState * ExecInitExpr(Expr *node, PlanState *parent)
Definition: execExpr.c:121
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:99
PlanState * ExecInitNode(Plan *node, EState *estate, int eflags)
Definition: execProcnode.c:138
long val
Definition: informix.c:664
PlanState ps
Definition: execnodes.h:2345
static int64 compute_tuples_needed(LimitState *node)
Definition: nodeLimit.c:320