LCOV - code coverage report
Current view: top level - src/backend/executor - nodeLimit.c (source / functions) Hit Total Coverage
Test: PostgreSQL 17beta1 Lines: 150 172 87.2 %
Date: 2024-06-17 22:11:45 Functions: 6 6 100.0 %
Legend: Lines: hit not hit

          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       34958 : ExecLimit(PlanState *pstate)
      41             : {
      42       34958 :     LimitState *node = castNode(LimitState, pstate);
      43       34958 :     ExprContext *econtext = node->ps.ps_ExprContext;
      44             :     ScanDirection direction;
      45             :     TupleTableSlot *slot;
      46             :     PlanState  *outerPlan;
      47             : 
      48       34958 :     CHECK_FOR_INTERRUPTS();
      49             : 
      50             :     /*
      51             :      * get information from the node
      52             :      */
      53       34958 :     direction = node->ps.state->es_direction;
      54       34958 :     outerPlan = outerPlanState(node);
      55             : 
      56             :     /*
      57             :      * The main logic is a simple state machine.
      58             :      */
      59       34958 :     switch (node->lstate)
      60             :     {
      61        3258 :         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        3258 :             recompute_limits(node);
      70             : 
      71             :             /* FALL THRU */
      72             : 
      73        4188 :         case LIMIT_RESCAN:
      74             : 
      75             :             /*
      76             :              * If backwards scan, just return NULL without changing state.
      77             :              */
      78        4188 :             if (!ScanDirectionIsForward(direction))
      79           0 :                 return NULL;
      80             : 
      81             :             /*
      82             :              * Check for empty window; if so, treat like empty subplan.
      83             :              */
      84        4188 :             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      508808 :                 slot = ExecProcNode(outerPlan);
      96      508796 :                 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      508544 :                 if (node->limitOption == LIMIT_OPTION_WITH_TIES &&
     111          28 :                     node->position - node->offset == node->count - 1)
     112             :                 {
     113          12 :                     ExecCopySlot(node->last_slot, slot);
     114             :                 }
     115      508544 :                 node->subSlot = slot;
     116      508544 :                 if (++node->position > node->offset)
     117        3786 :                     break;
     118             :             }
     119             : 
     120             :             /*
     121             :              * Okay, we have the first tuple of the window.
     122             :              */
     123        3786 :             node->lstate = LIMIT_INWINDOW;
     124        3786 :             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       30534 :         case LIMIT_INWINDOW:
     135       30534 :             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       30444 :                 if (!node->noCount &&
     154       29940 :                     node->position - node->offset >= node->count)
     155             :                 {
     156        3312 :                     if (node->limitOption == LIMIT_OPTION_COUNT)
     157             :                     {
     158        3272 :                         node->lstate = LIMIT_WINDOWEND;
     159        3272 :                         return NULL;
     160             :                     }
     161             :                     else
     162             :                     {
     163          40 :                         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       27132 :                     slot = ExecProcNode(outerPlan);
     173       27126 :                     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       26958 :                     if (node->limitOption == LIMIT_OPTION_WITH_TIES &&
     185          28 :                         node->position - node->offset == node->count - 1)
     186             :                     {
     187          28 :                         ExecCopySlot(node->last_slot, slot);
     188             :                     }
     189       26958 :                     node->subSlot = slot;
     190       26958 :                     node->position++;
     191       26958 :                     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         216 :             if (ScanDirectionIsForward(direction))
     222             :             {
     223             :                 /*
     224             :                  * Advance the subplan until we find the first row with
     225             :                  * different ORDER BY pathkeys.
     226             :                  */
     227         216 :                 slot = ExecProcNode(outerPlan);
     228         216 :                 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         214 :                 econtext->ecxt_innertuple = slot;
     239         214 :                 econtext->ecxt_outertuple = node->last_slot;
     240         214 :                 if (ExecQualAndReset(node->eqfunction, econtext))
     241             :                 {
     242         176 :                     node->subSlot = slot;
     243         176 :                     node->position++;
     244             :                 }
     245             :                 else
     246             :                 {
     247          38 :                     node->lstate = LIMIT_WINDOWEND;
     248          38 :                     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         176 :             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       31040 :     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        4188 : recompute_limits(LimitState *node)
     354             : {
     355        4188 :     ExprContext *econtext = node->ps.ps_ExprContext;
     356             :     Datum       val;
     357             :     bool        isNull;
     358             : 
     359        4188 :     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        3888 :         node->offset = 0;
     380             :     }
     381             : 
     382        4188 :     if (node->limitCount)
     383             :     {
     384        4140 :         val = ExecEvalExprSwitchContext(node->limitCount,
     385             :                                         econtext,
     386             :                                         &isNull);
     387             :         /* Interpret NULL count as no count (LIMIT ALL) */
     388        4140 :         if (isNull)
     389             :         {
     390           6 :             node->count = 0;
     391           6 :             node->noCount = true;
     392             :         }
     393             :         else
     394             :         {
     395        4134 :             node->count = DatumGetInt64(val);
     396        4134 :             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        4134 :             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        4188 :     node->position = 0;
     412        4188 :     node->subSlot = NULL;
     413             : 
     414             :     /* Set state-machine state */
     415        4188 :     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        4188 :     ExecSetTupleBound(compute_tuples_needed(node), outerPlanState(node));
     424        4188 : }
     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        4188 : compute_tuples_needed(LimitState *node)
     432             : {
     433        4188 :     if ((node->noCount) || (node->limitOption == LIMIT_OPTION_WITH_TIES))
     434          82 :         return -1;
     435             :     /* Note: if this overflows, we'll return a negative value, which is OK */
     436        4106 :     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        4600 : 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        4600 :     limitstate = makeNode(LimitState);
     459        4600 :     limitstate->ps.plan = (Plan *) node;
     460        4600 :     limitstate->ps.state = estate;
     461        4600 :     limitstate->ps.ExecProcNode = ExecLimit;
     462             : 
     463        4600 :     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        4600 :     ExecAssignExprContext(estate, &limitstate->ps);
     472             : 
     473             :     /*
     474             :      * initialize outer plan
     475             :      */
     476        4600 :     outerPlan = outerPlan(node);
     477        4600 :     outerPlanState(limitstate) = ExecInitNode(outerPlan, estate, eflags);
     478             : 
     479             :     /*
     480             :      * initialize child expressions
     481             :      */
     482        4600 :     limitstate->limitOffset = ExecInitExpr((Expr *) node->limitOffset,
     483             :                                            (PlanState *) limitstate);
     484        4600 :     limitstate->limitCount = ExecInitExpr((Expr *) node->limitCount,
     485             :                                           (PlanState *) limitstate);
     486        4600 :     limitstate->limitOption = node->limitOption;
     487             : 
     488             :     /*
     489             :      * Initialize result type.
     490             :      */
     491        4600 :     ExecInitResultTypeTL(&limitstate->ps);
     492             : 
     493        4600 :     limitstate->ps.resultopsset = true;
     494        4600 :     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        4600 :     limitstate->ps.ps_ProjInfo = NULL;
     502             : 
     503             :     /*
     504             :      * Initialize the equality evaluation, to detect ties.
     505             :      */
     506        4600 :     if (node->limitOption == LIMIT_OPTION_WITH_TIES)
     507             :     {
     508             :         TupleDesc   desc;
     509             :         const TupleTableSlotOps *ops;
     510             : 
     511          30 :         desc = ExecGetResultType(outerPlanState(limitstate));
     512          30 :         ops = ExecGetResultSlotOps(outerPlanState(limitstate), NULL);
     513             : 
     514          30 :         limitstate->last_slot = ExecInitExtraTupleSlot(estate, desc, ops);
     515          30 :         limitstate->eqfunction = execTuplesMatchPrepare(desc,
     516             :                                                         node->uniqNumCols,
     517          30 :                                                         node->uniqColIdx,
     518          30 :                                                         node->uniqOperators,
     519          30 :                                                         node->uniqCollations,
     520             :                                                         &limitstate->ps);
     521             :     }
     522             : 
     523        4600 :     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        4540 : ExecEndLimit(LimitState *node)
     535             : {
     536        4540 :     ExecEndNode(outerPlanState(node));
     537        4540 : }
     538             : 
     539             : 
     540             : void
     541         930 : ExecReScanLimit(LimitState *node)
     542             : {
     543         930 :     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         930 :     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         930 :     if (outerPlan->chgParam == NULL)
     557         120 :         ExecReScan(outerPlan);
     558         930 : }

Generated by: LCOV version 1.14