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