SQLite
Check-in [c9f0f14094]
Not logged in
Overview
Comment:Evaluate multiple window functions in a single pass if they use the same window definition. Add xValue callbacks for other built-in aggregate functions.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | exp-window-functions
Files: files | file ages | folders
SHA3-256:c9f0f140941660ff368e5bb5752d54feb1964b7a9eac986d4bfb8f24a1c20d86
User & Date: dan 2018-05-17 19:24:08
Context
2018-05-19
14:15
Fix minor problems on this branch. check-in: 19c2e4b2f1 user: dan tags: exp-window-functions
2018-05-17
19:24
Evaluate multiple window functions in a single pass if they use the same window definition. Add xValue callbacks for other built-in aggregate functions. check-in: c9f0f14094 user: dan tags: exp-window-functions
14:26
Handle multiple window-functions in a single query. check-in: 35af0b750e user: dan tags: exp-window-functions
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/expr.c.

1282
1283
1284
1285
1286
1287
1288



1289

1290
1291
1292
1293
1294
1295
1296
        pNew->pRight = p->pRight ?
                       exprDup(db, p->pRight, EXPRDUP_REDUCE, &zAlloc) : 0;
      }
      if( pzBuffer ){
        *pzBuffer = zAlloc;
      }
    }else{



      pNew->pWin = winDup(db, p->pWin);

      if( !ExprHasProperty(p, EP_TokenOnly|EP_Leaf) ){
        if( pNew->op==TK_SELECT_COLUMN ){
          pNew->pLeft = p->pLeft;
          assert( p->iColumn==0 || p->pRight==0 );
          assert( p->pRight==0  || p->pRight==p->pLeft );
        }else{
          pNew->pLeft = sqlite3ExprDup(db, p->pLeft, 0);







>
>
>
|
>







1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
        pNew->pRight = p->pRight ?
                       exprDup(db, p->pRight, EXPRDUP_REDUCE, &zAlloc) : 0;
      }
      if( pzBuffer ){
        *pzBuffer = zAlloc;
      }
    }else{
      if( ExprHasProperty(p, EP_Reduced|EP_TokenOnly) ){
        pNew->pWin = 0;
      }else{
        pNew->pWin = winDup(db, p->pWin);
      }
      if( !ExprHasProperty(p, EP_TokenOnly|EP_Leaf) ){
        if( pNew->op==TK_SELECT_COLUMN ){
          pNew->pLeft = p->pLeft;
          assert( p->iColumn==0 || p->pRight==0 );
          assert( p->pRight==0  || p->pRight==p->pLeft );
        }else{
          pNew->pLeft = sqlite3ExprDup(db, p->pLeft, 0);

Changes to src/func.c.

1671
1672
1673
1674
1675
1676
1677














1678
1679
1680
1681
1682
1683
1684
....
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868

1869

1870
1871
1872
1873
1874
1875
1876
      sqlite3_result_error_nomem(context);
    }else{    
      sqlite3_result_text(context, sqlite3StrAccumFinish(pAccum), -1, 
                          sqlite3_free);
    }
  }
}















/*
** This routine does per-connection function registration.  Most
** of the built-in functions above are part of the global function set.
** This routine only deals with those that are not global.
*/
void sqlite3RegisterPerConnectionBuiltinFunctions(sqlite3 *db){
................................................................................
    VFUNCTION(last_insert_rowid, 0, 0, 0, last_insert_rowid),
    VFUNCTION(changes,           0, 0, 0, changes          ),
    VFUNCTION(total_changes,     0, 0, 0, total_changes    ),
    FUNCTION(replace,            3, 0, 0, replaceFunc      ),
    FUNCTION(zeroblob,           1, 0, 0, zeroblobFunc     ),
    FUNCTION(substr,             2, 0, 0, substrFunc       ),
    FUNCTION(substr,             3, 0, 0, substrFunc       ),
    WFUNCTION(sum,               1, 0, sumStep, sumFinalize, sumFinalize, 0),
    AGGREGATE(total,             1, 0, 0, sumStep,         totalFinalize    ),
    AGGREGATE(avg,               1, 0, 0, sumStep,         avgFinalize    ),
    AGGREGATE2(count,            0, 0, 0, countStep,       countFinalize,
               SQLITE_FUNC_COUNT  ),
    AGGREGATE(count,             1, 0, 0, countStep,       countFinalize  ),
    AGGREGATE(group_concat,      1, 0, 0, groupConcatStep, groupConcatFinalize),

    AGGREGATE(group_concat,      2, 0, 0, groupConcatStep, groupConcatFinalize),

  
    LIKEFUNC(glob, 2, &globInfo, SQLITE_FUNC_LIKE|SQLITE_FUNC_CASE),
#ifdef SQLITE_CASE_SENSITIVE_LIKE
    LIKEFUNC(like, 2, &likeInfoAlt, SQLITE_FUNC_LIKE|SQLITE_FUNC_CASE),
    LIKEFUNC(like, 3, &likeInfoAlt, SQLITE_FUNC_LIKE|SQLITE_FUNC_CASE),
#else
    LIKEFUNC(like, 2, &likeInfoNorm, SQLITE_FUNC_LIKE),







>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







|
|
|


|
|
>
|
>







1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
....
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
      sqlite3_result_error_nomem(context);
    }else{    
      sqlite3_result_text(context, sqlite3StrAccumFinish(pAccum), -1, 
                          sqlite3_free);
    }
  }
}
static void groupConcatValue(sqlite3_context *context){
  sqlite3_str *pAccum;
  pAccum = (sqlite3_str*)sqlite3_aggregate_context(context, 0);
  if( pAccum ){
    if( pAccum->accError==SQLITE_TOOBIG ){
      sqlite3_result_error_toobig(context);
    }else if( pAccum->accError==SQLITE_NOMEM ){
      sqlite3_result_error_nomem(context);
    }else{    
      const char *zText = sqlite3_str_value(pAccum);
      sqlite3_result_text(context, zText, -1, SQLITE_TRANSIENT);
    }
  }
}

/*
** This routine does per-connection function registration.  Most
** of the built-in functions above are part of the global function set.
** This routine only deals with those that are not global.
*/
void sqlite3RegisterPerConnectionBuiltinFunctions(sqlite3 *db){
................................................................................
    VFUNCTION(last_insert_rowid, 0, 0, 0, last_insert_rowid),
    VFUNCTION(changes,           0, 0, 0, changes          ),
    VFUNCTION(total_changes,     0, 0, 0, total_changes    ),
    FUNCTION(replace,            3, 0, 0, replaceFunc      ),
    FUNCTION(zeroblob,           1, 0, 0, zeroblobFunc     ),
    FUNCTION(substr,             2, 0, 0, substrFunc       ),
    FUNCTION(substr,             3, 0, 0, substrFunc       ),
    WAGGREGATE(sum,               1, 0, 0, sumStep,         sumFinalize),
    WAGGREGATE(total,             1, 0, 0, sumStep,         totalFinalize    ),
    WAGGREGATE(avg,               1, 0, 0, sumStep,         avgFinalize    ),
    AGGREGATE2(count,            0, 0, 0, countStep,       countFinalize,
               SQLITE_FUNC_COUNT  ),
    WAGGREGATE(count,             1, 0, 0, countStep,       countFinalize  ),
    AGGREGATE(group_concat,      1, 0, 0, groupConcatStep, groupConcatFinalize,
        groupConcatValue),
    AGGREGATE(group_concat,      2, 0, 0, groupConcatStep, groupConcatFinalize,
        groupConcatValue),
  
    LIKEFUNC(glob, 2, &globInfo, SQLITE_FUNC_LIKE|SQLITE_FUNC_CASE),
#ifdef SQLITE_CASE_SENSITIVE_LIKE
    LIKEFUNC(like, 2, &likeInfoAlt, SQLITE_FUNC_LIKE|SQLITE_FUNC_CASE),
    LIKEFUNC(like, 3, &likeInfoAlt, SQLITE_FUNC_LIKE|SQLITE_FUNC_CASE),
#else
    LIKEFUNC(like, 2, &likeInfoNorm, SQLITE_FUNC_LIKE),

Changes to src/resolve.c.

772
773
774
775
776
777
778



779
780

781
782
783
784
785
786
787
788
789
790
791
792
             nId, zId);
        pNC->nErr++;
      }
      if( is_agg ) pNC->ncFlags &= ~NC_AllowAgg;
      sqlite3WalkExprList(pWalker, pList);
      if( is_agg ){
        if( pExpr->pWin ){



          pExpr->pWin->pNextWin = pNC->pWin;
          pNC->pWin = pExpr->pWin;

          pExpr->pWin->pFunc = pDef;
          pExpr->pWin->nArg = pExpr->x.pList->nExpr;
        }
        else
        {
          NameContext *pNC2 = pNC;
          pExpr->op = TK_AGG_FUNCTION;
          pExpr->op2 = 0;
          while( pNC2 && !sqlite3FunctionUsesThisSrc(pExpr, pNC2->pSrcList) ){
            pExpr->op2++;
            pNC2 = pNC2->pNext;
          }







>
>
>
|
|
>

|
<
|
<







772
773
774
775
776
777
778
779
780
781
782
783
784
785
786

787

788
789
790
791
792
793
794
             nId, zId);
        pNC->nErr++;
      }
      if( is_agg ) pNC->ncFlags &= ~NC_AllowAgg;
      sqlite3WalkExprList(pWalker, pList);
      if( is_agg ){
        if( pExpr->pWin ){
          if( 0==pNC->pWin 
           || 0==sqlite3WindowCompare(pParse, pNC->pWin, pExpr->pWin) 
          ){
            pExpr->pWin->pNextWin = pNC->pWin;
            pNC->pWin = pExpr->pWin;
          }
          pExpr->pWin->pFunc = pDef;
          pExpr->pWin->nArg = (pExpr->x.pList ? pExpr->x.pList->nExpr : 0);

        }else{

          NameContext *pNC2 = pNC;
          pExpr->op = TK_AGG_FUNCTION;
          pExpr->op2 = 0;
          while( pNC2 && !sqlite3FunctionUsesThisSrc(pExpr, pNC2->pSrcList) ){
            pExpr->op2++;
            pNC2 = pNC2->pNext;
          }

Changes to src/select.c.

5411
5412
5413
5414
5415
5416
5417
5418
5419
5420
5421
5422
5423
5424



5425
5426
5427
5428



5429
5430
5431
5432
5433
5434
5435
....
5447
5448
5449
5450
5451
5452
5453
5454
5455
5456
5457
5458
5459
5460
5461
....
5528
5529
5530
5531
5532
5533
5534
5535

5536
5537
5538
5539
5540
5541
5542
5543
5544
5545
5546
5547
5548
5549
5550
5551
5552
5553
5554
5555
5556
5557
5558
5559
5560
5561
5562
5563
5564
5565
5566
5567



5568
5569




5570
5571
5572
5573
5574
5575
5576
....
5578
5579
5580
5581
5582
5583
5584
5585
5586
5587
5588
5589
5590
5591
5592
5593
5594
5595
5596
5597
5598
5599
5600
5601
5602
5603
....
6057
6058
6059
6060
6061
6062
6063
6064
6065
6066
6067
6068
6069
6070
6071
6072
6073
6074
6075
6076
6077
6078
6079
6080
6081
....
6103
6104
6105
6106
6107
6108
6109
6110

6111
6112
6113
6114
6115
6116
6117
....
6124
6125
6126
6127
6128
6129
6130
6131
6132
6133
6134
6135
6136
6137
6138
6139
6140
6141
6142
6143

6144
6145
6146

6147
6148
6149
6150
6151
6152
6153
6154
6155
6156
6157
6158
6159
6160

6161
6162
6163
6164
6165
6166
6167
6168
6169
6170
6171


6172
6173
6174
6175
6176

6177
6178
6179
6180

6181
6182
6183
6184
6185
6186
6187
6188
6189
6190
6191
6192
6193

6194
6195
6196

6197
6198
6199
6200
6201
6202
6203
6204
6205
6206
6207
6208
6209
6210
6211
6212
static int selectWindowRewriteSelectCb(Walker *pWalker, Select *pSelect){
  return WRC_Prune;
}

static int selectWindowRewriteExprCb(Walker *pWalker, Expr *pExpr){
  struct WindowRewrite *p = pWalker->u.pRewrite;
  Parse *pParse = pWalker->pParse;
  int rc = WRC_Continue;

  switch( pExpr->op ){

    case TK_FUNCTION:
      if( pExpr->pWin==0 ){
        break;



      }else if( pExpr->pWin==p->pWin ){
        rc = WRC_Prune;
        pExpr->pWin->pOwner = pExpr;
        break;



      }
      /* Fall through.  */

    case TK_COLUMN: {
      Expr *pDup = sqlite3ExprDup(pParse->db, pExpr, 0);
      p->pSub = sqlite3ExprListAppend(pParse, p->pSub, pDup);
      if( p->pSub ){
................................................................................
      break;
    }

    default: /* no-op */
      break;
  }

  return rc;
}

static int selectWindowRewriteEList(
  Parse *pParse, 
  Window *pWin,
  ExprList *pEList,               /* Rewrite expressions in this list */
  ExprList **ppSub                /* IN/OUT: Sub-select expression-list */
................................................................................
    SrcList *pSrc = p->pSrc;
    Expr *pWhere = p->pWhere;
    ExprList *pGroupBy = p->pGroupBy;
    Expr *pHaving = p->pHaving;
    ExprList *pSort = 0;

    ExprList *pSublist = 0;       /* Expression list for sub-query */
    Window *pWin = p->pWin;


    p->pSrc = 0;
    p->pWhere = 0;
    p->pGroupBy = 0;
    p->pHaving = 0;

    pWin->regAccum = ++pParse->nMem;
    pWin->regResult = ++pParse->nMem;

    /* Assign a cursor number for the ephemeral table used to buffer rows.
    ** The OpenEphemeral instruction is coded later, after it is known how
    ** many columns the table will have.  */
    pWin->iEphCsr = pParse->nTab++;

    rc = selectWindowRewriteEList(pParse, pWin, p->pEList, &pSublist);
    if( rc ) return rc;
    rc = selectWindowRewriteEList(pParse, pWin, p->pOrderBy, &pSublist);
    if( rc ) return rc;
    pWin->nBufferCol = (pSublist ? pSublist->nExpr : 0);

    /* Create the ORDER BY clause for the sub-select. This is the concatenation
    ** of the window PARTITION and ORDER BY clauses. Append the same 
    ** expressions to the sub-select expression list. They are required to
    ** figure out where boundaries for partitions and sets of peer rows.  */
    pSort = sqlite3ExprListDup(db, pWin->pPartition, 0);
    if( pWin->pOrderBy ){
      pSort = exprListAppendList(pParse, pSort, pWin->pOrderBy);
    }
    pSublist = exprListAppendList(pParse, pSublist, pSort);

    /* Also append the arguments passed to the window function to the
    ** sub-select expression list. */



    pWin->iArgCol = (pSublist ? pSublist->nExpr : 0);
    pSublist = exprListAppendList(pParse, pSublist, pWin->pOwner->x.pList);





    pSub = sqlite3SelectNew(
        pParse, pSublist, pSrc, pWhere, pGroupBy, pHaving, pSort, 0, 0
    );
    p->pSrc = sqlite3SrcListAppend(db, 0, 0, 0);
    if( p->pSrc ){
      int iTab;
................................................................................
      p->pSrc->a[0].pSelect = pSub;
      sqlite3SrcListAssignCursors(pParse, p->pSrc);
      if( selectExpandSubquery(pParse, &p->pSrc->a[0]) ){
        rc = SQLITE_NOMEM;
      }else{
        pSub->selFlags |= SF_Expanded;
      }
      pWin->pNextWin = 0;
    }

#if SELECTTRACE_ENABLED
    if( sqlite3SelectTrace & 0x108 ){
      SELECTTRACE(0x104,pParse,p, ("after window rewrite:\n"));
      sqlite3TreeViewSelect(0, p, 0);
    }
#endif

    sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pWin->iEphCsr, pWin->nBufferCol);
    sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);
  }

  return rc;
}

/*
** Generate code for the SELECT statement given in the p argument.  
................................................................................
    sqlite3VdbeChangeP5(v, BTREE_UNORDERED);
    sDistinct.eTnctType = WHERE_DISTINCT_UNORDERED;
  }else{
    sDistinct.eTnctType = WHERE_DISTINCT_NOOP;
  }

  if( !isAgg && pGroupBy==0 ){
    Window *pWin = p->pWin;
    int regPart = 0;

    /* No aggregate functions and no GROUP BY clause */
    u16 wctrlFlags = (sDistinct.isTnct ? WHERE_WANT_DISTINCT : 0);
    assert( WHERE_USE_LIMIT==SF_FixedLimit );
    wctrlFlags |= p->selFlags & SF_FixedLimit;

    if( pWin ){
      int nPart = (pWin->pPartition ? pWin->pPartition->nExpr : 0);
      nPart += (pWin->pOrderBy ? pWin->pOrderBy->nExpr : 0);
      if( nPart ){
        regPart = pParse->nMem+1;
        pParse->nMem += nPart;
        sqlite3VdbeAddOp3(v, OP_Null, 0, regPart, regPart+nPart-1);
      }
    }

................................................................................
    ** into an OP_Noop.
    */
    if( sSort.addrSortIndex>=0 && sSort.pOrderBy==0 ){
      sqlite3VdbeChangeToNoop(v, sSort.addrSortIndex);
    }

    assert( p->pEList==pEList );
    if( p->pWin ){

      int k;
      int iSubCsr = p->pSrc->a[0].iCursor;
      int nSub = p->pSrc->a[0].pTab->nCol;
      int reg = pParse->nMem+1;
      int regRecord = reg+nSub;
      int regRowid = regRecord+1;
      int regGosub = regRowid+1;
................................................................................
      ** registers. */
      for(k=0; k<nSub; k++){
        sqlite3VdbeAddOp3(v, OP_Column, iSubCsr, k, reg+k);
      }

      /* Check if this is the start of a new partition or peer group. */
      if( regPart ){
        ExprList *pPart = pWin->pPartition;
        int nPart = (pPart ? pPart->nExpr : 0);
        ExprList *pOrderBy = pWin->pOrderBy;
        int nPeer = (pOrderBy ? pOrderBy->nExpr : 0);
        int addrGoto = 0;
        int addrJump = 0;

        if( pPart ){
          int regNewPart = reg + pWin->nBufferCol;
          KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pPart, 0, 0);
          addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPart, regPart, nPart);
          sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
          addrJump = sqlite3VdbeAddOp3(v, OP_Jump, addr+2, 0, addr+2);

          sqlite3VdbeAddOp2(v, OP_AggFinal, pWin->regAccum, pWin->nArg);
          sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
          sqlite3VdbeAddOp2(v, OP_Copy, pWin->regAccum, pWin->regResult);

          if( pOrderBy ){
            addrGoto = sqlite3VdbeAddOp0(v, OP_Goto);
          }
        }

        if( pOrderBy ){
          int regNewPeer = reg + pWin->nBufferCol + nPart;
          int regPeer = regPart + nPart;

          KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pOrderBy, 0, 0);
          if( addrJump ) sqlite3VdbeJumpHere(v, addrJump);
          addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPeer, regPeer, nPeer);
          sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
          addrJump = sqlite3VdbeAddOp3(v, OP_Jump, addr+2, 0, addr+2);

          sqlite3VdbeAddOp3(v, 
              OP_AggFinal, pWin->regAccum, pWin->nArg, pWin->regResult
          );
          sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);

          if( addrGoto ) sqlite3VdbeJumpHere(v, addrGoto);
        }

        addrGosub = sqlite3VdbeAddOp1(v, OP_Gosub, regGosub);
        sqlite3VdbeAddOp1(v, OP_ResetSorter, pWin->iEphCsr);
        sqlite3VdbeAddOp3(v,OP_Copy,reg+pWin->nBufferCol,regPart,nPart+nPeer-1);



        sqlite3VdbeJumpHere(v, addrJump);
      }

      /* Invoke step function for window functions */

      sqlite3VdbeAddOp3(v, OP_AggStep0, 0, reg+pWin->iArgCol, pWin->regAccum);
      sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
      sqlite3VdbeChangeP5(v, (u8)pWin->nArg);


      /* Buffer the current row in the ephemeral table. */
      if( pWin->nBufferCol>0 ){
        sqlite3VdbeAddOp3(v, OP_MakeRecord, reg, pWin->nBufferCol, regRecord);
      }else{
        sqlite3VdbeAddOp2(v, OP_Blob, 0, regRecord);
        sqlite3VdbeAppendP4(v, (void*)"", 0);
      }
      sqlite3VdbeAddOp2(v, OP_NewRowid, pWin->iEphCsr, regRowid);
      sqlite3VdbeAddOp3(v, OP_Insert, pWin->iEphCsr, regRecord, regRowid);

      /* End the database scan loop. */
      sqlite3WhereEnd(pWInfo);


      sqlite3VdbeAddOp2(v, OP_AggFinal, pWin->regAccum, pWin->nArg);
      sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
      sqlite3VdbeAddOp2(v, OP_Copy, pWin->regAccum, pWin->regResult);

      sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, sqlite3VdbeCurrentAddr(v)+2);

      sqlite3VdbeAddOp0(v, OP_Goto);
      if( regPart ){
        sqlite3VdbeJumpHere(v, addrGosub);
      }
      addr = sqlite3VdbeAddOp1(v, OP_Rewind, pWin->iEphCsr);
      selectInnerLoop(pParse, p, -1, &sSort, &sDistinct, pDest, addr+1, 0);
      sqlite3VdbeAddOp2(v, OP_Next, pWin->iEphCsr, addr+1);
      sqlite3VdbeJumpHere(v, addr);
      sqlite3VdbeAddOp1(v, OP_Return, regGosub);
      sqlite3VdbeJumpHere(v, addr-1);       /* OP_Goto jumps here */

    }else{
      /* Use the standard inner loop. */
      selectInnerLoop(pParse, p, -1, &sSort, &sDistinct, pDest,







<






>
>
>
|
<
|
<
>
>
>







 







|







 







|
>






<
<
<



|

|

|

|





|
|
|



|
|
>
>
>
|
|
>
>
>
>







 







<









|
<







 







|







|
|
|







 







|
>







 







|

|





|




>
|
|
|
>






|







>
|
|
|
|
|




|
|
>
>





>
|
|
|
|
>

|
|




|
|




>
|
|
|
>






|

|







5411
5412
5413
5414
5415
5416
5417

5418
5419
5420
5421
5422
5423
5424
5425
5426
5427

5428

5429
5430
5431
5432
5433
5434
5435
5436
5437
5438
....
5450
5451
5452
5453
5454
5455
5456
5457
5458
5459
5460
5461
5462
5463
5464
....
5531
5532
5533
5534
5535
5536
5537
5538
5539
5540
5541
5542
5543
5544
5545



5546
5547
5548
5549
5550
5551
5552
5553
5554
5555
5556
5557
5558
5559
5560
5561
5562
5563
5564
5565
5566
5567
5568
5569
5570
5571
5572
5573
5574
5575
5576
5577
5578
5579
5580
5581
5582
5583
5584
....
5586
5587
5588
5589
5590
5591
5592

5593
5594
5595
5596
5597
5598
5599
5600
5601
5602

5603
5604
5605
5606
5607
5608
5609
....
6063
6064
6065
6066
6067
6068
6069
6070
6071
6072
6073
6074
6075
6076
6077
6078
6079
6080
6081
6082
6083
6084
6085
6086
6087
....
6109
6110
6111
6112
6113
6114
6115
6116
6117
6118
6119
6120
6121
6122
6123
6124
....
6131
6132
6133
6134
6135
6136
6137
6138
6139
6140
6141
6142
6143
6144
6145
6146
6147
6148
6149
6150
6151
6152
6153
6154
6155
6156
6157
6158
6159
6160
6161
6162
6163
6164
6165
6166
6167
6168
6169
6170
6171
6172
6173
6174
6175
6176
6177
6178
6179
6180
6181
6182
6183
6184
6185
6186
6187
6188
6189
6190
6191
6192
6193
6194
6195
6196
6197
6198
6199
6200
6201
6202
6203
6204
6205
6206
6207
6208
6209
6210
6211
6212
6213
6214
6215
6216
6217
6218
6219
6220
6221
6222
6223
6224
6225
6226
6227
6228
static int selectWindowRewriteSelectCb(Walker *pWalker, Select *pSelect){
  return WRC_Prune;
}

static int selectWindowRewriteExprCb(Walker *pWalker, Expr *pExpr){
  struct WindowRewrite *p = pWalker->u.pRewrite;
  Parse *pParse = pWalker->pParse;


  switch( pExpr->op ){

    case TK_FUNCTION:
      if( pExpr->pWin==0 ){
        break;
      }else{
        Window *pWin;
        for(pWin=p->pWin; pWin; pWin=pWin->pNextWin){
          if( pExpr->pWin==pWin ){

            pExpr->pWin->pOwner = pExpr;

            return WRC_Prune;
          }
        }
      }
      /* Fall through.  */

    case TK_COLUMN: {
      Expr *pDup = sqlite3ExprDup(pParse->db, pExpr, 0);
      p->pSub = sqlite3ExprListAppend(pParse, p->pSub, pDup);
      if( p->pSub ){
................................................................................
      break;
    }

    default: /* no-op */
      break;
  }

  return WRC_Continue;
}

static int selectWindowRewriteEList(
  Parse *pParse, 
  Window *pWin,
  ExprList *pEList,               /* Rewrite expressions in this list */
  ExprList **ppSub                /* IN/OUT: Sub-select expression-list */
................................................................................
    SrcList *pSrc = p->pSrc;
    Expr *pWhere = p->pWhere;
    ExprList *pGroupBy = p->pGroupBy;
    Expr *pHaving = p->pHaving;
    ExprList *pSort = 0;

    ExprList *pSublist = 0;       /* Expression list for sub-query */
    Window *pMWin = p->pWin;      /* Master window object */
    Window *pWin;                 /* Window object iterator */

    p->pSrc = 0;
    p->pWhere = 0;
    p->pGroupBy = 0;
    p->pHaving = 0;




    /* Assign a cursor number for the ephemeral table used to buffer rows.
    ** The OpenEphemeral instruction is coded later, after it is known how
    ** many columns the table will have.  */
    pMWin->iEphCsr = pParse->nTab++;

    rc = selectWindowRewriteEList(pParse, pMWin, p->pEList, &pSublist);
    if( rc ) return rc;
    rc = selectWindowRewriteEList(pParse, pMWin, p->pOrderBy, &pSublist);
    if( rc ) return rc;
    pMWin->nBufferCol = (pSublist ? pSublist->nExpr : 0);

    /* Create the ORDER BY clause for the sub-select. This is the concatenation
    ** of the window PARTITION and ORDER BY clauses. Append the same 
    ** expressions to the sub-select expression list. They are required to
    ** figure out where boundaries for partitions and sets of peer rows.  */
    pSort = sqlite3ExprListDup(db, pMWin->pPartition, 0);
    if( pMWin->pOrderBy ){
      pSort = exprListAppendList(pParse, pSort, pMWin->pOrderBy);
    }
    pSublist = exprListAppendList(pParse, pSublist, pSort);

    /* Append the arguments passed to each window function to the
    ** sub-select expression list. Also allocate two registers for each
    ** window function - one for the accumulator, another for interim
    ** results.  */
    for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
      pWin->iArgCol = (pSublist ? pSublist->nExpr : 0);
      pSublist = exprListAppendList(pParse, pSublist, pWin->pOwner->x.pList);
      pWin->regAccum = ++pParse->nMem;
      pWin->regResult = ++pParse->nMem;
      sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);
    }

    pSub = sqlite3SelectNew(
        pParse, pSublist, pSrc, pWhere, pGroupBy, pHaving, pSort, 0, 0
    );
    p->pSrc = sqlite3SrcListAppend(db, 0, 0, 0);
    if( p->pSrc ){
      int iTab;
................................................................................
      p->pSrc->a[0].pSelect = pSub;
      sqlite3SrcListAssignCursors(pParse, p->pSrc);
      if( selectExpandSubquery(pParse, &p->pSrc->a[0]) ){
        rc = SQLITE_NOMEM;
      }else{
        pSub->selFlags |= SF_Expanded;
      }

    }

#if SELECTTRACE_ENABLED
    if( sqlite3SelectTrace & 0x108 ){
      SELECTTRACE(0x104,pParse,p, ("after window rewrite:\n"));
      sqlite3TreeViewSelect(0, p, 0);
    }
#endif

    sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pMWin->iEphCsr, pMWin->nBufferCol);

  }

  return rc;
}

/*
** Generate code for the SELECT statement given in the p argument.  
................................................................................
    sqlite3VdbeChangeP5(v, BTREE_UNORDERED);
    sDistinct.eTnctType = WHERE_DISTINCT_UNORDERED;
  }else{
    sDistinct.eTnctType = WHERE_DISTINCT_NOOP;
  }

  if( !isAgg && pGroupBy==0 ){
    Window *pMWin = p->pWin;      /* Master window object (or NULL) */
    int regPart = 0;

    /* No aggregate functions and no GROUP BY clause */
    u16 wctrlFlags = (sDistinct.isTnct ? WHERE_WANT_DISTINCT : 0);
    assert( WHERE_USE_LIMIT==SF_FixedLimit );
    wctrlFlags |= p->selFlags & SF_FixedLimit;

    if( pMWin ){
      int nPart = (pMWin->pPartition ? pMWin->pPartition->nExpr : 0);
      nPart += (pMWin->pOrderBy ? pMWin->pOrderBy->nExpr : 0);
      if( nPart ){
        regPart = pParse->nMem+1;
        pParse->nMem += nPart;
        sqlite3VdbeAddOp3(v, OP_Null, 0, regPart, regPart+nPart-1);
      }
    }

................................................................................
    ** into an OP_Noop.
    */
    if( sSort.addrSortIndex>=0 && sSort.pOrderBy==0 ){
      sqlite3VdbeChangeToNoop(v, sSort.addrSortIndex);
    }

    assert( p->pEList==pEList );
    if( pMWin ){
      Window *pWin;
      int k;
      int iSubCsr = p->pSrc->a[0].iCursor;
      int nSub = p->pSrc->a[0].pTab->nCol;
      int reg = pParse->nMem+1;
      int regRecord = reg+nSub;
      int regRowid = regRecord+1;
      int regGosub = regRowid+1;
................................................................................
      ** registers. */
      for(k=0; k<nSub; k++){
        sqlite3VdbeAddOp3(v, OP_Column, iSubCsr, k, reg+k);
      }

      /* Check if this is the start of a new partition or peer group. */
      if( regPart ){
        ExprList *pPart = pMWin->pPartition;
        int nPart = (pPart ? pPart->nExpr : 0);
        ExprList *pOrderBy = pMWin->pOrderBy;
        int nPeer = (pOrderBy ? pOrderBy->nExpr : 0);
        int addrGoto = 0;
        int addrJump = 0;

        if( pPart ){
          int regNewPart = reg + pMWin->nBufferCol;
          KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pPart, 0, 0);
          addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPart, regPart, nPart);
          sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
          addrJump = sqlite3VdbeAddOp3(v, OP_Jump, addr+2, 0, addr+2);
          for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
            sqlite3VdbeAddOp2(v, OP_AggFinal, pWin->regAccum, pWin->nArg);
            sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
            sqlite3VdbeAddOp2(v, OP_Copy, pWin->regAccum, pWin->regResult);
          }
          if( pOrderBy ){
            addrGoto = sqlite3VdbeAddOp0(v, OP_Goto);
          }
        }

        if( pOrderBy ){
          int regNewPeer = reg + pMWin->nBufferCol + nPart;
          int regPeer = regPart + nPart;

          KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pOrderBy, 0, 0);
          if( addrJump ) sqlite3VdbeJumpHere(v, addrJump);
          addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPeer, regPeer, nPeer);
          sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
          addrJump = sqlite3VdbeAddOp3(v, OP_Jump, addr+2, 0, addr+2);
          for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
            sqlite3VdbeAddOp3(v, 
                OP_AggFinal, pWin->regAccum, pWin->nArg, pWin->regResult
            );
            sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
          }
          if( addrGoto ) sqlite3VdbeJumpHere(v, addrGoto);
        }

        addrGosub = sqlite3VdbeAddOp1(v, OP_Gosub, regGosub);
        sqlite3VdbeAddOp1(v, OP_ResetSorter, pMWin->iEphCsr);
        sqlite3VdbeAddOp3(
            v, OP_Copy, reg+pMWin->nBufferCol, regPart, nPart+nPeer-1
        );

        sqlite3VdbeJumpHere(v, addrJump);
      }

      /* Invoke step function for window functions */
      for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
        sqlite3VdbeAddOp3(v, OP_AggStep0, 0, reg+pWin->iArgCol, pWin->regAccum);
        sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
        sqlite3VdbeChangeP5(v, (u8)pWin->nArg);
      }

      /* Buffer the current row in the ephemeral table. */
      if( pMWin->nBufferCol>0 ){
        sqlite3VdbeAddOp3(v, OP_MakeRecord, reg, pMWin->nBufferCol, regRecord);
      }else{
        sqlite3VdbeAddOp2(v, OP_Blob, 0, regRecord);
        sqlite3VdbeAppendP4(v, (void*)"", 0);
      }
      sqlite3VdbeAddOp2(v, OP_NewRowid, pMWin->iEphCsr, regRowid);
      sqlite3VdbeAddOp3(v, OP_Insert, pMWin->iEphCsr, regRecord, regRowid);

      /* End the database scan loop. */
      sqlite3WhereEnd(pWInfo);

      for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
        sqlite3VdbeAddOp2(v, OP_AggFinal, pWin->regAccum, pWin->nArg);
        sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
        sqlite3VdbeAddOp2(v, OP_Copy, pWin->regAccum, pWin->regResult);
      }
      sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, sqlite3VdbeCurrentAddr(v)+2);

      sqlite3VdbeAddOp0(v, OP_Goto);
      if( regPart ){
        sqlite3VdbeJumpHere(v, addrGosub);
      }
      addr = sqlite3VdbeAddOp1(v, OP_Rewind, pMWin->iEphCsr);
      selectInnerLoop(pParse, p, -1, &sSort, &sDistinct, pDest, addr+1, 0);
      sqlite3VdbeAddOp2(v, OP_Next, pMWin->iEphCsr, addr+1);
      sqlite3VdbeJumpHere(v, addr);
      sqlite3VdbeAddOp1(v, OP_Return, regGosub);
      sqlite3VdbeJumpHere(v, addr-1);       /* OP_Goto jumps here */

    }else{
      /* Use the standard inner loop. */
      selectInnerLoop(pParse, p, -1, &sSort, &sDistinct, pDest,

Changes to src/sqliteInt.h.

1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
....
3489
3490
3491
3492
3493
3494
3495

3496
3497
3498
3499
3500
3501
3502
   SQLITE_INT_TO_PTR(iArg), 0, xFunc, 0, 0, 0, #zName, {0} }
#define STR_FUNCTION(zName, nArg, pArg, bNC, xFunc) \
  {nArg, SQLITE_FUNC_SLOCHNG|SQLITE_UTF8|(bNC*SQLITE_FUNC_NEEDCOLL), \
   pArg, 0, xFunc, 0, 0, 0, #zName, }
#define LIKEFUNC(zName, nArg, arg, flags) \
  {nArg, SQLITE_FUNC_CONSTANT|SQLITE_UTF8|flags, \
   (void *)arg, 0, likeFunc, 0, 0, 0, #zName, {0} }
#define AGGREGATE(zName, nArg, arg, nc, xStep, xFinal) \
  {nArg, SQLITE_UTF8|(nc*SQLITE_FUNC_NEEDCOLL), \
   SQLITE_INT_TO_PTR(arg), 0, xStep,xFinal,0,0,#zName, {0}}
#define AGGREGATE2(zName, nArg, arg, nc, xStep, xFinal, extraFlags) \
  {nArg, SQLITE_UTF8|(nc*SQLITE_FUNC_NEEDCOLL)|extraFlags, \
   SQLITE_INT_TO_PTR(arg), 0, xStep,xFinal,0,0,#zName, {0}}

#define WFUNCTION(zName, nArg, arg, xStep, xFinal, xValue, xInverse) \
  {nArg, SQLITE_UTF8, \
   SQLITE_INT_TO_PTR(arg), 0, xStep,xFinal,xValue,xInverse,#zName, {0}}

/*
** All current savepoints are stored in a linked list starting at
** sqlite3.pSavepoint. The first element in the list is the most recently
** opened savepoint. Savepoints are added to the list by the vdbe
** OP_Savepoint instruction.
*/
................................................................................
  int nBufferCol;         /* Number of columns in buffer table */
  int iArgCol;            /* Offset of first argument for this function */
};

void sqlite3WindowDelete(sqlite3*, Window*);
Window *sqlite3WindowAlloc(Parse*, int, int, Expr*, int , Expr*);
void sqlite3WindowAttach(Parse*, Expr*, Window*);


/*
** Assuming zIn points to the first byte of a UTF-8 character,
** advance zIn to point to the first byte of the next UTF-8 character.
*/
#define SQLITE_SKIP_UTF8(zIn) {                        \
  if( (*(zIn++))>=0xc0 ){                              \







|

|


|

|
|
|







 







>







1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
....
3489
3490
3491
3492
3493
3494
3495
3496
3497
3498
3499
3500
3501
3502
3503
   SQLITE_INT_TO_PTR(iArg), 0, xFunc, 0, 0, 0, #zName, {0} }
#define STR_FUNCTION(zName, nArg, pArg, bNC, xFunc) \
  {nArg, SQLITE_FUNC_SLOCHNG|SQLITE_UTF8|(bNC*SQLITE_FUNC_NEEDCOLL), \
   pArg, 0, xFunc, 0, 0, 0, #zName, }
#define LIKEFUNC(zName, nArg, arg, flags) \
  {nArg, SQLITE_FUNC_CONSTANT|SQLITE_UTF8|flags, \
   (void *)arg, 0, likeFunc, 0, 0, 0, #zName, {0} }
#define AGGREGATE(zName, nArg, arg, nc, xStep, xFinal, xValue) \
  {nArg, SQLITE_UTF8|(nc*SQLITE_FUNC_NEEDCOLL), \
   SQLITE_INT_TO_PTR(arg), 0, xStep,xFinal,xValue,0,#zName, {0}}
#define AGGREGATE2(zName, nArg, arg, nc, xStep, xFinal, extraFlags) \
  {nArg, SQLITE_UTF8|(nc*SQLITE_FUNC_NEEDCOLL)|extraFlags, \
   SQLITE_INT_TO_PTR(arg), 0, xStep,xFinal,xFinal,0,#zName, {0}}

#define WAGGREGATE(zName, nArg, arg, nc, xStep, xFinal) \
  {nArg, SQLITE_UTF8|(nc*SQLITE_FUNC_NEEDCOLL), \
   SQLITE_INT_TO_PTR(arg), 0, xStep,xFinal,xFinal,0,#zName, {0}}

/*
** All current savepoints are stored in a linked list starting at
** sqlite3.pSavepoint. The first element in the list is the most recently
** opened savepoint. Savepoints are added to the list by the vdbe
** OP_Savepoint instruction.
*/
................................................................................
  int nBufferCol;         /* Number of columns in buffer table */
  int iArgCol;            /* Offset of first argument for this function */
};

void sqlite3WindowDelete(sqlite3*, Window*);
Window *sqlite3WindowAlloc(Parse*, int, int, Expr*, int , Expr*);
void sqlite3WindowAttach(Parse*, Expr*, Window*);
int sqlite3WindowCompare(Parse*, Window*, Window*);

/*
** Assuming zIn points to the first byte of a UTF-8 character,
** advance zIn to point to the first byte of the next UTF-8 character.
*/
#define SQLITE_SKIP_UTF8(zIn) {                        \
  if( (*(zIn++))>=0xc0 ){                              \

Changes to src/window.c.

47
48
49
50
51
52
53
















void sqlite3WindowAttach(Parse *pParse, Expr *p, Window *pWin){
  if( p ){
    p->pWin = pWin;
  }else{
    sqlite3WindowDelete(pParse->db, pWin);
  }
}























>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
void sqlite3WindowAttach(Parse *pParse, Expr *p, Window *pWin){
  if( p ){
    p->pWin = pWin;
  }else{
    sqlite3WindowDelete(pParse->db, pWin);
  }
}

/*
** Return 0 if the two window objects are identical, or non-zero otherwise.
*/
int sqlite3WindowCompare(Parse *pParse, Window *p1, Window *p2){
  if( p1->eType!=p2->eType ) return 1;
  if( p1->eStart!=p2->eStart ) return 1;
  if( p1->eEnd!=p2->eEnd ) return 1;
  if( sqlite3ExprCompare(pParse, p1->pStart, p2->pStart, -1) ) return 1;
  if( sqlite3ExprCompare(pParse, p1->pEnd, p2->pEnd, -1) ) return 1;
  if( sqlite3ExprListCompare(p1->pPartition, p2->pPartition, -1) ) return 1;
  if( sqlite3ExprListCompare(p1->pOrderBy, p2->pOrderBy, -1) ) return 1;
  return 0;
}


Changes to test/window1.test.

131
132
133
134
135
136
137
138































139
  1   9  1 
  2  12  2 
  3   8  3 
  4  10  5 
  5   5  7 
  6   6  9
}
































finish_test








>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
  1   9  1 
  2  12  2 
  3   8  3 
  4  10  5 
  5   5  7 
  6   6  9
}

do_execsql_test 4.9 {
  SELECT a, 
    sum(a) OVER (ORDER BY a), 
    avg(a) OVER (ORDER BY a) 
  FROM t2 ORDER BY a
} {
  0  0       0.0
  1  1       0.5
  2  3       1.0
  3  6       1.5
  4  10      2.0
  5  15      2.5
  6  21      3.0
}

do_execsql_test 4.10 {
  SELECT a, 
    count() OVER (ORDER BY a DESC),
    group_concat(a, '.') OVER (ORDER BY a DESC) 
  FROM t2 ORDER BY a DESC
} {
  6 1 6
  5 2 6.5
  4 3 6.5.4
  3 4 6.5.4.3
  2 5 6.5.4.3.2
  1 6 6.5.4.3.2.1
  0 7 6.5.4.3.2.1.0
}


finish_test