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  if (!node->noCount &&
134  node->position - node->offset >= node->count)
135  {
136  node->lstate = LIMIT_WINDOWEND;
137 
138  /*
139  * If we know we won't need to back up, we can release
140  * resources at this point.
141  */
142  if (!(node->ps.state->es_top_eflags & EXEC_FLAG_BACKWARD))
143  (void) ExecShutdownNode(outerPlan);
144 
145  return NULL;
146  }
147 
148  /*
149  * Get next tuple from subplan, if any.
150  */
151  slot = ExecProcNode(outerPlan);
152  if (TupIsNull(slot))
153  {
154  node->lstate = LIMIT_SUBPLANEOF;
155  return NULL;
156  }
157  node->subSlot = slot;
158  node->position++;
159  }
160  else
161  {
162  /*
163  * Backwards scan, so check for stepping off start of window.
164  * As above, change only state-machine status if so.
165  */
166  if (node->position <= node->offset + 1)
167  {
168  node->lstate = LIMIT_WINDOWSTART;
169  return NULL;
170  }
171 
172  /*
173  * Get previous tuple from subplan; there should be one!
174  */
175  slot = ExecProcNode(outerPlan);
176  if (TupIsNull(slot))
177  elog(ERROR, "LIMIT subplan failed to run backwards");
178  node->subSlot = slot;
179  node->position--;
180  }
181  break;
182 
183  case LIMIT_SUBPLANEOF:
184  if (ScanDirectionIsForward(direction))
185  return NULL;
186 
187  /*
188  * Backing up from subplan EOF, so re-fetch previous tuple; there
189  * should be one! Note previous tuple must be in window.
190  */
191  slot = ExecProcNode(outerPlan);
192  if (TupIsNull(slot))
193  elog(ERROR, "LIMIT subplan failed to run backwards");
194  node->subSlot = slot;
195  node->lstate = LIMIT_INWINDOW;
196  /* position does not change 'cause we didn't advance it before */
197  break;
198 
199  case LIMIT_WINDOWEND:
200  if (ScanDirectionIsForward(direction))
201  return NULL;
202 
203  /*
204  * Backing up from window end: simply re-return the last tuple
205  * fetched from the subplan.
206  */
207  slot = node->subSlot;
208  node->lstate = LIMIT_INWINDOW;
209  /* position does not change 'cause we didn't advance it before */
210  break;
211 
212  case LIMIT_WINDOWSTART:
213  if (!ScanDirectionIsForward(direction))
214  return NULL;
215 
216  /*
217  * Advancing after having backed off window start: simply
218  * re-return the last tuple fetched from the subplan.
219  */
220  slot = node->subSlot;
221  node->lstate = LIMIT_INWINDOW;
222  /* position does not change 'cause we didn't change it before */
223  break;
224 
225  default:
226  elog(ERROR, "impossible LIMIT state: %d",
227  (int) node->lstate);
228  slot = NULL; /* keep compiler quiet */
229  break;
230  }
231 
232  /* Return the current tuple */
233  Assert(!TupIsNull(slot));
234 
235  return slot;
236 }
237 
238 /*
239  * Evaluate the limit/offset expressions --- done at startup or rescan.
240  *
241  * This is also a handy place to reset the current-position state info.
242  */
243 static void
245 {
246  ExprContext *econtext = node->ps.ps_ExprContext;
247  Datum val;
248  bool isNull;
249 
250  if (node->limitOffset)
251  {
253  econtext,
254  &isNull);
255  /* Interpret NULL offset as no offset */
256  if (isNull)
257  node->offset = 0;
258  else
259  {
260  node->offset = DatumGetInt64(val);
261  if (node->offset < 0)
262  ereport(ERROR,
263  (errcode(ERRCODE_INVALID_ROW_COUNT_IN_RESULT_OFFSET_CLAUSE),
264  errmsg("OFFSET must not be negative")));
265  }
266  }
267  else
268  {
269  /* No OFFSET supplied */
270  node->offset = 0;
271  }
272 
273  if (node->limitCount)
274  {
276  econtext,
277  &isNull);
278  /* Interpret NULL count as no count (LIMIT ALL) */
279  if (isNull)
280  {
281  node->count = 0;
282  node->noCount = true;
283  }
284  else
285  {
286  node->count = DatumGetInt64(val);
287  if (node->count < 0)
288  ereport(ERROR,
289  (errcode(ERRCODE_INVALID_ROW_COUNT_IN_LIMIT_CLAUSE),
290  errmsg("LIMIT must not be negative")));
291  node->noCount = false;
292  }
293  }
294  else
295  {
296  /* No COUNT supplied */
297  node->count = 0;
298  node->noCount = true;
299  }
300 
301  /* Reset position to start-of-scan */
302  node->position = 0;
303  node->subSlot = NULL;
304 
305  /* Set state-machine state */
306  node->lstate = LIMIT_RESCAN;
307 
308  /*
309  * Notify child node about limit. Note: think not to "optimize" by
310  * skipping ExecSetTupleBound if compute_tuples_needed returns < 0. We
311  * must update the child node anyway, in case this is a rescan and the
312  * previous time we got a different result.
313  */
315 }
316 
317 /*
318  * Compute the maximum number of tuples needed to satisfy this Limit node.
319  * Return a negative value if there is not a determinable limit.
320  */
321 static int64
323 {
324  if (node->noCount)
325  return -1;
326  /* Note: if this overflows, we'll return a negative value, which is OK */
327  return node->count + node->offset;
328 }
329 
330 /* ----------------------------------------------------------------
331  * ExecInitLimit
332  *
333  * This initializes the limit node state structures and
334  * the node's subplan.
335  * ----------------------------------------------------------------
336  */
337 LimitState *
338 ExecInitLimit(Limit *node, EState *estate, int eflags)
339 {
340  LimitState *limitstate;
341  Plan *outerPlan;
342 
343  /* check for unsupported flags */
344  Assert(!(eflags & EXEC_FLAG_MARK));
345 
346  /*
347  * create state structure
348  */
349  limitstate = makeNode(LimitState);
350  limitstate->ps.plan = (Plan *) node;
351  limitstate->ps.state = estate;
352  limitstate->ps.ExecProcNode = ExecLimit;
353 
354  limitstate->lstate = LIMIT_INITIAL;
355 
356  /*
357  * Miscellaneous initialization
358  *
359  * Limit nodes never call ExecQual or ExecProject, but they need an
360  * exprcontext anyway to evaluate the limit/offset parameters in.
361  */
362  ExecAssignExprContext(estate, &limitstate->ps);
363 
364  /*
365  * initialize outer plan
366  */
367  outerPlan = outerPlan(node);
368  outerPlanState(limitstate) = ExecInitNode(outerPlan, estate, eflags);
369 
370  /*
371  * initialize child expressions
372  */
373  limitstate->limitOffset = ExecInitExpr((Expr *) node->limitOffset,
374  (PlanState *) limitstate);
375  limitstate->limitCount = ExecInitExpr((Expr *) node->limitCount,
376  (PlanState *) limitstate);
377 
378  /*
379  * Initialize result type.
380  */
381  ExecInitResultTypeTL(&limitstate->ps);
382 
383  limitstate->ps.resultopsset = true;
384  limitstate->ps.resultops = ExecGetResultSlotOps(outerPlanState(limitstate),
385  &limitstate->ps.resultopsfixed);
386 
387  /*
388  * limit nodes do no projections, so initialize projection info for this
389  * node appropriately
390  */
391  limitstate->ps.ps_ProjInfo = NULL;
392 
393  return limitstate;
394 }
395 
396 /* ----------------------------------------------------------------
397  * ExecEndLimit
398  *
399  * This shuts down the subplan and frees resources allocated
400  * to this node.
401  * ----------------------------------------------------------------
402  */
403 void
405 {
406  ExecFreeExprContext(&node->ps);
408 }
409 
410 
411 void
413 {
414  /*
415  * Recompute limit/offset in case parameters changed, and reset the state
416  * machine. We must do this before rescanning our child node, in case
417  * it's a Sort that we are passing the parameters down to.
418  */
419  recompute_limits(node);
420 
421  /*
422  * if chgParam of subnode is not null then plan will be re-scanned by
423  * first ExecProcNode.
424  */
425  if (node->ps.lefttree->chgParam == NULL)
426  ExecReScan(node->ps.lefttree);
427 }
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:980
void ExecEndLimit(LimitState *node)
Definition: nodeLimit.c:404
const TupleTableSlotOps * ExecGetResultSlotOps(PlanState *planstate, bool *isfixed)
Definition: execUtils.c:463
#define ScanDirectionIsForward(direction)
Definition: sdir.h:55
bool noCount
Definition: execnodes.h:2355
#define castNode(_type_, nodeptr)
Definition: nodes.h:594
bool ExecShutdownNode(PlanState *node)
Definition: execProcnode.c:742
void ExecEndNode(PlanState *node)
Definition: execProcnode.c:538
ExprContext * ps_ExprContext
Definition: execnodes.h:979
void ExecReScan(PlanState *node)
Definition: execAmi.c:77
int errcode(int sqlerrcode)
Definition: elog.c:570
void ExecReScanLimit(LimitState *node)
Definition: nodeLimit.c:412
EState * state
Definition: execnodes.h:942
LimitStateCond lstate
Definition: execnodes.h:2356
ExprState * limitCount
Definition: execnodes.h:2352
Node * limitOffset
Definition: plannodes.h:968
int64 position
Definition: execnodes.h:2357
void ExecFreeExprContext(PlanState *planstate)
Definition: execUtils.c:614
ScanDirection es_direction
Definition: execnodes.h:502
const TupleTableSlotOps * resultops
Definition: execnodes.h:1015
void ExecSetTupleBound(int64 tuples_needed, PlanState *child_node)
Definition: execProcnode.c:812
int64 count
Definition: execnodes.h:2354
struct PlanState * lefttree
Definition: execnodes.h:962
#define ERROR
Definition: elog.h:43
int64 offset
Definition: execnodes.h:2353
Node * limitCount
Definition: plannodes.h:969
#define DatumGetInt64(X)
Definition: postgres.h:607
#define EXEC_FLAG_BACKWARD
Definition: executor.h:58
#define outerPlanState(node)
Definition: execnodes.h:1034
void ExecInitResultTypeTL(PlanState *planstate)
Definition: execTuples.c:1720
ScanDirection
Definition: sdir.h:22
ExprState * limitOffset
Definition: execnodes.h:2351
#define TupIsNull(slot)
Definition: tuptable.h:293
#define ereport(elevel, rest)
Definition: elog.h:141
bool resultopsset
Definition: execnodes.h:1023
Bitmapset * chgParam
Definition: execnodes.h:972
#define outerPlan(node)
Definition: plannodes.h:170
ExecProcNodeMtd ExecProcNode
Definition: execnodes.h:946
uintptr_t Datum
Definition: postgres.h:367
static TupleTableSlot * ExecProcNode(PlanState *node)
Definition: executor.h:235
Plan * plan
Definition: execnodes.h:940
#define makeNode(_type_)
Definition: nodes.h:573
#define Assert(condition)
Definition: c.h:732
#define EXEC_FLAG_MARK
Definition: executor.h:59
TupleTableSlot * subSlot
Definition: execnodes.h:2358
void ExecAssignExprContext(EState *estate, PlanState *planstate)
Definition: execUtils.c:444
bool resultopsfixed
Definition: execnodes.h:1019
int errmsg(const char *fmt,...)
Definition: elog.c:784
int es_top_eflags
Definition: execnodes.h:556
#define elog(elevel,...)
Definition: elog.h:226
LimitState * ExecInitLimit(Limit *node, EState *estate, int eflags)
Definition: nodeLimit.c:338
static void recompute_limits(LimitState *node)
Definition: nodeLimit.c:244
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:139
long val
Definition: informix.c:684
PlanState ps
Definition: execnodes.h:2350
static int64 compute_tuples_needed(LimitState *node)
Definition: nodeLimit.c:322