4 ** The author disclaims copyright to this source code. In place of
5 ** a legal notice, here is a blessing:
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.
11 *************************************************************************
13 #include "sqliteInt.h"
15 #ifndef SQLITE_OMIT_WINDOWFUNC
20 ** Any SELECT statement that contains one or more window functions in
21 ** either the select list or ORDER BY clause (the only two places window
22 ** functions may be used) is transformed by function sqlite3WindowRewrite()
23 ** in order to support window function processing. For example, with the
26 ** CREATE TABLE t1(a, b, c, d, e, f, g);
30 ** SELECT a+1, max(b) OVER (PARTITION BY c ORDER BY d) FROM t1 ORDER BY e;
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, d
38 ** The flattening optimization is disabled when processing this transformed
39 ** SELECT statement. This allows the implementation of the window function
40 ** (in this case max()) to process rows sorted in order of (c, d), which
41 ** makes things easier for obvious reasons. More generally:
43 ** * FROM, WHERE, GROUP BY and HAVING clauses are all moved to
46 ** * ORDER BY, LIMIT and OFFSET remain part of the parent query.
48 ** * Terminals from each of the expression trees that make up the
49 ** select-list and ORDER BY expressions in the parent query are
50 ** selected by the sub-query. For the purposes of the transformation,
51 ** terminals are column references and aggregate functions.
53 ** If there is more than one window function in the SELECT that uses
54 ** the same window declaration (the OVER bit), then a single scan may
55 ** be used to process more than one window function. For example:
57 ** SELECT max(b) OVER (PARTITION BY c ORDER BY d),
58 ** min(e) OVER (PARTITION BY c ORDER BY d)
61 ** is transformed in the same way as the example above. However:
63 ** SELECT max(b) OVER (PARTITION BY c ORDER BY d),
64 ** min(e) OVER (PARTITION BY a ORDER BY b)
67 ** Must be transformed to:
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 FROM
71 ** SELECT a, e, c, d, b FROM t1 ORDER BY a, b
75 ** so that both min() and max() may process rows in the order defined by
76 ** their respective window declarations.
78 ** INTERFACE WITH SELECT.C
80 ** When processing the rewritten SELECT statement, code in select.c calls
81 ** sqlite3WhereBegin() to begin iterating through the results of the
82 ** sub-query, which is always implemented as a co-routine. It then calls
83 ** sqlite3WindowCodeStep() to process rows and finish the scan by calling
86 ** sqlite3WindowCodeStep() generates VM code so that, for each row returned
87 ** by the sub-query a sub-routine (OP_Gosub) coded by select.c is invoked.
88 ** When the sub-routine is invoked:
90 ** * The results of all window-functions for the row are stored
91 ** in the associated Window.regResult registers.
93 ** * The required terminal values are stored in the current row of
94 ** temp table Window.iEphCsr.
96 ** In some cases, depending on the window frame and the specific window
97 ** functions invoked, sqlite3WindowCodeStep() caches each entire partition
98 ** 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 by
100 ** select.c is the same in either case.
102 ** BUILT-IN WINDOW FUNCTIONS
104 ** This implementation features the following built-in window functions:
112 ** lead(expr [, offset [, default]])
113 ** lag(expr [, offset [, default]])
116 ** nth_value(expr, N)
118 ** These are the same built-in window functions supported by Postgres.
119 ** Although the behaviour of aggregate window functions (functions that
120 ** can be used as either aggregates or window funtions) allows them to
121 ** be implemented using an API, built-in window functions are much more
122 ** 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 aggregate
125 ** window functions and some are implemented directly using VDBE
126 ** instructions. Additionally, for those functions that use the API, the
127 ** window frame is sometimes modified before the SELECT statement is
128 ** rewritten. For example, regardless of the specified window frame, the
129 ** row_number() function always uses:
131 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
133 ** See sqlite3WindowUpdate() for details.
135 ** As well as some of the built-in window functions, aggregate window
136 ** functions min() and max() are implemented using VDBE instructions if
137 ** the start of the window frame is declared as anything other than
138 ** UNBOUNDED PRECEDING.
142 ** Implementation of built-in window function row_number(). Assumes that the
143 ** window frame has been coerced to:
145 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
147 static void row_numberStepFunc(
148 sqlite3_context
*pCtx
,
150 sqlite3_value
**apArg
152 i64
*p
= (i64
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
155 static void row_numberInvFunc(
156 sqlite3_context
*pCtx
,
158 sqlite3_value
**apArg
161 static void row_numberValueFunc(sqlite3_context
*pCtx
){
162 i64
*p
= (i64
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
163 sqlite3_result_int64(pCtx
, (p
? *p
: 0));
167 ** Context object type used by rank(), dense_rank(), percent_rank() and
177 ** Implementation of built-in window function dense_rank(). Assumes that
178 ** the window frame has been set to:
180 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
182 static void dense_rankStepFunc(
183 sqlite3_context
*pCtx
,
185 sqlite3_value
**apArg
188 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
189 if( p
) p
->nStep
= 1;
191 static void dense_rankInvFunc(
192 sqlite3_context
*pCtx
,
194 sqlite3_value
**apArg
197 static void dense_rankValueFunc(sqlite3_context
*pCtx
){
199 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
205 sqlite3_result_int64(pCtx
, p
->nValue
);
210 ** Implementation of built-in window function rank(). Assumes that
211 ** the window frame has been set to:
213 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
215 static void rankStepFunc(
216 sqlite3_context
*pCtx
,
218 sqlite3_value
**apArg
221 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
225 p
->nValue
= p
->nStep
;
229 static void rankInvFunc(
230 sqlite3_context
*pCtx
,
232 sqlite3_value
**apArg
235 static void rankValueFunc(sqlite3_context
*pCtx
){
237 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
239 sqlite3_result_int64(pCtx
, p
->nValue
);
245 ** Implementation of built-in window function percent_rank(). Assumes that
246 ** the window frame has been set to:
248 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
250 static void percent_rankStepFunc(
251 sqlite3_context
*pCtx
,
253 sqlite3_value
**apArg
258 assert( sqlite3VdbeAssertAggContext(pCtx
) );
259 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
262 p
->nTotal
= sqlite3_value_int64(apArg
[0]);
266 p
->nValue
= p
->nStep
;
270 static void percent_rankInvFunc(
271 sqlite3_context
*pCtx
,
273 sqlite3_value
**apArg
276 static void percent_rankValueFunc(sqlite3_context
*pCtx
){
278 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
281 double r
= (double)(p
->nValue
-1) / (double)(p
->nTotal
-1);
282 sqlite3_result_double(pCtx
, r
);
284 sqlite3_result_double(pCtx
, 0.0);
291 ** Implementation of built-in window function cume_dist(). Assumes that
292 ** the window frame has been set to:
294 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
296 static void cume_distStepFunc(
297 sqlite3_context
*pCtx
,
299 sqlite3_value
**apArg
304 assert( sqlite3VdbeAssertAggContext(pCtx
) );
305 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
308 p
->nTotal
= sqlite3_value_int64(apArg
[0]);
313 static void cume_distInvFunc(
314 sqlite3_context
*pCtx
,
316 sqlite3_value
**apArg
319 static void cume_distValueFunc(sqlite3_context
*pCtx
){
321 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
322 if( p
&& p
->nTotal
){
323 double r
= (double)(p
->nStep
) / (double)(p
->nTotal
);
324 sqlite3_result_double(pCtx
, r
);
329 ** Context object for ntile() window function.
332 i64 nTotal
; /* Total rows in partition */
333 i64 nParam
; /* Parameter passed to ntile(N) */
334 i64 iRow
; /* Current row */
338 ** Implementation of ntile(). This assumes that the window frame has
341 ** ROWS UNBOUNDED PRECEDING AND CURRENT ROW
343 static void ntileStepFunc(
344 sqlite3_context
*pCtx
,
346 sqlite3_value
**apArg
350 p
= (struct NtileCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
353 p
->nParam
= sqlite3_value_int64(apArg
[0]);
354 p
->nTotal
= sqlite3_value_int64(apArg
[1]);
356 sqlite3_result_error(
357 pCtx
, "argument of ntile must be a positive integer", -1
364 static void ntileInvFunc(
365 sqlite3_context
*pCtx
,
367 sqlite3_value
**apArg
370 static void ntileValueFunc(sqlite3_context
*pCtx
){
372 p
= (struct NtileCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
373 if( p
&& p
->nParam
>0 ){
374 int nSize
= (p
->nTotal
/ p
->nParam
);
376 sqlite3_result_int64(pCtx
, p
->iRow
);
378 i64 nLarge
= p
->nTotal
- p
->nParam
*nSize
;
379 i64 iSmall
= nLarge
*(nSize
+1);
380 i64 iRow
= p
->iRow
-1;
382 assert( (nLarge
*(nSize
+1) + (p
->nParam
-nLarge
)*nSize
)==p
->nTotal
);
385 sqlite3_result_int64(pCtx
, 1 + iRow
/(nSize
+1));
387 sqlite3_result_int64(pCtx
, 1 + nLarge
+ (iRow
-iSmall
)/nSize
);
394 ** Context object for last_value() window function.
396 struct LastValueCtx
{
402 ** Implementation of last_value().
404 static void last_valueStepFunc(
405 sqlite3_context
*pCtx
,
407 sqlite3_value
**apArg
409 struct LastValueCtx
*p
;
410 p
= (struct LastValueCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
412 sqlite3_value_free(p
->pVal
);
413 p
->pVal
= sqlite3_value_dup(apArg
[0]);
415 sqlite3_result_error_nomem(pCtx
);
421 static void last_valueInvFunc(
422 sqlite3_context
*pCtx
,
424 sqlite3_value
**apArg
426 struct LastValueCtx
*p
;
427 p
= (struct LastValueCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
431 sqlite3_value_free(p
->pVal
);
436 static void last_valueValueFunc(sqlite3_context
*pCtx
){
437 struct LastValueCtx
*p
;
438 p
= (struct LastValueCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
440 sqlite3_result_value(pCtx
, p
->pVal
);
443 static void last_valueFinalizeFunc(sqlite3_context
*pCtx
){
444 struct LastValueCtx
*p
;
445 p
= (struct LastValueCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
447 sqlite3_result_value(pCtx
, p
->pVal
);
448 sqlite3_value_free(p
->pVal
);
454 ** No-op implementations of nth_value(), first_value(), lead() and lag().
455 ** These are all implemented inline using VDBE instructions.
457 static void nth_valueStepFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**a
){}
458 static void nth_valueInvFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**ap
){}
459 static void nth_valueValueFunc(sqlite3_context
*pCtx
){}
460 static void first_valueStepFunc(sqlite3_context
*p
, int n
, sqlite3_value
**ap
){}
461 static void first_valueInvFunc(sqlite3_context
*p
, int n
, sqlite3_value
**ap
){}
462 static void first_valueValueFunc(sqlite3_context
*pCtx
){}
463 static void leadStepFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**ap
){}
464 static void leadInvFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**ap
){}
465 static void leadValueFunc(sqlite3_context
*pCtx
){}
466 static void lagStepFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**ap
){}
467 static void lagInvFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**ap
){}
468 static void lagValueFunc(sqlite3_context
*pCtx
){}
470 #define WINDOWFUNC(name,nArg,extra) { \
471 nArg, (SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0, \
472 name ## StepFunc, name ## ValueFunc, name ## ValueFunc, \
473 name ## InvFunc, #name \
476 #define WINDOWFUNCF(name,nArg,extra) { \
477 nArg, (SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0, \
478 name ## StepFunc, name ## FinalizeFunc, name ## ValueFunc, \
479 name ## InvFunc, #name \
483 ** Register those built-in window functions that are not also aggregates.
485 void sqlite3WindowFunctions(void){
486 static FuncDef aWindowFuncs
[] = {
487 WINDOWFUNC(row_number
, 0, 0),
488 WINDOWFUNC(dense_rank
, 0, 0),
489 WINDOWFUNC(rank
, 0, 0),
490 WINDOWFUNC(percent_rank
, 0, SQLITE_FUNC_WINDOW_SIZE
),
491 WINDOWFUNC(cume_dist
, 0, SQLITE_FUNC_WINDOW_SIZE
),
492 WINDOWFUNC(ntile
, 1, SQLITE_FUNC_WINDOW_SIZE
),
493 WINDOWFUNCF(last_value
, 1, 0),
494 WINDOWFUNC(nth_value
, 2, 0),
495 WINDOWFUNC(first_value
, 1, 0),
496 WINDOWFUNC(lead
, 1, 0), WINDOWFUNC(lead
, 2, 0), WINDOWFUNC(lead
, 3, 0),
497 WINDOWFUNC(lag
, 1, 0), WINDOWFUNC(lag
, 2, 0), WINDOWFUNC(lag
, 3, 0),
499 sqlite3InsertBuiltinFuncs(aWindowFuncs
, ArraySize(aWindowFuncs
));
503 ** This function is called immediately after resolving the function name
504 ** for a window function within a SELECT statement. Argument pList is a
505 ** linked list of WINDOW definitions for the current SELECT statement.
506 ** Argument pFunc is the function definition just resolved and pWin
507 ** is the Window object representing the associated OVER clause. This
508 ** function updates the contents of pWin as follows:
510 ** * If the OVER clause refered to a named window (as in "max(x) OVER win"),
511 ** search list pList for a matching WINDOW definition, and update pWin
512 ** accordingly. If no such WINDOW clause can be found, leave an error
515 ** * If the function is a built-in window function that requires the
516 ** window to be coerced (see "BUILT-IN WINDOW FUNCTIONS" at the top
517 ** of this file), pWin is updated here.
519 void sqlite3WindowUpdate(
521 Window
*pList
, /* List of named windows for this SELECT */
522 Window
*pWin
, /* Window frame to update */
523 FuncDef
*pFunc
/* Window function definition */
525 if( pWin
->zName
&& pWin
->eType
==0 ){
527 for(p
=pList
; p
; p
=p
->pNextWin
){
528 if( sqlite3StrICmp(p
->zName
, pWin
->zName
)==0 ) break;
531 sqlite3ErrorMsg(pParse
, "no such window: %s", pWin
->zName
);
534 pWin
->pPartition
= sqlite3ExprListDup(pParse
->db
, p
->pPartition
, 0);
535 pWin
->pOrderBy
= sqlite3ExprListDup(pParse
->db
, p
->pOrderBy
, 0);
536 pWin
->pStart
= sqlite3ExprDup(pParse
->db
, p
->pStart
, 0);
537 pWin
->pEnd
= sqlite3ExprDup(pParse
->db
, p
->pEnd
, 0);
538 pWin
->eStart
= p
->eStart
;
539 pWin
->eEnd
= p
->eEnd
;
540 pWin
->eType
= p
->eType
;
542 if( pFunc
->funcFlags
& SQLITE_FUNC_WINDOW
){
543 sqlite3
*db
= pParse
->db
;
545 sqlite3ErrorMsg(pParse
,
546 "FILTER clause may only be used with aggregate window functions"
549 if( pFunc
->xSFunc
==row_numberStepFunc
|| pFunc
->xSFunc
==ntileStepFunc
){
550 sqlite3ExprDelete(db
, pWin
->pStart
);
551 sqlite3ExprDelete(db
, pWin
->pEnd
);
552 pWin
->pStart
= pWin
->pEnd
= 0;
553 pWin
->eType
= TK_ROWS
;
554 pWin
->eStart
= TK_UNBOUNDED
;
555 pWin
->eEnd
= TK_CURRENT
;
558 if( pFunc
->xSFunc
==dense_rankStepFunc
|| pFunc
->xSFunc
==rankStepFunc
559 || pFunc
->xSFunc
==percent_rankStepFunc
|| pFunc
->xSFunc
==cume_distStepFunc
561 sqlite3ExprDelete(db
, pWin
->pStart
);
562 sqlite3ExprDelete(db
, pWin
->pEnd
);
563 pWin
->pStart
= pWin
->pEnd
= 0;
564 pWin
->eType
= TK_RANGE
;
565 pWin
->eStart
= TK_UNBOUNDED
;
566 pWin
->eEnd
= TK_CURRENT
;
573 ** Context object passed through sqlite3WalkExprList() to
574 ** selectWindowRewriteExprCb() by selectWindowRewriteEList().
576 typedef struct WindowRewrite WindowRewrite
;
577 struct WindowRewrite
{
583 ** Callback function used by selectWindowRewriteEList(). If necessary,
584 ** this function appends to the output expression-list and updates
585 ** expression (*ppExpr) in place.
587 static int selectWindowRewriteExprCb(Walker
*pWalker
, Expr
*pExpr
){
588 struct WindowRewrite
*p
= pWalker
->u
.pRewrite
;
589 Parse
*pParse
= pWalker
->pParse
;
594 if( pExpr
->pWin
==0 ){
598 for(pWin
=p
->pWin
; pWin
; pWin
=pWin
->pNextWin
){
599 if( pExpr
->pWin
==pWin
){
600 assert( pWin
->pOwner
==pExpr
);
607 case TK_AGG_FUNCTION
:
609 Expr
*pDup
= sqlite3ExprDup(pParse
->db
, pExpr
, 0);
610 p
->pSub
= sqlite3ExprListAppend(pParse
, p
->pSub
, pDup
);
612 assert( ExprHasProperty(pExpr
, EP_Static
)==0 );
613 ExprSetProperty(pExpr
, EP_Static
);
614 sqlite3ExprDelete(pParse
->db
, pExpr
);
615 ExprClearProperty(pExpr
, EP_Static
);
616 memset(pExpr
, 0, sizeof(Expr
));
618 pExpr
->op
= TK_COLUMN
;
619 pExpr
->iColumn
= p
->pSub
->nExpr
-1;
620 pExpr
->iTable
= p
->pWin
->iEphCsr
;
632 static int selectWindowRewriteSelectCb(Walker
*pWalker
, Select
*pSelect
){
638 ** Iterate through each expression in expression-list pEList. For each:
641 ** * aggregate function, or
642 ** * window function with a Window object that is not a member of the
643 ** linked list passed as the second argument (pWin)
645 ** Append the node to output expression-list (*ppSub). And replace it
646 ** with a TK_COLUMN that reads the (N-1)th element of table
647 ** pWin->iEphCsr, where N is the number of elements in (*ppSub) after
648 ** appending the new one.
650 static void selectWindowRewriteEList(
653 ExprList
*pEList
, /* Rewrite expressions in this list */
654 ExprList
**ppSub
/* IN/OUT: Sub-select expression-list */
657 WindowRewrite sRewrite
;
659 memset(&sWalker
, 0, sizeof(Walker
));
660 memset(&sRewrite
, 0, sizeof(WindowRewrite
));
662 sRewrite
.pSub
= *ppSub
;
663 sRewrite
.pWin
= pWin
;
665 sWalker
.pParse
= pParse
;
666 sWalker
.xExprCallback
= selectWindowRewriteExprCb
;
667 sWalker
.xSelectCallback
= selectWindowRewriteSelectCb
;
668 sWalker
.u
.pRewrite
= &sRewrite
;
670 (void)sqlite3WalkExprList(&sWalker
, pEList
);
672 *ppSub
= sRewrite
.pSub
;
676 ** Append a copy of each expression in expression-list pAppend to
677 ** expression list pList. Return a pointer to the result list.
679 static ExprList
*exprListAppendList(
680 Parse
*pParse
, /* Parsing context */
681 ExprList
*pList
, /* List to which to append. Might be NULL */
682 ExprList
*pAppend
/* List of values to append. Might be NULL */
686 int nInit
= pList
? pList
->nExpr
: 0;
687 for(i
=0; i
<pAppend
->nExpr
; i
++){
688 Expr
*pDup
= sqlite3ExprDup(pParse
->db
, pAppend
->a
[i
].pExpr
, 0);
689 pList
= sqlite3ExprListAppend(pParse
, pList
, pDup
);
690 if( pList
) pList
->a
[nInit
+i
].sortOrder
= pAppend
->a
[i
].sortOrder
;
697 ** If the SELECT statement passed as the second argument does not invoke
698 ** any SQL window functions, this function is a no-op. Otherwise, it
699 ** rewrites the SELECT statement so that window function xStep functions
700 ** are invoked in the correct order as described under "SELECT REWRITING"
701 ** at the top of this file.
703 int sqlite3WindowRewrite(Parse
*pParse
, Select
*p
){
706 Vdbe
*v
= sqlite3GetVdbe(pParse
);
707 sqlite3
*db
= pParse
->db
;
708 Select
*pSub
= 0; /* The subquery */
709 SrcList
*pSrc
= p
->pSrc
;
710 Expr
*pWhere
= p
->pWhere
;
711 ExprList
*pGroupBy
= p
->pGroupBy
;
712 Expr
*pHaving
= p
->pHaving
;
715 ExprList
*pSublist
= 0; /* Expression list for sub-query */
716 Window
*pMWin
= p
->pWin
; /* Master window object */
717 Window
*pWin
; /* Window object iterator */
724 /* Create the ORDER BY clause for the sub-select. This is the concatenation
725 ** of the window PARTITION and ORDER BY clauses. Then, if this makes it
726 ** redundant, remove the ORDER BY from the parent SELECT. */
727 pSort
= sqlite3ExprListDup(db
, pMWin
->pPartition
, 0);
728 pSort
= exprListAppendList(pParse
, pSort
, pMWin
->pOrderBy
);
729 if( pSort
&& p
->pOrderBy
){
730 if( sqlite3ExprListCompare(pSort
, p
->pOrderBy
, -1)==0 ){
731 sqlite3ExprListDelete(db
, p
->pOrderBy
);
736 /* Assign a cursor number for the ephemeral table used to buffer rows.
737 ** The OpenEphemeral instruction is coded later, after it is known how
738 ** many columns the table will have. */
739 pMWin
->iEphCsr
= pParse
->nTab
++;
741 selectWindowRewriteEList(pParse
, pMWin
, p
->pEList
, &pSublist
);
742 selectWindowRewriteEList(pParse
, pMWin
, p
->pOrderBy
, &pSublist
);
743 pMWin
->nBufferCol
= (pSublist
? pSublist
->nExpr
: 0);
745 /* Append the PARTITION BY and ORDER BY expressions to the to the
746 ** sub-select expression list. They are required to figure out where
747 ** boundaries for partitions and sets of peer rows lie. */
748 pSublist
= exprListAppendList(pParse
, pSublist
, pMWin
->pPartition
);
749 pSublist
= exprListAppendList(pParse
, pSublist
, pMWin
->pOrderBy
);
751 /* Append the arguments passed to each window function to the
752 ** sub-select expression list. Also allocate two registers for each
753 ** window function - one for the accumulator, another for interim
755 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
756 pWin
->iArgCol
= (pSublist
? pSublist
->nExpr
: 0);
757 pSublist
= exprListAppendList(pParse
, pSublist
, pWin
->pOwner
->x
.pList
);
759 Expr
*pFilter
= sqlite3ExprDup(db
, pWin
->pFilter
, 0);
760 pSublist
= sqlite3ExprListAppend(pParse
, pSublist
, pFilter
);
762 pWin
->regAccum
= ++pParse
->nMem
;
763 pWin
->regResult
= ++pParse
->nMem
;
764 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regAccum
);
767 /* If there is no ORDER BY or PARTITION BY clause, and the window
768 ** function accepts zero arguments, and there are no other columns
769 ** selected (e.g. "SELECT row_number() OVER () FROM t1"), it is possible
770 ** that pSublist is still NULL here. Add a constant expression here to
771 ** keep everything legal in this case.
774 pSublist
= sqlite3ExprListAppend(pParse
, 0,
775 sqlite3ExprAlloc(db
, TK_INTEGER
, &sqlite3IntTokens
[0], 0)
779 pSub
= sqlite3SelectNew(
780 pParse
, pSublist
, pSrc
, pWhere
, pGroupBy
, pHaving
, pSort
, 0, 0
782 p
->pSrc
= sqlite3SrcListAppend(db
, 0, 0, 0);
783 assert( p
->pSrc
|| db
->mallocFailed
);
785 p
->pSrc
->a
[0].pSelect
= pSub
;
786 sqlite3SrcListAssignCursors(pParse
, p
->pSrc
);
787 if( sqlite3ExpandSubquery(pParse
, &p
->pSrc
->a
[0]) ){
790 pSub
->selFlags
|= SF_Expanded
;
791 p
->selFlags
&= ~SF_Aggregate
;
792 sqlite3SelectPrep(pParse
, pSub
, 0);
795 sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, pMWin
->iEphCsr
, pSublist
->nExpr
);
797 sqlite3SelectDelete(db
, pSub
);
799 if( db
->mallocFailed
) rc
= SQLITE_NOMEM
;
806 ** Free the Window object passed as the second argument.
808 void sqlite3WindowDelete(sqlite3
*db
, Window
*p
){
810 sqlite3ExprDelete(db
, p
->pFilter
);
811 sqlite3ExprListDelete(db
, p
->pPartition
);
812 sqlite3ExprListDelete(db
, p
->pOrderBy
);
813 sqlite3ExprDelete(db
, p
->pEnd
);
814 sqlite3ExprDelete(db
, p
->pStart
);
815 sqlite3DbFree(db
, p
->zName
);
816 sqlite3DbFree(db
, p
);
821 ** Free the linked list of Window objects starting at the second argument.
823 void sqlite3WindowListDelete(sqlite3
*db
, Window
*p
){
825 Window
*pNext
= p
->pNextWin
;
826 sqlite3WindowDelete(db
, p
);
832 ** Allocate and return a new Window object.
834 Window
*sqlite3WindowAlloc(
837 int eStart
, Expr
*pStart
,
842 if( eType
==TK_RANGE
&& (pStart
|| pEnd
) ){
843 sqlite3ErrorMsg(pParse
, "RANGE %s is only supported with UNBOUNDED",
844 (pStart
? "PRECEDING" : "FOLLOWING")
847 pWin
= (Window
*)sqlite3DbMallocZero(pParse
->db
, sizeof(Window
));
853 pWin
->eStart
= eStart
;
856 pWin
->pStart
= pStart
;
858 sqlite3ExprDelete(pParse
->db
, pEnd
);
859 sqlite3ExprDelete(pParse
->db
, pStart
);
866 ** Attach window object pWin to expression p.
868 void sqlite3WindowAttach(Parse
*pParse
, Expr
*p
, Window
*pWin
){
873 if( p
->flags
& EP_Distinct
){
874 sqlite3ErrorMsg(pParse
,"DISTINCT is not supported for window functions");
878 sqlite3WindowDelete(pParse
->db
, pWin
);
883 ** Return 0 if the two window objects are identical, or non-zero otherwise.
884 ** Identical window objects can be processed in a single scan.
886 int sqlite3WindowCompare(Parse
*pParse
, Window
*p1
, Window
*p2
){
887 if( p1
->eType
!=p2
->eType
) return 1;
888 if( p1
->eStart
!=p2
->eStart
) return 1;
889 if( p1
->eEnd
!=p2
->eEnd
) return 1;
890 if( sqlite3ExprCompare(pParse
, p1
->pStart
, p2
->pStart
, -1) ) return 1;
891 if( sqlite3ExprCompare(pParse
, p1
->pEnd
, p2
->pEnd
, -1) ) return 1;
892 if( sqlite3ExprListCompare(p1
->pPartition
, p2
->pPartition
, -1) ) return 1;
893 if( sqlite3ExprListCompare(p1
->pOrderBy
, p2
->pOrderBy
, -1) ) return 1;
899 ** This is called by code in select.c before it calls sqlite3WhereBegin()
900 ** to begin iterating through the sub-query results. It is used to allocate
901 ** and initialize registers and cursors used by sqlite3WindowCodeStep().
903 void sqlite3WindowCodeInit(Parse
*pParse
, Window
*pMWin
){
905 Vdbe
*v
= sqlite3GetVdbe(pParse
);
906 int nPart
= (pMWin
->pPartition
? pMWin
->pPartition
->nExpr
: 0);
907 nPart
+= (pMWin
->pOrderBy
? pMWin
->pOrderBy
->nExpr
: 0);
909 pMWin
->regPart
= pParse
->nMem
+1;
910 pParse
->nMem
+= nPart
;
911 sqlite3VdbeAddOp3(v
, OP_Null
, 0, pMWin
->regPart
, pMWin
->regPart
+nPart
-1);
914 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
915 FuncDef
*p
= pWin
->pFunc
;
916 if( (p
->funcFlags
& SQLITE_FUNC_MINMAX
) && pWin
->eStart
!=TK_UNBOUNDED
){
917 /* The inline versions of min() and max() require a single ephemeral
918 ** table and 3 registers. The registers are used as follows:
920 ** regApp+0: slot to copy min()/max() argument to for MakeRecord
921 ** regApp+1: integer value used to ensure keys are unique
922 ** regApp+2: output of MakeRecord
924 ExprList
*pList
= pWin
->pOwner
->x
.pList
;
925 KeyInfo
*pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
, pList
, 0, 0);
926 pWin
->csrApp
= pParse
->nTab
++;
927 pWin
->regApp
= pParse
->nMem
+1;
929 if( pKeyInfo
&& pWin
->pFunc
->zName
[1]=='i' ){
930 assert( pKeyInfo
->aSortOrder
[0]==0 );
931 pKeyInfo
->aSortOrder
[0] = 1;
933 sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, pWin
->csrApp
, 2);
934 sqlite3VdbeAppendP4(v
, pKeyInfo
, P4_KEYINFO
);
935 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, pWin
->regApp
+1);
937 else if( p
->xSFunc
==nth_valueStepFunc
|| p
->xSFunc
==first_valueStepFunc
){
938 /* Allocate two registers at pWin->regApp. These will be used to
939 ** store the start and end index of the current frame. */
940 assert( pMWin
->iEphCsr
);
941 pWin
->regApp
= pParse
->nMem
+1;
942 pWin
->csrApp
= pParse
->nTab
++;
944 sqlite3VdbeAddOp2(v
, OP_OpenDup
, pWin
->csrApp
, pMWin
->iEphCsr
);
946 else if( p
->xSFunc
==leadStepFunc
|| p
->xSFunc
==lagStepFunc
){
947 assert( pMWin
->iEphCsr
);
948 pWin
->csrApp
= pParse
->nTab
++;
949 sqlite3VdbeAddOp2(v
, OP_OpenDup
, pWin
->csrApp
, pMWin
->iEphCsr
);
955 ** A "PRECEDING <expr>" (bEnd==0) or "FOLLOWING <expr>" (bEnd==1) has just
956 ** been evaluated and the result left in register reg. This function generates
957 ** VM code to check that the value is a non-negative integer and throws
958 ** an exception if it is not.
960 static void windowCheckFrameValue(Parse
*pParse
, int reg
, int bEnd
){
961 static const char *azErr
[] = {
962 "frame starting offset must be a non-negative integer",
963 "frame ending offset must be a non-negative integer"
965 Vdbe
*v
= sqlite3GetVdbe(pParse
);
966 int regZero
= sqlite3GetTempReg(pParse
);
967 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, regZero
);
968 sqlite3VdbeAddOp2(v
, OP_MustBeInt
, reg
, sqlite3VdbeCurrentAddr(v
)+2);
969 sqlite3VdbeAddOp3(v
, OP_Ge
, regZero
, sqlite3VdbeCurrentAddr(v
)+2, reg
);
971 sqlite3VdbeAddOp2(v
, OP_Halt
, SQLITE_ERROR
, OE_Abort
);
972 sqlite3VdbeAppendP4(v
, (void*)azErr
[bEnd
], P4_STATIC
);
973 sqlite3ReleaseTempReg(pParse
, regZero
);
977 ** Return the number of arguments passed to the window-function associated
978 ** with the object passed as the only argument to this function.
980 static int windowArgCount(Window
*pWin
){
981 ExprList
*pList
= pWin
->pOwner
->x
.pList
;
982 return (pList
? pList
->nExpr
: 0);
986 ** Generate VM code to invoke either xStep() (if bInverse is 0) or
987 ** xInverse (if bInverse is non-zero) for each window function in the
988 ** linked list starting at pMWin. Or, for built-in window functions
989 ** that do not use the standard function API, generate the required
992 ** If argument csr is greater than or equal to 0, then argument reg is
993 ** the first register in an array of registers guaranteed to be large
994 ** enough to hold the array of arguments for each function. In this case
995 ** the arguments are extracted from the current row of csr into the
996 ** array of registers before invoking OP_AggStep or OP_AggInverse
998 ** Or, if csr is less than zero, then the array of registers at reg is
999 ** already populated with all columns from the current row of the sub-query.
1001 ** If argument regPartSize is non-zero, then it is a register containing the
1002 ** number of rows in the current partition.
1004 static void windowAggStep(
1006 Window
*pMWin
, /* Linked list of window functions */
1007 int csr
, /* Read arguments from this cursor */
1008 int bInverse
, /* True to invoke xInverse instead of xStep */
1009 int reg
, /* Array of registers */
1010 int regPartSize
/* Register containing size of partition */
1012 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1014 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
1015 int flags
= pWin
->pFunc
->funcFlags
;
1017 int nArg
= windowArgCount(pWin
);
1021 for(i
=0; i
<nArg
; i
++){
1022 sqlite3VdbeAddOp3(v
, OP_Column
, csr
, pWin
->iArgCol
+i
, reg
+i
);
1025 if( flags
& SQLITE_FUNC_WINDOW_SIZE
){
1027 regArg
= regPartSize
;
1029 sqlite3VdbeAddOp2(v
, OP_SCopy
, regPartSize
, reg
+nArg
);
1034 assert( !(flags
& SQLITE_FUNC_WINDOW_SIZE
) );
1035 regArg
= reg
+ pWin
->iArgCol
;
1038 if( (pWin
->pFunc
->funcFlags
& SQLITE_FUNC_MINMAX
)
1039 && pWin
->eStart
!=TK_UNBOUNDED
1042 sqlite3VdbeAddOp2(v
, OP_AddImm
, pWin
->regApp
+1, 1);
1043 sqlite3VdbeAddOp2(v
, OP_SCopy
, regArg
, pWin
->regApp
);
1044 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, pWin
->regApp
, 2, pWin
->regApp
+2);
1045 sqlite3VdbeAddOp2(v
, OP_IdxInsert
, pWin
->csrApp
, pWin
->regApp
+2);
1047 sqlite3VdbeAddOp4Int(v
, OP_SeekGE
, pWin
->csrApp
, 0, regArg
, 1);
1049 sqlite3VdbeAddOp1(v
, OP_Delete
, pWin
->csrApp
);
1050 sqlite3VdbeJumpHere(v
, sqlite3VdbeCurrentAddr(v
)-2);
1052 }else if( pWin
->regApp
){
1053 assert( pWin
->pFunc
->xSFunc
==nth_valueStepFunc
1054 || pWin
->pFunc
->xSFunc
==first_valueStepFunc
1056 assert( bInverse
==0 || bInverse
==1 );
1057 sqlite3VdbeAddOp2(v
, OP_AddImm
, pWin
->regApp
+1-bInverse
, 1);
1058 }else if( pWin
->pFunc
->xSFunc
==leadStepFunc
1059 || pWin
->pFunc
->xSFunc
==lagStepFunc
1064 if( pWin
->pFilter
){
1066 assert( nArg
==pWin
->pOwner
->x
.pList
->nExpr
);
1068 regTmp
= sqlite3GetTempReg(pParse
);
1069 sqlite3VdbeAddOp3(v
, OP_Column
, csr
, pWin
->iArgCol
+nArg
,regTmp
);
1071 regTmp
= regArg
+ nArg
;
1073 addrIf
= sqlite3VdbeAddOp3(v
, OP_IfNot
, regTmp
, 0, 1);
1076 sqlite3ReleaseTempReg(pParse
, regTmp
);
1079 if( pWin
->pFunc
->funcFlags
& SQLITE_FUNC_NEEDCOLL
){
1081 pColl
= sqlite3ExprNNCollSeq(pParse
, pWin
->pOwner
->x
.pList
->a
[0].pExpr
);
1082 sqlite3VdbeAddOp4(v
, OP_CollSeq
, 0,0,0, (const char*)pColl
, P4_COLLSEQ
);
1084 sqlite3VdbeAddOp3(v
, bInverse
? OP_AggInverse
: OP_AggStep
,
1085 bInverse
, regArg
, pWin
->regAccum
);
1086 sqlite3VdbeAppendP4(v
, pWin
->pFunc
, P4_FUNCDEF
);
1087 sqlite3VdbeChangeP5(v
, (u8
)nArg
);
1088 if( addrIf
) sqlite3VdbeJumpHere(v
, addrIf
);
1094 ** Generate VM code to invoke either xValue() (bFinal==0) or xFinalize()
1095 ** (bFinal==1) for each window function in the linked list starting at
1096 ** pMWin. Or, for built-in window-functions that do not use the standard
1097 ** API, generate the equivalent VM code.
1099 static void windowAggFinal(Parse
*pParse
, Window
*pMWin
, int bFinal
){
1100 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1103 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
1104 if( (pWin
->pFunc
->funcFlags
& SQLITE_FUNC_MINMAX
)
1105 && pWin
->eStart
!=TK_UNBOUNDED
1107 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regResult
);
1108 sqlite3VdbeAddOp1(v
, OP_Last
, pWin
->csrApp
);
1110 sqlite3VdbeAddOp3(v
, OP_Column
, pWin
->csrApp
, 0, pWin
->regResult
);
1111 sqlite3VdbeJumpHere(v
, sqlite3VdbeCurrentAddr(v
)-2);
1113 sqlite3VdbeAddOp1(v
, OP_ResetSorter
, pWin
->csrApp
);
1115 }else if( pWin
->regApp
){
1118 sqlite3VdbeAddOp2(v
, OP_AggFinal
, pWin
->regAccum
, windowArgCount(pWin
));
1119 sqlite3VdbeAppendP4(v
, pWin
->pFunc
, P4_FUNCDEF
);
1120 sqlite3VdbeAddOp2(v
, OP_Copy
, pWin
->regAccum
, pWin
->regResult
);
1121 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regAccum
);
1123 sqlite3VdbeAddOp3(v
, OP_AggValue
, pWin
->regAccum
, windowArgCount(pWin
),
1125 sqlite3VdbeAppendP4(v
, pWin
->pFunc
, P4_FUNCDEF
);
1132 ** This function generates VM code to invoke the sub-routine at address
1133 ** lblFlushPart once for each partition with the entire partition cached in
1134 ** the Window.iEphCsr temp table.
1136 static void windowPartitionCache(
1138 Select
*p
, /* The rewritten SELECT statement */
1139 WhereInfo
*pWInfo
, /* WhereInfo to call WhereEnd() on */
1140 int regFlushPart
, /* Register to use with Gosub lblFlushPart */
1141 int lblFlushPart
, /* Subroutine to Gosub to */
1142 int *pRegSize
/* OUT: Register containing partition size */
1144 Window
*pMWin
= p
->pWin
;
1145 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1146 int iSubCsr
= p
->pSrc
->a
[0].iCursor
;
1147 int nSub
= p
->pSrc
->a
[0].pTab
->nCol
;
1150 int reg
= pParse
->nMem
+1;
1151 int regRecord
= reg
+nSub
;
1152 int regRowid
= regRecord
+1;
1154 *pRegSize
= regRowid
;
1155 pParse
->nMem
+= nSub
+ 2;
1157 /* Martial the row returned by the sub-select into an array of
1159 for(k
=0; k
<nSub
; k
++){
1160 sqlite3VdbeAddOp3(v
, OP_Column
, iSubCsr
, k
, reg
+k
);
1162 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, reg
, nSub
, regRecord
);
1164 /* Check if this is the start of a new partition. If so, call the
1165 ** flush_partition sub-routine. */
1166 if( pMWin
->pPartition
){
1168 ExprList
*pPart
= pMWin
->pPartition
;
1169 int nPart
= pPart
->nExpr
;
1170 int regNewPart
= reg
+ pMWin
->nBufferCol
;
1171 KeyInfo
*pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
, pPart
, 0, 0);
1173 addr
= sqlite3VdbeAddOp3(v
, OP_Compare
, regNewPart
, pMWin
->regPart
,nPart
);
1174 sqlite3VdbeAppendP4(v
, (void*)pKeyInfo
, P4_KEYINFO
);
1175 sqlite3VdbeAddOp3(v
, OP_Jump
, addr
+2, addr
+4, addr
+2);
1177 sqlite3VdbeAddOp3(v
, OP_Copy
, regNewPart
, pMWin
->regPart
, nPart
-1);
1178 sqlite3VdbeAddOp2(v
, OP_Gosub
, regFlushPart
, lblFlushPart
);
1181 /* Buffer the current row in the ephemeral table. */
1182 sqlite3VdbeAddOp2(v
, OP_NewRowid
, pMWin
->iEphCsr
, regRowid
);
1183 sqlite3VdbeAddOp3(v
, OP_Insert
, pMWin
->iEphCsr
, regRecord
, regRowid
);
1185 /* End of the input loop */
1186 sqlite3WhereEnd(pWInfo
);
1188 /* Invoke "flush_partition" to deal with the final (or only) partition */
1189 sqlite3VdbeAddOp2(v
, OP_Gosub
, regFlushPart
, lblFlushPart
);
1193 ** Invoke the sub-routine at regGosub (generated by code in select.c) to
1194 ** return the current row of Window.iEphCsr. If all window functions are
1195 ** aggregate window functions that use the standard API, a single
1196 ** OP_Gosub instruction is all that this routine generates. Extra VM code
1197 ** for per-row processing is only generated for the following built-in window
1205 static void windowReturnOneRow(
1211 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1213 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
1214 FuncDef
*pFunc
= pWin
->pFunc
;
1215 if( pFunc
->xSFunc
==nth_valueStepFunc
1216 || pFunc
->xSFunc
==first_valueStepFunc
1218 int csr
= pWin
->csrApp
;
1219 int lbl
= sqlite3VdbeMakeLabel(v
);
1220 int tmpReg
= sqlite3GetTempReg(pParse
);
1221 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regResult
);
1223 if( pFunc
->xSFunc
==nth_valueStepFunc
){
1224 sqlite3VdbeAddOp3(v
, OP_Column
, pMWin
->iEphCsr
, pWin
->iArgCol
+1,tmpReg
);
1226 sqlite3VdbeAddOp2(v
, OP_Integer
, 1, tmpReg
);
1228 sqlite3VdbeAddOp3(v
, OP_Add
, tmpReg
, pWin
->regApp
, tmpReg
);
1229 sqlite3VdbeAddOp3(v
, OP_Gt
, pWin
->regApp
+1, lbl
, tmpReg
);
1231 sqlite3VdbeAddOp3(v
, OP_SeekRowid
, csr
, lbl
, tmpReg
);
1233 sqlite3VdbeAddOp3(v
, OP_Column
, csr
, pWin
->iArgCol
, pWin
->regResult
);
1234 sqlite3VdbeResolveLabel(v
, lbl
);
1235 sqlite3ReleaseTempReg(pParse
, tmpReg
);
1237 else if( pFunc
->xSFunc
==leadStepFunc
|| pFunc
->xSFunc
==lagStepFunc
){
1238 int nArg
= pWin
->pOwner
->x
.pList
->nExpr
;
1239 int iEph
= pMWin
->iEphCsr
;
1240 int csr
= pWin
->csrApp
;
1241 int lbl
= sqlite3VdbeMakeLabel(v
);
1242 int tmpReg
= sqlite3GetTempReg(pParse
);
1245 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regResult
);
1247 sqlite3VdbeAddOp3(v
, OP_Column
, iEph
, pWin
->iArgCol
+2, pWin
->regResult
);
1249 sqlite3VdbeAddOp2(v
, OP_Rowid
, iEph
, tmpReg
);
1251 int val
= (pFunc
->xSFunc
==leadStepFunc
? 1 : -1);
1252 sqlite3VdbeAddOp2(v
, OP_AddImm
, tmpReg
, val
);
1254 int op
= (pFunc
->xSFunc
==leadStepFunc
? OP_Add
: OP_Subtract
);
1255 int tmpReg2
= sqlite3GetTempReg(pParse
);
1256 sqlite3VdbeAddOp3(v
, OP_Column
, iEph
, pWin
->iArgCol
+1, tmpReg2
);
1257 sqlite3VdbeAddOp3(v
, op
, tmpReg2
, tmpReg
, tmpReg
);
1258 sqlite3ReleaseTempReg(pParse
, tmpReg2
);
1261 sqlite3VdbeAddOp3(v
, OP_SeekRowid
, csr
, lbl
, tmpReg
);
1263 sqlite3VdbeAddOp3(v
, OP_Column
, csr
, pWin
->iArgCol
, pWin
->regResult
);
1264 sqlite3VdbeResolveLabel(v
, lbl
);
1265 sqlite3ReleaseTempReg(pParse
, tmpReg
);
1268 sqlite3VdbeAddOp2(v
, OP_Gosub
, regGosub
, addrGosub
);
1272 ** Invoke the code generated by windowReturnOneRow() and, optionally, the
1273 ** xInverse() function for each window function, for one or more rows
1274 ** from the Window.iEphCsr temp table. This routine generates VM code
1277 ** while( regCtr>0 ){
1279 ** windowReturnOneRow()
1283 ** Next (Window.iEphCsr)
1286 static void windowReturnRows(
1288 Window
*pMWin
, /* List of window functions */
1289 int regCtr
, /* Register containing number of rows */
1290 int regGosub
, /* Register for Gosub addrGosub */
1291 int addrGosub
, /* Address of sub-routine for ReturnOneRow */
1292 int regInvArg
, /* Array of registers for xInverse args */
1293 int regInvSize
/* Register containing size of partition */
1296 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1297 windowAggFinal(pParse
, pMWin
, 0);
1298 addr
= sqlite3VdbeAddOp3(v
, OP_IfPos
, regCtr
, sqlite3VdbeCurrentAddr(v
)+2 ,1);
1300 sqlite3VdbeAddOp2(v
, OP_Goto
, 0, 0);
1301 windowReturnOneRow(pParse
, pMWin
, regGosub
, addrGosub
);
1303 windowAggStep(pParse
, pMWin
, pMWin
->iEphCsr
, 1, regInvArg
, regInvSize
);
1305 sqlite3VdbeAddOp2(v
, OP_Next
, pMWin
->iEphCsr
, addr
);
1307 sqlite3VdbeJumpHere(v
, addr
+1); /* The OP_Goto */
1311 ** Generate code to set the accumulator register for each window function
1312 ** in the linked list passed as the second argument to NULL. And perform
1313 ** any equivalent initialization required by any built-in window functions
1316 static int windowInitAccum(Parse
*pParse
, Window
*pMWin
){
1317 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1321 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
1322 FuncDef
*pFunc
= pWin
->pFunc
;
1323 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regAccum
);
1324 nArg
= MAX(nArg
, windowArgCount(pWin
));
1325 if( pFunc
->xSFunc
==nth_valueStepFunc
1326 || pFunc
->xSFunc
==first_valueStepFunc
1328 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, pWin
->regApp
);
1329 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, pWin
->regApp
+1);
1332 if( (pFunc
->funcFlags
& SQLITE_FUNC_MINMAX
) && pWin
->csrApp
){
1333 assert( pWin
->eStart
!=TK_UNBOUNDED
);
1334 sqlite3VdbeAddOp1(v
, OP_ResetSorter
, pWin
->csrApp
);
1335 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, pWin
->regApp
+1);
1338 regArg
= pParse
->nMem
+1;
1339 pParse
->nMem
+= nArg
;
1345 ** This function does the work of sqlite3WindowCodeStep() for all "ROWS"
1346 ** window frame types except for "BETWEEN UNBOUNDED PRECEDING AND CURRENT
1347 ** ROW". Pseudo-code for each follows.
1349 ** ROWS BETWEEN <expr1> PRECEDING AND <expr2> FOLLOWING
1352 ** if( new partition ){
1353 ** Gosub flush_partition
1355 ** Insert (record in eph-table)
1356 ** sqlite3WhereEnd()
1357 ** Gosub flush_partition
1361 ** OpenDup (iEphCsr -> csrStart)
1362 ** OpenDup (iEphCsr -> csrEnd)
1364 ** regStart = <expr1> // PRECEDING expression
1365 ** regEnd = <expr2> // FOLLOWING expression
1366 ** if( regStart<0 || regEnd<0 ){ error! }
1367 ** Rewind (csr,csrStart,csrEnd) // if EOF goto flush_partition_done
1368 ** Next(csrEnd) // if EOF skip Aggstep
1370 ** if( (regEnd--)<=0 ){
1371 ** AggFinal (xValue)
1373 ** Next(csr) // if EOF goto flush_partition_done
1374 ** if( (regStart--)<=0 ){
1375 ** AggInverse (csrStart)
1379 ** flush_partition_done:
1380 ** ResetSorter (csr)
1383 ** ROWS BETWEEN <expr> PRECEDING AND CURRENT ROW
1384 ** ROWS BETWEEN CURRENT ROW AND <expr> FOLLOWING
1385 ** ROWS BETWEEN UNBOUNDED PRECEDING AND <expr> FOLLOWING
1387 ** These are similar to the above. For "CURRENT ROW", intialize the
1388 ** register to 0. For "UNBOUNDED PRECEDING" to infinity.
1390 ** ROWS BETWEEN <expr> PRECEDING AND UNBOUNDED FOLLOWING
1391 ** ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
1393 ** Rewind (csr,csrStart,csrEnd) // if EOF goto flush_partition_done
1395 ** Next(csrEnd) // Exit while(1) at EOF
1399 ** AggFinal (xValue)
1401 ** Next(csr) // if EOF goto flush_partition_done
1402 ** if( (regStart--)<=0 ){
1403 ** AggInverse (csrStart)
1408 ** For the "CURRENT ROW AND UNBOUNDED FOLLOWING" case, the final if()
1409 ** condition is always true (as if regStart were initialized to 0).
1411 ** RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
1413 ** This is the only RANGE case handled by this routine. It modifies the
1414 ** second while( 1 ) loop in "ROWS BETWEEN CURRENT ... UNBOUNDED..." to
1418 ** AggFinal (xValue)
1422 ** Next(csr) // if EOF goto flush_partition_done
1423 ** if( new peer ) break;
1425 ** while( (regPeer--)>0 ){
1426 ** AggInverse (csrStart)
1431 ** ROWS BETWEEN <expr> FOLLOWING AND <expr> FOLLOWING
1433 ** regEnd = regEnd - regStart
1434 ** Rewind (csr,csrStart,csrEnd) // if EOF goto flush_partition_done
1436 ** Next(csrEnd) // if EOF fall-through
1437 ** if( (regEnd--)<=0 ){
1438 ** if( (regStart--)<=0 ){
1439 ** AggFinal (xValue)
1441 ** Next(csr) // if EOF goto flush_partition_done
1443 ** AggInverse (csrStart)
1447 ** ROWS BETWEEN <expr> PRECEDING AND <expr> PRECEDING
1449 ** Replace the bit after "Rewind" in the above with:
1451 ** if( (regEnd--)<=0 ){
1455 ** AggFinal (xValue)
1457 ** Next(csr) // if EOF goto flush_partition_done
1458 ** if( (regStart--)<=0 ){
1459 ** AggInverse (csr2)
1464 static void windowCodeRowExprStep(
1471 Window
*pMWin
= p
->pWin
;
1472 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1473 int regFlushPart
; /* Register for "Gosub flush_partition" */
1474 int lblFlushPart
; /* Label for "Gosub flush_partition" */
1475 int lblFlushDone
; /* Label for "Gosub flush_partition_done" */
1479 int csrStart
= pParse
->nTab
++;
1480 int csrEnd
= pParse
->nTab
++;
1481 int regStart
; /* Value of <expr> PRECEDING */
1482 int regEnd
; /* Value of <expr> FOLLOWING */
1489 assert( pMWin
->eStart
==TK_PRECEDING
1490 || pMWin
->eStart
==TK_CURRENT
1491 || pMWin
->eStart
==TK_FOLLOWING
1492 || pMWin
->eStart
==TK_UNBOUNDED
1494 assert( pMWin
->eEnd
==TK_FOLLOWING
1495 || pMWin
->eEnd
==TK_CURRENT
1496 || pMWin
->eEnd
==TK_UNBOUNDED
1497 || pMWin
->eEnd
==TK_PRECEDING
1500 /* Allocate register and label for the "flush_partition" sub-routine. */
1501 regFlushPart
= ++pParse
->nMem
;
1502 lblFlushPart
= sqlite3VdbeMakeLabel(v
);
1503 lblFlushDone
= sqlite3VdbeMakeLabel(v
);
1505 regStart
= ++pParse
->nMem
;
1506 regEnd
= ++pParse
->nMem
;
1508 windowPartitionCache(pParse
, p
, pWInfo
, regFlushPart
, lblFlushPart
, ®Size
);
1510 addrGoto
= sqlite3VdbeAddOp0(v
, OP_Goto
);
1512 /* Start of "flush_partition" */
1513 sqlite3VdbeResolveLabel(v
, lblFlushPart
);
1514 sqlite3VdbeAddOp2(v
, OP_Once
, 0, sqlite3VdbeCurrentAddr(v
)+3);
1516 sqlite3VdbeAddOp2(v
, OP_OpenDup
, csrStart
, pMWin
->iEphCsr
);
1517 sqlite3VdbeAddOp2(v
, OP_OpenDup
, csrEnd
, pMWin
->iEphCsr
);
1519 /* If either regStart or regEnd are not non-negative integers, throw
1521 if( pMWin
->pStart
){
1522 sqlite3ExprCode(pParse
, pMWin
->pStart
, regStart
);
1523 windowCheckFrameValue(pParse
, regStart
, 0);
1526 sqlite3ExprCode(pParse
, pMWin
->pEnd
, regEnd
);
1527 windowCheckFrameValue(pParse
, regEnd
, 1);
1530 /* If this is "ROWS <expr1> FOLLOWING AND ROWS <expr2> FOLLOWING", do:
1532 ** if( regEnd<regStart ){
1533 ** // The frame always consists of 0 rows
1534 ** regStart = regSize;
1536 ** regEnd = regEnd - regStart;
1538 if( pMWin
->pEnd
&& pMWin
->pStart
&& pMWin
->eStart
==TK_FOLLOWING
){
1539 assert( pMWin
->eEnd
==TK_FOLLOWING
);
1540 sqlite3VdbeAddOp3(v
, OP_Ge
, regStart
, sqlite3VdbeCurrentAddr(v
)+2, regEnd
);
1542 sqlite3VdbeAddOp2(v
, OP_Copy
, regSize
, regStart
);
1543 sqlite3VdbeAddOp3(v
, OP_Subtract
, regStart
, regEnd
, regEnd
);
1546 if( pMWin
->pEnd
&& pMWin
->pStart
&& pMWin
->eEnd
==TK_PRECEDING
){
1547 assert( pMWin
->eStart
==TK_PRECEDING
);
1548 sqlite3VdbeAddOp3(v
, OP_Le
, regStart
, sqlite3VdbeCurrentAddr(v
)+3, regEnd
);
1550 sqlite3VdbeAddOp2(v
, OP_Copy
, regSize
, regStart
);
1551 sqlite3VdbeAddOp2(v
, OP_Copy
, regSize
, regEnd
);
1554 /* Initialize the accumulator register for each window function to NULL */
1555 regArg
= windowInitAccum(pParse
, pMWin
);
1557 sqlite3VdbeAddOp2(v
, OP_Rewind
, pMWin
->iEphCsr
, lblFlushDone
);
1559 sqlite3VdbeAddOp2(v
, OP_Rewind
, csrStart
, lblFlushDone
);
1560 VdbeCoverageNeverTaken(v
);
1561 sqlite3VdbeChangeP5(v
, 1);
1562 sqlite3VdbeAddOp2(v
, OP_Rewind
, csrEnd
, lblFlushDone
);
1563 VdbeCoverageNeverTaken(v
);
1564 sqlite3VdbeChangeP5(v
, 1);
1566 /* Invoke AggStep function for each window function using the row that
1567 ** csrEnd currently points to. Or, if csrEnd is already at EOF,
1569 addrTop
= sqlite3VdbeCurrentAddr(v
);
1570 if( pMWin
->eEnd
==TK_PRECEDING
){
1571 addrIfPos1
= sqlite3VdbeAddOp3(v
, OP_IfPos
, regEnd
, 0 , 1);
1574 sqlite3VdbeAddOp2(v
, OP_Next
, csrEnd
, sqlite3VdbeCurrentAddr(v
)+2);
1576 addr
= sqlite3VdbeAddOp0(v
, OP_Goto
);
1577 windowAggStep(pParse
, pMWin
, csrEnd
, 0, regArg
, regSize
);
1578 if( pMWin
->eEnd
==TK_UNBOUNDED
){
1579 sqlite3VdbeAddOp2(v
, OP_Goto
, 0, addrTop
);
1580 sqlite3VdbeJumpHere(v
, addr
);
1581 addrTop
= sqlite3VdbeCurrentAddr(v
);
1583 sqlite3VdbeJumpHere(v
, addr
);
1584 if( pMWin
->eEnd
==TK_PRECEDING
){
1585 sqlite3VdbeJumpHere(v
, addrIfPos1
);
1589 if( pMWin
->eEnd
==TK_FOLLOWING
){
1590 addrIfPos1
= sqlite3VdbeAddOp3(v
, OP_IfPos
, regEnd
, 0 , 1);
1593 if( pMWin
->eStart
==TK_FOLLOWING
){
1594 addrIfPos2
= sqlite3VdbeAddOp3(v
, OP_IfPos
, regStart
, 0 , 1);
1597 windowAggFinal(pParse
, pMWin
, 0);
1598 windowReturnOneRow(pParse
, pMWin
, regGosub
, addrGosub
);
1599 sqlite3VdbeAddOp2(v
, OP_Next
, pMWin
->iEphCsr
, sqlite3VdbeCurrentAddr(v
)+2);
1601 sqlite3VdbeAddOp2(v
, OP_Goto
, 0, lblFlushDone
);
1602 if( pMWin
->eStart
==TK_FOLLOWING
){
1603 sqlite3VdbeJumpHere(v
, addrIfPos2
);
1606 if( pMWin
->eStart
==TK_CURRENT
1607 || pMWin
->eStart
==TK_PRECEDING
1608 || pMWin
->eStart
==TK_FOLLOWING
1610 int lblSkipInverse
= sqlite3VdbeMakeLabel(v
);;
1611 if( pMWin
->eStart
==TK_PRECEDING
){
1612 sqlite3VdbeAddOp3(v
, OP_IfPos
, regStart
, lblSkipInverse
, 1);
1615 if( pMWin
->eStart
==TK_FOLLOWING
){
1616 sqlite3VdbeAddOp2(v
, OP_Next
, csrStart
, sqlite3VdbeCurrentAddr(v
)+2);
1618 sqlite3VdbeAddOp2(v
, OP_Goto
, 0, lblSkipInverse
);
1620 sqlite3VdbeAddOp2(v
, OP_Next
, csrStart
, sqlite3VdbeCurrentAddr(v
)+1);
1623 windowAggStep(pParse
, pMWin
, csrStart
, 1, regArg
, regSize
);
1624 sqlite3VdbeResolveLabel(v
, lblSkipInverse
);
1626 if( pMWin
->eEnd
==TK_FOLLOWING
){
1627 sqlite3VdbeJumpHere(v
, addrIfPos1
);
1629 sqlite3VdbeAddOp2(v
, OP_Goto
, 0, addrTop
);
1631 /* flush_partition_done: */
1632 sqlite3VdbeResolveLabel(v
, lblFlushDone
);
1633 sqlite3VdbeAddOp1(v
, OP_ResetSorter
, pMWin
->iEphCsr
);
1634 sqlite3VdbeAddOp1(v
, OP_Return
, regFlushPart
);
1636 /* Jump to here to skip over flush_partition */
1637 sqlite3VdbeJumpHere(v
, addrGoto
);
1641 ** This function does the work of sqlite3WindowCodeStep() for cases that
1642 ** would normally be handled by windowCodeDefaultStep() when there are
1643 ** one or more built-in window-functions that require the entire partition
1644 ** to be cached in a temp table before any rows can be returned. Additionally.
1645 ** "RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING" is always handled by
1648 ** Pseudo-code corresponding to the VM code generated by this function
1649 ** for each type of window follows.
1651 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1655 ** OpenDup (iEphCsr -> csrLead)
1658 ** foreach row (csrLead){
1660 ** AggFinal (xValue)
1661 ** for(i=0; i<ctr; i++){
1667 ** AggStep (csrLead)
1671 ** AggFinal (xFinalize)
1672 ** for(i=0; i<ctr; i++){
1677 ** ResetSorter (csr)
1680 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1682 ** As above, except that the "if( new peer )" branch is always taken.
1684 ** RANGE BETWEEN CURRENT ROW AND CURRENT ROW
1686 ** As above, except that each of the for() loops becomes:
1688 ** for(i=0; i<ctr; i++){
1690 ** AggInverse (iEphCsr)
1694 ** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
1698 ** OpenDup (iEphCsr -> csrLead)
1700 ** foreach row (csrLead) {
1701 ** AggStep (csrLead)
1703 ** foreach row (iEphCsr) {
1707 ** RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
1711 ** OpenDup (iEphCsr -> csrLead)
1713 ** foreach row (csrLead){
1714 ** AggStep (csrLead)
1718 ** foreach row (csrLead){
1720 ** AggFinal (xValue)
1721 ** for(i=0; i<ctr; i++){
1723 ** AggInverse (iEphCsr)
1731 ** AggFinal (xFinalize)
1732 ** for(i=0; i<ctr; i++){
1737 ** ResetSorter (csr)
1740 static void windowCodeCacheStep(
1747 Window
*pMWin
= p
->pWin
;
1748 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1751 ExprList
*pPart
= pMWin
->pPartition
;
1752 ExprList
*pOrderBy
= pMWin
->pOrderBy
;
1753 int nPeer
= pOrderBy
? pOrderBy
->nExpr
: 0;
1756 int addrGoto
; /* Address of Goto used to jump flush_par.. */
1757 int addrNext
; /* Jump here for next iteration of loop */
1762 int regArg
; /* Register array to martial function args */
1765 int bReverse
= pMWin
->pOrderBy
&& pMWin
->eStart
==TK_CURRENT
1766 && pMWin
->eEnd
==TK_UNBOUNDED
;
1768 assert( (pMWin
->eStart
==TK_UNBOUNDED
&& pMWin
->eEnd
==TK_CURRENT
)
1769 || (pMWin
->eStart
==TK_UNBOUNDED
&& pMWin
->eEnd
==TK_UNBOUNDED
)
1770 || (pMWin
->eStart
==TK_CURRENT
&& pMWin
->eEnd
==TK_CURRENT
)
1771 || (pMWin
->eStart
==TK_CURRENT
&& pMWin
->eEnd
==TK_UNBOUNDED
)
1774 lblEmpty
= sqlite3VdbeMakeLabel(v
);
1775 regNewPeer
= pParse
->nMem
+1;
1776 pParse
->nMem
+= nPeer
;
1778 /* Allocate register and label for the "flush_partition" sub-routine. */
1779 regFlushPart
= ++pParse
->nMem
;
1780 lblFlushPart
= sqlite3VdbeMakeLabel(v
);
1782 csrLead
= pParse
->nTab
++;
1783 regCtr
= ++pParse
->nMem
;
1785 windowPartitionCache(pParse
, p
, pWInfo
, regFlushPart
, lblFlushPart
, ®Size
);
1786 addrGoto
= sqlite3VdbeAddOp0(v
, OP_Goto
);
1788 /* Start of "flush_partition" */
1789 sqlite3VdbeResolveLabel(v
, lblFlushPart
);
1790 sqlite3VdbeAddOp2(v
, OP_Once
, 0, sqlite3VdbeCurrentAddr(v
)+2);
1792 sqlite3VdbeAddOp2(v
, OP_OpenDup
, csrLead
, pMWin
->iEphCsr
);
1794 /* Initialize the accumulator register for each window function to NULL */
1795 regArg
= windowInitAccum(pParse
, pMWin
);
1797 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, regCtr
);
1798 sqlite3VdbeAddOp2(v
, OP_Rewind
, csrLead
, lblEmpty
);
1800 sqlite3VdbeAddOp2(v
, OP_Rewind
, pMWin
->iEphCsr
, lblEmpty
);
1801 VdbeCoverageNeverTaken(v
);
1804 int addr
= sqlite3VdbeCurrentAddr(v
);
1805 windowAggStep(pParse
, pMWin
, csrLead
, 0, regArg
, regSize
);
1806 sqlite3VdbeAddOp2(v
, OP_Next
, csrLead
, addr
);
1808 sqlite3VdbeAddOp2(v
, OP_Rewind
, csrLead
, lblEmpty
);
1809 VdbeCoverageNeverTaken(v
);
1811 addrNext
= sqlite3VdbeCurrentAddr(v
);
1813 if( pOrderBy
&& (pMWin
->eEnd
==TK_CURRENT
|| pMWin
->eStart
==TK_CURRENT
) ){
1814 int bCurrent
= (pMWin
->eStart
==TK_CURRENT
);
1815 int addrJump
= 0; /* Address of OP_Jump below */
1816 if( pMWin
->eType
==TK_RANGE
){
1817 int iOff
= pMWin
->nBufferCol
+ (pPart
? pPart
->nExpr
: 0);
1818 int regPeer
= pMWin
->regPart
+ (pPart
? pPart
->nExpr
: 0);
1819 KeyInfo
*pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
, pOrderBy
, 0, 0);
1820 for(k
=0; k
<nPeer
; k
++){
1821 sqlite3VdbeAddOp3(v
, OP_Column
, csrLead
, iOff
+k
, regNewPeer
+k
);
1823 addr
= sqlite3VdbeAddOp3(v
, OP_Compare
, regNewPeer
, regPeer
, nPeer
);
1824 sqlite3VdbeAppendP4(v
, (void*)pKeyInfo
, P4_KEYINFO
);
1825 addrJump
= sqlite3VdbeAddOp3(v
, OP_Jump
, addr
+2, 0, addr
+2);
1827 sqlite3VdbeAddOp3(v
, OP_Copy
, regNewPeer
, regPeer
, nPeer
-1);
1830 windowReturnRows(pParse
, pMWin
, regCtr
, regGosub
, addrGosub
,
1831 (bCurrent
? regArg
: 0), (bCurrent
? regSize
: 0)
1833 if( addrJump
) sqlite3VdbeJumpHere(v
, addrJump
);
1837 windowAggStep(pParse
, pMWin
, csrLead
, 0, regArg
, regSize
);
1839 sqlite3VdbeAddOp2(v
, OP_AddImm
, regCtr
, 1);
1840 sqlite3VdbeAddOp2(v
, OP_Next
, csrLead
, addrNext
);
1843 windowReturnRows(pParse
, pMWin
, regCtr
, regGosub
, addrGosub
, 0, 0);
1845 sqlite3VdbeResolveLabel(v
, lblEmpty
);
1846 sqlite3VdbeAddOp1(v
, OP_ResetSorter
, pMWin
->iEphCsr
);
1847 sqlite3VdbeAddOp1(v
, OP_Return
, regFlushPart
);
1849 /* Jump to here to skip over flush_partition */
1850 sqlite3VdbeJumpHere(v
, addrGoto
);
1855 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1858 ** if( new partition ){
1859 ** AggFinal (xFinalize)
1861 ** ResetSorter eph-table
1863 ** else if( new peer ){
1864 ** AggFinal (xValue)
1866 ** ResetSorter eph-table
1869 ** Insert (record into eph-table)
1870 ** sqlite3WhereEnd()
1871 ** AggFinal (xFinalize)
1874 ** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
1876 ** As above, except take no action for a "new peer". Invoke
1877 ** the sub-routine once only for each partition.
1879 ** RANGE BETWEEN CURRENT ROW AND CURRENT ROW
1881 ** As above, except that the "new peer" condition is handled in the
1882 ** same way as "new partition" (so there is no "else if" block).
1884 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1886 ** As above, except assume every row is a "new peer".
1888 static void windowCodeDefaultStep(
1895 Window
*pMWin
= p
->pWin
;
1896 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1898 int iSubCsr
= p
->pSrc
->a
[0].iCursor
;
1899 int nSub
= p
->pSrc
->a
[0].pTab
->nCol
;
1900 int reg
= pParse
->nMem
+1;
1901 int regRecord
= reg
+nSub
;
1902 int regRowid
= regRecord
+1;
1904 ExprList
*pPart
= pMWin
->pPartition
;
1905 ExprList
*pOrderBy
= pMWin
->pOrderBy
;
1907 assert( pMWin
->eType
==TK_RANGE
1908 || (pMWin
->eStart
==TK_UNBOUNDED
&& pMWin
->eEnd
==TK_CURRENT
)
1911 assert( (pMWin
->eStart
==TK_UNBOUNDED
&& pMWin
->eEnd
==TK_CURRENT
)
1912 || (pMWin
->eStart
==TK_UNBOUNDED
&& pMWin
->eEnd
==TK_UNBOUNDED
)
1913 || (pMWin
->eStart
==TK_CURRENT
&& pMWin
->eEnd
==TK_CURRENT
)
1914 || (pMWin
->eStart
==TK_CURRENT
&& pMWin
->eEnd
==TK_UNBOUNDED
&& !pOrderBy
)
1917 if( pMWin
->eEnd
==TK_UNBOUNDED
){
1921 pParse
->nMem
+= nSub
+ 2;
1923 /* Martial the row returned by the sub-select into an array of
1925 for(k
=0; k
<nSub
; k
++){
1926 sqlite3VdbeAddOp3(v
, OP_Column
, iSubCsr
, k
, reg
+k
);
1929 /* Check if this is the start of a new partition or peer group. */
1930 if( pPart
|| pOrderBy
){
1931 int nPart
= (pPart
? pPart
->nExpr
: 0);
1934 int nPeer
= (pOrderBy
? pOrderBy
->nExpr
: 0);
1937 int regNewPart
= reg
+ pMWin
->nBufferCol
;
1938 KeyInfo
*pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
, pPart
, 0, 0);
1939 addr
= sqlite3VdbeAddOp3(v
, OP_Compare
, regNewPart
, pMWin
->regPart
,nPart
);
1940 sqlite3VdbeAppendP4(v
, (void*)pKeyInfo
, P4_KEYINFO
);
1941 addrJump
= sqlite3VdbeAddOp3(v
, OP_Jump
, addr
+2, 0, addr
+2);
1943 windowAggFinal(pParse
, pMWin
, 1);
1945 addrGoto
= sqlite3VdbeAddOp0(v
, OP_Goto
);
1950 int regNewPeer
= reg
+ pMWin
->nBufferCol
+ nPart
;
1951 int regPeer
= pMWin
->regPart
+ nPart
;
1953 if( addrJump
) sqlite3VdbeJumpHere(v
, addrJump
);
1954 if( pMWin
->eType
==TK_RANGE
){
1955 KeyInfo
*pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
, pOrderBy
, 0, 0);
1956 addr
= sqlite3VdbeAddOp3(v
, OP_Compare
, regNewPeer
, regPeer
, nPeer
);
1957 sqlite3VdbeAppendP4(v
, (void*)pKeyInfo
, P4_KEYINFO
);
1958 addrJump
= sqlite3VdbeAddOp3(v
, OP_Jump
, addr
+2, 0, addr
+2);
1963 windowAggFinal(pParse
, pMWin
, pMWin
->eStart
==TK_CURRENT
);
1964 if( addrGoto
) sqlite3VdbeJumpHere(v
, addrGoto
);
1967 sqlite3VdbeAddOp2(v
, OP_Rewind
, pMWin
->iEphCsr
,sqlite3VdbeCurrentAddr(v
)+3);
1969 sqlite3VdbeAddOp2(v
, OP_Gosub
, regGosub
, addrGosub
);
1970 sqlite3VdbeAddOp2(v
, OP_Next
, pMWin
->iEphCsr
, sqlite3VdbeCurrentAddr(v
)-1);
1973 sqlite3VdbeAddOp1(v
, OP_ResetSorter
, pMWin
->iEphCsr
);
1975 v
, OP_Copy
, reg
+pMWin
->nBufferCol
, pMWin
->regPart
, nPart
+nPeer
-1
1978 if( addrJump
) sqlite3VdbeJumpHere(v
, addrJump
);
1981 /* Invoke step function for window functions */
1982 windowAggStep(pParse
, pMWin
, -1, 0, reg
, 0);
1984 /* Buffer the current row in the ephemeral table. */
1985 if( pMWin
->nBufferCol
>0 ){
1986 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, reg
, pMWin
->nBufferCol
, regRecord
);
1988 sqlite3VdbeAddOp2(v
, OP_Blob
, 0, regRecord
);
1989 sqlite3VdbeAppendP4(v
, (void*)"", 0);
1991 sqlite3VdbeAddOp2(v
, OP_NewRowid
, pMWin
->iEphCsr
, regRowid
);
1992 sqlite3VdbeAddOp3(v
, OP_Insert
, pMWin
->iEphCsr
, regRecord
, regRowid
);
1994 /* End the database scan loop. */
1995 sqlite3WhereEnd(pWInfo
);
1997 windowAggFinal(pParse
, pMWin
, 1);
1998 sqlite3VdbeAddOp2(v
, OP_Rewind
, pMWin
->iEphCsr
,sqlite3VdbeCurrentAddr(v
)+3);
2000 sqlite3VdbeAddOp2(v
, OP_Gosub
, regGosub
, addrGosub
);
2001 sqlite3VdbeAddOp2(v
, OP_Next
, pMWin
->iEphCsr
, sqlite3VdbeCurrentAddr(v
)-1);
2006 ** Allocate and return a duplicate of the Window object indicated by the
2007 ** third argument. Set the Window.pOwner field of the new object to
2010 Window
*sqlite3WindowDup(sqlite3
*db
, Expr
*pOwner
, Window
*p
){
2013 pNew
= sqlite3DbMallocZero(db
, sizeof(Window
));
2015 pNew
->zName
= sqlite3DbStrDup(db
, p
->zName
);
2016 pNew
->pFilter
= sqlite3ExprDup(db
, p
->pFilter
, 0);
2017 pNew
->pPartition
= sqlite3ExprListDup(db
, p
->pPartition
, 0);
2018 pNew
->pOrderBy
= sqlite3ExprListDup(db
, p
->pOrderBy
, 0);
2019 pNew
->eType
= p
->eType
;
2020 pNew
->eEnd
= p
->eEnd
;
2021 pNew
->eStart
= p
->eStart
;
2022 pNew
->pStart
= sqlite3ExprDup(db
, p
->pStart
, 0);
2023 pNew
->pEnd
= sqlite3ExprDup(db
, p
->pEnd
, 0);
2024 pNew
->pOwner
= pOwner
;
2031 ** Return a copy of the linked list of Window objects passed as the
2034 Window
*sqlite3WindowListDup(sqlite3
*db
, Window
*p
){
2037 Window
**pp
= &pRet
;
2039 for(pWin
=p
; pWin
; pWin
=pWin
->pNextWin
){
2040 *pp
= sqlite3WindowDup(db
, 0, pWin
);
2042 pp
= &((*pp
)->pNextWin
);
2049 ** sqlite3WhereBegin() has already been called for the SELECT statement
2050 ** passed as the second argument when this function is invoked. It generates
2051 ** code to populate the Window.regResult register for each window function and
2052 ** invoke the sub-routine at instruction addrGosub once for each row.
2053 ** This function calls sqlite3WhereEnd() before returning.
2055 void sqlite3WindowCodeStep(
2056 Parse
*pParse
, /* Parse context */
2057 Select
*p
, /* Rewritten SELECT statement */
2058 WhereInfo
*pWInfo
, /* Context returned by sqlite3WhereBegin() */
2059 int regGosub
, /* Register for OP_Gosub */
2060 int addrGosub
/* OP_Gosub here to return each row */
2062 Window
*pMWin
= p
->pWin
;
2064 /* There are three different functions that may be used to do the work
2065 ** of this one, depending on the window frame and the specific built-in
2066 ** window functions used (if any).
2068 ** windowCodeRowExprStep() handles all "ROWS" window frames, except for:
2070 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
2072 ** The exception is because windowCodeRowExprStep() implements all window
2073 ** frame types by caching the entire partition in a temp table, and
2074 ** "ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW" is easy enough to
2075 ** implement without such a cache.
2077 ** windowCodeCacheStep() is used for:
2079 ** RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
2081 ** It is also used for anything not handled by windowCodeRowExprStep()
2082 ** that invokes a built-in window function that requires the entire
2083 ** partition to be cached in a temp table before any rows are returned
2084 ** (e.g. nth_value() or percent_rank()).
2086 ** Finally, assuming there is no built-in window function that requires
2087 ** the partition to be cached, windowCodeDefaultStep() is used for:
2089 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
2090 ** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
2091 ** RANGE BETWEEN CURRENT ROW AND CURRENT ROW
2092 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
2094 ** windowCodeDefaultStep() is the only one of the three functions that
2095 ** does not cache each partition in a temp table before beginning to
2098 if( pMWin
->eType
==TK_ROWS
2099 && (pMWin
->eStart
!=TK_UNBOUNDED
||pMWin
->eEnd
!=TK_CURRENT
||!pMWin
->pOrderBy
)
2101 windowCodeRowExprStep(pParse
, p
, pWInfo
, regGosub
, addrGosub
);
2104 int bCache
= 0; /* True to use CacheStep() */
2106 if( pMWin
->eStart
==TK_CURRENT
&& pMWin
->eEnd
==TK_UNBOUNDED
){
2109 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
2110 FuncDef
*pFunc
= pWin
->pFunc
;
2111 if( (pFunc
->funcFlags
& SQLITE_FUNC_WINDOW_SIZE
)
2112 || (pFunc
->xSFunc
==nth_valueStepFunc
)
2113 || (pFunc
->xSFunc
==first_valueStepFunc
)
2114 || (pFunc
->xSFunc
==leadStepFunc
)
2115 || (pFunc
->xSFunc
==lagStepFunc
)
2123 /* Otherwise, call windowCodeDefaultStep(). */
2125 windowCodeCacheStep(pParse
, p
, pWInfo
, regGosub
, addrGosub
);
2127 windowCodeDefaultStep(pParse
, p
, pWInfo
, regGosub
, addrGosub
);
2132 #endif /* SQLITE_OMIT_WINDOWFUNC */