src/window.c

   1 /*
   2 **
   3 ** The author disclaims copyright to this source code.  In place of
   4 ** a legal notice, here is a blessing:
   5 **
   6 **    May you do good and not evil.
   7 **    May you find forgiveness for yourself and forgive others.
   8 **    May you share freely, never taking more than you give.
   9 **
  10 *************************************************************************
  11 */
  12 #include "sqliteInt.h"
  13
  14 /*
  15 ** Implementation of built-in window function row_number(). Assumes that the
  16 ** window frame has been coerced to:
  17 **
  18 **   ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
  19 */
  20 static void row_numberStepFunc(
  21   sqlite3_context *pCtx,
  22   int nArg,
  23   sqlite3_value **apArg
  24 ){
  25   i64 *p = (i64*)sqlite3_aggregate_context(pCtx, sizeof(*p));
  26   if( p ) (*p)++;
  27 }
  28 static void row_numberInverseFunc(
  29   sqlite3_context *pCtx,
  30   int nArg,
  31   sqlite3_value **apArg
  32 ){
  33 }
  34 static void row_numberValueFunc(sqlite3_context *pCtx){
  35   i64 *p = (i64*)sqlite3_aggregate_context(pCtx, sizeof(*p));
  36   sqlite3_result_int64(pCtx, (p ? *p : 0));
  37 }
  38
  39 /*
  40 ** Context object type used by rank() and dense_rank().
  41 */
  42 struct CallCount {
  43   i64 nValue;
  44   i64 nStep;
  45   i64 nTotal;
  46 };
  47
  48 /*
  49 ** Implementation of built-in window function dense_rank().
  50 */
  51 static void dense_rankStepFunc(
  52   sqlite3_context *pCtx,
  53   int nArg,
  54   sqlite3_value **apArg
  55 ){
  56   struct CallCount *p;
  57   p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
  58   if( p ) p->nStep = 1;
  59 }
  60 static void dense_rankInverseFunc(
  61   sqlite3_context *pCtx,
  62   int nArg,
  63   sqlite3_value **apArg
  64 ){
  65 }
  66 static void dense_rankValueFunc(sqlite3_context *pCtx){
  67   struct CallCount *p;
  68   p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
  69   if( p ){
  70     if( p->nStep ){
  71       p->nValue++;
  72       p->nStep = 0;
  73     }
  74     sqlite3_result_int64(pCtx, p->nValue);
  75   }
  76 }
  77
  78 /*
  79 ** Implementation of built-in window function rank().
  80 */
  81 static void rankStepFunc(
  82   sqlite3_context *pCtx,
  83   int nArg,
  84   sqlite3_value **apArg
  85 ){
  86   struct CallCount *p;
  87   p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
  88   if( p ){
  89     p->nStep++;
  90     if( p->nValue==0 ){
  91       p->nValue = p->nStep;
  92     }
  93   }
  94 }
  95 static void rankInverseFunc(
  96   sqlite3_context *pCtx,
  97   int nArg,
  98   sqlite3_value **apArg
  99 ){
 100 }
 101 static void rankValueFunc(sqlite3_context *pCtx){
 102   struct CallCount *p;
 103   p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
 104   if( p ){
 105     sqlite3_result_int64(pCtx, p->nValue);
 106     p->nValue = 0;
 107   }
 108 }
 109
 110 /*
 111 ** Implementation of built-in window function percent_rank().
 112 */
 113 static void percent_rankStepFunc(
 114   sqlite3_context *pCtx,
 115   int nArg,
 116   sqlite3_value **apArg
 117 ){
 118   struct CallCount *p;
 119   assert( nArg==1 );
 120
 121   p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
 122   if( p ){
 123     if( p->nTotal==0 ){
 124       p->nTotal = sqlite3_value_int64(apArg[0]);
 125     }
 126     p->nStep++;
 127     if( p->nValue==0 ){
 128       p->nValue = p->nStep;
 129     }
 130   }
 131 }
 132 static void percent_rankInverseFunc(
 133   sqlite3_context *pCtx,
 134   int nArg,
 135   sqlite3_value **apArg
 136 ){
 137 }
 138 static void percent_rankValueFunc(sqlite3_context *pCtx){
 139   struct CallCount *p;
 140   p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
 141   if( p ){
 142     if( p->nTotal>1 ){
 143       double r = (double)(p->nValue-1) / (double)(p->nTotal-1);
 144       sqlite3_result_double(pCtx, r);
 145     }else{
 146       sqlite3_result_double(pCtx, 100.0);
 147     }
 148     p->nValue = 0;
 149   }
 150 }
 151
 152 static void nth_valueStepFunc(
 153   sqlite3_context *pCtx,
 154   int nArg,
 155   sqlite3_value **apArg
 156 ){
 157 }
 158 static void nth_valueInverseFunc(
 159   sqlite3_context *pCtx,
 160   int nArg,
 161   sqlite3_value **apArg
 162 ){
 163 }
 164 static void nth_valueValueFunc(sqlite3_context *pCtx){
 165 }
 166
 167 #define WINDOWFUNC(name,nArg,extra) {                                      \
 168   nArg, (SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0,                      \
 169   name ## StepFunc, name ## ValueFunc, name ## ValueFunc,                  \
 170   name ## InverseFunc, #name                                               \
 171 }
 172
 173 /*
 174 ** Register those built-in window functions that are not also aggregates.
 175 */
 176 void sqlite3WindowFunctions(void){
 177   static FuncDef aWindowFuncs[] = {
 178     WINDOWFUNC(row_number, 0, 0),
 179     WINDOWFUNC(dense_rank, 0, 0),
 180     WINDOWFUNC(rank, 0, 0),
 181     WINDOWFUNC(percent_rank, 0, SQLITE_FUNC_WINDOW_SIZE),
 182     WINDOWFUNC(nth_value, 2, 0),
 183   };
 184   sqlite3InsertBuiltinFuncs(aWindowFuncs, ArraySize(aWindowFuncs));
 185 }
 186
 187 void sqlite3WindowUpdate(Parse *pParse, Window *pWin, FuncDef *pFunc){
 188   if( pFunc->funcFlags & SQLITE_FUNC_WINDOW ){
 189     sqlite3 *db = pParse->db;
 190     if( pFunc->xSFunc==row_numberStepFunc ){
 191       sqlite3ExprDelete(db, pWin->pStart);
 192       sqlite3ExprDelete(db, pWin->pEnd);
 193       pWin->pStart = pWin->pEnd = 0;
 194       pWin->eType = TK_ROWS;
 195       pWin->eStart = TK_UNBOUNDED;
 196       pWin->eEnd = TK_CURRENT;
 197     }
 198
 199     if( pFunc->xSFunc==dense_rankStepFunc || pFunc->xSFunc==rankStepFunc
 200      || pFunc->xSFunc==percent_rankStepFunc
 201     ){
 202       sqlite3ExprDelete(db, pWin->pStart);
 203       sqlite3ExprDelete(db, pWin->pEnd);
 204       pWin->pStart = pWin->pEnd = 0;
 205       pWin->eType = TK_RANGE;
 206       pWin->eStart = TK_UNBOUNDED;
 207       pWin->eEnd = TK_CURRENT;
 208     }
 209   }
 210 }
 211
 212 typedef struct WindowRewrite WindowRewrite;
 213 struct WindowRewrite {
 214   Window *pWin;
 215   ExprList *pSub;
 216 };
 217
 218 static int selectWindowRewriteSelectCb(Walker *pWalker, Select *pSelect){
 219   return WRC_Prune;
 220 }
 221
 222 static int selectWindowRewriteExprCb(Walker *pWalker, Expr *pExpr){
 223   struct WindowRewrite *p = pWalker->u.pRewrite;
 224   Parse *pParse = pWalker->pParse;
 225
 226   switch( pExpr->op ){
 227
 228     case TK_FUNCTION:
 229       if( pExpr->pWin==0 ){
 230         break;
 231       }else{
 232         Window *pWin;
 233         for(pWin=p->pWin; pWin; pWin=pWin->pNextWin){
 234           if( pExpr->pWin==pWin ){
 235             pExpr->pWin->pOwner = pExpr;
 236             return WRC_Prune;
 237           }
 238         }
 239       }
 240       /* Fall through.  */
 241
 242     case TK_COLUMN: {
 243       Expr *pDup = sqlite3ExprDup(pParse->db, pExpr, 0);
 244       p->pSub = sqlite3ExprListAppend(pParse, p->pSub, pDup);
 245       if( p->pSub ){
 246         assert( ExprHasProperty(pExpr, EP_Static)==0 );
 247         ExprSetProperty(pExpr, EP_Static);
 248         sqlite3ExprDelete(pParse->db, pExpr);
 249         ExprClearProperty(pExpr, EP_Static);
 250         memset(pExpr, 0, sizeof(Expr));
 251
 252         pExpr->op = TK_COLUMN;
 253         pExpr->iColumn = p->pSub->nExpr-1;
 254         pExpr->iTable = p->pWin->iEphCsr;
 255       }
 256
 257       break;
 258     }
 259
 260     default: /* no-op */
 261       break;
 262   }
 263
 264   return WRC_Continue;
 265 }
 266
 267 static int selectWindowRewriteEList(
 268   Parse *pParse,
 269   Window *pWin,
 270   ExprList *pEList,               /* Rewrite expressions in this list */
 271   ExprList **ppSub                /* IN/OUT: Sub-select expression-list */
 272 ){
 273   Walker sWalker;
 274   WindowRewrite sRewrite;
 275   int rc;
 276
 277   memset(&sWalker, 0, sizeof(Walker));
 278   memset(&sRewrite, 0, sizeof(WindowRewrite));
 279
 280   sRewrite.pSub = *ppSub;
 281   sRewrite.pWin = pWin;
 282
 283   sWalker.pParse = pParse;
 284   sWalker.xExprCallback = selectWindowRewriteExprCb;
 285   sWalker.xSelectCallback = selectWindowRewriteSelectCb;
 286   sWalker.u.pRewrite = &sRewrite;
 287
 288   rc = sqlite3WalkExprList(&sWalker, pEList);
 289
 290   *ppSub = sRewrite.pSub;
 291   return rc;
 292 }
 293
 294 static ExprList *exprListAppendList(
 295   Parse *pParse,          /* Parsing context */
 296   ExprList *pList,        /* List to which to append. Might be NULL */
 297   ExprList *pAppend       /* List of values to append. Might be NULL */
 298 ){
 299   if( pAppend ){
 300     int i;
 301     int nInit = pList ? pList->nExpr : 0;
 302     for(i=0; i<pAppend->nExpr; i++){
 303       Expr *pDup = sqlite3ExprDup(pParse->db, pAppend->a[i].pExpr, 0);
 304       pList = sqlite3ExprListAppend(pParse, pList, pDup);
 305       if( pList ) pList->a[nInit+i].sortOrder = pAppend->a[i].sortOrder;
 306     }
 307   }
 308   return pList;
 309 }
 310
 311 /*
 312 ** If the SELECT statement passed as the second argument does not invoke
 313 ** any SQL window functions, this function is a no-op. Otherwise, it
 314 ** rewrites the SELECT statement so that window function xStep functions
 315 ** are invoked in the correct order. The simplest version of the
 316 ** transformation is:
 317 **
 318 **   SELECT win(args...) OVER (<list1>) FROM <src> ORDER BY <list2>
 319 **
 320 ** to
 321 **
 322 **   SELECT win(args...) FROM (
 323 **     SELECT args... FROM <src> ORDER BY <list1>
 324 **   ) ORDER BY <list2>
 325 **
 326 ** where <src> may contain WHERE, GROUP BY and HAVING clauses, and <list1>
 327 ** is the concatenation of the PARTITION BY and ORDER BY clauses in the
 328 ** OVER clause.
 329 **
 330 */
 331 int sqlite3WindowRewrite(Parse *pParse, Select *p){
 332   int rc = SQLITE_OK;
 333   if( p->pWin ){
 334     Vdbe *v = sqlite3GetVdbe(pParse);
 335     int i;
 336     sqlite3 *db = pParse->db;
 337     Select *pSub = 0;             /* The subquery */
 338     SrcList *pSrc = p->pSrc;
 339     Expr *pWhere = p->pWhere;
 340     ExprList *pGroupBy = p->pGroupBy;
 341     Expr *pHaving = p->pHaving;
 342     ExprList *pSort = 0;
 343
 344     ExprList *pSublist = 0;       /* Expression list for sub-query */
 345     Window *pMWin = p->pWin;      /* Master window object */
 346     Window *pWin;                 /* Window object iterator */
 347
 348     p->pSrc = 0;
 349     p->pWhere = 0;
 350     p->pGroupBy = 0;
 351     p->pHaving = 0;
 352
 353     /* Assign a cursor number for the ephemeral table used to buffer rows.
 354     ** The OpenEphemeral instruction is coded later, after it is known how
 355     ** many columns the table will have.  */
 356     pMWin->iEphCsr = pParse->nTab++;
 357
 358     rc = selectWindowRewriteEList(pParse, pMWin, p->pEList, &pSublist);
 359     if( rc ) return rc;
 360     rc = selectWindowRewriteEList(pParse, pMWin, p->pOrderBy, &pSublist);
 361     if( rc ) return rc;
 362     pMWin->nBufferCol = (pSublist ? pSublist->nExpr : 0);
 363
 364     /* Create the ORDER BY clause for the sub-select. This is the concatenation
 365     ** of the window PARTITION and ORDER BY clauses. Append the same
 366     ** expressions to the sub-select expression list. They are required to
 367     ** figure out where boundaries for partitions and sets of peer rows.  */
 368     pSort = sqlite3ExprListDup(db, pMWin->pPartition, 0);
 369     if( pMWin->pOrderBy ){
 370       pSort = exprListAppendList(pParse, pSort, pMWin->pOrderBy);
 371     }
 372     pSublist = exprListAppendList(pParse, pSublist, pSort);
 373
 374     /* Append the arguments passed to each window function to the
 375     ** sub-select expression list. Also allocate two registers for each
 376     ** window function - one for the accumulator, another for interim
 377     ** results.  */
 378     for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
 379       pWin->iArgCol = (pSublist ? pSublist->nExpr : 0);
 380       pSublist = exprListAppendList(pParse, pSublist, pWin->pOwner->x.pList);
 381       pWin->regAccum = ++pParse->nMem;
 382       pWin->regResult = ++pParse->nMem;
 383       sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);
 384     }
 385
 386     pSub = sqlite3SelectNew(
 387         pParse, pSublist, pSrc, pWhere, pGroupBy, pHaving, pSort, 0, 0
 388     );
 389     p->pSrc = sqlite3SrcListAppend(db, 0, 0, 0);
 390     if( p->pSrc ){
 391       int iTab;
 392       ExprList *pList = 0;
 393       p->pSrc->a[0].pSelect = pSub;
 394       sqlite3SrcListAssignCursors(pParse, p->pSrc);
 395       if( sqlite3ExpandSubquery(pParse, &p->pSrc->a[0]) ){
 396         rc = SQLITE_NOMEM;
 397       }else{
 398         pSub->selFlags |= SF_Expanded;
 399       }
 400     }
 401
 402     sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pMWin->iEphCsr, pSublist->nExpr);
 403   }
 404
 405   return rc;
 406 }
 407
 408 void sqlite3WindowDelete(sqlite3 *db, Window *p){
 409   if( p ){
 410     sqlite3ExprDelete(db, p->pFilter);
 411     sqlite3ExprListDelete(db, p->pPartition);
 412     sqlite3ExprListDelete(db, p->pOrderBy);
 413     sqlite3ExprDelete(db, p->pEnd);
 414     sqlite3ExprDelete(db, p->pStart);
 415     sqlite3DbFree(db, p);
 416   }
 417 }
 418
 419 Window *sqlite3WindowAlloc(
 420   Parse *pParse,
 421   int eType,
 422   int eStart, Expr *pStart,
 423   int eEnd, Expr *pEnd
 424 ){
 425   Window *pWin = (Window*)sqlite3DbMallocZero(pParse->db, sizeof(Window));
 426
 427   if( pWin ){
 428     pWin->eType = eType;
 429     pWin->eStart = eStart;
 430     pWin->eEnd = eEnd;
 431     pWin->pEnd = pEnd;
 432     pWin->pStart = pStart;
 433   }else{
 434     sqlite3ExprDelete(pParse->db, pEnd);
 435     sqlite3ExprDelete(pParse->db, pStart);
 436   }
 437
 438   return pWin;
 439 }
 440
 441 void sqlite3WindowAttach(Parse *pParse, Expr *p, Window *pWin){
 442   if( p ){
 443     p->pWin = pWin;
 444   }else{
 445     sqlite3WindowDelete(pParse->db, pWin);
 446   }
 447 }
 448
 449 /*
 450 ** Return 0 if the two window objects are identical, or non-zero otherwise.
 451 */
 452 int sqlite3WindowCompare(Parse *pParse, Window *p1, Window *p2){
 453   if( p1->eType!=p2->eType ) return 1;
 454   if( p1->eStart!=p2->eStart ) return 1;
 455   if( p1->eEnd!=p2->eEnd ) return 1;
 456   if( sqlite3ExprCompare(pParse, p1->pStart, p2->pStart, -1) ) return 1;
 457   if( sqlite3ExprCompare(pParse, p1->pEnd, p2->pEnd, -1) ) return 1;
 458   if( sqlite3ExprListCompare(p1->pPartition, p2->pPartition, -1) ) return 1;
 459   if( sqlite3ExprListCompare(p1->pOrderBy, p2->pOrderBy, -1) ) return 1;
 460   return 0;
 461 }
 462
 463 static void windowAggInit(Parse *pParse, Window *pMWin){
 464   Window *pWin;
 465   for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
 466     int funcFlags = pWin->pFunc->funcFlags;
 467     if( (funcFlags & SQLITE_FUNC_MINMAX) && pWin->eStart!=TK_UNBOUNDED ){
 468       ExprList *pList = pWin->pOwner->x.pList;
 469       KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pList, 0, 0);
 470       Vdbe *v = sqlite3GetVdbe(pParse);
 471       pWin->csrApp = pParse->nTab++;
 472       pWin->regApp = pParse->nMem+1;
 473       pParse->nMem += 3;
 474       if( pKeyInfo && pWin->pFunc->zName[1]=='i' ){
 475         assert( pKeyInfo->aSortOrder[0]==0 );
 476         pKeyInfo->aSortOrder[0] = 1;
 477       }
 478       sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pWin->csrApp, 2);
 479       sqlite3VdbeAppendP4(v, pKeyInfo, P4_KEYINFO);
 480       sqlite3VdbeAddOp2(v, OP_Integer, 0, pWin->regApp+1);
 481     }
 482   }
 483 }
 484
 485 void sqlite3WindowCodeInit(Parse *pParse, Window *pWin){
 486   Vdbe *v = sqlite3GetVdbe(pParse);
 487   int nPart = (pWin->pPartition ? pWin->pPartition->nExpr : 0);
 488   nPart += (pWin->pOrderBy ? pWin->pOrderBy->nExpr : 0);
 489   if( nPart ){
 490     pWin->regPart = pParse->nMem+1;
 491     pParse->nMem += nPart;
 492     sqlite3VdbeAddOp3(v, OP_Null, 0, pWin->regPart, pWin->regPart+nPart-1);
 493   }
 494   windowAggInit(pParse, pWin);
 495 }
 496
 497 static void windowCheckFrameValue(Parse *pParse, int reg, int bEnd){
 498   static const char *azErr[] = {
 499     "frame starting offset must be a non-negative integer",
 500     "frame ending offset must be a non-negative integer"
 501   };
 502   Vdbe *v = sqlite3GetVdbe(pParse);
 503   int regZero = ++pParse->nMem;
 504
 505   sqlite3VdbeAddOp2(v, OP_Integer, 0, regZero);
 506   sqlite3VdbeAddOp2(v, OP_MustBeInt, reg, sqlite3VdbeCurrentAddr(v)+2);
 507   sqlite3VdbeAddOp3(v, OP_Ge, regZero, sqlite3VdbeCurrentAddr(v)+2, reg);
 508   sqlite3VdbeAddOp2(v, OP_Halt, SQLITE_ERROR, OE_Abort);
 509   sqlite3VdbeAppendP4(v, (void*)azErr[bEnd], P4_STATIC);
 510 }
 511
 512 /*
 513 ** Generate VM code to invoke either xStep() (if bInverse is 0) or
 514 ** xInverse (if bInverse is non-zero) for each window function in the
 515 ** linked list starting at pMWin.
 516 */
 517 static void windowAggStep(
 518   Parse *pParse,
 519   Window *pMWin,
 520   int csr,
 521   int bInverse,
 522   int reg,
 523   int regPartSize                 /* Register containing size of partition */
 524 ){
 525   Vdbe *v = sqlite3GetVdbe(pParse);
 526   Window *pWin;
 527   for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
 528     int flags = pWin->pFunc->funcFlags;
 529     int regArg;
 530     int nArg = pWin->nArg;
 531
 532     if( flags & SQLITE_FUNC_WINDOW_SIZE ){
 533       regArg = regPartSize;
 534       nArg++;
 535     }else if( csr>=0 ){
 536       int i;
 537       for(i=0; i<pWin->nArg; i++){
 538         sqlite3VdbeAddOp3(v, OP_Column, csr, pWin->iArgCol+i, reg+i);
 539       }
 540       regArg = reg;
 541     }else{
 542       regArg = reg + pWin->iArgCol;
 543     }
 544
 545     if( pWin->csrApp ){
 546       if( bInverse==0 ){
 547         sqlite3VdbeAddOp2(v, OP_AddImm, pWin->regApp+1, 1);
 548         sqlite3VdbeAddOp2(v, OP_SCopy, regArg, pWin->regApp);
 549         sqlite3VdbeAddOp3(v, OP_MakeRecord, pWin->regApp, 2, pWin->regApp+2);
 550         sqlite3VdbeAddOp2(v, OP_IdxInsert, pWin->csrApp, pWin->regApp+2);
 551       }else{
 552         sqlite3VdbeAddOp4Int(v, OP_SeekGE, pWin->csrApp, 0, regArg, 1);
 553         sqlite3VdbeAddOp1(v, OP_Delete, pWin->csrApp);
 554         sqlite3VdbeJumpHere(v, sqlite3VdbeCurrentAddr(v)-2);
 555       }
 556     }else{
 557       if( pWin->pFunc->funcFlags & SQLITE_FUNC_NEEDCOLL ){
 558         CollSeq *pColl;
 559         pColl = sqlite3ExprCollSeq(pParse, pWin->pOwner->x.pList->a[0].pExpr);
 560         sqlite3VdbeAddOp4(v, OP_CollSeq, 0,0,0, (const char*)pColl, P4_COLLSEQ);
 561       }
 562       sqlite3VdbeAddOp3(v, OP_AggStep0, bInverse, regArg, pWin->regAccum);
 563       sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
 564       sqlite3VdbeChangeP5(v, (u8)nArg);
 565     }
 566   }
 567 }
 568
 569 static void windowAggFinal(Parse *pParse, Window *pMWin, int bFinal){
 570   Vdbe *v = sqlite3GetVdbe(pParse);
 571   Window *pWin;
 572
 573   for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
 574     if( pWin->csrApp ){
 575       sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regResult);
 576       sqlite3VdbeAddOp1(v, OP_Last, pWin->csrApp);
 577       sqlite3VdbeAddOp3(v, OP_Column, pWin->csrApp, 0, pWin->regResult);
 578       sqlite3VdbeJumpHere(v, sqlite3VdbeCurrentAddr(v)-2);
 579       if( bFinal ){
 580         sqlite3VdbeAddOp1(v, OP_ResetSorter, pWin->csrApp);
 581       }
 582     }else{
 583       if( bFinal==0 ){
 584         sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regResult);
 585       }
 586       sqlite3VdbeAddOp2(v, OP_AggFinal, pWin->regAccum, pWin->nArg);
 587       sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
 588       if( bFinal ){
 589         sqlite3VdbeAddOp2(v, OP_Copy, pWin->regAccum, pWin->regResult);
 590       }else{
 591         sqlite3VdbeChangeP3(v, -1, pWin->regResult);
 592       }
 593     }
 594   }
 595 }
 596
 597 static void windowPartitionCache(
 598   Parse *pParse,
 599   Select *p,
 600   WhereInfo *pWInfo,
 601   int regFlushPart,
 602   int lblFlushPart,
 603   int *pRegSize
 604 ){
 605   Window *pMWin = p->pWin;
 606   Vdbe *v = sqlite3GetVdbe(pParse);
 607   Window *pWin;
 608   int iSubCsr = p->pSrc->a[0].iCursor;
 609   int nSub = p->pSrc->a[0].pTab->nCol;
 610   int k;
 611
 612   int reg = pParse->nMem+1;
 613   int regRecord = reg+nSub;
 614   int regRowid = regRecord+1;
 615
 616   *pRegSize = regRowid;
 617   pParse->nMem += nSub + 2;
 618
 619   /* Martial the row returned by the sub-select into an array of
 620   ** registers. */
 621   for(k=0; k<nSub; k++){
 622     sqlite3VdbeAddOp3(v, OP_Column, iSubCsr, k, reg+k);
 623   }
 624   sqlite3VdbeAddOp3(v, OP_MakeRecord, reg, nSub, regRecord);
 625
 626   /* Check if this is the start of a new partition. If so, call the
 627   ** flush_partition sub-routine.  */
 628   if( pMWin->pPartition ){
 629     int addr;
 630     ExprList *pPart = pMWin->pPartition;
 631     int nPart = (pPart ? pPart->nExpr : 0);
 632     int regNewPart = reg + pMWin->nBufferCol;
 633     KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pPart, 0, 0);
 634
 635     addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPart, pMWin->regPart,nPart);
 636     sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
 637     sqlite3VdbeAddOp3(v, OP_Jump, addr+2, addr+4, addr+2);
 638     sqlite3VdbeAddOp3(v, OP_Copy, regNewPart, pMWin->regPart, nPart-1);
 639     sqlite3VdbeAddOp2(v, OP_Gosub, regFlushPart, lblFlushPart);
 640   }
 641
 642   /* Buffer the current row in the ephemeral table. */
 643   sqlite3VdbeAddOp2(v, OP_NewRowid, pMWin->iEphCsr, regRowid);
 644   sqlite3VdbeAddOp3(v, OP_Insert, pMWin->iEphCsr, regRecord, regRowid);
 645
 646   /* End of the input loop */
 647   sqlite3WhereEnd(pWInfo);
 648
 649   /* Invoke "flush_partition" to deal with the final (or only) partition */
 650   sqlite3VdbeAddOp2(v, OP_Gosub, regFlushPart, lblFlushPart);
 651 }
 652
 653 /*
 654 ** ROWS BETWEEN <expr1> PRECEDING AND <expr2> FOLLOWING
 655 ** ----------------------------------------------------
 656 **
 657 ** Pseudo-code for the implementation of this window frame type is as
 658 ** follows. sqlite3WhereBegin() has already been called to generate the
 659 ** top of the main loop when this function is called.
 660 **
 661 ** Each time the sub-routine at addrGosub is invoked, a single output
 662 ** row is generated based on the current row indicated by Window.iEphCsr.
 663 **
 664 **     ...
 665 **       if( new partition ){
 666 **         Gosub flush_partition
 667 **       }
 668 **       Insert (record in eph-table)
 669 **     sqlite3WhereEnd()
 670 **     Gosub flush_partition
 671 **
 672 **   flush_partition:
 673 **     Once {
 674 **       OpenDup (iEphCsr -> csrStart)
 675 **       OpenDup (iEphCsr -> csrEnd)
 676 **     }
 677 **     regStart = <expr1>                // PRECEDING expression
 678 **     regEnd = <expr2>                  // FOLLOWING expression
 679 **     if( regStart<0 || regEnd<0 ){ error! }
 680 **     Rewind (csr,csrStart,csrEnd)      // if EOF goto flush_partition_done
 681 **       Next(csrEnd)                    // if EOF skip Aggstep
 682 **       Aggstep (csrEnd)
 683 **       if( (regEnd--)<=0 ){
 684 **         AggFinal (xValue)
 685 **         Gosub addrGosub
 686 **         Next(csr)                // if EOF goto flush_partition_done
 687 **         if( (regStart--)<=0 ){
 688 **           AggStep (csrStart, xInverse)
 689 **           Next(csrStart)
 690 **         }
 691 **       }
 692 **   flush_partition_done:
 693 **     ResetSorter (csr)
 694 **     Return
 695 **
 696 ** ROWS BETWEEN <expr> PRECEDING    AND CURRENT ROW
 697 ** ROWS BETWEEN CURRENT ROW         AND <expr> FOLLOWING
 698 ** ROWS BETWEEN UNBOUNDED PRECEDING AND <expr> FOLLOWING
 699 **
 700 **   These are similar to the above. For "CURRENT ROW", intialize the
 701 **   register to 0. For "UNBOUNDED PRECEDING" to infinity.
 702 **
 703 ** ROWS BETWEEN <expr> PRECEDING    AND UNBOUNDED FOLLOWING
 704 ** ROWS BETWEEN CURRENT ROW         AND UNBOUNDED FOLLOWING
 705 **
 706 **     Rewind (csr,csrStart,csrEnd)    // if EOF goto flush_partition_done
 707 **     while( 1 ){
 708 **       Next(csrEnd)                  // Exit while(1) at EOF
 709 **       Aggstep (csrEnd)
 710 **     }
 711 **     while( 1 ){
 712 **       AggFinal (xValue)
 713 **       Gosub addrGosub
 714 **       Next(csr)                     // if EOF goto flush_partition_done
 715 **       if( (regStart--)<=0 ){
 716 **         AggStep (csrStart, xInverse)
 717 **         Next(csrStart)
 718 **       }
 719 **     }
 720 **
 721 **   For the "CURRENT ROW AND UNBOUNDED FOLLOWING" case, the final if()
 722 **   condition is always true (as if regStart were initialized to 0).
 723 **
 724 ** RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
 725 **
 726 **   This is the only RANGE case handled by this routine. It modifies the
 727 **   second while( 1 ) loop in "ROWS BETWEEN CURRENT ... UNBOUNDED..." to
 728 **   be:
 729 **
 730 **     while( 1 ){
 731 **       AggFinal (xValue)
 732 **       while( 1 ){
 733 **         regPeer++
 734 **         Gosub addrGosub
 735 **         Next(csr)                     // if EOF goto flush_partition_done
 736 **         if( new peer ) break;
 737 **       }
 738 **       while( (regPeer--)>0 ){
 739 **         AggStep (csrStart, xInverse)
 740 **         Next(csrStart)
 741 **       }
 742 **     }
 743 **
 744 ** ROWS BETWEEN <expr> FOLLOWING    AND <expr> FOLLOWING
 745 **
 746 **   regEnd = regEnd - regStart
 747 **   Rewind (csr,csrStart,csrEnd)   // if EOF goto flush_partition_done
 748 **     Aggstep (csrEnd)
 749 **     Next(csrEnd)                 // if EOF fall-through
 750 **     if( (regEnd--)<=0 ){
 751 **       if( (regStart--)<=0 ){
 752 **         AggFinal (xValue)
 753 **         Gosub addrGosub
 754 **         Next(csr)              // if EOF goto flush_partition_done
 755 **       }
 756 **       AggStep (csrStart, xInverse)
 757 **       Next (csrStart)
 758 **     }
 759 **
 760 ** ROWS BETWEEN <expr> PRECEDING    AND <expr> PRECEDING
 761 **
 762 **   Replace the bit after "Rewind" in the above with:
 763 **
 764 **     if( (regEnd--)<=0 ){
 765 **       AggStep (csrEnd)
 766 **       Next (csrEnd)
 767 **     }
 768 **     AggFinal (xValue)
 769 **     Gosub addrGosub
 770 **     Next(csr)                  // if EOF goto flush_partition_done
 771 **     if( (regStart--)<=0 ){
 772 **       AggStep (csr2, xInverse)
 773 **       Next (csr2)
 774 **     }
 775 **
 776 */
 777 static void windowCodeRowExprStep(
 778   Parse *pParse,
 779   Select *p,
 780   WhereInfo *pWInfo,
 781   int regGosub,
 782   int addrGosub
 783 ){
 784   Window *pMWin = p->pWin;
 785   Vdbe *v = sqlite3GetVdbe(pParse);
 786   Window *pWin;
 787   int k;
 788   int nSub = p->pSrc->a[0].pTab->nCol;
 789   int regFlushPart;               /* Register for "Gosub flush_partition" */
 790   int lblFlushPart;               /* Label for "Gosub flush_partition" */
 791   int lblFlushDone;               /* Label for "Gosub flush_partition_done" */
 792
 793   int regArg;
 794   int nArg;
 795   int addr;
 796   int csrStart = pParse->nTab++;
 797   int csrEnd = pParse->nTab++;
 798   int regStart;                    /* Value of <expr> PRECEDING */
 799   int regEnd;                      /* Value of <expr> FOLLOWING */
 800   int addrNext;
 801   int addrGoto;
 802   int addrTop;
 803   int addrIfPos1;
 804   int addrIfPos2;
 805
 806   int regPeer = 0;                 /* Number of peers in current group */
 807   int regPeerVal = 0;              /* Array of values identifying peer group */
 808   int iPeer = 0;                   /* Column offset in eph-table of peer vals */
 809   int nPeerVal;                    /* Number of peer values */
 810   int bRange = 0;
 811   int regSize = 0;
 812
 813   assert( pMWin->eStart==TK_PRECEDING
 814        || pMWin->eStart==TK_CURRENT
 815        || pMWin->eStart==TK_FOLLOWING
 816        || pMWin->eStart==TK_UNBOUNDED
 817   );
 818   assert( pMWin->eEnd==TK_FOLLOWING
 819        || pMWin->eEnd==TK_CURRENT
 820        || pMWin->eEnd==TK_UNBOUNDED
 821        || pMWin->eEnd==TK_PRECEDING
 822   );
 823
 824   if( pMWin->eType==TK_RANGE
 825    && pMWin->eStart==TK_CURRENT
 826    && pMWin->eEnd==TK_UNBOUNDED
 827   ){
 828     bRange = 1;
 829   }
 830
 831   /* Allocate register and label for the "flush_partition" sub-routine. */
 832   regFlushPart = ++pParse->nMem;
 833   lblFlushPart = sqlite3VdbeMakeLabel(v);
 834   lblFlushDone = sqlite3VdbeMakeLabel(v);
 835
 836   regStart = ++pParse->nMem;
 837   regEnd = ++pParse->nMem;
 838
 839   windowPartitionCache(pParse, p, pWInfo, regFlushPart, lblFlushPart, &regSize);
 840
 841   addrGoto = sqlite3VdbeAddOp0(v, OP_Goto);
 842
 843   /* Start of "flush_partition" */
 844   sqlite3VdbeResolveLabel(v, lblFlushPart);
 845   sqlite3VdbeAddOp2(v, OP_Once, 0, sqlite3VdbeCurrentAddr(v)+3);
 846   sqlite3VdbeAddOp2(v, OP_OpenDup, csrStart, pMWin->iEphCsr);
 847   sqlite3VdbeAddOp2(v, OP_OpenDup, csrEnd, pMWin->iEphCsr);
 848
 849   /* If either regStart or regEnd are not non-negative integers, throw
 850   ** an exception.  */
 851   if( pMWin->pStart ){
 852     sqlite3ExprCode(pParse, pMWin->pStart, regStart);
 853     windowCheckFrameValue(pParse, regStart, 0);
 854   }
 855   if( pMWin->pEnd ){
 856     sqlite3ExprCode(pParse, pMWin->pEnd, regEnd);
 857     windowCheckFrameValue(pParse, regEnd, 1);
 858   }
 859
 860   /* If this is "ROWS <expr1> FOLLOWING AND ROWS <expr2> FOLLOWING", do:
 861   **
 862   **   regEnd = regEnd - regStart;
 863   */
 864   if( pMWin->pEnd && pMWin->pStart && pMWin->eStart==TK_FOLLOWING ){
 865     assert( pMWin->eEnd==TK_FOLLOWING );
 866     sqlite3VdbeAddOp3(v, OP_Subtract, regStart, regEnd, regEnd);
 867   }
 868
 869   /* Initialize the accumulator register for each window function to NULL */
 870   nArg = 0;
 871   for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
 872     sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);
 873     nArg = MAX(nArg, pWin->nArg);
 874   }
 875   regArg = pParse->nMem+1;
 876   pParse->nMem += nArg;
 877
 878   sqlite3VdbeAddOp2(v, OP_Rewind, pMWin->iEphCsr, lblFlushDone);
 879   sqlite3VdbeAddOp2(v, OP_Rewind, csrStart, lblFlushDone);
 880   sqlite3VdbeChangeP5(v, 1);
 881   sqlite3VdbeAddOp2(v, OP_Rewind, csrEnd, lblFlushDone);
 882   sqlite3VdbeChangeP5(v, 1);
 883
 884   /* Invoke AggStep function for each window function using the row that
 885   ** csrEnd currently points to. Or, if csrEnd is already at EOF,
 886   ** do nothing.  */
 887   addrTop = sqlite3VdbeCurrentAddr(v);
 888   if( pMWin->eEnd==TK_PRECEDING ){
 889     addrIfPos1 = sqlite3VdbeAddOp3(v, OP_IfPos, regEnd, 0 , 1);
 890   }
 891   sqlite3VdbeAddOp2(v, OP_Next, csrEnd, sqlite3VdbeCurrentAddr(v)+2);
 892   addr = sqlite3VdbeAddOp0(v, OP_Goto);
 893   windowAggStep(pParse, pMWin, csrEnd, 0, regArg, regSize);
 894   if( pMWin->eEnd==TK_UNBOUNDED ){
 895     sqlite3VdbeAddOp2(v, OP_Goto, 0, addrTop);
 896     sqlite3VdbeJumpHere(v, addr);
 897     addrTop = sqlite3VdbeCurrentAddr(v);
 898   }else{
 899     sqlite3VdbeJumpHere(v, addr);
 900     if( pMWin->eEnd==TK_PRECEDING ){
 901       sqlite3VdbeJumpHere(v, addrIfPos1);
 902     }
 903   }
 904
 905   if( pMWin->eEnd==TK_FOLLOWING ){
 906     addrIfPos1 = sqlite3VdbeAddOp3(v, OP_IfPos, regEnd, 0 , 1);
 907   }
 908   if( pMWin->eStart==TK_FOLLOWING ){
 909     addrIfPos2 = sqlite3VdbeAddOp3(v, OP_IfPos, regStart, 0 , 1);
 910   }
 911   if( bRange ){
 912     assert( pMWin->eStart==TK_CURRENT && pMWin->pOrderBy );
 913     regPeer = ++pParse->nMem;
 914     regPeerVal = pParse->nMem+1;
 915     iPeer = pMWin->nBufferCol + (pMWin->pPartition?pMWin->pPartition->nExpr:0);
 916     nPeerVal = pMWin->pOrderBy->nExpr;
 917     pParse->nMem += (2 * nPeerVal);
 918     for(k=0; k<nPeerVal; k++){
 919       sqlite3VdbeAddOp3(v, OP_Column, pMWin->iEphCsr, iPeer+k, regPeerVal+k);
 920     }
 921     sqlite3VdbeAddOp2(v, OP_Integer, 0, regPeer);
 922   }
 923   windowAggFinal(pParse, pMWin, 0);
 924   if( bRange ){
 925     sqlite3VdbeAddOp2(v, OP_AddImm, regPeer, 1);
 926   }
 927   sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrGosub);
 928   sqlite3VdbeAddOp2(v, OP_Next, pMWin->iEphCsr, sqlite3VdbeCurrentAddr(v)+2);
 929   sqlite3VdbeAddOp2(v, OP_Goto, 0, lblFlushDone);
 930   if( bRange ){
 931     KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pMWin->pOrderBy,0,0);
 932     int addrJump = sqlite3VdbeCurrentAddr(v)-4;
 933     for(k=0; k<nPeerVal; k++){
 934       int iOut = regPeerVal + nPeerVal + k;
 935       sqlite3VdbeAddOp3(v, OP_Column, pMWin->iEphCsr, iPeer+k, iOut);
 936     }
 937     sqlite3VdbeAddOp3(v, OP_Compare, regPeerVal, regPeerVal+nPeerVal, nPeerVal);
 938     sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
 939     addr = sqlite3VdbeCurrentAddr(v)+1;
 940     sqlite3VdbeAddOp3(v, OP_Jump, addr, addrJump, addr);
 941   }
 942   if( pMWin->eStart==TK_FOLLOWING ){
 943     sqlite3VdbeJumpHere(v, addrIfPos2);
 944   }
 945
 946   if( pMWin->eStart==TK_CURRENT
 947    || pMWin->eStart==TK_PRECEDING
 948    || pMWin->eStart==TK_FOLLOWING
 949   ){
 950     int addrJumpHere = 0;
 951     if( pMWin->eStart==TK_PRECEDING ){
 952       addrJumpHere = sqlite3VdbeAddOp3(v, OP_IfPos, regStart, 0 , 1);
 953     }
 954     if( bRange ){
 955       sqlite3VdbeAddOp3(v, OP_IfPos, regPeer, sqlite3VdbeCurrentAddr(v)+2, 1);
 956       addrJumpHere = sqlite3VdbeAddOp0(v, OP_Goto);
 957     }
 958     sqlite3VdbeAddOp2(v, OP_Next, csrStart, sqlite3VdbeCurrentAddr(v)+1);
 959     windowAggStep(pParse, pMWin, csrStart, 1, regArg, regSize);
 960     if( bRange ){
 961       sqlite3VdbeAddOp2(v, OP_Goto, 0, addrJumpHere-1);
 962     }
 963     if( addrJumpHere ){
 964       sqlite3VdbeJumpHere(v, addrJumpHere);
 965     }
 966   }
 967   if( pMWin->eEnd==TK_FOLLOWING ){
 968     sqlite3VdbeJumpHere(v, addrIfPos1);
 969   }
 970   sqlite3VdbeAddOp2(v, OP_Goto, 0, addrTop);
 971
 972   /* flush_partition_done: */
 973   sqlite3VdbeResolveLabel(v, lblFlushDone);
 974   sqlite3VdbeAddOp1(v, OP_ResetSorter, pMWin->iEphCsr);
 975   sqlite3VdbeAddOp1(v, OP_Return, regFlushPart);
 976
 977   /* Jump to here to skip over flush_partition */
 978   sqlite3VdbeJumpHere(v, addrGoto);
 979 }
 980
 981 /*
 982 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
 983 **
 984 **   flush_partition:
 985 **     Once {
 986 **       OpenDup (iEphCsr -> csrLead)
 987 **     }
 988 **     Integer ctr 0
 989 **     foreach row (csrLead){
 990 **       if( new peer ){
 991 **         AggFinal (xValue)
 992 **         for(i=0; i<ctr; i++){
 993 **           Gosub addrGosub
 994 **           Next iEphCsr
 995 **         }
 996 **         Integer ctr 0
 997 **       }
 998 **       AggStep (csrLead)
 999 **       Incr ctr
1000 **     }
1001 **
1002 **     AggFinal (xFinalize)
1003 **     for(i=0; i<ctr; i++){
1004 **       Gosub addrGosub
1005 **       Next iEphCsr
1006 **     }
1007 **
1008 **     ResetSorter (csr)
1009 **     Return
1010 **
1011 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1012 ** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
1013 ** RANGE BETWEEN CURRENT ROW AND CURRENT ROW
1014 **
1015 **   TODO.
1016 */
1017 static void windowCodeCacheStep(
1018   Parse *pParse,
1019   Select *p,
1020   WhereInfo *pWInfo,
1021   int regGosub,
1022   int addrGosub
1023 ){
1024   Window *pMWin = p->pWin;
1025   Vdbe *v = sqlite3GetVdbe(pParse);
1026   Window *pWin;
1027   int k;
1028   int addr;
1029   ExprList *pPart = pMWin->pPartition;
1030   ExprList *pOrderBy = pMWin->pOrderBy;
1031   int nPeer = pOrderBy->nExpr;
1032   int regNewPeer;
1033
1034   int addrGoto;                   /* Address of Goto used to jump flush_par.. */
1035   int addrRewind;                 /* Address of Rewind that starts loop */
1036   int regFlushPart;
1037   int lblFlushPart;
1038   int csrLead;
1039   int regCtr;
1040   int regArg;                     /* Register array to martial function args */
1041   int regSize;
1042   int nArg;
1043
1044   assert( (pMWin->eStart==TK_UNBOUNDED && pMWin->eEnd==TK_CURRENT)
1045   );
1046
1047   regNewPeer = pParse->nMem+1;
1048   pParse->nMem += nPeer;
1049
1050   /* Allocate register and label for the "flush_partition" sub-routine. */
1051   regFlushPart = ++pParse->nMem;
1052   lblFlushPart = sqlite3VdbeMakeLabel(v);
1053
1054   csrLead = pParse->nTab++;
1055   regCtr = ++pParse->nMem;
1056
1057   windowPartitionCache(pParse, p, pWInfo, regFlushPart, lblFlushPart, &regSize);
1058   addrGoto = sqlite3VdbeAddOp0(v, OP_Goto);
1059
1060   /* Start of "flush_partition" */
1061   sqlite3VdbeResolveLabel(v, lblFlushPart);
1062   sqlite3VdbeAddOp2(v, OP_Once, 0, sqlite3VdbeCurrentAddr(v)+2);
1063   sqlite3VdbeAddOp2(v, OP_OpenDup, csrLead, pMWin->iEphCsr);
1064
1065   /* Initialize the accumulator register for each window function to NULL */
1066   nArg = 0;
1067   for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
1068     sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);
1069     nArg = MAX(nArg, pWin->nArg);
1070   }
1071   regArg = pParse->nMem+1;
1072   pParse->nMem += nArg;
1073
1074   sqlite3VdbeAddOp2(v, OP_Integer, 0, regCtr);
1075   addrRewind = sqlite3VdbeAddOp1(v, OP_Rewind, csrLead);
1076   sqlite3VdbeAddOp1(v, OP_Rewind, pMWin->iEphCsr);
1077
1078   if( pOrderBy ){
1079     int addrJump;                 /* Address of OP_Jump below */
1080     int iOff = pMWin->nBufferCol + (pPart ? pPart->nExpr : 0);
1081     int regPeer = pMWin->regPart + (pPart ? pPart->nExpr : 0);
1082     KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pOrderBy, 0, 0);
1083
1084     for(k=0; k<nPeer; k++){
1085       sqlite3VdbeAddOp3(v, OP_Column, csrLead, iOff+k, regNewPeer+k);
1086     }
1087
1088     addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPeer, regPeer, nPeer);
1089     sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
1090     addrJump = sqlite3VdbeAddOp3(v, OP_Jump, addr+2, 0, addr+2);
1091     sqlite3VdbeAddOp3(v, OP_Copy, regNewPeer, regPeer, nPeer-1);
1092     windowAggFinal(pParse, pMWin, 0);
1093     sqlite3VdbeAddOp3(v, OP_IfPos, regCtr, sqlite3VdbeCurrentAddr(v)+2 , 1);
1094     sqlite3VdbeAddOp2(v, OP_Goto, 0, sqlite3VdbeCurrentAddr(v)+3);
1095     sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrGosub);
1096     sqlite3VdbeAddOp2(v, OP_Next, pMWin->iEphCsr, sqlite3VdbeCurrentAddr(v)-3);
1097     sqlite3VdbeJumpHere(v, addrJump);
1098   }
1099
1100   windowAggStep(pParse, pMWin, csrLead, 0, regArg, regSize);
1101   sqlite3VdbeAddOp2(v, OP_AddImm, regCtr, 1);
1102
1103   sqlite3VdbeAddOp2(v, OP_Next, csrLead, addrRewind+2);
1104
1105   windowAggFinal(pParse, pMWin, 1);
1106
1107   sqlite3VdbeAddOp3(v, OP_IfPos, regCtr, sqlite3VdbeCurrentAddr(v)+2 , 1);
1108   sqlite3VdbeAddOp2(v, OP_Goto, 0, sqlite3VdbeCurrentAddr(v)+3);
1109   sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrGosub);
1110   sqlite3VdbeAddOp2(v, OP_Next, pMWin->iEphCsr, sqlite3VdbeCurrentAddr(v)-3);
1111
1112   sqlite3VdbeJumpHere(v, addrRewind);
1113   sqlite3VdbeJumpHere(v, addrRewind+1);
1114   sqlite3VdbeAddOp1(v, OP_ResetSorter, pMWin->iEphCsr);
1115   sqlite3VdbeAddOp1(v, OP_Return, regFlushPart);
1116
1117   /* Jump to here to skip over flush_partition */
1118   sqlite3VdbeJumpHere(v, addrGoto);
1119 }
1120
1121
1122 /*
1123 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1124 **
1125 **   ...
1126 **     if( new partition ){
1127 **       AggFinal (xFinalize)
1128 **       Gosub addrGosub
1129 **       ResetSorter eph-table
1130 **     }
1131 **     else if( new peer ){
1132 **       AggFinal (xValue)
1133 **       Gosub addrGosub
1134 **       ResetSorter eph-table
1135 **     }
1136 **     AggStep
1137 **     Insert (record into eph-table)
1138 **   sqlite3WhereEnd()
1139 **   AggFinal (xFinalize)
1140 **   Gosub addrGosub
1141 **
1142 ** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
1143 **
1144 **   As above, except take no action for a "new peer". Invoke
1145 **   the sub-routine once only for each partition.
1146 **
1147 ** RANGE BETWEEN CURRENT ROW AND CURRENT ROW
1148 **
1149 **   As above, except that the "new peer" condition is handled in the
1150 **   same way as "new partition" (so there is no "else if" block).
1151 **
1152 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1153 **
1154 **   As above, except assume every row is a "new peer".
1155 */
1156 static void windowCodeDefaultStep(
1157   Parse *pParse,
1158   Select *p,
1159   WhereInfo *pWInfo,
1160   int regGosub,
1161   int addrGosub
1162 ){
1163   Window *pMWin = p->pWin;
1164   Vdbe *v = sqlite3GetVdbe(pParse);
1165   Window *pWin;
1166   int k;
1167   int iSubCsr = p->pSrc->a[0].iCursor;
1168   int nSub = p->pSrc->a[0].pTab->nCol;
1169   int reg = pParse->nMem+1;
1170   int regRecord = reg+nSub;
1171   int regRowid = regRecord+1;
1172   int addr;
1173   ExprList *pPart = pMWin->pPartition;
1174   ExprList *pOrderBy = pMWin->pOrderBy;
1175
1176   assert( pMWin->eType==TK_RANGE
1177       || (pMWin->eStart==TK_UNBOUNDED && pMWin->eEnd==TK_CURRENT)
1178   );
1179
1180   assert( (pMWin->eStart==TK_UNBOUNDED && pMWin->eEnd==TK_CURRENT)
1181        || (pMWin->eStart==TK_UNBOUNDED && pMWin->eEnd==TK_UNBOUNDED)
1182        || (pMWin->eStart==TK_CURRENT && pMWin->eEnd==TK_CURRENT)
1183        || (pMWin->eStart==TK_CURRENT && pMWin->eEnd==TK_UNBOUNDED && !pOrderBy)
1184   );
1185
1186   if( pMWin->eEnd==TK_UNBOUNDED ){
1187     pOrderBy = 0;
1188   }
1189
1190   pParse->nMem += nSub + 2;
1191
1192   /* Martial the row returned by the sub-select into an array of
1193   ** registers. */
1194   for(k=0; k<nSub; k++){
1195     sqlite3VdbeAddOp3(v, OP_Column, iSubCsr, k, reg+k);
1196   }
1197
1198   /* Check if this is the start of a new partition or peer group. */
1199   if( pPart || pOrderBy ){
1200     int nPart = (pPart ? pPart->nExpr : 0);
1201     int addrGoto = 0;
1202     int addrJump = 0;
1203     int nPeer = (pOrderBy ? pOrderBy->nExpr : 0);
1204
1205     if( pPart ){
1206       int regNewPart = reg + pMWin->nBufferCol;
1207       KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pPart, 0, 0);
1208       addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPart, pMWin->regPart,nPart);
1209       sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
1210       addrJump = sqlite3VdbeAddOp3(v, OP_Jump, addr+2, 0, addr+2);
1211       windowAggFinal(pParse, pMWin, 1);
1212       if( pOrderBy ){
1213         addrGoto = sqlite3VdbeAddOp0(v, OP_Goto);
1214       }
1215     }
1216
1217     if( pOrderBy ){
1218       int regNewPeer = reg + pMWin->nBufferCol + nPart;
1219       int regPeer = pMWin->regPart + nPart;
1220
1221       if( addrJump ) sqlite3VdbeJumpHere(v, addrJump);
1222       if( pMWin->eType==TK_RANGE ){
1223         KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pOrderBy, 0, 0);
1224         addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPeer, regPeer, nPeer);
1225         sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
1226         addrJump = sqlite3VdbeAddOp3(v, OP_Jump, addr+2, 0, addr+2);
1227       }else{
1228         addrJump = 0;
1229       }
1230       windowAggFinal(pParse, pMWin, pMWin->eStart==TK_CURRENT);
1231       if( addrGoto ) sqlite3VdbeJumpHere(v, addrGoto);
1232     }
1233
1234     sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrGosub);
1235     sqlite3VdbeAddOp1(v, OP_ResetSorter, pMWin->iEphCsr);
1236     sqlite3VdbeAddOp3(
1237         v, OP_Copy, reg+pMWin->nBufferCol, pMWin->regPart, nPart+nPeer-1
1238     );
1239
1240     if( addrJump ) sqlite3VdbeJumpHere(v, addrJump);
1241   }
1242
1243   /* Invoke step function for window functions */
1244   windowAggStep(pParse, pMWin, -1, 0, reg, 0);
1245
1246   /* Buffer the current row in the ephemeral table. */
1247   if( pMWin->nBufferCol>0 ){
1248     sqlite3VdbeAddOp3(v, OP_MakeRecord, reg, pMWin->nBufferCol, regRecord);
1249   }else{
1250     sqlite3VdbeAddOp2(v, OP_Blob, 0, regRecord);
1251     sqlite3VdbeAppendP4(v, (void*)"", 0);
1252   }
1253   sqlite3VdbeAddOp2(v, OP_NewRowid, pMWin->iEphCsr, regRowid);
1254   sqlite3VdbeAddOp3(v, OP_Insert, pMWin->iEphCsr, regRecord, regRowid);
1255
1256   /* End the database scan loop. */
1257   sqlite3WhereEnd(pWInfo);
1258
1259   windowAggFinal(pParse, pMWin, 1);
1260   sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrGosub);
1261 }
1262
1263
1264 /*
1265 ** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
1266 **
1267 **   As above, except take no action for a "new peer". Invoke
1268 **   the sub-routine once only for each partition.
1269 **
1270 ** RANGE BETWEEN CURRENT ROW AND CURRENT ROW
1271 **
1272 **   As above, except that the "new peer" condition is handled in the
1273 **   same way as "new partition" (so there is no "else if" block).
1274 **
1275 ** RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
1276 **
1277 **   One way is to just reverse the sort order and do as for BETWEEN
1278 **   UNBOUNDED PRECEDING AND CURRENT ROW. But that is not quite the same for
1279 **   things like group_concat(). And perhaps other user defined aggregates
1280 **   as well.
1281 **
1282 **   ...
1283 **     if( new partition ){
1284 **       Gosub flush_partition;
1285 **       ResetSorter eph-table
1286 **     }
1287 **     AggStep
1288 **     Insert (record into eph-table)
1289 **   sqlite3WhereEnd()
1290 **   Gosub flush_partition
1291 **
1292 **  flush_partition:
1293 **   OpenDup (csr -> csr2)
1294 **   foreach (record in eph-table) {
1295 **     if( new peer ){
1296 **       while( csr2!=csr ){
1297 **         AggStep (xInverse)
1298 **         Next (csr2)
1299 **       }
1300 **     }
1301 **     AggFinal (xValue)
1302 **     Gosub addrGosub
1303 **   }
1304 **
1305 **========================================================================
1306 **
1307 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1308 **   ...
1309 **     if( new partition ){
1310 **       AggFinal (xFinalize)
1311 **     }
1312 **     AggStep
1313 **     AggFinal (xValue)
1314 **     Gosub addrGosub
1315 **   sqlite3WhereEnd()
1316 **
1317 */
1318 void sqlite3WindowCodeStep(
1319   Parse *pParse,
1320   Select *p,
1321   WhereInfo *pWInfo,
1322   int regGosub,
1323   int addrGosub,
1324   int *pbLoop
1325 ){
1326   Window *pMWin = p->pWin;
1327   Window *pWin;
1328
1329   *pbLoop = 0;
1330   if( (pMWin->eType==TK_ROWS
1331    && (pMWin->eStart!=TK_UNBOUNDED||pMWin->eEnd!=TK_CURRENT||!pMWin->pOrderBy))
1332    || (pMWin->eStart==TK_CURRENT&&pMWin->eEnd==TK_UNBOUNDED&&pMWin->pOrderBy)
1333   ){
1334     windowCodeRowExprStep(pParse, p, pWInfo, regGosub, addrGosub);
1335     return;
1336   }
1337
1338   for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
1339     if( pWin->pFunc->funcFlags & SQLITE_FUNC_WINDOW_SIZE ){
1340       windowCodeCacheStep(pParse, p, pWInfo, regGosub, addrGosub);
1341       return;
1342     }
1343   }
1344
1345   *pbLoop = 1;
1346   windowCodeDefaultStep(pParse, p, pWInfo, regGosub, addrGosub);
1347 }
1348
1349