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
29static void recompute_limits(LimitState *node);
30static 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 */
40static TupleTableSlot * /* return: a tuple or NULL */
41ExecLimit(PlanState *pstate)
42{
43 LimitState *node = castNode(LimitState, pstate);
44 ScanDirection direction;
45 TupleTableSlot *slot;
46 PlanState *outerPlan;
47
48 CHECK_FOR_INTERRUPTS();
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 */
243static void
244recompute_limits(LimitState *node)
245{
246 ExprContext *econtext = node->ps.ps_ExprContext;
247 Datum val;
248 bool isNull;
249
250 if (node->limitOffset)
251 {
252 val = ExecEvalExprSwitchContext(node->limitOffset,
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 {
275 val = ExecEvalExprSwitchContext(node->limitCount,
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 */
314 ExecSetTupleBound(compute_tuples_needed(node), outerPlanState(node));
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 */
321static int64
322compute_tuples_needed(LimitState *node)
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 */
337LimitState *
338ExecInitLimit(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 */
403void
404ExecEndLimit(LimitState *node)
405{
406 ExecFreeExprContext(&node->ps);
407 ExecEndNode(outerPlanState(node));
408}
409
410
411void
412ExecReScanLimit(LimitState *node)
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}
428