/ Check-in [35af0b75]
Login
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 Unified Diffs Ignore Whitespace Patch

Changes to src/expr.c.

768
769
770
771
772
773
774

775
776
777
778
779
780
781
...
857
858
859
860
861
862
863

864
865
866
867
868
869
870
....
1175
1176
1177
1178
1179
1180
1181


















1182
1183
1184
1185
1186
1187
1188
....
1262
1263
1264
1265
1266
1267
1268

1269
1270
1271
1272
1273
1274
1275
....
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
....
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
    }
  }
  pNew = sqlite3DbMallocRawNN(db, sizeof(Expr)+nExtra);
  if( pNew ){
    memset(pNew, 0, sizeof(Expr));
    pNew->op = (u8)op;
    pNew->iAgg = -1;

    if( pToken ){
      if( nExtra==0 ){
        pNew->flags |= EP_IntValue|EP_Leaf;
        pNew->u.iValue = iValue;
      }else{
        pNew->u.zToken = (char*)&pNew[1];
        assert( pToken->z!=0 || pToken->n==0 );
................................................................................
    p = sqlite3ExprAnd(pParse->db, pLeft, pRight);
  }else{
    p = sqlite3DbMallocRawNN(pParse->db, sizeof(Expr));
    if( p ){
      memset(p, 0, sizeof(Expr));
      p->op = op & TKFLG_MASK;
      p->iAgg = -1;

    }
    sqlite3ExprAttachSubtrees(pParse->db, p, pLeft, pRight);
  }
  if( p ) {
    sqlite3ExprCheckHeight(pParse, p->nHeight);
  }
  return p;
................................................................................
    nByte = dupedExprNodeSize(p, flags);
    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
................................................................................
        pNew->pRight = p->pRight ?
                       exprDup(db, p->pRight, EXPRDUP_REDUCE, &zAlloc) : 0;
      }
      if( pzBuffer ){
        *pzBuffer = zAlloc;
      }
    }else{

      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{
          pNew->pLeft = sqlite3ExprDup(db, p->pLeft, 0);
................................................................................
  }
  return pRet;
}
#else
# define withDup(x,y) 0
#endif

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

/*
** The following group of routines make deep copies of expressions,
** expression lists, ID lists, and select statements.  The copies can
** be deleted (by being passed to their respective ...Delete() routines)
** without effecting the originals.
**
** The expression list, ID, and source lists return by sqlite3ExprListDup(),
................................................................................
    pNew->iLimit = 0;
    pNew->iOffset = 0;
    pNew->selFlags = p->selFlags & ~SF_UsesEphemeral;
    pNew->addrOpenEphm[0] = -1;
    pNew->addrOpenEphm[1] = -1;
    pNew->nSelectRow = p->nSelectRow;
    pNew->pWith = withDup(db, p->pWith);
    pNew->pWin = winDup(db, p->pWin);
    sqlite3SelectSetName(pNew, p->zSelName);
    *pp = pNew;
    pp = &pNew->pPrior;
    pNext = pNew;
  }

  return pRet;







>







 







>







 







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







 







>







 







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







 







|







768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
...
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
....
1177
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
....
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
....
1325
1326
1327
1328
1329
1330
1331


















1332
1333
1334
1335
1336
1337
1338
....
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
    }
  }
  pNew = sqlite3DbMallocRawNN(db, sizeof(Expr)+nExtra);
  if( pNew ){
    memset(pNew, 0, sizeof(Expr));
    pNew->op = (u8)op;
    pNew->iAgg = -1;
    pNew->pWin = 0;
    if( pToken ){
      if( nExtra==0 ){
        pNew->flags |= EP_IntValue|EP_Leaf;
        pNew->u.iValue = iValue;
      }else{
        pNew->u.zToken = (char*)&pNew[1];
        assert( pToken->z!=0 || pToken->n==0 );
................................................................................
    p = sqlite3ExprAnd(pParse->db, pLeft, pRight);
  }else{
    p = sqlite3DbMallocRawNN(pParse->db, sizeof(Expr));
    if( p ){
      memset(p, 0, sizeof(Expr));
      p->op = op & TKFLG_MASK;
      p->iAgg = -1;
      p->pWin = 0;
    }
    sqlite3ExprAttachSubtrees(pParse->db, p, pLeft, pRight);
  }
  if( p ) {
    sqlite3ExprCheckHeight(pParse, p->nHeight);
  }
  return p;
................................................................................
    nByte = dupedExprNodeSize(p, flags);
    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
................................................................................
        pNew->pRight = p->pRight ?
                       exprDup(db, p->pRight, EXPRDUP_REDUCE, &zAlloc) : 0;
      }
      if( pzBuffer ){
        *pzBuffer = zAlloc;
      }
    }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{
          pNew->pLeft = sqlite3ExprDup(db, p->pLeft, 0);
................................................................................
  }
  return pRet;
}
#else
# define withDup(x,y) 0
#endif



















/*
** The following group of routines make deep copies of expressions,
** expression lists, ID lists, and select statements.  The copies can
** be deleted (by being passed to their respective ...Delete() routines)
** without effecting the originals.
**
** The expression list, ID, and source lists return by sqlite3ExprListDup(),
................................................................................
    pNew->iLimit = 0;
    pNew->iOffset = 0;
    pNew->selFlags = p->selFlags & ~SF_UsesEphemeral;
    pNew->addrOpenEphm[0] = -1;
    pNew->addrOpenEphm[1] = -1;
    pNew->nSelectRow = p->nSelectRow;
    pNew->pWith = withDup(db, p->pWith);
    pNew->pWin = 0;
    sqlite3SelectSetName(pNew, p->zSelName);
    *pp = pNew;
    pp = &pNew->pPrior;
    pNext = pNew;
  }

  return pRet;

Changes to src/select.c.

5414
5415
5416
5417
5418
5419
5420











5421
5422
5423
5424
5425
5426
5427
....
5432
5433
5434
5435
5436
5437
5438
5439
5440
5441
5442
5443
5444
5445
5446
5447
5448
5449
5450
5451
5452
....
5526
5527
5528
5529
5530
5531
5532
5533
5534
5535
5536
5537
5538
5539
5540
5541
5542
....
5577
5578
5579
5580
5581
5582
5583

5584
5585
5586
5587
5588
5589
5590

static int selectWindowRewriteExprCb(Walker *pWalker, Expr *pExpr){
  struct WindowRewrite *p = pWalker->u.pRewrite;
  Parse *pParse = pWalker->pParse;
  int rc = WRC_Continue;

  switch( pExpr->op ){











    case TK_COLUMN: {
      Expr *pDup = sqlite3ExprDup(pParse->db, pExpr, 0);
      p->pSub = sqlite3ExprListAppend(pParse, p->pSub, pDup);
      if( p->pSub ){
        assert( ExprHasProperty(pExpr, EP_Static)==0 );
        ExprSetProperty(pExpr, EP_Static);
        sqlite3ExprDelete(pParse->db, pExpr);
................................................................................
        pExpr->iColumn = p->pSub->nExpr-1;
        pExpr->iTable = p->pWin->iEphCsr;
      }

      break;
    }

    case TK_FUNCTION:
      if( pExpr->pWin ){
        rc = WRC_Prune;
        pExpr->pWin->pOwner = pExpr;
      }
      break;

    default: /* no-op */
      break;
  }

  return rc;
}

................................................................................
    ExprList *pGroupBy = p->pGroupBy;
    Expr *pHaving = p->pHaving;
    ExprList *pSort = 0;

    ExprList *pSublist = 0;       /* Expression list for sub-query */
    Window *pWin = p->pWin;

    /* TODO: This is of course temporary requirements */
    assert( pWin->pNextWin==0 );

    p->pSrc = 0;
    p->pWhere = 0;
    p->pGroupBy = 0;
    p->pHaving = 0;

    pWin->regAccum = ++pParse->nMem;
    pWin->regResult = ++pParse->nMem;
................................................................................
      p->pSrc->a[0].pSelect = pSub;
      sqlite3SrcListAssignCursors(pParse, p->pSrc);
      if( selectExpandSubquery(pParse, &p->pSrc->a[0]) ){
        rc = SQLITE_NOMEM;
      }else{
        pSub->selFlags |= SF_Expanded;
      }

    }

#if SELECTTRACE_ENABLED
    if( sqlite3SelectTrace & 0x108 ){
      SELECTTRACE(0x104,pParse,p, ("after window rewrite:\n"));
      sqlite3TreeViewSelect(0, p, 0);
    }







>
>
>
>
>
>
>
>
>
>
>







 







<
<
<
<
<
<
<







 







<
<
<







 







>







5414
5415
5416
5417
5418
5419
5420
5421
5422
5423
5424
5425
5426
5427
5428
5429
5430
5431
5432
5433
5434
5435
5436
5437
5438
....
5443
5444
5445
5446
5447
5448
5449







5450
5451
5452
5453
5454
5455
5456
....
5530
5531
5532
5533
5534
5535
5536



5537
5538
5539
5540
5541
5542
5543
....
5578
5579
5580
5581
5582
5583
5584
5585
5586
5587
5588
5589
5590
5591
5592

static int selectWindowRewriteExprCb(Walker *pWalker, Expr *pExpr){
  struct WindowRewrite *p = pWalker->u.pRewrite;
  Parse *pParse = pWalker->pParse;
  int rc = WRC_Continue;

  switch( pExpr->op ){

    case TK_FUNCTION:
      if( pExpr->pWin==0 ){
        break;
      }else if( pExpr->pWin==p->pWin ){
        rc = WRC_Prune;
        pExpr->pWin->pOwner = pExpr;
        break;
      }
      /* Fall through.  */

    case TK_COLUMN: {
      Expr *pDup = sqlite3ExprDup(pParse->db, pExpr, 0);
      p->pSub = sqlite3ExprListAppend(pParse, p->pSub, pDup);
      if( p->pSub ){
        assert( ExprHasProperty(pExpr, EP_Static)==0 );
        ExprSetProperty(pExpr, EP_Static);
        sqlite3ExprDelete(pParse->db, pExpr);
................................................................................
        pExpr->iColumn = p->pSub->nExpr-1;
        pExpr->iTable = p->pWin->iEphCsr;
      }

      break;
    }








    default: /* no-op */
      break;
  }

  return rc;
}

................................................................................
    ExprList *pGroupBy = p->pGroupBy;
    Expr *pHaving = p->pHaving;
    ExprList *pSort = 0;

    ExprList *pSublist = 0;       /* Expression list for sub-query */
    Window *pWin = p->pWin;




    p->pSrc = 0;
    p->pWhere = 0;
    p->pGroupBy = 0;
    p->pHaving = 0;

    pWin->regAccum = ++pParse->nMem;
    pWin->regResult = ++pParse->nMem;
................................................................................
      p->pSrc->a[0].pSelect = pSub;
      sqlite3SrcListAssignCursors(pParse, p->pSrc);
      if( selectExpandSubquery(pParse, &p->pSrc->a[0]) ){
        rc = SQLITE_NOMEM;
      }else{
        pSub->selFlags |= SF_Expanded;
      }
      pWin->pNextWin = 0;
    }

#if SELECTTRACE_ENABLED
    if( sqlite3SelectTrace & 0x108 ){
      SELECTTRACE(0x104,pParse,p, ("after window rewrite:\n"));
      sqlite3TreeViewSelect(0, p, 0);
    }

Changes to test/window1.test.

104
105
106
107
108
109
110
111



























112
}

do_execsql_test 4.5 {
  SELECT a, sum(a) OVER (PARTITION BY b ORDER BY a) FROM t2 ORDER BY a
} {
  0 0  1 1  2 2  3 4  4 6  5 9  6 12
}




























finish_test








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

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
}

do_execsql_test 4.5 {
  SELECT a, sum(a) OVER (PARTITION BY b ORDER BY a) FROM t2 ORDER BY a
} {
  0 0  1 1  2 2  3 4  4 6  5 9  6 12
}

do_execsql_test 4.6 {
  SELECT a, sum(a) OVER (PARTITION BY c ORDER BY a) FROM t2 ORDER BY a
} {
  0 0  1 1  2 2  3 3  4 5  5 7  6 9
}

do_execsql_test 4.7 {
  SELECT a, sum(a) OVER (PARTITION BY b ORDER BY a DESC) FROM t2 ORDER BY a
} {
  0 12  1 9  2 12  3 8  4 10  5 5  6 6
}

do_execsql_test 4.8 {
  SELECT a, 
    sum(a) OVER (PARTITION BY b ORDER BY a DESC),
    sum(a) OVER (PARTITION BY c ORDER BY a) 
  FROM t2 ORDER BY a
} {
  0  12  0
  1   9  1 
  2  12  2 
  3   8  3 
  4  10  5 
  5   5  7 
  6   6  9
}

finish_test