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 void sqlite3WindowDelete(sqlite3 *db, Window *p){
  15   if( p ){
  16     sqlite3ExprDelete(db, p->pFilter);
  17     sqlite3ExprListDelete(db, p->pPartition);
  18     sqlite3ExprListDelete(db, p->pOrderBy);
  19     sqlite3ExprDelete(db, p->pEnd);
  20     sqlite3ExprDelete(db, p->pStart);
  21     sqlite3DbFree(db, p);
  22   }
  23 }
  24
  25 Window *sqlite3WindowAlloc(
  26   Parse *pParse,
  27   int eType,
  28   int eStart, Expr *pStart,
  29   int eEnd, Expr *pEnd
  30 ){
  31   Window *pWin = (Window*)sqlite3DbMallocZero(pParse->db, sizeof(Window));
  32
  33   if( pWin ){
  34     pWin->eType = eType;
  35     pWin->eStart = eStart;
  36     pWin->eEnd = eEnd;
  37     pWin->pEnd = pEnd;
  38     pWin->pStart = pStart;
  39   }else{
  40     sqlite3ExprDelete(pParse->db, pEnd);
  41     sqlite3ExprDelete(pParse->db, pStart);
  42   }
  43
  44   return pWin;
  45 }
  46
  47 void sqlite3WindowAttach(Parse *pParse, Expr *p, Window *pWin){
  48   if( p ){
  49     p->pWin = pWin;
  50   }else{
  51     sqlite3WindowDelete(pParse->db, pWin);
  52   }
  53 }
  54
  55 /*
  56 ** Return 0 if the two window objects are identical, or non-zero otherwise.
  57 */
  58 int sqlite3WindowCompare(Parse *pParse, Window *p1, Window *p2){
  59   if( p1->eType!=p2->eType ) return 1;
  60   if( p1->eStart!=p2->eStart ) return 1;
  61   if( p1->eEnd!=p2->eEnd ) return 1;
  62   if( sqlite3ExprCompare(pParse, p1->pStart, p2->pStart, -1) ) return 1;
  63   if( sqlite3ExprCompare(pParse, p1->pEnd, p2->pEnd, -1) ) return 1;
  64   if( sqlite3ExprListCompare(p1->pPartition, p2->pPartition, -1) ) return 1;
  65   if( sqlite3ExprListCompare(p1->pOrderBy, p2->pOrderBy, -1) ) return 1;
  66   return 0;
  67 }
  68
  69 void sqlite3WindowCodeInit(Parse *pParse, Window *pWin){
  70   Vdbe *v = sqlite3GetVdbe(pParse);
  71   int nPart = (pWin->pPartition ? pWin->pPartition->nExpr : 0);
  72   nPart += (pWin->pOrderBy ? pWin->pOrderBy->nExpr : 0);
  73   if( nPart ){
  74     pWin->regPart = pParse->nMem+1;
  75     pParse->nMem += nPart;
  76     sqlite3VdbeAddOp3(v, OP_Null, 0, pWin->regPart, pWin->regPart+nPart-1);
  77   }
  78 }
  79
  80 static void windowCheckFrameValue(Parse *pParse, int reg, int bEnd){
  81   static const char *azErr[] = {
  82     "frame starting offset must be a non-negative integer",
  83     "frame ending offset must be a non-negative integer"
  84   };
  85   Vdbe *v = sqlite3GetVdbe(pParse);
  86   int regZero = ++pParse->nMem;
  87
  88
  89   sqlite3VdbeAddOp2(v, OP_Integer, 0, regZero);
  90   sqlite3VdbeAddOp2(v, OP_MustBeInt, reg, sqlite3VdbeCurrentAddr(v)+2);
  91   sqlite3VdbeAddOp3(v, OP_Ge, regZero, sqlite3VdbeCurrentAddr(v)+2, reg);
  92   sqlite3VdbeAddOp2(v, OP_Halt, SQLITE_ERROR, OE_Abort);
  93   sqlite3VdbeAppendP4(v, (void*)azErr[bEnd], P4_STATIC);
  94 }
  95
  96 static void windowAggStep(
  97   Parse *pParse,
  98   Window *pMWin,
  99   int csr,
 100   int bInverse,
 101   int reg
 102 ){
 103   Vdbe *v = sqlite3GetVdbe(pParse);
 104   Window *pWin;
 105   for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
 106     int i;
 107     for(i=0; i<pWin->nArg; i++){
 108       sqlite3VdbeAddOp3(v, OP_Column, csr, pWin->iArgCol+i, reg+i);
 109     }
 110     sqlite3VdbeAddOp3(v, OP_AggStep0, bInverse, reg, pWin->regAccum);
 111     sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
 112     sqlite3VdbeChangeP5(v, (u8)pWin->nArg);
 113   }
 114 }
 115
 116 /*
 117 ** ROWS BETWEEN <expr1> PRECEDING AND <expr2> FOLLOWING
 118 ** ----------------------------------------------------
 119 **
 120 ** Pseudo-code for the implementation of this window frame type is as
 121 ** follows. sqlite3WhereBegin() has already been called to generate the
 122 ** top of the main loop when this function is called.
 123 **
 124 ** Each time the sub-routine at addrGosub is invoked, a single output
 125 ** row is generated based on the current row indicated by Window.iEphCsr.
 126 **
 127 **     ...
 128 **       if( new partition ){
 129 **         Gosub flush_partition
 130 **       }
 131 **       Insert (record in eph-table)
 132 **     sqlite3WhereEnd()
 133 **     Gosub flush_partition
 134 **
 135 **   flush_partition:
 136 **     Once {
 137 **       OpenDup (iEphCsr -> csrStart)
 138 **       OpenDup (iEphCsr -> csrEnd)
 139 **     }
 140 **     regStart = <expr1>                // PRECEDING expression
 141 **     regEnd = <expr2>                  // FOLLOWING expression
 142 **     if( regStart<0 || regEnd<0 ){ error! }
 143 **     Rewind (csr,csrStart,csrEnd)      // if EOF goto flush_partition_done
 144 **       Next(csrEnd)                    // if EOF skip Aggstep
 145 **       Aggstep (csrEnd)
 146 **       if( (regEnd--)<=0 ){
 147 **         AggFinal (xValue)
 148 **         Gosub addrGosub
 149 **         Next(csr)                // if EOF goto flush_partition_done
 150 **         if( (regStart--)<=0 ){
 151 **           AggStep (csrStart, xInverse)
 152 **           Next(csrStart)
 153 **         }
 154 **       }
 155 **   flush_partition_done:
 156 **     ResetSorter (csr)
 157 **     Return
 158 **
 159 ** ROWS BETWEEN <expr> PRECEDING    AND CURRENT ROW
 160 ** ROWS BETWEEN CURRENT ROW         AND <expr> FOLLOWING
 161 ** ROWS BETWEEN UNBOUNDED PRECEDING AND <expr> FOLLOWING
 162 **
 163 **   These are similar to the above. For "CURRENT ROW", intialize the
 164 **   register to 0. For "UNBOUNDED PRECEDING" to infinity.
 165 **
 166 ** ROWS BETWEEN <expr> PRECEDING    AND UNBOUNDED FOLLOWING
 167 ** ROWS BETWEEN CURRENT ROW         AND UNBOUNDED FOLLOWING
 168 **
 169 **     Rewind (csr,csrStart,csrEnd)    // if EOF goto flush_partition_done
 170 **     while( 1 ){
 171 **       Next(csrEnd)                  // Exit while(1) at EOF
 172 **       Aggstep (csrEnd)
 173 **     }
 174 **     while( 1 ){
 175 **       AggFinal (xValue)
 176 **       Gosub addrGosub
 177 **       Next(csr)                     // if EOF goto flush_partition_done
 178 **       if( (regStart--)<=0 ){
 179 **         AggStep (csrStart, xInverse)
 180 **         Next(csrStart)
 181 **       }
 182 **     }
 183 **
 184 **   For the "CURRENT ROW AND UNBOUNDED FOLLOWING" case, the final if()
 185 **   condition is always true (as if regStart were initialized to 0).
 186 **
 187 ** RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
 188 **
 189 **   This is the only RANGE case handled by this routine. It modifies the
 190 **   second while( 1 ) loop in "ROWS BETWEEN CURRENT ... UNBOUNDED..." to
 191 **   be:
 192 **
 193 **     while( 1 ){
 194 **       AggFinal (xValue)
 195 **       while( 1 ){
 196 **         regPeer++
 197 **         Gosub addrGosub
 198 **         Next(csr)                     // if EOF goto flush_partition_done
 199 **         if( new peer ) break;
 200 **       }
 201 **       while( (regPeer--)>0 ){
 202 **         AggStep (csrStart, xInverse)
 203 **         Next(csrStart)
 204 **       }
 205 **     }
 206 **
 207 ** ROWS BETWEEN <expr> FOLLOWING    AND <expr> FOLLOWING
 208 **
 209 **   regEnd = regEnd - regStart
 210 **   Rewind (csr,csrStart,csrEnd)   // if EOF goto flush_partition_done
 211 **     Aggstep (csrEnd)
 212 **     Next(csrEnd)                 // if EOF fall-through
 213 **     if( (regEnd--)<=0 ){
 214 **       if( (regStart--)<=0 ){
 215 **         AggFinal (xValue)
 216 **         Gosub addrGosub
 217 **         Next(csr)              // if EOF goto flush_partition_done
 218 **       }
 219 **       AggStep (csrStart, xInverse)
 220 **       Next (csrStart)
 221 **     }
 222 **
 223 ** ROWS BETWEEN <expr> PRECEDING    AND <expr> PRECEDING
 224 **
 225 **   Replace the bit after "Rewind" in the above with:
 226 **
 227 **     if( (regEnd--)<=0 ){
 228 **       AggStep (csrEnd)
 229 **       Next (csrEnd)
 230 **     }
 231 **     AggFinal (xValue)
 232 **     Gosub addrGosub
 233 **     Next(csr)                  // if EOF goto flush_partition_done
 234 **     if( (regStart--)<=0 ){
 235 **       AggStep (csr2, xInverse)
 236 **       Next (csr2)
 237 **     }
 238 **
 239 */
 240 static void windowCodeRowExprStep(
 241   Parse *pParse,
 242   Select *p,
 243   WhereInfo *pWInfo,
 244   int regGosub,
 245   int addrGosub
 246 ){
 247   Window *pMWin = p->pWin;
 248   Vdbe *v = sqlite3GetVdbe(pParse);
 249   Window *pWin;
 250   int k;
 251   int iSubCsr = p->pSrc->a[0].iCursor;
 252   int nSub = p->pSrc->a[0].pTab->nCol;
 253   int regFlushPart;               /* Register for "Gosub flush_partition" */
 254   int lblFlushPart;               /* Label for "Gosub flush_partition" */
 255   int lblFlushDone;               /* Label for "Gosub flush_partition_done" */
 256
 257   int reg = pParse->nMem+1;
 258   int regRecord = reg+nSub;
 259   int regRowid = regRecord+1;
 260   int addr;
 261   int csrStart = pParse->nTab++;
 262   int csrEnd = pParse->nTab++;
 263   int regStart;                    /* Value of <expr> PRECEDING */
 264   int regEnd;                      /* Value of <expr> FOLLOWING */
 265   int addrNext;
 266   int addrGoto;
 267   int addrTop;
 268   int addrIfPos1;
 269   int addrIfPos2;
 270
 271   int regPeer = 0;                 /* Number of peers in current group */
 272   int regPeerVal = 0;              /* Array of values identifying peer group */
 273   int iPeer = 0;                   /* Column offset in eph-table of peer vals */
 274   int nPeerVal;                    /* Number of peer values */
 275
 276   assert( pMWin->eStart==TK_PRECEDING
 277        || pMWin->eStart==TK_CURRENT
 278        || pMWin->eStart==TK_FOLLOWING
 279        || pMWin->eStart==TK_UNBOUNDED
 280   );
 281   assert( pMWin->eEnd==TK_FOLLOWING
 282        || pMWin->eEnd==TK_CURRENT
 283        || pMWin->eEnd==TK_UNBOUNDED
 284        || pMWin->eEnd==TK_PRECEDING
 285   );
 286
 287   pParse->nMem += nSub + 2;
 288
 289   /* Allocate register and label for the "flush_partition" sub-routine. */
 290   regFlushPart = ++pParse->nMem;
 291   lblFlushPart = sqlite3VdbeMakeLabel(v);
 292   lblFlushDone = sqlite3VdbeMakeLabel(v);
 293
 294   regStart = ++pParse->nMem;
 295   regEnd = ++pParse->nMem;
 296
 297   /* Martial the row returned by the sub-select into an array of
 298   ** registers. */
 299   for(k=0; k<nSub; k++){
 300     sqlite3VdbeAddOp3(v, OP_Column, iSubCsr, k, reg+k);
 301   }
 302   sqlite3VdbeAddOp3(v, OP_MakeRecord, reg, nSub, regRecord);
 303
 304   /* Check if this is the start of a new partition. If so, call the
 305   ** flush_partition sub-routine.  */
 306   if( pMWin->pPartition ){
 307     ExprList *pPart = pMWin->pPartition;
 308     int nPart = (pPart ? pPart->nExpr : 0);
 309     int addrJump = 0;
 310     int regNewPart = reg + pMWin->nBufferCol;
 311     KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pPart, 0, 0);
 312
 313     addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPart, pMWin->regPart,nPart);
 314     sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
 315     addrJump = sqlite3VdbeAddOp3(v, OP_Jump, addr+2, addr+4, addr+2);
 316     sqlite3VdbeAddOp2(v, OP_Gosub, regFlushPart, lblFlushPart);
 317     sqlite3VdbeAddOp3(v, OP_Copy, regNewPart, pMWin->regPart, nPart);
 318   }
 319
 320   /* Buffer the current row in the ephemeral table. */
 321   sqlite3VdbeAddOp2(v, OP_NewRowid, pMWin->iEphCsr, regRowid);
 322   sqlite3VdbeAddOp3(v, OP_Insert, pMWin->iEphCsr, regRecord, regRowid);
 323
 324   /* End of the input loop */
 325   sqlite3WhereEnd(pWInfo);
 326
 327   /* Invoke "flush_partition" to deal with the final (or only) partition */
 328   sqlite3VdbeAddOp2(v, OP_Gosub, regFlushPart, lblFlushPart);
 329   addrGoto = sqlite3VdbeAddOp0(v, OP_Goto);
 330
 331   /* flush_partition: */
 332   sqlite3VdbeResolveLabel(v, lblFlushPart);
 333   sqlite3VdbeAddOp2(v, OP_Once, 0, sqlite3VdbeCurrentAddr(v)+3);
 334   sqlite3VdbeAddOp2(v, OP_OpenDup, csrStart, pMWin->iEphCsr);
 335   sqlite3VdbeAddOp2(v, OP_OpenDup, csrEnd, pMWin->iEphCsr);
 336
 337   /* If either regStart or regEnd are not non-negative integers, throw
 338   ** an exception.  */
 339   if( pMWin->pStart ){
 340     sqlite3ExprCode(pParse, pMWin->pStart, regStart);
 341     windowCheckFrameValue(pParse, regStart, 0);
 342   }
 343   if( pMWin->pEnd ){
 344     sqlite3ExprCode(pParse, pMWin->pEnd, regEnd);
 345     windowCheckFrameValue(pParse, regEnd, 1);
 346     if( pMWin->pStart && pMWin->eStart==TK_FOLLOWING ){
 347       assert( pMWin->eEnd==TK_FOLLOWING );
 348       sqlite3VdbeAddOp3(v, OP_Subtract, regStart, regEnd, regEnd);
 349     }
 350   }
 351
 352   for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
 353     sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);
 354   }
 355
 356   sqlite3VdbeAddOp2(v, OP_Rewind, pMWin->iEphCsr, lblFlushDone);
 357   sqlite3VdbeAddOp2(v, OP_Rewind, csrStart, lblFlushDone);
 358   sqlite3VdbeChangeP5(v, 1);
 359   sqlite3VdbeAddOp2(v, OP_Rewind, csrEnd, lblFlushDone);
 360   sqlite3VdbeChangeP5(v, 1);
 361
 362   /* Invoke AggStep function for each window function using the row that
 363   ** csrEnd currently points to. Or, if csrEnd is already at EOF,
 364   ** do nothing.  */
 365   addrTop = sqlite3VdbeCurrentAddr(v);
 366   if( pMWin->eEnd==TK_PRECEDING ){
 367     addrIfPos1 = sqlite3VdbeAddOp3(v, OP_IfPos, regEnd, 0 , 1);
 368   }
 369   sqlite3VdbeAddOp2(v, OP_Next, csrEnd, sqlite3VdbeCurrentAddr(v)+2);
 370   addr = sqlite3VdbeAddOp0(v, OP_Goto);
 371   windowAggStep(pParse, pMWin, csrEnd, 0, reg);
 372   if( pMWin->eEnd==TK_UNBOUNDED ){
 373     sqlite3VdbeAddOp2(v, OP_Goto, 0, addrTop);
 374     sqlite3VdbeJumpHere(v, addr);
 375     addrTop = sqlite3VdbeCurrentAddr(v);
 376   }else{
 377     sqlite3VdbeJumpHere(v, addr);
 378     if( pMWin->eEnd==TK_PRECEDING ){
 379       sqlite3VdbeJumpHere(v, addrIfPos1);
 380     }
 381   }
 382
 383   if( pMWin->eEnd==TK_FOLLOWING ){
 384     addrIfPos1 = sqlite3VdbeAddOp3(v, OP_IfPos, regEnd, 0 , 1);
 385   }
 386   if( pMWin->eStart==TK_FOLLOWING ){
 387     addrIfPos2 = sqlite3VdbeAddOp3(v, OP_IfPos, regStart, 0 , 1);
 388   }
 389   if( pMWin->eType==TK_RANGE ){
 390     assert( pMWin->eStart==TK_CURRENT && pMWin->pOrderBy );
 391     regPeer = ++pParse->nMem;
 392     regPeerVal = pParse->nMem+1;
 393     iPeer = pMWin->nBufferCol + (pMWin->pPartition?pMWin->pPartition->nExpr:0);
 394     nPeerVal = pMWin->pOrderBy->nExpr;
 395     pParse->nMem += (2 * nPeerVal);
 396     for(k=0; k<nPeerVal; k++){
 397       sqlite3VdbeAddOp3(v, OP_Column, pMWin->iEphCsr, iPeer+k, regPeerVal+k);
 398     }
 399     sqlite3VdbeAddOp2(v, OP_Integer, 0, regPeer);
 400   }
 401   for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
 402     sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regResult);
 403     sqlite3VdbeAddOp3(v,
 404         OP_AggFinal, pWin->regAccum, pWin->nArg, pWin->regResult
 405     );
 406     sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
 407   }
 408   if( pMWin->eType==TK_RANGE ){
 409     sqlite3VdbeAddOp2(v, OP_AddImm, regPeer, 1);
 410   }
 411   sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrGosub);
 412   sqlite3VdbeAddOp2(v, OP_Next, pMWin->iEphCsr, sqlite3VdbeCurrentAddr(v)+2);
 413   sqlite3VdbeAddOp2(v, OP_Goto, 0, lblFlushDone);
 414   if( pMWin->eType==TK_RANGE ){
 415     KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pMWin->pOrderBy,0,0);
 416     int addrJump = sqlite3VdbeCurrentAddr(v)-4;
 417     for(k=0; k<nPeerVal; k++){
 418       int iOut = regPeerVal + nPeerVal + k;
 419       sqlite3VdbeAddOp3(v, OP_Column, pMWin->iEphCsr, iPeer+k, iOut);
 420     }
 421     sqlite3VdbeAddOp3(v, OP_Compare, regPeerVal, regPeerVal+nPeerVal, nPeerVal);
 422     sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
 423     addr = sqlite3VdbeCurrentAddr(v)+1;
 424     sqlite3VdbeAddOp3(v, OP_Jump, addr, addrJump, addr);
 425   }
 426   if( pMWin->eStart==TK_FOLLOWING ){
 427     sqlite3VdbeJumpHere(v, addrIfPos2);
 428   }
 429
 430   if( pMWin->eStart==TK_CURRENT
 431    || pMWin->eStart==TK_PRECEDING
 432    || pMWin->eStart==TK_FOLLOWING
 433   ){
 434     int addrJumpHere = 0;
 435     if( pMWin->eStart==TK_PRECEDING ){
 436       addrJumpHere = sqlite3VdbeAddOp3(v, OP_IfPos, regStart, 0 , 1);
 437     }
 438     if( pMWin->eType==TK_RANGE ){
 439       sqlite3VdbeAddOp3(v, OP_IfPos, regPeer, sqlite3VdbeCurrentAddr(v)+2, 1);
 440       addrJumpHere = sqlite3VdbeAddOp0(v, OP_Goto);
 441     }
 442     sqlite3VdbeAddOp2(v, OP_Next, csrStart, sqlite3VdbeCurrentAddr(v)+1);
 443     windowAggStep(pParse, pMWin, csrStart, 1, reg);
 444     if( pMWin->eType==TK_RANGE ){
 445       sqlite3VdbeAddOp2(v, OP_Goto, 0, addrJumpHere-1);
 446     }
 447     if( addrJumpHere ){
 448       sqlite3VdbeJumpHere(v, addrJumpHere);
 449     }
 450   }
 451   if( pMWin->eEnd==TK_FOLLOWING ){
 452     sqlite3VdbeJumpHere(v, addrIfPos1);
 453   }
 454   sqlite3VdbeAddOp2(v, OP_Goto, 0, addrTop);
 455
 456   /* flush_partition_done: */
 457   sqlite3VdbeResolveLabel(v, lblFlushDone);
 458   sqlite3VdbeAddOp1(v, OP_ResetSorter, pMWin->iEphCsr);
 459   sqlite3VdbeAddOp1(v, OP_Return, regFlushPart);
 460
 461   /* Jump to here to skip over flush_partition */
 462   sqlite3VdbeJumpHere(v, addrGoto);
 463 }
 464
 465 /*
 466 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
 467 **
 468 **   ...
 469 **     if( new partition ){
 470 **       AggFinal (xFinalize)
 471 **       Gosub addrGosub
 472 **       ResetSorter eph-table
 473 **     }
 474 **     else if( new peer ){
 475 **       AggFinal (xValue)
 476 **       Gosub addrGosub
 477 **       ResetSorter eph-table
 478 **     }
 479 **     AggStep
 480 **     Insert (record into eph-table)
 481 **   sqlite3WhereEnd()
 482 **   AggFinal (xFinalize)
 483 **   Gosub addrGosub
 484 */
 485 static void windowCodeDefaultStep(
 486   Parse *pParse,
 487   Select *p,
 488   WhereInfo *pWInfo,
 489   int regGosub,
 490   int addrGosub
 491 ){
 492   Window *pMWin = p->pWin;
 493   Vdbe *v = sqlite3GetVdbe(pParse);
 494   Window *pWin;
 495   int k;
 496   int iSubCsr = p->pSrc->a[0].iCursor;
 497   int nSub = p->pSrc->a[0].pTab->nCol;
 498   int reg = pParse->nMem+1;
 499   int regRecord = reg+nSub;
 500   int regRowid = regRecord+1;
 501   int addr;
 502
 503   assert( pMWin->eType==TK_RANGE
 504       || (pMWin->eStart==TK_UNBOUNDED && pMWin->eEnd==TK_CURRENT)
 505   );
 506
 507   pParse->nMem += nSub + 2;
 508
 509   /* Martial the row returned by the sub-select into an array of
 510   ** registers. */
 511   for(k=0; k<nSub; k++){
 512     sqlite3VdbeAddOp3(v, OP_Column, iSubCsr, k, reg+k);
 513   }
 514
 515   /* Check if this is the start of a new partition or peer group. */
 516   if( pMWin->regPart ){
 517     ExprList *pPart = pMWin->pPartition;
 518     int nPart = (pPart ? pPart->nExpr : 0);
 519     ExprList *pOrderBy = pMWin->pOrderBy;
 520     int nPeer = (pOrderBy ? pOrderBy->nExpr : 0);
 521     int addrGoto = 0;
 522     int addrJump = 0;
 523
 524     if( pPart ){
 525       int regNewPart = reg + pMWin->nBufferCol;
 526       KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pPart, 0, 0);
 527       addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPart, pMWin->regPart,nPart);
 528       sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
 529       addrJump = sqlite3VdbeAddOp3(v, OP_Jump, addr+2, 0, addr+2);
 530       for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
 531         sqlite3VdbeAddOp2(v, OP_AggFinal, pWin->regAccum, pWin->nArg);
 532         sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
 533         sqlite3VdbeAddOp2(v, OP_Copy, pWin->regAccum, pWin->regResult);
 534       }
 535       if( pOrderBy ){
 536         addrGoto = sqlite3VdbeAddOp0(v, OP_Goto);
 537       }
 538     }
 539
 540     if( pOrderBy ){
 541       int regNewPeer = reg + pMWin->nBufferCol + nPart;
 542       int regPeer = pMWin->regPart + nPart;
 543
 544       if( addrJump ) sqlite3VdbeJumpHere(v, addrJump);
 545       if( pMWin->eType==TK_RANGE ){
 546         KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pOrderBy, 0, 0);
 547         addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPeer, regPeer, nPeer);
 548         sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
 549         addrJump = sqlite3VdbeAddOp3(v, OP_Jump, addr+2, 0, addr+2);
 550       }else{
 551         addrJump = 0;
 552       }
 553       for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
 554         sqlite3VdbeAddOp3(v,
 555             OP_AggFinal, pWin->regAccum, pWin->nArg, pWin->regResult
 556         );
 557         sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
 558       }
 559       if( addrGoto ) sqlite3VdbeJumpHere(v, addrGoto);
 560     }
 561
 562     sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrGosub);
 563     sqlite3VdbeAddOp1(v, OP_ResetSorter, pMWin->iEphCsr);
 564     sqlite3VdbeAddOp3(
 565         v, OP_Copy, reg+pMWin->nBufferCol, pMWin->regPart, nPart+nPeer-1
 566     );
 567
 568     if( addrJump ) sqlite3VdbeJumpHere(v, addrJump);
 569   }
 570
 571   /* Invoke step function for window functions */
 572   for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
 573     sqlite3VdbeAddOp3(v, OP_AggStep0, 0, reg+pWin->iArgCol, pWin->regAccum);
 574     sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
 575     sqlite3VdbeChangeP5(v, (u8)pWin->nArg);
 576   }
 577
 578   /* Buffer the current row in the ephemeral table. */
 579   if( pMWin->nBufferCol>0 ){
 580     sqlite3VdbeAddOp3(v, OP_MakeRecord, reg, pMWin->nBufferCol, regRecord);
 581   }else{
 582     sqlite3VdbeAddOp2(v, OP_Blob, 0, regRecord);
 583     sqlite3VdbeAppendP4(v, (void*)"", 0);
 584   }
 585   sqlite3VdbeAddOp2(v, OP_NewRowid, pMWin->iEphCsr, regRowid);
 586   sqlite3VdbeAddOp3(v, OP_Insert, pMWin->iEphCsr, regRecord, regRowid);
 587
 588   /* End the database scan loop. */
 589   sqlite3WhereEnd(pWInfo);
 590
 591   for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
 592     sqlite3VdbeAddOp2(v, OP_AggFinal, pWin->regAccum, pWin->nArg);
 593     sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
 594     sqlite3VdbeAddOp2(v, OP_Copy, pWin->regAccum, pWin->regResult);
 595   }
 596   sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrGosub);
 597 }
 598
 599
 600 /*
 601 ** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
 602 **
 603 **   As above, except take no action for a "new peer". Invoke
 604 **   the sub-routine once only for each partition.
 605 **
 606 ** RANGE BETWEEN CURRENT ROW AND CURRENT ROW
 607 **
 608 **   As above, except that the "new peer" condition is handled in the
 609 **   same way as "new partition" (so there is no "else if" block).
 610 **
 611 ** RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
 612 **
 613 **   One way is to just reverse the sort order and do as for BETWEEN
 614 **   UNBOUNDED PRECEDING AND CURRENT ROW. But that is not quite the same for
 615 **   things like group_concat(). And perhaps other user defined aggregates
 616 **   as well.
 617 **
 618 **   ...
 619 **     if( new partition ){
 620 **       Gosub flush_partition;
 621 **       ResetSorter eph-table
 622 **     }
 623 **     AggStep
 624 **     Insert (record into eph-table)
 625 **   sqlite3WhereEnd()
 626 **   Gosub flush_partition
 627 **
 628 **  flush_partition:
 629 **   OpenDup (csr -> csr2)
 630 **   foreach (record in eph-table) {
 631 **     if( new peer ){
 632 **       while( csr2!=csr ){
 633 **         AggStep (xInverse)
 634 **         Next (csr2)
 635 **       }
 636 **     }
 637 **     AggFinal (xValue)
 638 **     Gosub addrGosub
 639 **   }
 640 **
 641 **========================================================================
 642 **
 643 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
 644 **   ...
 645 **     if( new partition ){
 646 **       AggFinal (xFinalize)
 647 **     }
 648 **     AggStep
 649 **     AggFinal (xValue)
 650 **     Gosub addrGosub
 651 **   sqlite3WhereEnd()
 652 **
 653 */
 654 void sqlite3WindowCodeStep(
 655   Parse *pParse,
 656   Select *p,
 657   WhereInfo *pWInfo,
 658   int regGosub,
 659   int addrGosub,
 660   int *pbLoop
 661 ){
 662   Window *pMWin = p->pWin;
 663
 664   if( (pMWin->eType==TK_ROWS
 665    && (pMWin->eStart!=TK_UNBOUNDED || pMWin->eEnd!=TK_CURRENT))
 666    || (pMWin->eStart==TK_CURRENT && pMWin->eEnd==TK_UNBOUNDED)
 667   ){
 668     *pbLoop = 0;
 669     windowCodeRowExprStep(pParse, p, pWInfo, regGosub, addrGosub);
 670     return;
 671   }
 672
 673   *pbLoop = 1;
 674   windowCodeDefaultStep(pParse, p, pWInfo, regGosub, addrGosub);
 675 }
 676
 677