src/window.c

   1 /*
   2 ** 2018 May 08
   3 **
   4 ** The author disclaims copyright to this source code.  In place of
   5 ** a legal notice, here is a blessing:
   6 **
   7 **    May you do good and not evil.
   8 **    May you find forgiveness for yourself and forgive others.
   9 **    May you share freely, never taking more than you give.
  10 **
  11 *************************************************************************
  12 */
  13 #include "sqliteInt.h"
  14
  15 #ifndef SQLITE_OMIT_WINDOWFUNC
  16
  17 /*
  18 ** SELECT REWRITING
  19 **
  20 **   Any SELECT statement that contains one or more window functions in
  21 **   either the select list or ORDER BY clause (the only two places window
  22 **   functions may be used) is transformed by function sqlite3WindowRewrite()
  23 **   in order to support window function processing. For example, with the
  24 **   schema:
  25 **
  26 **     CREATE TABLE t1(a, b, c, d, e, f, g);
  27 **
  28 **   the statement:
  29 **
  30 **     SELECT a+1, max(b) OVER (PARTITION BY c ORDER BY d) FROM t1 ORDER BY e;
  31 **
  32 **   is transformed to:
  33 **
  34 **     SELECT a+1, max(b) OVER (PARTITION BY c ORDER BY d) FROM (
  35 **         SELECT a, e, c, d, b FROM t1 ORDER BY c, d
  36 **     ) ORDER BY e;
  37 **
  38 **   The flattening optimization is disabled when processing this transformed
  39 **   SELECT statement. This allows the implementation of the window function
  40 **   (in this case max()) to process rows sorted in order of (c, d), which
  41 **   makes things easier for obvious reasons. More generally:
  42 **
  43 **     * FROM, WHERE, GROUP BY and HAVING clauses are all moved to
  44 **       the sub-query.
  45 **
  46 **     * ORDER BY, LIMIT and OFFSET remain part of the parent query.
  47 **
  48 **     * Terminals from each of the expression trees that make up the
  49 **       select-list and ORDER BY expressions in the parent query are
  50 **       selected by the sub-query. For the purposes of the transformation,
  51 **       terminals are column references and aggregate functions.
  52 **
  53 **   If there is more than one window function in the SELECT that uses
  54 **   the same window declaration (the OVER bit), then a single scan may
  55 **   be used to process more than one window function. For example:
  56 **
  57 **     SELECT max(b) OVER (PARTITION BY c ORDER BY d),
  58 **            min(e) OVER (PARTITION BY c ORDER BY d)
  59 **     FROM t1;
  60 **
  61 **   is transformed in the same way as the example above. However:
  62 **
  63 **     SELECT max(b) OVER (PARTITION BY c ORDER BY d),
  64 **            min(e) OVER (PARTITION BY a ORDER BY b)
  65 **     FROM t1;
  66 **
  67 **   Must be transformed to:
  68 **
  69 **     SELECT max(b) OVER (PARTITION BY c ORDER BY d) FROM (
  70 **         SELECT e, min(e) OVER (PARTITION BY a ORDER BY b), c, d, b FROM
  71 **           SELECT a, e, c, d, b FROM t1 ORDER BY a, b
  72 **         ) ORDER BY c, d
  73 **     ) ORDER BY e;
  74 **
  75 **   so that both min() and max() may process rows in the order defined by
  76 **   their respective window declarations.
  77 **
  78 ** INTERFACE WITH SELECT.C
  79 **
  80 **   When processing the rewritten SELECT statement, code in select.c calls
  81 **   sqlite3WhereBegin() to begin iterating through the results of the
  82 **   sub-query, which is always implemented as a co-routine. It then calls
  83 **   sqlite3WindowCodeStep() to process rows and finish the scan by calling
  84 **   sqlite3WhereEnd().
  85 **
  86 **   sqlite3WindowCodeStep() generates VM code so that, for each row returned
  87 **   by the sub-query a sub-routine (OP_Gosub) coded by select.c is invoked.
  88 **   When the sub-routine is invoked:
  89 **
  90 **     * The results of all window-functions for the row are stored
  91 **       in the associated Window.regResult registers.
  92 **
  93 **     * The required terminal values are stored in the current row of
  94 **       temp table Window.iEphCsr.
  95 **
  96 **   In some cases, depending on the window frame and the specific window
  97 **   functions invoked, sqlite3WindowCodeStep() caches each entire partition
  98 **   in a temp table before returning any rows. In other cases it does not.
  99 **   This detail is encapsulated within this file, the code generated by
 100 **   select.c is the same in either case.
 101 **
 102 ** BUILT-IN WINDOW FUNCTIONS
 103 **
 104 **   This implementation features the following built-in window functions:
 105 **
 106 **     row_number()
 107 **     rank()
 108 **     dense_rank()
 109 **     percent_rank()
 110 **     cume_dist()
 111 **     ntile(N)
 112 **     lead(expr [, offset [, default]])
 113 **     lag(expr [, offset [, default]])
 114 **     first_value(expr)
 115 **     last_value(expr)
 116 **     nth_value(expr, N)
 117 **
 118 **   These are the same built-in window functions supported by Postgres.
 119 **   Although the behaviour of aggregate window functions (functions that
 120 **   can be used as either aggregates or window funtions) allows them to
 121 **   be implemented using an API, built-in window functions are much more
 122 **   esoteric. Additionally, some window functions (e.g. nth_value())
 123 **   may only be implemented by caching the entire partition in memory.
 124 **   As such, some built-in window functions use the same API as aggregate
 125 **   window functions and some are implemented directly using VDBE
 126 **   instructions. Additionally, for those functions that use the API, the
 127 **   window frame is sometimes modified before the SELECT statement is
 128 **   rewritten. For example, regardless of the specified window frame, the
 129 **   row_number() function always uses:
 130 **
 131 **     ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
 132 **
 133 **   See sqlite3WindowUpdate() for details.
 134 **
 135 **   As well as some of the built-in window functions, aggregate window
 136 **   functions min() and max() are implemented using VDBE instructions if
 137 **   the start of the window frame is declared as anything other than
 138 **   UNBOUNDED PRECEDING.
 139 */
 140
 141 /*
 142 ** Implementation of built-in window function row_number(). Assumes that the
 143 ** window frame has been coerced to:
 144 **
 145 **   ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
 146 */
 147 static void row_numberStepFunc(
 148   sqlite3_context *pCtx,
 149   int nArg,
 150   sqlite3_value **apArg
 151 ){
 152   i64 *p = (i64*)sqlite3_aggregate_context(pCtx, sizeof(*p));
 153   if( p ) (*p)++;
 154   UNUSED_PARAMETER(nArg);
 155   UNUSED_PARAMETER(apArg);
 156 }
 157 static void row_numberValueFunc(sqlite3_context *pCtx){
 158   i64 *p = (i64*)sqlite3_aggregate_context(pCtx, sizeof(*p));
 159   sqlite3_result_int64(pCtx, (p ? *p : 0));
 160 }
 161
 162 /*
 163 ** Context object type used by rank(), dense_rank(), percent_rank() and
 164 ** cume_dist().
 165 */
 166 struct CallCount {
 167   i64 nValue;
 168   i64 nStep;
 169   i64 nTotal;
 170 };
 171
 172 /*
 173 ** Implementation of built-in window function dense_rank(). Assumes that
 174 ** the window frame has been set to:
 175 **
 176 **   RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
 177 */
 178 static void dense_rankStepFunc(
 179   sqlite3_context *pCtx,
 180   int nArg,
 181   sqlite3_value **apArg
 182 ){
 183   struct CallCount *p;
 184   p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
 185   if( p ) p->nStep = 1;
 186   UNUSED_PARAMETER(nArg);
 187   UNUSED_PARAMETER(apArg);
 188 }
 189 static void dense_rankValueFunc(sqlite3_context *pCtx){
 190   struct CallCount *p;
 191   p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
 192   if( p ){
 193     if( p->nStep ){
 194       p->nValue++;
 195       p->nStep = 0;
 196     }
 197     sqlite3_result_int64(pCtx, p->nValue);
 198   }
 199 }
 200
 201 /*
 202 ** Implementation of built-in window function rank(). Assumes that
 203 ** the window frame has been set to:
 204 **
 205 **   RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
 206 */
 207 static void rankStepFunc(
 208   sqlite3_context *pCtx,
 209   int nArg,
 210   sqlite3_value **apArg
 211 ){
 212   struct CallCount *p;
 213   p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
 214   if( p ){
 215     p->nStep++;
 216     if( p->nValue==0 ){
 217       p->nValue = p->nStep;
 218     }
 219   }
 220   UNUSED_PARAMETER(nArg);
 221   UNUSED_PARAMETER(apArg);
 222 }
 223 static void rankValueFunc(sqlite3_context *pCtx){
 224   struct CallCount *p;
 225   p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
 226   if( p ){
 227     sqlite3_result_int64(pCtx, p->nValue);
 228     p->nValue = 0;
 229   }
 230 }
 231
 232 /*
 233 ** Implementation of built-in window function percent_rank(). Assumes that
 234 ** the window frame has been set to:
 235 **
 236 **   RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
 237 */
 238 static void percent_rankStepFunc(
 239   sqlite3_context *pCtx,
 240   int nArg,
 241   sqlite3_value **apArg
 242 ){
 243   struct CallCount *p;
 244   UNUSED_PARAMETER(nArg); assert( nArg==1 );
 245
 246   p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
 247   if( p ){
 248     if( p->nTotal==0 ){
 249       p->nTotal = sqlite3_value_int64(apArg[0]);
 250     }
 251     p->nStep++;
 252     if( p->nValue==0 ){
 253       p->nValue = p->nStep;
 254     }
 255   }
 256 }
 257 static void percent_rankValueFunc(sqlite3_context *pCtx){
 258   struct CallCount *p;
 259   p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
 260   if( p ){
 261     if( p->nTotal>1 ){
 262       double r = (double)(p->nValue-1) / (double)(p->nTotal-1);
 263       sqlite3_result_double(pCtx, r);
 264     }else{
 265       sqlite3_result_double(pCtx, 0.0);
 266     }
 267     p->nValue = 0;
 268   }
 269 }
 270
 271 /*
 272 ** Implementation of built-in window function cume_dist(). Assumes that
 273 ** the window frame has been set to:
 274 **
 275 **   RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
 276 */
 277 static void cume_distStepFunc(
 278   sqlite3_context *pCtx,
 279   int nArg,
 280   sqlite3_value **apArg
 281 ){
 282   struct CallCount *p;
 283   assert( nArg==1 ); UNUSED_PARAMETER(nArg);
 284
 285   p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
 286   if( p ){
 287     if( p->nTotal==0 ){
 288       p->nTotal = sqlite3_value_int64(apArg[0]);
 289     }
 290     p->nStep++;
 291   }
 292 }
 293 static void cume_distValueFunc(sqlite3_context *pCtx){
 294   struct CallCount *p;
 295   p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
 296   if( p && p->nTotal ){
 297     double r = (double)(p->nStep) / (double)(p->nTotal);
 298     sqlite3_result_double(pCtx, r);
 299   }
 300 }
 301
 302 /*
 303 ** Context object for ntile() window function.
 304 */
 305 struct NtileCtx {
 306   i64 nTotal;                     /* Total rows in partition */
 307   i64 nParam;                     /* Parameter passed to ntile(N) */
 308   i64 iRow;                       /* Current row */
 309 };
 310
 311 /*
 312 ** Implementation of ntile(). This assumes that the window frame has
 313 ** been coerced to:
 314 **
 315 **   ROWS UNBOUNDED PRECEDING AND CURRENT ROW
 316 */
 317 static void ntileStepFunc(
 318   sqlite3_context *pCtx,
 319   int nArg,
 320   sqlite3_value **apArg
 321 ){
 322   struct NtileCtx *p;
 323   assert( nArg==2 ); UNUSED_PARAMETER(nArg);
 324   p = (struct NtileCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));
 325   if( p ){
 326     if( p->nTotal==0 ){
 327       p->nParam = sqlite3_value_int64(apArg[0]);
 328       p->nTotal = sqlite3_value_int64(apArg[1]);
 329       if( p->nParam<=0 ){
 330         sqlite3_result_error(
 331             pCtx, "argument of ntile must be a positive integer", -1
 332         );
 333       }
 334     }
 335     p->iRow++;
 336   }
 337 }
 338 static void ntileValueFunc(sqlite3_context *pCtx){
 339   struct NtileCtx *p;
 340   p = (struct NtileCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));
 341   if( p && p->nParam>0 ){
 342     int nSize = (p->nTotal / p->nParam);
 343     if( nSize==0 ){
 344       sqlite3_result_int64(pCtx, p->iRow);
 345     }else{
 346       i64 nLarge = p->nTotal - p->nParam*nSize;
 347       i64 iSmall = nLarge*(nSize+1);
 348       i64 iRow = p->iRow-1;
 349
 350       assert( (nLarge*(nSize+1) + (p->nParam-nLarge)*nSize)==p->nTotal );
 351
 352       if( iRow<iSmall ){
 353         sqlite3_result_int64(pCtx, 1 + iRow/(nSize+1));
 354       }else{
 355         sqlite3_result_int64(pCtx, 1 + nLarge + (iRow-iSmall)/nSize);
 356       }
 357     }
 358   }
 359 }
 360
 361 /*
 362 ** Context object for last_value() window function.
 363 */
 364 struct LastValueCtx {
 365   sqlite3_value *pVal;
 366   int nVal;
 367 };
 368
 369 /*
 370 ** Implementation of last_value().
 371 */
 372 static void last_valueStepFunc(
 373   sqlite3_context *pCtx,
 374   int nArg,
 375   sqlite3_value **apArg
 376 ){
 377   struct LastValueCtx *p;
 378   UNUSED_PARAMETER(nArg);
 379   p = (struct LastValueCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));
 380   if( p ){
 381     sqlite3_value_free(p->pVal);
 382     p->pVal = sqlite3_value_dup(apArg[0]);
 383     if( p->pVal==0 ){
 384       sqlite3_result_error_nomem(pCtx);
 385     }else{
 386       p->nVal++;
 387     }
 388   }
 389 }
 390 static void last_valueInvFunc(
 391   sqlite3_context *pCtx,
 392   int nArg,
 393   sqlite3_value **apArg
 394 ){
 395   struct LastValueCtx *p;
 396   UNUSED_PARAMETER(nArg);
 397   UNUSED_PARAMETER(apArg);
 398   p = (struct LastValueCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));
 399   if( ALWAYS(p) ){
 400     p->nVal--;
 401     if( p->nVal==0 ){
 402       sqlite3_value_free(p->pVal);
 403       p->pVal = 0;
 404     }
 405   }
 406 }
 407 static void last_valueValueFunc(sqlite3_context *pCtx){
 408   struct LastValueCtx *p;
 409   p = (struct LastValueCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));
 410   if( p && p->pVal ){
 411     sqlite3_result_value(pCtx, p->pVal);
 412   }
 413 }
 414 static void last_valueFinalizeFunc(sqlite3_context *pCtx){
 415   struct LastValueCtx *p;
 416   p = (struct LastValueCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));
 417   if( p && p->pVal ){
 418     sqlite3_result_value(pCtx, p->pVal);
 419     sqlite3_value_free(p->pVal);
 420     p->pVal = 0;
 421   }
 422 }
 423
 424 /*
 425 ** Static names for the built-in window function names.  These static
 426 ** names are used, rather than string literals, so that FuncDef objects
 427 ** can be associated with a particular window function by direct
 428 ** comparison of the zName pointer.  Example:
 429 **
 430 **       if( pFuncDef->zName==row_valueName ){ ... }
 431 */
 432 static const char row_numberName[] =   "row_number";
 433 static const char dense_rankName[] =   "dense_rank";
 434 static const char rankName[] =         "rank";
 435 static const char percent_rankName[] = "percent_rank";
 436 static const char cume_distName[] =    "cume_dist";
 437 static const char ntileName[] =        "ntile";
 438 static const char last_valueName[] =   "last_value";
 439 static const char nth_valueName[] =    "nth_value";
 440 static const char first_valueName[] =  "first_value";
 441 static const char leadName[] =         "lead";
 442 static const char lagName[] =          "lag";
 443
 444 /*
 445 ** No-op implementations of xStep() and xFinalize().  Used as place-holders
 446 ** for built-in window functions that never call those interfaces.
 447 **
 448 ** The noopValueFunc() is called but is expected to do nothing.  The
 449 ** noopStepFunc() is never called, and so it is marked with NO_TEST to
 450 ** let the test coverage routine know not to expect this function to be
 451 ** invoked.
 452 */
 453 static void noopStepFunc(    /*NO_TEST*/
 454   sqlite3_context *p,        /*NO_TEST*/
 455   int n,                     /*NO_TEST*/
 456   sqlite3_value **a          /*NO_TEST*/
 457 ){                           /*NO_TEST*/
 458   UNUSED_PARAMETER(p);       /*NO_TEST*/
 459   UNUSED_PARAMETER(n);       /*NO_TEST*/
 460   UNUSED_PARAMETER(a);       /*NO_TEST*/
 461   assert(0);                 /*NO_TEST*/
 462 }                            /*NO_TEST*/
 463 static void noopValueFunc(sqlite3_context *p){ UNUSED_PARAMETER(p); /*no-op*/ }
 464
 465 /* Window functions that use all window interfaces: xStep, xFinal,
 466 ** xValue, and xInverse */
 467 #define WINDOWFUNCALL(name,nArg,extra) {                                   \
 468   nArg, (SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0,                      \
 469   name ## StepFunc, name ## FinalizeFunc, name ## ValueFunc,               \
 470   name ## InvFunc, name ## Name, {0}                                       \
 471 }
 472
 473 /* Window functions that are implemented using bytecode and thus have
 474 ** no-op routines for their methods */
 475 #define WINDOWFUNCNOOP(name,nArg,extra) {                                  \
 476   nArg, (SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0,                      \
 477   noopStepFunc, noopValueFunc, noopValueFunc,                              \
 478   noopStepFunc, name ## Name, {0}                                          \
 479 }
 480
 481 /* Window functions that use all window interfaces: xStep, the
 482 ** same routine for xFinalize and xValue and which never call
 483 ** xInverse. */
 484 #define WINDOWFUNCX(name,nArg,extra) {                                     \
 485   nArg, (SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0,                      \
 486   name ## StepFunc, name ## ValueFunc, name ## ValueFunc,                  \
 487   noopStepFunc, name ## Name, {0}                                          \
 488 }
 489
 490
 491 /*
 492 ** Register those built-in window functions that are not also aggregates.
 493 */
 494 void sqlite3WindowFunctions(void){
 495   static FuncDef aWindowFuncs[] = {
 496     WINDOWFUNCX(row_number, 0, 0),
 497     WINDOWFUNCX(dense_rank, 0, 0),
 498     WINDOWFUNCX(rank, 0, 0),
 499     WINDOWFUNCX(percent_rank, 0, SQLITE_FUNC_WINDOW_SIZE),
 500     WINDOWFUNCX(cume_dist, 0, SQLITE_FUNC_WINDOW_SIZE),
 501     WINDOWFUNCX(ntile, 1, SQLITE_FUNC_WINDOW_SIZE),
 502     WINDOWFUNCALL(last_value, 1, 0),
 503     WINDOWFUNCNOOP(nth_value, 2, 0),
 504     WINDOWFUNCNOOP(first_value, 1, 0),
 505     WINDOWFUNCNOOP(lead, 1, 0),
 506     WINDOWFUNCNOOP(lead, 2, 0),
 507     WINDOWFUNCNOOP(lead, 3, 0),
 508     WINDOWFUNCNOOP(lag, 1, 0),
 509     WINDOWFUNCNOOP(lag, 2, 0),
 510     WINDOWFUNCNOOP(lag, 3, 0),
 511   };
 512   sqlite3InsertBuiltinFuncs(aWindowFuncs, ArraySize(aWindowFuncs));
 513 }
 514
 515 /*
 516 ** This function is called immediately after resolving the function name
 517 ** for a window function within a SELECT statement. Argument pList is a
 518 ** linked list of WINDOW definitions for the current SELECT statement.
 519 ** Argument pFunc is the function definition just resolved and pWin
 520 ** is the Window object representing the associated OVER clause. This
 521 ** function updates the contents of pWin as follows:
 522 **
 523 **   * If the OVER clause refered to a named window (as in "max(x) OVER win"),
 524 **     search list pList for a matching WINDOW definition, and update pWin
 525 **     accordingly. If no such WINDOW clause can be found, leave an error
 526 **     in pParse.
 527 **
 528 **   * If the function is a built-in window function that requires the
 529 **     window to be coerced (see "BUILT-IN WINDOW FUNCTIONS" at the top
 530 **     of this file), pWin is updated here.
 531 */
 532 void sqlite3WindowUpdate(
 533   Parse *pParse,
 534   Window *pList,                  /* List of named windows for this SELECT */
 535   Window *pWin,                   /* Window frame to update */
 536   FuncDef *pFunc                  /* Window function definition */
 537 ){
 538   if( pWin->zName && pWin->eType==0 ){
 539     Window *p;
 540     for(p=pList; p; p=p->pNextWin){
 541       if( sqlite3StrICmp(p->zName, pWin->zName)==0 ) break;
 542     }
 543     if( p==0 ){
 544       sqlite3ErrorMsg(pParse, "no such window: %s", pWin->zName);
 545       return;
 546     }
 547     pWin->pPartition = sqlite3ExprListDup(pParse->db, p->pPartition, 0);
 548     pWin->pOrderBy = sqlite3ExprListDup(pParse->db, p->pOrderBy, 0);
 549     pWin->pStart = sqlite3ExprDup(pParse->db, p->pStart, 0);
 550     pWin->pEnd = sqlite3ExprDup(pParse->db, p->pEnd, 0);
 551     pWin->eStart = p->eStart;
 552     pWin->eEnd = p->eEnd;
 553     pWin->eType = p->eType;
 554   }
 555   if( pFunc->funcFlags & SQLITE_FUNC_WINDOW ){
 556     sqlite3 *db = pParse->db;
 557     if( pWin->pFilter ){
 558       sqlite3ErrorMsg(pParse,
 559           "FILTER clause may only be used with aggregate window functions"
 560       );
 561     }else
 562     if( pFunc->zName==row_numberName || pFunc->zName==ntileName ){
 563       sqlite3ExprDelete(db, pWin->pStart);
 564       sqlite3ExprDelete(db, pWin->pEnd);
 565       pWin->pStart = pWin->pEnd = 0;
 566       pWin->eType = TK_ROWS;
 567       pWin->eStart = TK_UNBOUNDED;
 568       pWin->eEnd = TK_CURRENT;
 569     }else
 570
 571     if( pFunc->zName==dense_rankName || pFunc->zName==rankName
 572      || pFunc->zName==percent_rankName || pFunc->zName==cume_distName
 573     ){
 574       sqlite3ExprDelete(db, pWin->pStart);
 575       sqlite3ExprDelete(db, pWin->pEnd);
 576       pWin->pStart = pWin->pEnd = 0;
 577       pWin->eType = TK_RANGE;
 578       pWin->eStart = TK_UNBOUNDED;
 579       pWin->eEnd = TK_CURRENT;
 580     }
 581   }
 582   pWin->pFunc = pFunc;
 583 }
 584
 585 /*
 586 ** Context object passed through sqlite3WalkExprList() to
 587 ** selectWindowRewriteExprCb() by selectWindowRewriteEList().
 588 */
 589 typedef struct WindowRewrite WindowRewrite;
 590 struct WindowRewrite {
 591   Window *pWin;
 592   ExprList *pSub;
 593 };
 594
 595 /*
 596 ** Callback function used by selectWindowRewriteEList(). If necessary,
 597 ** this function appends to the output expression-list and updates
 598 ** expression (*ppExpr) in place.
 599 */
 600 static int selectWindowRewriteExprCb(Walker *pWalker, Expr *pExpr){
 601   struct WindowRewrite *p = pWalker->u.pRewrite;
 602   Parse *pParse = pWalker->pParse;
 603
 604   switch( pExpr->op ){
 605
 606     case TK_FUNCTION:
 607       if( pExpr->pWin==0 ){
 608         break;
 609       }else{
 610         Window *pWin;
 611         for(pWin=p->pWin; pWin; pWin=pWin->pNextWin){
 612           if( pExpr->pWin==pWin ){
 613             assert( pWin->pOwner==pExpr );
 614             return WRC_Prune;
 615           }
 616         }
 617       }
 618       /* Fall through.  */
 619
 620     case TK_AGG_FUNCTION:
 621     case TK_COLUMN: {
 622       Expr *pDup = sqlite3ExprDup(pParse->db, pExpr, 0);
 623       p->pSub = sqlite3ExprListAppend(pParse, p->pSub, pDup);
 624       if( p->pSub ){
 625         assert( ExprHasProperty(pExpr, EP_Static)==0 );
 626         ExprSetProperty(pExpr, EP_Static);
 627         sqlite3ExprDelete(pParse->db, pExpr);
 628         ExprClearProperty(pExpr, EP_Static);
 629         memset(pExpr, 0, sizeof(Expr));
 630
 631         pExpr->op = TK_COLUMN;
 632         pExpr->iColumn = p->pSub->nExpr-1;
 633         pExpr->iTable = p->pWin->iEphCsr;
 634       }
 635
 636       break;
 637     }
 638
 639     default: /* no-op */
 640       break;
 641   }
 642
 643   return WRC_Continue;
 644 }
 645 static int selectWindowRewriteSelectCb(Walker *pWalker, Select *pSelect){
 646   UNUSED_PARAMETER(pWalker);
 647   UNUSED_PARAMETER(pSelect);
 648   return WRC_Prune;
 649 }
 650
 651
 652 /*
 653 ** Iterate through each expression in expression-list pEList. For each:
 654 **
 655 **   * TK_COLUMN,
 656 **   * aggregate function, or
 657 **   * window function with a Window object that is not a member of the
 658 **     linked list passed as the second argument (pWin)
 659 **
 660 ** Append the node to output expression-list (*ppSub). And replace it
 661 ** with a TK_COLUMN that reads the (N-1)th element of table
 662 ** pWin->iEphCsr, where N is the number of elements in (*ppSub) after
 663 ** appending the new one.
 664 */
 665 static void selectWindowRewriteEList(
 666   Parse *pParse,
 667   Window *pWin,
 668   ExprList *pEList,               /* Rewrite expressions in this list */
 669   ExprList **ppSub                /* IN/OUT: Sub-select expression-list */
 670 ){
 671   Walker sWalker;
 672   WindowRewrite sRewrite;
 673
 674   memset(&sWalker, 0, sizeof(Walker));
 675   memset(&sRewrite, 0, sizeof(WindowRewrite));
 676
 677   sRewrite.pSub = *ppSub;
 678   sRewrite.pWin = pWin;
 679
 680   sWalker.pParse = pParse;
 681   sWalker.xExprCallback = selectWindowRewriteExprCb;
 682   sWalker.xSelectCallback = selectWindowRewriteSelectCb;
 683   sWalker.u.pRewrite = &sRewrite;
 684
 685   (void)sqlite3WalkExprList(&sWalker, pEList);
 686
 687   *ppSub = sRewrite.pSub;
 688 }
 689
 690 /*
 691 ** Append a copy of each expression in expression-list pAppend to
 692 ** expression list pList. Return a pointer to the result list.
 693 */
 694 static ExprList *exprListAppendList(
 695   Parse *pParse,          /* Parsing context */
 696   ExprList *pList,        /* List to which to append. Might be NULL */
 697   ExprList *pAppend       /* List of values to append. Might be NULL */
 698 ){
 699   if( pAppend ){
 700     int i;
 701     int nInit = pList ? pList->nExpr : 0;
 702     for(i=0; i<pAppend->nExpr; i++){
 703       Expr *pDup = sqlite3ExprDup(pParse->db, pAppend->a[i].pExpr, 0);
 704       pList = sqlite3ExprListAppend(pParse, pList, pDup);
 705       if( pList ) pList->a[nInit+i].sortOrder = pAppend->a[i].sortOrder;
 706     }
 707   }
 708   return pList;
 709 }
 710
 711 /*
 712 ** If the SELECT statement passed as the second argument does not invoke
 713 ** any SQL window functions, this function is a no-op. Otherwise, it
 714 ** rewrites the SELECT statement so that window function xStep functions
 715 ** are invoked in the correct order as described under "SELECT REWRITING"
 716 ** at the top of this file.
 717 */
 718 int sqlite3WindowRewrite(Parse *pParse, Select *p){
 719   int rc = SQLITE_OK;
 720   if( p->pWin ){
 721     Vdbe *v = sqlite3GetVdbe(pParse);
 722     sqlite3 *db = pParse->db;
 723     Select *pSub = 0;             /* The subquery */
 724     SrcList *pSrc = p->pSrc;
 725     Expr *pWhere = p->pWhere;
 726     ExprList *pGroupBy = p->pGroupBy;
 727     Expr *pHaving = p->pHaving;
 728     ExprList *pSort = 0;
 729
 730     ExprList *pSublist = 0;       /* Expression list for sub-query */
 731     Window *pMWin = p->pWin;      /* Master window object */
 732     Window *pWin;                 /* Window object iterator */
 733
 734     p->pSrc = 0;
 735     p->pWhere = 0;
 736     p->pGroupBy = 0;
 737     p->pHaving = 0;
 738
 739     /* Create the ORDER BY clause for the sub-select. This is the concatenation
 740     ** of the window PARTITION and ORDER BY clauses. Then, if this makes it
 741     ** redundant, remove the ORDER BY from the parent SELECT.  */
 742     pSort = sqlite3ExprListDup(db, pMWin->pPartition, 0);
 743     pSort = exprListAppendList(pParse, pSort, pMWin->pOrderBy);
 744     if( pSort && p->pOrderBy ){
 745       if( sqlite3ExprListCompare(pSort, p->pOrderBy, -1)==0 ){
 746         sqlite3ExprListDelete(db, p->pOrderBy);
 747         p->pOrderBy = 0;
 748       }
 749     }
 750
 751     /* Assign a cursor number for the ephemeral table used to buffer rows.
 752     ** The OpenEphemeral instruction is coded later, after it is known how
 753     ** many columns the table will have.  */
 754     pMWin->iEphCsr = pParse->nTab++;
 755
 756     selectWindowRewriteEList(pParse, pMWin, p->pEList, &pSublist);
 757     selectWindowRewriteEList(pParse, pMWin, p->pOrderBy, &pSublist);
 758     pMWin->nBufferCol = (pSublist ? pSublist->nExpr : 0);
 759
 760     /* Append the PARTITION BY and ORDER BY expressions to the to the
 761     ** sub-select expression list. They are required to figure out where
 762     ** boundaries for partitions and sets of peer rows lie.  */
 763     pSublist = exprListAppendList(pParse, pSublist, pMWin->pPartition);
 764     pSublist = exprListAppendList(pParse, pSublist, pMWin->pOrderBy);
 765
 766     /* Append the arguments passed to each window function to the
 767     ** sub-select expression list. Also allocate two registers for each
 768     ** window function - one for the accumulator, another for interim
 769     ** results.  */
 770     for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
 771       pWin->iArgCol = (pSublist ? pSublist->nExpr : 0);
 772       pSublist = exprListAppendList(pParse, pSublist, pWin->pOwner->x.pList);
 773       if( pWin->pFilter ){
 774         Expr *pFilter = sqlite3ExprDup(db, pWin->pFilter, 0);
 775         pSublist = sqlite3ExprListAppend(pParse, pSublist, pFilter);
 776       }
 777       pWin->regAccum = ++pParse->nMem;
 778       pWin->regResult = ++pParse->nMem;
 779       sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);
 780     }
 781
 782     /* If there is no ORDER BY or PARTITION BY clause, and the window
 783     ** function accepts zero arguments, and there are no other columns
 784     ** selected (e.g. "SELECT row_number() OVER () FROM t1"), it is possible
 785     ** that pSublist is still NULL here. Add a constant expression here to
 786     ** keep everything legal in this case.
 787     */
 788     if( pSublist==0 ){
 789       pSublist = sqlite3ExprListAppend(pParse, 0,
 790           sqlite3ExprAlloc(db, TK_INTEGER, &sqlite3IntTokens[0], 0)
 791       );
 792     }
 793
 794     pSub = sqlite3SelectNew(
 795         pParse, pSublist, pSrc, pWhere, pGroupBy, pHaving, pSort, 0, 0
 796     );
 797     p->pSrc = sqlite3SrcListAppend(db, 0, 0, 0);
 798     assert( p->pSrc || db->mallocFailed );
 799     if( p->pSrc ){
 800       p->pSrc->a[0].pSelect = pSub;
 801       sqlite3SrcListAssignCursors(pParse, p->pSrc);
 802       if( sqlite3ExpandSubquery(pParse, &p->pSrc->a[0]) ){
 803         rc = SQLITE_NOMEM;
 804       }else{
 805         pSub->selFlags |= SF_Expanded;
 806         p->selFlags &= ~SF_Aggregate;
 807         sqlite3SelectPrep(pParse, pSub, 0);
 808       }
 809
 810       sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pMWin->iEphCsr, pSublist->nExpr);
 811     }else{
 812       sqlite3SelectDelete(db, pSub);
 813     }
 814     if( db->mallocFailed ) rc = SQLITE_NOMEM;
 815   }
 816
 817   return rc;
 818 }
 819
 820 /*
 821 ** Free the Window object passed as the second argument.
 822 */
 823 void sqlite3WindowDelete(sqlite3 *db, Window *p){
 824   if( p ){
 825     sqlite3ExprDelete(db, p->pFilter);
 826     sqlite3ExprListDelete(db, p->pPartition);
 827     sqlite3ExprListDelete(db, p->pOrderBy);
 828     sqlite3ExprDelete(db, p->pEnd);
 829     sqlite3ExprDelete(db, p->pStart);
 830     sqlite3DbFree(db, p->zName);
 831     sqlite3DbFree(db, p);
 832   }
 833 }
 834
 835 /*
 836 ** Free the linked list of Window objects starting at the second argument.
 837 */
 838 void sqlite3WindowListDelete(sqlite3 *db, Window *p){
 839   while( p ){
 840     Window *pNext = p->pNextWin;
 841     sqlite3WindowDelete(db, p);
 842     p = pNext;
 843   }
 844 }
 845
 846 /*
 847 ** The argument expression is an PRECEDING or FOLLOWING offset.  The
 848 ** value should be a non-negative integer.  If the value is not a
 849 ** constant, change it to NULL.  The fact that it is then a non-negative
 850 ** integer will be caught later.  But it is important not to leave
 851 ** variable values in the expression tree.
 852 */
 853 static Expr *sqlite3WindowOffsetExpr(Parse *pParse, Expr *pExpr){
 854   if( 0==sqlite3ExprIsConstant(pExpr) ){
 855     sqlite3ExprDelete(pParse->db, pExpr);
 856     pExpr = sqlite3ExprAlloc(pParse->db, TK_NULL, 0, 0);
 857   }
 858   return pExpr;
 859 }
 860
 861 /*
 862 ** Allocate and return a new Window object describing a Window Definition.
 863 */
 864 Window *sqlite3WindowAlloc(
 865   Parse *pParse,    /* Parsing context */
 866   int eType,        /* Frame type. TK_RANGE or TK_ROWS */
 867   int eStart,       /* Start type: CURRENT, PRECEDING, FOLLOWING, UNBOUNDED */
 868   Expr *pStart,     /* Start window size if TK_PRECEDING or FOLLOWING */
 869   int eEnd,         /* End type: CURRENT, FOLLOWING, TK_UNBOUNDED, PRECEDING */
 870   Expr *pEnd        /* End window size if TK_FOLLOWING or PRECEDING */
 871 ){
 872   Window *pWin = 0;
 873
 874   /* Parser assures the following: */
 875   assert( eType==TK_RANGE || eType==TK_ROWS );
 876   assert( eStart==TK_CURRENT || eStart==TK_PRECEDING
 877            || eStart==TK_UNBOUNDED || eStart==TK_FOLLOWING );
 878   assert( eEnd==TK_CURRENT || eEnd==TK_FOLLOWING
 879            || eEnd==TK_UNBOUNDED || eEnd==TK_PRECEDING );
 880   assert( (eStart==TK_PRECEDING || eStart==TK_FOLLOWING)==(pStart!=0) );
 881   assert( (eEnd==TK_FOLLOWING || eEnd==TK_PRECEDING)==(pEnd!=0) );
 882
 883
 884   /* If a frame is declared "RANGE" (not "ROWS"), then it may not use
 885   ** either "<expr> PRECEDING" or "<expr> FOLLOWING".
 886   */
 887   if( eType==TK_RANGE && (pStart!=0 || pEnd!=0) ){
 888     sqlite3ErrorMsg(pParse, "RANGE must use only UNBOUNDED or CURRENT ROW");
 889     goto windowAllocErr;
 890   }
 891
 892   /* Additionally, the
 893   ** starting boundary type may not occur earlier in the following list than
 894   ** the ending boundary type:
 895   **
 896   **   UNBOUNDED PRECEDING
 897   **   <expr> PRECEDING
 898   **   CURRENT ROW
 899   **   <expr> FOLLOWING
 900   **   UNBOUNDED FOLLOWING
 901   **
 902   ** The parser ensures that "UNBOUNDED PRECEDING" cannot be used as an ending
 903   ** boundary, and than "UNBOUNDED FOLLOWING" cannot be used as a starting
 904   ** frame boundary.
 905   */
 906   if( (eStart==TK_CURRENT && eEnd==TK_PRECEDING)
 907    || (eStart==TK_FOLLOWING && (eEnd==TK_PRECEDING || eEnd==TK_CURRENT))
 908   ){
 909     sqlite3ErrorMsg(pParse, "unsupported frame delimiter for ROWS");
 910     goto windowAllocErr;
 911   }
 912
 913   pWin = (Window*)sqlite3DbMallocZero(pParse->db, sizeof(Window));
 914   if( pWin==0 ) goto windowAllocErr;
 915   pWin->eType = eType;
 916   pWin->eStart = eStart;
 917   pWin->eEnd = eEnd;
 918   pWin->pEnd = sqlite3WindowOffsetExpr(pParse, pEnd);
 919   pWin->pStart = sqlite3WindowOffsetExpr(pParse, pStart);
 920   return pWin;
 921
 922 windowAllocErr:
 923   sqlite3ExprDelete(pParse->db, pEnd);
 924   sqlite3ExprDelete(pParse->db, pStart);
 925   return 0;
 926 }
 927
 928 /*
 929 ** Attach window object pWin to expression p.
 930 */
 931 void sqlite3WindowAttach(Parse *pParse, Expr *p, Window *pWin){
 932   if( p ){
 933     if( pWin ){
 934       p->pWin = pWin;
 935       pWin->pOwner = p;
 936       if( p->flags & EP_Distinct ){
 937         sqlite3ErrorMsg(pParse,
 938            "DISTINCT is not supported for window functions");
 939       }
 940     }
 941   }else{
 942     sqlite3WindowDelete(pParse->db, pWin);
 943   }
 944 }
 945
 946 /*
 947 ** Return 0 if the two window objects are identical, or non-zero otherwise.
 948 ** Identical window objects can be processed in a single scan.
 949 */
 950 int sqlite3WindowCompare(Parse *pParse, Window *p1, Window *p2){
 951   if( p1->eType!=p2->eType ) return 1;
 952   if( p1->eStart!=p2->eStart ) return 1;
 953   if( p1->eEnd!=p2->eEnd ) return 1;
 954   if( sqlite3ExprCompare(pParse, p1->pStart, p2->pStart, -1) ) return 1;
 955   if( sqlite3ExprCompare(pParse, p1->pEnd, p2->pEnd, -1) ) return 1;
 956   if( sqlite3ExprListCompare(p1->pPartition, p2->pPartition, -1) ) return 1;
 957   if( sqlite3ExprListCompare(p1->pOrderBy, p2->pOrderBy, -1) ) return 1;
 958   return 0;
 959 }
 960
 961
 962 /*
 963 ** This is called by code in select.c before it calls sqlite3WhereBegin()
 964 ** to begin iterating through the sub-query results. It is used to allocate
 965 ** and initialize registers and cursors used by sqlite3WindowCodeStep().
 966 */
 967 void sqlite3WindowCodeInit(Parse *pParse, Window *pMWin){
 968   Window *pWin;
 969   Vdbe *v = sqlite3GetVdbe(pParse);
 970   int nPart = (pMWin->pPartition ? pMWin->pPartition->nExpr : 0);
 971   nPart += (pMWin->pOrderBy ? pMWin->pOrderBy->nExpr : 0);
 972   if( nPart ){
 973     pMWin->regPart = pParse->nMem+1;
 974     pParse->nMem += nPart;
 975     sqlite3VdbeAddOp3(v, OP_Null, 0, pMWin->regPart, pMWin->regPart+nPart-1);
 976   }
 977
 978   for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
 979     FuncDef *p = pWin->pFunc;
 980     if( (p->funcFlags & SQLITE_FUNC_MINMAX) && pWin->eStart!=TK_UNBOUNDED ){
 981       /* The inline versions of min() and max() require a single ephemeral
 982       ** table and 3 registers. The registers are used as follows:
 983       **
 984       **   regApp+0: slot to copy min()/max() argument to for MakeRecord
 985       **   regApp+1: integer value used to ensure keys are unique
 986       **   regApp+2: output of MakeRecord
 987       */
 988       ExprList *pList = pWin->pOwner->x.pList;
 989       KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pList, 0, 0);
 990       pWin->csrApp = pParse->nTab++;
 991       pWin->regApp = pParse->nMem+1;
 992       pParse->nMem += 3;
 993       if( pKeyInfo && pWin->pFunc->zName[1]=='i' ){
 994         assert( pKeyInfo->aSortOrder[0]==0 );
 995         pKeyInfo->aSortOrder[0] = 1;
 996       }
 997       sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pWin->csrApp, 2);
 998       sqlite3VdbeAppendP4(v, pKeyInfo, P4_KEYINFO);
 999       sqlite3VdbeAddOp2(v, OP_Integer, 0, pWin->regApp+1);
1000     }
1001     else if( p->zName==nth_valueName || p->zName==first_valueName ){
1002       /* Allocate two registers at pWin->regApp. These will be used to
1003       ** store the start and end index of the current frame.  */
1004       assert( pMWin->iEphCsr );
1005       pWin->regApp = pParse->nMem+1;
1006       pWin->csrApp = pParse->nTab++;
1007       pParse->nMem += 2;
1008       sqlite3VdbeAddOp2(v, OP_OpenDup, pWin->csrApp, pMWin->iEphCsr);
1009     }
1010     else if( p->zName==leadName || p->zName==lagName ){
1011       assert( pMWin->iEphCsr );
1012       pWin->csrApp = pParse->nTab++;
1013       sqlite3VdbeAddOp2(v, OP_OpenDup, pWin->csrApp, pMWin->iEphCsr);
1014     }
1015   }
1016 }
1017
1018 /*
1019 ** A "PRECEDING <expr>" (eCond==0) or "FOLLOWING <expr>" (eCond==1) or the
1020 ** value of the second argument to nth_value() (eCond==2) has just been
1021 ** evaluated and the result left in register reg. This function generates VM
1022 ** code to check that the value is a non-negative integer and throws an
1023 ** exception if it is not.
1024 */
1025 static void windowCheckIntValue(Parse *pParse, int reg, int eCond){
1026   static const char *azErr[] = {
1027     "frame starting offset must be a non-negative integer",
1028     "frame ending offset must be a non-negative integer",
1029     "second argument to nth_value must be a positive integer"
1030   };
1031   static int aOp[] = { OP_Ge, OP_Ge, OP_Gt };
1032   Vdbe *v = sqlite3GetVdbe(pParse);
1033   int regZero = sqlite3GetTempReg(pParse);
1034   assert( eCond==0 || eCond==1 || eCond==2 );
1035   sqlite3VdbeAddOp2(v, OP_Integer, 0, regZero);
1036   sqlite3VdbeAddOp2(v, OP_MustBeInt, reg, sqlite3VdbeCurrentAddr(v)+2);
1037   VdbeCoverageIf(v, eCond==0);
1038   VdbeCoverageIf(v, eCond==1);
1039   VdbeCoverageIf(v, eCond==2);
1040   sqlite3VdbeAddOp3(v, aOp[eCond], regZero, sqlite3VdbeCurrentAddr(v)+2, reg);
1041   VdbeCoverageNeverNullIf(v, eCond==0);
1042   VdbeCoverageNeverNullIf(v, eCond==1);
1043   VdbeCoverageNeverNullIf(v, eCond==2);
1044   sqlite3VdbeAddOp2(v, OP_Halt, SQLITE_ERROR, OE_Abort);
1045   sqlite3VdbeAppendP4(v, (void*)azErr[eCond], P4_STATIC);
1046   sqlite3ReleaseTempReg(pParse, regZero);
1047 }
1048
1049 /*
1050 ** Return the number of arguments passed to the window-function associated
1051 ** with the object passed as the only argument to this function.
1052 */
1053 static int windowArgCount(Window *pWin){
1054   ExprList *pList = pWin->pOwner->x.pList;
1055   return (pList ? pList->nExpr : 0);
1056 }
1057
1058 /*
1059 ** Generate VM code to invoke either xStep() (if bInverse is 0) or
1060 ** xInverse (if bInverse is non-zero) for each window function in the
1061 ** linked list starting at pMWin. Or, for built-in window functions
1062 ** that do not use the standard function API, generate the required
1063 ** inline VM code.
1064 **
1065 ** If argument csr is greater than or equal to 0, then argument reg is
1066 ** the first register in an array of registers guaranteed to be large
1067 ** enough to hold the array of arguments for each function. In this case
1068 ** the arguments are extracted from the current row of csr into the
1069 ** array of registers before invoking OP_AggStep or OP_AggInverse
1070 **
1071 ** Or, if csr is less than zero, then the array of registers at reg is
1072 ** already populated with all columns from the current row of the sub-query.
1073 **
1074 ** If argument regPartSize is non-zero, then it is a register containing the
1075 ** number of rows in the current partition.
1076 */
1077 static void windowAggStep(
1078   Parse *pParse,
1079   Window *pMWin,                  /* Linked list of window functions */
1080   int csr,                        /* Read arguments from this cursor */
1081   int bInverse,                   /* True to invoke xInverse instead of xStep */
1082   int reg,                        /* Array of registers */
1083   int regPartSize                 /* Register containing size of partition */
1084 ){
1085   Vdbe *v = sqlite3GetVdbe(pParse);
1086   Window *pWin;
1087   for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
1088     int flags = pWin->pFunc->funcFlags;
1089     int regArg;
1090     int nArg = windowArgCount(pWin);
1091
1092     if( csr>=0 ){
1093       int i;
1094       for(i=0; i<nArg; i++){
1095         sqlite3VdbeAddOp3(v, OP_Column, csr, pWin->iArgCol+i, reg+i);
1096       }
1097       regArg = reg;
1098       if( flags & SQLITE_FUNC_WINDOW_SIZE ){
1099         if( nArg==0 ){
1100           regArg = regPartSize;
1101         }else{
1102           sqlite3VdbeAddOp2(v, OP_SCopy, regPartSize, reg+nArg);
1103         }
1104         nArg++;
1105       }
1106     }else{
1107       assert( !(flags & SQLITE_FUNC_WINDOW_SIZE) );
1108       regArg = reg + pWin->iArgCol;
1109     }
1110
1111     if( (pWin->pFunc->funcFlags & SQLITE_FUNC_MINMAX)
1112       && pWin->eStart!=TK_UNBOUNDED
1113     ){
1114       int addrIsNull = sqlite3VdbeAddOp1(v, OP_IsNull, regArg);
1115       VdbeCoverage(v);
1116       if( bInverse==0 ){
1117         sqlite3VdbeAddOp2(v, OP_AddImm, pWin->regApp+1, 1);
1118         sqlite3VdbeAddOp2(v, OP_SCopy, regArg, pWin->regApp);
1119         sqlite3VdbeAddOp3(v, OP_MakeRecord, pWin->regApp, 2, pWin->regApp+2);
1120         sqlite3VdbeAddOp2(v, OP_IdxInsert, pWin->csrApp, pWin->regApp+2);
1121       }else{
1122         sqlite3VdbeAddOp4Int(v, OP_SeekGE, pWin->csrApp, 0, regArg, 1);
1123         VdbeCoverage(v);
1124         sqlite3VdbeAddOp1(v, OP_Delete, pWin->csrApp);
1125         sqlite3VdbeJumpHere(v, sqlite3VdbeCurrentAddr(v)-2);
1126       }
1127       sqlite3VdbeJumpHere(v, addrIsNull);
1128     }else if( pWin->regApp ){
1129       assert( pWin->pFunc->zName==nth_valueName
1130            || pWin->pFunc->zName==first_valueName
1131       );
1132       assert( bInverse==0 || bInverse==1 );
1133       sqlite3VdbeAddOp2(v, OP_AddImm, pWin->regApp+1-bInverse, 1);
1134     }else if( pWin->pFunc->zName==leadName
1135            || pWin->pFunc->zName==lagName
1136     ){
1137       /* no-op */
1138     }else{
1139       int addrIf = 0;
1140       if( pWin->pFilter ){
1141         int regTmp;
1142         assert( nArg==0 || nArg==pWin->pOwner->x.pList->nExpr );
1143         assert( nArg || pWin->pOwner->x.pList==0 );
1144         if( csr>0 ){
1145           regTmp = sqlite3GetTempReg(pParse);
1146           sqlite3VdbeAddOp3(v, OP_Column, csr, pWin->iArgCol+nArg,regTmp);
1147         }else{
1148           regTmp = regArg + nArg;
1149         }
1150         addrIf = sqlite3VdbeAddOp3(v, OP_IfNot, regTmp, 0, 1);
1151         VdbeCoverage(v);
1152         if( csr>0 ){
1153           sqlite3ReleaseTempReg(pParse, regTmp);
1154         }
1155       }
1156       if( pWin->pFunc->funcFlags & SQLITE_FUNC_NEEDCOLL ){
1157         CollSeq *pColl;
1158         assert( nArg>0 );
1159         pColl = sqlite3ExprNNCollSeq(pParse, pWin->pOwner->x.pList->a[0].pExpr);
1160         sqlite3VdbeAddOp4(v, OP_CollSeq, 0,0,0, (const char*)pColl, P4_COLLSEQ);
1161       }
1162       sqlite3VdbeAddOp3(v, bInverse? OP_AggInverse : OP_AggStep,
1163                         bInverse, regArg, pWin->regAccum);
1164       sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
1165       sqlite3VdbeChangeP5(v, (u8)nArg);
1166       if( addrIf ) sqlite3VdbeJumpHere(v, addrIf);
1167     }
1168   }
1169 }
1170
1171 /*
1172 ** Generate VM code to invoke either xValue() (bFinal==0) or xFinalize()
1173 ** (bFinal==1) for each window function in the linked list starting at
1174 ** pMWin. Or, for built-in window-functions that do not use the standard
1175 ** API, generate the equivalent VM code.
1176 */
1177 static void windowAggFinal(Parse *pParse, Window *pMWin, int bFinal){
1178   Vdbe *v = sqlite3GetVdbe(pParse);
1179   Window *pWin;
1180
1181   for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
1182     if( (pWin->pFunc->funcFlags & SQLITE_FUNC_MINMAX)
1183      && pWin->eStart!=TK_UNBOUNDED
1184     ){
1185       sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regResult);
1186       sqlite3VdbeAddOp1(v, OP_Last, pWin->csrApp);
1187       VdbeCoverage(v);
1188       sqlite3VdbeAddOp3(v, OP_Column, pWin->csrApp, 0, pWin->regResult);
1189       sqlite3VdbeJumpHere(v, sqlite3VdbeCurrentAddr(v)-2);
1190       if( bFinal ){
1191         sqlite3VdbeAddOp1(v, OP_ResetSorter, pWin->csrApp);
1192       }
1193     }else if( pWin->regApp ){
1194     }else{
1195       if( bFinal ){
1196         sqlite3VdbeAddOp2(v, OP_AggFinal, pWin->regAccum, windowArgCount(pWin));
1197         sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
1198         sqlite3VdbeAddOp2(v, OP_Copy, pWin->regAccum, pWin->regResult);
1199         sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);
1200       }else{
1201         sqlite3VdbeAddOp3(v, OP_AggValue, pWin->regAccum, windowArgCount(pWin),
1202                              pWin->regResult);
1203         sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
1204       }
1205     }
1206   }
1207 }
1208
1209 /*
1210 ** This function generates VM code to invoke the sub-routine at address
1211 ** lblFlushPart once for each partition with the entire partition cached in
1212 ** the Window.iEphCsr temp table.
1213 */
1214 static void windowPartitionCache(
1215   Parse *pParse,
1216   Select *p,                      /* The rewritten SELECT statement */
1217   WhereInfo *pWInfo,              /* WhereInfo to call WhereEnd() on */
1218   int regFlushPart,               /* Register to use with Gosub lblFlushPart */
1219   int lblFlushPart,               /* Subroutine to Gosub to */
1220   int *pRegSize                   /* OUT: Register containing partition size */
1221 ){
1222   Window *pMWin = p->pWin;
1223   Vdbe *v = sqlite3GetVdbe(pParse);
1224   int iSubCsr = p->pSrc->a[0].iCursor;
1225   int nSub = p->pSrc->a[0].pTab->nCol;
1226   int k;
1227
1228   int reg = pParse->nMem+1;
1229   int regRecord = reg+nSub;
1230   int regRowid = regRecord+1;
1231
1232   *pRegSize = regRowid;
1233   pParse->nMem += nSub + 2;
1234
1235   /* Martial the row returned by the sub-select into an array of
1236   ** registers. */
1237   for(k=0; k<nSub; k++){
1238     sqlite3VdbeAddOp3(v, OP_Column, iSubCsr, k, reg+k);
1239   }
1240   sqlite3VdbeAddOp3(v, OP_MakeRecord, reg, nSub, regRecord);
1241
1242   /* Check if this is the start of a new partition. If so, call the
1243   ** flush_partition sub-routine.  */
1244   if( pMWin->pPartition ){
1245     int addr;
1246     ExprList *pPart = pMWin->pPartition;
1247     int nPart = pPart->nExpr;
1248     int regNewPart = reg + pMWin->nBufferCol;
1249     KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pPart, 0, 0);
1250
1251     addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPart, pMWin->regPart,nPart);
1252     sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
1253     sqlite3VdbeAddOp3(v, OP_Jump, addr+2, addr+4, addr+2);
1254     VdbeCoverage(v);
1255     sqlite3VdbeAddOp3(v, OP_Copy, regNewPart, pMWin->regPart, nPart-1);
1256     sqlite3VdbeAddOp2(v, OP_Gosub, regFlushPart, lblFlushPart);
1257     VdbeComment((v, "call flush_partition"));
1258   }
1259
1260   /* Buffer the current row in the ephemeral table. */
1261   sqlite3VdbeAddOp2(v, OP_NewRowid, pMWin->iEphCsr, regRowid);
1262   sqlite3VdbeAddOp3(v, OP_Insert, pMWin->iEphCsr, regRecord, regRowid);
1263
1264   /* End of the input loop */
1265   sqlite3WhereEnd(pWInfo);
1266
1267   /* Invoke "flush_partition" to deal with the final (or only) partition */
1268   sqlite3VdbeAddOp2(v, OP_Gosub, regFlushPart, lblFlushPart);
1269   VdbeComment((v, "call flush_partition"));
1270 }
1271
1272 /*
1273 ** Invoke the sub-routine at regGosub (generated by code in select.c) to
1274 ** return the current row of Window.iEphCsr. If all window functions are
1275 ** aggregate window functions that use the standard API, a single
1276 ** OP_Gosub instruction is all that this routine generates. Extra VM code
1277 ** for per-row processing is only generated for the following built-in window
1278 ** functions:
1279 **
1280 **   nth_value()
1281 **   first_value()
1282 **   lag()
1283 **   lead()
1284 */
1285 static void windowReturnOneRow(
1286   Parse *pParse,
1287   Window *pMWin,
1288   int regGosub,
1289   int addrGosub
1290 ){
1291   Vdbe *v = sqlite3GetVdbe(pParse);
1292   Window *pWin;
1293   for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
1294     FuncDef *pFunc = pWin->pFunc;
1295     if( pFunc->zName==nth_valueName
1296      || pFunc->zName==first_valueName
1297     ){
1298       int csr = pWin->csrApp;
1299       int lbl = sqlite3VdbeMakeLabel(v);
1300       int tmpReg = sqlite3GetTempReg(pParse);
1301       sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regResult);
1302
1303       if( pFunc->zName==nth_valueName ){
1304         sqlite3VdbeAddOp3(v, OP_Column, pMWin->iEphCsr, pWin->iArgCol+1,tmpReg);
1305         windowCheckIntValue(pParse, tmpReg, 2);
1306       }else{
1307         sqlite3VdbeAddOp2(v, OP_Integer, 1, tmpReg);
1308       }
1309       sqlite3VdbeAddOp3(v, OP_Add, tmpReg, pWin->regApp, tmpReg);
1310       sqlite3VdbeAddOp3(v, OP_Gt, pWin->regApp+1, lbl, tmpReg);
1311       VdbeCoverageNeverNull(v);
1312       sqlite3VdbeAddOp3(v, OP_SeekRowid, csr, lbl, tmpReg);
1313       VdbeCoverage(v);
1314       sqlite3VdbeAddOp3(v, OP_Column, csr, pWin->iArgCol, pWin->regResult);
1315       sqlite3VdbeResolveLabel(v, lbl);
1316       sqlite3ReleaseTempReg(pParse, tmpReg);
1317     }
1318     else if( pFunc->zName==leadName || pFunc->zName==lagName ){
1319       int nArg = pWin->pOwner->x.pList->nExpr;
1320       int iEph = pMWin->iEphCsr;
1321       int csr = pWin->csrApp;
1322       int lbl = sqlite3VdbeMakeLabel(v);
1323       int tmpReg = sqlite3GetTempReg(pParse);
1324
1325       if( nArg<3 ){
1326         sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regResult);
1327       }else{
1328         sqlite3VdbeAddOp3(v, OP_Column, iEph, pWin->iArgCol+2, pWin->regResult);
1329       }
1330       sqlite3VdbeAddOp2(v, OP_Rowid, iEph, tmpReg);
1331       if( nArg<2 ){
1332         int val = (pFunc->zName==leadName ? 1 : -1);
1333         sqlite3VdbeAddOp2(v, OP_AddImm, tmpReg, val);
1334       }else{
1335         int op = (pFunc->zName==leadName ? OP_Add : OP_Subtract);
1336         int tmpReg2 = sqlite3GetTempReg(pParse);
1337         sqlite3VdbeAddOp3(v, OP_Column, iEph, pWin->iArgCol+1, tmpReg2);
1338         sqlite3VdbeAddOp3(v, op, tmpReg2, tmpReg, tmpReg);
1339         sqlite3ReleaseTempReg(pParse, tmpReg2);
1340       }
1341
1342       sqlite3VdbeAddOp3(v, OP_SeekRowid, csr, lbl, tmpReg);
1343       VdbeCoverage(v);
1344       sqlite3VdbeAddOp3(v, OP_Column, csr, pWin->iArgCol, pWin->regResult);
1345       sqlite3VdbeResolveLabel(v, lbl);
1346       sqlite3ReleaseTempReg(pParse, tmpReg);
1347     }
1348   }
1349   sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrGosub);
1350 }
1351
1352 /*
1353 ** Invoke the code generated by windowReturnOneRow() and, optionally, the
1354 ** xInverse() function for each window function, for one or more rows
1355 ** from the Window.iEphCsr temp table. This routine generates VM code
1356 ** similar to:
1357 **
1358 **   while( regCtr>0 ){
1359 **     regCtr--;
1360 **     windowReturnOneRow()
1361 **     if( bInverse ){
1362 **       AggInverse
1363 **     }
1364 **     Next (Window.iEphCsr)
1365 **   }
1366 */
1367 static void windowReturnRows(
1368   Parse *pParse,
1369   Window *pMWin,                  /* List of window functions */
1370   int regCtr,                     /* Register containing number of rows */
1371   int regGosub,                   /* Register for Gosub addrGosub */
1372   int addrGosub,                  /* Address of sub-routine for ReturnOneRow */
1373   int regInvArg,                  /* Array of registers for xInverse args */
1374   int regInvSize                  /* Register containing size of partition */
1375 ){
1376   int addr;
1377   Vdbe *v = sqlite3GetVdbe(pParse);
1378   windowAggFinal(pParse, pMWin, 0);
1379   addr = sqlite3VdbeAddOp3(v, OP_IfPos, regCtr, sqlite3VdbeCurrentAddr(v)+2 ,1);
1380   VdbeCoverage(v);
1381   sqlite3VdbeAddOp2(v, OP_Goto, 0, 0);
1382   windowReturnOneRow(pParse, pMWin, regGosub, addrGosub);
1383   if( regInvArg ){
1384     windowAggStep(pParse, pMWin, pMWin->iEphCsr, 1, regInvArg, regInvSize);
1385   }
1386   sqlite3VdbeAddOp2(v, OP_Next, pMWin->iEphCsr, addr);
1387   VdbeCoverage(v);
1388   sqlite3VdbeJumpHere(v, addr+1);   /* The OP_Goto */
1389 }
1390
1391 /*
1392 ** Generate code to set the accumulator register for each window function
1393 ** in the linked list passed as the second argument to NULL. And perform
1394 ** any equivalent initialization required by any built-in window functions
1395 ** in the list.
1396 */
1397 static int windowInitAccum(Parse *pParse, Window *pMWin){
1398   Vdbe *v = sqlite3GetVdbe(pParse);
1399   int regArg;
1400   int nArg = 0;
1401   Window *pWin;
1402   for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
1403     FuncDef *pFunc = pWin->pFunc;
1404     sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);
1405     nArg = MAX(nArg, windowArgCount(pWin));
1406     if( pFunc->zName==nth_valueName
1407      || pFunc->zName==first_valueName
1408     ){
1409       sqlite3VdbeAddOp2(v, OP_Integer, 0, pWin->regApp);
1410       sqlite3VdbeAddOp2(v, OP_Integer, 0, pWin->regApp+1);
1411     }
1412
1413     if( (pFunc->funcFlags & SQLITE_FUNC_MINMAX) && pWin->csrApp ){
1414       assert( pWin->eStart!=TK_UNBOUNDED );
1415       sqlite3VdbeAddOp1(v, OP_ResetSorter, pWin->csrApp);
1416       sqlite3VdbeAddOp2(v, OP_Integer, 0, pWin->regApp+1);
1417     }
1418   }
1419   regArg = pParse->nMem+1;
1420   pParse->nMem += nArg;
1421   return regArg;
1422 }
1423
1424
1425 /*
1426 ** This function does the work of sqlite3WindowCodeStep() for all "ROWS"
1427 ** window frame types except for "BETWEEN UNBOUNDED PRECEDING AND CURRENT
1428 ** ROW". Pseudo-code for each follows.
1429 **
1430 ** ROWS BETWEEN <expr1> PRECEDING AND <expr2> FOLLOWING
1431 **
1432 **     ...
1433 **       if( new partition ){
1434 **         Gosub flush_partition
1435 **       }
1436 **       Insert (record in eph-table)
1437 **     sqlite3WhereEnd()
1438 **     Gosub flush_partition
1439 **
1440 **   flush_partition:
1441 **     Once {
1442 **       OpenDup (iEphCsr -> csrStart)
1443 **       OpenDup (iEphCsr -> csrEnd)
1444 **     }
1445 **     regStart = <expr1>                // PRECEDING expression
1446 **     regEnd = <expr2>                  // FOLLOWING expression
1447 **     if( regStart<0 || regEnd<0 ){ error! }
1448 **     Rewind (csr,csrStart,csrEnd)      // if EOF goto flush_partition_done
1449 **       Next(csrEnd)                    // if EOF skip Aggstep
1450 **       Aggstep (csrEnd)
1451 **       if( (regEnd--)<=0 ){
1452 **         AggFinal (xValue)
1453 **         Gosub addrGosub
1454 **         Next(csr)                // if EOF goto flush_partition_done
1455 **         if( (regStart--)<=0 ){
1456 **           AggInverse (csrStart)
1457 **           Next(csrStart)
1458 **         }
1459 **       }
1460 **   flush_partition_done:
1461 **     ResetSorter (csr)
1462 **     Return
1463 **
1464 ** ROWS BETWEEN <expr> PRECEDING    AND CURRENT ROW
1465 ** ROWS BETWEEN CURRENT ROW         AND <expr> FOLLOWING
1466 ** ROWS BETWEEN UNBOUNDED PRECEDING AND <expr> FOLLOWING
1467 **
1468 **   These are similar to the above. For "CURRENT ROW", intialize the
1469 **   register to 0. For "UNBOUNDED PRECEDING" to infinity.
1470 **
1471 ** ROWS BETWEEN <expr> PRECEDING    AND UNBOUNDED FOLLOWING
1472 ** ROWS BETWEEN CURRENT ROW         AND UNBOUNDED FOLLOWING
1473 **
1474 **     Rewind (csr,csrStart,csrEnd)    // if EOF goto flush_partition_done
1475 **     while( 1 ){
1476 **       Next(csrEnd)                  // Exit while(1) at EOF
1477 **       Aggstep (csrEnd)
1478 **     }
1479 **     while( 1 ){
1480 **       AggFinal (xValue)
1481 **       Gosub addrGosub
1482 **       Next(csr)                     // if EOF goto flush_partition_done
1483 **       if( (regStart--)<=0 ){
1484 **         AggInverse (csrStart)
1485 **         Next(csrStart)
1486 **       }
1487 **     }
1488 **
1489 **   For the "CURRENT ROW AND UNBOUNDED FOLLOWING" case, the final if()
1490 **   condition is always true (as if regStart were initialized to 0).
1491 **
1492 ** RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
1493 **
1494 **   This is the only RANGE case handled by this routine. It modifies the
1495 **   second while( 1 ) loop in "ROWS BETWEEN CURRENT ... UNBOUNDED..." to
1496 **   be:
1497 **
1498 **     while( 1 ){
1499 **       AggFinal (xValue)
1500 **       while( 1 ){
1501 **         regPeer++
1502 **         Gosub addrGosub
1503 **         Next(csr)                     // if EOF goto flush_partition_done
1504 **         if( new peer ) break;
1505 **       }
1506 **       while( (regPeer--)>0 ){
1507 **         AggInverse (csrStart)
1508 **         Next(csrStart)
1509 **       }
1510 **     }
1511 **
1512 ** ROWS BETWEEN <expr> FOLLOWING    AND <expr> FOLLOWING
1513 **
1514 **   regEnd = regEnd - regStart
1515 **   Rewind (csr,csrStart,csrEnd)   // if EOF goto flush_partition_done
1516 **     Aggstep (csrEnd)
1517 **     Next(csrEnd)                 // if EOF fall-through
1518 **     if( (regEnd--)<=0 ){
1519 **       if( (regStart--)<=0 ){
1520 **         AggFinal (xValue)
1521 **         Gosub addrGosub
1522 **         Next(csr)              // if EOF goto flush_partition_done
1523 **       }
1524 **       AggInverse (csrStart)
1525 **       Next (csrStart)
1526 **     }
1527 **
1528 ** ROWS BETWEEN <expr> PRECEDING    AND <expr> PRECEDING
1529 **
1530 **   Replace the bit after "Rewind" in the above with:
1531 **
1532 **     if( (regEnd--)<=0 ){
1533 **       AggStep (csrEnd)
1534 **       Next (csrEnd)
1535 **     }
1536 **     AggFinal (xValue)
1537 **     Gosub addrGosub
1538 **     Next(csr)                  // if EOF goto flush_partition_done
1539 **     if( (regStart--)<=0 ){
1540 **       AggInverse (csr2)
1541 **       Next (csr2)
1542 **     }
1543 **
1544 */
1545 static void windowCodeRowExprStep(
1546   Parse *pParse,
1547   Select *p,
1548   WhereInfo *pWInfo,
1549   int regGosub,
1550   int addrGosub
1551 ){
1552   Window *pMWin = p->pWin;
1553   Vdbe *v = sqlite3GetVdbe(pParse);
1554   int regFlushPart;               /* Register for "Gosub flush_partition" */
1555   int lblFlushPart;               /* Label for "Gosub flush_partition" */
1556   int lblFlushDone;               /* Label for "Gosub flush_partition_done" */
1557
1558   int regArg;
1559   int addr;
1560   int csrStart = pParse->nTab++;
1561   int csrEnd = pParse->nTab++;
1562   int regStart;                    /* Value of <expr> PRECEDING */
1563   int regEnd;                      /* Value of <expr> FOLLOWING */
1564   int addrGoto;
1565   int addrTop;
1566   int addrIfPos1 = 0;
1567   int addrIfPos2 = 0;
1568   int regSize = 0;
1569
1570   assert( pMWin->eStart==TK_PRECEDING
1571        || pMWin->eStart==TK_CURRENT
1572        || pMWin->eStart==TK_FOLLOWING
1573        || pMWin->eStart==TK_UNBOUNDED
1574   );
1575   assert( pMWin->eEnd==TK_FOLLOWING
1576        || pMWin->eEnd==TK_CURRENT
1577        || pMWin->eEnd==TK_UNBOUNDED
1578        || pMWin->eEnd==TK_PRECEDING
1579   );
1580
1581   /* Allocate register and label for the "flush_partition" sub-routine. */
1582   regFlushPart = ++pParse->nMem;
1583   lblFlushPart = sqlite3VdbeMakeLabel(v);
1584   lblFlushDone = sqlite3VdbeMakeLabel(v);
1585
1586   regStart = ++pParse->nMem;
1587   regEnd = ++pParse->nMem;
1588
1589   windowPartitionCache(pParse, p, pWInfo, regFlushPart, lblFlushPart, &regSize);
1590
1591   addrGoto = sqlite3VdbeAddOp0(v, OP_Goto);
1592
1593   /* Start of "flush_partition" */
1594   sqlite3VdbeResolveLabel(v, lblFlushPart);
1595   sqlite3VdbeAddOp2(v, OP_Once, 0, sqlite3VdbeCurrentAddr(v)+3);
1596   VdbeCoverage(v);
1597   VdbeComment((v, "Flush_partition subroutine"));
1598   sqlite3VdbeAddOp2(v, OP_OpenDup, csrStart, pMWin->iEphCsr);
1599   sqlite3VdbeAddOp2(v, OP_OpenDup, csrEnd, pMWin->iEphCsr);
1600
1601   /* If either regStart or regEnd are not non-negative integers, throw
1602   ** an exception.  */
1603   if( pMWin->pStart ){
1604     sqlite3ExprCode(pParse, pMWin->pStart, regStart);
1605     windowCheckIntValue(pParse, regStart, 0);
1606   }
1607   if( pMWin->pEnd ){
1608     sqlite3ExprCode(pParse, pMWin->pEnd, regEnd);
1609     windowCheckIntValue(pParse, regEnd, 1);
1610   }
1611
1612   /* If this is "ROWS <expr1> FOLLOWING AND ROWS <expr2> FOLLOWING", do:
1613   **
1614   **   if( regEnd<regStart ){
1615   **     // The frame always consists of 0 rows
1616   **     regStart = regSize;
1617   **   }
1618   **   regEnd = regEnd - regStart;
1619   */
1620   if( pMWin->pEnd && pMWin->eStart==TK_FOLLOWING ){
1621     assert( pMWin->pStart!=0 );
1622     assert( pMWin->eEnd==TK_FOLLOWING );
1623     sqlite3VdbeAddOp3(v, OP_Ge, regStart, sqlite3VdbeCurrentAddr(v)+2, regEnd);
1624     VdbeCoverageNeverNull(v);
1625     sqlite3VdbeAddOp2(v, OP_Copy, regSize, regStart);
1626     sqlite3VdbeAddOp3(v, OP_Subtract, regStart, regEnd, regEnd);
1627   }
1628
1629   if( pMWin->pStart && pMWin->eEnd==TK_PRECEDING ){
1630     assert( pMWin->pEnd!=0 );
1631     assert( pMWin->eStart==TK_PRECEDING );
1632     sqlite3VdbeAddOp3(v, OP_Le, regStart, sqlite3VdbeCurrentAddr(v)+3, regEnd);
1633     VdbeCoverageNeverNull(v);
1634     sqlite3VdbeAddOp2(v, OP_Copy, regSize, regStart);
1635     sqlite3VdbeAddOp2(v, OP_Copy, regSize, regEnd);
1636   }
1637
1638   /* Initialize the accumulator register for each window function to NULL */
1639   regArg = windowInitAccum(pParse, pMWin);
1640
1641   sqlite3VdbeAddOp2(v, OP_Rewind, pMWin->iEphCsr, lblFlushDone);
1642   VdbeCoverage(v);
1643   sqlite3VdbeAddOp2(v, OP_Rewind, csrStart, lblFlushDone);
1644   VdbeCoverageNeverTaken(v);
1645   sqlite3VdbeChangeP5(v, 1);
1646   sqlite3VdbeAddOp2(v, OP_Rewind, csrEnd, lblFlushDone);
1647   VdbeCoverageNeverTaken(v);
1648   sqlite3VdbeChangeP5(v, 1);
1649
1650   /* Invoke AggStep function for each window function using the row that
1651   ** csrEnd currently points to. Or, if csrEnd is already at EOF,
1652   ** do nothing.  */
1653   addrTop = sqlite3VdbeCurrentAddr(v);
1654   if( pMWin->eEnd==TK_PRECEDING ){
1655     addrIfPos1 = sqlite3VdbeAddOp3(v, OP_IfPos, regEnd, 0 , 1);
1656     VdbeCoverage(v);
1657   }
1658   sqlite3VdbeAddOp2(v, OP_Next, csrEnd, sqlite3VdbeCurrentAddr(v)+2);
1659   VdbeCoverage(v);
1660   addr = sqlite3VdbeAddOp0(v, OP_Goto);
1661   windowAggStep(pParse, pMWin, csrEnd, 0, regArg, regSize);
1662   if( pMWin->eEnd==TK_UNBOUNDED ){
1663     sqlite3VdbeAddOp2(v, OP_Goto, 0, addrTop);
1664     sqlite3VdbeJumpHere(v, addr);
1665     addrTop = sqlite3VdbeCurrentAddr(v);
1666   }else{
1667     sqlite3VdbeJumpHere(v, addr);
1668     if( pMWin->eEnd==TK_PRECEDING ){
1669       sqlite3VdbeJumpHere(v, addrIfPos1);
1670     }
1671   }
1672
1673   if( pMWin->eEnd==TK_FOLLOWING ){
1674     addrIfPos1 = sqlite3VdbeAddOp3(v, OP_IfPos, regEnd, 0 , 1);
1675     VdbeCoverage(v);
1676   }
1677   if( pMWin->eStart==TK_FOLLOWING ){
1678     addrIfPos2 = sqlite3VdbeAddOp3(v, OP_IfPos, regStart, 0 , 1);
1679     VdbeCoverage(v);
1680   }
1681   windowAggFinal(pParse, pMWin, 0);
1682   windowReturnOneRow(pParse, pMWin, regGosub, addrGosub);
1683   sqlite3VdbeAddOp2(v, OP_Next, pMWin->iEphCsr, sqlite3VdbeCurrentAddr(v)+2);
1684   VdbeCoverage(v);
1685   sqlite3VdbeAddOp2(v, OP_Goto, 0, lblFlushDone);
1686   if( pMWin->eStart==TK_FOLLOWING ){
1687     sqlite3VdbeJumpHere(v, addrIfPos2);
1688   }
1689
1690   if( pMWin->eStart==TK_CURRENT
1691    || pMWin->eStart==TK_PRECEDING
1692    || pMWin->eStart==TK_FOLLOWING
1693   ){
1694     int lblSkipInverse = sqlite3VdbeMakeLabel(v);;
1695     if( pMWin->eStart==TK_PRECEDING ){
1696       sqlite3VdbeAddOp3(v, OP_IfPos, regStart, lblSkipInverse, 1);
1697       VdbeCoverage(v);
1698     }
1699     if( pMWin->eStart==TK_FOLLOWING ){
1700       sqlite3VdbeAddOp2(v, OP_Next, csrStart, sqlite3VdbeCurrentAddr(v)+2);
1701       VdbeCoverage(v);
1702       sqlite3VdbeAddOp2(v, OP_Goto, 0, lblSkipInverse);
1703     }else{
1704       sqlite3VdbeAddOp2(v, OP_Next, csrStart, sqlite3VdbeCurrentAddr(v)+1);
1705       VdbeCoverage(v);
1706     }
1707     windowAggStep(pParse, pMWin, csrStart, 1, regArg, regSize);
1708     sqlite3VdbeResolveLabel(v, lblSkipInverse);
1709   }
1710   if( pMWin->eEnd==TK_FOLLOWING ){
1711     sqlite3VdbeJumpHere(v, addrIfPos1);
1712   }
1713   sqlite3VdbeAddOp2(v, OP_Goto, 0, addrTop);
1714
1715   /* flush_partition_done: */
1716   sqlite3VdbeResolveLabel(v, lblFlushDone);
1717   sqlite3VdbeAddOp1(v, OP_ResetSorter, pMWin->iEphCsr);
1718   sqlite3VdbeAddOp1(v, OP_Return, regFlushPart);
1719   VdbeComment((v, "end flush_partition subroutine"));
1720
1721   /* Jump to here to skip over flush_partition */
1722   sqlite3VdbeJumpHere(v, addrGoto);
1723 }
1724
1725 /*
1726 ** This function does the work of sqlite3WindowCodeStep() for cases that
1727 ** would normally be handled by windowCodeDefaultStep() when there are
1728 ** one or more built-in window-functions that require the entire partition
1729 ** to be cached in a temp table before any rows can be returned. Additionally.
1730 ** "RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING" is always handled by
1731 ** this function.
1732 **
1733 ** Pseudo-code corresponding to the VM code generated by this function
1734 ** for each type of window follows.
1735 **
1736 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1737 **
1738 **   flush_partition:
1739 **     Once {
1740 **       OpenDup (iEphCsr -> csrLead)
1741 **     }
1742 **     Integer ctr 0
1743 **     foreach row (csrLead){
1744 **       if( new peer ){
1745 **         AggFinal (xValue)
1746 **         for(i=0; i<ctr; i++){
1747 **           Gosub addrGosub
1748 **           Next iEphCsr
1749 **         }
1750 **         Integer ctr 0
1751 **       }
1752 **       AggStep (csrLead)
1753 **       Incr ctr
1754 **     }
1755 **
1756 **     AggFinal (xFinalize)
1757 **     for(i=0; i<ctr; i++){
1758 **       Gosub addrGosub
1759 **       Next iEphCsr
1760 **     }
1761 **
1762 **     ResetSorter (csr)
1763 **     Return
1764 **
1765 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1766 **
1767 **   As above, except that the "if( new peer )" branch is always taken.
1768 **
1769 ** RANGE BETWEEN CURRENT ROW AND CURRENT ROW
1770 **
1771 **   As above, except that each of the for() loops becomes:
1772 **
1773 **         for(i=0; i<ctr; i++){
1774 **           Gosub addrGosub
1775 **           AggInverse (iEphCsr)
1776 **           Next iEphCsr
1777 **         }
1778 **
1779 ** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
1780 **
1781 **   flush_partition:
1782 **     Once {
1783 **       OpenDup (iEphCsr -> csrLead)
1784 **     }
1785 **     foreach row (csrLead) {
1786 **       AggStep (csrLead)
1787 **     }
1788 **     foreach row (iEphCsr) {
1789 **       Gosub addrGosub
1790 **     }
1791 **
1792 ** RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
1793 **
1794 **   flush_partition:
1795 **     Once {
1796 **       OpenDup (iEphCsr -> csrLead)
1797 **     }
1798 **     foreach row (csrLead){
1799 **       AggStep (csrLead)
1800 **     }
1801 **     Rewind (csrLead)
1802 **     Integer ctr 0
1803 **     foreach row (csrLead){
1804 **       if( new peer ){
1805 **         AggFinal (xValue)
1806 **         for(i=0; i<ctr; i++){
1807 **           Gosub addrGosub
1808 **           AggInverse (iEphCsr)
1809 **           Next iEphCsr
1810 **         }
1811 **         Integer ctr 0
1812 **       }
1813 **       Incr ctr
1814 **     }
1815 **
1816 **     AggFinal (xFinalize)
1817 **     for(i=0; i<ctr; i++){
1818 **       Gosub addrGosub
1819 **       Next iEphCsr
1820 **     }
1821 **
1822 **     ResetSorter (csr)
1823 **     Return
1824 */
1825 static void windowCodeCacheStep(
1826   Parse *pParse,
1827   Select *p,
1828   WhereInfo *pWInfo,
1829   int regGosub,
1830   int addrGosub
1831 ){
1832   Window *pMWin = p->pWin;
1833   Vdbe *v = sqlite3GetVdbe(pParse);
1834   int k;
1835   int addr;
1836   ExprList *pPart = pMWin->pPartition;
1837   ExprList *pOrderBy = pMWin->pOrderBy;
1838   int nPeer = pOrderBy ? pOrderBy->nExpr : 0;
1839   int regNewPeer;
1840
1841   int addrGoto;                   /* Address of Goto used to jump flush_par.. */
1842   int addrNext;                   /* Jump here for next iteration of loop */
1843   int regFlushPart;
1844   int lblFlushPart;
1845   int csrLead;
1846   int regCtr;
1847   int regArg;                     /* Register array to martial function args */
1848   int regSize;
1849   int lblEmpty;
1850   int bReverse = pMWin->pOrderBy && pMWin->eStart==TK_CURRENT
1851           && pMWin->eEnd==TK_UNBOUNDED;
1852
1853   assert( (pMWin->eStart==TK_UNBOUNDED && pMWin->eEnd==TK_CURRENT)
1854        || (pMWin->eStart==TK_UNBOUNDED && pMWin->eEnd==TK_UNBOUNDED)
1855        || (pMWin->eStart==TK_CURRENT && pMWin->eEnd==TK_CURRENT)
1856        || (pMWin->eStart==TK_CURRENT && pMWin->eEnd==TK_UNBOUNDED)
1857   );
1858
1859   lblEmpty = sqlite3VdbeMakeLabel(v);
1860   regNewPeer = pParse->nMem+1;
1861   pParse->nMem += nPeer;
1862
1863   /* Allocate register and label for the "flush_partition" sub-routine. */
1864   regFlushPart = ++pParse->nMem;
1865   lblFlushPart = sqlite3VdbeMakeLabel(v);
1866
1867   csrLead = pParse->nTab++;
1868   regCtr = ++pParse->nMem;
1869
1870   windowPartitionCache(pParse, p, pWInfo, regFlushPart, lblFlushPart, &regSize);
1871   addrGoto = sqlite3VdbeAddOp0(v, OP_Goto);
1872
1873   /* Start of "flush_partition" */
1874   sqlite3VdbeResolveLabel(v, lblFlushPart);
1875   sqlite3VdbeAddOp2(v, OP_Once, 0, sqlite3VdbeCurrentAddr(v)+2);
1876   VdbeCoverage(v);
1877   sqlite3VdbeAddOp2(v, OP_OpenDup, csrLead, pMWin->iEphCsr);
1878
1879   /* Initialize the accumulator register for each window function to NULL */
1880   regArg = windowInitAccum(pParse, pMWin);
1881
1882   sqlite3VdbeAddOp2(v, OP_Integer, 0, regCtr);
1883   sqlite3VdbeAddOp2(v, OP_Rewind, csrLead, lblEmpty);
1884   VdbeCoverage(v);
1885   sqlite3VdbeAddOp2(v, OP_Rewind, pMWin->iEphCsr, lblEmpty);
1886   VdbeCoverageNeverTaken(v);
1887
1888   if( bReverse ){
1889     int addr2 = sqlite3VdbeCurrentAddr(v);
1890     windowAggStep(pParse, pMWin, csrLead, 0, regArg, regSize);
1891     sqlite3VdbeAddOp2(v, OP_Next, csrLead, addr2);
1892     VdbeCoverage(v);
1893     sqlite3VdbeAddOp2(v, OP_Rewind, csrLead, lblEmpty);
1894     VdbeCoverageNeverTaken(v);
1895   }
1896   addrNext = sqlite3VdbeCurrentAddr(v);
1897
1898   if( pOrderBy && (pMWin->eEnd==TK_CURRENT || pMWin->eStart==TK_CURRENT) ){
1899     int bCurrent = (pMWin->eStart==TK_CURRENT);
1900     int addrJump = 0;             /* Address of OP_Jump below */
1901     if( pMWin->eType==TK_RANGE ){
1902       int iOff = pMWin->nBufferCol + (pPart ? pPart->nExpr : 0);
1903       int regPeer = pMWin->regPart + (pPart ? pPart->nExpr : 0);
1904       KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pOrderBy, 0, 0);
1905       for(k=0; k<nPeer; k++){
1906         sqlite3VdbeAddOp3(v, OP_Column, csrLead, iOff+k, regNewPeer+k);
1907       }
1908       addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPeer, regPeer, nPeer);
1909       sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
1910       addrJump = sqlite3VdbeAddOp3(v, OP_Jump, addr+2, 0, addr+2);
1911       VdbeCoverage(v);
1912       sqlite3VdbeAddOp3(v, OP_Copy, regNewPeer, regPeer, nPeer-1);
1913     }
1914
1915     windowReturnRows(pParse, pMWin, regCtr, regGosub, addrGosub,
1916         (bCurrent ? regArg : 0), (bCurrent ? regSize : 0)
1917     );
1918     if( addrJump ) sqlite3VdbeJumpHere(v, addrJump);
1919   }
1920
1921   if( bReverse==0 ){
1922     windowAggStep(pParse, pMWin, csrLead, 0, regArg, regSize);
1923   }
1924   sqlite3VdbeAddOp2(v, OP_AddImm, regCtr, 1);
1925   sqlite3VdbeAddOp2(v, OP_Next, csrLead, addrNext);
1926   VdbeCoverage(v);
1927
1928   windowReturnRows(pParse, pMWin, regCtr, regGosub, addrGosub, 0, 0);
1929
1930   sqlite3VdbeResolveLabel(v, lblEmpty);
1931   sqlite3VdbeAddOp1(v, OP_ResetSorter, pMWin->iEphCsr);
1932   sqlite3VdbeAddOp1(v, OP_Return, regFlushPart);
1933
1934   /* Jump to here to skip over flush_partition */
1935   sqlite3VdbeJumpHere(v, addrGoto);
1936 }
1937
1938
1939 /*
1940 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1941 **
1942 **   ...
1943 **     if( new partition ){
1944 **       AggFinal (xFinalize)
1945 **       Gosub addrGosub
1946 **       ResetSorter eph-table
1947 **     }
1948 **     else if( new peer ){
1949 **       AggFinal (xValue)
1950 **       Gosub addrGosub
1951 **       ResetSorter eph-table
1952 **     }
1953 **     AggStep
1954 **     Insert (record into eph-table)
1955 **   sqlite3WhereEnd()
1956 **   AggFinal (xFinalize)
1957 **   Gosub addrGosub
1958 **
1959 ** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
1960 **
1961 **   As above, except take no action for a "new peer". Invoke
1962 **   the sub-routine once only for each partition.
1963 **
1964 ** RANGE BETWEEN CURRENT ROW AND CURRENT ROW
1965 **
1966 **   As above, except that the "new peer" condition is handled in the
1967 **   same way as "new partition" (so there is no "else if" block).
1968 **
1969 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1970 **
1971 **   As above, except assume every row is a "new peer".
1972 */
1973 static void windowCodeDefaultStep(
1974   Parse *pParse,
1975   Select *p,
1976   WhereInfo *pWInfo,
1977   int regGosub,
1978   int addrGosub
1979 ){
1980   Window *pMWin = p->pWin;
1981   Vdbe *v = sqlite3GetVdbe(pParse);
1982   int k;
1983   int iSubCsr = p->pSrc->a[0].iCursor;
1984   int nSub = p->pSrc->a[0].pTab->nCol;
1985   int reg = pParse->nMem+1;
1986   int regRecord = reg+nSub;
1987   int regRowid = regRecord+1;
1988   int addr;
1989   ExprList *pPart = pMWin->pPartition;
1990   ExprList *pOrderBy = pMWin->pOrderBy;
1991
1992   assert( pMWin->eType==TK_RANGE
1993       || (pMWin->eStart==TK_UNBOUNDED && pMWin->eEnd==TK_CURRENT)
1994   );
1995
1996   assert( (pMWin->eStart==TK_UNBOUNDED && pMWin->eEnd==TK_CURRENT)
1997        || (pMWin->eStart==TK_UNBOUNDED && pMWin->eEnd==TK_UNBOUNDED)
1998        || (pMWin->eStart==TK_CURRENT && pMWin->eEnd==TK_CURRENT)
1999        || (pMWin->eStart==TK_CURRENT && pMWin->eEnd==TK_UNBOUNDED && !pOrderBy)
2000   );
2001
2002   if( pMWin->eEnd==TK_UNBOUNDED ){
2003     pOrderBy = 0;
2004   }
2005
2006   pParse->nMem += nSub + 2;
2007
2008   /* Martial the row returned by the sub-select into an array of
2009   ** registers. */
2010   for(k=0; k<nSub; k++){
2011     sqlite3VdbeAddOp3(v, OP_Column, iSubCsr, k, reg+k);
2012   }
2013
2014   /* Check if this is the start of a new partition or peer group. */
2015   if( pPart || pOrderBy ){
2016     int nPart = (pPart ? pPart->nExpr : 0);
2017     int addrGoto = 0;
2018     int addrJump = 0;
2019     int nPeer = (pOrderBy ? pOrderBy->nExpr : 0);
2020
2021     if( pPart ){
2022       int regNewPart = reg + pMWin->nBufferCol;
2023       KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pPart, 0, 0);
2024       addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPart, pMWin->regPart,nPart);
2025       sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
2026       addrJump = sqlite3VdbeAddOp3(v, OP_Jump, addr+2, 0, addr+2);
2027       VdbeCoverage(v);
2028       windowAggFinal(pParse, pMWin, 1);
2029       if( pOrderBy ){
2030         addrGoto = sqlite3VdbeAddOp0(v, OP_Goto);
2031       }
2032     }
2033
2034     if( pOrderBy ){
2035       int regNewPeer = reg + pMWin->nBufferCol + nPart;
2036       int regPeer = pMWin->regPart + nPart;
2037
2038       if( addrJump ) sqlite3VdbeJumpHere(v, addrJump);
2039       if( pMWin->eType==TK_RANGE ){
2040         KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pOrderBy, 0, 0);
2041         addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPeer, regPeer, nPeer);
2042         sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
2043         addrJump = sqlite3VdbeAddOp3(v, OP_Jump, addr+2, 0, addr+2);
2044         VdbeCoverage(v);
2045       }else{
2046         addrJump = 0;
2047       }
2048       windowAggFinal(pParse, pMWin, pMWin->eStart==TK_CURRENT);
2049       if( addrGoto ) sqlite3VdbeJumpHere(v, addrGoto);
2050     }
2051
2052     sqlite3VdbeAddOp2(v, OP_Rewind, pMWin->iEphCsr,sqlite3VdbeCurrentAddr(v)+3);
2053     VdbeCoverage(v);
2054     sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrGosub);
2055     sqlite3VdbeAddOp2(v, OP_Next, pMWin->iEphCsr, sqlite3VdbeCurrentAddr(v)-1);
2056     VdbeCoverage(v);
2057
2058     sqlite3VdbeAddOp1(v, OP_ResetSorter, pMWin->iEphCsr);
2059     sqlite3VdbeAddOp3(
2060         v, OP_Copy, reg+pMWin->nBufferCol, pMWin->regPart, nPart+nPeer-1
2061     );
2062
2063     if( addrJump ) sqlite3VdbeJumpHere(v, addrJump);
2064   }
2065
2066   /* Invoke step function for window functions */
2067   windowAggStep(pParse, pMWin, -1, 0, reg, 0);
2068
2069   /* Buffer the current row in the ephemeral table. */
2070   if( pMWin->nBufferCol>0 ){
2071     sqlite3VdbeAddOp3(v, OP_MakeRecord, reg, pMWin->nBufferCol, regRecord);
2072   }else{
2073     sqlite3VdbeAddOp2(v, OP_Blob, 0, regRecord);
2074     sqlite3VdbeAppendP4(v, (void*)"", 0);
2075   }
2076   sqlite3VdbeAddOp2(v, OP_NewRowid, pMWin->iEphCsr, regRowid);
2077   sqlite3VdbeAddOp3(v, OP_Insert, pMWin->iEphCsr, regRecord, regRowid);
2078
2079   /* End the database scan loop. */
2080   sqlite3WhereEnd(pWInfo);
2081
2082   windowAggFinal(pParse, pMWin, 1);
2083   sqlite3VdbeAddOp2(v, OP_Rewind, pMWin->iEphCsr,sqlite3VdbeCurrentAddr(v)+3);
2084   VdbeCoverage(v);
2085   sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrGosub);
2086   sqlite3VdbeAddOp2(v, OP_Next, pMWin->iEphCsr, sqlite3VdbeCurrentAddr(v)-1);
2087   VdbeCoverage(v);
2088 }
2089
2090 /*
2091 ** Allocate and return a duplicate of the Window object indicated by the
2092 ** third argument. Set the Window.pOwner field of the new object to
2093 ** pOwner.
2094 */
2095 Window *sqlite3WindowDup(sqlite3 *db, Expr *pOwner, Window *p){
2096   Window *pNew = 0;
2097   if( p ){
2098     pNew = sqlite3DbMallocZero(db, sizeof(Window));
2099     if( pNew ){
2100       pNew->zName = sqlite3DbStrDup(db, p->zName);
2101       pNew->pFilter = sqlite3ExprDup(db, p->pFilter, 0);
2102       pNew->pPartition = sqlite3ExprListDup(db, p->pPartition, 0);
2103       pNew->pOrderBy = sqlite3ExprListDup(db, p->pOrderBy, 0);
2104       pNew->eType = p->eType;
2105       pNew->eEnd = p->eEnd;
2106       pNew->eStart = p->eStart;
2107       pNew->pStart = sqlite3ExprDup(db, p->pStart, 0);
2108       pNew->pEnd = sqlite3ExprDup(db, p->pEnd, 0);
2109       pNew->pOwner = pOwner;
2110     }
2111   }
2112   return pNew;
2113 }
2114
2115 /*
2116 ** Return a copy of the linked list of Window objects passed as the
2117 ** second argument.
2118 */
2119 Window *sqlite3WindowListDup(sqlite3 *db, Window *p){
2120   Window *pWin;
2121   Window *pRet = 0;
2122   Window **pp = &pRet;
2123
2124   for(pWin=p; pWin; pWin=pWin->pNextWin){
2125     *pp = sqlite3WindowDup(db, 0, pWin);
2126     if( *pp==0 ) break;
2127     pp = &((*pp)->pNextWin);
2128   }
2129
2130   return pRet;
2131 }
2132
2133 /*
2134 ** sqlite3WhereBegin() has already been called for the SELECT statement
2135 ** passed as the second argument when this function is invoked. It generates
2136 ** code to populate the Window.regResult register for each window function and
2137 ** invoke the sub-routine at instruction addrGosub once for each row.
2138 ** This function calls sqlite3WhereEnd() before returning.
2139 */
2140 void sqlite3WindowCodeStep(
2141   Parse *pParse,                  /* Parse context */
2142   Select *p,                      /* Rewritten SELECT statement */
2143   WhereInfo *pWInfo,              /* Context returned by sqlite3WhereBegin() */
2144   int regGosub,                   /* Register for OP_Gosub */
2145   int addrGosub                   /* OP_Gosub here to return each row */
2146 ){
2147   Window *pMWin = p->pWin;
2148
2149   /* There are three different functions that may be used to do the work
2150   ** of this one, depending on the window frame and the specific built-in
2151   ** window functions used (if any).
2152   **
2153   ** windowCodeRowExprStep() handles all "ROWS" window frames, except for:
2154   **
2155   **   ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
2156   **
2157   ** The exception is because windowCodeRowExprStep() implements all window
2158   ** frame types by caching the entire partition in a temp table, and
2159   ** "ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW" is easy enough to
2160   ** implement without such a cache.
2161   **
2162   ** windowCodeCacheStep() is used for:
2163   **
2164   **   RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
2165   **
2166   ** It is also used for anything not handled by windowCodeRowExprStep()
2167   ** that invokes a built-in window function that requires the entire
2168   ** partition to be cached in a temp table before any rows are returned
2169   ** (e.g. nth_value() or percent_rank()).
2170   **
2171   ** Finally, assuming there is no built-in window function that requires
2172   ** the partition to be cached, windowCodeDefaultStep() is used for:
2173   **
2174   **   RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
2175   **   RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
2176   **   RANGE BETWEEN CURRENT ROW AND CURRENT ROW
2177   **   ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
2178   **
2179   ** windowCodeDefaultStep() is the only one of the three functions that
2180   ** does not cache each partition in a temp table before beginning to
2181   ** return rows.
2182   */
2183   if( pMWin->eType==TK_ROWS
2184    && (pMWin->eStart!=TK_UNBOUNDED||pMWin->eEnd!=TK_CURRENT||!pMWin->pOrderBy)
2185   ){
2186     windowCodeRowExprStep(pParse, p, pWInfo, regGosub, addrGosub);
2187   }else{
2188     Window *pWin;
2189     int bCache = 0;               /* True to use CacheStep() */
2190
2191     if( pMWin->eStart==TK_CURRENT && pMWin->eEnd==TK_UNBOUNDED ){
2192       bCache = 1;
2193     }else{
2194       for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
2195         FuncDef *pFunc = pWin->pFunc;
2196         if( (pFunc->funcFlags & SQLITE_FUNC_WINDOW_SIZE)
2197          || (pFunc->zName==nth_valueName)
2198          || (pFunc->zName==first_valueName)
2199          || (pFunc->zName==leadName)
2200          || (pFunc->zName==lagName)
2201         ){
2202           bCache = 1;
2203           break;
2204         }
2205       }
2206     }
2207
2208     /* Otherwise, call windowCodeDefaultStep().  */
2209     if( bCache ){
2210       windowCodeCacheStep(pParse, p, pWInfo, regGosub, addrGosub);
2211     }else{
2212       windowCodeDefaultStep(pParse, p, pWInfo, regGosub, addrGosub);
2213     }
2214   }
2215 }
2216
2217 #endif /* SQLITE_OMIT_WINDOWFUNC */