src/backend/executor/nodeLimit.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * nodeLimit.c
   4  *        Routines to handle limiting of query results where appropriate
   5  *
   6  * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $PostgreSQL: pgsql/src/backend/executor/nodeLimit.c,v 1.32 2007/11/15 21:14:34 momjian Exp $
  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
  27 static void recompute_limits(LimitState *node);
  28
  29
  30 /* ----------------------------------------------------------------
  31  *              ExecLimit
  32  *
  33  *              This is a very simple node which just performs LIMIT/OFFSET
  34  *              filtering on the stream of tuples returned by a subplan.
  35  * ----------------------------------------------------------------
  36  */
  37 TupleTableSlot *                                /* return: a tuple or NULL */
  38 ExecLimit(LimitState *node)
  39 {
  40         ScanDirection direction;
  41         TupleTableSlot *slot;
  42         PlanState  *outerPlan;
  43
  44         /*
  45          * get information from the node
  46          */
  47         direction = node->ps.state->es_direction;
  48         outerPlan = outerPlanState(node);
  49
  50         /*
  51          * The main logic is a simple state machine.
  52          */
  53         switch (node->lstate)
  54         {
  55                 case LIMIT_INITIAL:
  56
  57                         /*
  58                          * First call for this node, so compute limit/offset. (We can't do
  59                          * this any earlier, because parameters from upper nodes will not
  60                          * be set during ExecInitLimit.)  This also sets position = 0 and
  61                          * changes the state to LIMIT_RESCAN.
  62                          */
  63                         recompute_limits(node);
  64
  65                         /* FALL THRU */
  66
  67                 case LIMIT_RESCAN:
  68
  69                         /*
  70                          * If backwards scan, just return NULL without changing state.
  71                          */
  72                         if (!ScanDirectionIsForward(direction))
  73                                 return NULL;
  74
  75                         /*
  76                          * Check for empty window; if so, treat like empty subplan.
  77                          */
  78                         if (node->count <= 0 && !node->noCount)
  79                         {
  80                                 node->lstate = LIMIT_EMPTY;
  81                                 return NULL;
  82                         }
  83
  84                         /*
  85                          * Fetch rows from subplan until we reach position > offset.
  86                          */
  87                         for (;;)
  88                         {
  89                                 slot = ExecProcNode(outerPlan);
  90                                 if (TupIsNull(slot))
  91                                 {
  92                                         /*
  93                                          * The subplan returns too few tuples for us to produce
  94                                          * any output at all.
  95                                          */
  96                                         node->lstate = LIMIT_EMPTY;
  97                                         return NULL;
  98                                 }
  99                                 node->subSlot = slot;
 100                                 if (++node->position > node->offset)
 101                                         break;
 102                         }
 103
 104                         /*
 105                          * Okay, we have the first tuple of the window.
 106                          */
 107                         node->lstate = LIMIT_INWINDOW;
 108                         break;
 109
 110                 case LIMIT_EMPTY:
 111
 112                         /*
 113                          * The subplan is known to return no tuples (or not more than
 114                          * OFFSET tuples, in general).  So we return no tuples.
 115                          */
 116                         return NULL;
 117
 118                 case LIMIT_INWINDOW:
 119                         if (ScanDirectionIsForward(direction))
 120                         {
 121                                 /*
 122                                  * Forwards scan, so check for stepping off end of window. If
 123                                  * we are at the end of the window, return NULL without
 124                                  * advancing the subplan or the position variable; but change
 125                                  * the state machine state to record having done so.
 126                                  */
 127                                 if (!node->noCount &&
 128                                         node->position >= node->offset + node->count)
 129                                 {
 130                                         node->lstate = LIMIT_WINDOWEND;
 131                                         return NULL;
 132                                 }
 133
 134                                 /*
 135                                  * Get next tuple from subplan, if any.
 136                                  */
 137                                 slot = ExecProcNode(outerPlan);
 138                                 if (TupIsNull(slot))
 139                                 {
 140                                         node->lstate = LIMIT_SUBPLANEOF;
 141                                         return NULL;
 142                                 }
 143                                 node->subSlot = slot;
 144                                 node->position++;
 145                         }
 146                         else
 147                         {
 148                                 /*
 149                                  * Backwards scan, so check for stepping off start of window.
 150                                  * As above, change only state-machine status if so.
 151                                  */
 152                                 if (node->position <= node->offset + 1)
 153                                 {
 154                                         node->lstate = LIMIT_WINDOWSTART;
 155                                         return NULL;
 156                                 }
 157
 158                                 /*
 159                                  * Get previous tuple from subplan; there should be one!
 160                                  */
 161                                 slot = ExecProcNode(outerPlan);
 162                                 if (TupIsNull(slot))
 163                                         elog(ERROR, "LIMIT subplan failed to run backwards");
 164                                 node->subSlot = slot;
 165                                 node->position--;
 166                         }
 167                         break;
 168
 169                 case LIMIT_SUBPLANEOF:
 170                         if (ScanDirectionIsForward(direction))
 171                                 return NULL;
 172
 173                         /*
 174                          * Backing up from subplan EOF, so re-fetch previous tuple; there
 175                          * should be one!  Note previous tuple must be in window.
 176                          */
 177                         slot = ExecProcNode(outerPlan);
 178                         if (TupIsNull(slot))
 179                                 elog(ERROR, "LIMIT subplan failed to run backwards");
 180                         node->subSlot = slot;
 181                         node->lstate = LIMIT_INWINDOW;
 182                         /* position does not change 'cause we didn't advance it before */
 183                         break;
 184
 185                 case LIMIT_WINDOWEND:
 186                         if (ScanDirectionIsForward(direction))
 187                                 return NULL;
 188
 189                         /*
 190                          * Backing up from window end: simply re-return the last tuple
 191                          * fetched from the subplan.
 192                          */
 193                         slot = node->subSlot;
 194                         node->lstate = LIMIT_INWINDOW;
 195                         /* position does not change 'cause we didn't advance it before */
 196                         break;
 197
 198                 case LIMIT_WINDOWSTART:
 199                         if (!ScanDirectionIsForward(direction))
 200                                 return NULL;
 201
 202                         /*
 203                          * Advancing after having backed off window start: simply
 204                          * re-return the last tuple fetched from the subplan.
 205                          */
 206                         slot = node->subSlot;
 207                         node->lstate = LIMIT_INWINDOW;
 208                         /* position does not change 'cause we didn't change it before */
 209                         break;
 210
 211                 default:
 212                         elog(ERROR, "impossible LIMIT state: %d",
 213                                  (int) node->lstate);
 214                         slot = NULL;            /* keep compiler quiet */
 215                         break;
 216         }
 217
 218         /* Return the current tuple */
 219         Assert(!TupIsNull(slot));
 220
 221         return slot;
 222 }
 223
 224 /*
 225  * Evaluate the limit/offset expressions --- done at startup or rescan.
 226  *
 227  * This is also a handy place to reset the current-position state info.
 228  */
 229 static void
 230 recompute_limits(LimitState *node)
 231 {
 232         ExprContext *econtext = node->ps.ps_ExprContext;
 233         Datum           val;
 234         bool            isNull;
 235
 236         if (node->limitOffset)
 237         {
 238                 val = ExecEvalExprSwitchContext(node->limitOffset,
 239                                                                                 econtext,
 240                                                                                 &isNull,
 241                                                                                 NULL);
 242                 /* Interpret NULL offset as no offset */
 243                 if (isNull)
 244                         node->offset = 0;
 245                 else
 246                 {
 247                         node->offset = DatumGetInt64(val);
 248                         if (node->offset < 0)
 249                                 node->offset = 0;
 250                 }
 251         }
 252         else
 253         {
 254                 /* No OFFSET supplied */
 255                 node->offset = 0;
 256         }
 257
 258         if (node->limitCount)
 259         {
 260                 val = ExecEvalExprSwitchContext(node->limitCount,
 261                                                                                 econtext,
 262                                                                                 &isNull,
 263                                                                                 NULL);
 264                 /* Interpret NULL count as no count (LIMIT ALL) */
 265                 if (isNull)
 266                 {
 267                         node->count = 0;
 268                         node->noCount = true;
 269                 }
 270                 else
 271                 {
 272                         node->count = DatumGetInt64(val);
 273                         if (node->count < 0)
 274                                 node->count = 0;
 275                         node->noCount = false;
 276                 }
 277         }
 278         else
 279         {
 280                 /* No COUNT supplied */
 281                 node->count = 0;
 282                 node->noCount = true;
 283         }
 284
 285         /* Reset position to start-of-scan */
 286         node->position = 0;
 287         node->subSlot = NULL;
 288
 289         /* Set state-machine state */
 290         node->lstate = LIMIT_RESCAN;
 291
 292         /*
 293          * If we have a COUNT, and our input is a Sort node, notify it that it can
 294          * use bounded sort.
 295          *
 296          * This is a bit of a kluge, but we don't have any more-abstract way of
 297          * communicating between the two nodes; and it doesn't seem worth trying
 298          * to invent one without some more examples of special communication
 299          * needs.
 300          *
 301          * Note: it is the responsibility of nodeSort.c to react properly to
 302          * changes of these parameters.  If we ever do redesign this, it'd be a
 303          * good idea to integrate this signaling with the parameter-change
 304          * mechanism.
 305          */
 306         if (IsA(outerPlanState(node), SortState))
 307         {
 308                 SortState  *sortState = (SortState *) outerPlanState(node);
 309                 int64           tuples_needed = node->count + node->offset;
 310
 311                 /* negative test checks for overflow */
 312                 if (node->noCount || tuples_needed < 0)
 313                 {
 314                         /* make sure flag gets reset if needed upon rescan */
 315                         sortState->bounded = false;
 316                 }
 317                 else
 318                 {
 319                         sortState->bounded = true;
 320                         sortState->bound = tuples_needed;
 321                 }
 322         }
 323 }
 324
 325 /* ----------------------------------------------------------------
 326  *              ExecInitLimit
 327  *
 328  *              This initializes the limit node state structures and
 329  *              the node's subplan.
 330  * ----------------------------------------------------------------
 331  */
 332 LimitState *
 333 ExecInitLimit(Limit *node, EState *estate, int eflags)
 334 {
 335         LimitState *limitstate;
 336         Plan       *outerPlan;
 337
 338         /* check for unsupported flags */
 339         Assert(!(eflags & EXEC_FLAG_MARK));
 340
 341         /*
 342          * create state structure
 343          */
 344         limitstate = makeNode(LimitState);
 345         limitstate->ps.plan = (Plan *) node;
 346         limitstate->ps.state = estate;
 347
 348         limitstate->lstate = LIMIT_INITIAL;
 349
 350         /*
 351          * Miscellaneous initialization
 352          *
 353          * Limit nodes never call ExecQual or ExecProject, but they need an
 354          * exprcontext anyway to evaluate the limit/offset parameters in.
 355          */
 356         ExecAssignExprContext(estate, &limitstate->ps);
 357
 358         /*
 359          * initialize child expressions
 360          */
 361         limitstate->limitOffset = ExecInitExpr((Expr *) node->limitOffset,
 362                                                                                    (PlanState *) limitstate);
 363         limitstate->limitCount = ExecInitExpr((Expr *) node->limitCount,
 364                                                                                   (PlanState *) limitstate);
 365
 366 #define LIMIT_NSLOTS 1
 367
 368         /*
 369          * Tuple table initialization (XXX not actually used...)
 370          */
 371         ExecInitResultTupleSlot(estate, &limitstate->ps);
 372
 373         /*
 374          * then initialize outer plan
 375          */
 376         outerPlan = outerPlan(node);
 377         outerPlanState(limitstate) = ExecInitNode(outerPlan, estate, eflags);
 378
 379         /*
 380          * limit nodes do no projections, so initialize projection info for this
 381          * node appropriately
 382          */
 383         ExecAssignResultTypeFromTL(&limitstate->ps);
 384         limitstate->ps.ps_ProjInfo = NULL;
 385
 386         return limitstate;
 387 }
 388
 389 int
 390 ExecCountSlotsLimit(Limit *node)
 391 {
 392         return ExecCountSlotsNode(outerPlan(node)) +
 393                 ExecCountSlotsNode(innerPlan(node)) +
 394                 LIMIT_NSLOTS;
 395 }
 396
 397 /* ----------------------------------------------------------------
 398  *              ExecEndLimit
 399  *
 400  *              This shuts down the subplan and frees resources allocated
 401  *              to this node.
 402  * ----------------------------------------------------------------
 403  */
 404 void
 405 ExecEndLimit(LimitState *node)
 406 {
 407         ExecFreeExprContext(&node->ps);
 408         ExecEndNode(outerPlanState(node));
 409 }
 410
 411
 412 void
 413 ExecReScanLimit(LimitState *node, ExprContext *exprCtxt)
 414 {
 415         /*
 416          * Recompute limit/offset in case parameters changed, and reset the state
 417          * machine.  We must do this before rescanning our child node, in case
 418          * it's a Sort that we are passing the parameters down to.
 419          */
 420         recompute_limits(node);
 421
 422         /*
 423          * if chgParam of subnode is not null then plan will be re-scanned by
 424          * first ExecProcNode.
 425          */
 426         if (((PlanState *) node)->lefttree->chgParam == NULL)
 427                 ExecReScan(((PlanState *) node)->lefttree, exprCtxt);
 428 }