Age Owner 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-2023, 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 */
2092 andres 41 CBC 17972 : ExecLimit(PlanState *pstate)
42 : {
43 17972 : LimitState *node = castNode(LimitState, pstate);
1097 alvherre 44 17972 : ExprContext *econtext = node->ps.ps_ExprContext;
45 : ScanDirection direction;
46 : TupleTableSlot *slot;
47 : PlanState *outerPlan;
48 :
2084 andres 49 17972 : CHECK_FOR_INTERRUPTS();
50 :
51 : /*
52 : * get information from the node
53 : */
7430 tgl 54 17972 : direction = node->ps.state->es_direction;
55 17972 : outerPlan = outerPlanState(node);
56 :
57 : /*
58 : * The main logic is a simple state machine.
59 : */
60 17972 : switch (node->lstate)
61 : {
7443 62 1960 : 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 : */
5806 70 1960 : recompute_limits(node);
71 :
72 : /* FALL THRU */
73 :
74 2410 : case LIMIT_RESCAN:
75 :
76 : /*
77 : * If backwards scan, just return NULL without changing state.
78 : */
79 2410 : if (!ScanDirectionIsForward(direction))
5806 tgl 80 UBC 0 : return NULL;
81 :
82 : /*
83 : * Check for empty window; if so, treat like empty subplan.
84 : */
7430 tgl 85 CBC 2410 : if (node->count <= 0 && !node->noCount)
86 : {
87 69 : node->lstate = LIMIT_EMPTY;
8200 88 69 : return NULL;
89 : }
90 :
91 : /*
92 : * Fetch rows from subplan until we reach position > offset.
93 : */
94 : for (;;)
95 : {
7430 96 254720 : slot = ExecProcNode(outerPlan);
7443 97 254713 : if (TupIsNull(slot))
98 : {
99 : /*
100 : * The subplan returns too few tuples for us to produce
101 : * any output at all.
102 : */
7430 103 125 : node->lstate = LIMIT_EMPTY;
7443 104 125 : return NULL;
105 : }
106 :
107 : /*
108 : * Tuple at limit is needed for comparison in subsequent
109 : * execution to detect ties.
110 : */
1097 alvherre 111 254588 : if (node->limitOption == LIMIT_OPTION_WITH_TIES &&
112 13 : node->position - node->offset == node->count - 1)
113 : {
114 6 : ExecCopySlot(node->last_slot, slot);
115 : }
7430 tgl 116 254588 : node->subSlot = slot;
117 254588 : if (++node->position > node->offset)
7443 118 2209 : break;
119 : }
120 :
121 : /*
122 : * Okay, we have the first tuple of the window.
123 : */
7430 124 2209 : node->lstate = LIMIT_INWINDOW;
7443 125 2209 : break;
126 :
7443 tgl 127 UBC 0 : 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 0 : return NULL;
134 :
7443 tgl 135 CBC 15446 : case LIMIT_INWINDOW:
8200 136 15446 : 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 : */
7430 154 15401 : if (!node->noCount &&
4268 heikki.linnakangas 155 15149 : node->position - node->offset >= node->count)
156 : {
1097 alvherre 157 1882 : if (node->limitOption == LIMIT_OPTION_COUNT)
158 : {
159 1863 : node->lstate = LIMIT_WINDOWEND;
160 1863 : return NULL;
161 : }
162 : else
163 : {
164 19 : 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 13519 : slot = ExecProcNode(outerPlan);
174 13516 : if (TupIsNull(slot))
175 : {
176 82 : node->lstate = LIMIT_SUBPLANEOF;
177 82 : 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 13434 : if (node->limitOption == LIMIT_OPTION_WITH_TIES &&
186 13 : node->position - node->offset == node->count - 1)
187 : {
188 13 : ExecCopySlot(node->last_slot, slot);
189 : }
190 13434 : node->subSlot = slot;
191 13434 : node->position++;
192 13434 : 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 45 : if (node->position <= node->offset + 1)
202 : {
203 15 : node->lstate = LIMIT_WINDOWSTART;
7443 tgl 204 15 : return NULL;
205 : }
206 :
207 : /*
208 : * Get previous tuple from subplan; there should be one!
209 : */
1097 alvherre 210 30 : slot = ExecProcNode(outerPlan);
211 30 : if (TupIsNull(slot))
1097 alvherre 212 UBC 0 : elog(ERROR, "LIMIT subplan failed to run backwards");
1097 alvherre 213 CBC 30 : node->subSlot = slot;
214 30 : node->position--;
215 30 : break;
216 : }
217 :
1093 tgl 218 19 : Assert(node->lstate == LIMIT_WINDOWEND_TIES);
219 : /* FALL THRU */
220 :
221 : case LIMIT_WINDOWEND_TIES:
1097 alvherre 222 105 : if (ScanDirectionIsForward(direction))
223 : {
224 : /*
225 : * Advance the subplan until we find the first row with
226 : * different ORDER BY pathkeys.
227 : */
7430 tgl 228 105 : slot = ExecProcNode(outerPlan);
7443 229 105 : if (TupIsNull(slot))
230 : {
7430 231 1 : node->lstate = LIMIT_SUBPLANEOF;
7443 232 1 : return NULL;
233 : }
234 :
235 : /*
236 : * Test if the new tuple and the last tuple match. If so we
237 : * return the tuple.
238 : */
1097 alvherre 239 104 : econtext->ecxt_innertuple = slot;
240 104 : econtext->ecxt_outertuple = node->last_slot;
241 104 : if (ExecQualAndReset(node->eqfunction, econtext))
242 : {
243 86 : node->subSlot = slot;
244 86 : node->position++;
245 : }
246 : else
247 : {
248 18 : node->lstate = LIMIT_WINDOWEND;
249 18 : 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 : */
7430 tgl 258 UBC 0 : if (node->position <= node->offset + 1)
259 : {
260 0 : node->lstate = LIMIT_WINDOWSTART;
7443 261 0 : return NULL;
262 : }
263 :
264 : /*
265 : * Get previous tuple from subplan; there should be one! And
266 : * change state-machine status.
267 : */
7430 268 0 : slot = ExecProcNode(outerPlan);
7443 269 0 : if (TupIsNull(slot))
7202 270 0 : elog(ERROR, "LIMIT subplan failed to run backwards");
7430 271 0 : node->subSlot = slot;
272 0 : node->position--;
1097 alvherre 273 0 : node->lstate = LIMIT_INWINDOW;
274 : }
7443 tgl 275 CBC 86 : break;
276 :
277 6 : case LIMIT_SUBPLANEOF:
278 6 : if (ScanDirectionIsForward(direction))
7443 tgl 279 UBC 0 : 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 : */
7430 tgl 285 CBC 6 : slot = ExecProcNode(outerPlan);
7443 286 6 : if (TupIsNull(slot))
7202 tgl 287 UBC 0 : elog(ERROR, "LIMIT subplan failed to run backwards");
7430 tgl 288 CBC 6 : node->subSlot = slot;
289 6 : node->lstate = LIMIT_INWINDOW;
290 : /* position does not change 'cause we didn't advance it before */
7443 291 6 : break;
292 :
293 12 : case LIMIT_WINDOWEND:
294 12 : if (ScanDirectionIsForward(direction))
7443 tgl 295 UBC 0 : 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 : */
1097 alvherre 302 CBC 12 : if (node->limitOption == LIMIT_OPTION_WITH_TIES)
303 : {
304 9 : slot = ExecProcNode(outerPlan);
305 9 : if (TupIsNull(slot))
1097 alvherre 306 UBC 0 : elog(ERROR, "LIMIT subplan failed to run backwards");
1097 alvherre 307 CBC 9 : node->subSlot = slot;
308 9 : 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 3 : slot = node->subSlot;
317 3 : node->lstate = LIMIT_INWINDOW;
318 : /* position does not change 'cause we didn't advance it before */
319 : }
7443 tgl 320 12 : break;
321 :
322 12 : case LIMIT_WINDOWSTART:
323 12 : if (!ScanDirectionIsForward(direction))
7443 tgl 324 UBC 0 : return NULL;
325 :
326 : /*
327 : * Advancing after having backed off window start: simply
328 : * re-return the last tuple fetched from the subplan.
329 : */
7430 tgl 330 CBC 12 : slot = node->subSlot;
331 12 : node->lstate = LIMIT_INWINDOW;
332 : /* position does not change 'cause we didn't change it before */
7443 333 12 : break;
334 :
7443 tgl 335 UBC 0 : default:
7202 336 0 : 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 */
7443 tgl 343 CBC 15789 : Assert(!TupIsNull(slot));
344 :
6598 345 15789 : 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
7430 354 2410 : recompute_limits(LimitState *node)
355 : {
356 2410 : ExprContext *econtext = node->ps.ps_ExprContext;
357 : Datum val;
358 : bool isNull;
359 :
8200 360 2410 : if (node->limitOffset)
361 : {
5971 362 150 : val = ExecEvalExprSwitchContext(node->limitOffset,
363 : econtext,
364 : &isNull);
365 : /* Interpret NULL offset as no offset */
8200 366 150 : if (isNull)
7430 367 3 : node->offset = 0;
368 : else
369 : {
5971 370 147 : node->offset = DatumGetInt64(val);
371 147 : if (node->offset < 0)
5508 tgl 372 UBC 0 : 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 */
7430 tgl 380 CBC 2260 : node->offset = 0;
381 : }
382 :
8200 383 2410 : if (node->limitCount)
384 : {
5971 385 2386 : val = ExecEvalExprSwitchContext(node->limitCount,
386 : econtext,
387 : &isNull);
388 : /* Interpret NULL count as no count (LIMIT ALL) */
8200 389 2386 : if (isNull)
390 : {
7430 391 3 : node->count = 0;
5971 392 3 : node->noCount = true;
393 : }
394 : else
395 : {
396 2383 : node->count = DatumGetInt64(val);
397 2383 : if (node->count < 0)
5508 tgl 398 UBC 0 : ereport(ERROR,
399 : (errcode(ERRCODE_INVALID_ROW_COUNT_IN_LIMIT_CLAUSE),
400 : errmsg("LIMIT must not be negative")));
5971 tgl 401 CBC 2383 : node->noCount = false;
402 : }
403 : }
404 : else
405 : {
406 : /* No COUNT supplied */
7430 407 24 : node->count = 0;
408 24 : node->noCount = true;
409 : }
410 :
411 : /* Reset position to start-of-scan */
412 2410 : node->position = 0;
413 2410 : node->subSlot = NULL;
414 :
415 : /* Set state-machine state */
5806 416 2410 : 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 : */
2049 rhaas 424 2410 : ExecSetTupleBound(compute_tuples_needed(node), outerPlanState(node));
4525 tgl 425 2410 : }
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
2049 rhaas 432 2410 : compute_tuples_needed(LimitState *node)
433 : {
1097 alvherre 434 2410 : if ((node->noCount) || (node->limitOption == LIMIT_OPTION_WITH_TIES))
2049 rhaas 435 40 : return -1;
436 : /* Note: if this overflows, we'll return a negative value, which is OK */
437 2370 : 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 *
6249 tgl 448 2572 : ExecInitLimit(Limit *node, EState *estate, int eflags)
449 : {
450 : LimitState *limitstate;
451 : Plan *outerPlan;
452 :
453 : /* check for unsupported flags */
454 2572 : Assert(!(eflags & EXEC_FLAG_MARK));
455 :
456 : /*
457 : * create state structure
458 : */
8200 459 2572 : limitstate = makeNode(LimitState);
7430 460 2572 : limitstate->ps.plan = (Plan *) node;
461 2572 : limitstate->ps.state = estate;
2092 andres 462 2572 : limitstate->ps.ExecProcNode = ExecLimit;
463 :
7443 tgl 464 2572 : 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 : */
7430 472 2572 : ExecAssignExprContext(estate, &limitstate->ps);
473 :
474 : /*
475 : * initialize outer plan
476 : */
1878 andres 477 2572 : outerPlan = outerPlan(node);
478 2572 : outerPlanState(limitstate) = ExecInitNode(outerPlan, estate, eflags);
479 :
480 : /*
481 : * initialize child expressions
482 : */
7422 tgl 483 2572 : limitstate->limitOffset = ExecInitExpr((Expr *) node->limitOffset,
484 : (PlanState *) limitstate);
485 2572 : limitstate->limitCount = ExecInitExpr((Expr *) node->limitCount,
486 : (PlanState *) limitstate);
1097 alvherre 487 2572 : limitstate->limitOption = node->limitOption;
488 :
489 : /*
490 : * Initialize result type.
491 : */
1612 andres 492 2572 : ExecInitResultTypeTL(&limitstate->ps);
493 :
1606 494 2572 : limitstate->ps.resultopsset = true;
495 2572 : 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 : */
7430 tgl 502 2572 : limitstate->ps.ps_ProjInfo = NULL;
503 :
504 : /*
505 : * Initialize the equality evaluation, to detect ties.
506 : */
1097 alvherre 507 2572 : if (node->limitOption == LIMIT_OPTION_WITH_TIES)
508 : {
509 : TupleDesc desc;
510 : const TupleTableSlotOps *ops;
511 :
512 13 : desc = ExecGetResultType(outerPlanState(limitstate));
513 13 : ops = ExecGetResultSlotOps(outerPlanState(limitstate), NULL);
514 :
515 13 : limitstate->last_slot = ExecInitExtraTupleSlot(estate, desc, ops);
516 13 : limitstate->eqfunction = execTuplesMatchPrepare(desc,
517 : node->uniqNumCols,
518 13 : node->uniqColIdx,
519 13 : node->uniqOperators,
520 13 : node->uniqCollations,
521 : &limitstate->ps);
522 : }
523 :
7430 tgl 524 2572 : 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
535 2541 : ExecEndLimit(LimitState *node)
536 : {
537 2541 : ExecFreeExprContext(&node->ps);
7420 538 2541 : ExecEndNode(outerPlanState(node));
8200 539 2541 : }
540 :
541 :
542 : void
4654 543 450 : ExecReScanLimit(LimitState *node)
544 : {
276 tgl 545 GNC 450 : PlanState *outerPlan = outerPlanState(node);
546 :
5806 tgl 547 ECB : /*
548 : * Recompute limit/offset in case parameters changed, and reset the state
549 : * machine. We must do this before rescanning our child node, in case
550 : * it's a Sort that we are passing the parameters down to.
551 : */
5806 tgl 552 GIC 450 : recompute_limits(node);
553 :
8200 tgl 554 ECB : /*
555 : * if chgParam of subnode is not null then plan will be re-scanned by
556 : * first ExecProcNode.
557 : */
276 tgl 558 GNC 450 : if (outerPlan->chgParam == NULL)
559 60 : ExecReScan(outerPlan);
8200 tgl 560 CBC 450 : }
|
