LCOV - code coverage report
Current view: top level - src/backend/executor - nodeLimit.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13beta1 Lines: 148 172 86.0 %
Date: 2020-06-05 18:07:03 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-2020, 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       23472 : ExecLimit(PlanState *pstate)
      42             : {
      43       23472 :     LimitState *node = castNode(LimitState, pstate);
      44       23472 :     ExprContext *econtext = node->ps.ps_ExprContext;
      45             :     ScanDirection direction;
      46             :     TupleTableSlot *slot;
      47             :     PlanState  *outerPlan;
      48             : 
      49       23472 :     CHECK_FOR_INTERRUPTS();
      50             : 
      51             :     /*
      52             :      * get information from the node
      53             :      */
      54       23472 :     direction = node->ps.state->es_direction;
      55       23472 :     outerPlan = outerPlanState(node);
      56             : 
      57             :     /*
      58             :      * The main logic is a simple state machine.
      59             :      */
      60       23472 :     switch (node->lstate)
      61             :     {
      62        2746 :         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        2746 :             recompute_limits(node);
      71             : 
      72             :             /* FALL THRU */
      73             : 
      74        3234 :         case LIMIT_RESCAN:
      75             : 
      76             :             /*
      77             :              * If backwards scan, just return NULL without changing state.
      78             :              */
      79        3234 :             if (!ScanDirectionIsForward(direction))
      80           0 :                 return NULL;
      81             : 
      82             :             /*
      83             :              * Check for empty window; if so, treat like empty subplan.
      84             :              */
      85        3234 :             if (node->count <= 0 && !node->noCount)
      86             :             {
      87          92 :                 node->lstate = LIMIT_EMPTY;
      88          92 :                 return NULL;
      89             :             }
      90             : 
      91             :             /*
      92             :              * Fetch rows from subplan until we reach position > offset.
      93             :              */
      94             :             for (;;)
      95             :             {
      96      341748 :                 slot = ExecProcNode(outerPlan);
      97      341738 :                 if (TupIsNull(slot))
      98             :                 {
      99             :                     /*
     100             :                      * The subplan returns too few tuples for us to produce
     101             :                      * any output at all.
     102             :                      */
     103         184 :                     node->lstate = LIMIT_EMPTY;
     104         184 :                     return NULL;
     105             :                 }
     106             : 
     107             :                 /*
     108             :                  * Tuple at limit is needed for comparation in subsequent
     109             :                  * execution to detect ties.
     110             :                  */
     111      341554 :                 if (node->limitOption == LIMIT_OPTION_WITH_TIES &&
     112          16 :                     node->position - node->offset == node->count - 1)
     113             :                 {
     114           8 :                     ExecCopySlot(node->last_slot, slot);
     115             :                 }
     116      341554 :                 node->subSlot = slot;
     117      341554 :                 if (++node->position > node->offset)
     118        2948 :                     break;
     119             :             }
     120             : 
     121             :             /*
     122             :              * Okay, we have the first tuple of the window.
     123             :              */
     124        2948 :             node->lstate = LIMIT_INWINDOW;
     125        2948 :             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       20094 :         case LIMIT_INWINDOW:
     136       20094 :             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       20034 :                 if (!node->noCount &&
     155       19698 :                     node->position - node->offset >= node->count)
     156             :                 {
     157        2806 :                     if (node->limitOption == LIMIT_OPTION_COUNT)
     158             :                     {
     159        2782 :                         node->lstate = LIMIT_WINDOWEND;
     160        2782 :                         return NULL;
     161             :                     }
     162             :                     else
     163             :                     {
     164          24 :                         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       17228 :                     slot = ExecProcNode(outerPlan);
     174       17224 :                     if (TupIsNull(slot))
     175             :                     {
     176          68 :                         node->lstate = LIMIT_SUBPLANEOF;
     177          68 :                         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       17156 :                     if (node->limitOption == LIMIT_OPTION_WITH_TIES &&
     186          16 :                         node->position - node->offset == node->count - 1)
     187             :                     {
     188          16 :                         ExecCopySlot(node->last_slot, slot);
     189             :                     }
     190       17156 :                     node->subSlot = slot;
     191       17156 :                     node->position++;
     192       17156 :                     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          60 :                 if (node->position <= node->offset + 1)
     202             :                 {
     203          20 :                     node->lstate = LIMIT_WINDOWSTART;
     204          20 :                     return NULL;
     205             :                 }
     206             : 
     207             :                 /*
     208             :                  * Get previous tuple from subplan; there should be one!
     209             :                  */
     210          40 :                 slot = ExecProcNode(outerPlan);
     211          40 :                 if (TupIsNull(slot))
     212           0 :                     elog(ERROR, "LIMIT subplan failed to run backwards");
     213          40 :                 node->subSlot = slot;
     214          40 :                 node->position--;
     215          40 :                 break;
     216             :             }
     217             : 
     218             :             Assert(node->lstate == LIMIT_WINDOWEND_TIES);
     219             :             /* FALL THRU */
     220             : 
     221             :         case LIMIT_WINDOWEND_TIES:
     222         128 :             if (ScanDirectionIsForward(direction))
     223             :             {
     224             :                 /*
     225             :                  * Advance the subplan until we find the first row with
     226             :                  * different ORDER BY pathkeys.
     227             :                  */
     228         128 :                 slot = ExecProcNode(outerPlan);
     229         128 :                 if (TupIsNull(slot))
     230             :                 {
     231           0 :                     node->lstate = LIMIT_SUBPLANEOF;
     232           0 :                     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         128 :                 econtext->ecxt_innertuple = slot;
     240         128 :                 econtext->ecxt_outertuple = node->last_slot;
     241         128 :                 if (ExecQualAndReset(node->eqfunction, econtext))
     242             :                 {
     243         104 :                     node->subSlot = slot;
     244         104 :                     node->position++;
     245             :                 }
     246             :                 else
     247             :                 {
     248          24 :                     node->lstate = LIMIT_WINDOWEND;
     249          24 :                     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         104 :             break;
     276             : 
     277           8 :         case LIMIT_SUBPLANEOF:
     278           8 :             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           8 :             slot = ExecProcNode(outerPlan);
     286           8 :             if (TupIsNull(slot))
     287           0 :                 elog(ERROR, "LIMIT subplan failed to run backwards");
     288           8 :             node->subSlot = slot;
     289           8 :             node->lstate = LIMIT_INWINDOW;
     290             :             /* position does not change 'cause we didn't advance it before */
     291           8 :             break;
     292             : 
     293          16 :         case LIMIT_WINDOWEND:
     294          16 :             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          16 :             if (node->limitOption == LIMIT_OPTION_WITH_TIES)
     303             :             {
     304          12 :                 slot = ExecProcNode(outerPlan);
     305          12 :                 if (TupIsNull(slot))
     306           0 :                     elog(ERROR, "LIMIT subplan failed to run backwards");
     307          12 :                 node->subSlot = slot;
     308          12 :                 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           4 :                 slot = node->subSlot;
     317           4 :                 node->lstate = LIMIT_INWINDOW;
     318             :                 /* position does not change 'cause we didn't advance it before */
     319             :             }
     320          16 :             break;
     321             : 
     322          16 :         case LIMIT_WINDOWSTART:
     323          16 :             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          16 :             slot = node->subSlot;
     331          16 :             node->lstate = LIMIT_INWINDOW;
     332             :             /* position does not change 'cause we didn't change it before */
     333          16 :             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       20288 :     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        3234 : recompute_limits(LimitState *node)
     355             : {
     356        3234 :     ExprContext *econtext = node->ps.ps_ExprContext;
     357             :     Datum       val;
     358             :     bool        isNull;
     359             : 
     360        3234 :     if (node->limitOffset)
     361             :     {
     362         222 :         val = ExecEvalExprSwitchContext(node->limitOffset,
     363             :                                         econtext,
     364             :                                         &isNull);
     365             :         /* Interpret NULL offset as no offset */
     366         222 :         if (isNull)
     367           4 :             node->offset = 0;
     368             :         else
     369             :         {
     370         218 :             node->offset = DatumGetInt64(val);
     371         218 :             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        3012 :         node->offset = 0;
     381             :     }
     382             : 
     383        3234 :     if (node->limitCount)
     384             :     {
     385        3202 :         val = ExecEvalExprSwitchContext(node->limitCount,
     386             :                                         econtext,
     387             :                                         &isNull);
     388             :         /* Interpret NULL count as no count (LIMIT ALL) */
     389        3202 :         if (isNull)
     390             :         {
     391           4 :             node->count = 0;
     392           4 :             node->noCount = true;
     393             :         }
     394             :         else
     395             :         {
     396        3198 :             node->count = DatumGetInt64(val);
     397        3198 :             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        3198 :             node->noCount = false;
     402             :         }
     403             :     }
     404             :     else
     405             :     {
     406             :         /* No COUNT supplied */
     407          32 :         node->count = 0;
     408          32 :         node->noCount = true;
     409             :     }
     410             : 
     411             :     /* Reset position to start-of-scan */
     412        3234 :     node->position = 0;
     413        3234 :     node->subSlot = NULL;
     414             : 
     415             :     /* Set state-machine state */
     416        3234 :     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        3234 :     ExecSetTupleBound(compute_tuples_needed(node), outerPlanState(node));
     425        3234 : }
     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        3234 : compute_tuples_needed(LimitState *node)
     433             : {
     434        3234 :     if ((node->noCount) || (node->limitOption == LIMIT_OPTION_WITH_TIES))
     435          52 :         return -1;
     436             :     /* Note: if this overflows, we'll return a negative value, which is OK */
     437        3182 :     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        3374 : 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        3374 :     limitstate = makeNode(LimitState);
     460        3374 :     limitstate->ps.plan = (Plan *) node;
     461        3374 :     limitstate->ps.state = estate;
     462        3374 :     limitstate->ps.ExecProcNode = ExecLimit;
     463             : 
     464        3374 :     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        3374 :     ExecAssignExprContext(estate, &limitstate->ps);
     473             : 
     474             :     /*
     475             :      * initialize outer plan
     476             :      */
     477        3374 :     outerPlan = outerPlan(node);
     478        3374 :     outerPlanState(limitstate) = ExecInitNode(outerPlan, estate, eflags);
     479             : 
     480             :     /*
     481             :      * initialize child expressions
     482             :      */
     483        3374 :     limitstate->limitOffset = ExecInitExpr((Expr *) node->limitOffset,
     484             :                                            (PlanState *) limitstate);
     485        3374 :     limitstate->limitCount = ExecInitExpr((Expr *) node->limitCount,
     486             :                                           (PlanState *) limitstate);
     487        3374 :     limitstate->limitOption = node->limitOption;
     488             : 
     489             :     /*
     490             :      * Initialize result type.
     491             :      */
     492        3374 :     ExecInitResultTypeTL(&limitstate->ps);
     493             : 
     494        3374 :     limitstate->ps.resultopsset = true;
     495        3374 :     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        3374 :     limitstate->ps.ps_ProjInfo = NULL;
     503             : 
     504             :     /*
     505             :      * Initialize the equality evaluation, to detect ties.
     506             :      */
     507        3374 :     if (node->limitOption == LIMIT_OPTION_WITH_TIES)
     508             :     {
     509             :         TupleDesc   desc;
     510             :         const TupleTableSlotOps *ops;
     511             : 
     512          16 :         desc = ExecGetResultType(outerPlanState(limitstate));
     513          16 :         ops = ExecGetResultSlotOps(outerPlanState(limitstate), NULL);
     514             : 
     515          16 :         limitstate->last_slot = ExecInitExtraTupleSlot(estate, desc, ops);
     516          16 :         limitstate->eqfunction = execTuplesMatchPrepare(desc,
     517             :                                                         node->uniqNumCols,
     518          16 :                                                         node->uniqColIdx,
     519          16 :                                                         node->uniqOperators,
     520          16 :                                                         node->uniqCollations,
     521             :                                                         &limitstate->ps);
     522             :     }
     523             : 
     524        3374 :     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        3332 : ExecEndLimit(LimitState *node)
     536             : {
     537        3332 :     ExecFreeExprContext(&node->ps);
     538        3332 :     ExecEndNode(outerPlanState(node));
     539        3332 : }
     540             : 
     541             : 
     542             : void
     543         488 : ExecReScanLimit(LimitState *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         488 :     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         488 :     if (node->ps.lefttree->chgParam == NULL)
     557          80 :         ExecReScan(node->ps.lefttree);
     558         488 : }

Generated by: LCOV version 1.13