/ Check-in [b5b18f66]
Login

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

Overview
Comment:Allow an entire partition to be cached in a temp table for all types of window frames. This is required by nth_value() and others.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | exp-window-functions
Files: files | file ages | folders
SHA3-256:b5b18f661341d8d450147e62d321791c706f16c0550bcd98eec3e0220c039189
User & Date: dan 2018-06-01 21:00:08
Context
2018-06-02
21:04
Add support for window functions row_number(), rank(), dense_rank() and percent_rank(). check-in: 91c1cb7a user: dan tags: exp-window-functions
2018-06-01
21:00
Allow an entire partition to be cached in a temp table for all types of window frames. This is required by nth_value() and others. check-in: b5b18f66 user: dan tags: exp-window-functions
2018-05-30
20:44
Allow min() and max() to be used as window functions. check-in: c16125a8 user: dan tags: exp-window-functions
Changes
Hide Diffs Side-by-Side Diffs Show Whitespace Changes Patch

Changes to src/window.c.

   189    189         }else{
   190    190           sqlite3VdbeChangeP3(v, -1, pWin->regResult);
   191    191         }
   192    192       }
   193    193     }
   194    194   }
   195    195   
          196  +static void windowPartitionCache(
          197  +  Parse *pParse,
          198  +  Select *p,
          199  +  WhereInfo *pWInfo,
          200  +  int regFlushPart,
          201  +  int lblFlushPart
          202  +){
          203  +  Window *pMWin = p->pWin;
          204  +  Vdbe *v = sqlite3GetVdbe(pParse);
          205  +  Window *pWin;
          206  +  int iSubCsr = p->pSrc->a[0].iCursor;
          207  +  int nSub = p->pSrc->a[0].pTab->nCol;
          208  +  int k;
          209  +
          210  +  int reg = pParse->nMem+1;
          211  +  int regRecord = reg+nSub;
          212  +  int regRowid = regRecord+1;
          213  +
          214  +  pParse->nMem += nSub + 2;
          215  +
          216  +  /* Martial the row returned by the sub-select into an array of 
          217  +  ** registers. */
          218  +  for(k=0; k<nSub; k++){
          219  +    sqlite3VdbeAddOp3(v, OP_Column, iSubCsr, k, reg+k);
          220  +  }
          221  +  sqlite3VdbeAddOp3(v, OP_MakeRecord, reg, nSub, regRecord);
          222  +
          223  +  /* Check if this is the start of a new partition. If so, call the
          224  +  ** flush_partition sub-routine.  */
          225  +  if( pMWin->pPartition ){
          226  +    int addr;
          227  +    ExprList *pPart = pMWin->pPartition;
          228  +    int nPart = (pPart ? pPart->nExpr : 0);
          229  +    int regNewPart = reg + pMWin->nBufferCol;
          230  +    KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pPart, 0, 0);
          231  +
          232  +    addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPart, pMWin->regPart,nPart);
          233  +    sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
          234  +    sqlite3VdbeAddOp3(v, OP_Jump, addr+2, addr+4, addr+2);
          235  +    sqlite3VdbeAddOp3(v, OP_Copy, regNewPart, pMWin->regPart, nPart-1);
          236  +    sqlite3VdbeAddOp2(v, OP_Gosub, regFlushPart, lblFlushPart);
          237  +  }
          238  +
          239  +  /* Buffer the current row in the ephemeral table. */
          240  +  sqlite3VdbeAddOp2(v, OP_NewRowid, pMWin->iEphCsr, regRowid);
          241  +  sqlite3VdbeAddOp3(v, OP_Insert, pMWin->iEphCsr, regRecord, regRowid);
          242  +
          243  +  /* End of the input loop */
          244  +  sqlite3WhereEnd(pWInfo);
          245  +
          246  +  /* Invoke "flush_partition" to deal with the final (or only) partition */
          247  +  sqlite3VdbeAddOp2(v, OP_Gosub, regFlushPart, lblFlushPart);
          248  +}
   196    249   
   197    250   /*
   198    251   ** ROWS BETWEEN <expr1> PRECEDING AND <expr2> FOLLOWING
   199    252   ** ----------------------------------------------------
   200    253   **
   201    254   ** Pseudo-code for the implementation of this window frame type is as
   202    255   ** follows. sqlite3WhereBegin() has already been called to generate the
................................................................................
   325    378     int regGosub, 
   326    379     int addrGosub
   327    380   ){
   328    381     Window *pMWin = p->pWin;
   329    382     Vdbe *v = sqlite3GetVdbe(pParse);
   330    383     Window *pWin;
   331    384     int k;
   332         -  int iSubCsr = p->pSrc->a[0].iCursor;
   333    385     int nSub = p->pSrc->a[0].pTab->nCol;
   334    386     int regFlushPart;               /* Register for "Gosub flush_partition" */
   335    387     int lblFlushPart;               /* Label for "Gosub flush_partition" */
   336    388     int lblFlushDone;               /* Label for "Gosub flush_partition_done" */
   337    389   
   338         -  int reg = pParse->nMem+1;
   339         -  int regRecord = reg+nSub;
   340         -  int regRowid = regRecord+1;
          390  +  int regArg;
          391  +  int nArg;
   341    392     int addr;
   342    393     int csrStart = pParse->nTab++;
   343    394     int csrEnd = pParse->nTab++;
   344    395     int regStart;                    /* Value of <expr> PRECEDING */
   345    396     int regEnd;                      /* Value of <expr> FOLLOWING */
   346    397     int addrNext;
   347    398     int addrGoto;
................................................................................
   369    420     if( pMWin->eType==TK_RANGE 
   370    421      && pMWin->eStart==TK_CURRENT 
   371    422      && pMWin->eEnd==TK_UNBOUNDED
   372    423     ){
   373    424       bRange = 1;
   374    425     }
   375    426   
   376         -  pParse->nMem += nSub + 2;
   377         -
   378    427     /* Allocate register and label for the "flush_partition" sub-routine. */
   379    428     regFlushPart = ++pParse->nMem;
   380    429     lblFlushPart = sqlite3VdbeMakeLabel(v);
   381    430     lblFlushDone = sqlite3VdbeMakeLabel(v);
   382    431   
   383    432     regStart = ++pParse->nMem;
   384    433     regEnd = ++pParse->nMem;
   385    434   
   386         -  /* Martial the row returned by the sub-select into an array of 
   387         -  ** registers. */
   388         -  for(k=0; k<nSub; k++){
   389         -    sqlite3VdbeAddOp3(v, OP_Column, iSubCsr, k, reg+k);
   390         -  }
   391         -  sqlite3VdbeAddOp3(v, OP_MakeRecord, reg, nSub, regRecord);
          435  +  windowPartitionCache(pParse, p, pWInfo, regFlushPart, lblFlushPart);
   392    436   
   393         -  /* Check if this is the start of a new partition. If so, call the
   394         -  ** flush_partition sub-routine.  */
   395         -  if( pMWin->pPartition ){
   396         -    ExprList *pPart = pMWin->pPartition;
   397         -    int nPart = (pPart ? pPart->nExpr : 0);
   398         -    int regNewPart = reg + pMWin->nBufferCol;
   399         -    KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pPart, 0, 0);
   400         -
   401         -    addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPart, pMWin->regPart,nPart);
   402         -    sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
   403         -    sqlite3VdbeAddOp3(v, OP_Jump, addr+2, addr+4, addr+2);
   404         -    sqlite3VdbeAddOp2(v, OP_Gosub, regFlushPart, lblFlushPart);
   405         -    sqlite3VdbeAddOp3(v, OP_Copy, regNewPart, pMWin->regPart, nPart);
   406         -  }
   407         -
   408         -  /* Buffer the current row in the ephemeral table. */
   409         -  sqlite3VdbeAddOp2(v, OP_NewRowid, pMWin->iEphCsr, regRowid);
   410         -  sqlite3VdbeAddOp3(v, OP_Insert, pMWin->iEphCsr, regRecord, regRowid);
   411         -
   412         -  /* End of the input loop */
   413         -  sqlite3WhereEnd(pWInfo);
   414         -
   415         -  /* Invoke "flush_partition" to deal with the final (or only) partition */
   416         -  sqlite3VdbeAddOp2(v, OP_Gosub, regFlushPart, lblFlushPart);
   417    437     addrGoto = sqlite3VdbeAddOp0(v, OP_Goto);
   418    438   
   419    439     /* Start of "flush_partition" */
   420    440     sqlite3VdbeResolveLabel(v, lblFlushPart);
   421    441     sqlite3VdbeAddOp2(v, OP_Once, 0, sqlite3VdbeCurrentAddr(v)+3);
   422    442     sqlite3VdbeAddOp2(v, OP_OpenDup, csrStart, pMWin->iEphCsr);
   423    443     sqlite3VdbeAddOp2(v, OP_OpenDup, csrEnd, pMWin->iEphCsr);
................................................................................
   439    459     */
   440    460     if( pMWin->pEnd && pMWin->pStart && pMWin->eStart==TK_FOLLOWING ){
   441    461       assert( pMWin->eEnd==TK_FOLLOWING );
   442    462       sqlite3VdbeAddOp3(v, OP_Subtract, regStart, regEnd, regEnd);
   443    463     }
   444    464   
   445    465     /* Initialize the accumulator register for each window function to NULL */
          466  +  nArg = 0;
   446    467     for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
   447    468       sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);
          469  +    nArg = MAX(nArg, pWin->nArg);
   448    470     }
          471  +  regArg = pParse->nMem+1;
          472  +  pParse->nMem += nArg;
   449    473   
   450    474     sqlite3VdbeAddOp2(v, OP_Rewind, pMWin->iEphCsr, lblFlushDone);
   451    475     sqlite3VdbeAddOp2(v, OP_Rewind, csrStart, lblFlushDone);
   452    476     sqlite3VdbeChangeP5(v, 1);
   453    477     sqlite3VdbeAddOp2(v, OP_Rewind, csrEnd, lblFlushDone);
   454    478     sqlite3VdbeChangeP5(v, 1);
   455    479   
................................................................................
   458    482     ** do nothing.  */
   459    483     addrTop = sqlite3VdbeCurrentAddr(v);
   460    484     if( pMWin->eEnd==TK_PRECEDING ){
   461    485       addrIfPos1 = sqlite3VdbeAddOp3(v, OP_IfPos, regEnd, 0 , 1);
   462    486     }
   463    487     sqlite3VdbeAddOp2(v, OP_Next, csrEnd, sqlite3VdbeCurrentAddr(v)+2);
   464    488     addr = sqlite3VdbeAddOp0(v, OP_Goto);
   465         -  windowAggStep(pParse, pMWin, csrEnd, 0, reg);
          489  +  windowAggStep(pParse, pMWin, csrEnd, 0, regArg);
   466    490     if( pMWin->eEnd==TK_UNBOUNDED ){
   467    491       sqlite3VdbeAddOp2(v, OP_Goto, 0, addrTop);
   468    492       sqlite3VdbeJumpHere(v, addr);
   469    493       addrTop = sqlite3VdbeCurrentAddr(v);
   470    494     }else{
   471    495       sqlite3VdbeJumpHere(v, addr);
   472    496       if( pMWin->eEnd==TK_PRECEDING ){
................................................................................
   524    548         addrJumpHere = sqlite3VdbeAddOp3(v, OP_IfPos, regStart, 0 , 1);
   525    549       }
   526    550       if( bRange ){
   527    551         sqlite3VdbeAddOp3(v, OP_IfPos, regPeer, sqlite3VdbeCurrentAddr(v)+2, 1);
   528    552         addrJumpHere = sqlite3VdbeAddOp0(v, OP_Goto);
   529    553       }
   530    554       sqlite3VdbeAddOp2(v, OP_Next, csrStart, sqlite3VdbeCurrentAddr(v)+1);
   531         -    windowAggStep(pParse, pMWin, csrStart, 1, reg);
          555  +    windowAggStep(pParse, pMWin, csrStart, 1, regArg);
   532    556       if( bRange ){
   533    557         sqlite3VdbeAddOp2(v, OP_Goto, 0, addrJumpHere-1);
   534    558       }
   535    559       if( addrJumpHere ){
   536    560         sqlite3VdbeJumpHere(v, addrJumpHere);
   537    561       }
   538    562     }
................................................................................
   549    573     /* Jump to here to skip over flush_partition */
   550    574     sqlite3VdbeJumpHere(v, addrGoto);
   551    575   }
   552    576   
   553    577   /*
   554    578   ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
   555    579   **
          580  +**   flush_partition:
          581  +**     Once {
          582  +**       OpenDup (iEphCsr -> csrLead)
          583  +**     }
          584  +**     Integer ctr 0
          585  +**     foreach row (csrLead){
          586  +**       if( new peer ){
          587  +**         AggFinal (xValue)
          588  +**         for(i=0; i<ctr; i++){
          589  +**           Gosub addrGosub
          590  +**           Next iEphCsr
          591  +**         }
          592  +**         Integer ctr 0
          593  +**       }
          594  +**       AggStep (csrLead)
          595  +**       Incr ctr
          596  +**     }
          597  +**
          598  +**     AggFinal (xFinalize)
          599  +**     for(i=0; i<ctr; i++){
          600  +**       Gosub addrGosub
          601  +**       Next iEphCsr
          602  +**     }
          603  +**
          604  +**     ResetSorter (csr)
          605  +**     Return
          606  +**
          607  +** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
          608  +** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
          609  +** RANGE BETWEEN CURRENT ROW AND CURRENT ROW 
          610  +**
          611  +**   TODO.
          612  +*/
          613  +static void windowCodeCacheStep(
          614  +  Parse *pParse, 
          615  +  Select *p,
          616  +  WhereInfo *pWInfo,
          617  +  int regGosub, 
          618  +  int addrGosub
          619  +){
          620  +  Window *pMWin = p->pWin;
          621  +  Vdbe *v = sqlite3GetVdbe(pParse);
          622  +  Window *pWin;
          623  +  int k;
          624  +  int addr;
          625  +  ExprList *pPart = pMWin->pPartition;
          626  +  ExprList *pOrderBy = pMWin->pOrderBy;
          627  +  int nPeer = pOrderBy->nExpr;
          628  +  int regNewPeer;
          629  +
          630  +  int addrGoto;                   /* Address of Goto used to jump flush_par.. */
          631  +  int addrRewind;                 /* Address of Rewind that starts loop */
          632  +  int regFlushPart;
          633  +  int lblFlushPart;
          634  +  int csrLead;
          635  +  int regCtr;
          636  +  int regArg;                     /* Register array to martial function args */
          637  +  int nArg;
          638  +
          639  +  assert( (pMWin->eStart==TK_UNBOUNDED && pMWin->eEnd==TK_CURRENT) 
          640  +  );
          641  +
          642  +  regNewPeer = pParse->nMem+1;
          643  +  pParse->nMem += nPeer;
          644  +
          645  +  /* Allocate register and label for the "flush_partition" sub-routine. */
          646  +  regFlushPart = ++pParse->nMem;
          647  +  lblFlushPart = sqlite3VdbeMakeLabel(v);
          648  +
          649  +  csrLead = pParse->nTab++;
          650  +  regCtr = ++pParse->nMem;
          651  +
          652  +  windowPartitionCache(pParse, p, pWInfo, regFlushPart, lblFlushPart);
          653  +  addrGoto = sqlite3VdbeAddOp0(v, OP_Goto);
          654  +
          655  +  /* Start of "flush_partition" */
          656  +  sqlite3VdbeResolveLabel(v, lblFlushPart);
          657  +  sqlite3VdbeAddOp2(v, OP_Once, 0, sqlite3VdbeCurrentAddr(v)+2);
          658  +  sqlite3VdbeAddOp2(v, OP_OpenDup, csrLead, pMWin->iEphCsr);
          659  +
          660  +  /* Initialize the accumulator register for each window function to NULL */
          661  +  nArg = 0;
          662  +  for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
          663  +    sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);
          664  +    nArg = MAX(nArg, pWin->nArg);
          665  +  }
          666  +  regArg = pParse->nMem+1;
          667  +  pParse->nMem += nArg;
          668  +
          669  +  sqlite3VdbeAddOp2(v, OP_Integer, 0, regCtr);
          670  +  addrRewind = sqlite3VdbeAddOp1(v, OP_Rewind, csrLead);
          671  +  sqlite3VdbeAddOp1(v, OP_Rewind, pMWin->iEphCsr);
          672  +
          673  +  if( pOrderBy ){
          674  +    int addrJump;                 /* Address of OP_Jump below */
          675  +    int iOff = pMWin->nBufferCol + (pPart ? pPart->nExpr : 0);
          676  +    int regPeer = pMWin->regPart + (pPart ? pPart->nExpr : 0);
          677  +    KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pOrderBy, 0, 0);
          678  +
          679  +    for(k=0; k<nPeer; k++){
          680  +      sqlite3VdbeAddOp3(v, OP_Column, csrLead, iOff+k, regNewPeer+k);
          681  +    }
          682  +
          683  +    addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPeer, regPeer, nPeer);
          684  +    sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
          685  +    addrJump = sqlite3VdbeAddOp3(v, OP_Jump, addr+2, 0, addr+2);
          686  +    sqlite3VdbeAddOp3(v, OP_Copy, regNewPeer, regPeer, nPeer-1);
          687  +    windowAggFinal(pParse, pMWin, 0);
          688  +    sqlite3VdbeAddOp3(v, OP_IfPos, regCtr, sqlite3VdbeCurrentAddr(v)+2 , 1);
          689  +    sqlite3VdbeAddOp2(v, OP_Goto, 0, sqlite3VdbeCurrentAddr(v)+3);
          690  +    sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrGosub);
          691  +    sqlite3VdbeAddOp2(v, OP_Next, pMWin->iEphCsr, sqlite3VdbeCurrentAddr(v)-3);
          692  +    sqlite3VdbeJumpHere(v, addrJump);
          693  +  }
          694  +
          695  +  windowAggStep(pParse, pMWin, csrLead, 0, regArg);
          696  +  sqlite3VdbeAddOp2(v, OP_AddImm, regCtr, 1);
          697  +
          698  +  sqlite3VdbeAddOp2(v, OP_Next, csrLead, addrRewind+2);
          699  +
          700  +  windowAggFinal(pParse, pMWin, 1);
          701  +
          702  +  sqlite3VdbeAddOp3(v, OP_IfPos, regCtr, sqlite3VdbeCurrentAddr(v)+2 , 1);
          703  +  sqlite3VdbeAddOp2(v, OP_Goto, 0, sqlite3VdbeCurrentAddr(v)+3);
          704  +  sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, addrGosub);
          705  +  sqlite3VdbeAddOp2(v, OP_Next, pMWin->iEphCsr, sqlite3VdbeCurrentAddr(v)-3);
          706  +
          707  +  sqlite3VdbeJumpHere(v, addrRewind);
          708  +  sqlite3VdbeJumpHere(v, addrRewind+1);
          709  +  sqlite3VdbeAddOp1(v, OP_ResetSorter, pMWin->iEphCsr);
          710  +  sqlite3VdbeAddOp1(v, OP_Return, regFlushPart);
          711  +
          712  +  /* Jump to here to skip over flush_partition */
          713  +  sqlite3VdbeJumpHere(v, addrGoto);
          714  +}
          715  +
          716  +
          717  +/*
          718  +** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
          719  +**
   556    720   **   ...
   557    721   **     if( new partition ){
   558    722   **       AggFinal (xFinalize)
   559    723   **       Gosub addrGosub
   560    724   **       ResetSorter eph-table
   561    725   **     }
   562    726   **     else if( new peer ){
................................................................................
   565    729   **       ResetSorter eph-table
   566    730   **     }
   567    731   **     AggStep
   568    732   **     Insert (record into eph-table)
   569    733   **   sqlite3WhereEnd()
   570    734   **   AggFinal (xFinalize)
   571    735   **   Gosub addrGosub
          736  +**
          737  +** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
          738  +**
          739  +**   As above, except take no action for a "new peer". Invoke
          740  +**   the sub-routine once only for each partition.
          741  +**
          742  +** RANGE BETWEEN CURRENT ROW AND CURRENT ROW
          743  +**
          744  +**   As above, except that the "new peer" condition is handled in the
          745  +**   same way as "new partition" (so there is no "else if" block).
          746  +**
          747  +** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
          748  +** 
          749  +**   As above, except assume every row is a "new peer".
   572    750   */
   573    751   static void windowCodeDefaultStep(
   574    752     Parse *pParse, 
   575    753     Select *p,
   576    754     WhereInfo *pWInfo,
   577    755     int regGosub, 
   578    756     int addrGosub
................................................................................
   738    916     WhereInfo *pWInfo,
   739    917     int regGosub, 
   740    918     int addrGosub,
   741    919     int *pbLoop
   742    920   ){
   743    921     Window *pMWin = p->pWin;
   744    922   
          923  +  *pbLoop = 0;
   745    924     if( (pMWin->eType==TK_ROWS 
   746    925      && (pMWin->eStart!=TK_UNBOUNDED||pMWin->eEnd!=TK_CURRENT||!pMWin->pOrderBy))
   747    926      || (pMWin->eStart==TK_CURRENT&&pMWin->eEnd==TK_UNBOUNDED&&pMWin->pOrderBy)
   748    927     ){
   749         -    *pbLoop = 0;
   750    928       windowCodeRowExprStep(pParse, p, pWInfo, regGosub, addrGosub);
   751    929       return;
   752    930     }
   753    931   
          932  +#if 0
          933  +  if( pMWin->eType==TK_RANGE
          934  +   && pMWin->eStart==TK_UNBOUNDED
          935  +   && pMWin->eEnd==TK_CURRENT
          936  +   && pMWin->pOrderBy
          937  +  ){
          938  +    windowCodeCacheStep(pParse, p, pWInfo, regGosub, addrGosub);
          939  +    return;
          940  +  }
          941  +#endif
          942  +
   754    943     *pbLoop = 1;
   755    944     windowCodeDefaultStep(pParse, p, pWInfo, regGosub, addrGosub);
   756    945   }
   757    946   
   758    947