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