diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/analyze.c | 3 | ||||
| -rw-r--r-- | src/attach.c | 2 | ||||
| -rw-r--r-- | src/expr.c | 28 | ||||
| -rw-r--r-- | src/func.c | 2 | ||||
| -rw-r--r-- | src/parse.y | 60 | ||||
| -rw-r--r-- | src/resolve.c | 48 | ||||
| -rw-r--r-- | src/select.c | 357 | ||||
| -rw-r--r-- | src/sqliteInt.h | 61 | ||||
| -rw-r--r-- | src/test1.c | 7 | ||||
| -rw-r--r-- | src/vdbe.c | 6 | ||||
| -rw-r--r-- | src/vdbeInt.h | 1 | ||||
| -rw-r--r-- | src/vdbemem.c | 17 | ||||
| -rw-r--r-- | src/window.c | 53 |
13 files changed, 608 insertions, 37 deletions
diff --git a/src/analyze.c b/src/analyze.c index 48fd4951c..9492e2c2f 100644 --- a/src/analyze.c +++ b/src/analyze.c @@ -485,6 +485,7 @@ static const FuncDef statInitFuncdef = { 0, /* pNext */ statInit, /* xSFunc */ 0, /* xFinalize */ + 0, 0, "stat_init", /* zName */ {0} }; @@ -801,6 +802,7 @@ static const FuncDef statPushFuncdef = { 0, /* pNext */ statPush, /* xSFunc */ 0, /* xFinalize */ + 0, 0, "stat_push", /* zName */ {0} }; @@ -952,6 +954,7 @@ static const FuncDef statGetFuncdef = { 0, /* pNext */ statGet, /* xSFunc */ 0, /* xFinalize */ + 0, 0, "stat_get", /* zName */ {0} }; diff --git a/src/attach.c b/src/attach.c index ca0fd9fd1..1f276156b 100644 --- a/src/attach.c +++ b/src/attach.c @@ -414,6 +414,7 @@ void sqlite3Detach(Parse *pParse, Expr *pDbname){ 0, /* pNext */ detachFunc, /* xSFunc */ 0, /* xFinalize */ + 0, 0, "sqlite_detach", /* zName */ {0} }; @@ -433,6 +434,7 @@ void sqlite3Attach(Parse *pParse, Expr *p, Expr *pDbname, Expr *pKey){ 0, /* pNext */ attachFunc, /* xSFunc */ 0, /* xFinalize */ + 0, 0, "sqlite_attach", /* zName */ {0} }; diff --git a/src/expr.c b/src/expr.c index 6aff83a25..a1407a85f 100644 --- a/src/expr.c +++ b/src/expr.c @@ -1063,6 +1063,9 @@ static SQLITE_NOINLINE void sqlite3ExprDeleteNN(sqlite3 *db, Expr *p){ }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 @@ static With *withDup(sqlite3 *db, With *p){ # 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 @@ Select *sqlite3SelectDup(sqlite3 *db, Select *pDup, int flags){ 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 @@ expr_code_doover: 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 @@ expr_code_doover: 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 17a267e22..f5a839d39 100644 --- a/src/func.c +++ b/src/func.c @@ -1859,7 +1859,7 @@ void sqlite3RegisterBuiltinFunctions(void){ 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 aca3bfb1c..1d1a2ddaa 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 @@ columnname(A) ::= nm(A) typetoken(Y). {sqlite3AddColumn(pParse,&A,&Y);} 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 @@ expr(A) ::= CAST LP expr(E) AS typetoken(T) RP. { 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 @@ term(A) ::= CTIME_KW(OP). { 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 4ed36a479..073fdf193 100644 --- a/src/resolve.c +++ b/src/resolve.c @@ -753,8 +753,11 @@ static int resolveExprStep(Walker *pWalker, Expr *pExpr){ 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 @@ static int resolveExprStep(Walker *pWalker, Expr *pExpr){ 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 @@ static int resolveSelectStep(Walker *pWalker, Select *p){ 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 @@ static int resolveSelectStep(Walker *pWalker, Select *p){ /* 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 @@ static int resolveSelectStep(Walker *pWalker, Select *p){ ** 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 @@ static int resolveSelectStep(Walker *pWalker, Select *p){ 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 @@ static int resolveSelectStep(Walker *pWalker, Select *p){ 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 3818ef517..2b5a3dc54 100644 --- a/src/select.c +++ b/src/select.c @@ -162,6 +162,7 @@ Select *sqlite3SelectNew( 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 @@ static int flattenSubquery( 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 @@ static void selectPopWith(Walker *pWalker, Select *p){ #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 @@ static int selectExpander(Walker *pWalker, Select *p){ 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 @@ static int selectExpander(Walker *pWalker, Select *p){ 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 @@ static int countOfViewOptimization(Parse *pParse, Select *p){ } #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 @@ int sqlite3Select( 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 @@ int sqlite3Select( 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 @@ int sqlite3Select( } 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 @@ int sqlite3Select( 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; + + 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); + } - /* End the database scan loop. - */ - sqlite3WhereEnd(pWInfo); + /* 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 7b19e0a98..8a1376fd2 100644 --- a/src/sqliteInt.h +++ b/src/sqliteInt.h @@ -1107,6 +1107,7 @@ typedef struct VTable VTable; 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 @@ struct FuncDef { 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 @@ struct FuncDestructor { ** 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 @@ struct FuncDestructor { */ #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 @@ struct Expr { 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 @@ struct NameContext { 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 @@ struct NameContext { #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 @@ struct Select { 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 Walker { 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 @@ struct TreeView { }; #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 f2511d259..b62c3104f 100644 --- a/src/test1.c +++ b/src/test1.c @@ -7799,6 +7799,9 @@ int Sqlitetest1_Init(Tcl_Interp *interp){ 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 @@ int Sqlitetest1_Init(Tcl_Interp *interp){ (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 70537ce11..7ab104455 100644 --- a/src/vdbe.c +++ b/src/vdbe.c @@ -6313,7 +6313,11 @@ case OP_AggFinal: { 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 44f901abf..24d6bf91d 100644 --- a/src/vdbeInt.h +++ b/src/vdbeInt.h @@ -494,6 +494,7 @@ void sqlite3VdbeMemCast(Mem*,u8,u8); 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 d118d2bb9..a64ed0963 100644 --- a/src/vdbemem.c +++ b/src/vdbemem.c @@ -415,6 +415,23 @@ int sqlite3VdbeMemFinalize(Mem *pMem, FuncDef *pFunc){ 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 000000000..57d467424 --- /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); + } +} |