1 /*-------------------------------------------------------------------------
4 * Routines to handle limiting of query results where appropriate
6 * Portions Copyright (c) 1996-2014, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
11 * src/backend/executor/nodeLimit.c
13 *-------------------------------------------------------------------------
17 * ExecLimit - extract a limited range of tuples
18 * ExecInitLimit - initialize node and subnodes..
19 * ExecEndLimit - shutdown node and subnodes
24 #include "executor/executor.h"
25 #include "executor/nodeLimit.h"
26 #include "nodes/nodeFuncs.h"
28 static void recompute_limits(LimitState *node);
29 static void pass_down_bound(LimitState *node, PlanState *child_node);
32 /* ----------------------------------------------------------------
35 * This is a very simple node which just performs LIMIT/OFFSET
36 * filtering on the stream of tuples returned by a subplan.
37 * ----------------------------------------------------------------
39 TupleTableSlot * /* return: a tuple or NULL */
40 ExecLimit(LimitState *node)
42 ScanDirection direction;
47 * get information from the node
49 direction = node->ps.state->es_direction;
50 outerPlan = outerPlanState(node);
53 * The main logic is a simple state machine.
60 * First call for this node, so compute limit/offset. (We can't do
61 * this any earlier, because parameters from upper nodes will not
62 * be set during ExecInitLimit.) This also sets position = 0 and
63 * changes the state to LIMIT_RESCAN.
65 recompute_limits(node);
72 * If backwards scan, just return NULL without changing state.
74 if (!ScanDirectionIsForward(direction))
78 * Check for empty window; if so, treat like empty subplan.
80 if (node->count <= 0 && !node->noCount)
82 node->lstate = LIMIT_EMPTY;
87 * Fetch rows from subplan until we reach position > offset.
91 slot = ExecProcNode(outerPlan);
95 * The subplan returns too few tuples for us to produce
98 node->lstate = LIMIT_EMPTY;
101 node->subSlot = slot;
102 if (++node->position > node->offset)
107 * Okay, we have the first tuple of the window.
109 node->lstate = LIMIT_INWINDOW;
115 * The subplan is known to return no tuples (or not more than
116 * OFFSET tuples, in general). So we return no tuples.
121 if (ScanDirectionIsForward(direction))
124 * Forwards scan, so check for stepping off end of window. If
125 * we are at the end of the window, return NULL without
126 * advancing the subplan or the position variable; but change
127 * the state machine state to record having done so.
129 if (!node->noCount &&
130 node->position - node->offset >= node->count)
132 node->lstate = LIMIT_WINDOWEND;
137 * Get next tuple from subplan, if any.
139 slot = ExecProcNode(outerPlan);
142 node->lstate = LIMIT_SUBPLANEOF;
145 node->subSlot = slot;
151 * Backwards scan, so check for stepping off start of window.
152 * As above, change only state-machine status if so.
154 if (node->position <= node->offset + 1)
156 node->lstate = LIMIT_WINDOWSTART;
161 * Get previous tuple from subplan; there should be one!
163 slot = ExecProcNode(outerPlan);
165 elog(ERROR, "LIMIT subplan failed to run backwards");
166 node->subSlot = slot;
171 case LIMIT_SUBPLANEOF:
172 if (ScanDirectionIsForward(direction))
176 * Backing up from subplan EOF, so re-fetch previous tuple; there
177 * should be one! Note previous tuple must be in window.
179 slot = ExecProcNode(outerPlan);
181 elog(ERROR, "LIMIT subplan failed to run backwards");
182 node->subSlot = slot;
183 node->lstate = LIMIT_INWINDOW;
184 /* position does not change 'cause we didn't advance it before */
187 case LIMIT_WINDOWEND:
188 if (ScanDirectionIsForward(direction))
192 * Backing up from window end: simply re-return the last tuple
193 * fetched from the subplan.
195 slot = node->subSlot;
196 node->lstate = LIMIT_INWINDOW;
197 /* position does not change 'cause we didn't advance it before */
200 case LIMIT_WINDOWSTART:
201 if (!ScanDirectionIsForward(direction))
205 * Advancing after having backed off window start: simply
206 * re-return the last tuple fetched from the subplan.
208 slot = node->subSlot;
209 node->lstate = LIMIT_INWINDOW;
210 /* position does not change 'cause we didn't change it before */
214 elog(ERROR, "impossible LIMIT state: %d",
216 slot = NULL; /* keep compiler quiet */
220 /* Return the current tuple */
221 Assert(!TupIsNull(slot));
227 * Evaluate the limit/offset expressions --- done at startup or rescan.
229 * This is also a handy place to reset the current-position state info.
232 recompute_limits(LimitState *node)
234 ExprContext *econtext = node->ps.ps_ExprContext;
238 if (node->limitOffset)
240 val = ExecEvalExprSwitchContext(node->limitOffset,
244 /* Interpret NULL offset as no offset */
249 node->offset = DatumGetInt64(val);
250 if (node->offset < 0)
252 (errcode(ERRCODE_INVALID_ROW_COUNT_IN_RESULT_OFFSET_CLAUSE),
253 errmsg("OFFSET must not be negative")));
258 /* No OFFSET supplied */
262 if (node->limitCount)
264 val = ExecEvalExprSwitchContext(node->limitCount,
268 /* Interpret NULL count as no count (LIMIT ALL) */
272 node->noCount = true;
276 node->count = DatumGetInt64(val);
279 (errcode(ERRCODE_INVALID_ROW_COUNT_IN_LIMIT_CLAUSE),
280 errmsg("LIMIT must not be negative")));
281 node->noCount = false;
286 /* No COUNT supplied */
288 node->noCount = true;
291 /* Reset position to start-of-scan */
293 node->subSlot = NULL;
295 /* Set state-machine state */
296 node->lstate = LIMIT_RESCAN;
298 /* Notify child node about limit, if useful */
299 pass_down_bound(node, outerPlanState(node));
303 * If we have a COUNT, and our input is a Sort node, notify it that it can
304 * use bounded sort. Also, if our input is a MergeAppend, we can apply the
305 * same bound to any Sorts that are direct children of the MergeAppend,
306 * since the MergeAppend surely need read no more than that many tuples from
307 * any one input. We also have to be prepared to look through a Result,
308 * since the planner might stick one atop MergeAppend for projection purposes.
310 * This is a bit of a kluge, but we don't have any more-abstract way of
311 * communicating between the two nodes; and it doesn't seem worth trying
312 * to invent one without some more examples of special communication needs.
314 * Note: it is the responsibility of nodeSort.c to react properly to
315 * changes of these parameters. If we ever do redesign this, it'd be a
316 * good idea to integrate this signaling with the parameter-change mechanism.
319 pass_down_bound(LimitState *node, PlanState *child_node)
321 if (IsA(child_node, SortState))
323 SortState *sortState = (SortState *) child_node;
324 int64 tuples_needed = node->count + node->offset;
326 /* negative test checks for overflow in sum */
327 if (node->noCount || tuples_needed < 0)
329 /* make sure flag gets reset if needed upon rescan */
330 sortState->bounded = false;
334 sortState->bounded = true;
335 sortState->bound = tuples_needed;
338 else if (IsA(child_node, MergeAppendState))
340 MergeAppendState *maState = (MergeAppendState *) child_node;
343 for (i = 0; i < maState->ms_nplans; i++)
344 pass_down_bound(node, maState->mergeplans[i]);
346 else if (IsA(child_node, ResultState))
349 * An extra consideration here is that if the Result is projecting a
350 * targetlist that contains any SRFs, we can't assume that every input
351 * tuple generates an output tuple, so a Sort underneath might need to
352 * return more than N tuples to satisfy LIMIT N. So we cannot use
355 * If Result supported qual checking, we'd have to punt on seeing a
356 * qual, too. Note that having a resconstantqual is not a
357 * showstopper: if that fails we're not getting any rows at all.
359 if (outerPlanState(child_node) &&
360 !expression_returns_set((Node *) child_node->plan->targetlist))
361 pass_down_bound(node, outerPlanState(child_node));
365 /* ----------------------------------------------------------------
368 * This initializes the limit node state structures and
369 * the node's subplan.
370 * ----------------------------------------------------------------
373 ExecInitLimit(Limit *node, EState *estate, int eflags)
375 LimitState *limitstate;
378 /* check for unsupported flags */
379 Assert(!(eflags & EXEC_FLAG_MARK));
382 * create state structure
384 limitstate = makeNode(LimitState);
385 limitstate->ps.plan = (Plan *) node;
386 limitstate->ps.state = estate;
388 limitstate->lstate = LIMIT_INITIAL;
391 * Miscellaneous initialization
393 * Limit nodes never call ExecQual or ExecProject, but they need an
394 * exprcontext anyway to evaluate the limit/offset parameters in.
396 ExecAssignExprContext(estate, &limitstate->ps);
399 * initialize child expressions
401 limitstate->limitOffset = ExecInitExpr((Expr *) node->limitOffset,
402 (PlanState *) limitstate);
403 limitstate->limitCount = ExecInitExpr((Expr *) node->limitCount,
404 (PlanState *) limitstate);
407 * Tuple table initialization (XXX not actually used...)
409 ExecInitResultTupleSlot(estate, &limitstate->ps);
412 * then initialize outer plan
414 outerPlan = outerPlan(node);
415 outerPlanState(limitstate) = ExecInitNode(outerPlan, estate, eflags);
418 * limit nodes do no projections, so initialize projection info for this
421 ExecAssignResultTypeFromTL(&limitstate->ps);
422 limitstate->ps.ps_ProjInfo = NULL;
427 /* ----------------------------------------------------------------
430 * This shuts down the subplan and frees resources allocated
432 * ----------------------------------------------------------------
435 ExecEndLimit(LimitState *node)
437 ExecFreeExprContext(&node->ps);
438 ExecEndNode(outerPlanState(node));
443 ExecReScanLimit(LimitState *node)
446 * Recompute limit/offset in case parameters changed, and reset the state
447 * machine. We must do this before rescanning our child node, in case
448 * it's a Sort that we are passing the parameters down to.
450 recompute_limits(node);
453 * if chgParam of subnode is not null then plan will be re-scanned by
454 * first ExecProcNode.
456 if (node->ps.lefttree->chgParam == NULL)
457 ExecReScan(node->ps.lefttree);