Age Owner Branch data TLA 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-2025, 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 */
2973 andres@anarazel.de 40 :CBC 50729 : ExecLimit(PlanState *pstate)
41 : : {
42 : 50729 : LimitState *node = castNode(LimitState, pstate);
1978 alvherre@alvh.no-ip. 43 : 50729 : ExprContext *econtext = node->ps.ps_ExprContext;
44 : : ScanDirection direction;
45 : : TupleTableSlot *slot;
46 : : PlanState *outerPlan;
47 : :
2965 andres@anarazel.de 48 [ - + ]: 50729 : CHECK_FOR_INTERRUPTS();
49 : :
50 : : /*
51 : : * get information from the node
52 : : */
8311 tgl@sss.pgh.pa.us 53 : 50729 : direction = node->ps.state->es_direction;
54 : 50729 : outerPlan = outerPlanState(node);
55 : :
56 : : /*
57 : : * The main logic is a simple state machine.
58 : : */
59 [ + + - + : 50729 : switch (node->lstate)
+ + + +
- ]
60 : : {
8324 61 : 1689 : 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 : : */
6687 69 : 1689 : recompute_limits(node);
70 : :
71 : : /* FALL THRU */
72 : :
73 : 32184 : case LIMIT_RESCAN:
74 : :
75 : : /*
76 : : * If backwards scan, just return NULL without changing state.
77 : : */
78 [ - + ]: 32184 : if (!ScanDirectionIsForward(direction))
6687 tgl@sss.pgh.pa.us 79 :UBC 0 : return NULL;
80 : :
81 : : /*
82 : : * Check for empty window; if so, treat like empty subplan.
83 : : */
8311 tgl@sss.pgh.pa.us 84 [ + + + + ]:CBC 32184 : if (node->count <= 0 && !node->noCount)
85 : : {
86 : 69 : node->lstate = LIMIT_EMPTY;
9081 87 : 69 : return NULL;
88 : : }
89 : :
90 : : /*
91 : : * Fetch rows from subplan until we reach position > offset.
92 : : */
93 : : for (;;)
94 : : {
8311 95 : 284502 : slot = ExecProcNode(outerPlan);
8324 96 [ + + + + ]: 284494 : if (TupIsNull(slot))
97 : : {
98 : : /*
99 : : * The subplan returns too few tuples for us to produce
100 : : * any output at all.
101 : : */
8311 102 : 27114 : node->lstate = LIMIT_EMPTY;
8324 103 : 27114 : return NULL;
104 : : }
105 : :
106 : : /*
107 : : * Tuple at limit is needed for comparison in subsequent
108 : : * execution to detect ties.
109 : : */
1978 alvherre@alvh.no-ip. 110 [ + + ]: 257380 : if (node->limitOption == LIMIT_OPTION_WITH_TIES &&
111 [ + + ]: 14 : node->position - node->offset == node->count - 1)
112 : : {
113 : 6 : ExecCopySlot(node->last_slot, slot);
114 : : }
8311 tgl@sss.pgh.pa.us 115 : 257380 : node->subSlot = slot;
116 [ + + ]: 257380 : if (++node->position > node->offset)
8324 117 : 4993 : break;
118 : : }
119 : :
120 : : /*
121 : : * Okay, we have the first tuple of the window.
122 : : */
8311 123 : 4993 : node->lstate = LIMIT_INWINDOW;
8324 124 : 4993 : break;
125 : :
8324 tgl@sss.pgh.pa.us 126 :UBC 0 : 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 : :
8324 tgl@sss.pgh.pa.us 134 :CBC 18427 : case LIMIT_INWINDOW:
9081 135 [ + + ]: 18427 : 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 : : */
8311 153 [ + + ]: 18382 : if (!node->noCount &&
5149 heikki.linnakangas@i 154 [ + + ]: 18130 : node->position - node->offset >= node->count)
155 : : {
1978 alvherre@alvh.no-ip. 156 [ + + ]: 4755 : if (node->limitOption == LIMIT_OPTION_COUNT)
157 : : {
158 : 4735 : node->lstate = LIMIT_WINDOWEND;
159 : 4735 : return NULL;
160 : : }
161 : : else
162 : : {
163 : 20 : node->lstate = LIMIT_WINDOWEND_TIES;
164 : : /* we'll fall through to the next case */
165 : : }
166 : : }
167 : : else
168 : : {
169 : : /*
170 : : * Get next tuple from subplan, if any.
171 : : */
172 : 13627 : slot = ExecProcNode(outerPlan);
173 [ + + + + ]: 13624 : if (TupIsNull(slot))
174 : : {
175 : 85 : node->lstate = LIMIT_SUBPLANEOF;
176 : 85 : 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 [ + + ]: 13539 : if (node->limitOption == LIMIT_OPTION_WITH_TIES &&
185 [ + - ]: 14 : node->position - node->offset == node->count - 1)
186 : : {
187 : 14 : ExecCopySlot(node->last_slot, slot);
188 : : }
189 : 13539 : node->subSlot = slot;
190 : 13539 : node->position++;
191 : 13539 : break;
192 : : }
193 : : }
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 [ + + ]: 45 : if (node->position <= node->offset + 1)
201 : : {
202 : 15 : node->lstate = LIMIT_WINDOWSTART;
8324 tgl@sss.pgh.pa.us 203 : 15 : return NULL;
204 : : }
205 : :
206 : : /*
207 : : * Get previous tuple from subplan; there should be one!
208 : : */
1978 alvherre@alvh.no-ip. 209 : 30 : slot = ExecProcNode(outerPlan);
210 [ + - - + ]: 30 : if (TupIsNull(slot))
1978 alvherre@alvh.no-ip. 211 [ # # ]:UBC 0 : elog(ERROR, "LIMIT subplan failed to run backwards");
1978 alvherre@alvh.no-ip. 212 :CBC 30 : node->subSlot = slot;
213 : 30 : node->position--;
214 : 30 : break;
215 : : }
216 : :
1974 tgl@sss.pgh.pa.us 217 [ - + ]: 20 : Assert(node->lstate == LIMIT_WINDOWEND_TIES);
218 : : /* FALL THRU */
219 : :
220 : : case LIMIT_WINDOWEND_TIES:
1978 alvherre@alvh.no-ip. 221 [ + - ]: 108 : if (ScanDirectionIsForward(direction))
222 : : {
223 : : /*
224 : : * Advance the subplan until we find the first row with
225 : : * different ORDER BY pathkeys.
226 : : */
8311 tgl@sss.pgh.pa.us 227 : 108 : slot = ExecProcNode(outerPlan);
8324 228 [ + - + + ]: 108 : if (TupIsNull(slot))
229 : : {
8311 230 : 1 : node->lstate = LIMIT_SUBPLANEOF;
8324 231 : 1 : return NULL;
232 : : }
233 : :
234 : : /*
235 : : * Test if the new tuple and the last tuple match. If so we
236 : : * return the tuple.
237 : : */
1978 alvherre@alvh.no-ip. 238 : 107 : econtext->ecxt_innertuple = slot;
239 : 107 : econtext->ecxt_outertuple = node->last_slot;
240 [ + + ]: 107 : if (ExecQualAndReset(node->eqfunction, econtext))
241 : : {
242 : 88 : node->subSlot = slot;
243 : 88 : node->position++;
244 : : }
245 : : else
246 : : {
247 : 19 : node->lstate = LIMIT_WINDOWEND;
248 : 19 : return NULL;
249 : : }
250 : : }
251 : : else
252 : : {
253 : : /*
254 : : * Backwards scan, so check for stepping off start of window.
255 : : * Change only state-machine status if so.
256 : : */
8311 tgl@sss.pgh.pa.us 257 [ # # ]:UBC 0 : if (node->position <= node->offset + 1)
258 : : {
259 : 0 : node->lstate = LIMIT_WINDOWSTART;
8324 260 : 0 : return NULL;
261 : : }
262 : :
263 : : /*
264 : : * Get previous tuple from subplan; there should be one! And
265 : : * change state-machine status.
266 : : */
8311 267 : 0 : slot = ExecProcNode(outerPlan);
8324 268 [ # # # # ]: 0 : if (TupIsNull(slot))
8083 269 [ # # ]: 0 : elog(ERROR, "LIMIT subplan failed to run backwards");
8311 270 : 0 : node->subSlot = slot;
271 : 0 : node->position--;
1978 alvherre@alvh.no-ip. 272 : 0 : node->lstate = LIMIT_INWINDOW;
273 : : }
8324 tgl@sss.pgh.pa.us 274 :CBC 88 : break;
275 : :
276 : 6 : case LIMIT_SUBPLANEOF:
277 [ - + ]: 6 : if (ScanDirectionIsForward(direction))
8324 tgl@sss.pgh.pa.us 278 :UBC 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 : : */
8311 tgl@sss.pgh.pa.us 284 :CBC 6 : slot = ExecProcNode(outerPlan);
8324 285 [ + - - + ]: 6 : if (TupIsNull(slot))
8083 tgl@sss.pgh.pa.us 286 [ # # ]:UBC 0 : elog(ERROR, "LIMIT subplan failed to run backwards");
8311 tgl@sss.pgh.pa.us 287 :CBC 6 : node->subSlot = slot;
288 : 6 : node->lstate = LIMIT_INWINDOW;
289 : : /* position does not change 'cause we didn't advance it before */
8324 290 : 6 : break;
291 : :
292 : 12 : case LIMIT_WINDOWEND:
293 [ - + ]: 12 : if (ScanDirectionIsForward(direction))
8324 tgl@sss.pgh.pa.us 294 :UBC 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 : : */
1978 alvherre@alvh.no-ip. 301 [ + + ]:CBC 12 : if (node->limitOption == LIMIT_OPTION_WITH_TIES)
302 : : {
303 : 9 : slot = ExecProcNode(outerPlan);
304 [ + - - + ]: 9 : if (TupIsNull(slot))
1978 alvherre@alvh.no-ip. 305 [ # # ]:UBC 0 : elog(ERROR, "LIMIT subplan failed to run backwards");
1978 alvherre@alvh.no-ip. 306 :CBC 9 : node->subSlot = slot;
307 : 9 : node->lstate = LIMIT_INWINDOW;
308 : : }
309 : : else
310 : : {
311 : : /*
312 : : * Backing up from window end: simply re-return the last tuple
313 : : * fetched from the subplan.
314 : : */
315 : 3 : slot = node->subSlot;
316 : 3 : node->lstate = LIMIT_INWINDOW;
317 : : /* position does not change 'cause we didn't advance it before */
318 : : }
8324 tgl@sss.pgh.pa.us 319 : 12 : break;
320 : :
321 : 12 : case LIMIT_WINDOWSTART:
322 [ - + ]: 12 : if (!ScanDirectionIsForward(direction))
8324 tgl@sss.pgh.pa.us 323 :UBC 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 : : */
8311 tgl@sss.pgh.pa.us 329 :CBC 12 : slot = node->subSlot;
330 : 12 : node->lstate = LIMIT_INWINDOW;
331 : : /* position does not change 'cause we didn't change it before */
8324 332 : 12 : break;
333 : :
8324 tgl@sss.pgh.pa.us 334 :UBC 0 : default:
8083 335 [ # # ]: 0 : elog(ERROR, "impossible LIMIT state: %d",
336 : : (int) node->lstate);
337 : : slot = NULL; /* keep compiler quiet */
338 : : break;
339 : : }
340 : :
341 : : /* Return the current tuple */
8324 tgl@sss.pgh.pa.us 342 [ + - - + ]:CBC 18680 : Assert(!TupIsNull(slot));
343 : :
7479 344 : 18680 : return slot;
345 : : }
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
8311 353 : 32184 : recompute_limits(LimitState *node)
354 : : {
355 : 32184 : ExprContext *econtext = node->ps.ps_ExprContext;
356 : : Datum val;
357 : : bool isNull;
358 : :
9081 359 [ + + ]: 32184 : if (node->limitOffset)
360 : : {
6852 361 : 158 : val = ExecEvalExprSwitchContext(node->limitOffset,
362 : : econtext,
363 : : &isNull);
364 : : /* Interpret NULL offset as no offset */
9081 365 [ + + ]: 158 : if (isNull)
8311 366 : 3 : node->offset = 0;
367 : : else
368 : : {
6852 369 : 155 : node->offset = DatumGetInt64(val);
370 [ - + ]: 155 : if (node->offset < 0)
6389 tgl@sss.pgh.pa.us 371 [ # # ]:UBC 0 : ereport(ERROR,
372 : : (errcode(ERRCODE_INVALID_ROW_COUNT_IN_RESULT_OFFSET_CLAUSE),
373 : : errmsg("OFFSET must not be negative")));
374 : : }
375 : : }
376 : : else
377 : : {
378 : : /* No OFFSET supplied */
8311 tgl@sss.pgh.pa.us 379 :CBC 32026 : node->offset = 0;
380 : : }
381 : :
9081 382 [ + + ]: 32184 : if (node->limitCount)
383 : : {
6852 384 : 32158 : val = ExecEvalExprSwitchContext(node->limitCount,
385 : : econtext,
386 : : &isNull);
387 : : /* Interpret NULL count as no count (LIMIT ALL) */
9081 388 [ + + ]: 32158 : if (isNull)
389 : : {
8311 390 : 3 : node->count = 0;
6852 391 : 3 : node->noCount = true;
392 : : }
393 : : else
394 : : {
395 : 32155 : node->count = DatumGetInt64(val);
396 [ - + ]: 32155 : if (node->count < 0)
6389 tgl@sss.pgh.pa.us 397 [ # # ]:UBC 0 : ereport(ERROR,
398 : : (errcode(ERRCODE_INVALID_ROW_COUNT_IN_LIMIT_CLAUSE),
399 : : errmsg("LIMIT must not be negative")));
6852 tgl@sss.pgh.pa.us 400 :CBC 32155 : node->noCount = false;
401 : : }
402 : : }
403 : : else
404 : : {
405 : : /* No COUNT supplied */
8311 406 : 26 : node->count = 0;
407 : 26 : node->noCount = true;
408 : : }
409 : :
410 : : /* Reset position to start-of-scan */
411 : 32184 : node->position = 0;
412 : 32184 : node->subSlot = NULL;
413 : :
414 : : /* Set state-machine state */
6687 415 : 32184 : 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 : : */
2930 rhaas@postgresql.org 423 : 32184 : ExecSetTupleBound(compute_tuples_needed(node), outerPlanState(node));
5406 tgl@sss.pgh.pa.us 424 : 32184 : }
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
2930 rhaas@postgresql.org 431 : 32184 : compute_tuples_needed(LimitState *node)
432 : : {
1978 alvherre@alvh.no-ip. 433 [ + + + + ]: 32184 : if ((node->noCount) || (node->limitOption == LIMIT_OPTION_WITH_TIES))
2930 rhaas@postgresql.org 434 : 43 : return -1;
435 : : /* Note: if this overflows, we'll return a negative value, which is OK */
436 : 32141 : return node->count + node->offset;
437 : : }
438 : :
439 : : /* ----------------------------------------------------------------
440 : : * ExecInitLimit
441 : : *
442 : : * This initializes the limit node state structures and
443 : : * the node's subplan.
444 : : * ----------------------------------------------------------------
445 : : */
446 : : LimitState *
7130 tgl@sss.pgh.pa.us 447 : 2468 : ExecInitLimit(Limit *node, EState *estate, int eflags)
448 : : {
449 : : LimitState *limitstate;
450 : : Plan *outerPlan;
451 : :
452 : : /* check for unsupported flags */
453 [ - + ]: 2468 : Assert(!(eflags & EXEC_FLAG_MARK));
454 : :
455 : : /*
456 : : * create state structure
457 : : */
9081 458 : 2468 : limitstate = makeNode(LimitState);
8311 459 : 2468 : limitstate->ps.plan = (Plan *) node;
460 : 2468 : limitstate->ps.state = estate;
2973 andres@anarazel.de 461 : 2468 : limitstate->ps.ExecProcNode = ExecLimit;
462 : :
8324 tgl@sss.pgh.pa.us 463 : 2468 : 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 : : */
8311 471 : 2468 : ExecAssignExprContext(estate, &limitstate->ps);
472 : :
473 : : /*
474 : : * initialize outer plan
475 : : */
2759 andres@anarazel.de 476 : 2468 : outerPlan = outerPlan(node);
477 : 2468 : outerPlanState(limitstate) = ExecInitNode(outerPlan, estate, eflags);
478 : :
479 : : /*
480 : : * initialize child expressions
481 : : */
8303 tgl@sss.pgh.pa.us 482 : 2468 : limitstate->limitOffset = ExecInitExpr((Expr *) node->limitOffset,
483 : : (PlanState *) limitstate);
484 : 2468 : limitstate->limitCount = ExecInitExpr((Expr *) node->limitCount,
485 : : (PlanState *) limitstate);
1978 alvherre@alvh.no-ip. 486 : 2468 : limitstate->limitOption = node->limitOption;
487 : :
488 : : /*
489 : : * Initialize result type.
490 : : */
2493 andres@anarazel.de 491 : 2468 : ExecInitResultTypeTL(&limitstate->ps);
492 : :
2487 493 : 2468 : limitstate->ps.resultopsset = true;
494 : 2468 : limitstate->ps.resultops = ExecGetResultSlotOps(outerPlanState(limitstate),
495 : : &limitstate->ps.resultopsfixed);
496 : :
497 : : /*
498 : : * limit nodes do no projections, so initialize projection info for this
499 : : * node appropriately
500 : : */
8311 tgl@sss.pgh.pa.us 501 : 2468 : limitstate->ps.ps_ProjInfo = NULL;
502 : :
503 : : /*
504 : : * Initialize the equality evaluation, to detect ties.
505 : : */
1978 alvherre@alvh.no-ip. 506 [ + + ]: 2468 : if (node->limitOption == LIMIT_OPTION_WITH_TIES)
507 : : {
508 : : TupleDesc desc;
509 : : const TupleTableSlotOps *ops;
510 : :
511 : 15 : desc = ExecGetResultType(outerPlanState(limitstate));
512 : 15 : ops = ExecGetResultSlotOps(outerPlanState(limitstate), NULL);
513 : :
514 : 15 : limitstate->last_slot = ExecInitExtraTupleSlot(estate, desc, ops);
515 : 15 : limitstate->eqfunction = execTuplesMatchPrepare(desc,
516 : : node->uniqNumCols,
517 : 15 : node->uniqColIdx,
518 : 15 : node->uniqOperators,
519 : 15 : node->uniqCollations,
520 : : &limitstate->ps);
521 : : }
522 : :
8311 tgl@sss.pgh.pa.us 523 : 2468 : return limitstate;
524 : : }
525 : :
526 : : /* ----------------------------------------------------------------
527 : : * ExecEndLimit
528 : : *
529 : : * This shuts down the subplan and frees resources allocated
530 : : * to this node.
531 : : * ----------------------------------------------------------------
532 : : */
533 : : void
534 : 2436 : ExecEndLimit(LimitState *node)
535 : : {
8301 536 : 2436 : ExecEndNode(outerPlanState(node));
9081 537 : 2436 : }
538 : :
539 : :
540 : : void
5535 541 : 30495 : ExecReScanLimit(LimitState *node)
542 : : {
1157 543 : 30495 : 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 : : */
6687 550 : 30495 : recompute_limits(node);
551 : :
552 : : /*
553 : : * if chgParam of subnode is not null then plan will be re-scanned by
554 : : * first ExecProcNode.
555 : : */
1157 556 [ + + ]: 30495 : if (outerPlan->chgParam == NULL)
557 : 60 : ExecReScan(outerPlan);
9081 558 : 30495 : }
|
