/ Check-in [35af0b75]
Login

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

Overview
Comment:Handle multiple window-functions in a single query.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | exp-window-functions
Files: files | file ages | folders
SHA3-256:35af0b750e70dcf0f343b115f4bbd0860a7e8064be204d4dfba1a43c22ff07b1
User & Date: dan 2018-05-17 14:26:27
Context
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: c9f0f140 user: dan tags: exp-window-functions
14:26
Handle multiple window-functions in a single query. check-in: 35af0b75 user: dan tags: exp-window-functions
2018-05-16
20:58
Start of experimental implementation of SQL window functions. Does not yet work. check-in: 3781e520 user: dan tags: exp-window-functions
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/expr.c.

   768    768       }
   769    769     }
   770    770     pNew = sqlite3DbMallocRawNN(db, sizeof(Expr)+nExtra);
   771    771     if( pNew ){
   772    772       memset(pNew, 0, sizeof(Expr));
   773    773       pNew->op = (u8)op;
   774    774       pNew->iAgg = -1;
          775  +    pNew->pWin = 0;
   775    776       if( pToken ){
   776    777         if( nExtra==0 ){
   777    778           pNew->flags |= EP_IntValue|EP_Leaf;
   778    779           pNew->u.iValue = iValue;
   779    780         }else{
   780    781           pNew->u.zToken = (char*)&pNew[1];
   781    782           assert( pToken->z!=0 || pToken->n==0 );
................................................................................
   857    858       p = sqlite3ExprAnd(pParse->db, pLeft, pRight);
   858    859     }else{
   859    860       p = sqlite3DbMallocRawNN(pParse->db, sizeof(Expr));
   860    861       if( p ){
   861    862         memset(p, 0, sizeof(Expr));
   862    863         p->op = op & TKFLG_MASK;
   863    864         p->iAgg = -1;
          865  +      p->pWin = 0;
   864    866       }
   865    867       sqlite3ExprAttachSubtrees(pParse->db, p, pLeft, pRight);
   866    868     }
   867    869     if( p ) {
   868    870       sqlite3ExprCheckHeight(pParse, p->nHeight);
   869    871     }
   870    872     return p;
................................................................................
  1175   1177       nByte = dupedExprNodeSize(p, flags);
  1176   1178       if( flags&EXPRDUP_REDUCE ){
  1177   1179         nByte += dupedExprSize(p->pLeft, flags) + dupedExprSize(p->pRight, flags);
  1178   1180       }
  1179   1181     }
  1180   1182     return nByte;
  1181   1183   }
         1184  +
         1185  +static Window *winDup(sqlite3 *db, Window *p){
         1186  +  Window *pNew = 0;
         1187  +  if( p ){
         1188  +    pNew = sqlite3DbMallocZero(db, sizeof(Window));
         1189  +    if( pNew ){
         1190  +      pNew->pFilter = sqlite3ExprDup(db, p->pFilter, 0);
         1191  +      pNew->pPartition = sqlite3ExprListDup(db, p->pPartition, 0);
         1192  +      pNew->pOrderBy = sqlite3ExprListDup(db, p->pOrderBy, 0);
         1193  +      pNew->eType = p->eType;
         1194  +      pNew->eEnd = p->eEnd;
         1195  +      pNew->eStart = p->eStart;
         1196  +      pNew->pStart = sqlite3ExprDup(db, pNew->pStart, 0);
         1197  +      pNew->pEnd = sqlite3ExprDup(db, pNew->pEnd, 0);
         1198  +    }
         1199  +  }
         1200  +  return pNew;
         1201  +}
  1182   1202   
  1183   1203   /*
  1184   1204   ** This function is similar to sqlite3ExprDup(), except that if pzBuffer 
  1185   1205   ** is not NULL then *pzBuffer is assumed to point to a buffer large enough 
  1186   1206   ** to store the copy of expression p, the copies of p->u.zToken
  1187   1207   ** (if applicable), and the copies of the p->pLeft and p->pRight expressions,
  1188   1208   ** if any. Before returning, *pzBuffer is set to the first byte past the
................................................................................
  1262   1282           pNew->pRight = p->pRight ?
  1263   1283                          exprDup(db, p->pRight, EXPRDUP_REDUCE, &zAlloc) : 0;
  1264   1284         }
  1265   1285         if( pzBuffer ){
  1266   1286           *pzBuffer = zAlloc;
  1267   1287         }
  1268   1288       }else{
         1289  +      pNew->pWin = winDup(db, p->pWin);
  1269   1290         if( !ExprHasProperty(p, EP_TokenOnly|EP_Leaf) ){
  1270   1291           if( pNew->op==TK_SELECT_COLUMN ){
  1271   1292             pNew->pLeft = p->pLeft;
  1272   1293             assert( p->iColumn==0 || p->pRight==0 );
  1273   1294             assert( p->pRight==0  || p->pRight==p->pLeft );
  1274   1295           }else{
  1275   1296             pNew->pLeft = sqlite3ExprDup(db, p->pLeft, 0);
................................................................................
  1304   1325     }
  1305   1326     return pRet;
  1306   1327   }
  1307   1328   #else
  1308   1329   # define withDup(x,y) 0
  1309   1330   #endif
  1310   1331   
  1311         -static Window *winDup(sqlite3 *db, Window *p){
  1312         -  Window *pNew = 0;
  1313         -  if( p ){
  1314         -    pNew = sqlite3DbMallocZero(db, sizeof(Window));
  1315         -    if( pNew ){
  1316         -      pNew->pFilter = sqlite3ExprDup(db, p->pFilter, 0);
  1317         -      pNew->pPartition = sqlite3ExprListDup(db, p->pPartition, 0);
  1318         -      pNew->pOrderBy = sqlite3ExprListDup(db, p->pOrderBy, 0);
  1319         -      pNew->eType = p->eType;
  1320         -      pNew->eEnd = p->eEnd;
  1321         -      pNew->eStart = p->eStart;
  1322         -      pNew->pStart = sqlite3ExprDup(db, pNew->pStart, 0);
  1323         -      pNew->pEnd = sqlite3ExprDup(db, pNew->pEnd, 0);
  1324         -    }
  1325         -  }
  1326         -  return pNew;
  1327         -}
  1328         -
  1329   1332   /*
  1330   1333   ** The following group of routines make deep copies of expressions,
  1331   1334   ** expression lists, ID lists, and select statements.  The copies can
  1332   1335   ** be deleted (by being passed to their respective ...Delete() routines)
  1333   1336   ** without effecting the originals.
  1334   1337   **
  1335   1338   ** The expression list, ID, and source lists return by sqlite3ExprListDup(),
................................................................................
  1486   1489       pNew->iLimit = 0;
  1487   1490       pNew->iOffset = 0;
  1488   1491       pNew->selFlags = p->selFlags & ~SF_UsesEphemeral;
  1489   1492       pNew->addrOpenEphm[0] = -1;
  1490   1493       pNew->addrOpenEphm[1] = -1;
  1491   1494       pNew->nSelectRow = p->nSelectRow;
  1492   1495       pNew->pWith = withDup(db, p->pWith);
  1493         -    pNew->pWin = winDup(db, p->pWin);
         1496  +    pNew->pWin = 0;
  1494   1497       sqlite3SelectSetName(pNew, p->zSelName);
  1495   1498       *pp = pNew;
  1496   1499       pp = &pNew->pPrior;
  1497   1500       pNext = pNew;
  1498   1501     }
  1499   1502   
  1500   1503     return pRet;

Changes to src/select.c.

  5414   5414   
  5415   5415   static int selectWindowRewriteExprCb(Walker *pWalker, Expr *pExpr){
  5416   5416     struct WindowRewrite *p = pWalker->u.pRewrite;
  5417   5417     Parse *pParse = pWalker->pParse;
  5418   5418     int rc = WRC_Continue;
  5419   5419   
  5420   5420     switch( pExpr->op ){
         5421  +
         5422  +    case TK_FUNCTION:
         5423  +      if( pExpr->pWin==0 ){
         5424  +        break;
         5425  +      }else if( pExpr->pWin==p->pWin ){
         5426  +        rc = WRC_Prune;
         5427  +        pExpr->pWin->pOwner = pExpr;
         5428  +        break;
         5429  +      }
         5430  +      /* Fall through.  */
         5431  +
  5421   5432       case TK_COLUMN: {
  5422   5433         Expr *pDup = sqlite3ExprDup(pParse->db, pExpr, 0);
  5423   5434         p->pSub = sqlite3ExprListAppend(pParse, p->pSub, pDup);
  5424   5435         if( p->pSub ){
  5425   5436           assert( ExprHasProperty(pExpr, EP_Static)==0 );
  5426   5437           ExprSetProperty(pExpr, EP_Static);
  5427   5438           sqlite3ExprDelete(pParse->db, pExpr);
................................................................................
  5432   5443           pExpr->iColumn = p->pSub->nExpr-1;
  5433   5444           pExpr->iTable = p->pWin->iEphCsr;
  5434   5445         }
  5435   5446   
  5436   5447         break;
  5437   5448       }
  5438   5449   
  5439         -    case TK_FUNCTION:
  5440         -      if( pExpr->pWin ){
  5441         -        rc = WRC_Prune;
  5442         -        pExpr->pWin->pOwner = pExpr;
  5443         -      }
  5444         -      break;
  5445         -
  5446   5450       default: /* no-op */
  5447   5451         break;
  5448   5452     }
  5449   5453   
  5450   5454     return rc;
  5451   5455   }
  5452   5456   
................................................................................
  5526   5530       ExprList *pGroupBy = p->pGroupBy;
  5527   5531       Expr *pHaving = p->pHaving;
  5528   5532       ExprList *pSort = 0;
  5529   5533   
  5530   5534       ExprList *pSublist = 0;       /* Expression list for sub-query */
  5531   5535       Window *pWin = p->pWin;
  5532   5536   
  5533         -    /* TODO: This is of course temporary requirements */
  5534         -    assert( pWin->pNextWin==0 );
  5535         -
  5536   5537       p->pSrc = 0;
  5537   5538       p->pWhere = 0;
  5538   5539       p->pGroupBy = 0;
  5539   5540       p->pHaving = 0;
  5540   5541   
  5541   5542       pWin->regAccum = ++pParse->nMem;
  5542   5543       pWin->regResult = ++pParse->nMem;
................................................................................
  5577   5578         p->pSrc->a[0].pSelect = pSub;
  5578   5579         sqlite3SrcListAssignCursors(pParse, p->pSrc);
  5579   5580         if( selectExpandSubquery(pParse, &p->pSrc->a[0]) ){
  5580   5581           rc = SQLITE_NOMEM;
  5581   5582         }else{
  5582   5583           pSub->selFlags |= SF_Expanded;
  5583   5584         }
         5585  +      pWin->pNextWin = 0;
  5584   5586       }
  5585   5587   
  5586   5588   #if SELECTTRACE_ENABLED
  5587   5589       if( sqlite3SelectTrace & 0x108 ){
  5588   5590         SELECTTRACE(0x104,pParse,p, ("after window rewrite:\n"));
  5589   5591         sqlite3TreeViewSelect(0, p, 0);
  5590   5592       }

Changes to test/window1.test.

   104    104   }
   105    105   
   106    106   do_execsql_test 4.5 {
   107    107     SELECT a, sum(a) OVER (PARTITION BY b ORDER BY a) FROM t2 ORDER BY a
   108    108   } {
   109    109     0 0  1 1  2 2  3 4  4 6  5 9  6 12
   110    110   }
          111  +
          112  +do_execsql_test 4.6 {
          113  +  SELECT a, sum(a) OVER (PARTITION BY c ORDER BY a) FROM t2 ORDER BY a
          114  +} {
          115  +  0 0  1 1  2 2  3 3  4 5  5 7  6 9
          116  +}
          117  +
          118  +do_execsql_test 4.7 {
          119  +  SELECT a, sum(a) OVER (PARTITION BY b ORDER BY a DESC) FROM t2 ORDER BY a
          120  +} {
          121  +  0 12  1 9  2 12  3 8  4 10  5 5  6 6
          122  +}
          123  +
          124  +do_execsql_test 4.8 {
          125  +  SELECT a, 
          126  +    sum(a) OVER (PARTITION BY b ORDER BY a DESC),
          127  +    sum(a) OVER (PARTITION BY c ORDER BY a) 
          128  +  FROM t2 ORDER BY a
          129  +} {
          130  +  0  12  0
          131  +  1   9  1 
          132  +  2  12  2 
          133  +  3   8  3 
          134  +  4  10  5 
          135  +  5   5  7 
          136  +  6   6  9
          137  +}
   111    138   
   112    139   finish_test