AryaWu/sqlite
0
1/*2** 2018 May 083**4** The author disclaims copyright to this source code. In place of5** a legal notice, here is a blessing:6**7** May you do good and not evil.8** May you find forgiveness for yourself and forgive others.9** May you share freely, never taking more than you give.10**11*************************************************************************12*/13#include "sqliteInt.h"14 15#ifndef SQLITE_OMIT_WINDOWFUNC16 17/*18** SELECT REWRITING19**20** Any SELECT statement that contains one or more window functions in21** either the select list or ORDER BY clause (the only two places window22** functions may be used) is transformed by function sqlite3WindowRewrite()23** in order to support window function processing. For example, with the24** schema:25**26** CREATE TABLE t1(a, b, c, d, e, f, g);27**28** the statement:29**30** SELECT a+1, max(b) OVER (PARTITION BY c ORDER BY d) FROM t1 ORDER BY e;31**32** is transformed to:33**34** SELECT a+1, max(b) OVER (PARTITION BY c ORDER BY d) FROM (35** SELECT a, e, c, d, b FROM t1 ORDER BY c, d36** ) ORDER BY e;37**38** The flattening optimization is disabled when processing this transformed39** SELECT statement. This allows the implementation of the window function40** (in this case max()) to process rows sorted in order of (c, d), which41** makes things easier for obvious reasons. More generally:42**43** * FROM, WHERE, GROUP BY and HAVING clauses are all moved to44** the sub-query.45**46** * ORDER BY, LIMIT and OFFSET remain part of the parent query.47**48** * Terminals from each of the expression trees that make up the49** select-list and ORDER BY expressions in the parent query are50** selected by the sub-query. For the purposes of the transformation,51** terminals are column references and aggregate functions.52**53** If there is more than one window function in the SELECT that uses54** the same window declaration (the OVER bit), then a single scan may55** be used to process more than one window function. For example:56**57** SELECT max(b) OVER (PARTITION BY c ORDER BY d),58** min(e) OVER (PARTITION BY c ORDER BY d)59** FROM t1;60**61** is transformed in the same way as the example above. However:62**63** SELECT max(b) OVER (PARTITION BY c ORDER BY d),64** min(e) OVER (PARTITION BY a ORDER BY b)65** FROM t1;66**67** Must be transformed to:68**69** SELECT max(b) OVER (PARTITION BY c ORDER BY d) FROM (70** SELECT e, min(e) OVER (PARTITION BY a ORDER BY b), c, d, b FROM71** SELECT a, e, c, d, b FROM t1 ORDER BY a, b72** ) ORDER BY c, d73** ) ORDER BY e;74**75** so that both min() and max() may process rows in the order defined by76** their respective window declarations.77**78** INTERFACE WITH SELECT.C79**80** When processing the rewritten SELECT statement, code in select.c calls81** sqlite3WhereBegin() to begin iterating through the results of the82** sub-query, which is always implemented as a co-routine. It then calls83** sqlite3WindowCodeStep() to process rows and finish the scan by calling84** sqlite3WhereEnd().85**86** sqlite3WindowCodeStep() generates VM code so that, for each row returned87** by the sub-query a sub-routine (OP_Gosub) coded by select.c is invoked.88** When the sub-routine is invoked:89**90** * The results of all window-functions for the row are stored91** in the associated Window.regResult registers.92**93** * The required terminal values are stored in the current row of94** temp table Window.iEphCsr.95**96** In some cases, depending on the window frame and the specific window97** functions invoked, sqlite3WindowCodeStep() caches each entire partition98** in a temp table before returning any rows. In other cases it does not.99** This detail is encapsulated within this file, the code generated by100** select.c is the same in either case.101**102** BUILT-IN WINDOW FUNCTIONS103**104** This implementation features the following built-in window functions:105**106** row_number()107** rank()108** dense_rank()109** percent_rank()110** cume_dist()111** ntile(N)112** lead(expr [, offset [, default]])113** lag(expr [, offset [, default]])114** first_value(expr)115** last_value(expr)116** nth_value(expr, N)117** 118** These are the same built-in window functions supported by Postgres.119** Although the behaviour of aggregate window functions (functions that120** can be used as either aggregates or window functions) allows them to121** be implemented using an API, built-in window functions are much more122** esoteric. Additionally, some window functions (e.g. nth_value())123** may only be implemented by caching the entire partition in memory.124** As such, some built-in window functions use the same API as aggregate125** window functions and some are implemented directly using VDBE126** instructions. Additionally, for those functions that use the API, the127** window frame is sometimes modified before the SELECT statement is128** rewritten. For example, regardless of the specified window frame, the129** row_number() function always uses:130**131** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW132**133** See sqlite3WindowUpdate() for details.134**135** As well as some of the built-in window functions, aggregate window136** functions min() and max() are implemented using VDBE instructions if137** the start of the window frame is declared as anything other than138** UNBOUNDED PRECEDING.139*/140 141/*142** Implementation of built-in window function row_number(). Assumes that the143** window frame has been coerced to:144**145** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW146*/147static void row_numberStepFunc(148 sqlite3_context *pCtx,149 int nArg,150 sqlite3_value **apArg151){152 i64 *p = (i64*)sqlite3_aggregate_context(pCtx, sizeof(*p));153 if( p ) (*p)++;154 UNUSED_PARAMETER(nArg);155 UNUSED_PARAMETER(apArg);156}157static void row_numberValueFunc(sqlite3_context *pCtx){158 i64 *p = (i64*)sqlite3_aggregate_context(pCtx, sizeof(*p));159 sqlite3_result_int64(pCtx, (p ? *p : 0));160}161 162/*163** Context object type used by rank(), dense_rank(), percent_rank() and164** cume_dist().165*/166struct CallCount {167 i64 nValue;168 i64 nStep;169 i64 nTotal;170};171 172/*173** Implementation of built-in window function dense_rank(). Assumes that174** the window frame has been set to:175**176** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW177*/178static void dense_rankStepFunc(179 sqlite3_context *pCtx,180 int nArg,181 sqlite3_value **apArg182){183 struct CallCount *p;184 p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));185 if( p ) p->nStep = 1;186 UNUSED_PARAMETER(nArg);187 UNUSED_PARAMETER(apArg);188}189static void dense_rankValueFunc(sqlite3_context *pCtx){190 struct CallCount *p;191 p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));192 if( p ){193 if( p->nStep ){194 p->nValue++;195 p->nStep = 0;196 }197 sqlite3_result_int64(pCtx, p->nValue);198 }199}200 201/*202** Implementation of built-in window function nth_value(). This203** implementation is used in "slow mode" only - when the EXCLUDE clause204** is not set to the default value "NO OTHERS".205*/206struct NthValueCtx {207 i64 nStep;208 sqlite3_value *pValue;209};210static void nth_valueStepFunc(211 sqlite3_context *pCtx,212 int nArg,213 sqlite3_value **apArg214){215 struct NthValueCtx *p;216 p = (struct NthValueCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));217 if( p ){218 i64 iVal;219 switch( sqlite3_value_numeric_type(apArg[1]) ){220 case SQLITE_INTEGER:221 iVal = sqlite3_value_int64(apArg[1]);222 break;223 case SQLITE_FLOAT: {224 double fVal = sqlite3_value_double(apArg[1]);225 if( ((i64)fVal)!=fVal ) goto error_out;226 iVal = (i64)fVal;227 break;228 }229 default:230 goto error_out;231 }232 if( iVal<=0 ) goto error_out;233 234 p->nStep++;235 if( iVal==p->nStep ){236 p->pValue = sqlite3_value_dup(apArg[0]);237 if( !p->pValue ){238 sqlite3_result_error_nomem(pCtx);239 }240 }241 }242 UNUSED_PARAMETER(nArg);243 UNUSED_PARAMETER(apArg);244 return;245 246 error_out:247 sqlite3_result_error(248 pCtx, "second argument to nth_value must be a positive integer", -1249 );250}251static void nth_valueFinalizeFunc(sqlite3_context *pCtx){252 struct NthValueCtx *p;253 p = (struct NthValueCtx*)sqlite3_aggregate_context(pCtx, 0);254 if( p && p->pValue ){255 sqlite3_result_value(pCtx, p->pValue);256 sqlite3_value_free(p->pValue);257 p->pValue = 0;258 }259}260#define nth_valueInvFunc noopStepFunc261#define nth_valueValueFunc noopValueFunc262 263static void first_valueStepFunc(264 sqlite3_context *pCtx,265 int nArg,266 sqlite3_value **apArg267){268 struct NthValueCtx *p;269 p = (struct NthValueCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));270 if( p && p->pValue==0 ){271 p->pValue = sqlite3_value_dup(apArg[0]);272 if( !p->pValue ){273 sqlite3_result_error_nomem(pCtx);274 }275 }276 UNUSED_PARAMETER(nArg);277 UNUSED_PARAMETER(apArg);278}279static void first_valueFinalizeFunc(sqlite3_context *pCtx){280 struct NthValueCtx *p;281 p = (struct NthValueCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));282 if( p && p->pValue ){283 sqlite3_result_value(pCtx, p->pValue);284 sqlite3_value_free(p->pValue);285 p->pValue = 0;286 }287}288#define first_valueInvFunc noopStepFunc289#define first_valueValueFunc noopValueFunc290 291/*292** Implementation of built-in window function rank(). Assumes that293** the window frame has been set to:294**295** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW296*/297static void rankStepFunc(298 sqlite3_context *pCtx,299 int nArg,300 sqlite3_value **apArg301){302 struct CallCount *p;303 p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));304 if( p ){305 p->nStep++;306 if( p->nValue==0 ){307 p->nValue = p->nStep;308 }309 }310 UNUSED_PARAMETER(nArg);311 UNUSED_PARAMETER(apArg);312}313static void rankValueFunc(sqlite3_context *pCtx){314 struct CallCount *p;315 p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));316 if( p ){317 sqlite3_result_int64(pCtx, p->nValue);318 p->nValue = 0;319 }320}321 322/*323** Implementation of built-in window function percent_rank(). Assumes that324** the window frame has been set to:325**326** GROUPS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING327*/328static void percent_rankStepFunc(329 sqlite3_context *pCtx,330 int nArg,331 sqlite3_value **apArg332){333 struct CallCount *p;334 UNUSED_PARAMETER(nArg); assert( nArg==0 );335 UNUSED_PARAMETER(apArg);336 p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));337 if( p ){338 p->nTotal++;339 }340}341static void percent_rankInvFunc(342 sqlite3_context *pCtx,343 int nArg,344 sqlite3_value **apArg345){346 struct CallCount *p;347 UNUSED_PARAMETER(nArg); assert( nArg==0 );348 UNUSED_PARAMETER(apArg);349 p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));350 p->nStep++;351}352static void percent_rankValueFunc(sqlite3_context *pCtx){353 struct CallCount *p;354 p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));355 if( p ){356 p->nValue = p->nStep;357 if( p->nTotal>1 ){358 double r = (double)p->nValue / (double)(p->nTotal-1);359 sqlite3_result_double(pCtx, r);360 }else{361 sqlite3_result_double(pCtx, 0.0);362 }363 }364}365#define percent_rankFinalizeFunc percent_rankValueFunc366 367/*368** Implementation of built-in window function cume_dist(). Assumes that369** the window frame has been set to:370**371** GROUPS BETWEEN 1 FOLLOWING AND UNBOUNDED FOLLOWING372*/373static void cume_distStepFunc(374 sqlite3_context *pCtx,375 int nArg,376 sqlite3_value **apArg377){378 struct CallCount *p;379 UNUSED_PARAMETER(nArg); assert( nArg==0 );380 UNUSED_PARAMETER(apArg);381 p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));382 if( p ){383 p->nTotal++;384 }385}386static void cume_distInvFunc(387 sqlite3_context *pCtx,388 int nArg,389 sqlite3_value **apArg390){391 struct CallCount *p;392 UNUSED_PARAMETER(nArg); assert( nArg==0 );393 UNUSED_PARAMETER(apArg);394 p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));395 p->nStep++;396}397static void cume_distValueFunc(sqlite3_context *pCtx){398 struct CallCount *p;399 p = (struct CallCount*)sqlite3_aggregate_context(pCtx, 0);400 if( p ){401 double r = (double)(p->nStep) / (double)(p->nTotal);402 sqlite3_result_double(pCtx, r);403 }404}405#define cume_distFinalizeFunc cume_distValueFunc406 407/*408** Context object for ntile() window function.409*/410struct NtileCtx {411 i64 nTotal; /* Total rows in partition */412 i64 nParam; /* Parameter passed to ntile(N) */413 i64 iRow; /* Current row */414};415 416/*417** Implementation of ntile(). This assumes that the window frame has418** been coerced to:419**420** ROWS CURRENT ROW AND UNBOUNDED FOLLOWING421*/422static void ntileStepFunc(423 sqlite3_context *pCtx,424 int nArg,425 sqlite3_value **apArg426){427 struct NtileCtx *p;428 assert( nArg==1 ); UNUSED_PARAMETER(nArg);429 p = (struct NtileCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));430 if( p ){431 if( p->nTotal==0 ){432 p->nParam = sqlite3_value_int64(apArg[0]);433 if( p->nParam<=0 ){434 sqlite3_result_error(435 pCtx, "argument of ntile must be a positive integer", -1436 );437 }438 }439 p->nTotal++;440 }441}442static void ntileInvFunc(443 sqlite3_context *pCtx,444 int nArg,445 sqlite3_value **apArg446){447 struct NtileCtx *p;448 assert( nArg==1 ); UNUSED_PARAMETER(nArg);449 UNUSED_PARAMETER(apArg);450 p = (struct NtileCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));451 p->iRow++;452}453static void ntileValueFunc(sqlite3_context *pCtx){454 struct NtileCtx *p;455 p = (struct NtileCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));456 if( p && p->nParam>0 ){457 int nSize = (p->nTotal / p->nParam);458 if( nSize==0 ){459 sqlite3_result_int64(pCtx, p->iRow+1);460 }else{461 i64 nLarge = p->nTotal - p->nParam*nSize;462 i64 iSmall = nLarge*(nSize+1);463 i64 iRow = p->iRow;464 465 assert( (nLarge*(nSize+1) + (p->nParam-nLarge)*nSize)==p->nTotal );466 467 if( iRow<iSmall ){468 sqlite3_result_int64(pCtx, 1 + iRow/(nSize+1));469 }else{470 sqlite3_result_int64(pCtx, 1 + nLarge + (iRow-iSmall)/nSize);471 }472 }473 }474}475#define ntileFinalizeFunc ntileValueFunc476 477/*478** Context object for last_value() window function.479*/480struct LastValueCtx {481 sqlite3_value *pVal;482 int nVal;483};484 485/*486** Implementation of last_value().487*/488static void last_valueStepFunc(489 sqlite3_context *pCtx,490 int nArg,491 sqlite3_value **apArg492){493 struct LastValueCtx *p;494 UNUSED_PARAMETER(nArg);495 p = (struct LastValueCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));496 if( p ){497 sqlite3_value_free(p->pVal);498 p->pVal = sqlite3_value_dup(apArg[0]);499 if( p->pVal==0 ){500 sqlite3_result_error_nomem(pCtx);501 }else{502 p->nVal++;503 }504 }505}506static void last_valueInvFunc(507 sqlite3_context *pCtx,508 int nArg,509 sqlite3_value **apArg510){511 struct LastValueCtx *p;512 UNUSED_PARAMETER(nArg);513 UNUSED_PARAMETER(apArg);514 p = (struct LastValueCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));515 if( ALWAYS(p) ){516 p->nVal--;517 if( p->nVal==0 ){518 sqlite3_value_free(p->pVal);519 p->pVal = 0;520 }521 }522}523static void last_valueValueFunc(sqlite3_context *pCtx){524 struct LastValueCtx *p;525 p = (struct LastValueCtx*)sqlite3_aggregate_context(pCtx, 0);526 if( p && p->pVal ){527 sqlite3_result_value(pCtx, p->pVal);528 }529}530static void last_valueFinalizeFunc(sqlite3_context *pCtx){531 struct LastValueCtx *p;532 p = (struct LastValueCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));533 if( p && p->pVal ){534 sqlite3_result_value(pCtx, p->pVal);535 sqlite3_value_free(p->pVal);536 p->pVal = 0;537 }538}539 540/*541** Static names for the built-in window function names. These static542** names are used, rather than string literals, so that FuncDef objects543** can be associated with a particular window function by direct544** comparison of the zName pointer. Example:545**546** if( pFuncDef->zName==row_valueName ){ ... }547*/548static const char row_numberName[] = "row_number";549static const char dense_rankName[] = "dense_rank";550static const char rankName[] = "rank";551static const char percent_rankName[] = "percent_rank";552static const char cume_distName[] = "cume_dist";553static const char ntileName[] = "ntile";554static const char last_valueName[] = "last_value";555static const char nth_valueName[] = "nth_value";556static const char first_valueName[] = "first_value";557static const char leadName[] = "lead";558static const char lagName[] = "lag";559 560/*561** No-op implementations of xStep() and xFinalize(). Used as place-holders562** for built-in window functions that never call those interfaces.563**564** The noopValueFunc() is called but is expected to do nothing. The565** noopStepFunc() is never called, and so it is marked with NO_TEST to566** let the test coverage routine know not to expect this function to be567** invoked.568*/569static void noopStepFunc( /*NO_TEST*/570 sqlite3_context *p, /*NO_TEST*/571 int n, /*NO_TEST*/572 sqlite3_value **a /*NO_TEST*/573){ /*NO_TEST*/574 UNUSED_PARAMETER(p); /*NO_TEST*/575 UNUSED_PARAMETER(n); /*NO_TEST*/576 UNUSED_PARAMETER(a); /*NO_TEST*/577 assert(0); /*NO_TEST*/578} /*NO_TEST*/579static void noopValueFunc(sqlite3_context *p){ UNUSED_PARAMETER(p); /*no-op*/ }580 581/* Window functions that use all window interfaces: xStep, xFinal,582** xValue, and xInverse */583#define WINDOWFUNCALL(name,nArg,extra) { \584 nArg, (SQLITE_FUNC_BUILTIN|SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0, \585 name ## StepFunc, name ## FinalizeFunc, name ## ValueFunc, \586 name ## InvFunc, name ## Name, {0} \587}588 589/* Window functions that are implemented using bytecode and thus have590** no-op routines for their methods */591#define WINDOWFUNCNOOP(name,nArg,extra) { \592 nArg, (SQLITE_FUNC_BUILTIN|SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0, \593 noopStepFunc, noopValueFunc, noopValueFunc, \594 noopStepFunc, name ## Name, {0} \595}596 597/* Window functions that use all window interfaces: xStep, the598** same routine for xFinalize and xValue and which never call599** xInverse. */600#define WINDOWFUNCX(name,nArg,extra) { \601 nArg, (SQLITE_FUNC_BUILTIN|SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0, \602 name ## StepFunc, name ## ValueFunc, name ## ValueFunc, \603 noopStepFunc, name ## Name, {0} \604}605 606 607/*608** Register those built-in window functions that are not also aggregates.609*/610void sqlite3WindowFunctions(void){611 static FuncDef aWindowFuncs[] = {612 WINDOWFUNCX(row_number, 0, 0),613 WINDOWFUNCX(dense_rank, 0, 0),614 WINDOWFUNCX(rank, 0, 0),615 WINDOWFUNCALL(percent_rank, 0, 0),616 WINDOWFUNCALL(cume_dist, 0, 0),617 WINDOWFUNCALL(ntile, 1, 0),618 WINDOWFUNCALL(last_value, 1, 0),619 WINDOWFUNCALL(nth_value, 2, 0),620 WINDOWFUNCALL(first_value, 1, 0),621 WINDOWFUNCNOOP(lead, 1, 0),622 WINDOWFUNCNOOP(lead, 2, 0),623 WINDOWFUNCNOOP(lead, 3, 0),624 WINDOWFUNCNOOP(lag, 1, 0),625 WINDOWFUNCNOOP(lag, 2, 0),626 WINDOWFUNCNOOP(lag, 3, 0),627 };628 sqlite3InsertBuiltinFuncs(aWindowFuncs, ArraySize(aWindowFuncs));629}630 631static Window *windowFind(Parse *pParse, Window *pList, const char *zName){632 Window *p;633 for(p=pList; p; p=p->pNextWin){634 if( sqlite3StrICmp(p->zName, zName)==0 ) break;635 }636 if( p==0 ){637 sqlite3ErrorMsg(pParse, "no such window: %s", zName);638 }639 return p;640}641 642/*643** This function is called immediately after resolving the function name644** for a window function within a SELECT statement. Argument pList is a645** linked list of WINDOW definitions for the current SELECT statement.646** Argument pFunc is the function definition just resolved and pWin647** is the Window object representing the associated OVER clause. This648** function updates the contents of pWin as follows:649**650** * If the OVER clause referred to a named window (as in "max(x) OVER win"),651** search list pList for a matching WINDOW definition, and update pWin652** accordingly. If no such WINDOW clause can be found, leave an error653** in pParse.654**655** * If the function is a built-in window function that requires the656** window to be coerced (see "BUILT-IN WINDOW FUNCTIONS" at the top657** of this file), pWin is updated here.658*/659void sqlite3WindowUpdate(660 Parse *pParse,661 Window *pList, /* List of named windows for this SELECT */662 Window *pWin, /* Window frame to update */663 FuncDef *pFunc /* Window function definition */664){665 if( pWin->zName && pWin->eFrmType==0 ){666 Window *p = windowFind(pParse, pList, pWin->zName);667 if( p==0 ) return;668 pWin->pPartition = sqlite3ExprListDup(pParse->db, p->pPartition, 0);669 pWin->pOrderBy = sqlite3ExprListDup(pParse->db, p->pOrderBy, 0);670 pWin->pStart = sqlite3ExprDup(pParse->db, p->pStart, 0);671 pWin->pEnd = sqlite3ExprDup(pParse->db, p->pEnd, 0);672 pWin->eStart = p->eStart;673 pWin->eEnd = p->eEnd;674 pWin->eFrmType = p->eFrmType;675 pWin->eExclude = p->eExclude;676 }else{677 sqlite3WindowChain(pParse, pWin, pList);678 }679 if( (pWin->eFrmType==TK_RANGE)680 && (pWin->pStart || pWin->pEnd)681 && (pWin->pOrderBy==0 || pWin->pOrderBy->nExpr!=1)682 ){683 sqlite3ErrorMsg(pParse,684 "RANGE with offset PRECEDING/FOLLOWING requires one ORDER BY expression"685 );686 }else687 if( pFunc->funcFlags & SQLITE_FUNC_WINDOW ){688 sqlite3 *db = pParse->db;689 if( pWin->pFilter ){690 sqlite3ErrorMsg(pParse,691 "FILTER clause may only be used with aggregate window functions"692 );693 }else{694 struct WindowUpdate {695 const char *zFunc;696 int eFrmType;697 int eStart;698 int eEnd;699 } aUp[] = {700 { row_numberName, TK_ROWS, TK_UNBOUNDED, TK_CURRENT },701 { dense_rankName, TK_RANGE, TK_UNBOUNDED, TK_CURRENT },702 { rankName, TK_RANGE, TK_UNBOUNDED, TK_CURRENT },703 { percent_rankName, TK_GROUPS, TK_CURRENT, TK_UNBOUNDED },704 { cume_distName, TK_GROUPS, TK_FOLLOWING, TK_UNBOUNDED },705 { ntileName, TK_ROWS, TK_CURRENT, TK_UNBOUNDED },706 { leadName, TK_ROWS, TK_UNBOUNDED, TK_UNBOUNDED },707 { lagName, TK_ROWS, TK_UNBOUNDED, TK_CURRENT },708 };709 int i;710 for(i=0; i<ArraySize(aUp); i++){711 if( pFunc->zName==aUp[i].zFunc ){712 sqlite3ExprDelete(db, pWin->pStart);713 sqlite3ExprDelete(db, pWin->pEnd);714 pWin->pEnd = pWin->pStart = 0;715 pWin->eFrmType = aUp[i].eFrmType;716 pWin->eStart = aUp[i].eStart;717 pWin->eEnd = aUp[i].eEnd;718 pWin->eExclude = 0;719 if( pWin->eStart==TK_FOLLOWING ){720 pWin->pStart = sqlite3ExprInt32(db, 1);721 }722 break;723 }724 }725 }726 }727 pWin->pWFunc = pFunc;728}729 730/*731** Context object passed through sqlite3WalkExprList() to732** selectWindowRewriteExprCb() by selectWindowRewriteEList().733*/734typedef struct WindowRewrite WindowRewrite;735struct WindowRewrite {736 Window *pWin;737 SrcList *pSrc;738 ExprList *pSub;739 Table *pTab;740 Select *pSubSelect; /* Current sub-select, if any */741};742 743/*744** Callback function used by selectWindowRewriteEList(). If necessary,745** this function appends to the output expression-list and updates746** expression (*ppExpr) in place.747*/748static int selectWindowRewriteExprCb(Walker *pWalker, Expr *pExpr){749 struct WindowRewrite *p = pWalker->u.pRewrite;750 Parse *pParse = pWalker->pParse;751 assert( p!=0 );752 assert( p->pWin!=0 );753 754 /* If this function is being called from within a scalar sub-select755 ** that used by the SELECT statement being processed, only process756 ** TK_COLUMN expressions that refer to it (the outer SELECT). Do757 ** not process aggregates or window functions at all, as they belong758 ** to the scalar sub-select. */759 if( p->pSubSelect ){760 if( pExpr->op!=TK_COLUMN ){761 return WRC_Continue;762 }else{763 int nSrc = p->pSrc->nSrc;764 int i;765 for(i=0; i<nSrc; i++){766 if( pExpr->iTable==p->pSrc->a[i].iCursor ) break;767 }768 if( i==nSrc ) return WRC_Continue;769 }770 }771 772 switch( pExpr->op ){773 774 case TK_FUNCTION:775 if( !ExprHasProperty(pExpr, EP_WinFunc) ){776 break;777 }else{778 Window *pWin;779 for(pWin=p->pWin; pWin; pWin=pWin->pNextWin){780 if( pExpr->y.pWin==pWin ){781 assert( pWin->pOwner==pExpr );782 return WRC_Prune;783 }784 }785 }786 /* no break */ deliberate_fall_through787 788 case TK_IF_NULL_ROW:789 case TK_AGG_FUNCTION:790 case TK_COLUMN: {791 int iCol = -1;792 if( pParse->db->mallocFailed ) return WRC_Abort;793 if( p->pSub ){794 int i;795 for(i=0; i<p->pSub->nExpr; i++){796 if( 0==sqlite3ExprCompare(0, p->pSub->a[i].pExpr, pExpr, -1) ){797 iCol = i;798 break;799 }800 }801 }802 if( iCol<0 ){803 Expr *pDup = sqlite3ExprDup(pParse->db, pExpr, 0);804 if( pDup && pDup->op==TK_AGG_FUNCTION ) pDup->op = TK_FUNCTION;805 p->pSub = sqlite3ExprListAppend(pParse, p->pSub, pDup);806 }807 if( p->pSub ){808 int f = pExpr->flags & EP_Collate;809 assert( ExprHasProperty(pExpr, EP_Static)==0 );810 ExprSetProperty(pExpr, EP_Static);811 sqlite3ExprDelete(pParse->db, pExpr);812 ExprClearProperty(pExpr, EP_Static);813 memset(pExpr, 0, sizeof(Expr));814 815 pExpr->op = TK_COLUMN;816 pExpr->iColumn = (iCol<0 ? p->pSub->nExpr-1: iCol);817 pExpr->iTable = p->pWin->iEphCsr;818 pExpr->y.pTab = p->pTab;819 pExpr->flags = f;820 }821 if( pParse->db->mallocFailed ) return WRC_Abort;822 break;823 }824 825 default: /* no-op */826 break;827 }828 829 return WRC_Continue;830}831static int selectWindowRewriteSelectCb(Walker *pWalker, Select *pSelect){832 struct WindowRewrite *p = pWalker->u.pRewrite;833 Select *pSave = p->pSubSelect;834 if( pSave==pSelect ){835 return WRC_Continue;836 }else{837 p->pSubSelect = pSelect;838 sqlite3WalkSelect(pWalker, pSelect);839 p->pSubSelect = pSave;840 }841 return WRC_Prune;842}843 844 845/*846** Iterate through each expression in expression-list pEList. For each:847**848** * TK_COLUMN,849** * aggregate function, or850** * window function with a Window object that is not a member of the851** Window list passed as the second argument (pWin).852**853** Append the node to output expression-list (*ppSub). And replace it854** with a TK_COLUMN that reads the (N-1)th element of table855** pWin->iEphCsr, where N is the number of elements in (*ppSub) after856** appending the new one.857*/858static void selectWindowRewriteEList(859 Parse *pParse,860 Window *pWin,861 SrcList *pSrc,862 ExprList *pEList, /* Rewrite expressions in this list */863 Table *pTab,864 ExprList **ppSub /* IN/OUT: Sub-select expression-list */865){866 Walker sWalker;867 WindowRewrite sRewrite;868 869 assert( pWin!=0 );870 memset(&sWalker, 0, sizeof(Walker));871 memset(&sRewrite, 0, sizeof(WindowRewrite));872 873 sRewrite.pSub = *ppSub;874 sRewrite.pWin = pWin;875 sRewrite.pSrc = pSrc;876 sRewrite.pTab = pTab;877 878 sWalker.pParse = pParse;879 sWalker.xExprCallback = selectWindowRewriteExprCb;880 sWalker.xSelectCallback = selectWindowRewriteSelectCb;881 sWalker.u.pRewrite = &sRewrite;882 883 (void)sqlite3WalkExprList(&sWalker, pEList);884 885 *ppSub = sRewrite.pSub;886}887 888/*889** Append a copy of each expression in expression-list pAppend to890** expression list pList. Return a pointer to the result list.891*/892static ExprList *exprListAppendList(893 Parse *pParse, /* Parsing context */894 ExprList *pList, /* List to which to append. Might be NULL */895 ExprList *pAppend, /* List of values to append. Might be NULL */896 int bIntToNull897){898 if( pAppend ){899 int i;900 int nInit = pList ? pList->nExpr : 0;901 for(i=0; i<pAppend->nExpr; i++){902 sqlite3 *db = pParse->db;903 Expr *pDup = sqlite3ExprDup(db, pAppend->a[i].pExpr, 0);904 if( db->mallocFailed ){905 sqlite3ExprDelete(db, pDup);906 break;907 }908 if( bIntToNull ){909 int iDummy;910 Expr *pSub;911 pSub = sqlite3ExprSkipCollateAndLikely(pDup);912 if( sqlite3ExprIsInteger(pSub, &iDummy, 0) ){913 pSub->op = TK_NULL;914 pSub->flags &= ~(EP_IntValue|EP_IsTrue|EP_IsFalse);915 pSub->u.zToken = 0;916 }917 }918 pList = sqlite3ExprListAppend(pParse, pList, pDup);919 if( pList ) pList->a[nInit+i].fg.sortFlags = pAppend->a[i].fg.sortFlags;920 }921 }922 return pList;923}924 925/*926** When rewriting a query, if the new subquery in the FROM clause927** contains TK_AGG_FUNCTION nodes that refer to an outer query,928** then we have to increase the Expr->op2 values of those nodes929** due to the extra subquery layer that was added.930**931** See also the incrAggDepth() routine in resolve.c932*/933static int sqlite3WindowExtraAggFuncDepth(Walker *pWalker, Expr *pExpr){934 if( pExpr->op==TK_AGG_FUNCTION935 && pExpr->op2>=pWalker->walkerDepth936 ){937 pExpr->op2++;938 }939 return WRC_Continue;940}941 942static int disallowAggregatesInOrderByCb(Walker *pWalker, Expr *pExpr){943 if( pExpr->op==TK_AGG_FUNCTION && pExpr->pAggInfo==0 ){944 assert( !ExprHasProperty(pExpr, EP_IntValue) );945 sqlite3ErrorMsg(pWalker->pParse,946 "misuse of aggregate: %s()", pExpr->u.zToken);947 }948 return WRC_Continue;949}950 951/*952** If the SELECT statement passed as the second argument does not invoke953** any SQL window functions, this function is a no-op. Otherwise, it954** rewrites the SELECT statement so that window function xStep functions955** are invoked in the correct order as described under "SELECT REWRITING"956** at the top of this file.957*/958int sqlite3WindowRewrite(Parse *pParse, Select *p){959 int rc = SQLITE_OK;960 if( p->pWin961 && p->pPrior==0962 && ALWAYS((p->selFlags & SF_WinRewrite)==0)963 && ALWAYS(!IN_RENAME_OBJECT)964 ){965 Vdbe *v = sqlite3GetVdbe(pParse);966 sqlite3 *db = pParse->db;967 Select *pSub = 0; /* The subquery */968 SrcList *pSrc = p->pSrc;969 Expr *pWhere = p->pWhere;970 ExprList *pGroupBy = p->pGroupBy;971 Expr *pHaving = p->pHaving;972 ExprList *pSort = 0;973 974 ExprList *pSublist = 0; /* Expression list for sub-query */975 Window *pMWin = p->pWin; /* Main window object */976 Window *pWin; /* Window object iterator */977 Table *pTab;978 Walker w;979 980 u32 selFlags = p->selFlags;981 982 pTab = sqlite3DbMallocZero(db, sizeof(Table));983 if( pTab==0 ){984 return sqlite3ErrorToParser(db, SQLITE_NOMEM);985 }986 sqlite3AggInfoPersistWalkerInit(&w, pParse);987 sqlite3WalkSelect(&w, p);988 if( (p->selFlags & SF_Aggregate)==0 ){989 w.xExprCallback = disallowAggregatesInOrderByCb;990 w.xSelectCallback = 0;991 sqlite3WalkExprList(&w, p->pOrderBy);992 }993 994 p->pSrc = 0;995 p->pWhere = 0;996 p->pGroupBy = 0;997 p->pHaving = 0;998 p->selFlags &= ~(u32)SF_Aggregate;999 p->selFlags |= SF_WinRewrite;1000 1001 /* Create the ORDER BY clause for the sub-select. This is the concatenation1002 ** of the window PARTITION and ORDER BY clauses. Then, if this makes it1003 ** redundant, remove the ORDER BY from the parent SELECT. */1004 pSort = exprListAppendList(pParse, 0, pMWin->pPartition, 1);1005 pSort = exprListAppendList(pParse, pSort, pMWin->pOrderBy, 1);1006 if( pSort && p->pOrderBy && p->pOrderBy->nExpr<=pSort->nExpr ){1007 int nSave = pSort->nExpr;1008 pSort->nExpr = p->pOrderBy->nExpr;1009 if( sqlite3ExprListCompare(pSort, p->pOrderBy, -1)==0 ){1010 sqlite3ExprListDelete(db, p->pOrderBy);1011 p->pOrderBy = 0;1012 }1013 pSort->nExpr = nSave;1014 }1015 1016 /* Assign a cursor number for the ephemeral table used to buffer rows.1017 ** The OpenEphemeral instruction is coded later, after it is known how1018 ** many columns the table will have. */1019 pMWin->iEphCsr = pParse->nTab++;1020 pParse->nTab += 3;1021 1022 selectWindowRewriteEList(pParse, pMWin, pSrc, p->pEList, pTab, &pSublist);1023 selectWindowRewriteEList(pParse, pMWin, pSrc, p->pOrderBy, pTab, &pSublist);1024 pMWin->nBufferCol = (pSublist ? pSublist->nExpr : 0);1025 1026 /* Append the PARTITION BY and ORDER BY expressions to the to the1027 ** sub-select expression list. They are required to figure out where1028 ** boundaries for partitions and sets of peer rows lie. */1029 pSublist = exprListAppendList(pParse, pSublist, pMWin->pPartition, 0);1030 pSublist = exprListAppendList(pParse, pSublist, pMWin->pOrderBy, 0);1031 1032 /* Append the arguments passed to each window function to the1033 ** sub-select expression list. Also allocate two registers for each1034 ** window function - one for the accumulator, another for interim1035 ** results. */1036 for(pWin=pMWin; pWin; pWin=pWin->pNextWin){1037 ExprList *pArgs;1038 assert( ExprUseXList(pWin->pOwner) );1039 assert( pWin->pWFunc!=0 );1040 pArgs = pWin->pOwner->x.pList;1041 if( pWin->pWFunc->funcFlags & SQLITE_SUBTYPE ){1042 selectWindowRewriteEList(pParse, pMWin, pSrc, pArgs, pTab, &pSublist);1043 pWin->iArgCol = (pSublist ? pSublist->nExpr : 0);1044 pWin->bExprArgs = 1;1045 }else{1046 pWin->iArgCol = (pSublist ? pSublist->nExpr : 0);1047 pSublist = exprListAppendList(pParse, pSublist, pArgs, 0);1048 }1049 if( pWin->pFilter ){1050 Expr *pFilter = sqlite3ExprDup(db, pWin->pFilter, 0);1051 pSublist = sqlite3ExprListAppend(pParse, pSublist, pFilter);1052 }1053 pWin->regAccum = ++pParse->nMem;1054 pWin->regResult = ++pParse->nMem;1055 sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);1056 }1057 1058 /* If there is no ORDER BY or PARTITION BY clause, and the window1059 ** function accepts zero arguments, and there are no other columns1060 ** selected (e.g. "SELECT row_number() OVER () FROM t1"), it is possible1061 ** that pSublist is still NULL here. Add a constant expression here to1062 ** keep everything legal in this case.1063 */1064 if( pSublist==0 ){1065 pSublist = sqlite3ExprListAppend(pParse, 0, sqlite3ExprInt32(db, 0));1066 }1067 1068 pSub = sqlite3SelectNew(1069 pParse, pSublist, pSrc, pWhere, pGroupBy, pHaving, pSort, 0, 01070 );1071 TREETRACE(0x40,pParse,pSub,1072 ("New window-function subquery in FROM clause of (%u/%p)\n",1073 p->selId, p));1074 p->pSrc = sqlite3SrcListAppend(pParse, 0, 0, 0);1075 assert( pSub!=0 || p->pSrc==0 ); /* Due to db->mallocFailed test inside1076 ** of sqlite3DbMallocRawNN() called from1077 ** sqlite3SrcListAppend() */1078 if( p->pSrc==0 ){1079 sqlite3SelectDelete(db, pSub);1080 }else if( sqlite3SrcItemAttachSubquery(pParse, &p->pSrc->a[0], pSub, 0) ){1081 Table *pTab2;1082 p->pSrc->a[0].fg.isCorrelated = 1;1083 sqlite3SrcListAssignCursors(pParse, p->pSrc);1084 pSub->selFlags |= SF_Expanded|SF_OrderByReqd;1085 pTab2 = sqlite3ResultSetOfSelect(pParse, pSub, SQLITE_AFF_NONE);1086 pSub->selFlags |= (selFlags & SF_Aggregate);1087 if( pTab2==0 ){1088 /* Might actually be some other kind of error, but in that case1089 ** pParse->nErr will be set, so if SQLITE_NOMEM is set, we will get1090 ** the correct error message regardless. */1091 rc = SQLITE_NOMEM;1092 }else{1093 memcpy(pTab, pTab2, sizeof(Table));1094 pTab->tabFlags |= TF_Ephemeral;1095 p->pSrc->a[0].pSTab = pTab;1096 pTab = pTab2;1097 memset(&w, 0, sizeof(w));1098 w.xExprCallback = sqlite3WindowExtraAggFuncDepth;1099 w.xSelectCallback = sqlite3WalkerDepthIncrease;1100 w.xSelectCallback2 = sqlite3WalkerDepthDecrease;1101 sqlite3WalkSelect(&w, pSub);1102 }1103 }1104 if( db->mallocFailed ) rc = SQLITE_NOMEM;1105 1106 /* Defer deleting the temporary table pTab because if an error occurred,1107 ** there could still be references to that table embedded in the1108 ** result-set or ORDER BY clause of the SELECT statement p. */1109 sqlite3ParserAddCleanup(pParse, sqlite3DbFree, pTab);1110 }1111 1112 assert( rc==SQLITE_OK || pParse->nErr!=0 );1113 return rc;1114}1115 1116/*1117** Unlink the Window object from the Select to which it is attached,1118** if it is attached.1119*/1120void sqlite3WindowUnlinkFromSelect(Window *p){1121 if( p->ppThis ){1122 *p->ppThis = p->pNextWin;1123 if( p->pNextWin ) p->pNextWin->ppThis = p->ppThis;1124 p->ppThis = 0;1125 }1126}1127 1128/*1129** Free the Window object passed as the second argument.1130*/1131void sqlite3WindowDelete(sqlite3 *db, Window *p){1132 if( p ){1133 sqlite3WindowUnlinkFromSelect(p);1134 sqlite3ExprDelete(db, p->pFilter);1135 sqlite3ExprListDelete(db, p->pPartition);1136 sqlite3ExprListDelete(db, p->pOrderBy);1137 sqlite3ExprDelete(db, p->pEnd);1138 sqlite3ExprDelete(db, p->pStart);1139 sqlite3DbFree(db, p->zName);1140 sqlite3DbFree(db, p->zBase);1141 sqlite3DbFree(db, p);1142 }1143}1144 1145/*1146** Free the linked list of Window objects starting at the second argument.1147*/1148void sqlite3WindowListDelete(sqlite3 *db, Window *p){1149 while( p ){1150 Window *pNext = p->pNextWin;1151 sqlite3WindowDelete(db, p);1152 p = pNext;1153 }1154}1155 1156/*1157** The argument expression is an PRECEDING or FOLLOWING offset. The1158** value should be a non-negative integer. If the value is not a1159** constant, change it to NULL. The fact that it is then a non-negative1160** integer will be caught later. But it is important not to leave1161** variable values in the expression tree.1162*/1163static Expr *sqlite3WindowOffsetExpr(Parse *pParse, Expr *pExpr){1164 if( 0==sqlite3ExprIsConstant(0,pExpr) ){1165 if( IN_RENAME_OBJECT ) sqlite3RenameExprUnmap(pParse, pExpr);1166 sqlite3ExprDelete(pParse->db, pExpr);1167 pExpr = sqlite3ExprAlloc(pParse->db, TK_NULL, 0, 0);1168 }1169 return pExpr;1170}1171 1172/*1173** Allocate and return a new Window object describing a Window Definition.1174*/1175Window *sqlite3WindowAlloc(1176 Parse *pParse, /* Parsing context */1177 int eType, /* Frame type. TK_RANGE, TK_ROWS, TK_GROUPS, or 0 */1178 int eStart, /* Start type: CURRENT, PRECEDING, FOLLOWING, UNBOUNDED */1179 Expr *pStart, /* Start window size if TK_PRECEDING or FOLLOWING */1180 int eEnd, /* End type: CURRENT, FOLLOWING, TK_UNBOUNDED, PRECEDING */1181 Expr *pEnd, /* End window size if TK_FOLLOWING or PRECEDING */1182 u8 eExclude /* EXCLUDE clause */1183){1184 Window *pWin = 0;1185 int bImplicitFrame = 0;1186 1187 /* Parser assures the following: */1188 assert( eType==0 || eType==TK_RANGE || eType==TK_ROWS || eType==TK_GROUPS );1189 assert( eStart==TK_CURRENT || eStart==TK_PRECEDING1190 || eStart==TK_UNBOUNDED || eStart==TK_FOLLOWING );1191 assert( eEnd==TK_CURRENT || eEnd==TK_FOLLOWING1192 || eEnd==TK_UNBOUNDED || eEnd==TK_PRECEDING );1193 assert( (eStart==TK_PRECEDING || eStart==TK_FOLLOWING)==(pStart!=0) );1194 assert( (eEnd==TK_FOLLOWING || eEnd==TK_PRECEDING)==(pEnd!=0) );1195 1196 if( eType==0 ){1197 bImplicitFrame = 1;1198 eType = TK_RANGE;1199 }1200