PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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-2017, 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 "nodes/nodeFuncs.h"
27 
28 static void recompute_limits(LimitState *node);
29 static void pass_down_bound(LimitState *node, PlanState *child_node);
30 
31 
32 /* ----------------------------------------------------------------
33  * ExecLimit
34  *
35  * This is a very simple node which just performs LIMIT/OFFSET
36  * filtering on the stream of tuples returned by a subplan.
37  * ----------------------------------------------------------------
38  */
39 TupleTableSlot * /* return: a tuple or NULL */
41 {
42  ScanDirection direction;
43  TupleTableSlot *slot;
45 
46  /*
47  * get information from the node
48  */
49  direction = node->ps.state->es_direction;
50  outerPlan = outerPlanState(node);
51 
52  /*
53  * The main logic is a simple state machine.
54  */
55  switch (node->lstate)
56  {
57  case LIMIT_INITIAL:
58 
59  /*
60  * First call for this node, so compute limit/offset. (We can't do
61  * this any earlier, because parameters from upper nodes will not
62  * be set during ExecInitLimit.) This also sets position = 0 and
63  * changes the state to LIMIT_RESCAN.
64  */
65  recompute_limits(node);
66 
67  /* FALL THRU */
68 
69  case LIMIT_RESCAN:
70 
71  /*
72  * If backwards scan, just return NULL without changing state.
73  */
74  if (!ScanDirectionIsForward(direction))
75  return NULL;
76 
77  /*
78  * Check for empty window; if so, treat like empty subplan.
79  */
80  if (node->count <= 0 && !node->noCount)
81  {
82  node->lstate = LIMIT_EMPTY;
83  return NULL;
84  }
85 
86  /*
87  * Fetch rows from subplan until we reach position > offset.
88  */
89  for (;;)
90  {
91  slot = ExecProcNode(outerPlan);
92  if (TupIsNull(slot))
93  {
94  /*
95  * The subplan returns too few tuples for us to produce
96  * any output at all.
97  */
98  node->lstate = LIMIT_EMPTY;
99  return NULL;
100  }
101  node->subSlot = slot;
102  if (++node->position > node->offset)
103  break;
104  }
105 
106  /*
107  * Okay, we have the first tuple of the window.
108  */
109  node->lstate = LIMIT_INWINDOW;
110  break;
111 
112  case LIMIT_EMPTY:
113 
114  /*
115  * The subplan is known to return no tuples (or not more than
116  * OFFSET tuples, in general). So we return no tuples.
117  */
118  return NULL;
119 
120  case LIMIT_INWINDOW:
121  if (ScanDirectionIsForward(direction))
122  {
123  /*
124  * Forwards scan, so check for stepping off end of window. If
125  * we are at the end of the window, return NULL without
126  * advancing the subplan or the position variable; but change
127  * the state machine state to record having done so.
128  */
129  if (!node->noCount &&
130  node->position - node->offset >= node->count)
131  {
132  node->lstate = LIMIT_WINDOWEND;
133  return NULL;
134  }
135 
136  /*
137  * Get next tuple from subplan, if any.
138  */
139  slot = ExecProcNode(outerPlan);
140  if (TupIsNull(slot))
141  {
142  node->lstate = LIMIT_SUBPLANEOF;
143  return NULL;
144  }
145  node->subSlot = slot;
146  node->position++;
147  }
148  else
149  {
150  /*
151  * Backwards scan, so check for stepping off start of window.
152  * As above, change only state-machine status if so.
153  */
154  if (node->position <= node->offset + 1)
155  {
156  node->lstate = LIMIT_WINDOWSTART;
157  return NULL;
158  }
159 
160  /*
161  * Get previous tuple from subplan; there should be one!
162  */
163  slot = ExecProcNode(outerPlan);
164  if (TupIsNull(slot))
165  elog(ERROR, "LIMIT subplan failed to run backwards");
166  node->subSlot = slot;
167  node->position--;
168  }
169  break;
170 
171  case LIMIT_SUBPLANEOF:
172  if (ScanDirectionIsForward(direction))
173  return NULL;
174 
175  /*
176  * Backing up from subplan EOF, so re-fetch previous tuple; there
177  * should be one! Note previous tuple must be in window.
178  */
179  slot = ExecProcNode(outerPlan);
180  if (TupIsNull(slot))
181  elog(ERROR, "LIMIT subplan failed to run backwards");
182  node->subSlot = slot;
183  node->lstate = LIMIT_INWINDOW;
184  /* position does not change 'cause we didn't advance it before */
185  break;
186 
187  case LIMIT_WINDOWEND:
188  if (ScanDirectionIsForward(direction))
189  return NULL;
190 
191  /*
192  * Backing up from window end: simply re-return the last tuple
193  * fetched from the subplan.
194  */
195  slot = node->subSlot;
196  node->lstate = LIMIT_INWINDOW;
197  /* position does not change 'cause we didn't advance it before */
198  break;
199 
200  case LIMIT_WINDOWSTART:
201  if (!ScanDirectionIsForward(direction))
202  return NULL;
203 
204  /*
205  * Advancing after having backed off window start: simply
206  * re-return the last tuple fetched from the subplan.
207  */
208  slot = node->subSlot;
209  node->lstate = LIMIT_INWINDOW;
210  /* position does not change 'cause we didn't change it before */
211  break;
212 
213  default:
214  elog(ERROR, "impossible LIMIT state: %d",
215  (int) node->lstate);
216  slot = NULL; /* keep compiler quiet */
217  break;
218  }
219 
220  /* Return the current tuple */
221  Assert(!TupIsNull(slot));
222 
223  return slot;
224 }
225 
226 /*
227  * Evaluate the limit/offset expressions --- done at startup or rescan.
228  *
229  * This is also a handy place to reset the current-position state info.
230  */
231 static void
233 {
234  ExprContext *econtext = node->ps.ps_ExprContext;
235  Datum val;
236  bool isNull;
237 
238  if (node->limitOffset)
239  {
241  econtext,
242  &isNull);
243  /* Interpret NULL offset as no offset */
244  if (isNull)
245  node->offset = 0;
246  else
247  {
248  node->offset = DatumGetInt64(val);
249  if (node->offset < 0)
250  ereport(ERROR,
251  (errcode(ERRCODE_INVALID_ROW_COUNT_IN_RESULT_OFFSET_CLAUSE),
252  errmsg("OFFSET must not be negative")));
253  }
254  }
255  else
256  {
257  /* No OFFSET supplied */
258  node->offset = 0;
259  }
260 
261  if (node->limitCount)
262  {
264  econtext,
265  &isNull);
266  /* Interpret NULL count as no count (LIMIT ALL) */
267  if (isNull)
268  {
269  node->count = 0;
270  node->noCount = true;
271  }
272  else
273  {
274  node->count = DatumGetInt64(val);
275  if (node->count < 0)
276  ereport(ERROR,
277  (errcode(ERRCODE_INVALID_ROW_COUNT_IN_LIMIT_CLAUSE),
278  errmsg("LIMIT must not be negative")));
279  node->noCount = false;
280  }
281  }
282  else
283  {
284  /* No COUNT supplied */
285  node->count = 0;
286  node->noCount = true;
287  }
288 
289  /* Reset position to start-of-scan */
290  node->position = 0;
291  node->subSlot = NULL;
292 
293  /* Set state-machine state */
294  node->lstate = LIMIT_RESCAN;
295 
296  /* Notify child node about limit, if useful */
297  pass_down_bound(node, outerPlanState(node));
298 }
299 
300 /*
301  * If we have a COUNT, and our input is a Sort node, notify it that it can
302  * use bounded sort. Also, if our input is a MergeAppend, we can apply the
303  * same bound to any Sorts that are direct children of the MergeAppend,
304  * since the MergeAppend surely need read no more than that many tuples from
305  * any one input. We also have to be prepared to look through a Result,
306  * since the planner might stick one atop MergeAppend for projection purposes.
307  *
308  * This is a bit of a kluge, but we don't have any more-abstract way of
309  * communicating between the two nodes; and it doesn't seem worth trying
310  * to invent one without some more examples of special communication needs.
311  *
312  * Note: it is the responsibility of nodeSort.c to react properly to
313  * changes of these parameters. If we ever do redesign this, it'd be a
314  * good idea to integrate this signaling with the parameter-change mechanism.
315  */
316 static void
318 {
319  if (IsA(child_node, SortState))
320  {
321  SortState *sortState = (SortState *) child_node;
322  int64 tuples_needed = node->count + node->offset;
323 
324  /* negative test checks for overflow in sum */
325  if (node->noCount || tuples_needed < 0)
326  {
327  /* make sure flag gets reset if needed upon rescan */
328  sortState->bounded = false;
329  }
330  else
331  {
332  sortState->bounded = true;
333  sortState->bound = tuples_needed;
334  }
335  }
336  else if (IsA(child_node, MergeAppendState))
337  {
338  MergeAppendState *maState = (MergeAppendState *) child_node;
339  int i;
340 
341  for (i = 0; i < maState->ms_nplans; i++)
342  pass_down_bound(node, maState->mergeplans[i]);
343  }
344  else if (IsA(child_node, ResultState))
345  {
346  /*
347  * If Result supported qual checking, we'd have to punt on seeing a
348  * qual. Note that having a resconstantqual is not a showstopper: if
349  * that fails we're not getting any rows at all.
350  */
351  if (outerPlanState(child_node))
352  pass_down_bound(node, outerPlanState(child_node));
353  }
354 }
355 
356 /* ----------------------------------------------------------------
357  * ExecInitLimit
358  *
359  * This initializes the limit node state structures and
360  * the node's subplan.
361  * ----------------------------------------------------------------
362  */
363 LimitState *
364 ExecInitLimit(Limit *node, EState *estate, int eflags)
365 {
366  LimitState *limitstate;
367  Plan *outerPlan;
368 
369  /* check for unsupported flags */
370  Assert(!(eflags & EXEC_FLAG_MARK));
371 
372  /*
373  * create state structure
374  */
375  limitstate = makeNode(LimitState);
376  limitstate->ps.plan = (Plan *) node;
377  limitstate->ps.state = estate;
378 
379  limitstate->lstate = LIMIT_INITIAL;
380 
381  /*
382  * Miscellaneous initialization
383  *
384  * Limit nodes never call ExecQual or ExecProject, but they need an
385  * exprcontext anyway to evaluate the limit/offset parameters in.
386  */
387  ExecAssignExprContext(estate, &limitstate->ps);
388 
389  /*
390  * initialize child expressions
391  */
392  limitstate->limitOffset = ExecInitExpr((Expr *) node->limitOffset,
393  (PlanState *) limitstate);
394  limitstate->limitCount = ExecInitExpr((Expr *) node->limitCount,
395  (PlanState *) limitstate);
396 
397  /*
398  * Tuple table initialization (XXX not actually used...)
399  */
400  ExecInitResultTupleSlot(estate, &limitstate->ps);
401 
402  /*
403  * then initialize outer plan
404  */
405  outerPlan = outerPlan(node);
406  outerPlanState(limitstate) = ExecInitNode(outerPlan, estate, eflags);
407 
408  /*
409  * limit nodes do no projections, so initialize projection info for this
410  * node appropriately
411  */
412  ExecAssignResultTypeFromTL(&limitstate->ps);
413  limitstate->ps.ps_ProjInfo = NULL;
414 
415  return limitstate;
416 }
417 
418 /* ----------------------------------------------------------------
419  * ExecEndLimit
420  *
421  * This shuts down the subplan and frees resources allocated
422  * to this node.
423  * ----------------------------------------------------------------
424  */
425 void
427 {
428  ExecFreeExprContext(&node->ps);
430 }
431 
432 
433 void
435 {
436  /*
437  * Recompute limit/offset in case parameters changed, and reset the state
438  * machine. We must do this before rescanning our child node, in case
439  * it's a Sort that we are passing the parameters down to.
440  */
441  recompute_limits(node);
442 
443  /*
444  * if chgParam of subnode is not null then plan will be re-scanned by
445  * first ExecProcNode.
446  */
447  if (node->ps.lefttree->chgParam == NULL)
448  ExecReScan(node->ps.lefttree);
449 }
TupleTableSlot * ExecProcNode(PlanState *node)
Definition: execProcnode.c:392
#define IsA(nodeptr, _type_)
Definition: nodes.h:569
ProjectionInfo * ps_ProjInfo
Definition: execnodes.h:1081
void ExecEndLimit(LimitState *node)
Definition: nodeLimit.c:426
#define ScanDirectionIsForward(direction)
Definition: sdir.h:55
bool noCount
Definition: execnodes.h:2213
void ExecEndNode(PlanState *node)
Definition: execProcnode.c:644
bool bounded
Definition: execnodes.h:1910
ExprContext * ps_ExprContext
Definition: execnodes.h:1080
int64 bound
Definition: execnodes.h:1911
void ExecReScan(PlanState *node)
Definition: execAmi.c:74
int errcode(int sqlerrcode)
Definition: elog.c:575
void ExecReScanLimit(LimitState *node)
Definition: nodeLimit.c:434
EState * state
Definition: execnodes.h:1051
LimitStateCond lstate
Definition: execnodes.h:2214
ExprState * limitCount
Definition: execnodes.h:2210
Node * limitOffset
Definition: plannodes.h:889
int64 position
Definition: execnodes.h:2215
void ExecFreeExprContext(PlanState *planstate)
Definition: execUtils.c:686
Datum ExecEvalExprSwitchContext(ExprState *expression, ExprContext *econtext, bool *isNull)
Definition: execQual.c:4220
ScanDirection es_direction
Definition: execnodes.h:371
void ExecAssignResultTypeFromTL(PlanState *planstate)
Definition: execUtils.c:431
int64 count
Definition: execnodes.h:2212
struct PlanState * lefttree
Definition: execnodes.h:1065
ExprState * ExecInitExpr(Expr *node, PlanState *parent)
Definition: execQual.c:4267
#define ERROR
Definition: elog.h:43
int64 offset
Definition: execnodes.h:2211
void ExecInitResultTupleSlot(EState *estate, PlanState *planstate)
Definition: execTuples.c:832
Node * limitCount
Definition: plannodes.h:890
#define DatumGetInt64(X)
Definition: postgres.h:613
#define outerPlanState(node)
Definition: execnodes.h:1092
ScanDirection
Definition: sdir.h:22
PlanState ** mergeplans
Definition: execnodes.h:1212
static void pass_down_bound(LimitState *node, PlanState *child_node)
Definition: nodeLimit.c:317
ExprState * limitOffset
Definition: execnodes.h:2209
#define TupIsNull(slot)
Definition: tuptable.h:138
#define ereport(elevel, rest)
Definition: elog.h:122
Bitmapset * chgParam
Definition: execnodes.h:1074
#define outerPlan(node)
Definition: plannodes.h:162
uintptr_t Datum
Definition: postgres.h:372
Plan * plan
Definition: execnodes.h:1049
TupleTableSlot * ExecLimit(LimitState *node)
Definition: nodeLimit.c:40
#define makeNode(_type_)
Definition: nodes.h:566
#define NULL
Definition: c.h:229
#define Assert(condition)
Definition: c.h:675
#define EXEC_FLAG_MARK
Definition: executor.h:61
TupleTableSlot * subSlot
Definition: execnodes.h:2216
void ExecAssignExprContext(EState *estate, PlanState *planstate)
Definition: execUtils.c:409
int errmsg(const char *fmt,...)
Definition: elog.c:797
LimitState * ExecInitLimit(Limit *node, EState *estate, int eflags)
Definition: nodeLimit.c:364
int i
static void recompute_limits(LimitState *node)
Definition: nodeLimit.c:232
#define elog
Definition: elog.h:219
PlanState * ExecInitNode(Plan *node, EState *estate, int eflags)
Definition: execProcnode.c:139
long val
Definition: informix.c:689
PlanState ps
Definition: execnodes.h:2208