| /* |
| ** 2018 May 08 |
| ** |
| ** 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" |
| |
| #ifndef SQLITE_OMIT_WINDOWFUNC |
| |
| /* |
| ** SELECT REWRITING |
| ** |
| ** Any SELECT statement that contains one or more window functions in |
| ** either the select list or ORDER BY clause (the only two places window |
| ** functions may be used) is transformed by function sqlite3WindowRewrite() |
| ** in order to support window function processing. For example, with the |
| ** schema: |
| ** |
| ** CREATE TABLE t1(a, b, c, d, e, f, g); |
| ** |
| ** the statement: |
| ** |
| ** SELECT a+1, max(b) OVER (PARTITION BY c ORDER BY d) FROM t1 ORDER BY e; |
| ** |
| ** is transformed to: |
| ** |
| ** SELECT a+1, max(b) OVER (PARTITION BY c ORDER BY d) FROM ( |
| ** SELECT a, e, c, d, b FROM t1 ORDER BY c, d |
| ** ) ORDER BY e; |
| ** |
| ** The flattening optimization is disabled when processing this transformed |
| ** SELECT statement. This allows the implementation of the window function |
| ** (in this case max()) to process rows sorted in order of (c, d), which |
| ** makes things easier for obvious reasons. More generally: |
| ** |
| ** * FROM, WHERE, GROUP BY and HAVING clauses are all moved to |
| ** the sub-query. |
| ** |
| ** * ORDER BY, LIMIT and OFFSET remain part of the parent query. |
| ** |
| ** * Terminals from each of the expression trees that make up the |
| ** select-list and ORDER BY expressions in the parent query are |
| ** selected by the sub-query. For the purposes of the transformation, |
| ** terminals are column references and aggregate functions. |
| ** |
| ** If there is more than one window function in the SELECT that uses |
| ** the same window declaration (the OVER bit), then a single scan may |
| ** be used to process more than one window function. For example: |
| ** |
| ** SELECT max(b) OVER (PARTITION BY c ORDER BY d), |
| ** min(e) OVER (PARTITION BY c ORDER BY d) |
| ** FROM t1; |
| ** |
| ** is transformed in the same way as the example above. However: |
| ** |
| ** SELECT max(b) OVER (PARTITION BY c ORDER BY d), |
| ** min(e) OVER (PARTITION BY a ORDER BY b) |
| ** FROM t1; |
| ** |
| ** Must be transformed to: |
| ** |
| ** SELECT max(b) OVER (PARTITION BY c ORDER BY d) FROM ( |
| ** SELECT e, min(e) OVER (PARTITION BY a ORDER BY b), c, d, b FROM |
| ** SELECT a, e, c, d, b FROM t1 ORDER BY a, b |
| ** ) ORDER BY c, d |
| ** ) ORDER BY e; |
| ** |
| ** so that both min() and max() may process rows in the order defined by |
| ** their respective window declarations. |
| ** |
| ** INTERFACE WITH SELECT.C |
| ** |
| ** When processing the rewritten SELECT statement, code in select.c calls |
| ** sqlite3WhereBegin() to begin iterating through the results of the |
| ** sub-query, which is always implemented as a co-routine. It then calls |
| ** sqlite3WindowCodeStep() to process rows and finish the scan by calling |
| ** sqlite3WhereEnd(). |
| ** |
| ** sqlite3WindowCodeStep() generates VM code so that, for each row returned |
| ** by the sub-query a sub-routine (OP_Gosub) coded by select.c is invoked. |
| ** When the sub-routine is invoked: |
| ** |
| ** * The results of all window-functions for the row are stored |
| ** in the associated Window.regResult registers. |
| ** |
| ** * The required terminal values are stored in the current row of |
| ** temp table Window.iEphCsr. |
| ** |
| ** In some cases, depending on the window frame and the specific window |
| ** functions invoked, sqlite3WindowCodeStep() caches each entire partition |
| ** in a temp table before returning any rows. In other cases it does not. |
| ** This detail is encapsulated within this file, the code generated by |
| ** select.c is the same in either case. |
| ** |
| ** BUILT-IN WINDOW FUNCTIONS |
| ** |
| ** This implementation features the following built-in window functions: |
| ** |
| ** row_number() |
| ** rank() |
| ** dense_rank() |
| ** percent_rank() |
| ** cume_dist() |
| ** ntile(N) |
| ** lead(expr [, offset [, default]]) |
| ** lag(expr [, offset [, default]]) |
| ** first_value(expr) |
| ** last_value(expr) |
| ** nth_value(expr, N) |
| ** |
| ** These are the same built-in window functions supported by Postgres. |
| ** Although the behaviour of aggregate window functions (functions that |
| ** can be used as either aggregates or window funtions) allows them to |
| ** be implemented using an API, built-in window functions are much more |
| ** esoteric. Additionally, some window functions (e.g. nth_value()) |
| ** may only be implemented by caching the entire partition in memory. |
| ** As such, some built-in window functions use the same API as aggregate |
| ** window functions and some are implemented directly using VDBE |
| ** instructions. Additionally, for those functions that use the API, the |
| ** window frame is sometimes modified before the SELECT statement is |
| ** rewritten. For example, regardless of the specified window frame, the |
| ** row_number() function always uses: |
| ** |
| ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW |
| ** |
| ** See sqlite3WindowUpdate() for details. |
| ** |
| ** As well as some of the built-in window functions, aggregate window |
| ** functions min() and max() are implemented using VDBE instructions if |
| ** the start of the window frame is declared as anything other than |
| ** UNBOUNDED PRECEDING. |
| */ |
| |
| /* |
| ** Implementation of built-in window function row_number(). Assumes that the |
| ** window frame has been coerced to: |
| ** |
| ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW |
| */ |
| static void row_numberStepFunc( |
| sqlite3_context *pCtx, |
| int nArg, |
| sqlite3_value **apArg |
| ){ |
| i64 *p = (i64*)sqlite3_aggregate_context(pCtx, sizeof(*p)); |
| if( p ) (*p)++; |
| UNUSED_PARAMETER(nArg); |
| UNUSED_PARAMETER(apArg); |
| } |
| static void row_numberValueFunc(sqlite3_context *pCtx){ |
| i64 *p = (i64*)sqlite3_aggregate_context(pCtx, sizeof(*p)); |
| sqlite3_result_int64(pCtx, (p ? *p : 0)); |
| } |
| |
| /* |
| ** Context object type used by rank(), dense_rank(), percent_rank() and |
| ** cume_dist(). |
| */ |
| struct CallCount { |
| i64 nValue; |
| i64 nStep; |
| i64 nTotal; |
| }; |
| |
| /* |
| ** Implementation of built-in window function dense_rank(). Assumes that |
| ** the window frame has been set to: |
| ** |
| ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW |
| */ |
| static void dense_rankStepFunc( |
| sqlite3_context *pCtx, |
| int nArg, |
| sqlite3_value **apArg |
| ){ |
| struct CallCount *p; |
| p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p)); |
| if( p ) p->nStep = 1; |
| UNUSED_PARAMETER(nArg); |
| UNUSED_PARAMETER(apArg); |
| } |
| static void dense_rankValueFunc(sqlite3_context *pCtx){ |
| struct CallCount *p; |
| p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p)); |
| if( p ){ |
| if( p->nStep ){ |
| p->nValue++; |
| p->nStep = 0; |
| } |
| sqlite3_result_int64(pCtx, p->nValue); |
| } |
| } |
| |
| /* |
| ** Implementation of built-in window function nth_value(). This |
| ** implementation is used in "slow mode" only - when the EXCLUDE clause |
| ** is not set to the default value "NO OTHERS". |
| */ |
| struct NthValueCtx { |
| i64 nStep; |
| sqlite3_value *pValue; |
| }; |
| static void nth_valueStepFunc( |
| sqlite3_context *pCtx, |
| int nArg, |
| sqlite3_value **apArg |
| ){ |
| struct NthValueCtx *p; |
| p = (struct NthValueCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p)); |
| if( p ){ |
| i64 iVal; |
| switch( sqlite3_value_numeric_type(apArg[1]) ){ |
| case SQLITE_INTEGER: |
| iVal = sqlite3_value_int64(apArg[1]); |
| break; |
| case SQLITE_FLOAT: { |
| double fVal = sqlite3_value_double(apArg[1]); |
| if( ((i64)fVal)!=fVal ) goto error_out; |
| iVal = (i64)fVal; |
| break; |
| } |
| default: |
| goto error_out; |
| } |
| if( iVal<=0 ) goto error_out; |
| |
| p->nStep++; |
| if( iVal==p->nStep ){ |
| p->pValue = sqlite3_value_dup(apArg[0]); |
| if( !p->pValue ){ |
| sqlite3_result_error_nomem(pCtx); |
| } |
| } |
| } |
| UNUSED_PARAMETER(nArg); |
| UNUSED_PARAMETER(apArg); |
| return; |
| |
| error_out: |
| sqlite3_result_error( |
| pCtx, "second argument to nth_value must be a positive integer", -1 |
| ); |
| } |
| static void nth_valueFinalizeFunc(sqlite3_context *pCtx){ |
| struct NthValueCtx *p; |
| p = (struct NthValueCtx*)sqlite3_aggregate_context(pCtx, 0); |
| if( p && p->pValue ){ |
| sqlite3_result_value(pCtx, p->pValue); |
| sqlite3_value_free(p->pValue); |
| p->pValue = 0; |
| } |
| } |
| #define nth_valueInvFunc noopStepFunc |
| #define nth_valueValueFunc noopValueFunc |
| |
| static void first_valueStepFunc( |
| sqlite3_context *pCtx, |
| int nArg, |
| sqlite3_value **apArg |
| ){ |
| struct NthValueCtx *p; |
| p = (struct NthValueCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p)); |
| if( p && p->pValue==0 ){ |
| p->pValue = sqlite3_value_dup(apArg[0]); |
| if( !p->pValue ){ |
| sqlite3_result_error_nomem(pCtx); |
| } |
| } |
| UNUSED_PARAMETER(nArg); |
| UNUSED_PARAMETER(apArg); |
| } |
| static void first_valueFinalizeFunc(sqlite3_context *pCtx){ |
| struct NthValueCtx *p; |
| p = (struct NthValueCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p)); |
| if( p && p->pValue ){ |
| sqlite3_result_value(pCtx, p->pValue); |
| sqlite3_value_free(p->pValue); |
| p->pValue = 0; |
| } |
| } |
| #define first_valueInvFunc noopStepFunc |
| #define first_valueValueFunc noopValueFunc |
| |
| /* |
| ** Implementation of built-in window function rank(). Assumes that |
| ** the window frame has been set to: |
| ** |
| ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW |
| */ |
| static void rankStepFunc( |
| sqlite3_context *pCtx, |
| int nArg, |
| sqlite3_value **apArg |
| ){ |
| struct CallCount *p; |
| p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p)); |
| if( p ){ |
| p->nStep++; |
| if( p->nValue==0 ){ |
| p->nValue = p->nStep; |
| } |
| } |
| UNUSED_PARAMETER(nArg); |
| UNUSED_PARAMETER(apArg); |
| } |
| static void rankValueFunc(sqlite3_context *pCtx){ |
| struct CallCount *p; |
| p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p)); |
| if( p ){ |
| sqlite3_result_int64(pCtx, p->nValue); |
| p->nValue = 0; |
| } |
| } |
| |
| /* |
| ** Implementation of built-in window function percent_rank(). Assumes that |
| ** the window frame has been set to: |
| ** |
| ** GROUPS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING |
| */ |
| static void percent_rankStepFunc( |
| sqlite3_context *pCtx, |
| int nArg, |
| sqlite3_value **apArg |
| ){ |
| struct CallCount *p; |
| UNUSED_PARAMETER(nArg); assert( nArg==0 ); |
| UNUSED_PARAMETER(apArg); |
| p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p)); |
| if( p ){ |
| p->nTotal++; |
| } |
| } |
| static void percent_rankInvFunc( |
| sqlite3_context *pCtx, |
| int nArg, |
| sqlite3_value **apArg |
| ){ |
| struct CallCount *p; |
| UNUSED_PARAMETER(nArg); assert( nArg==0 ); |
| UNUSED_PARAMETER(apArg); |
| p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p)); |
| p->nStep++; |
| } |
| static void percent_rankValueFunc(sqlite3_context *pCtx){ |
| struct CallCount *p; |
| p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p)); |
| if( p ){ |
| p->nValue = p->nStep; |
| if( p->nTotal>1 ){ |
| double r = (double)p->nValue / (double)(p->nTotal-1); |
| sqlite3_result_double(pCtx, r); |
| }else{ |
| sqlite3_result_double(pCtx, 0.0); |
| } |
| } |
| } |
| #define percent_rankFinalizeFunc percent_rankValueFunc |
| |
| /* |
| ** Implementation of built-in window function cume_dist(). Assumes that |
| ** the window frame has been set to: |
| ** |
| ** GROUPS BETWEEN 1 FOLLOWING AND UNBOUNDED FOLLOWING |
| */ |
| static void cume_distStepFunc( |
| sqlite3_context *pCtx, |
| int nArg, |
| sqlite3_value **apArg |
| ){ |
| struct CallCount *p; |
| UNUSED_PARAMETER(nArg); assert( nArg==0 ); |
| UNUSED_PARAMETER(apArg); |
| p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p)); |
| if( p ){ |
| p->nTotal++; |
| } |
| } |
| static void cume_distInvFunc( |
| sqlite3_context *pCtx, |
| int nArg, |
| sqlite3_value **apArg |
| ){ |
| struct CallCount *p; |
| UNUSED_PARAMETER(nArg); assert( nArg==0 ); |
| UNUSED_PARAMETER(apArg); |
| p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p)); |
| p->nStep++; |
| } |
| static void cume_distValueFunc(sqlite3_context *pCtx){ |
| struct CallCount *p; |
| p = (struct CallCount*)sqlite3_aggregate_context(pCtx, 0); |
| if( p ){ |
| double r = (double)(p->nStep) / (double)(p->nTotal); |
| sqlite3_result_double(pCtx, r); |
| } |
| } |
| #define cume_distFinalizeFunc cume_distValueFunc |
| |
| /* |
| ** Context object for ntile() window function. |
| */ |
| struct NtileCtx { |
| i64 nTotal; /* Total rows in partition */ |
| i64 nParam; /* Parameter passed to ntile(N) */ |
| i64 iRow; /* Current row */ |
| }; |
| |
| /* |
| ** Implementation of ntile(). This assumes that the window frame has |
| ** been coerced to: |
| ** |
| ** ROWS CURRENT ROW AND UNBOUNDED FOLLOWING |
| */ |
| static void ntileStepFunc( |
| sqlite3_context *pCtx, |
| int nArg, |
| sqlite3_value **apArg |
| ){ |
| struct NtileCtx *p; |
| assert( nArg==1 ); UNUSED_PARAMETER(nArg); |
| p = (struct NtileCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p)); |
| if( p ){ |
| if( p->nTotal==0 ){ |
| p->nParam = sqlite3_value_int64(apArg[0]); |
| if( p->nParam<=0 ){ |
| sqlite3_result_error( |
| pCtx, "argument of ntile must be a positive integer", -1 |
| ); |
| } |
| } |
| p->nTotal++; |
| } |
| } |
| static void ntileInvFunc( |
| sqlite3_context *pCtx, |
| int nArg, |
| sqlite3_value **apArg |
| ){ |
| struct NtileCtx *p; |
| assert( nArg==1 ); UNUSED_PARAMETER(nArg); |
| UNUSED_PARAMETER(apArg); |
| p = (struct NtileCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p)); |
| p->iRow++; |
| } |
| static void ntileValueFunc(sqlite3_context *pCtx){ |
| struct NtileCtx *p; |
| p = (struct NtileCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p)); |
| if( p && p->nParam>0 ){ |
| int nSize = (p->nTotal / p->nParam); |
| if( nSize==0 ){ |
| sqlite3_result_int64(pCtx, p->iRow+1); |
| }else{ |
| i64 nLarge = p->nTotal - p->nParam*nSize; |
| i64 iSmall = nLarge*(nSize+1); |
| i64 iRow = p->iRow; |
| |
| assert( (nLarge*(nSize+1) + (p->nParam-nLarge)*nSize)==p->nTotal ); |
| |
| if( iRow<iSmall ){ |
| sqlite3_result_int64(pCtx, 1 + iRow/(nSize+1)); |
| }else{ |
| sqlite3_result_int64(pCtx, 1 + nLarge + (iRow-iSmall)/nSize); |
| } |
| } |
| } |
| } |
| #define ntileFinalizeFunc ntileValueFunc |
| |
| /* |
| ** Context object for last_value() window function. |
| */ |
| struct LastValueCtx { |
| sqlite3_value *pVal; |
| int nVal; |
| }; |
| |
| /* |
| ** Implementation of last_value(). |
| */ |
| static void last_valueStepFunc( |
| sqlite3_context *pCtx, |
| int nArg, |
| sqlite3_value **apArg |
| ){ |
| struct LastValueCtx *p; |
| UNUSED_PARAMETER(nArg); |
| p = (struct LastValueCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p)); |
| if( p ){ |
| sqlite3_value_free(p->pVal); |
| p->pVal = sqlite3_value_dup(apArg[0]); |
| if( p->pVal==0 ){ |
| sqlite3_result_error_nomem(pCtx); |
| }else{ |
| p->nVal++; |
| } |
| } |
| } |
| static void last_valueInvFunc( |
| sqlite3_context *pCtx, |
| int nArg, |
| sqlite3_value **apArg |
| ){ |
| struct LastValueCtx *p; |
| UNUSED_PARAMETER(nArg); |
| UNUSED_PARAMETER(apArg); |
| p = (struct LastValueCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p)); |
| if( ALWAYS(p) ){ |
| p->nVal--; |
| if( p->nVal==0 ){ |
| sqlite3_value_free(p->pVal); |
| p->pVal = 0; |
| } |
| } |
| } |
| static void last_valueValueFunc(sqlite3_context *pCtx){ |
| struct LastValueCtx *p; |
| p = (struct LastValueCtx*)sqlite3_aggregate_context(pCtx, 0); |
| if( p && p->pVal ){ |
| sqlite3_result_value(pCtx, p->pVal); |
| } |
| } |
| static void last_valueFinalizeFunc(sqlite3_context *pCtx){ |
| struct LastValueCtx *p; |
| p = (struct LastValueCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p)); |
| if( p && p->pVal ){ |
| sqlite3_result_value(pCtx, p->pVal); |
| sqlite3_value_free(p->pVal); |
| p->pVal = 0; |
| } |
| } |
| |
| /* |
| ** Static names for the built-in window function names. These static |
| ** names are used, rather than string literals, so that FuncDef objects |
| ** can be associated with a particular window function by direct |
| ** comparison of the zName pointer. Example: |
| ** |
| ** if( pFuncDef->zName==row_valueName ){ ... } |
| */ |
| static const char row_numberName[] = "row_number"; |
| static const char dense_rankName[] = "dense_rank"; |
| static const char rankName[] = "rank"; |
| static const char percent_rankName[] = "percent_rank"; |
| static const char cume_distName[] = "cume_dist"; |
| static const char ntileName[] = "ntile"; |
| static const char last_valueName[] = "last_value"; |
| static const char nth_valueName[] = "nth_value"; |
| static const char first_valueName[] = "first_value"; |
| static const char leadName[] = "lead"; |
| static const char lagName[] = "lag"; |
| |
| /* |
| ** No-op implementations of xStep() and xFinalize(). Used as place-holders |
| ** for built-in window functions that never call those interfaces. |
| ** |
| ** The noopValueFunc() is called but is expected to do nothing. The |
| ** noopStepFunc() is never called, and so it is marked with NO_TEST to |
| ** let the test coverage routine know not to expect this function to be |
| ** invoked. |
| */ |
| static void noopStepFunc( /*NO_TEST*/ |
| sqlite3_context *p, /*NO_TEST*/ |
| int n, /*NO_TEST*/ |
| sqlite3_value **a /*NO_TEST*/ |
| ){ /*NO_TEST*/ |
| UNUSED_PARAMETER(p); /*NO_TEST*/ |
| UNUSED_PARAMETER(n); /*NO_TEST*/ |
| UNUSED_PARAMETER(a); /*NO_TEST*/ |
| assert(0); /*NO_TEST*/ |
| } /*NO_TEST*/ |
| static void noopValueFunc(sqlite3_context *p){ UNUSED_PARAMETER(p); /*no-op*/ } |
| |
| /* Window functions that use all window interfaces: xStep, xFinal, |
| ** xValue, and xInverse */ |
| #define WINDOWFUNCALL(name,nArg,extra) { \ |
| nArg, (SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0, \ |
| name ## StepFunc, name ## FinalizeFunc, name ## ValueFunc, \ |
| name ## InvFunc, name ## Name, {0} \ |
| } |
| |
| /* Window functions that are implemented using bytecode and thus have |
| ** no-op routines for their methods */ |
| #define WINDOWFUNCNOOP(name,nArg,extra) { \ |
| nArg, (SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0, \ |
| noopStepFunc, noopValueFunc, noopValueFunc, \ |
| noopStepFunc, name ## Name, {0} \ |
| } |
| |
| /* Window functions that use all window interfaces: xStep, the |
| ** same routine for xFinalize and xValue and which never call |
| ** xInverse. */ |
| #define WINDOWFUNCX(name,nArg,extra) { \ |
| nArg, (SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0, \ |
| name ## StepFunc, name ## ValueFunc, name ## ValueFunc, \ |
| noopStepFunc, name ## Name, {0} \ |
| } |
| |
| |
| /* |
| ** Register those built-in window functions that are not also aggregates. |
| */ |
| void sqlite3WindowFunctions(void){ |
| static FuncDef aWindowFuncs[] = { |
| WINDOWFUNCX(row_number, 0, 0), |
| WINDOWFUNCX(dense_rank, 0, 0), |
| WINDOWFUNCX(rank, 0, 0), |
| WINDOWFUNCALL(percent_rank, 0, 0), |
| WINDOWFUNCALL(cume_dist, 0, 0), |
| WINDOWFUNCALL(ntile, 1, 0), |
| WINDOWFUNCALL(last_value, 1, 0), |
| WINDOWFUNCALL(nth_value, 2, 0), |
| WINDOWFUNCALL(first_value, 1, 0), |
| WINDOWFUNCNOOP(lead, 1, 0), |
| WINDOWFUNCNOOP(lead, 2, 0), |
| WINDOWFUNCNOOP(lead, 3, 0), |
| WINDOWFUNCNOOP(lag, 1, 0), |
| WINDOWFUNCNOOP(lag, 2, 0), |
| WINDOWFUNCNOOP(lag, 3, 0), |
| }; |
| sqlite3InsertBuiltinFuncs(aWindowFuncs, ArraySize(aWindowFuncs)); |
| } |
| |
| static Window *windowFind(Parse *pParse, Window *pList, const char *zName){ |
| Window *p; |
| for(p=pList; p; p=p->pNextWin){ |
| if( sqlite3StrICmp(p->zName, zName)==0 ) break; |
| } |
| if( p==0 ){ |
| sqlite3ErrorMsg(pParse, "no such window: %s", zName); |
| } |
| return p; |
| } |
| |
| /* |
| ** This function is called immediately after resolving the function name |
| ** for a window function within a SELECT statement. Argument pList is a |
| ** linked list of WINDOW definitions for the current SELECT statement. |
| ** Argument pFunc is the function definition just resolved and pWin |
| ** is the Window object representing the associated OVER clause. This |
| ** function updates the contents of pWin as follows: |
| ** |
| ** * If the OVER clause refered to a named window (as in "max(x) OVER win"), |
| ** search list pList for a matching WINDOW definition, and update pWin |
| ** accordingly. If no such WINDOW clause can be found, leave an error |
| ** in pParse. |
| ** |
| ** * If the function is a built-in window function that requires the |
| ** window to be coerced (see "BUILT-IN WINDOW FUNCTIONS" at the top |
| ** of this file), pWin is updated here. |
| */ |
| void sqlite3WindowUpdate( |
| Parse *pParse, |
| Window *pList, /* List of named windows for this SELECT */ |
| Window *pWin, /* Window frame to update */ |
| FuncDef *pFunc /* Window function definition */ |
| ){ |
| if( pWin->zName && pWin->eFrmType==0 ){ |
| Window *p = windowFind(pParse, pList, pWin->zName); |
| if( p==0 ) return; |
| pWin->pPartition = sqlite3ExprListDup(pParse->db, p->pPartition, 0); |
| pWin->pOrderBy = sqlite3ExprListDup(pParse->db, p->pOrderBy, 0); |
| pWin->pStart = sqlite3ExprDup(pParse->db, p->pStart, 0); |
| pWin->pEnd = sqlite3ExprDup(pParse->db, p->pEnd, 0); |
| pWin->eStart = p->eStart; |
| pWin->eEnd = p->eEnd; |
| pWin->eFrmType = p->eFrmType; |
| pWin->eExclude = p->eExclude; |
| }else{ |
| sqlite3WindowChain(pParse, pWin, pList); |
| } |
| if( (pWin->eFrmType==TK_RANGE) |
| && (pWin->pStart || pWin->pEnd) |
| && (pWin->pOrderBy==0 || pWin->pOrderBy->nExpr!=1) |
| ){ |
| sqlite3ErrorMsg(pParse, |
| "RANGE with offset PRECEDING/FOLLOWING requires one ORDER BY expression" |
| ); |
| }else |
| if( pFunc->funcFlags & SQLITE_FUNC_WINDOW ){ |
| sqlite3 *db = pParse->db; |
| if( pWin->pFilter ){ |
| sqlite3ErrorMsg(pParse, |
| "FILTER clause may only be used with aggregate window functions" |
| ); |
| }else{ |
| struct WindowUpdate { |
| const char *zFunc; |
| int eFrmType; |
| int eStart; |
| int eEnd; |
| } aUp[] = { |
| { row_numberName, TK_ROWS, TK_UNBOUNDED, TK_CURRENT }, |
| { dense_rankName, TK_RANGE, TK_UNBOUNDED, TK_CURRENT }, |
| { rankName, TK_RANGE, TK_UNBOUNDED, TK_CURRENT }, |
| { percent_rankName, TK_GROUPS, TK_CURRENT, TK_UNBOUNDED }, |
| { cume_distName, TK_GROUPS, TK_FOLLOWING, TK_UNBOUNDED }, |
| { ntileName, TK_ROWS, TK_CURRENT, TK_UNBOUNDED }, |
| { leadName, TK_ROWS, TK_UNBOUNDED, TK_UNBOUNDED }, |
| { lagName, TK_ROWS, TK_UNBOUNDED, TK_CURRENT }, |
| }; |
| int i; |
| for(i=0; i<ArraySize(aUp); i++){ |
| if( pFunc->zName==aUp[i].zFunc ){ |
| sqlite3ExprDelete(db, pWin->pStart); |
| sqlite3ExprDelete(db, pWin->pEnd); |
| pWin->pEnd = pWin->pStart = 0; |
| pWin->eFrmType = aUp[i].eFrmType; |
| pWin->eStart = aUp[i].eStart; |
| pWin->eEnd = aUp[i].eEnd; |
| pWin->eExclude = 0; |
| if( pWin->eStart==TK_FOLLOWING ){ |
| pWin->pStart = sqlite3Expr(db, TK_INTEGER, "1"); |
| } |
| break; |
| } |
| } |
| } |
| } |
| pWin->pFunc = pFunc; |
| } |
| |
| /* |
| ** Context object passed through sqlite3WalkExprList() to |
| ** selectWindowRewriteExprCb() by selectWindowRewriteEList(). |
| */ |
| typedef struct WindowRewrite WindowRewrite; |
| struct WindowRewrite { |
| Window *pWin; |
| SrcList *pSrc; |
| ExprList *pSub; |
| Select *pSubSelect; /* Current sub-select, if any */ |
| }; |
| |
| /* |
| ** Callback function used by selectWindowRewriteEList(). If necessary, |
| ** this function appends to the output expression-list and updates |
| ** expression (*ppExpr) in place. |
| */ |
| static int selectWindowRewriteExprCb(Walker *pWalker, Expr *pExpr){ |
| struct WindowRewrite *p = pWalker->u.pRewrite; |
| Parse *pParse = pWalker->pParse; |
| |
| /* If this function is being called from within a scalar sub-select |
| ** that used by the SELECT statement being processed, only process |
| ** TK_COLUMN expressions that refer to it (the outer SELECT). Do |
| ** not process aggregates or window functions at all, as they belong |
| ** to the scalar sub-select. */ |
| if( p->pSubSelect ){ |
| if( pExpr->op!=TK_COLUMN ){ |
| return WRC_Continue; |
| }else{ |
| int nSrc = p->pSrc->nSrc; |
| int i; |
| for(i=0; i<nSrc; i++){ |
| if( pExpr->iTable==p->pSrc->a[i].iCursor ) break; |
| } |
| if( i==nSrc ) return WRC_Continue; |
| } |
| } |
| |
| switch( pExpr->op ){ |
| |
| case TK_FUNCTION: |
| if( !ExprHasProperty(pExpr, EP_WinFunc) ){ |
| break; |
| }else{ |
| Window *pWin; |
| for(pWin=p->pWin; pWin; pWin=pWin->pNextWin){ |
| if( pExpr->y.pWin==pWin ){ |
| assert( pWin->pOwner==pExpr ); |
| return WRC_Prune; |
| } |
| } |
| } |
| /* Fall through. */ |
| |
| case TK_AGG_FUNCTION: |
| 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; |
| } |
| |
| default: /* no-op */ |
| break; |
| } |
| |
| return WRC_Continue; |
| } |
| static int selectWindowRewriteSelectCb(Walker *pWalker, Select *pSelect){ |
| struct WindowRewrite *p = pWalker->u.pRewrite; |
| Select *pSave = p->pSubSelect; |
| if( pSave==pSelect ){ |
| return WRC_Continue; |
| }else{ |
| p->pSubSelect = pSelect; |
| sqlite3WalkSelect(pWalker, pSelect); |
| p->pSubSelect = pSave; |
| } |
| return WRC_Prune; |
| } |
| |
| |
| /* |
| ** Iterate through each expression in expression-list pEList. For each: |
| ** |
| ** * TK_COLUMN, |
| ** * aggregate function, or |
| ** * window function with a Window object that is not a member of the |
| ** Window list passed as the second argument (pWin). |
| ** |
| ** Append the node to output expression-list (*ppSub). And replace it |
| ** with a TK_COLUMN that reads the (N-1)th element of table |
| ** pWin->iEphCsr, where N is the number of elements in (*ppSub) after |
| ** appending the new one. |
| */ |
| static void selectWindowRewriteEList( |
| Parse *pParse, |
| Window *pWin, |
| SrcList *pSrc, |
| ExprList *pEList, /* Rewrite expressions in this list */ |
| ExprList **ppSub /* IN/OUT: Sub-select expression-list */ |
| ){ |
| Walker sWalker; |
| WindowRewrite sRewrite; |
| |
| memset(&sWalker, 0, sizeof(Walker)); |
| memset(&sRewrite, 0, sizeof(WindowRewrite)); |
| |
| sRewrite.pSub = *ppSub; |
| sRewrite.pWin = pWin; |
| sRewrite.pSrc = pSrc; |
| |
| sWalker.pParse = pParse; |
| sWalker.xExprCallback = selectWindowRewriteExprCb; |
| sWalker.xSelectCallback = selectWindowRewriteSelectCb; |
| sWalker.u.pRewrite = &sRewrite; |
| |
| (void)sqlite3WalkExprList(&sWalker, pEList); |
| |
| *ppSub = sRewrite.pSub; |
| } |
| |
| /* |
| ** Append a copy of each expression in expression-list pAppend to |
| ** expression list pList. Return a pointer to the result list. |
| */ |
| 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 as described under "SELECT REWRITING" |
| ** at the top of this file. |
| */ |
| int sqlite3WindowRewrite(Parse *pParse, Select *p){ |
| int rc = SQLITE_OK; |
| if( p->pWin && p->pPrior==0 ){ |
| Vdbe *v = sqlite3GetVdbe(pParse); |
| 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 *pMWin = p->pWin; /* Master window object */ |
| Window *pWin; /* Window object iterator */ |
| |
| p->pSrc = 0; |
| p->pWhere = 0; |
| p->pGroupBy = 0; |
| p->pHaving = 0; |
| |
| /* Create the ORDER BY clause for the sub-select. This is the concatenation |
| ** of the window PARTITION and ORDER BY clauses. Then, if this makes it |
| ** redundant, remove the ORDER BY from the parent SELECT. */ |
| pSort = sqlite3ExprListDup(db, pMWin->pPartition, 0); |
| pSort = exprListAppendList(pParse, pSort, pMWin->pOrderBy); |
| if( pSort && p->pOrderBy ){ |
| if( sqlite3ExprListCompare(pSort, p->pOrderBy, -1)==0 ){ |
| sqlite3ExprListDelete(db, p->pOrderBy); |
| p->pOrderBy = 0; |
| } |
| } |
| |
| /* 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. */ |
| pMWin->iEphCsr = pParse->nTab++; |
| pParse->nTab += 3; |
| |
| selectWindowRewriteEList(pParse, pMWin, pSrc, p->pEList, &pSublist); |
| selectWindowRewriteEList(pParse, pMWin, pSrc, p->pOrderBy, &pSublist); |
| pMWin->nBufferCol = (pSublist ? pSublist->nExpr : 0); |
| |
| /* Append the PARTITION BY and ORDER BY expressions to the to the |
| ** sub-select expression list. They are required to figure out where |
| ** boundaries for partitions and sets of peer rows lie. */ |
| pSublist = exprListAppendList(pParse, pSublist, pMWin->pPartition); |
| pSublist = exprListAppendList(pParse, pSublist, pMWin->pOrderBy); |
| |
| /* Append the arguments passed to each window function to the |
| ** sub-select expression list. Also allocate two registers for each |
| ** window function - one for the accumulator, another for interim |
| ** results. */ |
| for(pWin=pMWin; pWin; pWin=pWin->pNextWin){ |
| pWin->iArgCol = (pSublist ? pSublist->nExpr : 0); |
| pSublist = exprListAppendList(pParse, pSublist, pWin->pOwner->x.pList); |
| if( pWin->pFilter ){ |
| Expr *pFilter = sqlite3ExprDup(db, pWin->pFilter, 0); |
| pSublist = sqlite3ExprListAppend(pParse, pSublist, pFilter); |
| } |
| pWin->regAccum = ++pParse->nMem; |
| pWin->regResult = ++pParse->nMem; |
| sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum); |
| } |
| |
| /* If there is no ORDER BY or PARTITION BY clause, and the window |
| ** function accepts zero arguments, and there are no other columns |
| ** selected (e.g. "SELECT row_number() OVER () FROM t1"), it is possible |
| ** that pSublist is still NULL here. Add a constant expression here to |
| ** keep everything legal in this case. |
| */ |
| if( pSublist==0 ){ |
| pSublist = sqlite3ExprListAppend(pParse, 0, |
| sqlite3ExprAlloc(db, TK_INTEGER, &sqlite3IntTokens[0], 0) |
| ); |
| } |
| |
| pSub = sqlite3SelectNew( |
| pParse, pSublist, pSrc, pWhere, pGroupBy, pHaving, pSort, 0, 0 |
| ); |
| p->pSrc = sqlite3SrcListAppend(pParse, 0, 0, 0); |
| if( p->pSrc ){ |
| p->pSrc->a[0].pSelect = pSub; |
| sqlite3SrcListAssignCursors(pParse, p->pSrc); |
| if( sqlite3ExpandSubquery(pParse, &p->pSrc->a[0]) ){ |
| rc = SQLITE_NOMEM; |
| }else{ |
| pSub->selFlags |= SF_Expanded; |
| p->selFlags &= ~SF_Aggregate; |
| sqlite3SelectPrep(pParse, pSub, 0); |
| } |
| |
| sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pMWin->iEphCsr, pSublist->nExpr); |
| sqlite3VdbeAddOp2(v, OP_OpenDup, pMWin->iEphCsr+1, pMWin->iEphCsr); |
| sqlite3VdbeAddOp2(v, OP_OpenDup, pMWin->iEphCsr+2, pMWin->iEphCsr); |
| sqlite3VdbeAddOp2(v, OP_OpenDup, pMWin->iEphCsr+3, pMWin->iEphCsr); |
| }else{ |
| sqlite3SelectDelete(db, pSub); |
| } |
| if( db->mallocFailed ) rc = SQLITE_NOMEM; |
| } |
| |
| return rc; |
| } |
| |
| /* |
| ** Free the Window object passed as the second argument. |
| */ |
| 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->zName); |
| sqlite3DbFree(db, p->zBase); |
| sqlite3DbFree(db, p); |
| } |
| } |
| |
| /* |
| ** Free the linked list of Window objects starting at the second argument. |
| */ |
| void sqlite3WindowListDelete(sqlite3 *db, Window *p){ |
| while( p ){ |
| Window *pNext = p->pNextWin; |
| sqlite3WindowDelete(db, p); |
| p = pNext; |
| } |
| } |
| |
| /* |
| ** The argument expression is an PRECEDING or FOLLOWING offset. The |
| ** value should be a non-negative integer. If the value is not a |
| ** constant, change it to NULL. The fact that it is then a non-negative |
| ** integer will be caught later. But it is important not to leave |
| ** variable values in the expression tree. |
| */ |
| static Expr *sqlite3WindowOffsetExpr(Parse *pParse, Expr *pExpr){ |
| if( 0==sqlite3ExprIsConstant(pExpr) ){ |
| if( IN_RENAME_OBJECT ) sqlite3RenameExprUnmap(pParse, pExpr); |
| sqlite3ExprDelete(pParse->db, pExpr); |
| pExpr = sqlite3ExprAlloc(pParse->db, TK_NULL, 0, 0); |
| } |
| return pExpr; |
| } |
| |
| /* |
| ** Allocate and return a new Window object describing a Window Definition. |
| */ |
| Window *sqlite3WindowAlloc( |
| Parse *pParse, /* Parsing context */ |
| int eType, /* Frame type. TK_RANGE, TK_ROWS, TK_GROUPS, or 0 */ |
| int eStart, /* Start type: CURRENT, PRECEDING, FOLLOWING, UNBOUNDED */ |
| Expr *pStart, /* Start window size if TK_PRECEDING or FOLLOWING */ |
| int eEnd, /* End type: CURRENT, FOLLOWING, TK_UNBOUNDED, PRECEDING */ |
| Expr *pEnd, /* End window size if TK_FOLLOWING or PRECEDING */ |
| u8 eExclude /* EXCLUDE clause */ |
| ){ |
| Window *pWin = 0; |
| int bImplicitFrame = 0; |
| |
| /* Parser assures the following: */ |
| assert( eType==0 || eType==TK_RANGE || eType==TK_ROWS || eType==TK_GROUPS ); |
| assert( eStart==TK_CURRENT || eStart==TK_PRECEDING |
| || eStart==TK_UNBOUNDED || eStart==TK_FOLLOWING ); |
| assert( eEnd==TK_CURRENT || eEnd==TK_FOLLOWING |
| || eEnd==TK_UNBOUNDED || eEnd==TK_PRECEDING ); |
| assert( (eStart==TK_PRECEDING || eStart==TK_FOLLOWING)==(pStart!=0) ); |
| assert( (eEnd==TK_FOLLOWING || eEnd==TK_PRECEDING)==(pEnd!=0) ); |
| |
| if( eType==0 ){ |
| bImplicitFrame = 1; |
| eType = TK_RANGE; |
| } |
| |
| /* Additionally, the |
| ** starting boundary type may not occur earlier in the following list than |
| ** the ending boundary type: |
| ** |
| ** UNBOUNDED PRECEDING |
| ** <expr> PRECEDING |
| ** CURRENT ROW |
| ** <expr> FOLLOWING |
| ** UNBOUNDED FOLLOWING |
| ** |
| ** The parser ensures that "UNBOUNDED PRECEDING" cannot be used as an ending |
| ** boundary, and than "UNBOUNDED FOLLOWING" cannot be used as a starting |
| ** frame boundary. |
| */ |
| if( (eStart==TK_CURRENT && eEnd==TK_PRECEDING) |
| || (eStart==TK_FOLLOWING && (eEnd==TK_PRECEDING || eEnd==TK_CURRENT)) |
| ){ |
| sqlite3ErrorMsg(pParse, "unsupported frame specification"); |
| goto windowAllocErr; |
| } |
| |
| pWin = (Window*)sqlite3DbMallocZero(pParse->db, sizeof(Window)); |
| if( pWin==0 ) goto windowAllocErr; |
| pWin->eFrmType = eType; |
| pWin->eStart = eStart; |
| pWin->eEnd = eEnd; |
| if( eExclude==0 && OptimizationDisabled(pParse->db, SQLITE_WindowFunc) ){ |
| eExclude = TK_NO; |
| } |
| pWin->eExclude = eExclude; |
| pWin->bImplicitFrame = bImplicitFrame; |
| pWin->pEnd = sqlite3WindowOffsetExpr(pParse, pEnd); |
| pWin->pStart = sqlite3WindowOffsetExpr(pParse, pStart); |
| return pWin; |
| |
| windowAllocErr: |
| sqlite3ExprDelete(pParse->db, pEnd); |
| sqlite3ExprDelete(pParse->db, pStart); |
| return 0; |
| } |
| |
| /* |
| ** Attach PARTITION and ORDER BY clauses pPartition and pOrderBy to window |
| ** pWin. Also, if parameter pBase is not NULL, set pWin->zBase to the |
| ** equivalent nul-terminated string. |
| */ |
| Window *sqlite3WindowAssemble( |
| Parse *pParse, |
| Window *pWin, |
| ExprList *pPartition, |
| ExprList *pOrderBy, |
| Token *pBase |
| ){ |
| if( pWin ){ |
| pWin->pPartition = pPartition; |
| pWin->pOrderBy = pOrderBy; |
| if( pBase ){ |
| pWin->zBase = sqlite3DbStrNDup(pParse->db, pBase->z, pBase->n); |
| } |
| }else{ |
| sqlite3ExprListDelete(pParse->db, pPartition); |
| sqlite3ExprListDelete(pParse->db, pOrderBy); |
| } |
| return pWin; |
| } |
| |
| /* |
| ** Window *pWin has just been created from a WINDOW clause. Tokne pBase |
| ** is the base window. Earlier windows from the same WINDOW clause are |
| ** stored in the linked list starting at pWin->pNextWin. This function |
| ** either updates *pWin according to the base specification, or else |
| ** leaves an error in pParse. |
| */ |
| void sqlite3WindowChain(Parse *pParse, Window *pWin, Window *pList){ |
| if( pWin->zBase ){ |
| sqlite3 *db = pParse->db; |
| Window *pExist = windowFind(pParse, pList, pWin->zBase); |
| if( pExist ){ |
| const char *zErr = 0; |
| /* Check for errors */ |
| if( pWin->pPartition ){ |
| zErr = "PARTITION clause"; |
| }else if( pExist->pOrderBy && pWin->pOrderBy ){ |
| zErr = "ORDER BY clause"; |
| }else if( pExist->bImplicitFrame==0 ){ |
| zErr = "frame specification"; |
| } |
| if( zErr ){ |
| sqlite3ErrorMsg(pParse, |
| "cannot override %s of window: %s", zErr, pWin->zBase |
| ); |
| }else{ |
| pWin->pPartition = sqlite3ExprListDup(db, pExist->pPartition, 0); |
| if( pExist->pOrderBy ){ |
| assert( pWin->pOrderBy==0 ); |
| pWin->pOrderBy = sqlite3ExprListDup(db, pExist->pOrderBy, 0); |
| } |
| sqlite3DbFree(db, pWin->zBase); |
| pWin->zBase = 0; |
| } |
| } |
| } |
| } |
| |
| /* |
| ** Attach window object pWin to expression p. |
| */ |
| void sqlite3WindowAttach(Parse *pParse, Expr *p, Window *pWin){ |
| if( p ){ |
| assert( p->op==TK_FUNCTION ); |
| /* This routine is only called for the parser. If pWin was not |
| ** allocated due to an OOM, then the parser would fail before ever |
| ** invoking this routine */ |
| if( ALWAYS(pWin) ){ |
| p->y.pWin = pWin; |
| ExprSetProperty(p, EP_WinFunc); |
| pWin->pOwner = p; |
| if( p->flags & EP_Distinct ){ |
| sqlite3ErrorMsg(pParse, |
| "DISTINCT is not supported for window functions"); |
| } |
| } |
| }else{ |
| sqlite3WindowDelete(pParse->db, pWin); |
| } |
| } |
| |
| /* |
| ** Return 0 if the two window objects are identical, or non-zero otherwise. |
| ** Identical window objects can be processed in a single scan. |
| */ |
| int sqlite3WindowCompare(Parse *pParse, Window *p1, Window *p2){ |
| if( p1->eFrmType!=p2->eFrmType ) return 1; |
| if( p1->eStart!=p2->eStart ) return 1; |
| if( p1->eEnd!=p2->eEnd ) return 1; |
| if( p1->eExclude!=p2->eExclude ) return 1; |
| if( sqlite3ExprCompare(pParse, p1->pStart, p2->pStart, -1) ) return 1; |
| if( sqlite3ExprCompare(pParse, p1->pEnd, p2->pEnd, -1) ) return 1; |
| if( sqlite3ExprListCompare(p1->pPartition, p2->pPartition, -1) ) return 1; |
| if( sqlite3ExprListCompare(p1->pOrderBy, p2->pOrderBy, -1) ) return 1; |
| return 0; |
| } |
| |
| |
| /* |
| ** This is called by code in select.c before it calls sqlite3WhereBegin() |
| ** to begin iterating through the sub-query results. It is used to allocate |
| ** and initialize registers and cursors used by sqlite3WindowCodeStep(). |
| */ |
| void sqlite3WindowCodeInit(Parse *pParse, Window *pMWin){ |
| Window *pWin; |
| Vdbe *v = sqlite3GetVdbe(pParse); |
| |
| /* Allocate registers to use for PARTITION BY values, if any. Initialize |
| ** said registers to NULL. */ |
| if( pMWin->pPartition ){ |
| int nExpr = pMWin->pPartition->nExpr; |
| pMWin->regPart = pParse->nMem+1; |
| pParse->nMem += nExpr; |
| sqlite3VdbeAddOp3(v, OP_Null, 0, pMWin->regPart, pMWin->regPart+nExpr-1); |
| } |
| |
| pMWin->regOne = ++pParse->nMem; |
| sqlite3VdbeAddOp2(v, OP_Integer, 1, pMWin->regOne); |
| |
| if( pMWin->eExclude ){ |
| pMWin->regStartRowid = ++pParse->nMem; |
| pMWin->regEndRowid = ++pParse->nMem; |
| pMWin->csrApp = pParse->nTab++; |
| sqlite3VdbeAddOp2(v, OP_Integer, 1, pMWin->regStartRowid); |
| sqlite3VdbeAddOp2(v, OP_Integer, 0, pMWin->regEndRowid); |
| sqlite3VdbeAddOp2(v, OP_OpenDup, pMWin->csrApp, pMWin->iEphCsr); |
| return; |
| } |
| |
| for(pWin=pMWin; pWin; pWin=pWin->pNextWin){ |
| FuncDef *p = pWin->pFunc; |
| if( (p->funcFlags & SQLITE_FUNC_MINMAX) && pWin->eStart!=TK_UNBOUNDED ){ |
| /* The inline versions of min() and max() require a single ephemeral |
| ** table and 3 registers. The registers are used as follows: |
| ** |
| ** regApp+0: slot to copy min()/max() argument to for MakeRecord |
| ** regApp+1: integer value used to ensure keys are unique |
| ** regApp+2: output of MakeRecord |
| */ |
| ExprList *pList = pWin->pOwner->x.pList; |
| KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pList, 0, 0); |
| pWin->csrApp = pParse->nTab++; |
| pWin->regApp = pParse->nMem+1; |
| pParse->nMem += 3; |
| if( pKeyInfo && pWin->pFunc->zName[1]=='i' ){ |
| assert( pKeyInfo->aSortOrder[0]==0 ); |
| pKeyInfo->aSortOrder[0] = 1; |
| } |
| sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pWin->csrApp, 2); |
| sqlite3VdbeAppendP4(v, pKeyInfo, P4_KEYINFO); |
| sqlite3VdbeAddOp2(v, OP_Integer, 0, pWin->regApp+1); |
| } |
| else if( p->zName==nth_valueName || p->zName==first_valueName ){ |
| /* Allocate two registers at pWin->regApp. These will be used to |
| ** store the start and end index of the current frame. */ |
| pWin->regApp = pParse->nMem+1; |
| pWin->csrApp = pParse->nTab++; |
| pParse->nMem += 2; |
| sqlite3VdbeAddOp2(v, OP_OpenDup, pWin->csrApp, pMWin->iEphCsr); |
| } |
| else if( p->zName==leadName || p->zName==lagName ){ |
| pWin->csrApp = pParse->nTab++; |
| sqlite3VdbeAddOp2(v, OP_OpenDup, pWin->csrApp, pMWin->iEphCsr); |
| } |
| } |
| } |
| |
| #define WINDOW_STARTING_INT 0 |
| #define WINDOW_ENDING_INT 1 |
| #define WINDOW_NTH_VALUE_INT 2 |
| #define WINDOW_STARTING_NUM 3 |
| #define WINDOW_ENDING_NUM 4 |
| |
| /* |
| ** A "PRECEDING <expr>" (eCond==0) or "FOLLOWING <expr>" (eCond==1) or the |
| ** value of the second argument to nth_value() (eCond==2) has just been |
| ** evaluated and the result left in register reg. This function generates VM |
| ** code to check that the value is a non-negative integer and throws an |
| ** exception if it is not. |
| */ |
| static void windowCheckValue(Parse *pParse, int reg, int eCond){ |
| static const char *azErr[] = { |
| "frame starting offset must be a non-negative integer", |
| "frame ending offset must be a non-negative integer", |
| "second argument to nth_value must be a positive integer", |
| "frame starting offset must be a non-negative number", |
| "frame ending offset must be a non-negative number", |
| }; |
| static int aOp[] = { OP_Ge, OP_Ge, OP_Gt, OP_Ge, OP_Ge }; |
| Vdbe *v = sqlite3GetVdbe(pParse); |
| int regZero = sqlite3GetTempReg(pParse); |
| assert( eCond>=0 && eCond<ArraySize(azErr) ); |
| sqlite3VdbeAddOp2(v, OP_Integer, 0, regZero); |
| if( eCond>=WINDOW_STARTING_NUM ){ |
| int regString = sqlite3GetTempReg(pParse); |
| sqlite3VdbeAddOp4(v, OP_String8, 0, regString, 0, "", P4_STATIC); |
| sqlite3VdbeAddOp3(v, OP_Ge, regString, sqlite3VdbeCurrentAddr(v)+2, reg); |
| sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC|SQLITE_JUMPIFNULL); |
| VdbeCoverage(v); |
| assert( eCond==3 || eCond==4 ); |
| VdbeCoverageIf(v, eCond==3); |
| VdbeCoverageIf(v, eCond==4); |
| }else{ |
| sqlite3VdbeAddOp2(v, OP_MustBeInt, reg, sqlite3VdbeCurrentAddr(v)+2); |
| VdbeCoverage(v); |
| assert( eCond==0 || eCond==1 || eCond==2 ); |
| VdbeCoverageIf(v, eCond==0); |
| VdbeCoverageIf(v, eCond==1); |
| VdbeCoverageIf(v, eCond==2); |
| } |
| sqlite3VdbeAddOp3(v, aOp[eCond], regZero, sqlite3VdbeCurrentAddr(v)+2, reg); |
| VdbeCoverageNeverNullIf(v, eCond==0); /* NULL case captured by */ |
| VdbeCoverageNeverNullIf(v, eCond==1); /* the OP_MustBeInt */ |
| VdbeCoverageNeverNullIf(v, eCond==2); |
| VdbeCoverageNeverNullIf(v, eCond==3); /* NULL case caught by */ |
| VdbeCoverageNeverNullIf(v, eCond==4); /* the OP_Ge */ |
| sqlite3MayAbort(pParse); |
| sqlite3VdbeAddOp2(v, OP_Halt, SQLITE_ERROR, OE_Abort); |
| sqlite3VdbeAppendP4(v, (void*)azErr[eCond], P4_STATIC); |
| sqlite3ReleaseTempReg(pParse, regZero); |
| } |
| |
| /* |
| ** Return the number of arguments passed to the window-function associated |
| ** with the object passed as the only argument to this function. |
| */ |
| static int windowArgCount(Window *pWin){ |
| ExprList *pList = pWin->pOwner->x.pList; |
| return (pList ? pList->nExpr : 0); |
| } |
| |
| /* |
| ** Generate VM code to invoke either xStep() (if bInverse is 0) or |
| ** xInverse (if bInverse is non-zero) for each window function in the |
| ** linked list starting at pMWin. Or, for built-in window functions |
| ** that do not use the standard function API, generate the required |
| ** inline VM code. |
| ** |
| ** If argument csr is greater than or equal to 0, then argument reg is |
| ** the first register in an array of registers guaranteed to be large |
| ** enough to hold the array of arguments for each function. In this case |
| ** the arguments are extracted from the current row of csr into the |
| ** array of registers before invoking OP_AggStep or OP_AggInverse |
| ** |
| ** Or, if csr is less than zero, then the array of registers at reg is |
| ** already populated with all columns from the current row of the sub-query. |
| ** |
| ** If argument regPartSize is non-zero, then it is a register containing the |
| ** number of rows in the current partition. |
| */ |
| static void windowAggStep( |
| Parse *pParse, |
| Window *pMWin, /* Linked list of window functions */ |
| int csr, /* Read arguments from this cursor */ |
| int bInverse, /* True to invoke xInverse instead of xStep */ |
| int reg /* Array of registers */ |
| ){ |
| Vdbe *v = sqlite3GetVdbe(pParse); |
| Window *pWin; |
| for(pWin=pMWin; pWin; pWin=pWin->pNextWin){ |
| FuncDef *pFunc = pWin->pFunc; |
| int regArg; |
| int nArg = windowArgCount(pWin); |
| int i; |
| |
| for(i=0; i<nArg; i++){ |
| if( i!=1 || pFunc->zName!=nth_valueName ){ |
| sqlite3VdbeAddOp3(v, OP_Column, csr, pWin->iArgCol+i, reg+i); |
| }else{ |
| sqlite3VdbeAddOp3(v, OP_Column, pMWin->iEphCsr, pWin->iArgCol+i, reg+i); |
| } |
| } |
| regArg = reg; |
| |
| if( pMWin->regStartRowid==0 |
| && (pFunc->funcFlags & SQLITE_FUNC_MINMAX) |
| && (pWin->eStart!=TK_UNBOUNDED) |
| ){ |
| int addrIsNull = sqlite3VdbeAddOp1(v, OP_IsNull, regArg); |
| VdbeCoverage(v); |
| if( bInverse==0 ){ |
| sqlite3VdbeAddOp2(v, OP_AddImm, pWin->regApp+1, 1); |
| sqlite3VdbeAddOp2(v, OP_SCopy, regArg, pWin->regApp); |
| sqlite3VdbeAddOp3(v, OP_MakeRecord, pWin->regApp, 2, pWin->regApp+2); |
| sqlite3VdbeAddOp2(v, OP_IdxInsert, pWin->csrApp, pWin->regApp+2); |
| }else{ |
| sqlite3VdbeAddOp4Int(v, OP_SeekGE, pWin->csrApp, 0, regArg, 1); |
| VdbeCoverageNeverTaken(v); |
| sqlite3VdbeAddOp1(v, OP_Delete, pWin->csrApp); |
| sqlite3VdbeJumpHere(v, sqlite3VdbeCurrentAddr(v)-2); |
| } |
| sqlite3VdbeJumpHere(v, addrIsNull); |
| }else if( pWin->regApp ){ |
| assert( pFunc->zName==nth_valueName |
| || pFunc->zName==first_valueName |
| ); |
| assert( bInverse==0 || bInverse==1 ); |
| sqlite3VdbeAddOp2(v, OP_AddImm, pWin->regApp+1-bInverse, 1); |
| }else if( pFunc->xSFunc!=noopStepFunc ){ |
| int addrIf = 0; |
| if( pWin->pFilter ){ |
| int regTmp; |
| assert( nArg==0 || nArg==pWin->pOwner->x.pList->nExpr ); |
| assert( nArg || pWin->pOwner->x.pList==0 ); |
| regTmp = sqlite3GetTempReg(pParse); |
| sqlite3VdbeAddOp3(v, OP_Column, csr, pWin->iArgCol+nArg,regTmp); |
| addrIf = sqlite3VdbeAddOp3(v, OP_IfNot, regTmp, 0, 1); |
| VdbeCoverage(v); |
| sqlite3ReleaseTempReg(pParse, regTmp); |
| } |
| if( pFunc->funcFlags & SQLITE_FUNC_NEEDCOLL ){ |
| CollSeq *pColl; |
| assert( nArg>0 ); |
| pColl = sqlite3ExprNNCollSeq(pParse, pWin->pOwner->x.pList->a[0].pExpr); |
| sqlite3VdbeAddOp4(v, OP_CollSeq, 0,0,0, (const char*)pColl, P4_COLLSEQ); |
| } |
| sqlite3VdbeAddOp3(v, bInverse? OP_AggInverse : OP_AggStep, |
| bInverse, regArg, pWin->regAccum); |
| sqlite3VdbeAppendP4(v, pFunc, P4_FUNCDEF); |
| sqlite3VdbeChangeP5(v, (u8)nArg); |
| if( addrIf ) sqlite3VdbeJumpHere(v, addrIf); |
| } |
| } |
| } |
| |
| typedef struct WindowCodeArg WindowCodeArg; |
| typedef struct WindowCsrAndReg WindowCsrAndReg; |
| struct WindowCsrAndReg { |
| int csr; |
| int reg; |
| }; |
| |
| struct WindowCodeArg { |
| Parse *pParse; |
| Window *pMWin; |
| Vdbe *pVdbe; |
| int regGosub; |
| int addrGosub; |
| int regArg; |
| int eDelete; |
| |
| WindowCsrAndReg start; |
| WindowCsrAndReg current; |
| WindowCsrAndReg end; |
| }; |
| |
| /* |
| ** Values that may be passed as the second argument to windowCodeOp(). |
| */ |
| #define WINDOW_RETURN_ROW 1 |
| #define WINDOW_AGGINVERSE 2 |
| #define WINDOW_AGGSTEP 3 |
| |
| /* |
| ** Generate VM code to read the window frames peer values from cursor csr into |
| ** an array of registers starting at reg. |
| */ |
| static void windowReadPeerValues( |
| WindowCodeArg *p, |
| int csr, |
| int reg |
| ){ |
| Window *pMWin = p->pMWin; |
| ExprList *pOrderBy = pMWin->pOrderBy; |
| if( pOrderBy ){ |
| Vdbe *v = sqlite3GetVdbe(p->pParse); |
| ExprList *pPart = pMWin->pPartition; |
| int iColOff = pMWin->nBufferCol + (pPart ? pPart->nExpr : 0); |
| int i; |
| for(i=0; i<pOrderBy->nExpr; i++){ |
| sqlite3VdbeAddOp3(v, OP_Column, csr, iColOff+i, reg+i); |
| } |
| } |
| } |
| |
| /* |
| ** Generate VM code to invoke either xValue() (bFin==0) or xFinalize() |
| ** (bFin==1) for each window function in the linked list starting at |
| ** pMWin. Or, for built-in window-functions that do not use the standard |
| ** API, generate the equivalent VM code. |
| */ |
| static void windowAggFinal(WindowCodeArg *p, int bFin){ |
| Parse *pParse = p->pParse; |
| Window *pMWin = p->pMWin; |
| Vdbe *v = sqlite3GetVdbe(pParse); |
| Window *pWin; |
| |
| for(pWin=pMWin; pWin; pWin=pWin->pNextWin){ |
| if( pMWin->regStartRowid==0 |
| && (pWin->pFunc->funcFlags & SQLITE_FUNC_MINMAX) |
| && (pWin->eStart!=TK_UNBOUNDED) |
| ){ |
| sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regResult); |
| sqlite3VdbeAddOp1(v, OP_Last, pWin->csrApp); |
| VdbeCoverage(v); |
| sqlite3VdbeAddOp3(v, OP_Column, pWin->csrApp, 0, pWin->regResult); |
| sqlite3VdbeJumpHere(v, sqlite3VdbeCurrentAddr(v)-2); |
| }else if( pWin->regApp ){ |
| assert( pMWin->regStartRowid==0 ); |
| }else{ |
| int nArg = windowArgCount(pWin); |
| if( bFin ){ |
| sqlite3VdbeAddOp2(v, OP_AggFinal, pWin->regAccum, nArg); |
| sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF); |
| sqlite3VdbeAddOp2(v, OP_Copy, pWin->regAccum, pWin->regResult); |
| sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum); |
| }else{ |
| sqlite3VdbeAddOp3(v, OP_AggValue,pWin->regAccum,nArg,pWin->regResult); |
| sqlite3VdbeAppendP4(v, pWin->pFunc, P4_FUNCDEF); |
| } |
| } |
| } |
| } |
| |
| /* |
| ** Generate code to calculate the current values of all window functions in the |
| ** p->pMWin list by doing a full scan of the current window frame. Store the |
| ** results in the Window.regResult registers, ready to return the upper |
| ** layer. |
| */ |
| static void windowFullScan(WindowCodeArg *p){ |
| Window *pWin; |
| Parse *pParse = p->pParse; |
| Window *pMWin = p->pMWin; |
| Vdbe *v = p->pVdbe; |
| |
| int regCRowid = 0; /* Current rowid value */ |
| int regCPeer = 0; /* Current peer values */ |
| int regRowid = 0; /* AggStep rowid value */ |
| int regPeer = 0; /* AggStep peer values */ |
| |
| int nPeer; |
| int lblNext; |
| int lblBrk; |
| int addrNext; |
| int csr = pMWin->csrApp; |
| |
| nPeer = (pMWin->pOrderBy ? pMWin->pOrderBy->nExpr : 0); |
| |
| lblNext = sqlite3VdbeMakeLabel(pParse); |
| lblBrk = sqlite3VdbeMakeLabel(pParse); |
| |
| regCRowid = sqlite3GetTempReg(pParse); |
| regRowid = sqlite3GetTempReg(pParse); |
| if( nPeer ){ |
| regCPeer = sqlite3GetTempRange(pParse, nPeer); |
| regPeer = sqlite3GetTempRange(pParse, nPeer); |
| } |
| |
| sqlite3VdbeAddOp2(v, OP_Rowid, pMWin->iEphCsr, regCRowid); |
| windowReadPeerValues(p, pMWin->iEphCsr, regCPeer); |
| |
| for(pWin=pMWin; pWin; pWin=pWin->pNextWin){ |
| sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum); |
| } |
| |
| sqlite3VdbeAddOp3(v, OP_SeekGE, csr, lblBrk, pMWin->regStartRowid); |
| VdbeCoverage(v); |
| addrNext = sqlite3VdbeCurrentAddr(v); |
| sqlite3VdbeAddOp2(v, OP_Rowid, csr, regRowid); |
| sqlite3VdbeAddOp3(v, OP_Gt, pMWin->regEndRowid, lblBrk, regRowid); |
| VdbeCoverageNeverNull(v); |
| |
| if( pMWin->eExclude==TK_CURRENT ){ |
| sqlite3VdbeAddOp3(v, OP_Eq, regCRowid, lblNext, regRowid); |
| VdbeCoverageNeverNull(v); |
| }else if( pMWin->eExclude!=TK_NO ){ |
| int addr; |
| int addrEq = 0; |
| KeyInfo *pKeyInfo = 0; |
| |
| if( pMWin->pOrderBy ){ |
| pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pMWin->pOrderBy, 0, 0); |
| } |
| if( pMWin->eExclude==TK_TIES ){ |
| addrEq = sqlite3VdbeAddOp3(v, OP_Eq, regCRowid, 0, regRowid); |
| VdbeCoverageNeverNull(v); |
| } |
| if( pKeyInfo ){ |
| windowReadPeerValues(p, csr, regPeer); |
| sqlite3VdbeAddOp3(v, OP_Compare, regPeer, regCPeer, nPeer); |
| sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO); |
| addr = sqlite3VdbeCurrentAddr(v)+1; |
| sqlite3VdbeAddOp3(v, OP_Jump, addr, lblNext, addr); |
| VdbeCoverageEqNe(v); |
| }else{ |
| sqlite3VdbeAddOp2(v, OP_Goto, 0, lblNext); |
| } |
| if( addrEq ) sqlite3VdbeJumpHere(v, addrEq); |
| } |
| |
| windowAggStep(pParse, pMWin, csr, 0, p->regArg); |
| |
| sqlite3VdbeResolveLabel(v, lblNext); |
| sqlite3VdbeAddOp2(v, OP_Next, csr, addrNext); |
| VdbeCoverage(v); |
| sqlite3VdbeJumpHere(v, addrNext-1); |
| sqlite3VdbeJumpHere(v, addrNext+1); |
| sqlite3ReleaseTempReg(pParse, regRowid); |
| sqlite3ReleaseTempReg(pParse, regCRowid); |
| if( nPeer ){ |
| sqlite3ReleaseTempRange(pParse, regPeer, nPeer); |
| sqlite3ReleaseTempRange(pParse, regCPeer, nPeer); |
| } |
| |
| windowAggFinal(p, 1); |
| } |
| |
| /* |
| ** Invoke the sub-routine at regGosub (generated by code in select.c) to |
| ** return the current row of Window.iEphCsr. If all window functions are |
| ** aggregate window functions that use the standard API, a single |
| ** OP_Gosub instruction is all that this routine generates. Extra VM code |
| ** for per-row processing is only generated for the following built-in window |
| ** functions: |
| ** |
| ** nth_value() |
| ** first_value() |
| ** lag() |
| ** lead() |
| */ |
| static void windowReturnOneRow(WindowCodeArg *p){ |
| Window *pMWin = p->pMWin; |
| Vdbe *v = p->pVdbe; |
| |
| if( pMWin->regStartRowid ){ |
| windowFullScan(p); |
| }else{ |
| Parse *pParse = p->pParse; |
| Window *pWin; |
| |
| for(pWin=pMWin; pWin; pWin=pWin->pNextWin){ |
| FuncDef *pFunc = pWin->pFunc; |
| if( pFunc->zName==nth_valueName |
| || pFunc->zName==first_valueName |
| ){ |
| int csr = pWin->csrApp; |
| int lbl = sqlite3VdbeMakeLabel(pParse); |
| int tmpReg = sqlite3GetTempReg(pParse); |
| sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regResult); |
| |
| if( pFunc->zName==nth_valueName ){ |
| sqlite3VdbeAddOp3(v, OP_Column,pMWin->iEphCsr,pWin->iArgCol+1,tmpReg); |
| windowCheckValue(pParse, tmpReg, 2); |
| }else{ |
| sqlite3VdbeAddOp2(v, OP_Integer, 1, tmpReg); |
| } |
| sqlite3VdbeAddOp3(v, OP_Add, tmpReg, pWin->regApp, tmpReg); |
| sqlite3VdbeAddOp3(v, OP_Gt, pWin->regApp+1, lbl, tmpReg); |
| VdbeCoverageNeverNull(v); |
| sqlite3VdbeAddOp3(v, OP_SeekRowid, csr, 0, tmpReg); |
| VdbeCoverageNeverTaken(v); |
| sqlite3VdbeAddOp3(v, OP_Column, csr, pWin->iArgCol, pWin->regResult); |
| sqlite3VdbeResolveLabel(v, lbl); |
| sqlite3ReleaseTempReg(pParse, tmpReg); |
| } |
| else if( pFunc->zName==leadName || pFunc->zName==lagName ){ |
| int nArg = pWin->pOwner->x.pList->nExpr; |
| int csr = pWin->csrApp; |
| int lbl = sqlite3VdbeMakeLabel(pParse); |
| int tmpReg = sqlite3GetTempReg(pParse); |
| int iEph = pMWin->iEphCsr; |
| |
| if( nArg<3 ){ |
| sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regResult); |
| }else{ |
| sqlite3VdbeAddOp3(v, OP_Column, iEph,pWin->iArgCol+2,pWin->regResult); |
| } |
| sqlite3VdbeAddOp2(v, OP_Rowid, iEph, tmpReg); |
| if( nArg<2 ){ |
| int val = (pFunc->zName==leadName ? 1 : -1); |
| sqlite3VdbeAddOp2(v, OP_AddImm, tmpReg, val); |
| }else{ |
| int op = (pFunc->zName==leadName ? OP_Add : OP_Subtract); |
| int tmpReg2 = sqlite3GetTempReg(pParse); |
| sqlite3VdbeAddOp3(v, OP_Column, iEph, pWin->iArgCol+1, tmpReg2); |
| sqlite3VdbeAddOp3(v, op, tmpReg2, tmpReg, tmpReg); |
| sqlite3ReleaseTempReg(pParse, tmpReg2); |
| } |
| |
| sqlite3VdbeAddOp3(v, OP_SeekRowid, csr, lbl, tmpReg); |
| VdbeCoverage(v); |
| sqlite3VdbeAddOp3(v, OP_Column, csr, pWin->iArgCol, pWin->regResult); |
| sqlite3VdbeResolveLabel(v, lbl); |
| sqlite3ReleaseTempReg(pParse, tmpReg); |
| } |
| } |
| } |
| sqlite3VdbeAddOp2(v, OP_Gosub, p->regGosub, p->addrGosub); |
| } |
| |
| /* |
| ** Generate code to set the accumulator register for each window function |
| ** in the linked list passed as the second argument to NULL. And perform |
| ** any equivalent initialization required by any built-in window functions |
| ** in the list. |
| */ |
| static int windowInitAccum(Parse *pParse, Window *pMWin){ |
| Vdbe *v = sqlite3GetVdbe(pParse); |
| int regArg; |
| int nArg = 0; |
| Window *pWin; |
| for(pWin=pMWin; pWin; pWin=pWin->pNextWin){ |
| FuncDef *pFunc = pWin->pFunc; |
| sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum); |
| nArg = MAX(nArg, windowArgCount(pWin)); |
| if( pMWin->regStartRowid==0 ){ |
| if( pFunc->zName==nth_valueName || pFunc->zName==first_valueName ){ |
| sqlite3VdbeAddOp2(v, OP_Integer, 0, pWin->regApp); |
| sqlite3VdbeAddOp2(v, OP_Integer, 0, pWin->regApp+1); |
| } |
| |
| if( (pFunc->funcFlags & SQLITE_FUNC_MINMAX) && pWin->csrApp ){ |
| assert( pWin->eStart!=TK_UNBOUNDED ); |
| sqlite3VdbeAddOp1(v, OP_ResetSorter, pWin->csrApp); |
| sqlite3VdbeAddOp2(v, OP_Integer, 0, pWin->regApp+1); |
| } |
| } |
| } |
| regArg = pParse->nMem+1; |
| pParse->nMem += nArg; |
| return regArg; |
| } |
| |
| /* |
| ** Return true if the current frame should be cached in the ephemeral table, |
| ** even if there are no xInverse() calls required. |
| */ |
| static int windowCacheFrame(Window *pMWin){ |
| Window *pWin; |
| if( pMWin->regStartRowid ) return 1; |
| for(pWin=pMWin; pWin; pWin=pWin->pNextWin){ |
| FuncDef *pFunc = pWin->pFunc; |
| if( (pFunc->zName==nth_valueName) |
| || (pFunc->zName==first_valueName) |
| || (pFunc->zName==leadName) |
| || (pFunc->zName==lagName) |
| ){ |
| return 1; |
| } |
| } |
| return 0; |
| } |
| |
| /* |
| ** regOld and regNew are each the first register in an array of size |
| ** pOrderBy->nExpr. This function generates code to compare the two |
| ** arrays of registers using the collation sequences and other comparison |
| ** parameters specified by pOrderBy. |
| ** |
| ** If the two arrays are not equal, the contents of regNew is copied to |
| ** regOld and control falls through. Otherwise, if the contents of the arrays |
| ** are equal, an OP_Goto is executed. The address of the OP_Goto is returned. |
| */ |
| static void windowIfNewPeer( |
| Parse *pParse, |
| ExprList *pOrderBy, |
| int regNew, /* First in array of new values */ |
| int regOld, /* First in array of old values */ |
| int addr /* Jump here */ |
| ){ |
| Vdbe *v = sqlite3GetVdbe(pParse); |
| if( pOrderBy ){ |
| int nVal = pOrderBy->nExpr; |
| KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pOrderBy, 0, 0); |
| sqlite3VdbeAddOp3(v, OP_Compare, regOld, regNew, nVal); |
| sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO); |
| sqlite3VdbeAddOp3(v, OP_Jump, |
| sqlite3VdbeCurrentAddr(v)+1, addr, sqlite3VdbeCurrentAddr(v)+1 |
| ); |
| VdbeCoverageEqNe(v); |
| sqlite3VdbeAddOp3(v, OP_Copy, regNew, regOld, nVal-1); |
| }else{ |
| sqlite3VdbeAddOp2(v, OP_Goto, 0, addr); |
| } |
| } |
| |
| /* |
| ** This function is called as part of generating VM programs for RANGE |
| ** offset PRECEDING/FOLLOWING frame boundaries. Assuming "ASC" order for |
| ** the ORDER BY term in the window, it generates code equivalent to: |
| ** |
| ** if( csr1.peerVal + regVal >= csr2.peerVal ) goto lbl; |
| ** |
| ** A special type of arithmetic is used such that if csr.peerVal is not |
| ** a numeric type (real or integer), then the result of the addition is |
| ** a copy of csr1.peerVal. |
| */ |
| static void windowCodeRangeTest( |
| WindowCodeArg *p, |
| int op, /* OP_Ge or OP_Gt */ |
| int csr1, |
| int regVal, |
| int csr2, |
| int lbl |
| ){ |
| Parse *pParse = p->pParse; |
| Vdbe *v = sqlite3GetVdbe(pParse); |
| int reg1 = sqlite3GetTempReg(pParse); |
| int reg2 = sqlite3GetTempReg(pParse); |
| int arith = OP_Add; |
| int addrGe; |
| |
| int regString = ++pParse->nMem; |
| |
| assert( op==OP_Ge || op==OP_Gt || op==OP_Le ); |
| assert( p->pMWin->pOrderBy && p->pMWin->pOrderBy->nExpr==1 ); |
| if( p->pMWin->pOrderBy->a[0].sortOrder ){ |
| switch( op ){ |
| case OP_Ge: op = OP_Le; break; |
| case OP_Gt: op = OP_Lt; break; |
| default: assert( op==OP_Le ); op = OP_Ge; break; |
| } |
| arith = OP_Subtract; |
| } |
| |
| windowReadPeerValues(p, csr1, reg1); |
| windowReadPeerValues(p, csr2, reg2); |
| |
| /* Check if the peer value for csr1 value is a text or blob by comparing |
| ** it to the smallest possible string - ''. If it is, jump over the |
| ** OP_Add or OP_Subtract operation and proceed directly to the comparison. */ |
| sqlite3VdbeAddOp4(v, OP_String8, 0, regString, 0, "", P4_STATIC); |
| addrGe = sqlite3VdbeAddOp3(v, OP_Ge, regString, 0, reg1); |
| VdbeCoverage(v); |
| sqlite3VdbeAddOp3(v, arith, regVal, reg1, reg1); |
| sqlite3VdbeJumpHere(v, addrGe); |
| sqlite3VdbeAddOp3(v, op, reg2, lbl, reg1); VdbeCoverage(v); |
| sqlite3VdbeChangeP5(v, SQLITE_NULLEQ); |
| assert( op==OP_Ge || op==OP_Gt || op==OP_Lt || op==OP_Le ); |
| testcase(op==OP_Ge); VdbeCoverageIf(v, op==OP_Ge); |
| testcase(op==OP_Lt); VdbeCoverageIf(v, op==OP_Lt); |
| testcase(op==OP_Le); VdbeCoverageIf(v, op==OP_Le); |
| testcase(op==OP_Gt); VdbeCoverageIf(v, op==OP_Gt); |
| |
| sqlite3ReleaseTempReg(pParse, reg1); |
| sqlite3ReleaseTempReg(pParse, reg2); |
| } |
| |
| /* |
| ** Helper function for sqlite3WindowCodeStep(). Each call to this function |
| ** generates VM code for a single RETURN_ROW, AGGSTEP or AGGINVERSE |
| ** operation. Refer to the header comment for sqlite3WindowCodeStep() for |
| ** details. |
| */ |
| static int windowCodeOp( |
| WindowCodeArg *p, /* Context object */ |
| int op, /* WINDOW_RETURN_ROW, AGGSTEP or AGGINVERSE */ |
| int regCountdown, /* Register for OP_IfPos countdown */ |
| int jumpOnEof /* Jump here if stepped cursor reaches EOF */ |
| ){ |
| int csr, reg; |
| Parse *pParse = p->pParse; |
| Window *pMWin = p->pMWin; |
| int ret = 0; |
| Vdbe *v = p->pVdbe; |
| int addrIf = 0; |
| int addrContinue = 0; |
| int addrGoto = 0; |
| int bPeer = (pMWin->eFrmType!=TK_ROWS); |
| |
| int lblDone = sqlite3VdbeMakeLabel(pParse); |
| int addrNextRange = 0; |
| |
| /* Special case - WINDOW_AGGINVERSE is always a no-op if the frame |
| ** starts with UNBOUNDED PRECEDING. */ |
| if( op==WINDOW_AGGINVERSE && pMWin->eStart==TK_UNBOUNDED ){ |
| assert( regCountdown==0 && jumpOnEof==0 ); |
| return 0; |
| } |
| |
| if( regCountdown>0 ){ |
| if( pMWin->eFrmType==TK_RANGE ){ |
| addrNextRange = sqlite3VdbeCurrentAddr(v); |
| assert( op==WINDOW_AGGINVERSE || op==WINDOW_AGGSTEP ); |
| if( op==WINDOW_AGGINVERSE ){ |
| if( pMWin->eStart==TK_FOLLOWING ){ |
| windowCodeRangeTest( |
| p, OP_Le, p->current.csr, regCountdown, p->start.csr, lblDone |
| ); |
| }else{ |
| windowCodeRangeTest( |
| p, OP_Ge, p->start.csr, regCountdown, p->current.csr, lblDone |
| ); |
| } |
| }else{ |
| windowCodeRangeTest( |
| p, OP_Gt, p->end.csr, regCountdown, p->current.csr, lblDone |
| ); |
| } |
| }else{ |
| addrIf = sqlite3VdbeAddOp3(v, OP_IfPos, regCountdown, 0, 1); |
| VdbeCoverage(v); |
| } |
| } |
| |
| if( op==WINDOW_RETURN_ROW && pMWin->regStartRowid==0 ){ |
| windowAggFinal(p, 0); |
| } |
| addrContinue = sqlite3VdbeCurrentAddr(v); |
| switch( op ){ |
| case WINDOW_RETURN_ROW: |
| csr = p->current.csr; |
| reg = p->current.reg; |
| windowReturnOneRow(p); |
| break; |
| |
| case WINDOW_AGGINVERSE: |
| csr = p->start.csr; |
| reg = p->start.reg; |
| if( pMWin->regStartRowid ){ |
| assert( pMWin->regEndRowid ); |
| sqlite3VdbeAddOp2(v, OP_AddImm, pMWin->regStartRowid, 1); |
| }else{ |
| windowAggStep(pParse, pMWin, csr, 1, p->regArg); |
| } |
| break; |
| |
| default: |
| assert( op==WINDOW_AGGSTEP ); |
| csr = p->end.csr; |
| reg = p->end.reg; |
| if( pMWin->regStartRowid ){ |
| assert( pMWin->regEndRowid ); |
| sqlite3VdbeAddOp2(v, OP_AddImm, pMWin->regEndRowid, 1); |
| }else{ |
| windowAggStep(pParse, pMWin, csr, 0, p->regArg); |
| } |
| break; |
| } |
| |
| if( op==p->eDelete ){ |
| sqlite3VdbeAddOp1(v, OP_Delete, csr); |
| sqlite3VdbeChangeP5(v, OPFLAG_SAVEPOSITION); |
| } |
| |
| if( jumpOnEof ){ |
| sqlite3VdbeAddOp2(v, OP_Next, csr, sqlite3VdbeCurrentAddr(v)+2); |
| VdbeCoverage(v); |
| ret = sqlite3VdbeAddOp0(v, OP_Goto); |
| }else{ |
| sqlite3VdbeAddOp2(v, OP_Next, csr, sqlite3VdbeCurrentAddr(v)+1+bPeer); |
| VdbeCoverage(v); |
| if( bPeer ){ |
| addrGoto = sqlite3VdbeAddOp0(v, OP_Goto); |
| } |
| } |
| |
| if( bPeer ){ |
| int nReg = (pMWin->pOrderBy ? pMWin->pOrderBy->nExpr : 0); |
| int regTmp = (nReg ? sqlite3GetTempRange(pParse, nReg) : 0); |
| windowReadPeerValues(p, csr, regTmp); |
| windowIfNewPeer(pParse, pMWin->pOrderBy, regTmp, reg, addrContinue); |
| sqlite3ReleaseTempRange(pParse, regTmp, nReg); |
| } |
| |
| if( addrNextRange ){ |
| sqlite3VdbeAddOp2(v, OP_Goto, 0, addrNextRange); |
| } |
| sqlite3VdbeResolveLabel(v, lblDone); |
| if( addrGoto ) sqlite3VdbeJumpHere(v, addrGoto); |
| if( addrIf ) sqlite3VdbeJumpHere(v, addrIf); |
| return ret; |
| } |
| |
| |
| /* |
| ** Allocate and return a duplicate of the Window object indicated by the |
| ** third argument. Set the Window.pOwner field of the new object to |
| ** pOwner. |
| */ |
| Window *sqlite3WindowDup(sqlite3 *db, Expr *pOwner, Window *p){ |
| Window *pNew = 0; |
| if( ALWAYS(p) ){ |
| pNew = sqlite3DbMallocZero(db, sizeof(Window)); |
| if( pNew ){ |
| pNew->zName = sqlite3DbStrDup(db, p->zName); |
| pNew->pFilter = sqlite3ExprDup(db, p->pFilter, 0); |
| pNew->pFunc = p->pFunc; |
| pNew->pPartition = sqlite3ExprListDup(db, p->pPartition, 0); |
| pNew->pOrderBy = sqlite3ExprListDup(db, p->pOrderBy, 0); |
| pNew->eFrmType = p->eFrmType; |
| pNew->eEnd = p->eEnd; |
| pNew->eStart = p->eStart; |
| pNew->eExclude = p->eExclude; |
| pNew->pStart = sqlite3ExprDup(db, p->pStart, 0); |
| pNew->pEnd = sqlite3ExprDup(db, p->pEnd, 0); |
| pNew->pOwner = pOwner; |
| } |
| } |
| return pNew; |
| } |
| |
| /* |
| ** Return a copy of the linked list of Window objects passed as the |
| ** second argument. |
| */ |
| Window *sqlite3WindowListDup(sqlite3 *db, Window *p){ |
| Window *pWin; |
| Window *pRet = 0; |
| Window **pp = &pRet; |
| |
| for(pWin=p; pWin; pWin=pWin->pNextWin){ |
| *pp = sqlite3WindowDup(db, 0, pWin); |
| if( *pp==0 ) break; |
| pp = &((*pp)->pNextWin); |
| } |
| |
| return pRet; |
| } |
| |
| /* |
| ** Return true if it can be determined at compile time that expression |
| ** pExpr evaluates to a value that, when cast to an integer, is greater |
| ** than zero. False otherwise. |
| ** |
| ** If an OOM error occurs, this function sets the Parse.db.mallocFailed |
| ** flag and returns zero. |
| */ |
| static int windowExprGtZero(Parse *pParse, Expr *pExpr){ |
| int ret = 0; |
| sqlite3 *db = pParse->db; |
| sqlite3_value *pVal = 0; |
| sqlite3ValueFromExpr(db, pExpr, db->enc, SQLITE_AFF_NUMERIC, &pVal); |
| if( pVal && sqlite3_value_int(pVal)>0 ){ |
| ret = 1; |
| } |
| sqlite3ValueFree(pVal); |
| return ret; |
| } |
| |
| /* |
| ** sqlite3WhereBegin() has already been called for the SELECT statement |
| ** passed as the second argument when this function is invoked. It generates |
| ** code to populate the Window.regResult register for each window function |
| ** and invoke the sub-routine at instruction addrGosub once for each row. |
| ** sqlite3WhereEnd() is always called before returning. |
| ** |
| ** This function handles several different types of window frames, which |
| ** require slightly different processing. The following pseudo code is |
| ** used to implement window frames of the form: |
| ** |
| ** ROWS BETWEEN <expr1> PRECEDING AND <expr2> FOLLOWING |
| ** |
| ** Other window frame types use variants of the following: |
| ** |
| ** ... loop started by sqlite3WhereBegin() ... |
| ** if( new partition ){ |
| ** Gosub flush |
| ** } |
| ** Insert new row into eph table. |
| ** |
| ** if( first row of partition ){ |
| ** // Rewind three cursors, all open on the eph table. |
| ** Rewind(csrEnd); |
| ** Rewind(csrStart); |
| ** Rewind(csrCurrent); |
| ** |
| ** regEnd = <expr2> // FOLLOWING expression |
| ** regStart = <expr1> // PRECEDING expression |
| ** }else{ |
| ** // First time this branch is taken, the eph table contains two |
| ** // rows. The first row in the partition, which all three cursors |
| ** // currently point to, and the following row. |
| ** AGGSTEP |
| ** if( (regEnd--)<=0 ){ |
| ** RETURN_ROW |
| ** if( (regStart--)<=0 ){ |
| ** AGGINVERSE |
| ** } |
| ** } |
| ** } |
| ** } |
| ** flush: |
| ** AGGSTEP |
| ** while( 1 ){ |
| ** RETURN ROW |
| ** if( csrCurrent is EOF ) break; |
| ** if( (regStart--)<=0 ){ |
| ** AggInverse(csrStart) |
| ** Next(csrStart) |
| ** } |
| ** } |
| ** |
| ** The pseudo-code above uses the following shorthand: |
| ** |
| ** AGGSTEP: invoke the aggregate xStep() function for each window function |
| ** with arguments read from the current row of cursor csrEnd, then |
| ** step cursor csrEnd forward one row (i.e. sqlite3BtreeNext()). |
| ** |
| ** RETURN_ROW: return a row to the caller based on the contents of the |
| ** current row of csrCurrent and the current state of all |
| ** aggregates. Then step cursor csrCurrent forward one row. |
| ** |
| ** AGGINVERSE: invoke the aggregate xInverse() function for each window |
| ** functions with arguments read from the current row of cursor |
| ** csrStart. Then step csrStart forward one row. |
| ** |
| ** There are two other ROWS window frames that are handled significantly |
| ** differently from the above - "BETWEEN <expr> PRECEDING AND <expr> PRECEDING" |
| ** and "BETWEEN <expr> FOLLOWING AND <expr> FOLLOWING". These are special |
| ** cases because they change the order in which the three cursors (csrStart, |
| ** csrCurrent and csrEnd) iterate through the ephemeral table. Cases that |
| ** use UNBOUNDED or CURRENT ROW are much simpler variations on one of these |
| ** three. |
| ** |
| ** ROWS BETWEEN <expr1> PRECEDING AND <expr2> PRECEDING |
| ** |
| ** ... loop started by sqlite3WhereBegin() ... |
| ** if( new partition ){ |
| ** Gosub flush |
| ** } |
| ** Insert new row into eph table. |
| ** if( first row of partition ){ |
| ** Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent) |
| ** regEnd = <expr2> |
| ** regStart = <expr1> |
| ** }else{ |
| ** if( (regEnd--)<=0 ){ |
| ** AGGSTEP |
| ** } |
| ** RETURN_ROW |
| ** if( (regStart--)<=0 ){ |
| ** AGGINVERSE |
| ** } |
| ** } |
| ** } |
| ** flush: |
| ** if( (regEnd--)<=0 ){ |
| ** AGGSTEP |
| ** } |
| ** RETURN_ROW |
| ** |
| ** |
| ** ROWS BETWEEN <expr1> FOLLOWING AND <expr2> FOLLOWING |
| ** |
| ** ... loop started by sqlite3WhereBegin() ... |
| ** if( new partition ){ |
| ** Gosub flush |
| ** } |
| ** Insert new row into eph table. |
| ** if( first row of partition ){ |
| ** Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent) |
| ** regEnd = <expr2> |
| ** regStart = regEnd - <expr1> |
| ** }else{ |
| ** AGGSTEP |
| ** if( (regEnd--)<=0 ){ |
| ** RETURN_ROW |
| ** } |
| ** if( (regStart--)<=0 ){ |
| ** AGGINVERSE |
| ** } |
| ** } |
| ** } |
| ** flush: |
| ** AGGSTEP |
| ** while( 1 ){ |
| ** if( (regEnd--)<=0 ){ |
| ** RETURN_ROW |
| ** if( eof ) break; |
| ** } |
| ** if( (regStart--)<=0 ){ |
| ** AGGINVERSE |
| ** if( eof ) break |
| ** } |
| ** } |
| ** while( !eof csrCurrent ){ |
| ** RETURN_ROW |
| ** } |
| ** |
| ** For the most part, the patterns above are adapted to support UNBOUNDED by |
| ** assuming that it is equivalent to "infinity PRECEDING/FOLLOWING" and |
| ** CURRENT ROW by assuming that it is equivilent to "0 PRECEDING/FOLLOWING". |
| ** This is optimized of course - branches that will never be taken and |
| ** conditions that are always true are omitted from the VM code. The only |
| ** exceptional case is: |
| ** |
| ** ROWS BETWEEN <expr1> FOLLOWING AND UNBOUNDED FOLLOWING |
| ** |
| ** ... loop started by sqlite3WhereBegin() ... |
| ** if( new partition ){ |
| ** Gosub flush |
| ** } |
| ** Insert new row into eph table. |
| ** if( first row of partition ){ |
| ** Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent) |
| ** regStart = <expr1> |
| ** }else{ |
| ** AGGSTEP |
| ** } |
| ** } |
| ** flush: |
| ** AGGSTEP |
| ** while( 1 ){ |
| ** if( (regStart--)<=0 ){ |
| ** AGGINVERSE |
| ** if( eof ) break |
| ** } |
| ** RETURN_ROW |
| ** } |
| ** while( !eof csrCurrent ){ |
| ** RETURN_ROW |
| ** } |
| ** |
| ** Also requiring special handling are the cases: |
| ** |
| ** ROWS BETWEEN <expr1> PRECEDING AND <expr2> PRECEDING |
| ** ROWS BETWEEN <expr1> FOLLOWING AND <expr2> FOLLOWING |
| ** |
| ** when (expr1 < expr2). This is detected at runtime, not by this function. |
| ** To handle this case, the pseudo-code programs depicted above are modified |
| ** slightly to be: |
| ** |
| ** ... loop started by sqlite3WhereBegin() ... |
| ** if( new partition ){ |
| ** Gosub flush |
| ** } |
| ** Insert new row into eph table. |
| ** if( first row of partition ){ |
| ** Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent) |
| ** regEnd = <expr2> |
| ** regStart = <expr1> |
| ** if( regEnd < regStart ){ |
| ** RETURN_ROW |
| ** delete eph table contents |
| ** continue |
| ** } |
| ** ... |
| ** |
| ** The new "continue" statement in the above jumps to the next iteration |
| ** of the outer loop - the one started by sqlite3WhereBegin(). |
| ** |
| ** The various GROUPS cases are implemented using the same patterns as |
| ** ROWS. The VM code is modified slightly so that: |
| ** |
| ** 1. The else branch in the main loop is only taken if the row just |
| ** added to the ephemeral table is the start of a new group. In |
| ** other words, it becomes: |
| ** |
| ** ... loop started by sqlite3WhereBegin() ... |
| ** if( new partition ){ |
| ** Gosub flush |
| ** } |
| ** Insert new row into eph table. |
| ** if( first row of partition ){ |
| ** Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent) |
| ** regEnd = <expr2> |
| ** regStart = <expr1> |
| ** }else if( new group ){ |
| ** ... |
| ** } |
| ** } |
| ** |
| ** 2. Instead of processing a single row, each RETURN_ROW, AGGSTEP or |
| ** AGGINVERSE step processes the current row of the relevant cursor and |
| ** all subsequent rows belonging to the same group. |
| ** |
| ** RANGE window frames are a little different again. As for GROUPS, the |
| ** main loop runs once per group only. And RETURN_ROW, AGGSTEP and AGGINVERSE |
| ** deal in groups instead of rows. As for ROWS and GROUPS, there are three |
| ** basic cases: |
| ** |
| ** RANGE BETWEEN <expr1> PRECEDING AND <expr2> FOLLOWING |
| ** |
| ** ... loop started by sqlite3WhereBegin() ... |
| ** if( new partition ){ |
| ** Gosub flush |
| ** } |
| ** Insert new row into eph table. |
| ** if( first row of partition ){ |
| ** Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent) |
| ** regEnd = <expr2> |
| ** regStart = <expr1> |
| ** }else{ |
| ** AGGSTEP |
| ** while( (csrCurrent.key + regEnd) < csrEnd.key ){ |
| ** RETURN_ROW |
| ** while( csrStart.key + regStart) < csrCurrent.key ){ |
| ** AGGINVERSE |
| ** } |
| ** } |
| ** } |
| ** } |
| ** flush: |
| ** AGGSTEP |
| ** while( 1 ){ |
| ** RETURN ROW |
| ** if( csrCurrent is EOF ) break; |
| ** while( csrStart.key + regStart) < csrCurrent.key ){ |
| ** AGGINVERSE |
| ** } |
| ** } |
| ** } |
| ** |
| ** In the above notation, "csr.key" means the current value of the ORDER BY |
| ** expression (there is only ever 1 for a RANGE that uses an <expr> FOLLOWING |
| ** or <expr PRECEDING) read from cursor csr. |
| ** |
| ** RANGE BETWEEN <expr1> PRECEDING AND <expr2> PRECEDING |
| ** |
| ** ... loop started by sqlite3WhereBegin() ... |
| ** if( new partition ){ |
| ** Gosub flush |
| ** } |
| ** Insert new row into eph table. |
| ** if( first row of partition ){ |
| ** Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent) |
| ** regEnd = <expr2> |
| ** regStart = <expr1> |
| ** }else{ |
| ** if( (csrEnd.key + regEnd) <= csrCurrent.key ){ |
| ** AGGSTEP |
| ** } |
| ** while( (csrStart.key + regStart) < csrCurrent.key ){ |
| ** AGGINVERSE |
| ** } |
| ** RETURN_ROW |
| ** } |
| ** } |
| ** flush: |
| ** while( (csrEnd.key + regEnd) <= csrCurrent.key ){ |
| ** AGGSTEP |
| ** } |
| ** while( (csrStart.key + regStart) < csrCurrent.key ){ |
| ** AGGINVERSE |
| ** } |
| ** RETURN_ROW |
| ** |
| ** RANGE BETWEEN <expr1> FOLLOWING AND <expr2> FOLLOWING |
| ** |
| ** ... loop started by sqlite3WhereBegin() ... |
| ** if( new partition ){ |
| ** Gosub flush |
| ** } |
| ** Insert new row into eph table. |
| ** if( first row of partition ){ |
| ** Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent) |
| ** regEnd = <expr2> |
| ** regStart = <expr1> |
| ** }else{ |
| ** AGGSTEP |
| ** while( (csrCurrent.key + regEnd) < csrEnd.key ){ |
| ** while( (csrCurrent.key + regStart) > csrStart.key ){ |
| ** AGGINVERSE |
| ** } |
| ** RETURN_ROW |
| ** } |
| ** } |
| ** } |
| ** flush: |
| ** AGGSTEP |
| ** while( 1 ){ |
| ** while( (csrCurrent.key + regStart) > csrStart.key ){ |
| ** AGGINVERSE |
| ** if( eof ) break "while( 1 )" loop. |
| ** } |
| ** RETURN_ROW |
| ** } |
| ** while( !eof csrCurrent ){ |
| ** RETURN_ROW |
| ** } |
| ** |
| ** The text above leaves out many details. Refer to the code and comments |
| ** below for a more complete picture. |
| */ |
| void sqlite3WindowCodeStep( |
| Parse *pParse, /* Parse context */ |
| Select *p, /* Rewritten SELECT statement */ |
| WhereInfo *pWInfo, /* Context returned by sqlite3WhereBegin() */ |
| int regGosub, /* Register for OP_Gosub */ |
| int addrGosub /* OP_Gosub here to return each row */ |
| ){ |
| Window *pMWin = p->pWin; |
| ExprList *pOrderBy = pMWin->pOrderBy; |
| Vdbe *v = sqlite3GetVdbe(pParse); |
| int csrWrite; /* Cursor used to write to eph. table */ |
| int csrInput = p->pSrc->a[0].iCursor; /* Cursor of sub-select */ |
| int nInput = p->pSrc->a[0].pTab->nCol; /* Number of cols returned by sub */ |
| int iInput; /* To iterate through sub cols */ |
| int addrNe; /* Address of OP_Ne */ |
| int addrGosubFlush = 0; /* Address of OP_Gosub to flush: */ |
| int addrInteger = 0; /* Address of OP_Integer */ |
| int addrEmpty; /* Address of OP_Rewind in flush: */ |
| int regStart = 0; /* Value of <expr> PRECEDING */ |
| int regEnd = 0; /* Value of <expr> FOLLOWING */ |
| int regNew; /* Array of registers holding new input row */ |
| int regRecord; /* regNew array in record form */ |
| int regRowid; /* Rowid for regRecord in eph table */ |
| int regNewPeer = 0; /* Peer values for new row (part of regNew) */ |
| int regPeer = 0; /* Peer values for current row */ |
| int regFlushPart = 0; /* Register for "Gosub flush_partition" */ |
| WindowCodeArg s; /* Context object for sub-routines */ |
| int lblWhereEnd; /* Label just before sqlite3WhereEnd() code */ |
| |
| assert( pMWin->eStart==TK_PRECEDING || pMWin->eStart==TK_CURRENT |
| || pMWin->eStart==TK_FOLLOWING || pMWin->eStart==TK_UNBOUNDED |
| ); |
| assert( pMWin->eEnd==TK_FOLLOWING || pMWin->eEnd==TK_CURRENT |
| || pMWin->eEnd==TK_UNBOUNDED || pMWin->eEnd==TK_PRECEDING |
| ); |
| assert( pMWin->eExclude==0 || pMWin->eExclude==TK_CURRENT |
| || pMWin->eExclude==TK_GROUP || pMWin->eExclude==TK_TIES |
| || pMWin->eExclude==TK_NO |
| ); |
| |
| lblWhereEnd = sqlite3VdbeMakeLabel(pParse); |
| |
| /* Fill in the context object */ |
| memset(&s, 0, sizeof(WindowCodeArg)); |
| s.pParse = pParse; |
| s.pMWin = pMWin; |
| s.pVdbe = v; |
| s.regGosub = regGosub; |
| s.addrGosub = addrGosub; |
| s.current.csr = pMWin->iEphCsr; |
| csrWrite = s.current.csr+1; |
| s.start.csr = s.current.csr+2; |
| s.end.csr = s.current.csr+3; |
| |
| /* Figure out when rows may be deleted from the ephemeral table. There |
| ** are four options - they may never be deleted (eDelete==0), they may |
| ** be deleted as soon as they are no longer part of the window frame |
| ** (eDelete==WINDOW_AGGINVERSE), they may be deleted as after the row |
| ** has been returned to the caller (WINDOW_RETURN_ROW), or they may |
| ** be deleted after they enter the frame (WINDOW_AGGSTEP). */ |
| switch( pMWin->eStart ){ |
| case TK_FOLLOWING: |
| if( pMWin->eFrmType!=TK_RANGE |
| && windowExprGtZero(pParse, pMWin->pStart) |
| ){ |
| s.eDelete = WINDOW_RETURN_ROW; |
| } |
| break; |
| case TK_UNBOUNDED: |
| if( windowCacheFrame(pMWin)==0 ){ |
| if( pMWin->eEnd==TK_PRECEDING ){ |
| if( pMWin->eFrmType!=TK_RANGE |
| && windowExprGtZero(pParse, pMWin->pEnd) |
| ){ |
| s.eDelete = WINDOW_AGGSTEP; |
| } |
| }else{ |
| s.eDelete = WINDOW_RETURN_ROW; |
| } |
| } |
| break; |
| default: |
| s.eDelete = WINDOW_AGGINVERSE; |
| break; |
| } |
| |
| /* Allocate registers for the array of values from the sub-query, the |
| ** samve values in record form, and the rowid used to insert said record |
| ** into the ephemeral table. */ |
| regNew = pParse->nMem+1; |
| pParse->nMem += nInput; |
| regRecord = ++pParse->nMem; |
| regRowid = ++pParse->nMem; |
| |
| /* If the window frame contains an "<expr> PRECEDING" or "<expr> FOLLOWING" |
| ** clause, allocate registers to store the results of evaluating each |
| ** <expr>. */ |
| if( pMWin->eStart==TK_PRECEDING || pMWin->eStart==TK_FOLLOWING ){ |
| regStart = ++pParse->nMem; |
| } |
| if( pMWin->eEnd==TK_PRECEDING || pMWin->eEnd==TK_FOLLOWING ){ |
| regEnd = ++pParse->nMem; |
| } |
| |
| /* If this is not a "ROWS BETWEEN ..." frame, then allocate arrays of |
| ** registers to store copies of the ORDER BY expressions (peer values) |
| ** for the main loop, and for each cursor (start, current and end). */ |
| if( pMWin->eFrmType!=TK_ROWS ){ |
| int nPeer = (pOrderBy ? pOrderBy->nExpr : 0); |
| regNewPeer = regNew + pMWin->nBufferCol; |
| if( pMWin->pPartition ) regNewPeer += pMWin->pPartition->nExpr; |
| regPeer = pParse->nMem+1; pParse->nMem += nPeer; |
| s.start.reg = pParse->nMem+1; pParse->nMem += nPeer; |
| s.current.reg = pParse->nMem+1; pParse->nMem += nPeer; |
| s.end.reg = pParse->nMem+1; pParse->nMem += nPeer; |
| } |
| |
| /* Load the column values for the row returned by the sub-select |
| ** into an array of registers starting at regNew. Assemble them into |
| ** a record in register regRecord. */ |
| for(iInput=0; iInput<nInput; iInput++){ |
| sqlite3VdbeAddOp3(v, OP_Column, csrInput, iInput, regNew+iInput); |
| } |
| sqlite3VdbeAddOp3(v, OP_MakeRecord, regNew, nInput, regRecord); |
| |
| /* An input row has just been read into an array of registers starting |
| ** at regNew. If the window has a PARTITION clause, this block generates |
| ** VM code to check if the input row is the start of a new partition. |
| ** If so, it does an OP_Gosub to an address to be filled in later. The |
| ** address of the OP_Gosub is stored in local variable addrGosubFlush. */ |
| if( pMWin->pPartition ){ |
| int addr; |
| ExprList *pPart = pMWin->pPartition; |
| int nPart = pPart->nExpr; |
| int regNewPart = regNew + pMWin->nBufferCol; |
| KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pPart, 0, 0); |
| |
| regFlushPart = ++pParse->nMem; |
| addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPart, pMWin->regPart, nPart); |
| sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO); |
| sqlite3VdbeAddOp3(v, OP_Jump, addr+2, addr+4, addr+2); |
| VdbeCoverageEqNe(v); |
| addrGosubFlush = sqlite3VdbeAddOp1(v, OP_Gosub, regFlushPart); |
| VdbeComment((v, "call flush_partition")); |
| sqlite3VdbeAddOp3(v, OP_Copy, regNewPart, pMWin->regPart, nPart-1); |
| } |
| |
| /* Insert the new row into the ephemeral table */ |
| sqlite3VdbeAddOp2(v, OP_NewRowid, csrWrite, regRowid); |
| sqlite3VdbeAddOp3(v, OP_Insert, csrWrite, regRecord, regRowid); |
| addrNe = sqlite3VdbeAddOp3(v, OP_Ne, pMWin->regOne, 0, regRowid); |
| VdbeCoverageNeverNull(v); |
| |
| /* This block is run for the first row of each partition */ |
| s.regArg = windowInitAccum(pParse, pMWin); |
| |
| if( regStart ){ |
| sqlite3ExprCode(pParse, pMWin->pStart, regStart); |
| windowCheckValue(pParse, regStart, 0 + (pMWin->eFrmType==TK_RANGE ? 3 : 0)); |
| } |
| if( regEnd ){ |
| sqlite3ExprCode(pParse, pMWin->pEnd, regEnd); |
| windowCheckValue(pParse, regEnd, 1 + (pMWin->eFrmType==TK_RANGE ? 3 : 0)); |
| } |
| |
| if( pMWin->eStart==pMWin->eEnd && regStart ){ |
| int op = ((pMWin->eStart==TK_FOLLOWING) ? OP_Ge : OP_Le); |
| int addrGe = sqlite3VdbeAddOp3(v, op, regStart, 0, regEnd); |
| VdbeCoverageNeverNullIf(v, op==OP_Ge); /* NeverNull because bound <expr> */ |
| VdbeCoverageNeverNullIf(v, op==OP_Le); /* values previously checked */ |
| windowAggFinal(&s, 0); |
| sqlite3VdbeAddOp2(v, OP_Rewind, s.current.csr, 1); |
| VdbeCoverageNeverTaken(v); |
| windowReturnOneRow(&s); |
| sqlite3VdbeAddOp1(v, OP_ResetSorter, s.current.csr); |
| sqlite3VdbeAddOp2(v, OP_Goto, 0, lblWhereEnd); |
| sqlite3VdbeJumpHere(v, addrGe); |
| } |
| if( pMWin->eStart==TK_FOLLOWING && pMWin->eFrmType!=TK_RANGE && regEnd ){ |
| assert( pMWin->eEnd==TK_FOLLOWING ); |
| sqlite3VdbeAddOp3(v, OP_Subtract, regStart, regEnd, regStart); |
| } |
| |
| if( pMWin->eStart!=TK_UNBOUNDED ){ |
| sqlite3VdbeAddOp2(v, OP_Rewind, s.start.csr, 1); |
| VdbeCoverageNeverTaken(v); |
| } |
| sqlite3VdbeAddOp2(v, OP_Rewind, s.current.csr, 1); |
| VdbeCoverageNeverTaken(v); |
| sqlite3VdbeAddOp2(v, OP_Rewind, s.end.csr, 1); |
| VdbeCoverageNeverTaken(v); |
| if( regPeer && pOrderBy ){ |
| sqlite3VdbeAddOp3(v, OP_Copy, regNewPeer, regPeer, pOrderBy->nExpr-1); |
| sqlite3VdbeAddOp3(v, OP_Copy, regPeer, s.start.reg, pOrderBy->nExpr-1); |
| sqlite3VdbeAddOp3(v, OP_Copy, regPeer, s.current.reg, pOrderBy->nExpr-1); |
| sqlite3VdbeAddOp3(v, OP_Copy, regPeer, s.end.reg, pOrderBy->nExpr-1); |
| } |
| |
| sqlite3VdbeAddOp2(v, OP_Goto, 0, lblWhereEnd); |
| |
| sqlite3VdbeJumpHere(v, addrNe); |
| |
| /* Beginning of the block executed for the second and subsequent rows. */ |
| if( regPeer ){ |
| windowIfNewPeer(pParse, pOrderBy, regNewPeer, regPeer, lblWhereEnd); |
| } |
| if( pMWin->eStart==TK_FOLLOWING ){ |
| windowCodeOp(&s, WINDOW_AGGSTEP, 0, 0); |
| if( pMWin->eEnd!=TK_UNBOUNDED ){ |
| if( pMWin->eFrmType==TK_RANGE ){ |
| int lbl = sqlite3VdbeMakeLabel(pParse); |
| int addrNext = sqlite3VdbeCurrentAddr(v); |
| windowCodeRangeTest(&s, OP_Ge, s.current.csr, regEnd, s.end.csr, lbl); |
| windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 0); |
| windowCodeOp(&s, WINDOW_RETURN_ROW, 0, 0); |
| sqlite3VdbeAddOp2(v, OP_Goto, 0, addrNext); |
| sqlite3VdbeResolveLabel(v, lbl); |
| }else{ |
| windowCodeOp(&s, WINDOW_RETURN_ROW, regEnd, 0); |
| windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 0); |
| } |
| } |
| }else |
| if( pMWin->eEnd==TK_PRECEDING ){ |
| int bRPS = (pMWin->eStart==TK_PRECEDING && pMWin->eFrmType==TK_RANGE); |
| windowCodeOp(&s, WINDOW_AGGSTEP, regEnd, 0); |
| if( bRPS ) windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 0); |
| windowCodeOp(&s, WINDOW_RETURN_ROW, 0, 0); |
| if( !bRPS ) windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 0); |
| }else{ |
| int addr = 0; |
| windowCodeOp(&s, WINDOW_AGGSTEP, 0, 0); |
| if( pMWin->eEnd!=TK_UNBOUNDED ){ |
| if( pMWin->eFrmType==TK_RANGE ){ |
| int lbl = 0; |
| addr = sqlite3VdbeCurrentAddr(v); |
| if( regEnd ){ |
| lbl = sqlite3VdbeMakeLabel(pParse); |
| windowCodeRangeTest(&s, OP_Ge, s.current.csr, regEnd, s.end.csr, lbl); |
| } |
| windowCodeOp(&s, WINDOW_RETURN_ROW, 0, 0); |
| windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 0); |
| if( regEnd ){ |
| sqlite3VdbeAddOp2(v, OP_Goto, 0, addr); |
| sqlite3VdbeResolveLabel(v, lbl); |
| } |
| }else{ |
| if( regEnd ){ |
| addr = sqlite3VdbeAddOp3(v, OP_IfPos, regEnd, 0, 1); |
| VdbeCoverage(v); |
| } |
| windowCodeOp(&s, WINDOW_RETURN_ROW, 0, 0); |
| windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 0); |
| if( regEnd ) sqlite3VdbeJumpHere(v, addr); |
| } |
| } |
| } |
| |
| /* End of the main input loop */ |
| sqlite3VdbeResolveLabel(v, lblWhereEnd); |
| sqlite3WhereEnd(pWInfo); |
| |
| /* Fall through */ |
| if( pMWin->pPartition ){ |
| addrInteger = sqlite3VdbeAddOp2(v, OP_Integer, 0, regFlushPart); |
| sqlite3VdbeJumpHere(v, addrGosubFlush); |
| } |
| |
| addrEmpty = sqlite3VdbeAddOp1(v, OP_Rewind, csrWrite); |
| VdbeCoverage(v); |
| if( pMWin->eEnd==TK_PRECEDING ){ |
| int bRPS = (pMWin->eStart==TK_PRECEDING && pMWin->eFrmType==TK_RANGE); |
| windowCodeOp(&s, WINDOW_AGGSTEP, regEnd, 0); |
| if( bRPS ) windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 0); |
| windowCodeOp(&s, WINDOW_RETURN_ROW, 0, 0); |
| }else if( pMWin->eStart==TK_FOLLOWING ){ |
| int addrStart; |
| int addrBreak1; |
| int addrBreak2; |
| int addrBreak3; |
| windowCodeOp(&s, WINDOW_AGGSTEP, 0, 0); |
| if( pMWin->eFrmType==TK_RANGE ){ |
| addrStart = sqlite3VdbeCurrentAddr(v); |
| addrBreak2 = windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 1); |
| addrBreak1 = windowCodeOp(&s, WINDOW_RETURN_ROW, 0, 1); |
| }else |
| if( pMWin->eEnd==TK_UNBOUNDED ){ |
| addrStart = sqlite3VdbeCurrentAddr(v); |
| addrBreak1 = windowCodeOp(&s, WINDOW_RETURN_ROW, regStart, 1); |
| addrBreak2 = windowCodeOp(&s, WINDOW_AGGINVERSE, 0, 1); |
| }else{ |
| assert( pMWin->eEnd==TK_FOLLOWING ); |
| addrStart = sqlite3VdbeCurrentAddr(v); |
| addrBreak1 = windowCodeOp(&s, WINDOW_RETURN_ROW, regEnd, 1); |
| addrBreak2 = windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 1); |
| } |
| sqlite3VdbeAddOp2(v, OP_Goto, 0, addrStart); |
| sqlite3VdbeJumpHere(v, addrBreak2); |
| addrStart = sqlite3VdbeCurrentAddr(v); |
| addrBreak3 = windowCodeOp(&s, WINDOW_RETURN_ROW, 0, 1); |
| sqlite3VdbeAddOp2(v, OP_Goto, 0, addrStart); |
| sqlite3VdbeJumpHere(v, addrBreak1); |
| sqlite3VdbeJumpHere(v, addrBreak3); |
| }else{ |
| int addrBreak; |
| int addrStart; |
| windowCodeOp(&s, WINDOW_AGGSTEP, 0, 0); |
| addrStart = sqlite3VdbeCurrentAddr(v); |
| addrBreak = windowCodeOp(&s, WINDOW_RETURN_ROW, 0, 1); |
| windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 0); |
| sqlite3VdbeAddOp2(v, OP_Goto, 0, addrStart); |
| sqlite3VdbeJumpHere(v, addrBreak); |
| } |
| sqlite3VdbeJumpHere(v, addrEmpty); |
| |
| sqlite3VdbeAddOp1(v, OP_ResetSorter, s.current.csr); |
| if( pMWin->pPartition ){ |
| if( pMWin->regStartRowid ){ |
| sqlite3VdbeAddOp2(v, OP_Integer, 1, pMWin->regStartRowid); |
| sqlite3VdbeAddOp2(v, OP_Integer, 0, pMWin->regEndRowid); |
| } |
| sqlite3VdbeChangeP1(v, addrInteger, sqlite3VdbeCurrentAddr(v)); |
| sqlite3VdbeAddOp1(v, OP_Return, regFlushPart); |
| } |
| } |
| |
| #endif /* SQLITE_OMIT_WINDOWFUNC */ |