Start of experimental implementation of SQL window functions. Does not yet
work.
FossilOrigin-Name: 3781e520854808fe02ad3fe77dd11fc917448c58ff1fd79123289dd91937decd
diff --git a/src/analyze.c b/src/analyze.c
index 48fd495..9492e2c 100644
--- a/src/analyze.c
+++ b/src/analyze.c
@@ -485,6 +485,7 @@
0, /* pNext */
statInit, /* xSFunc */
0, /* xFinalize */
+ 0, 0,
"stat_init", /* zName */
{0}
};
@@ -801,6 +802,7 @@
0, /* pNext */
statPush, /* xSFunc */
0, /* xFinalize */
+ 0, 0,
"stat_push", /* zName */
{0}
};
@@ -952,6 +954,7 @@
0, /* pNext */
statGet, /* xSFunc */
0, /* xFinalize */
+ 0, 0,
"stat_get", /* zName */
{0}
};
diff --git a/src/attach.c b/src/attach.c
index ca0fd9f..1f27615 100644
--- a/src/attach.c
+++ b/src/attach.c
@@ -414,6 +414,7 @@
0, /* pNext */
detachFunc, /* xSFunc */
0, /* xFinalize */
+ 0, 0,
"sqlite_detach", /* zName */
{0}
};
@@ -433,6 +434,7 @@
0, /* pNext */
attachFunc, /* xSFunc */
0, /* xFinalize */
+ 0, 0,
"sqlite_attach", /* zName */
{0}
};
diff --git a/src/expr.c b/src/expr.c
index 6aff83a..a1407a8 100644
--- a/src/expr.c
+++ b/src/expr.c
@@ -1063,6 +1063,9 @@
}else{
sqlite3ExprListDelete(db, p->x.pList);
}
+ if( !ExprHasProperty(p, EP_Reduced) ){
+ sqlite3WindowDelete(db, p->pWin);
+ }
}
if( ExprHasProperty(p, EP_MemToken) ) sqlite3DbFree(db, p->u.zToken);
if( !ExprHasProperty(p, EP_Static) ){
@@ -1305,6 +1308,24 @@
# 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
@@ -1469,6 +1490,7 @@
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;
@@ -3778,6 +3800,10 @@
u8 enc = ENC(db); /* The text encoding used by this database */
CollSeq *pColl = 0; /* A collating sequence */
+ if( !ExprHasProperty(pExpr, EP_TokenOnly|EP_Reduced) && pExpr->pWin ){
+ return pExpr->pWin->regResult;
+ }
+
if( ConstFactorOk(pParse) && sqlite3ExprIsConstantNotJoin(pExpr) ){
/* SQL functions can be expensive. So try to move constant functions
** out of the inner loop, even if that means an extra OP_Copy. */
@@ -3798,7 +3824,7 @@
pDef = sqlite3FindFunction(db, "unknown", nFarg, enc, 0);
}
#endif
- if( pDef==0 || pDef->xFinalize!=0 ){
+ if( pDef==0 /* || pDef->xFinalize!=0 */ ){
sqlite3ErrorMsg(pParse, "unknown function: %s()", zId);
break;
}
diff --git a/src/func.c b/src/func.c
index 17a267e..f5a839d 100644
--- a/src/func.c
+++ b/src/func.c
@@ -1859,7 +1859,7 @@
FUNCTION(zeroblob, 1, 0, 0, zeroblobFunc ),
FUNCTION(substr, 2, 0, 0, substrFunc ),
FUNCTION(substr, 3, 0, 0, substrFunc ),
- AGGREGATE(sum, 1, 0, 0, sumStep, sumFinalize ),
+ WFUNCTION(sum, 1, 0, sumStep, sumFinalize, sumFinalize, 0),
AGGREGATE(total, 1, 0, 0, sumStep, totalFinalize ),
AGGREGATE(avg, 1, 0, 0, sumStep, avgFinalize ),
AGGREGATE2(count, 0, 0, 0, countStep, countFinalize,
diff --git a/src/parse.y b/src/parse.y
index aca3bfb..1d1a2dd 100644
--- a/src/parse.y
+++ b/src/parse.y
@@ -99,6 +99,8 @@
*/
struct TrigEvent { int a; IdList * b; };
+struct FrameBound { int eType; Expr *pExpr; };
+
/*
** Disable lookaside memory allocation for objects that might be
** shared across database connections.
@@ -209,7 +211,7 @@
CONFLICT DATABASE DEFERRED DESC DETACH DO
EACH END EXCLUSIVE EXPLAIN FAIL FOR
IGNORE IMMEDIATE INITIALLY INSTEAD LIKE_KW MATCH NO PLAN
- QUERY KEY OF OFFSET PRAGMA RAISE RECURSIVE RELEASE REPLACE RESTRICT ROW
+ QUERY KEY OF OFFSET PRAGMA RAISE RECURSIVE RELEASE REPLACE RESTRICT ROW ROWS
ROLLBACK SAVEPOINT TEMP TRIGGER VACUUM VIEW VIRTUAL WITH WITHOUT
%ifdef SQLITE_OMIT_COMPOUND_SELECT
EXCEPT INTERSECT UNION
@@ -1001,11 +1003,12 @@
sqlite3ExprAttachSubtrees(pParse->db, A, E, 0);
}
%endif SQLITE_OMIT_CAST
-expr(A) ::= id(X) LP distinct(D) exprlist(Y) RP. {
+expr(A) ::= id(X) LP distinct(D) exprlist(Y) RP window(Z). {
if( Y && Y->nExpr>pParse->db->aLimit[SQLITE_LIMIT_FUNCTION_ARG] ){
sqlite3ErrorMsg(pParse, "too many arguments on function %T", &X);
}
A = sqlite3ExprFunction(pParse, Y, &X);
+ sqlite3WindowAttach(pParse, A, Z);
if( D==SF_Distinct && A ){
A->flags |= EP_Distinct;
}
@@ -1017,6 +1020,59 @@
A = sqlite3ExprFunction(pParse, 0, &OP);
}
+
+%type window {Window*}
+%destructor window {sqlite3WindowDelete(pParse->db, $$);}
+
+%type frame_opt {Window*}
+%destructor frame_opt {sqlite3WindowDelete(pParse->db, $$);}
+
+%type part_opt {ExprList*}
+%destructor part_opt {sqlite3ExprListDelete(pParse->db, $$);}
+
+%type filter_opt {Expr*}
+%destructor filter_opt {sqlite3ExprDelete(pParse->db, $$);}
+
+%type range_or_rows {int}
+
+%type frame_bound {struct FrameBound}
+%destructor frame_bound {sqlite3ExprDelete(pParse->db, $$.pExpr);}
+
+window(A) ::= . { A = 0; }
+window(A) ::= filter_opt(W) OVER LP part_opt(X) orderby_opt(Y) frame_opt(Z) RP.{
+ if( Z ){
+ A = Z;
+ A->pFilter = W;
+ A->pPartition = X;
+ A->pOrderBy = Y;
+ }
+}
+
+part_opt(A) ::= PARTITION BY exprlist(X). { A = X; }
+part_opt(A) ::= . { A = 0; }
+filter_opt(A) ::= . { A = 0; }
+filter_opt(A) ::= FILTER LP WHERE expr(X) RP. { A = X; }
+
+frame_opt(A) ::= . {
+ A = sqlite3WindowAlloc(pParse, TK_RANGE, TK_UNBOUNDED, 0, TK_CURRENT, 0);
+}
+frame_opt(A) ::= range_or_rows(X) frame_bound(Y). {
+ A = sqlite3WindowAlloc(pParse, X, Y.eType, Y.pExpr, TK_CURRENT, 0);
+}
+frame_opt(A) ::= range_or_rows(X) BETWEEN frame_bound(Y) AND frame_bound(Z). {
+ A = sqlite3WindowAlloc(pParse, X, Y.eType, Y.pExpr, Z.eType, Z.pExpr);
+}
+
+range_or_rows(A) ::= RANGE. { A = TK_RANGE; }
+range_or_rows(A) ::= ROWS. { A = TK_ROWS; }
+
+frame_bound(A) ::= UNBOUNDED PRECEDING. { A.eType = TK_UNBOUNDED; A.pExpr = 0; }
+frame_bound(A) ::= expr(X) PRECEDING. { A.eType = TK_PRECEDING; A.pExpr = X; }
+frame_bound(A) ::= CURRENT ROW. { A.eType = TK_CURRENT ; A.pExpr = 0; }
+frame_bound(A) ::= expr(X) FOLLOWING. { A.eType = TK_FOLLOWING; A.pExpr = X; }
+frame_bound(A) ::= UNBOUNDED FOLLOWING. { A.eType = TK_UNBOUNDED; A.pExpr = 0; }
+
+
expr(A) ::= LP nexprlist(X) COMMA expr(Y) RP. {
ExprList *pList = sqlite3ExprListAppend(pParse, X, Y);
A = sqlite3PExpr(pParse, TK_VECTOR, 0, 0);
diff --git a/src/resolve.c b/src/resolve.c
index 4ed36a4..073fdf1 100644
--- a/src/resolve.c
+++ b/src/resolve.c
@@ -753,8 +753,11 @@
NC_IdxExpr|NC_PartIdx);
}
}
- if( is_agg && (pNC->ncFlags & NC_AllowAgg)==0 ){
- sqlite3ErrorMsg(pParse, "misuse of aggregate function %.*s()", nId,zId);
+ if( (is_agg && (pNC->ncFlags & NC_AllowAgg)==0)
+ || (pExpr->pWin && (pNC->ncFlags & NC_AllowWin)==0)
+ ){
+ const char *zType = pExpr->pWin ? "window" : "aggregate";
+ sqlite3ErrorMsg(pParse, "misuse of %s function %.*s()",zType,nId,zId);
pNC->nErr++;
is_agg = 0;
}else if( no_such_func && pParse->db->init.busy==0
@@ -772,19 +775,28 @@
if( is_agg ) pNC->ncFlags &= ~NC_AllowAgg;
sqlite3WalkExprList(pWalker, pList);
if( is_agg ){
- NameContext *pNC2 = pNC;
- pExpr->op = TK_AGG_FUNCTION;
- pExpr->op2 = 0;
- while( pNC2 && !sqlite3FunctionUsesThisSrc(pExpr, pNC2->pSrcList) ){
- pExpr->op2++;
- pNC2 = pNC2->pNext;
+ if( pExpr->pWin ){
+ pExpr->pWin->pNextWin = pNC->pWin;
+ pNC->pWin = pExpr->pWin;
+ pExpr->pWin->pFunc = pDef;
+ pExpr->pWin->nArg = pExpr->x.pList->nExpr;
}
- assert( pDef!=0 );
- if( pNC2 ){
- assert( SQLITE_FUNC_MINMAX==NC_MinMaxAgg );
- testcase( (pDef->funcFlags & SQLITE_FUNC_MINMAX)!=0 );
- pNC2->ncFlags |= NC_HasAgg | (pDef->funcFlags & SQLITE_FUNC_MINMAX);
+ else
+ {
+ NameContext *pNC2 = pNC;
+ pExpr->op = TK_AGG_FUNCTION;
+ pExpr->op2 = 0;
+ while( pNC2 && !sqlite3FunctionUsesThisSrc(pExpr, pNC2->pSrcList) ){
+ pExpr->op2++;
+ pNC2 = pNC2->pNext;
+ }
+ assert( pDef!=0 );
+ if( pNC2 ){
+ assert( SQLITE_FUNC_MINMAX==NC_MinMaxAgg );
+ testcase( (pDef->funcFlags & SQLITE_FUNC_MINMAX)!=0 );
+ pNC2->ncFlags |= NC_HasAgg | (pDef->funcFlags & SQLITE_FUNC_MINMAX);
+ }
}
pNC->ncFlags |= NC_AllowAgg;
}
@@ -1234,6 +1246,7 @@
nCompound = 0;
pLeftmost = p;
while( p ){
+ assert( p->pWin==0 );
assert( (p->selFlags & SF_Expanded)!=0 );
assert( (p->selFlags & SF_Resolved)==0 );
p->selFlags |= SF_Resolved;
@@ -1291,12 +1304,13 @@
/* Set up the local name-context to pass to sqlite3ResolveExprNames() to
** resolve the result-set expression list.
*/
- sNC.ncFlags = NC_AllowAgg;
+ sNC.ncFlags = NC_AllowAgg|NC_AllowWin;
sNC.pSrcList = p->pSrc;
sNC.pNext = pOuterNC;
/* Resolve names in the result set. */
if( sqlite3ResolveExprListNames(&sNC, p->pEList) ) return WRC_Abort;
+ sNC.ncFlags &= ~NC_AllowWin;
/* If there are no aggregate functions in the result-set, and no GROUP BY
** expression, do not allow aggregates in any of the other expressions.
@@ -1345,7 +1359,7 @@
** outer queries
*/
sNC.pNext = 0;
- sNC.ncFlags |= NC_AllowAgg;
+ sNC.ncFlags |= NC_AllowAgg|NC_AllowWin;
/* If this is a converted compound query, move the ORDER BY clause from
** the sub-query back to the parent query. At this point each term
@@ -1376,6 +1390,7 @@
if( db->mallocFailed ){
return WRC_Abort;
}
+ sNC.ncFlags &= ~NC_AllowWin;
/* Resolve the GROUP BY clause. At the same time, make sure
** the GROUP BY clause does not contain aggregate functions.
@@ -1402,6 +1417,9 @@
return WRC_Abort;
}
+ p->pWin = sNC.pWin;
+ sNC.pWin = 0;
+
/* Advance to the next term of the compound
*/
p = p->pPrior;
diff --git a/src/select.c b/src/select.c
index 3818ef5..2b5a3dc 100644
--- a/src/select.c
+++ b/src/select.c
@@ -162,6 +162,7 @@
pNew->pNext = 0;
pNew->pLimit = pLimit;
pNew->pWith = 0;
+ pNew->pWin = 0;
if( pParse->db->mallocFailed ) {
clearSelect(pParse->db, pNew, pNew!=&standin);
pNew = 0;
@@ -3719,6 +3720,8 @@
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,
@@ -4588,6 +4591,27 @@
#define selectPopWith 0
#endif
+static int selectExpandSubquery(Parse *pParse, struct SrcList_item *pFrom){
+ Select *pSel = pFrom->pSelect;
+ Table *pTab;
+
+ pFrom->pTab = pTab = sqlite3DbMallocZero(pParse->db, sizeof(Table));
+ if( pTab==0 ) return WRC_Abort;
+ pTab->nTabRef = 1;
+ if( pFrom->zAlias ){
+ pTab->zName = sqlite3DbStrDup(pParse->db, pFrom->zAlias);
+ }else{
+ pTab->zName = sqlite3MPrintf(pParse->db, "subquery_%p", (void*)pTab);
+ }
+ while( pSel->pPrior ){ pSel = pSel->pPrior; }
+ sqlite3ColumnsFromExprList(pParse, pSel->pEList,&pTab->nCol,&pTab->aCol);
+ pTab->iPKey = -1;
+ pTab->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) );
+ pTab->tabFlags |= TF_Ephemeral;
+
+ return WRC_Continue;
+}
+
/*
** This routine is a Walker callback for "expanding" a SELECT statement.
** "Expanding" means to do the following:
@@ -4660,6 +4684,8 @@
assert( pSel!=0 );
assert( pFrom->pTab==0 );
if( sqlite3WalkSelect(pWalker, pSel) ) return WRC_Abort;
+ if( selectExpandSubquery(pParse, pFrom) ) return WRC_Abort;
+#if 0
pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table));
if( pTab==0 ) return WRC_Abort;
pTab->nTabRef = 1;
@@ -4674,6 +4700,7 @@
pTab->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) );
pTab->tabFlags |= TF_Ephemeral;
#endif
+#endif
}else{
/* An ordinary table or view name in the FROM clause */
assert( pFrom->pTab==0 );
@@ -5375,6 +5402,201 @@
}
#endif /* SQLITE_COUNTOFVIEW_OPTIMIZATION */
+typedef struct WindowRewrite WindowRewrite;
+struct WindowRewrite {
+ Window *pWin;
+ ExprList *pSub;
+};
+
+static int selectWindowRewriteSelectCb(Walker *pWalker, Select *pSelect){
+ return WRC_Prune;
+}
+
+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);
+ ExprClearProperty(pExpr, EP_Static);
+ memset(pExpr, 0, sizeof(Expr));
+
+ pExpr->op = TK_COLUMN;
+ 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;
+}
+
+static int selectWindowRewriteEList(
+ Parse *pParse,
+ Window *pWin,
+ ExprList *pEList, /* Rewrite expressions in this list */
+ ExprList **ppSub /* IN/OUT: Sub-select expression-list */
+){
+ Walker sWalker;
+ WindowRewrite sRewrite;
+ int rc;
+
+ memset(&sWalker, 0, sizeof(Walker));
+ memset(&sRewrite, 0, sizeof(WindowRewrite));
+
+ sRewrite.pSub = *ppSub;
+ sRewrite.pWin = pWin;
+
+ sWalker.pParse = pParse;
+ sWalker.xExprCallback = selectWindowRewriteExprCb;
+ sWalker.xSelectCallback = selectWindowRewriteSelectCb;
+ sWalker.u.pRewrite = &sRewrite;
+
+ rc = sqlite3WalkExprList(&sWalker, pEList);
+
+ *ppSub = sRewrite.pSub;
+ return rc;
+}
+
+static ExprList *exprListAppendList(
+ Parse *pParse, /* Parsing context */
+ ExprList *pList, /* List to which to append. Might be NULL */
+ ExprList *pAppend /* List of values to append. Might be NULL */
+){
+ if( pAppend ){
+ int i;
+ int nInit = pList ? pList->nExpr : 0;
+ for(i=0; i<pAppend->nExpr; i++){
+ Expr *pDup = sqlite3ExprDup(pParse->db, pAppend->a[i].pExpr, 0);
+ pList = sqlite3ExprListAppend(pParse, pList, pDup);
+ if( pList ) pList->a[nInit+i].sortOrder = pAppend->a[i].sortOrder;
+ }
+ }
+ return pList;
+}
+
+/*
+** If the SELECT statement passed as the second argument does not invoke
+** any SQL window functions, this function is a no-op. Otherwise, it
+** rewrites the SELECT statement so that window function xStep functions
+** are invoked in the correct order. The simplest version of the
+** transformation is:
+**
+** SELECT win(args...) OVER (<list1>) FROM <src> ORDER BY <list2>
+**
+** to
+**
+** SELECT win(args...) FROM (
+** SELECT args... FROM <src> ORDER BY <list1>
+** ) ORDER BY <list2>
+**
+** where <src> may contain WHERE, GROUP BY and HAVING clauses, and <list1>
+** is the concatenation of the PARTITION BY and ORDER BY clauses in the
+** OVER clause.
+**
+*/
+static int selectWindowRewrite(Parse *pParse, Select *p){
+ int rc = SQLITE_OK;
+ if( p->pWin ){
+ Vdbe *v = sqlite3GetVdbe(pParse);
+ int i;
+ sqlite3 *db = pParse->db;
+ Select *pSub = 0; /* The subquery */
+ SrcList *pSrc = p->pSrc;
+ Expr *pWhere = p->pWhere;
+ 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;
+
+ /* Assign a cursor number for the ephemeral table used to buffer rows.
+ ** The OpenEphemeral instruction is coded later, after it is known how
+ ** many columns the table will have. */
+ pWin->iEphCsr = pParse->nTab++;
+
+ rc = selectWindowRewriteEList(pParse, pWin, p->pEList, &pSublist);
+ if( rc ) return rc;
+ rc = selectWindowRewriteEList(pParse, pWin, p->pOrderBy, &pSublist);
+ if( rc ) return rc;
+ pWin->nBufferCol = (pSublist ? pSublist->nExpr : 0);
+
+ /* Create the ORDER BY clause for the sub-select. This is the concatenation
+ ** of the window PARTITION and ORDER BY clauses. Append the same
+ ** expressions to the sub-select expression list. They are required to
+ ** figure out where boundaries for partitions and sets of peer rows. */
+ pSort = sqlite3ExprListDup(db, pWin->pPartition, 0);
+ if( pWin->pOrderBy ){
+ pSort = exprListAppendList(pParse, pSort, pWin->pOrderBy);
+ }
+ pSublist = exprListAppendList(pParse, pSublist, pSort);
+
+ /* Also append the arguments passed to the window function to the
+ ** sub-select expression list. */
+ pWin->iArgCol = (pSublist ? pSublist->nExpr : 0);
+ pSublist = exprListAppendList(pParse, pSublist, pWin->pOwner->x.pList);
+
+ pSub = sqlite3SelectNew(
+ pParse, pSublist, pSrc, pWhere, pGroupBy, pHaving, pSort, 0, 0
+ );
+ p->pSrc = sqlite3SrcListAppend(db, 0, 0, 0);
+ if( p->pSrc ){
+ int iTab;
+ ExprList *pList = 0;
+ 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);
+ }
+#endif
+
+ sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pWin->iEphCsr, pWin->nBufferCol);
+ sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);
+ }
+
+ return rc;
+}
+
/*
** Generate code for the SELECT statement given in the p argument.
**
@@ -5443,7 +5665,6 @@
sqlite3SelectPrep(pParse, p, 0);
memset(&sSort, 0, sizeof(sSort));
sSort.pOrderBy = p->pOrderBy;
- pTabList = p->pSrc;
if( pParse->nErr || db->mallocFailed ){
goto select_end;
}
@@ -5460,6 +5681,11 @@
generateColumnNames(pParse, p);
}
+ if( (rc = selectWindowRewrite(pParse, p)) ){
+ goto select_end;
+ }
+ pTabList = p->pSrc;
+
/* Try to various optimizations (flattening subqueries, and strength
** reduction of join operators) in the FROM clause up into the main query
*/
@@ -5833,11 +6059,24 @@
}
if( !isAgg && pGroupBy==0 ){
+ Window *pWin = p->pWin;
+ int regPart = 0;
+
/* No aggregate functions and no GROUP BY clause */
u16 wctrlFlags = (sDistinct.isTnct ? WHERE_WANT_DISTINCT : 0);
assert( WHERE_USE_LIMIT==SF_FixedLimit );
wctrlFlags |= p->selFlags & SF_FixedLimit;
+ if( pWin ){
+ int nPart = (pWin->pPartition ? pWin->pPartition->nExpr : 0);
+ nPart += (pWin->pOrderBy ? pWin->pOrderBy->nExpr : 0);
+ if( nPart ){
+ regPart = pParse->nMem+1;
+ pParse->nMem += nPart;
+ sqlite3VdbeAddOp3(v, OP_Null, 0, regPart, regPart+nPart-1);
+ }
+ }
+
/* Begin the database scan. */
SELECTTRACE(1,pParse,p,("WhereBegin\n"));
pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, sSort.pOrderBy,
@@ -5865,15 +6104,117 @@
sqlite3VdbeChangeToNoop(v, sSort.addrSortIndex);
}
- /* Use the standard inner loop. */
assert( p->pEList==pEList );
- selectInnerLoop(pParse, p, -1, &sSort, &sDistinct, pDest,
- sqlite3WhereContinueLabel(pWInfo),
- sqlite3WhereBreakLabel(pWInfo));
+ if( p->pWin ){
+ int k;
+ int iSubCsr = p->pSrc->a[0].iCursor;
+ int nSub = p->pSrc->a[0].pTab->nCol;
+ int reg = pParse->nMem+1;
+ int regRecord = reg+nSub;
+ int regRowid = regRecord+1;
+ int regGosub = regRowid+1;
+ int addr;
+ int addrGosub;
- /* End the database scan loop.
- */
- sqlite3WhereEnd(pWInfo);
+ pParse->nMem += nSub + 3;
+
+ /* Martial the row returned by the sub-select into an array of
+ ** registers. */
+ for(k=0; k<nSub; k++){
+ sqlite3VdbeAddOp3(v, OP_Column, iSubCsr, k, reg+k);
+ }
+
+ /* Check if this is the start of a new partition or peer group. */
+ if( regPart ){
+ ExprList *pPart = pWin->pPartition;
+ int nPart = (pPart ? pPart->nExpr : 0);
+ ExprList *pOrderBy = pWin->pOrderBy;
+ int nPeer = (pOrderBy ? pOrderBy->nExpr : 0);
+ int addrGoto = 0;
+ int addrJump = 0;
+
+ if( pPart ){
+ int regNewPart = reg + pWin->nBufferCol;
+ KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pPart, 0, 0);
+ addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPart, regPart, nPart);
+ sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
+ addrJump = sqlite3VdbeAddOp3(v, OP_Jump, addr+2, 0, addr+2);
+ sqlite3VdbeAddOp2(v, OP_AggFinal, pWin->regAccum, pWin->nArg);
+ sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
+ sqlite3VdbeAddOp2(v, OP_Copy, pWin->regAccum, pWin->regResult);
+ if( pOrderBy ){
+ addrGoto = sqlite3VdbeAddOp0(v, OP_Goto);
+ }
+ }
+
+ if( pOrderBy ){
+ int regNewPeer = reg + pWin->nBufferCol + nPart;
+ int regPeer = regPart + nPart;
+
+ KeyInfo *pKeyInfo = keyInfoFromExprList(pParse, pOrderBy, 0, 0);
+ if( addrJump ) sqlite3VdbeJumpHere(v, addrJump);
+ addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPeer, regPeer, nPeer);
+ sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
+ addrJump = sqlite3VdbeAddOp3(v, OP_Jump, addr+2, 0, addr+2);
+ sqlite3VdbeAddOp3(v,
+ OP_AggFinal, pWin->regAccum, pWin->nArg, pWin->regResult
+ );
+ sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
+
+ if( addrGoto ) sqlite3VdbeJumpHere(v, addrGoto);
+ }
+
+ addrGosub = sqlite3VdbeAddOp1(v, OP_Gosub, regGosub);
+ sqlite3VdbeAddOp1(v, OP_ResetSorter, pWin->iEphCsr);
+ sqlite3VdbeAddOp3(v,OP_Copy,reg+pWin->nBufferCol,regPart,nPart+nPeer-1);
+
+ sqlite3VdbeJumpHere(v, addrJump);
+ }
+
+ /* Invoke step function for window functions */
+ sqlite3VdbeAddOp3(v, OP_AggStep0, 0, reg+pWin->iArgCol, pWin->regAccum);
+ sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
+ sqlite3VdbeChangeP5(v, (u8)pWin->nArg);
+
+ /* Buffer the current row in the ephemeral table. */
+ if( pWin->nBufferCol>0 ){
+ sqlite3VdbeAddOp3(v, OP_MakeRecord, reg, pWin->nBufferCol, regRecord);
+ }else{
+ sqlite3VdbeAddOp2(v, OP_Blob, 0, regRecord);
+ sqlite3VdbeAppendP4(v, (void*)"", 0);
+ }
+ sqlite3VdbeAddOp2(v, OP_NewRowid, pWin->iEphCsr, regRowid);
+ sqlite3VdbeAddOp3(v, OP_Insert, pWin->iEphCsr, regRecord, regRowid);
+
+ /* End the database scan loop. */
+ sqlite3WhereEnd(pWInfo);
+
+ sqlite3VdbeAddOp2(v, OP_AggFinal, pWin->regAccum, pWin->nArg);
+ sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF);
+ sqlite3VdbeAddOp2(v, OP_Copy, pWin->regAccum, pWin->regResult);
+ sqlite3VdbeAddOp2(v, OP_Gosub, regGosub, sqlite3VdbeCurrentAddr(v)+2);
+
+ sqlite3VdbeAddOp0(v, OP_Goto);
+ if( regPart ){
+ sqlite3VdbeJumpHere(v, addrGosub);
+ }
+ addr = sqlite3VdbeAddOp1(v, OP_Rewind, pWin->iEphCsr);
+ selectInnerLoop(pParse, p, -1, &sSort, &sDistinct, pDest, addr+1, 0);
+ 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));
+
+ /* End the database scan loop.
+ */
+ sqlite3WhereEnd(pWInfo);
+ }
}else{
/* This case when there exist aggregate functions or a GROUP BY clause
** or both */
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index 7b19e0a..8a1376f 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -1107,6 +1107,7 @@
typedef struct VtabCtx VtabCtx;
typedef struct Walker Walker;
typedef struct WhereInfo WhereInfo;
+typedef struct Window Window;
typedef struct With With;
/* A VList object records a mapping between parameters/variables/wildcards
@@ -1588,6 +1589,8 @@
FuncDef *pNext; /* Next function with same name */
void (*xSFunc)(sqlite3_context*,int,sqlite3_value**); /* func or agg-step */
void (*xFinalize)(sqlite3_context*); /* Agg finalizer */
+ void (*xValue)(sqlite3_context*); /* Current agg value */
+ void (*xInverse)(sqlite3_context*,int,sqlite3_value**); /* inverse agg-step */
const char *zName; /* SQL name of the function. */
union {
FuncDef *pHash; /* Next with a different name but the same hash */
@@ -1678,6 +1681,12 @@
** are interpreted in the same way as the first 4 parameters to
** FUNCTION().
**
+** WFUNCTION(zName, nArg, iArg, xStep, xFinal, xValue, xInverse)
+** Used to create an aggregate function definition implemented by
+** the C functions xStep and xFinal. The first four parameters
+** are interpreted in the same way as the first 4 parameters to
+** FUNCTION().
+**
** LIKEFUNC(zName, nArg, pArg, flags)
** Used to create a scalar function definition of a function zName
** that accepts nArg arguments and is implemented by a call to C
@@ -1688,31 +1697,35 @@
*/
#define FUNCTION(zName, nArg, iArg, bNC, xFunc) \
{nArg, SQLITE_FUNC_CONSTANT|SQLITE_UTF8|(bNC*SQLITE_FUNC_NEEDCOLL), \
- SQLITE_INT_TO_PTR(iArg), 0, xFunc, 0, #zName, {0} }
+ SQLITE_INT_TO_PTR(iArg), 0, xFunc, 0, 0, 0, #zName, {0} }
#define VFUNCTION(zName, nArg, iArg, bNC, xFunc) \
{nArg, SQLITE_UTF8|(bNC*SQLITE_FUNC_NEEDCOLL), \
- SQLITE_INT_TO_PTR(iArg), 0, xFunc, 0, #zName, {0} }
+ SQLITE_INT_TO_PTR(iArg), 0, xFunc, 0, 0, 0, #zName, {0} }
#define DFUNCTION(zName, nArg, iArg, bNC, xFunc) \
{nArg, SQLITE_FUNC_SLOCHNG|SQLITE_UTF8, \
- 0, 0, xFunc, 0, #zName, {0} }
+ 0, 0, xFunc, 0, 0, 0, #zName, {0} }
#define PURE_DATE(zName, nArg, iArg, bNC, xFunc) \
{nArg, SQLITE_FUNC_SLOCHNG|SQLITE_UTF8|SQLITE_FUNC_CONSTANT, \
- (void*)&sqlite3Config, 0, xFunc, 0, #zName, {0} }
+ (void*)&sqlite3Config, 0, xFunc, 0, 0, 0, #zName, {0} }
#define FUNCTION2(zName, nArg, iArg, bNC, xFunc, extraFlags) \
{nArg,SQLITE_FUNC_CONSTANT|SQLITE_UTF8|(bNC*SQLITE_FUNC_NEEDCOLL)|extraFlags,\
- SQLITE_INT_TO_PTR(iArg), 0, xFunc, 0, #zName, {0} }
+ SQLITE_INT_TO_PTR(iArg), 0, xFunc, 0, 0, 0, #zName, {0} }
#define STR_FUNCTION(zName, nArg, pArg, bNC, xFunc) \
{nArg, SQLITE_FUNC_SLOCHNG|SQLITE_UTF8|(bNC*SQLITE_FUNC_NEEDCOLL), \
- pArg, 0, xFunc, 0, #zName, }
+ pArg, 0, xFunc, 0, 0, 0, #zName, }
#define LIKEFUNC(zName, nArg, arg, flags) \
{nArg, SQLITE_FUNC_CONSTANT|SQLITE_UTF8|flags, \
- (void *)arg, 0, likeFunc, 0, #zName, {0} }
+ (void *)arg, 0, likeFunc, 0, 0, 0, #zName, {0} }
#define AGGREGATE(zName, nArg, arg, nc, xStep, xFinal) \
{nArg, SQLITE_UTF8|(nc*SQLITE_FUNC_NEEDCOLL), \
- SQLITE_INT_TO_PTR(arg), 0, xStep,xFinal,#zName, {0}}
+ SQLITE_INT_TO_PTR(arg), 0, xStep,xFinal,0,0,#zName, {0}}
#define AGGREGATE2(zName, nArg, arg, nc, xStep, xFinal, extraFlags) \
{nArg, SQLITE_UTF8|(nc*SQLITE_FUNC_NEEDCOLL)|extraFlags, \
- SQLITE_INT_TO_PTR(arg), 0, xStep,xFinal,#zName, {0}}
+ SQLITE_INT_TO_PTR(arg), 0, xStep,xFinal,0,0,#zName, {0}}
+
+#define WFUNCTION(zName, nArg, arg, xStep, xFinal, xValue, xInverse) \
+ {nArg, SQLITE_UTF8, \
+ SQLITE_INT_TO_PTR(arg), 0, xStep,xFinal,xValue,xInverse,#zName, {0}}
/*
** All current savepoints are stored in a linked list starting at
@@ -2413,6 +2426,7 @@
AggInfo *pAggInfo; /* Used by TK_AGG_COLUMN and TK_AGG_FUNCTION */
Table *pTab; /* Table for TK_COLUMN expressions. Can be NULL
** for a column of an index on an expression */
+ Window *pWin; /* Window definition for window functions */
};
/*
@@ -2699,6 +2713,7 @@
int nRef; /* Number of names resolved by this context */
int nErr; /* Number of errors encountered while resolving names */
u16 ncFlags; /* Zero or more NC_* flags defined below */
+ Window *pWin; /* List of window functions in this context */
};
/*
@@ -2721,6 +2736,7 @@
#define NC_UUpsert 0x0200 /* True if uNC.pUpsert is used */
#define NC_MinMaxAgg 0x1000 /* min/max aggregates seen. See note above */
#define NC_Complex 0x2000 /* True if a function or subquery seen */
+#define NC_AllowWin 0x4000 /* Window functions are allowed here */
/*
** An instance of the following object describes a single ON CONFLICT
@@ -2788,6 +2804,7 @@
Select *pNext; /* Next select to the left in a compound */
Expr *pLimit; /* LIMIT expression. NULL means not used. */
With *pWith; /* WITH clause attached to this select. Or NULL. */
+ Window *pWin; /* List of window functions */
};
/*
@@ -3401,6 +3418,7 @@
struct IdxExprTrans *pIdxTrans; /* Convert idxed expr to column */
ExprList *pGroupBy; /* GROUP BY clause */
Select *pSelect; /* HAVING to WHERE clause ctx */
+ struct WindowRewrite *pRewrite; /* Window rewrite context */
} u;
};
@@ -3451,6 +3469,31 @@
};
#endif /* SQLITE_DEBUG */
+struct Window {
+ Expr *pFilter;
+ ExprList *pPartition;
+ ExprList *pOrderBy;
+ u8 eType; /* TK_RANGE or TK_ROWS */
+ u8 eStart; /* UNBOUNDED, CURRENT, PRECEDING or FOLLOWING */
+ u8 eEnd; /* UNBOUNDED, CURRENT, PRECEDING or FOLLOWING */
+ Expr *pStart; /* Expression for "<expr> PRECEDING" */
+ Expr *pEnd; /* Expression for "<expr> FOLLOWING" */
+ Window *pNextWin; /* Next window function belonging to this SELECT */
+ int iEphCsr; /* Temp table used by this window */
+ int regAccum;
+ int regResult;
+ FuncDef *pFunc;
+ int nArg;
+
+ Expr *pOwner; /* Expression object this window is attached to */
+ int nBufferCol; /* Number of columns in buffer table */
+ int iArgCol; /* Offset of first argument for this function */
+};
+
+void sqlite3WindowDelete(sqlite3*, Window*);
+Window *sqlite3WindowAlloc(Parse*, int, int, Expr*, int , Expr*);
+void sqlite3WindowAttach(Parse*, Expr*, Window*);
+
/*
** 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.
diff --git a/src/test1.c b/src/test1.c
index f2511d2..b62c310 100644
--- a/src/test1.c
+++ b/src/test1.c
@@ -7799,6 +7799,9 @@
extern int sqlite3_fts3_enable_parentheses;
#endif
#endif
+#if defined(SQLITE_ENABLE_SELECTTRACE)
+ extern int sqlite3SelectTrace;
+#endif
for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){
Tcl_CreateCommand(interp, aCmd[i].zName, aCmd[i].xProc, 0, 0);
@@ -7884,6 +7887,10 @@
(char*)&sqlite3_sync_count, TCL_LINK_INT);
Tcl_LinkVar(interp, "sqlite_fullsync_count",
(char*)&sqlite3_fullsync_count, TCL_LINK_INT);
+#if defined(SQLITE_ENABLE_SELECTTRACE)
+ Tcl_LinkVar(interp, "sqlite3SelectTrace",
+ (char*)&sqlite3SelectTrace, TCL_LINK_INT);
+#endif
#if defined(SQLITE_ENABLE_FTS3) && defined(SQLITE_TEST)
Tcl_LinkVar(interp, "sqlite_fts3_enable_parentheses",
(char*)&sqlite3_fts3_enable_parentheses, TCL_LINK_INT);
diff --git a/src/vdbe.c b/src/vdbe.c
index 70537ce..7ab1044 100644
--- a/src/vdbe.c
+++ b/src/vdbe.c
@@ -6313,7 +6313,11 @@
assert( pOp->p1>0 && pOp->p1<=(p->nMem+1 - p->nCursor) );
pMem = &aMem[pOp->p1];
assert( (pMem->flags & ~(MEM_Null|MEM_Agg))==0 );
- rc = sqlite3VdbeMemFinalize(pMem, pOp->p4.pFunc);
+ if( pOp->p3 ){
+ rc = sqlite3VdbeMemAggValue(pMem, &aMem[pOp->p3], pOp->p4.pFunc);
+ }else{
+ rc = sqlite3VdbeMemFinalize(pMem, pOp->p4.pFunc);
+ }
if( rc ){
sqlite3VdbeError(p, "%s", sqlite3_value_text(pMem));
goto abort_due_to_error;
diff --git a/src/vdbeInt.h b/src/vdbeInt.h
index 44f901a..24d6bf9 100644
--- a/src/vdbeInt.h
+++ b/src/vdbeInt.h
@@ -494,6 +494,7 @@
int sqlite3VdbeMemFromBtree(BtCursor*,u32,u32,Mem*);
void sqlite3VdbeMemRelease(Mem *p);
int sqlite3VdbeMemFinalize(Mem*, FuncDef*);
+int sqlite3VdbeMemAggValue(Mem*, Mem*, FuncDef*);
const char *sqlite3OpcodeName(int);
int sqlite3VdbeMemGrow(Mem *pMem, int n, int preserve);
int sqlite3VdbeMemClearAndResize(Mem *pMem, int n);
diff --git a/src/vdbemem.c b/src/vdbemem.c
index d118d2b..a64ed09 100644
--- a/src/vdbemem.c
+++ b/src/vdbemem.c
@@ -415,6 +415,23 @@
return ctx.isError;
}
+int sqlite3VdbeMemAggValue(Mem *pAccum, Mem *pOut, FuncDef *pFunc){
+ sqlite3_context ctx;
+ Mem t;
+ assert( pFunc!=0 );
+ assert( pFunc->xValue!=0 );
+ assert( (pAccum->flags & MEM_Null)!=0 || pFunc==pAccum->u.pDef );
+ assert( pAccum->db==0 || sqlite3_mutex_held(pAccum->db->mutex) );
+ memset(&ctx, 0, sizeof(ctx));
+ memset(&t, 0, sizeof(t));
+ t.flags = MEM_Null;
+ t.db = pAccum->db;
+ ctx.pOut = pOut;
+ ctx.pMem = pAccum;
+ ctx.pFunc = pFunc;
+ pFunc->xValue(&ctx);
+ return ctx.isError;
+}
/*
** If the memory cell contains a value that must be freed by
** invoking the external callback in Mem.xDel, then this routine
diff --git a/src/window.c b/src/window.c
new file mode 100644
index 0000000..57d4674
--- /dev/null
+++ b/src/window.c
@@ -0,0 +1,53 @@
+/*
+**
+** The author disclaims copyright to this source code. In place of
+** a legal notice, here is a blessing:
+**
+** May you do good and not evil.
+** May you find forgiveness for yourself and forgive others.
+** May you share freely, never taking more than you give.
+**
+*************************************************************************
+*/
+#include "sqliteInt.h"
+
+void sqlite3WindowDelete(sqlite3 *db, Window *p){
+ if( p ){
+ sqlite3ExprDelete(db, p->pFilter);
+ sqlite3ExprListDelete(db, p->pPartition);
+ sqlite3ExprListDelete(db, p->pOrderBy);
+ sqlite3ExprDelete(db, p->pEnd);
+ sqlite3ExprDelete(db, p->pStart);
+ sqlite3DbFree(db, p);
+ }
+}
+
+Window *sqlite3WindowAlloc(
+ Parse *pParse,
+ int eType,
+ int eEnd, Expr *pEnd,
+ int eStart, Expr *pStart
+){
+ Window *pWin = (Window*)sqlite3DbMallocZero(pParse->db, sizeof(Window));
+
+ if( pWin ){
+ pWin->eType = eType;
+ pWin->eStart = eStart;
+ pWin->eEnd = eEnd;
+ pWin->pEnd = pEnd;
+ pWin->pStart = pStart;
+ }else{
+ sqlite3ExprDelete(pParse->db, pEnd);
+ sqlite3ExprDelete(pParse->db, pStart);
+ }
+
+ return pWin;
+}
+
+void sqlite3WindowAttach(Parse *pParse, Expr *p, Window *pWin){
+ if( p ){
+ p->pWin = pWin;
+ }else{
+ sqlite3WindowDelete(pParse->db, pWin);
+ }
+}