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 void pass_down_bound(LimitState *node, PlanState *child_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 /* Notify child node about limit, if useful */
307 pass_down_bound(node, outerPlanState(node));
308 }
309
310 /*
311 * If we have a COUNT, and our input is a Sort node, notify it that it can
312 * use bounded sort. Also, if our input is a MergeAppend, we can apply the
313 * same bound to any Sorts that are direct children of the MergeAppend,
314 * since the MergeAppend surely need read no more than that many tuples from
315 * any one input. We also have to be prepared to look through a Result,
316 * since the planner might stick one atop MergeAppend for projection purposes.
317 *
318 * This is a bit of a kluge, but we don't have any more-abstract way of
319 * communicating between the two nodes; and it doesn't seem worth trying
320 * to invent one without some more examples of special communication needs.
321 *
322 * Note: it is the responsibility of nodeSort.c to react properly to
323 * changes of these parameters. If we ever do redesign this, it'd be a
324 * good idea to integrate this signaling with the parameter-change mechanism.
325 */
326 static void
pass_down_bound(LimitState * node,PlanState * child_node)327 pass_down_bound(LimitState *node, PlanState *child_node)
328 {
329 if (IsA(child_node, SortState))
330 {
331 SortState *sortState = (SortState *) child_node;
332 int64 tuples_needed = node->count + node->offset;
333
334 /* negative test checks for overflow in sum */
335 if (node->noCount || tuples_needed < 0)
336 {
337 /* make sure flag gets reset if needed upon rescan */
338 sortState->bounded = false;
339 }
340 else
341 {
342 sortState->bounded = true;
343 sortState->bound = tuples_needed;
344 }
345 }
346 else if (IsA(child_node, MergeAppendState))
347 {
348 MergeAppendState *maState = (MergeAppendState *) child_node;
349 int i;
350
351 for (i = 0; i < maState->ms_nplans; i++)
352 pass_down_bound(node, maState->mergeplans[i]);
353 }
354 else if (IsA(child_node, ResultState))
355 {
356 /*
357 * If Result supported qual checking, we'd have to punt on seeing a
358 * qual. Note that having a resconstantqual is not a showstopper: if
359 * that fails we're not getting any rows at all.
360 */
361 if (outerPlanState(child_node))
362 pass_down_bound(node, outerPlanState(child_node));
363 }
364 }
365
366 /* ----------------------------------------------------------------
367 * ExecInitLimit
368 *
369 * This initializes the limit node state structures and
370 * the node's subplan.
371 * ----------------------------------------------------------------
372 */
373 LimitState *
ExecInitLimit(Limit * node,EState * estate,int eflags)374 ExecInitLimit(Limit *node, EState *estate, int eflags)
375 {
376 LimitState *limitstate;
377 Plan *outerPlan;
378
379 /* check for unsupported flags */
380 Assert(!(eflags & EXEC_FLAG_MARK));
381
382 /*
383 * create state structure
384 */
385 limitstate = makeNode(LimitState);
386 limitstate->ps.plan = (Plan *) node;
387 limitstate->ps.state = estate;
388 limitstate->ps.ExecProcNode = ExecLimit;
389
390 limitstate->lstate = LIMIT_INITIAL;
391
392 /*
393 * Miscellaneous initialization
394 *
395 * Limit nodes never call ExecQual or ExecProject, but they need an
396 * exprcontext anyway to evaluate the limit/offset parameters in.
397 */
398 ExecAssignExprContext(estate, &limitstate->ps);
399
400 /*
401 * initialize child expressions
402 */
403 limitstate->limitOffset = ExecInitExpr((Expr *) node->limitOffset,
404 (PlanState *) limitstate);
405 limitstate->limitCount = ExecInitExpr((Expr *) node->limitCount,
406 (PlanState *) limitstate);
407
408 /*
409 * Tuple table initialization (XXX not actually used...)
410 */
411 ExecInitResultTupleSlot(estate, &limitstate->ps);
412
413 /*
414 * then initialize outer plan
415 */
416 outerPlan = outerPlan(node);
417 outerPlanState(limitstate) = ExecInitNode(outerPlan, estate, eflags);
418
419 /*
420 * limit nodes do no projections, so initialize projection info for this
421 * node appropriately
422 */
423 ExecAssignResultTypeFromTL(&limitstate->ps);
424 limitstate->ps.ps_ProjInfo = NULL;
425
426 return limitstate;
427 }
428
429 /* ----------------------------------------------------------------
430 * ExecEndLimit
431 *
432 * This shuts down the subplan and frees resources allocated
433 * to this node.
434 * ----------------------------------------------------------------
435 */
436 void
ExecEndLimit(LimitState * node)437 ExecEndLimit(LimitState *node)
438 {
439 ExecFreeExprContext(&node->ps);
440 ExecEndNode(outerPlanState(node));
441 }
442
443
444 void
ExecReScanLimit(LimitState * node)445 ExecReScanLimit(LimitState *node)
446 {
447 /*
448 * Recompute limit/offset in case parameters changed, and reset the state
449 * machine. We must do this before rescanning our child node, in case
450 * it's a Sort that we are passing the parameters down to.
451 */
452 recompute_limits(node);
453
454 /*
455 * if chgParam of subnode is not null then plan will be re-scanned by
456 * first ExecProcNode.
457 */
458 if (node->ps.lefttree->chgParam == NULL)
459 ExecReScan(node->ps.lefttree);
460 }
461