/ Check-in [bb915854]
Login

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

Overview
Comment:Improve comments and code legibility in new file window.c.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | exp-window-functions
Files: files | file ages | folders
SHA3-256:bb915854d435bdd78f141d70e23527e97922ec176acd3ed8060c78dffc96bab8
User & Date: dan 2018-06-14 14:27:05
Context
2018-06-14
14:30
Merge latest trunk changes into this branch. check-in: 5cf5f180 user: dan tags: exp-window-functions
14:27
Improve comments and code legibility in new file window.c. check-in: bb915854 user: dan tags: exp-window-functions
2018-06-13
20:29
Fix problems with "RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING" window frames. check-in: c34f31db user: dan tags: exp-window-functions
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/window.c.

1232
1233
1234
1235
1236
1237
1238






1239
1240
1241
1242
1243
1244
1245
....
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269

1270
1271
1272
1273
1274
1275
1276
....
1547
1548
1549
1550
1551
1552
1553










1554
1555
1556
1557
1558
1559
1560
....
1577
1578
1579
1580
1581
1582
1583













1584












1585































1586
1587
1588
1589
1590
1591
1592
....
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
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
....
1874
1875
1876
1877
1878
1879
1880
1881
1882




1883
1884
1885


























1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
  if( regInvArg ){
    windowAggStep(pParse, pMWin, pMWin->iEphCsr, 1, regInvArg, regInvSize);
  }
  sqlite3VdbeAddOp2(v, OP_Next, pMWin->iEphCsr, addr);
  sqlite3VdbeJumpHere(v, addr+1);   /* The OP_Goto */
}







static int windowInitAccum(Parse *pParse, Window *pMWin){
  Vdbe *v = sqlite3GetVdbe(pParse);
  int regArg;
  int nArg = 0;
  Window *pWin;
  for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
    sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);
................................................................................
  regArg = pParse->nMem+1;
  pParse->nMem += nArg;
  return regArg;
}


/*
** ROWS BETWEEN <expr1> PRECEDING AND <expr2> FOLLOWING
** ----------------------------------------------------
**
** Pseudo-code for the implementation of this window frame type is as
** follows. sqlite3WhereBegin() has already been called to generate the
** top of the main loop when this function is called.
**
** Each time the sub-routine at addrGosub is invoked, a single output
** row is generated based on the current row indicated by Window.iEphCsr.

**
**     ...
**       if( new partition ){
**         Gosub flush_partition
**       }
**       Insert (record in eph-table)
**     sqlite3WhereEnd()
................................................................................
  sqlite3VdbeAddOp1(v, OP_Return, regFlushPart);

  /* Jump to here to skip over flush_partition */
  sqlite3VdbeJumpHere(v, addrGoto);
}

/*










** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
**
**   flush_partition:
**     Once {
**       OpenDup (iEphCsr -> csrLead)
**     }
**     Integer ctr 0
................................................................................
**       Next iEphCsr
**     }
**
**     ResetSorter (csr)
**     Return
**
** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW













** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING












** RANGE BETWEEN CURRENT ROW AND CURRENT ROW 































*/
static void windowCodeCacheStep(
  Parse *pParse, 
  Select *p,
  WhereInfo *pWInfo,
  int regGosub, 
  int addrGosub
................................................................................
  Window *pMWin = p->pWin;
  Vdbe *v = sqlite3GetVdbe(pParse);
  Window *pWin;
  int k;
  int addr;
  ExprList *pPart = pMWin->pPartition;
  ExprList *pOrderBy = pMWin->pOrderBy;
  int nPeer = pOrderBy->nExpr;
  int regNewPeer;

  int addrGoto;                   /* Address of Goto used to jump flush_par.. */
  int addrNext;                   /* Jump here for next iteration of loop */
  int regFlushPart;
  int lblFlushPart;
  int csrLead;
  int regCtr;
  int regArg;                     /* Register array to martial function args */
  int regSize;
  int nArg;
  int bReverse;
  int lblEmpty;



  assert( (pMWin->eStart==TK_UNBOUNDED && pMWin->eEnd==TK_CURRENT) 
       || (pMWin->eStart==TK_UNBOUNDED && pMWin->eEnd==TK_UNBOUNDED) 
       || (pMWin->eStart==TK_CURRENT && pMWin->eEnd==TK_CURRENT) 
       || (pMWin->eStart==TK_CURRENT && pMWin->eEnd==TK_UNBOUNDED) 
  );

  lblEmpty = sqlite3VdbeMakeLabel(v);
  bReverse = (pMWin->eStart==TK_CURRENT && pMWin->eEnd==TK_UNBOUNDED);
  regNewPeer = pParse->nMem+1;
  pParse->nMem += nPeer;

  /* Allocate register and label for the "flush_partition" sub-routine. */
  regFlushPart = ++pParse->nMem;
  lblFlushPart = sqlite3VdbeMakeLabel(v);

................................................................................
  Parse *pParse,                  /* Parse context */
  Select *p,                      /* Rewritten SELECT statement */
  WhereInfo *pWInfo,              /* Context returned by sqlite3WhereBegin() */
  int regGosub,                   /* Register for OP_Gosub */
  int addrGosub                   /* OP_Gosub here to return each row */
){
  Window *pMWin = p->pWin;
  ExprList *pOrderBy = pMWin->pOrderBy;





  /* Call windowCodeRowExprStep() for all "ROWS" window modes except:
  **
  **   ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW


























  */
  if( (pMWin->eType==TK_ROWS 
   && (pMWin->eStart!=TK_UNBOUNDED || pMWin->eEnd!=TK_CURRENT || !pOrderBy))
  ){
    windowCodeRowExprStep(pParse, p, pWInfo, regGosub, addrGosub);
  }else{
    Window *pWin;
    int bCache = 0;

    if( pMWin->eStart==TK_CURRENT && pMWin->eEnd==TK_UNBOUNDED && pOrderBy ){
      bCache = 1;
    }else{
      /* Call windowCodeCacheStep() if there is a window function that requires
      ** that the entire partition be cached in a temp table before any rows
      ** are returned.  */
      for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
        FuncDef *pFunc = pWin->pFunc;
        if( (pFunc->funcFlags & SQLITE_FUNC_WINDOW_SIZE)
            || (pFunc->xSFunc==nth_valueStepFunc)
            || (pFunc->xSFunc==first_valueStepFunc)
            || (pFunc->xSFunc==leadStepFunc)
            || (pFunc->xSFunc==lagStepFunc)
          ){
          bCache = 1;
          break;
        }
      }
    }

    /* Otherwise, call windowCodeDefaultStep().  */







>
>
>
>
>
>







 







|
|
|
<
<
<

<
<
>







 







>
>
>
>
>
>
>
>
>
>







 







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

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







 







|











<

>
>








<







 







<

>
>
>
>
|


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

|
|




|

|


<
<
<



|
|
|
|
|







1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
....
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269



1270


1271
1272
1273
1274
1275
1276
1277
1278
....
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
....
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
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
....
1662
1663
1664
1665
1666
1667
1668
1669
1670
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
....
1942
1943
1944
1945
1946
1947
1948

1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994



1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
  if( regInvArg ){
    windowAggStep(pParse, pMWin, pMWin->iEphCsr, 1, regInvArg, regInvSize);
  }
  sqlite3VdbeAddOp2(v, OP_Next, pMWin->iEphCsr, addr);
  sqlite3VdbeJumpHere(v, addr+1);   /* The OP_Goto */
}

/*
** Generate code to set the accumulator register for each window function
** in the linked list passed as the second argument to NULL. And perform
** any equivalent initialization required by any built-in window functions
** in the list.
*/
static int windowInitAccum(Parse *pParse, Window *pMWin){
  Vdbe *v = sqlite3GetVdbe(pParse);
  int regArg;
  int nArg = 0;
  Window *pWin;
  for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
    sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);
................................................................................
  regArg = pParse->nMem+1;
  pParse->nMem += nArg;
  return regArg;
}


/*
** This function does the work of sqlite3WindowCodeStep() for all "ROWS"
** window frame types except for "BETWEEN UNBOUNDED PRECEDING AND CURRENT
** ROW". Pseudo-code for each follows.



**


** ROWS BETWEEN <expr1> PRECEDING AND <expr2> FOLLOWING
**
**     ...
**       if( new partition ){
**         Gosub flush_partition
**       }
**       Insert (record in eph-table)
**     sqlite3WhereEnd()
................................................................................
  sqlite3VdbeAddOp1(v, OP_Return, regFlushPart);

  /* Jump to here to skip over flush_partition */
  sqlite3VdbeJumpHere(v, addrGoto);
}

/*
** This function does the work of sqlite3WindowCodeStep() for cases that
** would normally be handled by windowCodeDefaultStep() when there are
** one or more built-in window-functions that require the entire partition
** to be cached in a temp table before any rows can be returned. Additionally.
** "RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING" is always handled by
** this function.
**
** Pseudo-code corresponding to the VM code generated by this function
** for each type of window follows.
**
** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
**
**   flush_partition:
**     Once {
**       OpenDup (iEphCsr -> csrLead)
**     }
**     Integer ctr 0
................................................................................
**       Next iEphCsr
**     }
**
**     ResetSorter (csr)
**     Return
**
** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
**
**   As above, except that the "if( new peer )" branch is always taken.
**
** RANGE BETWEEN CURRENT ROW AND CURRENT ROW 
**
**   As above, except that each of the for() loops becomes:
**
**         for(i=0; i<ctr; i++){
**           Gosub addrGosub
**           AggStep (xInverse, iEphCsr)
**           Next iEphCsr
**         }
**
** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
**
**   flush_partition:
**     Once {
**       OpenDup (iEphCsr -> csrLead)
**     }
**     foreach row (csrLead) {
**       AggStep (csrLead)
**     }
**     foreach row (iEphCsr) {
**       Gosub addrGosub
**     }
** 
** RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
**
**   flush_partition:
**     Once {
**       OpenDup (iEphCsr -> csrLead)
**     }
**     foreach row (csrLead){
**       AggStep (csrLead)
**     }
**     Rewind (csrLead)
**     Integer ctr 0
**     foreach row (csrLead){
**       if( new peer ){
**         AggFinal (xValue)
**         for(i=0; i<ctr; i++){
**           Gosub addrGosub
**           AggStep (xInverse, iEphCsr)
**           Next iEphCsr
**         }
**         Integer ctr 0
**       }
**       Incr ctr
**     }
**
**     AggFinal (xFinalize)
**     for(i=0; i<ctr; i++){
**       Gosub addrGosub
**       Next iEphCsr
**     }
**
**     ResetSorter (csr)
**     Return
*/
static void windowCodeCacheStep(
  Parse *pParse, 
  Select *p,
  WhereInfo *pWInfo,
  int regGosub, 
  int addrGosub
................................................................................
  Window *pMWin = p->pWin;
  Vdbe *v = sqlite3GetVdbe(pParse);
  Window *pWin;
  int k;
  int addr;
  ExprList *pPart = pMWin->pPartition;
  ExprList *pOrderBy = pMWin->pOrderBy;
  int nPeer = pOrderBy ? pOrderBy->nExpr : 0;
  int regNewPeer;

  int addrGoto;                   /* Address of Goto used to jump flush_par.. */
  int addrNext;                   /* Jump here for next iteration of loop */
  int regFlushPart;
  int lblFlushPart;
  int csrLead;
  int regCtr;
  int regArg;                     /* Register array to martial function args */
  int regSize;
  int nArg;

  int lblEmpty;
  int bReverse = pMWin->pOrderBy && pMWin->eStart==TK_CURRENT 
          && pMWin->eEnd==TK_UNBOUNDED;

  assert( (pMWin->eStart==TK_UNBOUNDED && pMWin->eEnd==TK_CURRENT) 
       || (pMWin->eStart==TK_UNBOUNDED && pMWin->eEnd==TK_UNBOUNDED) 
       || (pMWin->eStart==TK_CURRENT && pMWin->eEnd==TK_CURRENT) 
       || (pMWin->eStart==TK_CURRENT && pMWin->eEnd==TK_UNBOUNDED) 
  );

  lblEmpty = sqlite3VdbeMakeLabel(v);

  regNewPeer = pParse->nMem+1;
  pParse->nMem += nPeer;

  /* Allocate register and label for the "flush_partition" sub-routine. */
  regFlushPart = ++pParse->nMem;
  lblFlushPart = sqlite3VdbeMakeLabel(v);

................................................................................
  Parse *pParse,                  /* Parse context */
  Select *p,                      /* Rewritten SELECT statement */
  WhereInfo *pWInfo,              /* Context returned by sqlite3WhereBegin() */
  int regGosub,                   /* Register for OP_Gosub */
  int addrGosub                   /* OP_Gosub here to return each row */
){
  Window *pMWin = p->pWin;


  /* There are three different functions that may be used to do the work
  ** of this one, depending on the window frame and the specific built-in
  ** window functions used (if any).
  **
  ** windowCodeRowExprStep() handles all "ROWS" window frames, except for:
  **
  **   ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
  **
  ** The exception is because windowCodeRowExprStep() implements all window
  ** frame types by caching the entire partition in a temp table, and
  ** "ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW" is easy enough to
  ** implement without such a cache.
  **
  ** windowCodeCacheStep() is used for:
  **
  **   RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
  **
  ** It is also used for anything not handled by windowCodeRowExprStep() 
  ** that invokes a built-in window function that requires the entire 
  ** partition to be cached in a temp table before any rows are returned
  ** (e.g. nth_value() or percent_rank()).
  **
  ** Finally, assuming there is no built-in window function that requires
  ** the partition to be cached, windowCodeDefaultStep() is used for:
  **
  **   RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW 
  **   RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
  **   RANGE BETWEEN CURRENT ROW AND CURRENT ROW 
  **   ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
  **
  ** windowCodeDefaultStep() is the only one of the three functions that
  ** does not cache each partition in a temp table before beginning to
  ** return rows.
  */
  if( pMWin->eType==TK_ROWS 
   && (pMWin->eStart!=TK_UNBOUNDED||pMWin->eEnd!=TK_CURRENT||!pMWin->pOrderBy)
  ){
    windowCodeRowExprStep(pParse, p, pWInfo, regGosub, addrGosub);
  }else{
    Window *pWin;
    int bCache = 0;               /* True to use CacheStep() */

    if( pMWin->eStart==TK_CURRENT && pMWin->eEnd==TK_UNBOUNDED ){
      bCache = 1;
    }else{



      for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
        FuncDef *pFunc = pWin->pFunc;
        if( (pFunc->funcFlags & SQLITE_FUNC_WINDOW_SIZE)
         || (pFunc->xSFunc==nth_valueStepFunc)
         || (pFunc->xSFunc==first_valueStepFunc)
         || (pFunc->xSFunc==leadStepFunc)
         || (pFunc->xSFunc==lagStepFunc)
        ){
          bCache = 1;
          break;
        }
      }
    }

    /* Otherwise, call windowCodeDefaultStep().  */