SQLite

Check-in [bc4b81d60d]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Begin adding support for more esoteric window frames.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | exp-window-functions
Files: files | file ages | folders
SHA3-256: bc4b81d60d40583de0f929730159011c1a7696802532ebd02220de3ace94a60d
User & Date: dan 2018-05-21 19:45:11.880
Context
2018-05-22
20:35
Add comments to window.c describing how other window frames will be implemented. (check-in: 16168146b2 user: dan tags: exp-window-functions)
2018-05-21
19:45
Begin adding support for more esoteric window frames. (check-in: bc4b81d60d user: dan tags: exp-window-functions)
2018-05-19
14:15
Fix minor problems on this branch. (check-in: 19c2e4b2f1 user: dan tags: exp-window-functions)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/select.c.
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
                     isOuter, &p->pWhere);
      }
    }
  }
  return 0;
}

/* Forward reference */
static KeyInfo *keyInfoFromExprList(
  Parse *pParse,       /* Parsing context */
  ExprList *pList,     /* Form the KeyInfo object from this ExprList */
  int iStart,          /* Begin with this column of pList */
  int nExtra           /* Add this many extra columns to the end */
);

/*
** An instance of this object holds information (beyond pParse and pSelect)
** needed to load the next result row that is to be added to the sorter.
*/
typedef struct RowLoadInfo RowLoadInfo;
struct RowLoadInfo {
  int regResult;               /* Store results in array of registers here */







<
<
<
<
<
<
<
<







526
527
528
529
530
531
532








533
534
535
536
537
538
539
                     isOuter, &p->pWhere);
      }
    }
  }
  return 0;
}









/*
** An instance of this object holds information (beyond pParse and pSelect)
** needed to load the next result row that is to be added to the sorter.
*/
typedef struct RowLoadInfo RowLoadInfo;
struct RowLoadInfo {
  int regResult;               /* Store results in array of registers here */
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
    pOp = sqlite3VdbeGetOp(v, pSort->addrSortIndex);
    if( pParse->db->mallocFailed ) return;
    pOp->p2 = nKey + nData;
    pKI = pOp->p4.pKeyInfo;
    memset(pKI->aSortOrder, 0, pKI->nKeyField); /* Makes OP_Jump testable */
    sqlite3VdbeChangeP4(v, -1, (char*)pKI, P4_KEYINFO);
    testcase( pKI->nAllField > pKI->nKeyField+2 );
    pOp->p4.pKeyInfo = keyInfoFromExprList(pParse, pSort->pOrderBy, nOBSat,
                                           pKI->nAllField-pKI->nKeyField-1);
    addrJmp = sqlite3VdbeCurrentAddr(v);
    sqlite3VdbeAddOp3(v, OP_Jump, addrJmp+1, 0, addrJmp+1); VdbeCoverage(v);
    pSort->labelBkOut = sqlite3VdbeMakeLabel(v);
    pSort->regReturn = ++pParse->nMem;
    sqlite3VdbeAddOp2(v, OP_Gosub, pSort->regReturn, pSort->labelBkOut);
    sqlite3VdbeAddOp1(v, OP_ResetSorter, pSort->iECursor);







|







667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
    pOp = sqlite3VdbeGetOp(v, pSort->addrSortIndex);
    if( pParse->db->mallocFailed ) return;
    pOp->p2 = nKey + nData;
    pKI = pOp->p4.pKeyInfo;
    memset(pKI->aSortOrder, 0, pKI->nKeyField); /* Makes OP_Jump testable */
    sqlite3VdbeChangeP4(v, -1, (char*)pKI, P4_KEYINFO);
    testcase( pKI->nAllField > pKI->nKeyField+2 );
    pOp->p4.pKeyInfo = sqlite3KeyInfoFromExprList(pParse,pSort->pOrderBy,nOBSat,
                                           pKI->nAllField-pKI->nKeyField-1);
    addrJmp = sqlite3VdbeCurrentAddr(v);
    sqlite3VdbeAddOp3(v, OP_Jump, addrJmp+1, 0, addrJmp+1); VdbeCoverage(v);
    pSort->labelBkOut = sqlite3VdbeMakeLabel(v);
    pSort->regReturn = ++pParse->nMem;
    sqlite3VdbeAddOp2(v, OP_Gosub, pSort->regReturn, pSort->labelBkOut);
    sqlite3VdbeAddOp1(v, OP_ResetSorter, pSort->iECursor);
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
** then the KeyInfo structure is appropriate for initializing a virtual
** index to implement a DISTINCT test.
**
** Space to hold the KeyInfo structure is obtained from malloc.  The calling
** function is responsible for seeing that this structure is eventually
** freed.
*/
static KeyInfo *keyInfoFromExprList(
  Parse *pParse,       /* Parsing context */
  ExprList *pList,     /* Form the KeyInfo object from this ExprList */
  int iStart,          /* Begin with this column of pList */
  int nExtra           /* Add this many extra columns to the end */
){
  int nExpr;
  KeyInfo *pInfo;







|







1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
** then the KeyInfo structure is appropriate for initializing a virtual
** index to implement a DISTINCT test.
**
** Space to hold the KeyInfo structure is obtained from malloc.  The calling
** function is responsible for seeing that this structure is eventually
** freed.
*/
KeyInfo *sqlite3KeyInfoFromExprList(
  Parse *pParse,       /* Parsing context */
  ExprList *pList,     /* Form the KeyInfo object from this ExprList */
  int iStart,          /* Begin with this column of pList */
  int nExtra           /* Add this many extra columns to the end */
){
  int nExpr;
  KeyInfo *pInfo;
5084
5085
5086
5087
5088
5089
5090
5091
5092
5093
5094
5095
5096
5097
5098
      Expr *pE = pFunc->pExpr;
      assert( !ExprHasProperty(pE, EP_xIsSelect) );
      if( pE->x.pList==0 || pE->x.pList->nExpr!=1 ){
        sqlite3ErrorMsg(pParse, "DISTINCT aggregates must have exactly one "
           "argument");
        pFunc->iDistinct = -1;
      }else{
        KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pE->x.pList, 0, 0);
        sqlite3VdbeAddOp4(v, OP_OpenEphemeral, pFunc->iDistinct, 0, 0,
                          (char*)pKeyInfo, P4_KEYINFO);
      }
    }
  }
}








|







5076
5077
5078
5079
5080
5081
5082
5083
5084
5085
5086
5087
5088
5089
5090
      Expr *pE = pFunc->pExpr;
      assert( !ExprHasProperty(pE, EP_xIsSelect) );
      if( pE->x.pList==0 || pE->x.pList->nExpr!=1 ){
        sqlite3ErrorMsg(pParse, "DISTINCT aggregates must have exactly one "
           "argument");
        pFunc->iDistinct = -1;
      }else{
        KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pE->x.pList,0,0);
        sqlite3VdbeAddOp4(v, OP_OpenEphemeral, pFunc->iDistinct, 0, 0,
                          (char*)pKeyInfo, P4_KEYINFO);
      }
    }
  }
}

6004
6005
6006
6007
6008
6009
6010

6011
6012
6013
6014
6015
6016
6017
6018
  ** If that is the case, then the OP_OpenEphemeral instruction will be
  ** changed to an OP_Noop once we figure out that the sorting index is
  ** not needed.  The sSort.addrSortIndex variable is used to facilitate
  ** that change.
  */
  if( sSort.pOrderBy ){
    KeyInfo *pKeyInfo;

    pKeyInfo = keyInfoFromExprList(pParse, sSort.pOrderBy, 0, pEList->nExpr);
    sSort.iECursor = pParse->nTab++;
    sSort.addrSortIndex =
      sqlite3VdbeAddOp4(v, OP_OpenEphemeral,
          sSort.iECursor, sSort.pOrderBy->nExpr+1+pEList->nExpr, 0,
          (char*)pKeyInfo, P4_KEYINFO
      );
  }else{







>
|







5996
5997
5998
5999
6000
6001
6002
6003
6004
6005
6006
6007
6008
6009
6010
6011
  ** If that is the case, then the OP_OpenEphemeral instruction will be
  ** changed to an OP_Noop once we figure out that the sorting index is
  ** not needed.  The sSort.addrSortIndex variable is used to facilitate
  ** that change.
  */
  if( sSort.pOrderBy ){
    KeyInfo *pKeyInfo;
    pKeyInfo = sqlite3KeyInfoFromExprList(
        pParse, sSort.pOrderBy, 0, pEList->nExpr);
    sSort.iECursor = pParse->nTab++;
    sSort.addrSortIndex =
      sqlite3VdbeAddOp4(v, OP_OpenEphemeral,
          sSort.iECursor, sSort.pOrderBy->nExpr+1+pEList->nExpr, 0,
          (char*)pKeyInfo, P4_KEYINFO
      );
  }else{
6038
6039
6040
6041
6042
6043
6044
6045
6046
6047
6048
6049
6050
6051
6052
6053
6054
6055
6056
6057
6058
6059
6060
6061
6062
6063
6064
6065
6066
6067
6068
6069
6070
6071
6072
6073
6074
6075
6076
6077
  }

  /* Open an ephemeral index to use for the distinct set.
  */
  if( p->selFlags & SF_Distinct ){
    sDistinct.tabTnct = pParse->nTab++;
    sDistinct.addrTnct = sqlite3VdbeAddOp4(v, OP_OpenEphemeral,
                             sDistinct.tabTnct, 0, 0,
                             (char*)keyInfoFromExprList(pParse, p->pEList,0,0),
                             P4_KEYINFO);
    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);
      }
    }

    /* Begin the database scan. */
    SELECTTRACE(1,pParse,p,("WhereBegin\n"));
    pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, sSort.pOrderBy,
                               p->pEList, wctrlFlags, p->nSelectRow);
    if( pWInfo==0 ) goto select_end;







|
|
|







|
<






|
<
<
<
<
|
<
<







6031
6032
6033
6034
6035
6036
6037
6038
6039
6040
6041
6042
6043
6044
6045
6046
6047
6048

6049
6050
6051
6052
6053
6054
6055




6056


6057
6058
6059
6060
6061
6062
6063
  }

  /* Open an ephemeral index to use for the distinct set.
  */
  if( p->selFlags & SF_Distinct ){
    sDistinct.tabTnct = pParse->nTab++;
    sDistinct.addrTnct = sqlite3VdbeAddOp4(v, OP_OpenEphemeral,
                       sDistinct.tabTnct, 0, 0,
                       (char*)sqlite3KeyInfoFromExprList(pParse, p->pEList,0,0),
                       P4_KEYINFO);
    sqlite3VdbeChangeP5(v, BTREE_UNORDERED);
    sDistinct.eTnctType = WHERE_DISTINCT_UNORDERED;
  }else{
    sDistinct.eTnctType = WHERE_DISTINCT_NOOP;
  }

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


    /* 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 ){




      sqlite3WindowCodeInit(pParse, pWin);


    }

    /* Begin the database scan. */
    SELECTTRACE(1,pParse,p,("WhereBegin\n"));
    pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, sSort.pOrderBy,
                               p->pEList, wctrlFlags, p->nSelectRow);
    if( pWInfo==0 ) goto select_end;
6094
6095
6096
6097
6098
6099
6100
6101
6102
6103
6104
6105
6106
6107
6108
6109
6110
6111
6112
6113
6114
6115
6116
6117
6118
6119
6120
6121
6122
6123
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
6213
    ** 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;
      int addr;
      int addrGosub;

      pParse->nMem += nSub + 3;

      /* Martial the row returned by the sub-select into an array of 
      ** 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,







|
<
|
<
<
<
<
<
|

<

<
|
<
<
<
<
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
|
<
<
<
<
<
<
<
<
<
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
|

|







6080
6081
6082
6083
6084
6085
6086
6087

6088





6089
6090

6091

6092




6093




































6094









6095





































6096
6097
6098
6099
6100
6101
6102
6103
6104
6105
    ** into an OP_Noop.
    */
    if( sSort.addrSortIndex>=0 && sSort.pOrderBy==0 ){
      sqlite3VdbeChangeToNoop(v, sSort.addrSortIndex);
    }

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

      int addrGosub = sqlite3VdbeMakeLabel(v);





      int regGosub = ++pParse->nMem;
      int addr;



      sqlite3WindowCodeStep(pParse, p, pWInfo, regGosub, addrGosub);









































      sqlite3VdbeAddOp0(v, OP_Goto);









      sqlite3VdbeResolveLabel(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,
6342
6343
6344
6345
6346
6347
6348
6349
6350
6351
6352
6353
6354
6355
6356

      /* If there is a GROUP BY clause we might need a sorting index to
      ** implement it.  Allocate that sorting index now.  If it turns out
      ** that we do not need it after all, the OP_SorterOpen instruction
      ** will be converted into a Noop.  
      */
      sAggInfo.sortingIdx = pParse->nTab++;
      pKeyInfo = keyInfoFromExprList(pParse, pGroupBy, 0, sAggInfo.nColumn);
      addrSortingIdx = sqlite3VdbeAddOp4(v, OP_SorterOpen, 
          sAggInfo.sortingIdx, sAggInfo.nSortingColumn, 
          0, (char*)pKeyInfo, P4_KEYINFO);

      /* Initialize memory locations used by GROUP BY aggregate processing
      */
      iUseFlag = ++pParse->nMem;







|







6234
6235
6236
6237
6238
6239
6240
6241
6242
6243
6244
6245
6246
6247
6248

      /* If there is a GROUP BY clause we might need a sorting index to
      ** implement it.  Allocate that sorting index now.  If it turns out
      ** that we do not need it after all, the OP_SorterOpen instruction
      ** will be converted into a Noop.  
      */
      sAggInfo.sortingIdx = pParse->nTab++;
      pKeyInfo = sqlite3KeyInfoFromExprList(pParse,pGroupBy,0,sAggInfo.nColumn);
      addrSortingIdx = sqlite3VdbeAddOp4(v, OP_SorterOpen, 
          sAggInfo.sortingIdx, sAggInfo.nSortingColumn, 
          0, (char*)pKeyInfo, P4_KEYINFO);

      /* Initialize memory locations used by GROUP BY aggregate processing
      */
      iUseFlag = ++pParse->nMem;
Changes to src/sqliteInt.h.
3481
3482
3483
3484
3485
3486
3487

3488
3489
3490
3491
3492
3493
3494
3495
3496


3497
3498
3499
3500
3501
3502
3503
  Window *pNextWin;       /* Next window function belonging to this SELECT */
  int iEphCsr;            /* Temp table used by this window */
  int regAccum;
  int regResult;
  FuncDef *pFunc;
  int nArg;


  Expr *pOwner;           /* Expression object this window is attached to */
  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 ){                              \







>









>
>







3481
3482
3483
3484
3485
3486
3487
3488
3489
3490
3491
3492
3493
3494
3495
3496
3497
3498
3499
3500
3501
3502
3503
3504
3505
3506
  Window *pNextWin;       /* Next window function belonging to this SELECT */
  int iEphCsr;            /* Temp table used by this window */
  int regAccum;
  int regResult;
  FuncDef *pFunc;
  int nArg;

  int regPart;
  Expr *pOwner;           /* Expression object this window is attached to */
  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*);
void sqlite3WindowCodeInit(Parse*, Window*);
void sqlite3WindowCodeStep(Parse*, Select*, WhereInfo*, int, int);

/*
** 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 ){                              \
4198
4199
4200
4201
4202
4203
4204


4205
4206
4207
4208
4209
4210
4211
void sqlite3SchemaClear(void *);
Schema *sqlite3SchemaGet(sqlite3 *, Btree *);
int sqlite3SchemaToIndex(sqlite3 *db, Schema *);
KeyInfo *sqlite3KeyInfoAlloc(sqlite3*,int,int);
void sqlite3KeyInfoUnref(KeyInfo*);
KeyInfo *sqlite3KeyInfoRef(KeyInfo*);
KeyInfo *sqlite3KeyInfoOfIndex(Parse*, Index*);


#ifdef SQLITE_DEBUG
int sqlite3KeyInfoIsWriteable(KeyInfo*);
#endif
int sqlite3CreateFunc(sqlite3 *, const char *, int, int, void *,
  void (*)(sqlite3_context*,int,sqlite3_value **),
  void (*)(sqlite3_context*,int,sqlite3_value **), void (*)(sqlite3_context*),
  FuncDestructor *pDestructor







>
>







4201
4202
4203
4204
4205
4206
4207
4208
4209
4210
4211
4212
4213
4214
4215
4216
void sqlite3SchemaClear(void *);
Schema *sqlite3SchemaGet(sqlite3 *, Btree *);
int sqlite3SchemaToIndex(sqlite3 *db, Schema *);
KeyInfo *sqlite3KeyInfoAlloc(sqlite3*,int,int);
void sqlite3KeyInfoUnref(KeyInfo*);
KeyInfo *sqlite3KeyInfoRef(KeyInfo*);
KeyInfo *sqlite3KeyInfoOfIndex(Parse*, Index*);
KeyInfo *sqlite3KeyInfoFromExprList(Parse*, ExprList*, int, int);

#ifdef SQLITE_DEBUG
int sqlite3KeyInfoIsWriteable(KeyInfo*);
#endif
int sqlite3CreateFunc(sqlite3 *, const char *, int, int, void *,
  void (*)(sqlite3_context*,int,sqlite3_value **),
  void (*)(sqlite3_context*,int,sqlite3_value **), void (*)(sqlite3_context*),
  FuncDestructor *pDestructor
Changes to src/window.c.
61
62
63
64
65
66
67




















































































































































































































68
69
  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;
}





























































































































































































































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


61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
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
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
  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;
}

void sqlite3WindowCodeInit(Parse *pParse, Window *pWin){
  Vdbe *v = sqlite3GetVdbe(pParse);
  int nPart = (pWin->pPartition ? pWin->pPartition->nExpr : 0);
  nPart += (pWin->pOrderBy ? pWin->pOrderBy->nExpr : 0);
  if( nPart ){
    pWin->regPart = pParse->nMem+1;
    pParse->nMem += nPart;
    sqlite3VdbeAddOp3(v, OP_Null, 0, pWin->regPart, pWin->regPart+nPart-1);
  }
}

/*
** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
**
**   ...
**     if( new partition ){
**       AggFinal (xFinalize)
**       Gosub addrGosub
**       ResetSorter eph-table
**     }
**     else if( new peer ){
**       AggFinal (xValue)
**       Gosub addrGosub
**       ResetSorter eph-table
**     }
**     AggStep
**     Insert (record into eph-table)
**   sqlite3WhereEnd()
**   AggFinal (xFinalize)
**   Gosub addrGosub
**
** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
**
**   As above, except take no action for a "new peer". Invoke
**   the sub-routine once only for each partition.
**
** RANGE BETWEEN CURRENT ROW AND CURRENT ROW
**
**   As above, except that the "new peer" condition is handled in the
**   same way as "new partition" (so there is no "else if" block).
**
** RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
**
**   One way is to just reverse the sort order and do as for BETWEEN 
**   UNBOUNDED PRECEDING AND CURRENT ROW. But that is not quite the same for
**   things like group_concat(). And perhaps other user defined aggregates 
**   as well.
**
**   ...
**     if( new partition ){
**       Gosub flush_partition;
**       ResetSorter eph-table
**     }
**     AggStep
**     Insert (record into eph-table)
**   sqlite3WhereEnd()
**   Gosub flush_partition
**
**  flush_partition:
**   OpenDup (csr -> csr2)
**   foreach (record in eph-table) {
**     if( new peer ){
**       while( csr2!=csr ){
**         AggStep (xInverse)
**         Next (csr2)
**       }
**     }
**     AggFinal (xValue)
**     Gosub addrGosub
**   }
**
**========================================================================
**
** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
**   ...
**     if( new partition ){
**       AggFinal (xFinalize)
**     }
**     AggStep
**     AggFinal (xValue)
**     Gosub addrGosub
**   sqlite3WhereEnd()
**
** ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
** ROWS BETWEEN CURRENT ROW AND CURRENT ROW
** ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
**
**========================================================================
**
** ROWS BETWEEN UNBOUNDED PRECEDING AND <expr> PRECEDING
** ROWS BETWEEN <expr> PRECEDING    AND <expr> PRECEDING
** ROWS BETWEEN <expr> PRECEDING    AND CURRENT ROW
** ROWS BETWEEN UNBOUNDED PRECEDING AND <expr> FOLLOWING
** ROWS BETWEEN <expr> PRECEDING    AND <expr> FOLLOWING
** ROWS BETWEEN CURRENT ROW         AND <expr> FOLLOWING
** ROWS BETWEEN <expr> FOLLOWING    AND <expr> FOLLOWING
** ROWS BETWEEN <expr> PRECEDING    AND UNBOUNDED FOLLOWING
** ROWS BETWEEN <expr> FOLLOWING    AND UNBOUNDED FOLLOWING
**
**   Cases that involve <expr> PRECEDING or <expr> FOLLOWING.
**
**   ...
**     Insert (record in eph-table)
**   sqlite3WhereEnd()
**
*/
void sqlite3WindowCodeStep(
  Parse *pParse, 
  Select *p,
  WhereInfo *pWInfo,
  int regGosub, 
  int addrGosub
){
  Vdbe *v = sqlite3GetVdbe(pParse);
  Window *pWin;
  Window *pMWin = 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 addr;

  pParse->nMem += nSub + 2;

  /* Martial the row returned by the sub-select into an array of 
  ** 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( pMWin->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 = sqlite3KeyInfoFromExprList(pParse, pPart, 0, 0);
      addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPart, pMWin->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 = pMWin->regPart + nPart;

      KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(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);
    }

    sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrGosub);
    sqlite3VdbeAddOp1(v, OP_ResetSorter, pMWin->iEphCsr);
    sqlite3VdbeAddOp3(
        v, OP_Copy, reg+pMWin->nBufferCol, pMWin->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, addrGosub);
}


Changes to test/window2.tcl.
35
36
37
38
39
40
41
42
43
44
45
46
47





48
49
50
51
52
53
54
55
    }
  }
  if {$frag != ""} {
    lappend lSql $frag
  }
  #puts $lSql

  set ret [list]
  foreach stmt $lSql {
    set res [pg_exec $::db $stmt]
    set err [pg_result $res -error]
    if {$err!=""} { error $err }
    for {set i 0} {$i < [pg_result $res -numTuples]} {incr i} {





      lappend ret {*}[pg_result $res -getTuple $i]
    }
    pg_result $res -clear
  }

  set ret
}








|





>
>
>
>
>
|







35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
    }
  }
  if {$frag != ""} {
    lappend lSql $frag
  }
  #puts $lSql

  set ret ""
  foreach stmt $lSql {
    set res [pg_exec $::db $stmt]
    set err [pg_result $res -error]
    if {$err!=""} { error $err }
    for {set i 0} {$i < [pg_result $res -numTuples]} {incr i} {
      if {$i==0} {
        set ret [pg_result $res -getTuple 0]
      } else {
        append ret "   [pg_result $res -getTuple $i]"
      }
      # lappend ret {*}[pg_result $res -getTuple $i]
    }
    pg_result $res -clear
  }

  set ret
}

84
85
86
87
88
89
90









91
92
93
94
95
96
97
####################################################
"]
  puts $::fd {set testdir [file dirname $argv0]}
  puts $::fd {source $testdir/tester.tcl}
  puts $::fd "set testprefix $name"
  puts $::fd ""
}










proc finish_test {} {
  puts $::fd finish_test
  close $::fd
}

#=========================================================================







>
>
>
>
>
>
>
>
>







89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
####################################################
"]
  puts $::fd {set testdir [file dirname $argv0]}
  puts $::fd {source $testdir/tester.tcl}
  puts $::fd "set testprefix $name"
  puts $::fd ""
}

proc -- {args} {
  puts $::fd "# $args"
}

proc ========== {args} {
  puts $::fd "#[string repeat = 74]"
  puts $::fd ""
}

proc finish_test {} {
  puts $::fd finish_test
  close $::fd
}

#=========================================================================
117
118
119
120
121
122
123
























124
125
126
127
execsql_test 1.2 {
  SELECT sum(d) OVER () FROM t1;
}

execsql_test 1.3 {
  SELECT sum(d) OVER (PARTITION BY b) FROM t1;
}

























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
execsql_test 1.2 {
  SELECT sum(d) OVER () FROM t1;
}

execsql_test 1.3 {
  SELECT sum(d) OVER (PARTITION BY b) FROM t1;
}

puts $::fd finish_test
==========

execsql_test 2.1 {
  SELECT a, sum(d) OVER (
    PARTITION BY b ORDER BY d
    RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
  ) FROM t1
}

execsql_test 2.2 {
  SELECT a, sum(d) OVER (
    ORDER BY b
    RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
  ) FROM t1
}

execsql_test 2.3 {
  SELECT a, sum(d) OVER (
    ORDER BY d
    ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
  ) FROM t1
}

finish_test


Changes to test/window2.test.
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

43























44
45
  INSERT INTO t1 VALUES(4, 'even', 'four',  4);
  INSERT INTO t1 VALUES(5, 'odd',  'five',  5);
  INSERT INTO t1 VALUES(6, 'even', 'six',   6);
} {}

do_execsql_test 1.1 {
  SELECT c, sum(d) OVER (PARTITION BY b ORDER BY c) FROM t1;
} {four 4 six 10 two 12 five 5 one 6 three 9}

do_execsql_test 1.2 {
  SELECT sum(d) OVER () FROM t1;
} {21 21 21 21 21 21}

do_execsql_test 1.3 {
  SELECT sum(d) OVER (PARTITION BY b) FROM t1;

} {12 12 12 9 9 9}
























finish_test







|



|



>
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>


28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
  INSERT INTO t1 VALUES(4, 'even', 'four',  4);
  INSERT INTO t1 VALUES(5, 'odd',  'five',  5);
  INSERT INTO t1 VALUES(6, 'even', 'six',   6);
} {}

do_execsql_test 1.1 {
  SELECT c, sum(d) OVER (PARTITION BY b ORDER BY c) FROM t1;
} {four 4   six 10   two 12   five 5   one 6   three 9}

do_execsql_test 1.2 {
  SELECT sum(d) OVER () FROM t1;
} {21   21   21   21   21   21}

do_execsql_test 1.3 {
  SELECT sum(d) OVER (PARTITION BY b) FROM t1;
} {12   12   12   9   9   9}

finish_test
#==========================================================================

do_execsql_test 2.1 {
  SELECT a, sum(d) OVER (
    PARTITION BY b ORDER BY d
    RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
  ) FROM t1
} {2 12   4 10   6 6   1 9   3 8   5 5}

do_execsql_test 2.2 {
  SELECT a, sum(d) OVER (
    ORDER BY b
    RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
  ) FROM t1
} {2 21   4 21   6 21   1 9   3 9   5 9}

do_execsql_test 2.3 {
  SELECT a, sum(d) OVER (
    ORDER BY d
    ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
  ) FROM t1
} {1 21   2 21   3 21   4 21   5 21   6 21}

finish_test