/ Check-in [236cb75b]
Login

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

Overview
Comment:Do not flatten sub-queries that contain window functions.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | exp-window-functions
Files: files | file ages | folders
SHA3-256:236cb75bd1f0d5eb86aa5f52d8d548e7263c34633833dcea9dfc934f142113b8
User & Date: dan 2018-06-08 16:11:55
Context
2018-06-08
20:58
Add support for the WINDOW clause. check-in: 19c983b5 user: dan tags: exp-window-functions
16:11
Do not flatten sub-queries that contain window functions. check-in: 236cb75b user: dan tags: exp-window-functions
11:45
Fixes to allow group_concat() to be used as a window function. check-in: 89bbc9ba user: dan tags: exp-window-functions
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/expr.c.

1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
....
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
    if( flags&EXPRDUP_REDUCE ){
      nByte += dupedExprSize(p->pLeft, flags) + dupedExprSize(p->pRight, flags);
    }
  }
  return nByte;
}

static Window *winDup(sqlite3 *db, Window *p){
  Window *pNew = 0;
  if( p ){
    pNew = sqlite3DbMallocZero(db, sizeof(Window));
    if( pNew ){
      pNew->pFilter = sqlite3ExprDup(db, p->pFilter, 0);
      pNew->pPartition = sqlite3ExprListDup(db, p->pPartition, 0);
      pNew->pOrderBy = sqlite3ExprListDup(db, p->pOrderBy, 0);
      pNew->eType = p->eType;
      pNew->eEnd = p->eEnd;
      pNew->eStart = p->eStart;
      pNew->pStart = sqlite3ExprDup(db, pNew->pStart, 0);
      pNew->pEnd = sqlite3ExprDup(db, pNew->pEnd, 0);
    }
  }
  return pNew;
}

/*
** This function is similar to sqlite3ExprDup(), except that if pzBuffer 
** is not NULL then *pzBuffer is assumed to point to a buffer large enough 
** to store the copy of expression p, the copies of p->u.zToken
** (if applicable), and the copies of the p->pLeft and p->pRight expressions,
** if any. Before returning, *pzBuffer is set to the first byte past the
** portion of the buffer copied into by this function.
................................................................................
      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{







<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







 







|







1178
1179
1180
1181
1182
1183
1184


















1185
1186
1187
1188
1189
1190
1191
....
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
    if( flags&EXPRDUP_REDUCE ){
      nByte += dupedExprSize(p->pLeft, flags) + dupedExprSize(p->pRight, flags);
    }
  }
  return nByte;
}



















/*
** This function is similar to sqlite3ExprDup(), except that if pzBuffer 
** is not NULL then *pzBuffer is assumed to point to a buffer large enough 
** to store the copy of expression p, the copies of p->u.zToken
** (if applicable), and the copies of the p->pLeft and p->pRight expressions,
** if any. Before returning, *pzBuffer is set to the first byte past the
** portion of the buffer copied into by this function.
................................................................................
      if( pzBuffer ){
        *pzBuffer = zAlloc;
      }
    }else{
      if( ExprHasProperty(p, EP_Reduced|EP_TokenOnly) ){
        pNew->pWin = 0;
      }else{
        pNew->pWin = sqlite3WindowDup(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{

Changes to src/select.c.

3708
3709
3710
3711
3712
3713
3714
3715
3716
3717
3718
3719
3720
3721
3722
....
5894
5895
5896
5897
5898
5899
5900

5901
5902
5903
5904
5905
5906
5907
5908
5909
5910
5911
5912
5913
5914
5915
5916
5917
5918

5919
5920
5921
5922
5923
5924
5925
5926
5927
  pSrc = p->pSrc;
  assert( pSrc && iFrom>=0 && iFrom<pSrc->nSrc );
  pSubitem = &pSrc->a[iFrom];
  iParent = pSubitem->iCursor;
  pSub = pSubitem->pSelect;
  assert( pSub!=0 );

  if( p->pWin ) return 0;

  pSubSrc = pSub->pSrc;
  assert( pSubSrc );
  /* Prior to version 3.1.2, when LIMIT and OFFSET had to be simple constants,
  ** not arbitrary expressions, we allowed some combining of LIMIT and OFFSET
  ** because they could be computed at compile-time.  But when LIMIT and OFFSET
  ** became arbitrary expressions, we were forced to add restrictions (13)
................................................................................
    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 = 0;
      int bLoop = 0;

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

      sqlite3VdbeAddOp0(v, OP_Goto);
      sqlite3VdbeResolveLabel(v, addrGosub);
      if( bLoop ){
        addr = sqlite3VdbeAddOp1(v, OP_Rewind, pWin->iEphCsr);
      }else{
        addr = sqlite3VdbeCurrentAddr(v);
      }
      selectInnerLoop(pParse, p, -1, &sSort, &sDistinct, pDest, addr+1, 0);
      if( bLoop ){
        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,
          sqlite3WhereContinueLabel(pWInfo),
          sqlite3WhereBreakLabel(pWInfo));








|







 







>


<

|

|

<
<
<
<
<
|
<
<
<
<
>

|







3708
3709
3710
3711
3712
3713
3714
3715
3716
3717
3718
3719
3720
3721
3722
....
5894
5895
5896
5897
5898
5899
5900
5901
5902
5903

5904
5905
5906
5907
5908





5909




5910
5911
5912
5913
5914
5915
5916
5917
5918
5919
  pSrc = p->pSrc;
  assert( pSrc && iFrom>=0 && iFrom<pSrc->nSrc );
  pSubitem = &pSrc->a[iFrom];
  iParent = pSubitem->iCursor;
  pSub = pSubitem->pSelect;
  assert( pSub!=0 );

  if( p->pWin || pSub->pWin ) return 0;

  pSubSrc = pSub->pSrc;
  assert( pSubSrc );
  /* Prior to version 3.1.2, when LIMIT and OFFSET had to be simple constants,
  ** not arbitrary expressions, we allowed some combining of LIMIT and OFFSET
  ** because they could be computed at compile-time.  But when LIMIT and OFFSET
  ** became arbitrary expressions, we were forced to add restrictions (13)
................................................................................
    if( sSort.addrSortIndex>=0 && sSort.pOrderBy==0 ){
      sqlite3VdbeChangeToNoop(v, sSort.addrSortIndex);
    }

    assert( p->pEList==pEList );
    if( pWin ){
      int addrGosub = sqlite3VdbeMakeLabel(v);
      int iCont = sqlite3VdbeMakeLabel(v);
      int regGosub = ++pParse->nMem;
      int addr = 0;


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

      addr = sqlite3VdbeAddOp0(v, OP_Goto);
      sqlite3VdbeResolveLabel(v, addrGosub);





      selectInnerLoop(pParse, p, -1, &sSort, &sDistinct, pDest, iCont, 0);




      sqlite3VdbeResolveLabel(v, iCont);
      sqlite3VdbeAddOp1(v, OP_Return, regGosub);
      sqlite3VdbeJumpHere(v, addr);

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

Changes to src/sqliteInt.h.

3498
3499
3500
3501
3502
3503
3504
3505
3506
3507
3508

3509
3510
3511
3512
3513
3514
3515
};

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, int*);
int sqlite3WindowRewrite(Parse*, Select*);
int sqlite3ExpandSubquery(Parse*, struct SrcList_item*);
void sqlite3WindowUpdate(Parse*, Window*, FuncDef*);


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







|



>







3498
3499
3500
3501
3502
3503
3504
3505
3506
3507
3508
3509
3510
3511
3512
3513
3514
3515
3516
};

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);
int sqlite3WindowRewrite(Parse*, Select*);
int sqlite3ExpandSubquery(Parse*, struct SrcList_item*);
void sqlite3WindowUpdate(Parse*, Window*, FuncDef*);
Window *sqlite3WindowDup(sqlite3 *db, Window *p);

/*
** 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.

1556
1557
1558
1559
1560
1561
1562

1563


1564
1565
1566
1567
1568
1569
1570
....
1582
1583
1584
1585
1586
1587
1588

1589

1590
1591

















1592
1593
1594
1595
1596
1597
1598
....
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
....
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
      }else{
        addrJump = 0;
      }
      windowAggFinal(pParse, pMWin, pMWin->eStart==TK_CURRENT);
      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
    );

    if( addrJump ) sqlite3VdbeJumpHere(v, addrJump);
  }
................................................................................
  sqlite3VdbeAddOp2(v, OP_NewRowid, pMWin->iEphCsr, regRowid);
  sqlite3VdbeAddOp3(v, OP_Insert, pMWin->iEphCsr, regRecord, regRowid);

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

  windowAggFinal(pParse, pMWin, 1);

  sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, 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.
**
................................................................................
**
*/
void sqlite3WindowCodeStep(
  Parse *pParse, 
  Select *p,
  WhereInfo *pWInfo,
  int regGosub, 
  int addrGosub,
  int *pbLoop
){
  Window *pMWin = p->pWin;
  Window *pWin;

  *pbLoop = 0;
  if( (pMWin->eType==TK_ROWS 
   && (pMWin->eStart!=TK_UNBOUNDED||pMWin->eEnd!=TK_CURRENT||!pMWin->pOrderBy))
   || (pMWin->eStart==TK_CURRENT&&pMWin->eEnd==TK_UNBOUNDED&&pMWin->pOrderBy)
  ){
    windowCodeRowExprStep(pParse, p, pWInfo, regGosub, addrGosub);
    return;
  }
................................................................................
     || (pFunc->xSFunc==lagStepFunc)
    ){
      windowCodeCacheStep(pParse, p, pWInfo, regGosub, addrGosub);
      return;
    }
  }

  *pbLoop = 1;
  windowCodeDefaultStep(pParse, p, pWInfo, regGosub, addrGosub);
}








>

>
>







 







>

>


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







 







|
<




<







 







<



1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
....
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
....
1667
1668
1669
1670
1671
1672
1673
1674

1675
1676
1677
1678

1679
1680
1681
1682
1683
1684
1685
....
1693
1694
1695
1696
1697
1698
1699

1700
1701
1702
      }else{
        addrJump = 0;
      }
      windowAggFinal(pParse, pMWin, pMWin->eStart==TK_CURRENT);
      if( addrGoto ) sqlite3VdbeJumpHere(v, addrGoto);
    }

    sqlite3VdbeAddOp2(v, OP_Rewind, pMWin->iEphCsr,sqlite3VdbeCurrentAddr(v)+3);
    sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrGosub);
    sqlite3VdbeAddOp2(v, OP_Next, pMWin->iEphCsr, sqlite3VdbeCurrentAddr(v)-1);

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

    if( addrJump ) sqlite3VdbeJumpHere(v, addrJump);
  }
................................................................................
  sqlite3VdbeAddOp2(v, OP_NewRowid, pMWin->iEphCsr, regRowid);
  sqlite3VdbeAddOp3(v, OP_Insert, pMWin->iEphCsr, regRecord, regRowid);

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

  windowAggFinal(pParse, pMWin, 1);
  sqlite3VdbeAddOp2(v, OP_Rewind, pMWin->iEphCsr,sqlite3VdbeCurrentAddr(v)+3);
  sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrGosub);
  sqlite3VdbeAddOp2(v, OP_Next, pMWin->iEphCsr, sqlite3VdbeCurrentAddr(v)-1);
}

Window *sqlite3WindowDup(sqlite3 *db, Window *p){
  Window *pNew = 0;
  if( p ){
    pNew = sqlite3DbMallocZero(db, sizeof(Window));
    if( pNew ){
      pNew->pFilter = sqlite3ExprDup(db, p->pFilter, 0);
      pNew->pPartition = sqlite3ExprListDup(db, p->pPartition, 0);
      pNew->pOrderBy = sqlite3ExprListDup(db, p->pOrderBy, 0);
      pNew->eType = p->eType;
      pNew->eEnd = p->eEnd;
      pNew->eStart = p->eStart;
      pNew->pStart = sqlite3ExprDup(db, pNew->pStart, 0);
      pNew->pEnd = sqlite3ExprDup(db, pNew->pEnd, 0);
    }
  }
  return pNew;
}

/*
** 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.
**
................................................................................
**
*/
void sqlite3WindowCodeStep(
  Parse *pParse, 
  Select *p,
  WhereInfo *pWInfo,
  int regGosub, 
  int addrGosub

){
  Window *pMWin = p->pWin;
  Window *pWin;


  if( (pMWin->eType==TK_ROWS 
   && (pMWin->eStart!=TK_UNBOUNDED||pMWin->eEnd!=TK_CURRENT||!pMWin->pOrderBy))
   || (pMWin->eStart==TK_CURRENT&&pMWin->eEnd==TK_UNBOUNDED&&pMWin->pOrderBy)
  ){
    windowCodeRowExprStep(pParse, p, pWInfo, regGosub, addrGosub);
    return;
  }
................................................................................
     || (pFunc->xSFunc==lagStepFunc)
    ){
      windowCodeCacheStep(pParse, p, pWInfo, regGosub, addrGosub);
      return;
    }
  }


  windowCodeDefaultStep(pParse, p, pWInfo, regGosub, addrGosub);
}

Changes to test/window1.test.

190
191
192
193
194
195
196



















197
198
199
do_catchsql_test 5.3 {
  SELECT ntile('zbc') OVER (ORDER BY a) FROM t2;
} {1 {argument of ntile must be a positive integer}}
do_execsql_test 5.4 {
  CREATE TABLE t4(a, b);
  SELECT ntile(1) OVER (ORDER BY a) FROM t4;
} {}





















finish_test







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



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
do_catchsql_test 5.3 {
  SELECT ntile('zbc') OVER (ORDER BY a) FROM t2;
} {1 {argument of ntile must be a positive integer}}
do_execsql_test 5.4 {
  CREATE TABLE t4(a, b);
  SELECT ntile(1) OVER (ORDER BY a) FROM t4;
} {}

#-------------------------------------------------------------------------
reset_db
do_execsql_test 6.1 {
  CREATE TABLE t1(x);
  INSERT INTO t1 VALUES(7), (6), (5), (4), (3), (2), (1);

  CREATE TABLE t2(x);
  INSERT INTO t2 VALUES('b'), ('a');

  SELECT x, count(*) OVER (ORDER BY x) FROM t1;
} {1 1 2 2 3 3 4 4 5 5 6 6 7 7}

do_execsql_test 6.2 {
  SELECT * FROM t2, (SELECT x, count(*) OVER (ORDER BY x) FROM t1);
} {
  b 1 1 b 2 2 b 3 3 b 4 4 b 5 5 b 6 6 b 7 7
  a 1 1 a 2 2 a 3 3 a 4 4 a 5 5 a 6 6 a 7 7
}


finish_test