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