1 /*-------------------------------------------------------------------------
2 *
3 * nodeLimit.c
4 * Routines to handle limiting of query results where appropriate
5 *
6 * Portions Copyright (c) 1996-2021, 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 ExprContext *econtext = node->ps.ps_ExprContext;
45 ScanDirection direction;
46 TupleTableSlot *slot;
47 PlanState *outerPlan;
48
49 CHECK_FOR_INTERRUPTS();
50
51 /*
52 * get information from the node
53 */
54 direction = node->ps.state->es_direction;
55 outerPlan = outerPlanState(node);
56
57 /*
58 * The main logic is a simple state machine.
59 */
60 switch (node->lstate)
61 {
62 case LIMIT_INITIAL:
63
64 /*
65 * First call for this node, so compute limit/offset. (We can't do
66 * this any earlier, because parameters from upper nodes will not
67 * be set during ExecInitLimit.) This also sets position = 0 and
68 * changes the state to LIMIT_RESCAN.
69 */
70 recompute_limits(node);
71
72 /* FALL THRU */
73
74 case LIMIT_RESCAN:
75
76 /*
77 * If backwards scan, just return NULL without changing state.
78 */
79 if (!ScanDirectionIsForward(direction))
80 return NULL;
81
82 /*
83 * Check for empty window; if so, treat like empty subplan.
84 */
85 if (node->count <= 0 && !node->noCount)
86 {
87 node->lstate = LIMIT_EMPTY;
88 return NULL;
89 }
90
91 /*
92 * Fetch rows from subplan until we reach position > offset.
93 */
94 for (;;)
95 {
96 slot = ExecProcNode(outerPlan);
97 if (TupIsNull(slot))
98 {
99 /*
100 * The subplan returns too few tuples for us to produce
101 * any output at all.
102 */
103 node->lstate = LIMIT_EMPTY;
104 return NULL;
105 }
106
107 /*
108 * Tuple at limit is needed for comparison in subsequent
109 * execution to detect ties.
110 */
111 if (node->limitOption == LIMIT_OPTION_WITH_TIES &&
112 node->position - node->offset == node->count - 1)
113 {
114 ExecCopySlot(node->last_slot, slot);
115 }
116 node->subSlot = slot;
117 if (++node->position > node->offset)
118 break;
119 }
120
121 /*
122 * Okay, we have the first tuple of the window.
123 */
124 node->lstate = LIMIT_INWINDOW;
125 break;
126
127 case LIMIT_EMPTY:
128
129 /*
130 * The subplan is known to return no tuples (or not more than
131 * OFFSET tuples, in general). So we return no tuples.
132 */
133 return NULL;
134
135 case LIMIT_INWINDOW:
136 if (ScanDirectionIsForward(direction))
137 {
138 /*
139 * Forwards scan, so check for stepping off end of window. At
140 * the end of the window, the behavior depends on whether WITH
141 * TIES was specified: if so, we need to change the state
142 * machine to WINDOWEND_TIES, and fall through to the code for
143 * that case. If not (nothing was specified, or ONLY was)
144 * return NULL without advancing the subplan or the position
145 * variable, but change the state machine to record having
146 * done so.
147 *
148 * Once at the end, ideally, we would shut down parallel
149 * resources; but that would destroy the parallel context
150 * which might be required for rescans. To do that, we'll
151 * need to find a way to pass down more information about
152 * whether rescans are possible.
153 */
154 if (!node->noCount &&
155 node->position - node->offset >= node->count)
156 {
157 if (node->limitOption == LIMIT_OPTION_COUNT)
158 {
159 node->lstate = LIMIT_WINDOWEND;
160 return NULL;
161 }
162 else
163 {
164 node->lstate = LIMIT_WINDOWEND_TIES;
165 /* we'll fall through to the next case */
166 }
167 }
168 else
169 {
170 /*
171 * Get next tuple from subplan, if any.
172 */
173 slot = ExecProcNode(outerPlan);
174 if (TupIsNull(slot))
175 {
176 node->lstate = LIMIT_SUBPLANEOF;
177 return NULL;
178 }
179
180 /*
181 * If WITH TIES is active, and this is the last in-window
182 * tuple, save it to be used in subsequent WINDOWEND_TIES
183 * processing.
184 */
185 if (node->limitOption == LIMIT_OPTION_WITH_TIES &&
186 node->position - node->offset == node->count - 1)
187 {
188 ExecCopySlot(node->last_slot, slot);
189 }
190 node->subSlot = slot;
191 node->position++;
192 break;
193 }
194 }
195 else
196 {
197 /*
198 * Backwards scan, so check for stepping off start of window.
199 * As above, only change state-machine status if so.
200 */
201 if (node->position <= node->offset + 1)
202 {
203 node->lstate = LIMIT_WINDOWSTART;
204 return NULL;
205 }
206
207 /*
208 * Get previous tuple from subplan; there should be one!
209 */
210 slot = ExecProcNode(outerPlan);
211 if (TupIsNull(slot))
212 elog(ERROR, "LIMIT subplan failed to run backwards");
213 node->subSlot = slot;
214 node->position--;
215 break;
216 }
217
218 Assert(node->lstate == LIMIT_WINDOWEND_TIES);
219 /* FALL THRU */
220
221 case LIMIT_WINDOWEND_TIES:
222 if (ScanDirectionIsForward(direction))
223 {
224 /*
225 * Advance the subplan until we find the first row with
226 * different ORDER BY pathkeys.
227 */
228 slot = ExecProcNode(outerPlan);
229 if (TupIsNull(slot))
230 {
231 node->lstate = LIMIT_SUBPLANEOF;
232 return NULL;
233 }
234
235 /*
236 * Test if the new tuple and the last tuple match. If so we
237 * return the tuple.
238 */
239 econtext->ecxt_innertuple = slot;
240 econtext->ecxt_outertuple = node->last_slot;
241 if (ExecQualAndReset(node->eqfunction, econtext))
242 {
243 node->subSlot = slot;
244 node->position++;
245 }
246 else
247 {
248 node->lstate = LIMIT_WINDOWEND;
249 return NULL;
250 }
251 }
252 else
253 {
254 /*
255 * Backwards scan, so check for stepping off start of window.
256 * Change only state-machine status if so.
257 */
258 if (node->position <= node->offset + 1)
259 {
260 node->lstate = LIMIT_WINDOWSTART;
261 return NULL;
262 }
263
264 /*
265 * Get previous tuple from subplan; there should be one! And
266 * change state-machine status.
267 */
268 slot = ExecProcNode(outerPlan);
269 if (TupIsNull(slot))
270 elog(ERROR, "LIMIT subplan failed to run backwards");
271 node->subSlot = slot;
272 node->position--;
273 node->lstate = LIMIT_INWINDOW;
274 }
275 break;
276
277 case LIMIT_SUBPLANEOF:
278 if (ScanDirectionIsForward(direction))
279 return NULL;
280
281 /*
282 * Backing up from subplan EOF, so re-fetch previous tuple; there
283 * should be one! Note previous tuple must be in window.
284 */
285 slot = ExecProcNode(outerPlan);
286 if (TupIsNull(slot))
287 elog(ERROR, "LIMIT subplan failed to run backwards");
288 node->subSlot = slot;
289 node->lstate = LIMIT_INWINDOW;
290 /* position does not change 'cause we didn't advance it before */
291 break;
292
293 case LIMIT_WINDOWEND:
294 if (ScanDirectionIsForward(direction))
295 return NULL;
296
297 /*
298 * We already past one position to detect ties so re-fetch
299 * previous tuple; there should be one! Note previous tuple must
300 * be in window.
301 */
302 if (node->limitOption == LIMIT_OPTION_WITH_TIES)
303 {
304 slot = ExecProcNode(outerPlan);
305 if (TupIsNull(slot))
306 elog(ERROR, "LIMIT subplan failed to run backwards");
307 node->subSlot = slot;
308 node->lstate = LIMIT_INWINDOW;
309 }
310 else
311 {
312 /*
313 * Backing up from window end: simply re-return the last tuple
314 * fetched from the subplan.
315 */
316 slot = node->subSlot;
317 node->lstate = LIMIT_INWINDOW;
318 /* position does not change 'cause we didn't advance it before */
319 }
320 break;
321
322 case LIMIT_WINDOWSTART:
323 if (!ScanDirectionIsForward(direction))
324 return NULL;
325
326 /*
327 * Advancing after having backed off window start: simply
328 * re-return the last tuple fetched from the subplan.
329 */
330 slot = node->subSlot;
331 node->lstate = LIMIT_INWINDOW;
332 /* position does not change 'cause we didn't change it before */
333 break;
334
335 default:
336 elog(ERROR, "impossible LIMIT state: %d",
337 (int) node->lstate);
338 slot = NULL; /* keep compiler quiet */
339 break;
340 }
341
342 /* Return the current tuple */
343 Assert(!TupIsNull(slot));
344
345 return slot;
346 }
347
348 /*
349 * Evaluate the limit/offset expressions --- done at startup or rescan.
350 *
351 * This is also a handy place to reset the current-position state info.
352 */
353 static void
recompute_limits(LimitState * node)354 recompute_limits(LimitState *node)
355 {
356 ExprContext *econtext = node->ps.ps_ExprContext;
357 Datum val;
358 bool isNull;
359
360 if (node->limitOffset)
361 {
362 val = ExecEvalExprSwitchContext(node->limitOffset,
363 econtext,
364 &isNull);
365 /* Interpret NULL offset as no offset */
366 if (isNull)
367 node->offset = 0;
368 else
369 {
370 node->offset = DatumGetInt64(val);
371 if (node->offset < 0)
372 ereport(ERROR,
373 (errcode(ERRCODE_INVALID_ROW_COUNT_IN_RESULT_OFFSET_CLAUSE),
374 errmsg("OFFSET must not be negative")));
375 }
376 }
377 else
378 {
379 /* No OFFSET supplied */
380 node->offset = 0;
381 }
382
383 if (node->limitCount)
384 {
385 val = ExecEvalExprSwitchContext(node->limitCount,
386 econtext,
387 &isNull);
388 /* Interpret NULL count as no count (LIMIT ALL) */
389 if (isNull)
390 {
391 node->count = 0;
392 node->noCount = true;
393 }
394 else
395 {
396 node->count = DatumGetInt64(val);
397 if (node->count < 0)
398 ereport(ERROR,
399 (errcode(ERRCODE_INVALID_ROW_COUNT_IN_LIMIT_CLAUSE),
400 errmsg("LIMIT must not be negative")));
401 node->noCount = false;
402 }
403 }
404 else
405 {
406 /* No COUNT supplied */
407 node->count = 0;
408 node->noCount = true;
409 }
410
411 /* Reset position to start-of-scan */
412 node->position = 0;
413 node->subSlot = NULL;
414
415 /* Set state-machine state */
416 node->lstate = LIMIT_RESCAN;
417
418 /*
419 * Notify child node about limit. Note: think not to "optimize" by
420 * skipping ExecSetTupleBound if compute_tuples_needed returns < 0. We
421 * must update the child node anyway, in case this is a rescan and the
422 * previous time we got a different result.
423 */
424 ExecSetTupleBound(compute_tuples_needed(node), outerPlanState(node));
425 }
426
427 /*
428 * Compute the maximum number of tuples needed to satisfy this Limit node.
429 * Return a negative value if there is not a determinable limit.
430 */
431 static int64
compute_tuples_needed(LimitState * node)432 compute_tuples_needed(LimitState *node)
433 {
434 if ((node->noCount) || (node->limitOption == LIMIT_OPTION_WITH_TIES))
435 return -1;
436 /* Note: if this overflows, we'll return a negative value, which is OK */
437 return node->count + node->offset;
438 }
439
440 /* ----------------------------------------------------------------
441 * ExecInitLimit
442 *
443 * This initializes the limit node state structures and
444 * the node's subplan.
445 * ----------------------------------------------------------------
446 */
447 LimitState *
ExecInitLimit(Limit * node,EState * estate,int eflags)448 ExecInitLimit(Limit *node, EState *estate, int eflags)
449 {
450 LimitState *limitstate;
451 Plan *outerPlan;
452
453 /* check for unsupported flags */
454 Assert(!(eflags & EXEC_FLAG_MARK));
455
456 /*
457 * create state structure
458 */
459 limitstate = makeNode(LimitState);
460 limitstate->ps.plan = (Plan *) node;
461 limitstate->ps.state = estate;
462 limitstate->ps.ExecProcNode = ExecLimit;
463
464 limitstate->lstate = LIMIT_INITIAL;
465
466 /*
467 * Miscellaneous initialization
468 *
469 * Limit nodes never call ExecQual or ExecProject, but they need an
470 * exprcontext anyway to evaluate the limit/offset parameters in.
471 */
472 ExecAssignExprContext(estate, &limitstate->ps);
473
474 /*
475 * initialize outer plan
476 */
477 outerPlan = outerPlan(node);
478 outerPlanState(limitstate) = ExecInitNode(outerPlan, estate, eflags);
479
480 /*
481 * initialize child expressions
482 */
483 limitstate->limitOffset = ExecInitExpr((Expr *) node->limitOffset,
484 (PlanState *) limitstate);
485 limitstate->limitCount = ExecInitExpr((Expr *) node->limitCount,
486 (PlanState *) limitstate);
487 limitstate->limitOption = node->limitOption;
488
489 /*
490 * Initialize result type.
491 */
492 ExecInitResultTypeTL(&limitstate->ps);
493
494 limitstate->ps.resultopsset = true;
495 limitstate->ps.resultops = ExecGetResultSlotOps(outerPlanState(limitstate),
496 &limitstate->ps.resultopsfixed);
497
498 /*
499 * limit nodes do no projections, so initialize projection info for this
500 * node appropriately
501 */
502 limitstate->ps.ps_ProjInfo = NULL;
503
504 /*
505 * Initialize the equality evaluation, to detect ties.
506 */
507 if (node->limitOption == LIMIT_OPTION_WITH_TIES)
508 {
509 TupleDesc desc;
510 const TupleTableSlotOps *ops;
511
512 desc = ExecGetResultType(outerPlanState(limitstate));
513 ops = ExecGetResultSlotOps(outerPlanState(limitstate), NULL);
514
515 limitstate->last_slot = ExecInitExtraTupleSlot(estate, desc, ops);
516 limitstate->eqfunction = execTuplesMatchPrepare(desc,
517 node->uniqNumCols,
518 node->uniqColIdx,
519 node->uniqOperators,
520 node->uniqCollations,
521 &limitstate->ps);
522 }
523
524 return limitstate;
525 }
526
527 /* ----------------------------------------------------------------
528 * ExecEndLimit
529 *
530 * This shuts down the subplan and frees resources allocated
531 * to this node.
532 * ----------------------------------------------------------------
533 */
534 void
ExecEndLimit(LimitState * node)535 ExecEndLimit(LimitState *node)
536 {
537 ExecFreeExprContext(&node->ps);
538 ExecEndNode(outerPlanState(node));
539 }
540
541
542 void
ExecReScanLimit(LimitState * node)543 ExecReScanLimit(LimitState *node)
544 {
545 /*
546 * Recompute limit/offset in case parameters changed, and reset the state
547 * machine. We must do this before rescanning our child node, in case
548 * it's a Sort that we are passing the parameters down to.
549 */
550 recompute_limits(node);
551
552 /*
553 * if chgParam of subnode is not null then plan will be re-scanned by
554 * first ExecProcNode.
555 */
556 if (node->ps.lefttree->chgParam == NULL)
557 ExecReScan(node->ps.lefttree);
558 }
559