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 */
ExecLimit(PlanState * pstate)41 ExecLimit(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 * 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
recompute_limits(LimitState * node)242 recompute_limits(LimitState *node)
243 {
244 ExprContext *econtext = node->ps.ps_ExprContext;
245 Datum val;
246 bool isNull;
247
248 if (node->limitOffset)
249 {
250 val = ExecEvalExprSwitchContext(node->limitOffset,
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 {
273 val = ExecEvalExprSwitchContext(node->limitCount,
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 */
312 ExecSetTupleBound(compute_tuples_needed(node), outerPlanState(node));
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
compute_tuples_needed(LimitState * node)320 compute_tuples_needed(LimitState *node)
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 *
ExecInitLimit(Limit * node,EState * estate,int eflags)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
ExecEndLimit(LimitState * node)402 ExecEndLimit(LimitState *node)
403 {
404 ExecFreeExprContext(&node->ps);
405 ExecEndNode(outerPlanState(node));
406 }
407
408
409 void
ExecReScanLimit(LimitState * node)410 ExecReScanLimit(LimitState *node)
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 }
426