PostgreSQL Source Code git master
All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
nodeLimit.c
Go to the documentation of this file.
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
28static void recompute_limits(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 */
39static TupleTableSlot * /* return: a tuple or NULL */
41{
42 LimitState *node = castNode(LimitState, pstate);
43 ExprContext *econtext = node->ps.ps_ExprContext;
44 ScanDirection direction;
45 TupleTableSlot *slot;
47
49
50 /*
51 * get information from the node
52 */
53 direction = node->ps.state->es_direction;
55
56 /*
57 * The main logic is a simple state machine.
58 */
59 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 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 if (!ScanDirectionIsForward(direction))
79 return NULL;
80
81 /*
82 * Check for empty window; if so, treat like empty subplan.
83 */
84 if (node->count <= 0 && !node->noCount)
85 {
86 node->lstate = LIMIT_EMPTY;
87 return NULL;
88 }
89
90 /*
91 * Fetch rows from subplan until we reach position > offset.
92 */
93 for (;;)
94 {
95 slot = ExecProcNode(outerPlan);
96 if (TupIsNull(slot))
97 {
98 /*
99 * The subplan returns too few tuples for us to produce
100 * any output at all.
101 */
102 node->lstate = LIMIT_EMPTY;
103 return NULL;
104 }
105
106 /*
107 * Tuple at limit is needed for comparison in subsequent
108 * execution to detect ties.
109 */
110 if (node->limitOption == LIMIT_OPTION_WITH_TIES &&
111 node->position - node->offset == node->count - 1)
112 {
113 ExecCopySlot(node->last_slot, slot);
114 }
115 node->subSlot = slot;
116 if (++node->position > node->offset)
117 break;
118 }
119
120 /*
121 * Okay, we have the first tuple of the window.
122 */
123 node->lstate = LIMIT_INWINDOW;
124 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 return NULL;
133
134 case LIMIT_INWINDOW:
135 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 if (!node->noCount &&
154 node->position - node->offset >= node->count)
155 {
156 if (node->limitOption == LIMIT_OPTION_COUNT)
157 {
158 node->lstate = LIMIT_WINDOWEND;
159 return NULL;
160 }
161 else
162 {
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 slot = ExecProcNode(outerPlan);
173 if (TupIsNull(slot))
174 {
175 node->lstate = LIMIT_SUBPLANEOF;
176 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 if (node->limitOption == LIMIT_OPTION_WITH_TIES &&
185 node->position - node->offset == node->count - 1)
186 {
187 ExecCopySlot(node->last_slot, slot);
188 }
189 node->subSlot = slot;
190 node->position++;
191 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 if (node->position <= node->offset + 1)
201 {
203 return NULL;
204 }
205
206 /*
207 * Get previous tuple from subplan; there should be one!
208 */
209 slot = ExecProcNode(outerPlan);
210 if (TupIsNull(slot))
211 elog(ERROR, "LIMIT subplan failed to run backwards");
212 node->subSlot = slot;
213 node->position--;
214 break;
215 }
216
218 /* FALL THRU */
219
221 if (ScanDirectionIsForward(direction))
222 {
223 /*
224 * Advance the subplan until we find the first row with
225 * different ORDER BY pathkeys.
226 */
227 slot = ExecProcNode(outerPlan);
228 if (TupIsNull(slot))
229 {
230 node->lstate = LIMIT_SUBPLANEOF;
231 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 econtext->ecxt_innertuple = slot;
239 econtext->ecxt_outertuple = node->last_slot;
240 if (ExecQualAndReset(node->eqfunction, econtext))
241 {
242 node->subSlot = slot;
243 node->position++;
244 }
245 else
246 {
247 node->lstate = LIMIT_WINDOWEND;
248 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 if (node->position <= node->offset + 1)
258 {
260 return NULL;
261 }
262
263 /*
264 * Get previous tuple from subplan; there should be one! And
265 * change state-machine status.
266 */
267 slot = ExecProcNode(outerPlan);
268 if (TupIsNull(slot))
269 elog(ERROR, "LIMIT subplan failed to run backwards");
270 node->subSlot = slot;
271 node->position--;
272 node->lstate = LIMIT_INWINDOW;
273 }
274 break;
275
276 case LIMIT_SUBPLANEOF:
277 if (ScanDirectionIsForward(direction))
278 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 slot = ExecProcNode(outerPlan);
285 if (TupIsNull(slot))
286 elog(ERROR, "LIMIT subplan failed to run backwards");
287 node->subSlot = slot;
288 node->lstate = LIMIT_INWINDOW;
289 /* position does not change 'cause we didn't advance it before */
290 break;
291
292 case LIMIT_WINDOWEND:
293 if (ScanDirectionIsForward(direction))
294 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 */
302 {
303 slot = ExecProcNode(outerPlan);
304 if (TupIsNull(slot))
305 elog(ERROR, "LIMIT subplan failed to run backwards");
306 node->subSlot = slot;
307 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 slot = node->subSlot;
316 node->lstate = LIMIT_INWINDOW;
317 /* position does not change 'cause we didn't advance it before */
318 }
319 break;
320
322 if (!ScanDirectionIsForward(direction))
323 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 slot = node->subSlot;
330 node->lstate = LIMIT_INWINDOW;
331 /* position does not change 'cause we didn't change it before */
332 break;
333
334 default:
335 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 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 */
352static void
354{
355 ExprContext *econtext = node->ps.ps_ExprContext;
356 Datum val;
357 bool isNull;
358
359 if (node->limitOffset)
360 {
362 econtext,
363 &isNull);
364 /* Interpret NULL offset as no offset */
365 if (isNull)
366 node->offset = 0;
367 else
368 {
369 node->offset = DatumGetInt64(val);
370 if (node->offset < 0)
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 node->offset = 0;
380 }
381
382 if (node->limitCount)
383 {
385 econtext,
386 &isNull);
387 /* Interpret NULL count as no count (LIMIT ALL) */
388 if (isNull)
389 {
390 node->count = 0;
391 node->noCount = true;
392 }
393 else
394 {
395 node->count = DatumGetInt64(val);
396 if (node->count < 0)
398 (errcode(ERRCODE_INVALID_ROW_COUNT_IN_LIMIT_CLAUSE),
399 errmsg("LIMIT must not be negative")));
400 node->noCount = false;
401 }
402 }
403 else
404 {
405 /* No COUNT supplied */
406 node->count = 0;
407 node->noCount = true;
408 }
409
410 /* Reset position to start-of-scan */
411 node->position = 0;
412 node->subSlot = NULL;
413
414 /* Set state-machine state */
415 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 */
424}
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 */
430static int64
432{
433 if ((node->noCount) || (node->limitOption == LIMIT_OPTION_WITH_TIES))
434 return -1;
435 /* Note: if this overflows, we'll return a negative value, which is OK */
436 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 */
447ExecInitLimit(Limit *node, EState *estate, int eflags)
448{
449 LimitState *limitstate;
451
452 /* check for unsupported flags */
453 Assert(!(eflags & EXEC_FLAG_MARK));
454
455 /*
456 * create state structure
457 */
458 limitstate = makeNode(LimitState);
459 limitstate->ps.plan = (Plan *) node;
460 limitstate->ps.state = estate;
461 limitstate->ps.ExecProcNode = ExecLimit;
462
463 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 ExecAssignExprContext(estate, &limitstate->ps);
472
473 /*
474 * initialize outer plan
475 */
476 outerPlan = outerPlan(node);
477 outerPlanState(limitstate) = ExecInitNode(outerPlan, estate, eflags);
478
479 /*
480 * initialize child expressions
481 */
482 limitstate->limitOffset = ExecInitExpr((Expr *) node->limitOffset,
483 (PlanState *) limitstate);
484 limitstate->limitCount = ExecInitExpr((Expr *) node->limitCount,
485 (PlanState *) limitstate);
486 limitstate->limitOption = node->limitOption;
487
488 /*
489 * Initialize result type.
490 */
491 ExecInitResultTypeTL(&limitstate->ps);
492
493 limitstate->ps.resultopsset = true;
494 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 limitstate->ps.ps_ProjInfo = NULL;
502
503 /*
504 * Initialize the equality evaluation, to detect ties.
505 */
507 {
508 TupleDesc desc;
509 const TupleTableSlotOps *ops;
510
511 desc = ExecGetResultType(outerPlanState(limitstate));
512 ops = ExecGetResultSlotOps(outerPlanState(limitstate), NULL);
513
514 limitstate->last_slot = ExecInitExtraTupleSlot(estate, desc, ops);
515 limitstate->eqfunction = execTuplesMatchPrepare(desc,
516 node->uniqNumCols,
517 node->uniqColIdx,
518 node->uniqOperators,
519 node->uniqCollations,
520 &limitstate->ps);
521 }
522
523 return limitstate;
524}
525
526/* ----------------------------------------------------------------
527 * ExecEndLimit
528 *
529 * This shuts down the subplan and frees resources allocated
530 * to this node.
531 * ----------------------------------------------------------------
532 */
533void
535{
537}
538
539
540void
542{
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 (outerPlan->chgParam == NULL)
558}
#define Assert(condition)
Definition: c.h:812
int64_t int64
Definition: c.h:482
int errcode(int sqlerrcode)
Definition: elog.c:853
int errmsg(const char *fmt,...)
Definition: elog.c:1070
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
#define ereport(elevel,...)
Definition: elog.h:149
void ExecReScan(PlanState *node)
Definition: execAmi.c:76
ExprState * ExecInitExpr(Expr *node, PlanState *parent)
Definition: execExpr.c:138
ExprState * execTuplesMatchPrepare(TupleDesc desc, int numCols, const AttrNumber *keyColIdx, const Oid *eqOperators, const Oid *collations, PlanState *parent)
Definition: execGrouping.c:58
void ExecSetTupleBound(int64 tuples_needed, PlanState *child_node)
Definition: execProcnode.c:848
void ExecEndNode(PlanState *node)
Definition: execProcnode.c:562
PlanState * ExecInitNode(Plan *node, EState *estate, int eflags)
Definition: execProcnode.c:142
void ExecInitResultTypeTL(PlanState *planstate)
Definition: execTuples.c:1942
TupleTableSlot * ExecInitExtraTupleSlot(EState *estate, TupleDesc tupledesc, const TupleTableSlotOps *tts_ops)
Definition: execTuples.c:2018
TupleDesc ExecGetResultType(PlanState *planstate)
Definition: execUtils.c:495
void ExecAssignExprContext(EState *estate, PlanState *planstate)
Definition: execUtils.c:485
const TupleTableSlotOps * ExecGetResultSlotOps(PlanState *planstate, bool *isfixed)
Definition: execUtils.c:504
#define outerPlanState(node)
Definition: execnodes.h:1222
@ LIMIT_WINDOWEND_TIES
Definition: execnodes.h:2871
@ LIMIT_WINDOWEND
Definition: execnodes.h:2873
@ LIMIT_INWINDOW
Definition: execnodes.h:2870
@ LIMIT_SUBPLANEOF
Definition: execnodes.h:2872
@ LIMIT_WINDOWSTART
Definition: execnodes.h:2874
@ LIMIT_EMPTY
Definition: execnodes.h:2869
@ LIMIT_INITIAL
Definition: execnodes.h:2867
@ LIMIT_RESCAN
Definition: execnodes.h:2868
static bool ExecQualAndReset(ExprState *state, ExprContext *econtext)
Definition: executor.h:453
static TupleTableSlot * ExecProcNode(PlanState *node)
Definition: executor.h:267
static Datum ExecEvalExprSwitchContext(ExprState *state, ExprContext *econtext, bool *isNull)
Definition: executor.h:361
#define EXEC_FLAG_MARK
Definition: executor.h:69
long val
Definition: informix.c:689
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:122
void ExecReScanLimit(LimitState *node)
Definition: nodeLimit.c:541
LimitState * ExecInitLimit(Limit *node, EState *estate, int eflags)
Definition: nodeLimit.c:447
static int64 compute_tuples_needed(LimitState *node)
Definition: nodeLimit.c:431
static void recompute_limits(LimitState *node)
Definition: nodeLimit.c:353
void ExecEndLimit(LimitState *node)
Definition: nodeLimit.c:534
static TupleTableSlot * ExecLimit(PlanState *pstate)
Definition: nodeLimit.c:40
@ LIMIT_OPTION_COUNT
Definition: nodes.h:431
@ LIMIT_OPTION_WITH_TIES
Definition: nodes.h:432
#define makeNode(_type_)
Definition: nodes.h:155
#define castNode(_type_, nodeptr)
Definition: nodes.h:176
#define outerPlan(node)
Definition: plannodes.h:183
static int64 DatumGetInt64(Datum X)
Definition: postgres.h:385
uintptr_t Datum
Definition: postgres.h:64
#define ScanDirectionIsForward(direction)
Definition: sdir.h:64
ScanDirection
Definition: sdir.h:25
ScanDirection es_direction
Definition: execnodes.h:631
TupleTableSlot * ecxt_innertuple
Definition: execnodes.h:260
TupleTableSlot * ecxt_outertuple
Definition: execnodes.h:262
PlanState ps
Definition: execnodes.h:2879
ExprState * limitOffset
Definition: execnodes.h:2880
ExprState * limitCount
Definition: execnodes.h:2881
LimitOption limitOption
Definition: execnodes.h:2882
bool noCount
Definition: execnodes.h:2885
int64 position
Definition: execnodes.h:2887
TupleTableSlot * last_slot
Definition: execnodes.h:2891
int64 offset
Definition: execnodes.h:2883
ExprState * eqfunction
Definition: execnodes.h:2889
int64 count
Definition: execnodes.h:2884
LimitStateCond lstate
Definition: execnodes.h:2886
TupleTableSlot * subSlot
Definition: execnodes.h:2888
LimitOption limitOption
Definition: plannodes.h:1279
Node * limitCount
Definition: plannodes.h:1276
int uniqNumCols
Definition: plannodes.h:1282
Node * limitOffset
Definition: plannodes.h:1273
const TupleTableSlotOps * resultops
Definition: execnodes.h:1203
bool resultopsset
Definition: execnodes.h:1211
Plan * plan
Definition: execnodes.h:1126
EState * state
Definition: execnodes.h:1128
ExprContext * ps_ExprContext
Definition: execnodes.h:1165
ProjectionInfo * ps_ProjInfo
Definition: execnodes.h:1166
bool resultopsfixed
Definition: execnodes.h:1207
ExecProcNodeMtd ExecProcNode
Definition: execnodes.h:1132
#define TupIsNull(slot)
Definition: tuptable.h:306
static TupleTableSlot * ExecCopySlot(TupleTableSlot *dstslot, TupleTableSlot *srcslot)
Definition: tuptable.h:509