LCOV - code coverage report
Current view: top level - src/backend/executor - nodeLimit.c (source / functions) Hit Total Coverage
Test: PostgreSQL 16beta1 Lines: 151 173 87.3 %
Date: 2023-06-06 08:12:15 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-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 */
      41       35816 : ExecLimit(PlanState *pstate)
      42             : {
      43       35816 :     LimitState *node = castNode(LimitState, pstate);
      44       35816 :     ExprContext *econtext = node->ps.ps_ExprContext;
      45             :     ScanDirection direction;
      46             :     TupleTableSlot *slot;
      47             :     PlanState  *outerPlan;
      48             : 
      49       35816 :     CHECK_FOR_INTERRUPTS();
      50             : 
      51             :     /*
      52             :      * get information from the node
      53             :      */
      54       35816 :     direction = node->ps.state->es_direction;
      55       35816 :     outerPlan = outerPlanState(node);
      56             : 
      57             :     /*
      58             :      * The main logic is a simple state machine.
      59             :      */
      60       35816 :     switch (node->lstate)
      61             :     {
      62        3752 :         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             :              */
      70        3752 :             recompute_limits(node);
      71             : 
      72             :             /* FALL THRU */
      73             : 
      74        4652 :         case LIMIT_RESCAN:
      75             : 
      76             :             /*
      77             :              * If backwards scan, just return NULL without changing state.
      78             :              */
      79        4652 :             if (!ScanDirectionIsForward(direction))
      80           0 :                 return NULL;
      81             : 
      82             :             /*
      83             :              * Check for empty window; if so, treat like empty subplan.
      84             :              */
      85        4652 :             if (node->count <= 0 && !node->noCount)
      86             :             {
      87         138 :                 node->lstate = LIMIT_EMPTY;
      88         138 :                 return NULL;
      89             :             }
      90             : 
      91             :             /*
      92             :              * Fetch rows from subplan until we reach position > offset.
      93             :              */
      94             :             for (;;)
      95             :             {
      96      509272 :                 slot = ExecProcNode(outerPlan);
      97      509258 :                 if (TupIsNull(slot))
      98             :                 {
      99             :                     /*
     100             :                      * The subplan returns too few tuples for us to produce
     101             :                      * any output at all.
     102             :                      */
     103         250 :                     node->lstate = LIMIT_EMPTY;
     104         250 :                     return NULL;
     105             :                 }
     106             : 
     107             :                 /*
     108             :                  * Tuple at limit is needed for comparison in subsequent
     109             :                  * execution to detect ties.
     110             :                  */
     111      509008 :                 if (node->limitOption == LIMIT_OPTION_WITH_TIES &&
     112          26 :                     node->position - node->offset == node->count - 1)
     113             :                 {
     114          12 :                     ExecCopySlot(node->last_slot, slot);
     115             :                 }
     116      509008 :                 node->subSlot = slot;
     117      509008 :                 if (++node->position > node->offset)
     118        4250 :                     break;
     119             :             }
     120             : 
     121             :             /*
     122             :              * Okay, we have the first tuple of the window.
     123             :              */
     124        4250 :             node->lstate = LIMIT_INWINDOW;
     125        4250 :             break;
     126             : 
     127           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             : 
     135       30932 :         case LIMIT_INWINDOW:
     136       30932 :             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             :                  */
     154       30842 :                 if (!node->noCount &&
     155       30338 :                     node->position - node->offset >= node->count)
     156             :                 {
     157        3788 :                     if (node->limitOption == LIMIT_OPTION_COUNT)
     158             :                     {
     159        3750 :                         node->lstate = LIMIT_WINDOWEND;
     160        3750 :                         return NULL;
     161             :                     }
     162             :                     else
     163             :                     {
     164          38 :                         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       27054 :                     slot = ExecProcNode(outerPlan);
     174       27048 :                     if (TupIsNull(slot))
     175             :                     {
     176         164 :                         node->lstate = LIMIT_SUBPLANEOF;
     177         164 :                         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       26884 :                     if (node->limitOption == LIMIT_OPTION_WITH_TIES &&
     186          26 :                         node->position - node->offset == node->count - 1)
     187             :                     {
     188          26 :                         ExecCopySlot(node->last_slot, slot);
     189             :                     }
     190       26884 :                     node->subSlot = slot;
     191       26884 :                     node->position++;
     192       26884 :                     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          90 :                 if (node->position <= node->offset + 1)
     202             :                 {
     203          30 :                     node->lstate = LIMIT_WINDOWSTART;
     204          30 :                     return NULL;
     205             :                 }
     206             : 
     207             :                 /*
     208             :                  * Get previous tuple from subplan; there should be one!
     209             :                  */
     210          60 :                 slot = ExecProcNode(outerPlan);
     211          60 :                 if (TupIsNull(slot))
     212           0 :                     elog(ERROR, "LIMIT subplan failed to run backwards");
     213          60 :                 node->subSlot = slot;
     214          60 :                 node->position--;
     215          60 :                 break;
     216             :             }
     217             : 
     218             :             Assert(node->lstate == LIMIT_WINDOWEND_TIES);
     219             :             /* FALL THRU */
     220             : 
     221             :         case LIMIT_WINDOWEND_TIES:
     222         210 :             if (ScanDirectionIsForward(direction))
     223             :             {
     224             :                 /*
     225             :                  * Advance the subplan until we find the first row with
     226             :                  * different ORDER BY pathkeys.
     227             :                  */
     228         210 :                 slot = ExecProcNode(outerPlan);
     229         210 :                 if (TupIsNull(slot))
     230             :                 {
     231           2 :                     node->lstate = LIMIT_SUBPLANEOF;
     232           2 :                     return NULL;
     233             :                 }
     234             : 
     235             :                 /*
     236             :                  * Test if the new tuple and the last tuple match. If so we
     237             :                  * return the tuple.
     238             :                  */
     239         208 :                 econtext->ecxt_innertuple = slot;
     240         208 :                 econtext->ecxt_outertuple = node->last_slot;
     241         208 :                 if (ExecQualAndReset(node->eqfunction, econtext))
     242             :                 {
     243         172 :                     node->subSlot = slot;
     244         172 :                     node->position++;
     245             :                 }
     246             :                 else
     247             :                 {
     248          36 :                     node->lstate = LIMIT_WINDOWEND;
     249          36 :                     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             :                  */
     258           0 :                 if (node->position <= node->offset + 1)
     259             :                 {
     260           0 :                     node->lstate = LIMIT_WINDOWSTART;
     261           0 :                     return NULL;
     262             :                 }
     263             : 
     264             :                 /*
     265             :                  * Get previous tuple from subplan; there should be one! And
     266             :                  * change state-machine status.
     267             :                  */
     268           0 :                 slot = ExecProcNode(outerPlan);
     269           0 :                 if (TupIsNull(slot))
     270           0 :                     elog(ERROR, "LIMIT subplan failed to run backwards");
     271           0 :                 node->subSlot = slot;
     272           0 :                 node->position--;
     273           0 :                 node->lstate = LIMIT_INWINDOW;
     274             :             }
     275         172 :             break;
     276             : 
     277          12 :         case LIMIT_SUBPLANEOF:
     278          12 :             if (ScanDirectionIsForward(direction))
     279           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             :              */
     285          12 :             slot = ExecProcNode(outerPlan);
     286          12 :             if (TupIsNull(slot))
     287           0 :                 elog(ERROR, "LIMIT subplan failed to run backwards");
     288          12 :             node->subSlot = slot;
     289          12 :             node->lstate = LIMIT_INWINDOW;
     290             :             /* position does not change 'cause we didn't advance it before */
     291          12 :             break;
     292             : 
     293          24 :         case LIMIT_WINDOWEND:
     294          24 :             if (ScanDirectionIsForward(direction))
     295           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             :              */
     302          24 :             if (node->limitOption == LIMIT_OPTION_WITH_TIES)
     303             :             {
     304          18 :                 slot = ExecProcNode(outerPlan);
     305          18 :                 if (TupIsNull(slot))
     306           0 :                     elog(ERROR, "LIMIT subplan failed to run backwards");
     307          18 :                 node->subSlot = slot;
     308          18 :                 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           6 :                 slot = node->subSlot;
     317           6 :                 node->lstate = LIMIT_INWINDOW;
     318             :                 /* position does not change 'cause we didn't advance it before */
     319             :             }
     320          24 :             break;
     321             : 
     322          24 :         case LIMIT_WINDOWSTART:
     323          24 :             if (!ScanDirectionIsForward(direction))
     324           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             :              */
     330          24 :             slot = node->subSlot;
     331          24 :             node->lstate = LIMIT_INWINDOW;
     332             :             /* position does not change 'cause we didn't change it before */
     333          24 :             break;
     334             : 
     335           0 :         default:
     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 */
     343             :     Assert(!TupIsNull(slot));
     344             : 
     345       31426 :     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
     354        4652 : recompute_limits(LimitState *node)
     355             : {
     356        4652 :     ExprContext *econtext = node->ps.ps_ExprContext;
     357             :     Datum       val;
     358             :     bool        isNull;
     359             : 
     360        4652 :     if (node->limitOffset)
     361             :     {
     362         300 :         val = ExecEvalExprSwitchContext(node->limitOffset,
     363             :                                         econtext,
     364             :                                         &isNull);
     365             :         /* Interpret NULL offset as no offset */
     366         300 :         if (isNull)
     367           6 :             node->offset = 0;
     368             :         else
     369             :         {
     370         294 :             node->offset = DatumGetInt64(val);
     371         294 :             if (node->offset < 0)
     372           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 */
     380        4352 :         node->offset = 0;
     381             :     }
     382             : 
     383        4652 :     if (node->limitCount)
     384             :     {
     385        4604 :         val = ExecEvalExprSwitchContext(node->limitCount,
     386             :                                         econtext,
     387             :                                         &isNull);
     388             :         /* Interpret NULL count as no count (LIMIT ALL) */
     389        4604 :         if (isNull)
     390             :         {
     391           6 :             node->count = 0;
     392           6 :             node->noCount = true;
     393             :         }
     394             :         else
     395             :         {
     396        4598 :             node->count = DatumGetInt64(val);
     397        4598 :             if (node->count < 0)
     398           0 :                 ereport(ERROR,
     399             :                         (errcode(ERRCODE_INVALID_ROW_COUNT_IN_LIMIT_CLAUSE),
     400             :                          errmsg("LIMIT must not be negative")));
     401        4598 :             node->noCount = false;
     402             :         }
     403             :     }
     404             :     else
     405             :     {
     406             :         /* No COUNT supplied */
     407          48 :         node->count = 0;
     408          48 :         node->noCount = true;
     409             :     }
     410             : 
     411             :     /* Reset position to start-of-scan */
     412        4652 :     node->position = 0;
     413        4652 :     node->subSlot = NULL;
     414             : 
     415             :     /* Set state-machine state */
     416        4652 :     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             :      */
     424        4652 :     ExecSetTupleBound(compute_tuples_needed(node), outerPlanState(node));
     425        4652 : }
     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
     432        4652 : compute_tuples_needed(LimitState *node)
     433             : {
     434        4652 :     if ((node->noCount) || (node->limitOption == LIMIT_OPTION_WITH_TIES))
     435          80 :         return -1;
     436             :     /* Note: if this overflows, we'll return a negative value, which is OK */
     437        4572 :     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 *
     448        4976 : ExecInitLimit(Limit *node, EState *estate, int eflags)
     449             : {
     450             :     LimitState *limitstate;
     451             :     Plan       *outerPlan;
     452             : 
     453             :     /* check for unsupported flags */
     454             :     Assert(!(eflags & EXEC_FLAG_MARK));
     455             : 
     456             :     /*
     457             :      * create state structure
     458             :      */
     459        4976 :     limitstate = makeNode(LimitState);
     460        4976 :     limitstate->ps.plan = (Plan *) node;
     461        4976 :     limitstate->ps.state = estate;
     462        4976 :     limitstate->ps.ExecProcNode = ExecLimit;
     463             : 
     464        4976 :     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             :      */
     472        4976 :     ExecAssignExprContext(estate, &limitstate->ps);
     473             : 
     474             :     /*
     475             :      * initialize outer plan
     476             :      */
     477        4976 :     outerPlan = outerPlan(node);
     478        4976 :     outerPlanState(limitstate) = ExecInitNode(outerPlan, estate, eflags);
     479             : 
     480             :     /*
     481             :      * initialize child expressions
     482             :      */
     483        4976 :     limitstate->limitOffset = ExecInitExpr((Expr *) node->limitOffset,
     484             :                                            (PlanState *) limitstate);
     485        4976 :     limitstate->limitCount = ExecInitExpr((Expr *) node->limitCount,
     486             :                                           (PlanState *) limitstate);
     487        4976 :     limitstate->limitOption = node->limitOption;
     488             : 
     489             :     /*
     490             :      * Initialize result type.
     491             :      */
     492        4976 :     ExecInitResultTypeTL(&limitstate->ps);
     493             : 
     494        4976 :     limitstate->ps.resultopsset = true;
     495        4976 :     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             :      */
     502        4976 :     limitstate->ps.ps_ProjInfo = NULL;
     503             : 
     504             :     /*
     505             :      * Initialize the equality evaluation, to detect ties.
     506             :      */
     507        4976 :     if (node->limitOption == LIMIT_OPTION_WITH_TIES)
     508             :     {
     509             :         TupleDesc   desc;
     510             :         const TupleTableSlotOps *ops;
     511             : 
     512          26 :         desc = ExecGetResultType(outerPlanState(limitstate));
     513          26 :         ops = ExecGetResultSlotOps(outerPlanState(limitstate), NULL);
     514             : 
     515          26 :         limitstate->last_slot = ExecInitExtraTupleSlot(estate, desc, ops);
     516          26 :         limitstate->eqfunction = execTuplesMatchPrepare(desc,
     517             :                                                         node->uniqNumCols,
     518          26 :                                                         node->uniqColIdx,
     519          26 :                                                         node->uniqOperators,
     520          26 :                                                         node->uniqCollations,
     521             :                                                         &limitstate->ps);
     522             :     }
     523             : 
     524        4976 :     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        4914 : ExecEndLimit(LimitState *node)
     536             : {
     537        4914 :     ExecFreeExprContext(&node->ps);
     538        4914 :     ExecEndNode(outerPlanState(node));
     539        4914 : }
     540             : 
     541             : 
     542             : void
     543         900 : ExecReScanLimit(LimitState *node)
     544             : {
     545         900 :     PlanState  *outerPlan = outerPlanState(node);
     546             : 
     547             :     /*
     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             :      */
     552         900 :     recompute_limits(node);
     553             : 
     554             :     /*
     555             :      * if chgParam of subnode is not null then plan will be re-scanned by
     556             :      * first ExecProcNode.
     557             :      */
     558         900 :     if (outerPlan->chgParam == NULL)
     559         120 :         ExecReScan(outerPlan);
     560         900 : }

Generated by: LCOV version 1.14