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-2024, 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 34894 : ExecLimit(PlanState *pstate)
41 : {
42 34894 : LimitState *node = castNode(LimitState, pstate);
43 34894 : ExprContext *econtext = node->ps.ps_ExprContext;
44 : ScanDirection direction;
45 : TupleTableSlot *slot;
46 : PlanState *outerPlan;
47 :
48 34894 : CHECK_FOR_INTERRUPTS();
49 :
50 : /*
51 : * get information from the node
52 : */
53 34894 : direction = node->ps.state->es_direction;
54 34894 : outerPlan = outerPlanState(node);
55 :
56 : /*
57 : * The main logic is a simple state machine.
58 : */
59 34894 : switch (node->lstate)
60 : {
61 3256 : 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 3256 : recompute_limits(node);
70 :
71 : /* FALL THRU */
72 :
73 4156 : case LIMIT_RESCAN:
74 :
75 : /*
76 : * If backwards scan, just return NULL without changing state.
77 : */
78 4156 : if (!ScanDirectionIsForward(direction))
79 0 : return NULL;
80 :
81 : /*
82 : * Check for empty window; if so, treat like empty subplan.
83 : */
84 4156 : if (node->count <= 0 && !node->noCount)
85 : {
86 138 : node->lstate = LIMIT_EMPTY;
87 138 : return NULL;
88 : }
89 :
90 : /*
91 : * Fetch rows from subplan until we reach position > offset.
92 : */
93 : for (;;)
94 : {
95 508776 : slot = ExecProcNode(outerPlan);
96 508764 : if (TupIsNull(slot))
97 : {
98 : /*
99 : * The subplan returns too few tuples for us to produce
100 : * any output at all.
101 : */
102 252 : node->lstate = LIMIT_EMPTY;
103 252 : return NULL;
104 : }
105 :
106 : /*
107 : * Tuple at limit is needed for comparison in subsequent
108 : * execution to detect ties.
109 : */
110 508512 : if (node->limitOption == LIMIT_OPTION_WITH_TIES &&
111 26 : node->position - node->offset == node->count - 1)
112 : {
113 12 : ExecCopySlot(node->last_slot, slot);
114 : }
115 508512 : node->subSlot = slot;
116 508512 : if (++node->position > node->offset)
117 3754 : break;
118 : }
119 :
120 : /*
121 : * Okay, we have the first tuple of the window.
122 : */
123 3754 : node->lstate = LIMIT_INWINDOW;
124 3754 : break;
125 :
126 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 :
134 30506 : case LIMIT_INWINDOW:
135 30506 : 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 30416 : if (!node->noCount &&
154 29912 : node->position - node->offset >= node->count)
155 : {
156 3280 : if (node->limitOption == LIMIT_OPTION_COUNT)
157 : {
158 3242 : node->lstate = LIMIT_WINDOWEND;
159 3242 : return NULL;
160 : }
161 : else
162 : {
163 38 : 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 27136 : slot = ExecProcNode(outerPlan);
173 27130 : if (TupIsNull(slot))
174 : {
175 168 : node->lstate = LIMIT_SUBPLANEOF;
176 168 : 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 26962 : if (node->limitOption == LIMIT_OPTION_WITH_TIES &&
185 26 : node->position - node->offset == node->count - 1)
186 : {
187 26 : ExecCopySlot(node->last_slot, slot);
188 : }
189 26962 : node->subSlot = slot;
190 26962 : node->position++;
191 26962 : 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 90 : if (node->position <= node->offset + 1)
201 : {
202 30 : node->lstate = LIMIT_WINDOWSTART;
203 30 : return NULL;
204 : }
205 :
206 : /*
207 : * Get previous tuple from subplan; there should be one!
208 : */
209 60 : slot = ExecProcNode(outerPlan);
210 60 : if (TupIsNull(slot))
211 0 : elog(ERROR, "LIMIT subplan failed to run backwards");
212 60 : node->subSlot = slot;
213 60 : node->position--;
214 60 : break;
215 : }
216 :
217 : Assert(node->lstate == LIMIT_WINDOWEND_TIES);
218 : /* FALL THRU */
219 :
220 : case LIMIT_WINDOWEND_TIES:
221 210 : if (ScanDirectionIsForward(direction))
222 : {
223 : /*
224 : * Advance the subplan until we find the first row with
225 : * different ORDER BY pathkeys.
226 : */
227 210 : slot = ExecProcNode(outerPlan);
228 210 : if (TupIsNull(slot))
229 : {
230 2 : node->lstate = LIMIT_SUBPLANEOF;
231 2 : 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 208 : econtext->ecxt_innertuple = slot;
239 208 : econtext->ecxt_outertuple = node->last_slot;
240 208 : if (ExecQualAndReset(node->eqfunction, econtext))
241 : {
242 172 : node->subSlot = slot;
243 172 : node->position++;
244 : }
245 : else
246 : {
247 36 : node->lstate = LIMIT_WINDOWEND;
248 36 : 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 : */
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 172 : break;
275 :
276 12 : case LIMIT_SUBPLANEOF:
277 12 : 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 12 : slot = ExecProcNode(outerPlan);
285 12 : if (TupIsNull(slot))
286 0 : elog(ERROR, "LIMIT subplan failed to run backwards");
287 12 : node->subSlot = slot;
288 12 : node->lstate = LIMIT_INWINDOW;
289 : /* position does not change 'cause we didn't advance it before */
290 12 : break;
291 :
292 24 : case LIMIT_WINDOWEND:
293 24 : 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 24 : if (node->limitOption == LIMIT_OPTION_WITH_TIES)
302 : {
303 18 : slot = ExecProcNode(outerPlan);
304 18 : if (TupIsNull(slot))
305 0 : elog(ERROR, "LIMIT subplan failed to run backwards");
306 18 : node->subSlot = slot;
307 18 : 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 6 : slot = node->subSlot;
316 6 : node->lstate = LIMIT_INWINDOW;
317 : /* position does not change 'cause we didn't advance it before */
318 : }
319 24 : break;
320 :
321 24 : case LIMIT_WINDOWSTART:
322 24 : 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 24 : slot = node->subSlot;
330 24 : node->lstate = LIMIT_INWINDOW;
331 : /* position does not change 'cause we didn't change it before */
332 24 : break;
333 :
334 0 : default:
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 */
342 : Assert(!TupIsNull(slot));
343 :
344 31008 : 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
353 4156 : recompute_limits(LimitState *node)
354 : {
355 4156 : ExprContext *econtext = node->ps.ps_ExprContext;
356 : Datum val;
357 : bool isNull;
358 :
359 4156 : if (node->limitOffset)
360 : {
361 300 : val = ExecEvalExprSwitchContext(node->limitOffset,
362 : econtext,
363 : &isNull);
364 : /* Interpret NULL offset as no offset */
365 300 : if (isNull)
366 6 : node->offset = 0;
367 : else
368 : {
369 294 : node->offset = DatumGetInt64(val);
370 294 : 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 : }
376 : else
377 : {
378 : /* No OFFSET supplied */
379 3856 : node->offset = 0;
380 : }
381 :
382 4156 : if (node->limitCount)
383 : {
384 4108 : val = ExecEvalExprSwitchContext(node->limitCount,
385 : econtext,
386 : &isNull);
387 : /* Interpret NULL count as no count (LIMIT ALL) */
388 4108 : if (isNull)
389 : {
390 6 : node->count = 0;
391 6 : node->noCount = true;
392 : }
393 : else
394 : {
395 4102 : node->count = DatumGetInt64(val);
396 4102 : 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 4102 : node->noCount = false;
401 : }
402 : }
403 : else
404 : {
405 : /* No COUNT supplied */
406 48 : node->count = 0;
407 48 : node->noCount = true;
408 : }
409 :
410 : /* Reset position to start-of-scan */
411 4156 : node->position = 0;
412 4156 : node->subSlot = NULL;
413 :
414 : /* Set state-machine state */
415 4156 : 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 4156 : ExecSetTupleBound(compute_tuples_needed(node), outerPlanState(node));
424 4156 : }
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 4156 : compute_tuples_needed(LimitState *node)
432 : {
433 4156 : if ((node->noCount) || (node->limitOption == LIMIT_OPTION_WITH_TIES))
434 80 : return -1;
435 : /* Note: if this overflows, we'll return a negative value, which is OK */
436 4076 : 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 *
447 4646 : ExecInitLimit(Limit *node, EState *estate, int eflags)
448 : {
449 : LimitState *limitstate;
450 : Plan *outerPlan;
451 :
452 : /* check for unsupported flags */
453 : Assert(!(eflags & EXEC_FLAG_MARK));
454 :
455 : /*
456 : * create state structure
457 : */
458 4646 : limitstate = makeNode(LimitState);
459 4646 : limitstate->ps.plan = (Plan *) node;
460 4646 : limitstate->ps.state = estate;
461 4646 : limitstate->ps.ExecProcNode = ExecLimit;
462 :
463 4646 : 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 4646 : ExecAssignExprContext(estate, &limitstate->ps);
472 :
473 : /*
474 : * initialize outer plan
475 : */
476 4646 : outerPlan = outerPlan(node);
477 4646 : outerPlanState(limitstate) = ExecInitNode(outerPlan, estate, eflags);
478 :
479 : /*
480 : * initialize child expressions
481 : */
482 4646 : limitstate->limitOffset = ExecInitExpr((Expr *) node->limitOffset,
483 : (PlanState *) limitstate);
484 4646 : limitstate->limitCount = ExecInitExpr((Expr *) node->limitCount,
485 : (PlanState *) limitstate);
486 4646 : limitstate->limitOption = node->limitOption;
487 :
488 : /*
489 : * Initialize result type.
490 : */
491 4646 : ExecInitResultTypeTL(&limitstate->ps);
492 :
493 4646 : limitstate->ps.resultopsset = true;
494 4646 : 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 : */
501 4646 : limitstate->ps.ps_ProjInfo = NULL;
502 :
503 : /*
504 : * Initialize the equality evaluation, to detect ties.
505 : */
506 4646 : if (node->limitOption == LIMIT_OPTION_WITH_TIES)
507 : {
508 : TupleDesc desc;
509 : const TupleTableSlotOps *ops;
510 :
511 26 : desc = ExecGetResultType(outerPlanState(limitstate));
512 26 : ops = ExecGetResultSlotOps(outerPlanState(limitstate), NULL);
513 :
514 26 : limitstate->last_slot = ExecInitExtraTupleSlot(estate, desc, ops);
515 26 : limitstate->eqfunction = execTuplesMatchPrepare(desc,
516 : node->uniqNumCols,
517 26 : node->uniqColIdx,
518 26 : node->uniqOperators,
519 26 : node->uniqCollations,
520 : &limitstate->ps);
521 : }
522 :
523 4646 : 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 4586 : ExecEndLimit(LimitState *node)
535 : {
536 4586 : ExecEndNode(outerPlanState(node));
537 4586 : }
538 :
539 :
540 : void
541 900 : ExecReScanLimit(LimitState *node)
542 : {
543 900 : 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 900 : 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 900 : if (outerPlan->chgParam == NULL)
557 120 : ExecReScan(outerPlan);
558 900 : }
|
