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-2009, 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.40 2009/09/27 21:10:53 tgl 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                                 ereport(ERROR,
 250                                  (errcode(ERRCODE_INVALID_ROW_COUNT_IN_RESULT_OFFSET_CLAUSE),
 251                                   errmsg("OFFSET must not be negative")));
 252                 }
 253         }
 254         else
 255         {
 256                 /* No OFFSET supplied */
 257                 node->offset = 0;
 258         }
 259
 260         if (node->limitCount)
 261         {
 262                 val = ExecEvalExprSwitchContext(node->limitCount,
 263                                                                                 econtext,
 264                                                                                 &isNull,
 265                                                                                 NULL);
 266                 /* Interpret NULL count as no count (LIMIT ALL) */
 267                 if (isNull)
 268                 {
 269                         node->count = 0;
 270                         node->noCount = true;
 271                 }
 272                 else
 273                 {
 274                         node->count = DatumGetInt64(val);
 275                         if (node->count < 0)
 276                                 ereport(ERROR,
 277                                                 (errcode(ERRCODE_INVALID_ROW_COUNT_IN_LIMIT_CLAUSE),
 278                                                  errmsg("LIMIT must not be negative")));
 279                         node->noCount = false;
 280                 }
 281         }
 282         else
 283         {
 284                 /* No COUNT supplied */
 285                 node->count = 0;
 286                 node->noCount = true;
 287         }
 288
 289         /* Reset position to start-of-scan */
 290         node->position = 0;
 291         node->subSlot = NULL;
 292
 293         /* Set state-machine state */
 294         node->lstate = LIMIT_RESCAN;
 295
 296         /*
 297          * If we have a COUNT, and our input is a Sort node, notify it that it can
 298          * use bounded sort.
 299          *
 300          * This is a bit of a kluge, but we don't have any more-abstract way of
 301          * communicating between the two nodes; and it doesn't seem worth trying
 302          * to invent one without some more examples of special communication
 303          * needs.
 304          *
 305          * Note: it is the responsibility of nodeSort.c to react properly to
 306          * changes of these parameters.  If we ever do redesign this, it'd be a
 307          * good idea to integrate this signaling with the parameter-change
 308          * mechanism.
 309          */
 310         if (IsA(outerPlanState(node), SortState))
 311         {
 312                 SortState  *sortState = (SortState *) outerPlanState(node);
 313                 int64           tuples_needed = node->count + node->offset;
 314
 315                 /* negative test checks for overflow */
 316                 if (node->noCount || tuples_needed < 0)
 317                 {
 318                         /* make sure flag gets reset if needed upon rescan */
 319                         sortState->bounded = false;
 320                 }
 321                 else
 322                 {
 323                         sortState->bounded = true;
 324                         sortState->bound = tuples_needed;
 325                 }
 326         }
 327 }
 328
 329 /* ----------------------------------------------------------------
 330  *              ExecInitLimit
 331  *
 332  *              This initializes the limit node state structures and
 333  *              the node's subplan.
 334  * ----------------------------------------------------------------
 335  */
 336 LimitState *
 337 ExecInitLimit(Limit *node, EState *estate, int eflags)
 338 {
 339         LimitState *limitstate;
 340         Plan       *outerPlan;
 341
 342         /* check for unsupported flags */
 343         Assert(!(eflags & EXEC_FLAG_MARK));
 344
 345         /*
 346          * create state structure
 347          */
 348         limitstate = makeNode(LimitState);
 349         limitstate->ps.plan = (Plan *) node;
 350         limitstate->ps.state = estate;
 351
 352         limitstate->lstate = LIMIT_INITIAL;
 353
 354         /*
 355          * Miscellaneous initialization
 356          *
 357          * Limit nodes never call ExecQual or ExecProject, but they need an
 358          * exprcontext anyway to evaluate the limit/offset parameters in.
 359          */
 360         ExecAssignExprContext(estate, &limitstate->ps);
 361
 362         /*
 363          * initialize child expressions
 364          */
 365         limitstate->limitOffset = ExecInitExpr((Expr *) node->limitOffset,
 366                                                                                    (PlanState *) limitstate);
 367         limitstate->limitCount = ExecInitExpr((Expr *) node->limitCount,
 368                                                                                   (PlanState *) limitstate);
 369
 370         /*
 371          * Tuple table initialization (XXX not actually used...)
 372          */
 373         ExecInitResultTupleSlot(estate, &limitstate->ps);
 374
 375         /*
 376          * then initialize outer plan
 377          */
 378         outerPlan = outerPlan(node);
 379         outerPlanState(limitstate) = ExecInitNode(outerPlan, estate, eflags);
 380
 381         /*
 382          * limit nodes do no projections, so initialize projection info for this
 383          * node appropriately
 384          */
 385         ExecAssignResultTypeFromTL(&limitstate->ps);
 386         limitstate->ps.ps_ProjInfo = NULL;
 387
 388         return limitstate;
 389 }
 390
 391 /* ----------------------------------------------------------------
 392  *              ExecEndLimit
 393  *
 394  *              This shuts down the subplan and frees resources allocated
 395  *              to this node.
 396  * ----------------------------------------------------------------
 397  */
 398 void
 399 ExecEndLimit(LimitState *node)
 400 {
 401         ExecFreeExprContext(&node->ps);
 402         ExecEndNode(outerPlanState(node));
 403 }
 404
 405
 406 void
 407 ExecReScanLimit(LimitState *node, ExprContext *exprCtxt)
 408 {
 409         /*
 410          * Recompute limit/offset in case parameters changed, and reset the state
 411          * machine.  We must do this before rescanning our child node, in case
 412          * it's a Sort that we are passing the parameters down to.
 413          */
 414         recompute_limits(node);
 415
 416         /*
 417          * if chgParam of subnode is not null then plan will be re-scanned by
 418          * first ExecProcNode.
 419          */
 420         if (((PlanState *) node)->lefttree->chgParam == NULL)
 421                 ExecReScan(((PlanState *) node)->lefttree, exprCtxt);
 422 }