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"
18 ** Any SELECT statement that contains one or more window functions in
19 ** either the select list or ORDER BY clause (the only two places window
20 ** functions may be used) is transformed by function sqlite3WindowRewrite()
21 ** in order to support window function processing. For example, with the
24 ** CREATE TABLE t1(a, b, c, d, e, f, g);
28 ** SELECT a+1, max(b) OVER (PARTITION BY c ORDER BY d) FROM t1 ORDER BY e;
32 ** SELECT a+1, max(b) OVER (PARTITION BY c ORDER BY d) FROM (
33 ** SELECT a, e, c, d, b FROM t1 ORDER BY c, d
36 ** The flattening optimization is disabled when processing this transformed
37 ** SELECT statement. This allows the implementation of the window function
38 ** (in this case max()) to process rows sorted in order of (c, d), which
39 ** makes things easier for obvious reasons. More generally:
41 ** * FROM, WHERE, GROUP BY and HAVING clauses are all moved to
44 ** * ORDER BY, LIMIT and OFFSET remain part of the parent query.
46 ** * Terminals from each of the expression trees that make up the
47 ** select-list and ORDER BY expressions in the parent query are
48 ** selected by the sub-query. For the purposes of the transformation,
49 ** terminals are column references and aggregate functions.
51 ** If there is more than one window function in the SELECT that uses
52 ** the same window declaration (the OVER bit), then a single scan may
53 ** be used to process more than one window function. For example:
55 ** SELECT max(b) OVER (PARTITION BY c ORDER BY d),
56 ** min(e) OVER (PARTITION BY c ORDER BY d)
59 ** is transformed in the same way as the example above. However:
61 ** SELECT max(b) OVER (PARTITION BY c ORDER BY d),
62 ** min(e) OVER (PARTITION BY a ORDER BY b)
65 ** Must be transformed to:
67 ** SELECT max(b) OVER (PARTITION BY c ORDER BY d) FROM (
68 ** SELECT e, min(e) OVER (PARTITION BY a ORDER BY b), c, d, b FROM
69 ** SELECT a, e, c, d, b FROM t1 ORDER BY a, b
73 ** so that both min() and max() may process rows in the order defined by
74 ** their respective window declarations.
76 ** INTERFACE WITH SELECT.C
78 ** When processing the rewritten SELECT statement, code in select.c calls
79 ** sqlite3WhereBegin() to begin iterating through the results of the
80 ** sub-query, which is always implemented as a co-routine. It then calls
81 ** sqlite3WindowCodeStep() to process rows and finish the scan by calling
84 ** sqlite3WindowCodeStep() generates VM code so that, for each row returned
85 ** by the sub-query a sub-routine (OP_Gosub) coded by select.c is invoked.
86 ** When the sub-routine is invoked:
88 ** * The results of all window-functions for the row are stored
89 ** in the associated Window.regResult registers.
91 ** * The required terminal values are stored in the current row of
92 ** temp table Window.iEphCsr.
94 ** In some cases, depending on the window frame and the specific window
95 ** functions invoked, sqlite3WindowCodeStep() caches each entire partition
96 ** in a temp table before returning any rows. In other cases it does not.
97 ** This detail is encapsulated within this file, the code generated by
98 ** select.c is the same in either case.
100 ** BUILT-IN WINDOW FUNCTIONS
102 ** This implementation features the following built-in window functions:
110 ** lead(expr [, offset [, default]])
111 ** lag(expr [, offset [, default]])
114 ** nth_value(expr, N)
116 ** These are the same built-in window functions supported by Postgres.
117 ** Although the behaviour of aggregate window functions (functions that
118 ** can be used as either aggregates or window funtions) allows them to
119 ** be implemented using an API, built-in window functions are much more
120 ** esoteric. Additionally, some window functions (e.g. nth_value())
121 ** may only be implemented by caching the entire partition in memory.
122 ** As such, some built-in window functions use the same API as aggregate
123 ** window functions and some are implemented directly using VDBE
124 ** instructions. Additionally, for those functions that use the API, the
125 ** window frame is sometimes modified before the SELECT statement is
126 ** rewritten. For example, regardless of the specified window frame, the
127 ** row_number() function always uses:
129 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
131 ** See sqlite3WindowUpdate() for details.
133 ** As well as some of the built-in window functions, aggregate window
134 ** functions min() and max() are implemented using VDBE instructions if
135 ** the start of the window frame is declared as anything other than
136 ** UNBOUNDED PRECEDING.
140 ** Implementation of built-in window function row_number(). Assumes that the
141 ** window frame has been coerced to:
143 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
145 static void row_numberStepFunc(
146 sqlite3_context
*pCtx
,
148 sqlite3_value
**apArg
150 i64
*p
= (i64
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
153 static void row_numberInvFunc(
154 sqlite3_context
*pCtx
,
156 sqlite3_value
**apArg
159 static void row_numberValueFunc(sqlite3_context
*pCtx
){
160 i64
*p
= (i64
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
161 sqlite3_result_int64(pCtx
, (p
? *p
: 0));
165 ** Context object type used by rank(), dense_rank(), percent_rank() and
175 ** Implementation of built-in window function dense_rank(). Assumes that
176 ** the window frame has been set to:
178 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
180 static void dense_rankStepFunc(
181 sqlite3_context
*pCtx
,
183 sqlite3_value
**apArg
186 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
187 if( p
) p
->nStep
= 1;
189 static void dense_rankInvFunc(
190 sqlite3_context
*pCtx
,
192 sqlite3_value
**apArg
195 static void dense_rankValueFunc(sqlite3_context
*pCtx
){
197 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
203 sqlite3_result_int64(pCtx
, p
->nValue
);
208 ** Implementation of built-in window function rank(). Assumes that
209 ** the window frame has been set to:
211 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
213 static void rankStepFunc(
214 sqlite3_context
*pCtx
,
216 sqlite3_value
**apArg
219 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
223 p
->nValue
= p
->nStep
;
227 static void rankInvFunc(
228 sqlite3_context
*pCtx
,
230 sqlite3_value
**apArg
233 static void rankValueFunc(sqlite3_context
*pCtx
){
235 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
237 sqlite3_result_int64(pCtx
, p
->nValue
);
243 ** Implementation of built-in window function percent_rank(). Assumes that
244 ** the window frame has been set to:
246 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
248 static void percent_rankStepFunc(
249 sqlite3_context
*pCtx
,
251 sqlite3_value
**apArg
256 assert( sqlite3VdbeAssertAggContext(pCtx
) );
257 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
260 p
->nTotal
= sqlite3_value_int64(apArg
[0]);
264 p
->nValue
= p
->nStep
;
268 static void percent_rankInvFunc(
269 sqlite3_context
*pCtx
,
271 sqlite3_value
**apArg
274 static void percent_rankValueFunc(sqlite3_context
*pCtx
){
276 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
279 double r
= (double)(p
->nValue
-1) / (double)(p
->nTotal
-1);
280 sqlite3_result_double(pCtx
, r
);
282 sqlite3_result_double(pCtx
, 100.0);
289 ** Implementation of built-in window function cume_dist(). Assumes that
290 ** the window frame has been set to:
292 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
294 static void cume_distStepFunc(
295 sqlite3_context
*pCtx
,
297 sqlite3_value
**apArg
302 assert( sqlite3VdbeAssertAggContext(pCtx
) );
303 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
306 p
->nTotal
= sqlite3_value_int64(apArg
[0]);
311 static void cume_distInvFunc(
312 sqlite3_context
*pCtx
,
314 sqlite3_value
**apArg
317 static void cume_distValueFunc(sqlite3_context
*pCtx
){
319 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
320 if( p
&& p
->nTotal
){
321 double r
= (double)(p
->nStep
) / (double)(p
->nTotal
);
322 sqlite3_result_double(pCtx
, r
);
327 ** Context object for ntile() window function.
330 i64 nTotal
; /* Total rows in partition */
331 i64 nParam
; /* Parameter passed to ntile(N) */
332 i64 iRow
; /* Current row */
336 ** Implementation of ntile(). This assumes that the window frame has
339 ** ROWS UNBOUNDED PRECEDING AND CURRENT ROW
341 static void ntileStepFunc(
342 sqlite3_context
*pCtx
,
344 sqlite3_value
**apArg
348 assert( sqlite3VdbeAssertAggContext(pCtx
) );
349 p
= (struct NtileCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
352 p
->nParam
= sqlite3_value_int64(apArg
[0]);
353 p
->nTotal
= sqlite3_value_int64(apArg
[1]);
355 sqlite3_result_error(
356 pCtx
, "argument of ntile must be a positive integer", -1
363 static void ntileInvFunc(
364 sqlite3_context
*pCtx
,
366 sqlite3_value
**apArg
369 static void ntileValueFunc(sqlite3_context
*pCtx
){
371 p
= (struct NtileCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
372 if( p
&& p
->nParam
>0 ){
373 int nSize
= (p
->nTotal
/ p
->nParam
);
375 sqlite3_result_int64(pCtx
, p
->iRow
);
377 i64 nLarge
= p
->nTotal
- p
->nParam
*nSize
;
378 i64 iSmall
= nLarge
*(nSize
+1);
379 i64 iRow
= p
->iRow
-1;
381 assert( (nLarge
*(nSize
+1) + (p
->nParam
-nLarge
)*nSize
)==p
->nTotal
);
384 sqlite3_result_int64(pCtx
, 1 + iRow
/(nSize
+1));
386 sqlite3_result_int64(pCtx
, 1 + nLarge
+ (iRow
-iSmall
)/nSize
);
393 ** Context object for last_value() window function.
395 struct LastValueCtx
{
401 ** Implementation of last_value().
403 static void last_valueStepFunc(
404 sqlite3_context
*pCtx
,
406 sqlite3_value
**apArg
408 struct LastValueCtx
*p
;
409 p
= (struct LastValueCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
411 sqlite3_value_free(p
->pVal
);
412 p
->pVal
= sqlite3_value_dup(apArg
[0]);
414 sqlite3_result_error_nomem(pCtx
);
420 static void last_valueInvFunc(
421 sqlite3_context
*pCtx
,
423 sqlite3_value
**apArg
425 struct LastValueCtx
*p
;
426 p
= (struct LastValueCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
430 sqlite3_value_free(p
->pVal
);
435 static void last_valueValueFunc(sqlite3_context
*pCtx
){
436 struct LastValueCtx
*p
;
437 p
= (struct LastValueCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
439 sqlite3_result_value(pCtx
, p
->pVal
);
442 static void last_valueFinalizeFunc(sqlite3_context
*pCtx
){
443 struct LastValueCtx
*p
;
444 p
= (struct LastValueCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
446 sqlite3_result_value(pCtx
, p
->pVal
);
447 sqlite3_value_free(p
->pVal
);
453 ** No-op implementations of nth_value(), first_value(), lead() and lag().
454 ** These are all implemented inline using VDBE instructions.
456 static void nth_valueStepFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**a
){}
457 static void nth_valueInvFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**ap
){}
458 static void nth_valueValueFunc(sqlite3_context
*pCtx
){}
459 static void first_valueStepFunc(sqlite3_context
*p
, int n
, sqlite3_value
**ap
){}
460 static void first_valueInvFunc(sqlite3_context
*p
, int n
, sqlite3_value
**ap
){}
461 static void first_valueValueFunc(sqlite3_context
*pCtx
){}
462 static void leadStepFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**ap
){}
463 static void leadInvFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**ap
){}
464 static void leadValueFunc(sqlite3_context
*pCtx
){}
465 static void lagStepFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**ap
){}
466 static void lagInvFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**ap
){}
467 static void lagValueFunc(sqlite3_context
*pCtx
){}
469 #define WINDOWFUNC(name,nArg,extra) { \
470 nArg, (SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0, \
471 name ## StepFunc, name ## ValueFunc, name ## ValueFunc, \
472 name ## InvFunc, #name \
475 #define WINDOWFUNCF(name,nArg,extra) { \
476 nArg, (SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0, \
477 name ## StepFunc, name ## FinalizeFunc, name ## ValueFunc, \
478 name ## InvFunc, #name \
482 ** Register those built-in window functions that are not also aggregates.
484 void sqlite3WindowFunctions(void){
485 static FuncDef aWindowFuncs
[] = {
486 WINDOWFUNC(row_number
, 0, 0),
487 WINDOWFUNC(dense_rank
, 0, 0),
488 WINDOWFUNC(rank
, 0, 0),
489 WINDOWFUNC(percent_rank
, 0, SQLITE_FUNC_WINDOW_SIZE
),
490 WINDOWFUNC(cume_dist
, 0, SQLITE_FUNC_WINDOW_SIZE
),
491 WINDOWFUNC(ntile
, 1, SQLITE_FUNC_WINDOW_SIZE
),
492 WINDOWFUNCF(last_value
, 1, 0),
493 WINDOWFUNC(nth_value
, 2, 0),
494 WINDOWFUNC(first_value
, 1, 0),
495 WINDOWFUNC(lead
, 1, 0), WINDOWFUNC(lead
, 2, 0), WINDOWFUNC(lead
, 3, 0),
496 WINDOWFUNC(lag
, 1, 0), WINDOWFUNC(lag
, 2, 0), WINDOWFUNC(lag
, 3, 0),
498 sqlite3InsertBuiltinFuncs(aWindowFuncs
, ArraySize(aWindowFuncs
));
502 ** This function is called immediately after resolving the function name
503 ** for a window function within a SELECT statement. Argument pList is a
504 ** linked list of WINDOW definitions for the current SELECT statement.
505 ** Argument pFunc is the function definition just resolved and pWin
506 ** is the Window object representing the associated OVER clause. This
507 ** function updates the contents of pWin as follows:
509 ** * If the OVER clause refered to a named window (as in "max(x) OVER win"),
510 ** search list pList for a matching WINDOW definition, and update pWin
511 ** accordingly. If no such WINDOW clause can be found, leave an error
514 ** * If the function is a built-in window function that requires the
515 ** window to be coerced (see "BUILT-IN WINDOW FUNCTIONS" at the top
516 ** of this file), pWin is updated here.
518 void sqlite3WindowUpdate(
520 Window
*pList
, /* List of named windows for this SELECT */
521 Window
*pWin
, /* Window frame to update */
522 FuncDef
*pFunc
/* Window function definition */
524 if( pWin
->zName
&& pWin
->eType
==0 ){
526 for(p
=pList
; p
; p
=p
->pNextWin
){
527 if( sqlite3StrICmp(p
->zName
, pWin
->zName
)==0 ) break;
530 sqlite3ErrorMsg(pParse
, "no such window: %s", pWin
->zName
);
533 pWin
->pPartition
= sqlite3ExprListDup(pParse
->db
, p
->pPartition
, 0);
534 pWin
->pOrderBy
= sqlite3ExprListDup(pParse
->db
, p
->pOrderBy
, 0);
535 pWin
->pStart
= sqlite3ExprDup(pParse
->db
, p
->pStart
, 0);
536 pWin
->pEnd
= sqlite3ExprDup(pParse
->db
, p
->pEnd
, 0);
537 pWin
->eStart
= p
->eStart
;
538 pWin
->eEnd
= p
->eEnd
;
539 pWin
->eType
= p
->eType
;
541 if( pFunc
->funcFlags
& SQLITE_FUNC_WINDOW
){
542 sqlite3
*db
= pParse
->db
;
544 sqlite3ErrorMsg(pParse
,
545 "FILTER clause may only be used with aggregate window functions"
548 if( pFunc
->xSFunc
==row_numberStepFunc
|| pFunc
->xSFunc
==ntileStepFunc
){
549 sqlite3ExprDelete(db
, pWin
->pStart
);
550 sqlite3ExprDelete(db
, pWin
->pEnd
);
551 pWin
->pStart
= pWin
->pEnd
= 0;
552 pWin
->eType
= TK_ROWS
;
553 pWin
->eStart
= TK_UNBOUNDED
;
554 pWin
->eEnd
= TK_CURRENT
;
557 if( pFunc
->xSFunc
==dense_rankStepFunc
|| pFunc
->xSFunc
==rankStepFunc
558 || pFunc
->xSFunc
==percent_rankStepFunc
|| pFunc
->xSFunc
==cume_distStepFunc
560 sqlite3ExprDelete(db
, pWin
->pStart
);
561 sqlite3ExprDelete(db
, pWin
->pEnd
);
562 pWin
->pStart
= pWin
->pEnd
= 0;
563 pWin
->eType
= TK_RANGE
;
564 pWin
->eStart
= TK_UNBOUNDED
;
565 pWin
->eEnd
= TK_CURRENT
;
572 ** Context object passed through sqlite3WalkExprList() to
573 ** selectWindowRewriteExprCb() by selectWindowRewriteEList().
575 typedef struct WindowRewrite WindowRewrite
;
576 struct WindowRewrite
{
582 ** Callback function used by selectWindowRewriteEList(). If necessary,
583 ** this function appends to the output expression-list and updates
584 ** expression (*ppExpr) in place.
586 static int selectWindowRewriteExprCb(Walker
*pWalker
, Expr
*pExpr
){
587 struct WindowRewrite
*p
= pWalker
->u
.pRewrite
;
588 Parse
*pParse
= pWalker
->pParse
;
593 if( pExpr
->pWin
==0 ){
597 for(pWin
=p
->pWin
; pWin
; pWin
=pWin
->pNextWin
){
598 if( pExpr
->pWin
==pWin
){
599 assert( pWin
->pOwner
==pExpr
);
606 case TK_AGG_FUNCTION
:
608 Expr
*pDup
= sqlite3ExprDup(pParse
->db
, pExpr
, 0);
609 p
->pSub
= sqlite3ExprListAppend(pParse
, p
->pSub
, pDup
);
611 assert( ExprHasProperty(pExpr
, EP_Static
)==0 );
612 ExprSetProperty(pExpr
, EP_Static
);
613 sqlite3ExprDelete(pParse
->db
, pExpr
);
614 ExprClearProperty(pExpr
, EP_Static
);
615 memset(pExpr
, 0, sizeof(Expr
));
617 pExpr
->op
= TK_COLUMN
;
618 pExpr
->iColumn
= p
->pSub
->nExpr
-1;
619 pExpr
->iTable
= p
->pWin
->iEphCsr
;
631 static int selectWindowRewriteSelectCb(Walker
*pWalker
, Select
*pSelect
){
637 ** Iterate through each expression in expression-list pEList. For each:
640 ** * aggregate function, or
641 ** * window function with a Window object that is not a member of the
642 ** linked list passed as the second argument (pWin)
644 ** Append the node to output expression-list (*ppSub). And replace it
645 ** with a TK_COLUMN that reads the (N-1)th element of table
646 ** pWin->iEphCsr, where N is the number of elements in (*ppSub) after
647 ** appending the new one.
649 static void selectWindowRewriteEList(
652 ExprList
*pEList
, /* Rewrite expressions in this list */
653 ExprList
**ppSub
/* IN/OUT: Sub-select expression-list */
656 WindowRewrite sRewrite
;
658 memset(&sWalker
, 0, sizeof(Walker
));
659 memset(&sRewrite
, 0, sizeof(WindowRewrite
));
661 sRewrite
.pSub
= *ppSub
;
662 sRewrite
.pWin
= pWin
;
664 sWalker
.pParse
= pParse
;
665 sWalker
.xExprCallback
= selectWindowRewriteExprCb
;
666 sWalker
.xSelectCallback
= selectWindowRewriteSelectCb
;
667 sWalker
.u
.pRewrite
= &sRewrite
;
669 (void)sqlite3WalkExprList(&sWalker
, pEList
);
671 *ppSub
= sRewrite
.pSub
;
675 ** Append a copy of each expression in expression-list pAppend to
676 ** expression list pList. Return a pointer to the result list.
678 static ExprList
*exprListAppendList(
679 Parse
*pParse
, /* Parsing context */
680 ExprList
*pList
, /* List to which to append. Might be NULL */
681 ExprList
*pAppend
/* List of values to append. Might be NULL */
685 int nInit
= pList
? pList
->nExpr
: 0;
686 for(i
=0; i
<pAppend
->nExpr
; i
++){
687 Expr
*pDup
= sqlite3ExprDup(pParse
->db
, pAppend
->a
[i
].pExpr
, 0);
688 pList
= sqlite3ExprListAppend(pParse
, pList
, pDup
);
689 if( pList
) pList
->a
[nInit
+i
].sortOrder
= pAppend
->a
[i
].sortOrder
;
696 ** If the SELECT statement passed as the second argument does not invoke
697 ** any SQL window functions, this function is a no-op. Otherwise, it
698 ** rewrites the SELECT statement so that window function xStep functions
699 ** are invoked in the correct order as described under "SELECT REWRITING"
700 ** at the top of this file.
702 int sqlite3WindowRewrite(Parse
*pParse
, Select
*p
){
705 Vdbe
*v
= sqlite3GetVdbe(pParse
);
706 sqlite3
*db
= pParse
->db
;
707 Select
*pSub
= 0; /* The subquery */
708 SrcList
*pSrc
= p
->pSrc
;
709 Expr
*pWhere
= p
->pWhere
;
710 ExprList
*pGroupBy
= p
->pGroupBy
;
711 Expr
*pHaving
= p
->pHaving
;
714 ExprList
*pSublist
= 0; /* Expression list for sub-query */
715 Window
*pMWin
= p
->pWin
; /* Master window object */
716 Window
*pWin
; /* Window object iterator */
723 /* Assign a cursor number for the ephemeral table used to buffer rows.
724 ** The OpenEphemeral instruction is coded later, after it is known how
725 ** many columns the table will have. */
726 pMWin
->iEphCsr
= pParse
->nTab
++;
728 selectWindowRewriteEList(pParse
, pMWin
, p
->pEList
, &pSublist
);
729 selectWindowRewriteEList(pParse
, pMWin
, p
->pOrderBy
, &pSublist
);
730 pMWin
->nBufferCol
= (pSublist
? pSublist
->nExpr
: 0);
732 /* Create the ORDER BY clause for the sub-select. This is the concatenation
733 ** of the window PARTITION and ORDER BY clauses. Append the same
734 ** expressions to the sub-select expression list. They are required to
735 ** figure out where boundaries for partitions and sets of peer rows. */
736 pSort
= sqlite3ExprListDup(db
, pMWin
->pPartition
, 0);
737 if( pMWin
->pOrderBy
){
738 pSort
= exprListAppendList(pParse
, pSort
, pMWin
->pOrderBy
);
740 pSublist
= exprListAppendList(pParse
, pSublist
, pSort
);
742 /* Append the arguments passed to each window function to the
743 ** sub-select expression list. Also allocate two registers for each
744 ** window function - one for the accumulator, another for interim
746 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
747 pWin
->iArgCol
= (pSublist
? pSublist
->nExpr
: 0);
748 pSublist
= exprListAppendList(pParse
, pSublist
, pWin
->pOwner
->x
.pList
);
750 Expr
*pFilter
= sqlite3ExprDup(db
, pWin
->pFilter
, 0);
751 pSublist
= sqlite3ExprListAppend(pParse
, pSublist
, pFilter
);
753 pWin
->regAccum
= ++pParse
->nMem
;
754 pWin
->regResult
= ++pParse
->nMem
;
755 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regAccum
);
758 /* If there is no ORDER BY or PARTITION BY clause, and the window
759 ** function accepts zero arguments, and there are no other columns
760 ** selected (e.g. "SELECT row_number() OVER () FROM t1"), it is possible
761 ** that pSublist is still NULL here. Add a constant expression here to
762 ** keep everything legal in this case.
765 pSublist
= sqlite3ExprListAppend(pParse
, 0,
766 sqlite3ExprAlloc(db
, TK_INTEGER
, &sqlite3IntTokens
[0], 0)
770 pSub
= sqlite3SelectNew(
771 pParse
, pSublist
, pSrc
, pWhere
, pGroupBy
, pHaving
, pSort
, 0, 0
773 p
->pSrc
= sqlite3SrcListAppend(db
, 0, 0, 0);
774 assert( p
->pSrc
|| db
->mallocFailed
);
776 p
->pSrc
->a
[0].pSelect
= pSub
;
777 sqlite3SrcListAssignCursors(pParse
, p
->pSrc
);
778 if( sqlite3ExpandSubquery(pParse
, &p
->pSrc
->a
[0]) ){
781 pSub
->selFlags
|= SF_Expanded
;
782 p
->selFlags
&= ~SF_Aggregate
;
783 sqlite3SelectPrep(pParse
, pSub
, 0);
786 sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, pMWin
->iEphCsr
, pSublist
->nExpr
);
788 sqlite3SelectDelete(db
, pSub
);
790 if( db
->mallocFailed
) rc
= SQLITE_NOMEM
;
797 ** Free the Window object passed as the second argument.
799 void sqlite3WindowDelete(sqlite3
*db
, Window
*p
){
801 sqlite3ExprDelete(db
, p
->pFilter
);
802 sqlite3ExprListDelete(db
, p
->pPartition
);
803 sqlite3ExprListDelete(db
, p
->pOrderBy
);
804 sqlite3ExprDelete(db
, p
->pEnd
);
805 sqlite3ExprDelete(db
, p
->pStart
);
806 sqlite3DbFree(db
, p
->zName
);
807 sqlite3DbFree(db
, p
);
812 ** Free the linked list of Window objects starting at the second argument.
814 void sqlite3WindowListDelete(sqlite3
*db
, Window
*p
){
816 Window
*pNext
= p
->pNextWin
;
817 sqlite3WindowDelete(db
, p
);
823 ** Allocate and return a new Window object.
825 Window
*sqlite3WindowAlloc(
828 int eStart
, Expr
*pStart
,
831 Window
*pWin
= (Window
*)sqlite3DbMallocZero(pParse
->db
, sizeof(Window
));
836 pWin
->eStart
= eStart
;
839 pWin
->pStart
= pStart
;
841 sqlite3ExprDelete(pParse
->db
, pEnd
);
842 sqlite3ExprDelete(pParse
->db
, pStart
);
849 ** Attach window object pWin to expression p.
851 void sqlite3WindowAttach(Parse
*pParse
, Expr
*p
, Window
*pWin
){
854 if( pWin
) pWin
->pOwner
= p
;
856 sqlite3WindowDelete(pParse
->db
, pWin
);
861 ** Return 0 if the two window objects are identical, or non-zero otherwise.
862 ** Identical window objects can be processed in a single scan.
864 int sqlite3WindowCompare(Parse
*pParse
, Window
*p1
, Window
*p2
){
865 if( p1
->eType
!=p2
->eType
) return 1;
866 if( p1
->eStart
!=p2
->eStart
) return 1;
867 if( p1
->eEnd
!=p2
->eEnd
) return 1;
868 if( sqlite3ExprCompare(pParse
, p1
->pStart
, p2
->pStart
, -1) ) return 1;
869 if( sqlite3ExprCompare(pParse
, p1
->pEnd
, p2
->pEnd
, -1) ) return 1;
870 if( sqlite3ExprListCompare(p1
->pPartition
, p2
->pPartition
, -1) ) return 1;
871 if( sqlite3ExprListCompare(p1
->pOrderBy
, p2
->pOrderBy
, -1) ) return 1;
877 ** This is called by code in select.c before it calls sqlite3WhereBegin()
878 ** to begin iterating through the sub-query results. It is used to allocate
879 ** and initialize registers and cursors used by sqlite3WindowCodeStep().
881 void sqlite3WindowCodeInit(Parse
*pParse
, Window
*pMWin
){
883 Vdbe
*v
= sqlite3GetVdbe(pParse
);
884 int nPart
= (pMWin
->pPartition
? pMWin
->pPartition
->nExpr
: 0);
885 nPart
+= (pMWin
->pOrderBy
? pMWin
->pOrderBy
->nExpr
: 0);
887 pMWin
->regPart
= pParse
->nMem
+1;
888 pParse
->nMem
+= nPart
;
889 sqlite3VdbeAddOp3(v
, OP_Null
, 0, pMWin
->regPart
, pMWin
->regPart
+nPart
-1);
892 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
893 FuncDef
*p
= pWin
->pFunc
;
894 if( (p
->funcFlags
& SQLITE_FUNC_MINMAX
) && pWin
->eStart
!=TK_UNBOUNDED
){
895 /* The inline versions of min() and max() require a single ephemeral
896 ** table and 3 registers. The registers are used as follows:
898 ** regApp+0: slot to copy min()/max() argument to for MakeRecord
899 ** regApp+1: integer value used to ensure keys are unique
900 ** regApp+2: output of MakeRecord
902 ExprList
*pList
= pWin
->pOwner
->x
.pList
;
903 KeyInfo
*pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
, pList
, 0, 0);
904 pWin
->csrApp
= pParse
->nTab
++;
905 pWin
->regApp
= pParse
->nMem
+1;
907 if( pKeyInfo
&& pWin
->pFunc
->zName
[1]=='i' ){
908 assert( pKeyInfo
->aSortOrder
[0]==0 );
909 pKeyInfo
->aSortOrder
[0] = 1;
911 sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, pWin
->csrApp
, 2);
912 sqlite3VdbeAppendP4(v
, pKeyInfo
, P4_KEYINFO
);
913 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, pWin
->regApp
+1);
915 else if( p
->xSFunc
==nth_valueStepFunc
|| p
->xSFunc
==first_valueStepFunc
){
916 /* Allocate two registers at pWin->regApp. These will be used to
917 ** store the start and end index of the current frame. */
918 assert( pMWin
->iEphCsr
);
919 pWin
->regApp
= pParse
->nMem
+1;
920 pWin
->csrApp
= pParse
->nTab
++;
922 sqlite3VdbeAddOp2(v
, OP_OpenDup
, pWin
->csrApp
, pMWin
->iEphCsr
);
924 else if( p
->xSFunc
==leadStepFunc
|| p
->xSFunc
==lagStepFunc
){
925 assert( pMWin
->iEphCsr
);
926 pWin
->csrApp
= pParse
->nTab
++;
927 sqlite3VdbeAddOp2(v
, OP_OpenDup
, pWin
->csrApp
, pMWin
->iEphCsr
);
933 ** A "PRECEDING <expr>" (bEnd==0) or "FOLLOWING <expr>" (bEnd==1) has just
934 ** been evaluated and the result left in register reg. This function generates
935 ** VM code to check that the value is a non-negative integer and throws
936 ** an exception if it is not.
938 static void windowCheckFrameValue(Parse
*pParse
, int reg
, int bEnd
){
939 static const char *azErr
[] = {
940 "frame starting offset must be a non-negative integer",
941 "frame ending offset must be a non-negative integer"
943 Vdbe
*v
= sqlite3GetVdbe(pParse
);
944 int regZero
= sqlite3GetTempReg(pParse
);
945 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, regZero
);
946 sqlite3VdbeAddOp2(v
, OP_MustBeInt
, reg
, sqlite3VdbeCurrentAddr(v
)+2);
947 sqlite3VdbeAddOp3(v
, OP_Ge
, regZero
, sqlite3VdbeCurrentAddr(v
)+2, reg
);
948 sqlite3VdbeAddOp2(v
, OP_Halt
, SQLITE_ERROR
, OE_Abort
);
949 sqlite3VdbeAppendP4(v
, (void*)azErr
[bEnd
], P4_STATIC
);
950 sqlite3ReleaseTempReg(pParse
, regZero
);
954 ** Return the number of arguments passed to the window-function associated
955 ** with the object passed as the only argument to this function.
957 static int windowArgCount(Window
*pWin
){
958 ExprList
*pList
= pWin
->pOwner
->x
.pList
;
959 return (pList
? pList
->nExpr
: 0);
963 ** Generate VM code to invoke either xStep() (if bInverse is 0) or
964 ** xInverse (if bInverse is non-zero) for each window function in the
965 ** linked list starting at pMWin. Or, for built-in window functions
966 ** that do not use the standard function API, generate the required
969 ** If argument csr is greater than or equal to 0, then argument reg is
970 ** the first register in an array of registers guaranteed to be large
971 ** enough to hold the array of arguments for each function. In this case
972 ** the arguments are extracted from the current row of csr into the
973 ** array of registers before invoking OP_AggStep.
975 ** Or, if csr is less than zero, then the array of registers at reg is
976 ** already populated with all columns from the current row of the sub-query.
978 ** If argument regPartSize is non-zero, then it is a register containing the
979 ** number of rows in the current partition.
981 static void windowAggStep(
983 Window
*pMWin
, /* Linked list of window functions */
984 int csr
, /* Read arguments from this cursor */
985 int bInverse
, /* True to invoke xInverse instead of xStep */
986 int reg
, /* Array of registers */
987 int regPartSize
/* Register containing size of partition */
989 Vdbe
*v
= sqlite3GetVdbe(pParse
);
991 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
992 int flags
= pWin
->pFunc
->funcFlags
;
994 int nArg
= windowArgCount(pWin
);
998 for(i
=0; i
<nArg
; i
++){
999 sqlite3VdbeAddOp3(v
, OP_Column
, csr
, pWin
->iArgCol
+i
, reg
+i
);
1002 if( flags
& SQLITE_FUNC_WINDOW_SIZE
){
1004 regArg
= regPartSize
;
1006 sqlite3VdbeAddOp2(v
, OP_SCopy
, regPartSize
, reg
+nArg
);
1011 assert( !(flags
& SQLITE_FUNC_WINDOW_SIZE
) );
1012 regArg
= reg
+ pWin
->iArgCol
;
1015 if( (pWin
->pFunc
->funcFlags
& SQLITE_FUNC_MINMAX
)
1016 && pWin
->eStart
!=TK_UNBOUNDED
1019 sqlite3VdbeAddOp2(v
, OP_AddImm
, pWin
->regApp
+1, 1);
1020 sqlite3VdbeAddOp2(v
, OP_SCopy
, regArg
, pWin
->regApp
);
1021 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, pWin
->regApp
, 2, pWin
->regApp
+2);
1022 sqlite3VdbeAddOp2(v
, OP_IdxInsert
, pWin
->csrApp
, pWin
->regApp
+2);
1024 sqlite3VdbeAddOp4Int(v
, OP_SeekGE
, pWin
->csrApp
, 0, regArg
, 1);
1025 sqlite3VdbeAddOp1(v
, OP_Delete
, pWin
->csrApp
);
1026 sqlite3VdbeJumpHere(v
, sqlite3VdbeCurrentAddr(v
)-2);
1028 }else if( pWin
->regApp
){
1029 assert( pWin
->pFunc
->xSFunc
==nth_valueStepFunc
1030 || pWin
->pFunc
->xSFunc
==first_valueStepFunc
1032 assert( bInverse
==0 || bInverse
==1 );
1033 sqlite3VdbeAddOp2(v
, OP_AddImm
, pWin
->regApp
+1-bInverse
, 1);
1034 }else if( pWin
->pFunc
->xSFunc
==leadStepFunc
1035 || pWin
->pFunc
->xSFunc
==lagStepFunc
1040 if( pWin
->pFilter
){
1042 assert( nArg
==pWin
->pOwner
->x
.pList
->nExpr
);
1044 regTmp
= sqlite3GetTempReg(pParse
);
1045 sqlite3VdbeAddOp3(v
, OP_Column
, csr
, pWin
->iArgCol
+nArg
,regTmp
);
1047 regTmp
= regArg
+ nArg
;
1049 addrIf
= sqlite3VdbeAddOp3(v
, OP_IfNot
, regTmp
, 0, 1);
1051 sqlite3ReleaseTempReg(pParse
, regTmp
);
1054 if( pWin
->pFunc
->funcFlags
& SQLITE_FUNC_NEEDCOLL
){
1056 pColl
= sqlite3ExprNNCollSeq(pParse
, pWin
->pOwner
->x
.pList
->a
[0].pExpr
);
1057 sqlite3VdbeAddOp4(v
, OP_CollSeq
, 0,0,0, (const char*)pColl
, P4_COLLSEQ
);
1059 sqlite3VdbeAddOp3(v
, OP_AggStep0
, bInverse
, regArg
, pWin
->regAccum
);
1060 sqlite3VdbeAppendP4(v
, pWin
->pFunc
, P4_FUNCDEF
);
1061 sqlite3VdbeChangeP5(v
, (u8
)nArg
);
1062 if( addrIf
) sqlite3VdbeJumpHere(v
, addrIf
);
1068 ** Generate VM code to invoke either xValue() (bFinal==0) or xFinalize()
1069 ** (bFinal==1) for each window function in the linked list starting at
1070 ** pMWin. Or, for built-in window-functions that do not use the standard
1071 ** API, generate the equivalent VM code.
1073 static void windowAggFinal(Parse
*pParse
, Window
*pMWin
, int bFinal
){
1074 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1077 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
1078 if( (pWin
->pFunc
->funcFlags
& SQLITE_FUNC_MINMAX
)
1079 && pWin
->eStart
!=TK_UNBOUNDED
1081 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regResult
);
1082 sqlite3VdbeAddOp1(v
, OP_Last
, pWin
->csrApp
);
1083 sqlite3VdbeAddOp3(v
, OP_Column
, pWin
->csrApp
, 0, pWin
->regResult
);
1084 sqlite3VdbeJumpHere(v
, sqlite3VdbeCurrentAddr(v
)-2);
1086 sqlite3VdbeAddOp1(v
, OP_ResetSorter
, pWin
->csrApp
);
1088 }else if( pWin
->regApp
){
1091 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regResult
);
1093 sqlite3VdbeAddOp2(v
, OP_AggFinal
, pWin
->regAccum
, windowArgCount(pWin
));
1094 sqlite3VdbeAppendP4(v
, pWin
->pFunc
, P4_FUNCDEF
);
1096 sqlite3VdbeAddOp2(v
, OP_Copy
, pWin
->regAccum
, pWin
->regResult
);
1097 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regAccum
);
1099 sqlite3VdbeChangeP3(v
, -1, pWin
->regResult
);
1106 ** This function generates VM code to invoke the sub-routine at address
1107 ** lblFlushPart once for each partition with the entire partition cached in
1108 ** the Window.iEphCsr temp table.
1110 static void windowPartitionCache(
1112 Select
*p
, /* The rewritten SELECT statement */
1113 WhereInfo
*pWInfo
, /* WhereInfo to call WhereEnd() on */
1114 int regFlushPart
, /* Register to use with Gosub lblFlushPart */
1115 int lblFlushPart
, /* Subroutine to Gosub to */
1116 int *pRegSize
/* OUT: Register containing partition size */
1118 Window
*pMWin
= p
->pWin
;
1119 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1120 int iSubCsr
= p
->pSrc
->a
[0].iCursor
;
1121 int nSub
= p
->pSrc
->a
[0].pTab
->nCol
;
1124 int reg
= pParse
->nMem
+1;
1125 int regRecord
= reg
+nSub
;
1126 int regRowid
= regRecord
+1;
1128 *pRegSize
= regRowid
;
1129 pParse
->nMem
+= nSub
+ 2;
1131 /* Martial the row returned by the sub-select into an array of
1133 for(k
=0; k
<nSub
; k
++){
1134 sqlite3VdbeAddOp3(v
, OP_Column
, iSubCsr
, k
, reg
+k
);
1136 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, reg
, nSub
, regRecord
);
1138 /* Check if this is the start of a new partition. If so, call the
1139 ** flush_partition sub-routine. */
1140 if( pMWin
->pPartition
){
1142 ExprList
*pPart
= pMWin
->pPartition
;
1143 int nPart
= pPart
->nExpr
;
1144 int regNewPart
= reg
+ pMWin
->nBufferCol
;
1145 KeyInfo
*pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
, pPart
, 0, 0);
1147 addr
= sqlite3VdbeAddOp3(v
, OP_Compare
, regNewPart
, pMWin
->regPart
,nPart
);
1148 sqlite3VdbeAppendP4(v
, (void*)pKeyInfo
, P4_KEYINFO
);
1149 sqlite3VdbeAddOp3(v
, OP_Jump
, addr
+2, addr
+4, addr
+2);
1150 sqlite3VdbeAddOp3(v
, OP_Copy
, regNewPart
, pMWin
->regPart
, nPart
-1);
1151 sqlite3VdbeAddOp2(v
, OP_Gosub
, regFlushPart
, lblFlushPart
);
1154 /* Buffer the current row in the ephemeral table. */
1155 sqlite3VdbeAddOp2(v
, OP_NewRowid
, pMWin
->iEphCsr
, regRowid
);
1156 sqlite3VdbeAddOp3(v
, OP_Insert
, pMWin
->iEphCsr
, regRecord
, regRowid
);
1158 /* End of the input loop */
1159 sqlite3WhereEnd(pWInfo
);
1161 /* Invoke "flush_partition" to deal with the final (or only) partition */
1162 sqlite3VdbeAddOp2(v
, OP_Gosub
, regFlushPart
, lblFlushPart
);
1166 ** Invoke the sub-routine at regGosub (generated by code in select.c) to
1167 ** return the current row of Window.iEphCsr. If all window functions are
1168 ** aggregate window functions that use the standard API, a single
1169 ** OP_Gosub instruction is all that this routine generates. Extra VM code
1170 ** for per-row processing is only generated for the following built-in window
1178 static void windowReturnOneRow(
1184 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1186 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
1187 FuncDef
*pFunc
= pWin
->pFunc
;
1188 if( pFunc
->xSFunc
==nth_valueStepFunc
1189 || pFunc
->xSFunc
==first_valueStepFunc
1191 int csr
= pWin
->csrApp
;
1192 int lbl
= sqlite3VdbeMakeLabel(v
);
1193 int tmpReg
= sqlite3GetTempReg(pParse
);
1194 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regResult
);
1196 if( pFunc
->xSFunc
==nth_valueStepFunc
){
1197 sqlite3VdbeAddOp3(v
, OP_Column
, pMWin
->iEphCsr
, pWin
->iArgCol
+1,tmpReg
);
1199 sqlite3VdbeAddOp2(v
, OP_Integer
, 1, tmpReg
);
1201 sqlite3VdbeAddOp3(v
, OP_Add
, tmpReg
, pWin
->regApp
, tmpReg
);
1202 sqlite3VdbeAddOp3(v
, OP_Gt
, pWin
->regApp
+1, lbl
, tmpReg
);
1203 sqlite3VdbeAddOp3(v
, OP_SeekRowid
, csr
, lbl
, tmpReg
);
1204 sqlite3VdbeAddOp3(v
, OP_Column
, csr
, pWin
->iArgCol
, pWin
->regResult
);
1205 sqlite3VdbeResolveLabel(v
, lbl
);
1206 sqlite3ReleaseTempReg(pParse
, tmpReg
);
1208 else if( pFunc
->xSFunc
==leadStepFunc
|| pFunc
->xSFunc
==lagStepFunc
){
1209 int nArg
= pWin
->pOwner
->x
.pList
->nExpr
;
1210 int iEph
= pMWin
->iEphCsr
;
1211 int csr
= pWin
->csrApp
;
1212 int lbl
= sqlite3VdbeMakeLabel(v
);
1213 int tmpReg
= sqlite3GetTempReg(pParse
);
1216 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regResult
);
1218 sqlite3VdbeAddOp3(v
, OP_Column
, iEph
, pWin
->iArgCol
+2, pWin
->regResult
);
1220 sqlite3VdbeAddOp2(v
, OP_Rowid
, iEph
, tmpReg
);
1222 int val
= (pFunc
->xSFunc
==leadStepFunc
? 1 : -1);
1223 sqlite3VdbeAddOp2(v
, OP_AddImm
, tmpReg
, val
);
1225 int op
= (pFunc
->xSFunc
==leadStepFunc
? OP_Add
: OP_Subtract
);
1226 int tmpReg2
= sqlite3GetTempReg(pParse
);
1227 sqlite3VdbeAddOp3(v
, OP_Column
, iEph
, pWin
->iArgCol
+1, tmpReg2
);
1228 sqlite3VdbeAddOp3(v
, op
, tmpReg2
, tmpReg
, tmpReg
);
1229 sqlite3ReleaseTempReg(pParse
, tmpReg2
);
1232 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
);
1238 sqlite3VdbeAddOp2(v
, OP_Gosub
, regGosub
, addrGosub
);
1242 ** Invoke the code generated by windowReturnOneRow() and, optionally, the
1243 ** xInverse() function for each window function, for one or more rows
1244 ** from the Window.iEphCsr temp table. This routine generates VM code
1247 ** while( regCtr>0 ){
1249 ** windowReturnOneRow()
1251 ** AggStep (xInverse)
1253 ** Next (Window.iEphCsr)
1256 static void windowReturnRows(
1258 Window
*pMWin
, /* List of window functions */
1259 int regCtr
, /* Register containing number of rows */
1260 int regGosub
, /* Register for Gosub addrGosub */
1261 int addrGosub
, /* Address of sub-routine for ReturnOneRow */
1262 int regInvArg
, /* Array of registers for xInverse args */
1263 int regInvSize
/* Register containing size of partition */
1266 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1267 windowAggFinal(pParse
, pMWin
, 0);
1268 addr
= sqlite3VdbeAddOp3(v
, OP_IfPos
, regCtr
, sqlite3VdbeCurrentAddr(v
)+2 ,1);
1269 sqlite3VdbeAddOp2(v
, OP_Goto
, 0, 0);
1270 windowReturnOneRow(pParse
, pMWin
, regGosub
, addrGosub
);
1272 windowAggStep(pParse
, pMWin
, pMWin
->iEphCsr
, 1, regInvArg
, regInvSize
);
1274 sqlite3VdbeAddOp2(v
, OP_Next
, pMWin
->iEphCsr
, addr
);
1275 sqlite3VdbeJumpHere(v
, addr
+1); /* The OP_Goto */
1279 ** Generate code to set the accumulator register for each window function
1280 ** in the linked list passed as the second argument to NULL. And perform
1281 ** any equivalent initialization required by any built-in window functions
1284 static int windowInitAccum(Parse
*pParse
, Window
*pMWin
){
1285 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1289 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
1290 FuncDef
*pFunc
= pWin
->pFunc
;
1291 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regAccum
);
1292 nArg
= MAX(nArg
, windowArgCount(pWin
));
1293 if( pFunc
->xSFunc
==nth_valueStepFunc
1294 || pFunc
->xSFunc
==first_valueStepFunc
1296 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, pWin
->regApp
);
1297 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, pWin
->regApp
+1);
1300 if( (pFunc
->funcFlags
& SQLITE_FUNC_MINMAX
) && pWin
->csrApp
){
1301 assert( pWin
->eStart
!=TK_UNBOUNDED
);
1302 sqlite3VdbeAddOp1(v
, OP_ResetSorter
, pWin
->csrApp
);
1303 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, pWin
->regApp
+1);
1306 regArg
= pParse
->nMem
+1;
1307 pParse
->nMem
+= nArg
;
1313 ** This function does the work of sqlite3WindowCodeStep() for all "ROWS"
1314 ** window frame types except for "BETWEEN UNBOUNDED PRECEDING AND CURRENT
1315 ** ROW". Pseudo-code for each follows.
1317 ** ROWS BETWEEN <expr1> PRECEDING AND <expr2> FOLLOWING
1320 ** if( new partition ){
1321 ** Gosub flush_partition
1323 ** Insert (record in eph-table)
1324 ** sqlite3WhereEnd()
1325 ** Gosub flush_partition
1329 ** OpenDup (iEphCsr -> csrStart)
1330 ** OpenDup (iEphCsr -> csrEnd)
1332 ** regStart = <expr1> // PRECEDING expression
1333 ** regEnd = <expr2> // FOLLOWING expression
1334 ** if( regStart<0 || regEnd<0 ){ error! }
1335 ** Rewind (csr,csrStart,csrEnd) // if EOF goto flush_partition_done
1336 ** Next(csrEnd) // if EOF skip Aggstep
1338 ** if( (regEnd--)<=0 ){
1339 ** AggFinal (xValue)
1341 ** Next(csr) // if EOF goto flush_partition_done
1342 ** if( (regStart--)<=0 ){
1343 ** AggStep (csrStart, xInverse)
1347 ** flush_partition_done:
1348 ** ResetSorter (csr)
1351 ** ROWS BETWEEN <expr> PRECEDING AND CURRENT ROW
1352 ** ROWS BETWEEN CURRENT ROW AND <expr> FOLLOWING
1353 ** ROWS BETWEEN UNBOUNDED PRECEDING AND <expr> FOLLOWING
1355 ** These are similar to the above. For "CURRENT ROW", intialize the
1356 ** register to 0. For "UNBOUNDED PRECEDING" to infinity.
1358 ** ROWS BETWEEN <expr> PRECEDING AND UNBOUNDED FOLLOWING
1359 ** ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
1361 ** Rewind (csr,csrStart,csrEnd) // if EOF goto flush_partition_done
1363 ** Next(csrEnd) // Exit while(1) at EOF
1367 ** AggFinal (xValue)
1369 ** Next(csr) // if EOF goto flush_partition_done
1370 ** if( (regStart--)<=0 ){
1371 ** AggStep (csrStart, xInverse)
1376 ** For the "CURRENT ROW AND UNBOUNDED FOLLOWING" case, the final if()
1377 ** condition is always true (as if regStart were initialized to 0).
1379 ** RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
1381 ** This is the only RANGE case handled by this routine. It modifies the
1382 ** second while( 1 ) loop in "ROWS BETWEEN CURRENT ... UNBOUNDED..." to
1386 ** AggFinal (xValue)
1390 ** Next(csr) // if EOF goto flush_partition_done
1391 ** if( new peer ) break;
1393 ** while( (regPeer--)>0 ){
1394 ** AggStep (csrStart, xInverse)
1399 ** ROWS BETWEEN <expr> FOLLOWING AND <expr> FOLLOWING
1401 ** regEnd = regEnd - regStart
1402 ** Rewind (csr,csrStart,csrEnd) // if EOF goto flush_partition_done
1404 ** Next(csrEnd) // if EOF fall-through
1405 ** if( (regEnd--)<=0 ){
1406 ** if( (regStart--)<=0 ){
1407 ** AggFinal (xValue)
1409 ** Next(csr) // if EOF goto flush_partition_done
1411 ** AggStep (csrStart, xInverse)
1415 ** ROWS BETWEEN <expr> PRECEDING AND <expr> PRECEDING
1417 ** Replace the bit after "Rewind" in the above with:
1419 ** if( (regEnd--)<=0 ){
1423 ** AggFinal (xValue)
1425 ** Next(csr) // if EOF goto flush_partition_done
1426 ** if( (regStart--)<=0 ){
1427 ** AggStep (csr2, xInverse)
1432 static void windowCodeRowExprStep(
1439 Window
*pMWin
= p
->pWin
;
1440 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1441 int regFlushPart
; /* Register for "Gosub flush_partition" */
1442 int lblFlushPart
; /* Label for "Gosub flush_partition" */
1443 int lblFlushDone
; /* Label for "Gosub flush_partition_done" */
1447 int csrStart
= pParse
->nTab
++;
1448 int csrEnd
= pParse
->nTab
++;
1449 int regStart
; /* Value of <expr> PRECEDING */
1450 int regEnd
; /* Value of <expr> FOLLOWING */
1457 assert( pMWin
->eStart
==TK_PRECEDING
1458 || pMWin
->eStart
==TK_CURRENT
1459 || pMWin
->eStart
==TK_FOLLOWING
1460 || pMWin
->eStart
==TK_UNBOUNDED
1462 assert( pMWin
->eEnd
==TK_FOLLOWING
1463 || pMWin
->eEnd
==TK_CURRENT
1464 || pMWin
->eEnd
==TK_UNBOUNDED
1465 || pMWin
->eEnd
==TK_PRECEDING
1468 /* Allocate register and label for the "flush_partition" sub-routine. */
1469 regFlushPart
= ++pParse
->nMem
;
1470 lblFlushPart
= sqlite3VdbeMakeLabel(v
);
1471 lblFlushDone
= sqlite3VdbeMakeLabel(v
);
1473 regStart
= ++pParse
->nMem
;
1474 regEnd
= ++pParse
->nMem
;
1476 windowPartitionCache(pParse
, p
, pWInfo
, regFlushPart
, lblFlushPart
, ®Size
);
1478 addrGoto
= sqlite3VdbeAddOp0(v
, OP_Goto
);
1480 /* Start of "flush_partition" */
1481 sqlite3VdbeResolveLabel(v
, lblFlushPart
);
1482 sqlite3VdbeAddOp2(v
, OP_Once
, 0, sqlite3VdbeCurrentAddr(v
)+3);
1483 sqlite3VdbeAddOp2(v
, OP_OpenDup
, csrStart
, pMWin
->iEphCsr
);
1484 sqlite3VdbeAddOp2(v
, OP_OpenDup
, csrEnd
, pMWin
->iEphCsr
);
1486 /* If either regStart or regEnd are not non-negative integers, throw
1488 if( pMWin
->pStart
){
1489 sqlite3ExprCode(pParse
, pMWin
->pStart
, regStart
);
1490 windowCheckFrameValue(pParse
, regStart
, 0);
1493 sqlite3ExprCode(pParse
, pMWin
->pEnd
, regEnd
);
1494 windowCheckFrameValue(pParse
, regEnd
, 1);
1497 /* If this is "ROWS <expr1> FOLLOWING AND ROWS <expr2> FOLLOWING", do:
1499 ** if( regEnd<regStart ){
1500 ** // The frame always consists of 0 rows
1501 ** regStart = regSize;
1503 ** regEnd = regEnd - regStart;
1505 if( pMWin
->pEnd
&& pMWin
->pStart
&& pMWin
->eStart
==TK_FOLLOWING
){
1506 assert( pMWin
->eEnd
==TK_FOLLOWING
);
1507 sqlite3VdbeAddOp3(v
, OP_Ge
, regStart
, sqlite3VdbeCurrentAddr(v
)+2, regEnd
);
1508 sqlite3VdbeAddOp2(v
, OP_Copy
, regSize
, regStart
);
1509 sqlite3VdbeAddOp3(v
, OP_Subtract
, regStart
, regEnd
, regEnd
);
1512 if( pMWin
->pEnd
&& pMWin
->pStart
&& pMWin
->eEnd
==TK_PRECEDING
){
1513 assert( pMWin
->eStart
==TK_PRECEDING
);
1514 sqlite3VdbeAddOp3(v
, OP_Le
, regStart
, sqlite3VdbeCurrentAddr(v
)+3, regEnd
);
1515 sqlite3VdbeAddOp2(v
, OP_Copy
, regSize
, regStart
);
1516 sqlite3VdbeAddOp2(v
, OP_Copy
, regSize
, regEnd
);
1519 /* Initialize the accumulator register for each window function to NULL */
1520 regArg
= windowInitAccum(pParse
, pMWin
);
1522 sqlite3VdbeAddOp2(v
, OP_Rewind
, pMWin
->iEphCsr
, lblFlushDone
);
1523 sqlite3VdbeAddOp2(v
, OP_Rewind
, csrStart
, lblFlushDone
);
1524 sqlite3VdbeChangeP5(v
, 1);
1525 sqlite3VdbeAddOp2(v
, OP_Rewind
, csrEnd
, lblFlushDone
);
1526 sqlite3VdbeChangeP5(v
, 1);
1528 /* Invoke AggStep function for each window function using the row that
1529 ** csrEnd currently points to. Or, if csrEnd is already at EOF,
1531 addrTop
= sqlite3VdbeCurrentAddr(v
);
1532 if( pMWin
->eEnd
==TK_PRECEDING
){
1533 addrIfPos1
= sqlite3VdbeAddOp3(v
, OP_IfPos
, regEnd
, 0 , 1);
1535 sqlite3VdbeAddOp2(v
, OP_Next
, csrEnd
, sqlite3VdbeCurrentAddr(v
)+2);
1536 addr
= sqlite3VdbeAddOp0(v
, OP_Goto
);
1537 windowAggStep(pParse
, pMWin
, csrEnd
, 0, regArg
, regSize
);
1538 if( pMWin
->eEnd
==TK_UNBOUNDED
){
1539 sqlite3VdbeAddOp2(v
, OP_Goto
, 0, addrTop
);
1540 sqlite3VdbeJumpHere(v
, addr
);
1541 addrTop
= sqlite3VdbeCurrentAddr(v
);
1543 sqlite3VdbeJumpHere(v
, addr
);
1544 if( pMWin
->eEnd
==TK_PRECEDING
){
1545 sqlite3VdbeJumpHere(v
, addrIfPos1
);
1549 if( pMWin
->eEnd
==TK_FOLLOWING
){
1550 addrIfPos1
= sqlite3VdbeAddOp3(v
, OP_IfPos
, regEnd
, 0 , 1);
1552 if( pMWin
->eStart
==TK_FOLLOWING
){
1553 addrIfPos2
= sqlite3VdbeAddOp3(v
, OP_IfPos
, regStart
, 0 , 1);
1555 windowAggFinal(pParse
, pMWin
, 0);
1556 windowReturnOneRow(pParse
, pMWin
, regGosub
, addrGosub
);
1557 sqlite3VdbeAddOp2(v
, OP_Next
, pMWin
->iEphCsr
, sqlite3VdbeCurrentAddr(v
)+2);
1558 sqlite3VdbeAddOp2(v
, OP_Goto
, 0, lblFlushDone
);
1559 if( pMWin
->eStart
==TK_FOLLOWING
){
1560 sqlite3VdbeJumpHere(v
, addrIfPos2
);
1563 if( pMWin
->eStart
==TK_CURRENT
1564 || pMWin
->eStart
==TK_PRECEDING
1565 || pMWin
->eStart
==TK_FOLLOWING
1567 int addrJumpHere
= 0;
1568 if( pMWin
->eStart
==TK_PRECEDING
){
1569 addrJumpHere
= sqlite3VdbeAddOp3(v
, OP_IfPos
, regStart
, 0 , 1);
1571 sqlite3VdbeAddOp2(v
, OP_Next
, csrStart
, sqlite3VdbeCurrentAddr(v
)+1);
1572 windowAggStep(pParse
, pMWin
, csrStart
, 1, regArg
, regSize
);
1574 sqlite3VdbeJumpHere(v
, addrJumpHere
);
1577 if( pMWin
->eEnd
==TK_FOLLOWING
){
1578 sqlite3VdbeJumpHere(v
, addrIfPos1
);
1580 sqlite3VdbeAddOp2(v
, OP_Goto
, 0, addrTop
);
1582 /* flush_partition_done: */
1583 sqlite3VdbeResolveLabel(v
, lblFlushDone
);
1584 sqlite3VdbeAddOp1(v
, OP_ResetSorter
, pMWin
->iEphCsr
);
1585 sqlite3VdbeAddOp1(v
, OP_Return
, regFlushPart
);
1587 /* Jump to here to skip over flush_partition */
1588 sqlite3VdbeJumpHere(v
, addrGoto
);
1592 ** This function does the work of sqlite3WindowCodeStep() for cases that
1593 ** would normally be handled by windowCodeDefaultStep() when there are
1594 ** one or more built-in window-functions that require the entire partition
1595 ** to be cached in a temp table before any rows can be returned. Additionally.
1596 ** "RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING" is always handled by
1599 ** Pseudo-code corresponding to the VM code generated by this function
1600 ** for each type of window follows.
1602 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1606 ** OpenDup (iEphCsr -> csrLead)
1609 ** foreach row (csrLead){
1611 ** AggFinal (xValue)
1612 ** for(i=0; i<ctr; i++){
1618 ** AggStep (csrLead)
1622 ** AggFinal (xFinalize)
1623 ** for(i=0; i<ctr; i++){
1628 ** ResetSorter (csr)
1631 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1633 ** As above, except that the "if( new peer )" branch is always taken.
1635 ** RANGE BETWEEN CURRENT ROW AND CURRENT ROW
1637 ** As above, except that each of the for() loops becomes:
1639 ** for(i=0; i<ctr; i++){
1641 ** AggStep (xInverse, iEphCsr)
1645 ** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
1649 ** OpenDup (iEphCsr -> csrLead)
1651 ** foreach row (csrLead) {
1652 ** AggStep (csrLead)
1654 ** foreach row (iEphCsr) {
1658 ** RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
1662 ** OpenDup (iEphCsr -> csrLead)
1664 ** foreach row (csrLead){
1665 ** AggStep (csrLead)
1669 ** foreach row (csrLead){
1671 ** AggFinal (xValue)
1672 ** for(i=0; i<ctr; i++){
1674 ** AggStep (xInverse, iEphCsr)
1682 ** AggFinal (xFinalize)
1683 ** for(i=0; i<ctr; i++){
1688 ** ResetSorter (csr)
1691 static void windowCodeCacheStep(
1698 Window
*pMWin
= p
->pWin
;
1699 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1702 ExprList
*pPart
= pMWin
->pPartition
;
1703 ExprList
*pOrderBy
= pMWin
->pOrderBy
;
1704 int nPeer
= pOrderBy
? pOrderBy
->nExpr
: 0;
1707 int addrGoto
; /* Address of Goto used to jump flush_par.. */
1708 int addrNext
; /* Jump here for next iteration of loop */
1713 int regArg
; /* Register array to martial function args */
1716 int bReverse
= pMWin
->pOrderBy
&& pMWin
->eStart
==TK_CURRENT
1717 && pMWin
->eEnd
==TK_UNBOUNDED
;
1719 assert( (pMWin
->eStart
==TK_UNBOUNDED
&& pMWin
->eEnd
==TK_CURRENT
)
1720 || (pMWin
->eStart
==TK_UNBOUNDED
&& pMWin
->eEnd
==TK_UNBOUNDED
)
1721 || (pMWin
->eStart
==TK_CURRENT
&& pMWin
->eEnd
==TK_CURRENT
)
1722 || (pMWin
->eStart
==TK_CURRENT
&& pMWin
->eEnd
==TK_UNBOUNDED
)
1725 lblEmpty
= sqlite3VdbeMakeLabel(v
);
1726 regNewPeer
= pParse
->nMem
+1;
1727 pParse
->nMem
+= nPeer
;
1729 /* Allocate register and label for the "flush_partition" sub-routine. */
1730 regFlushPart
= ++pParse
->nMem
;
1731 lblFlushPart
= sqlite3VdbeMakeLabel(v
);
1733 csrLead
= pParse
->nTab
++;
1734 regCtr
= ++pParse
->nMem
;
1736 windowPartitionCache(pParse
, p
, pWInfo
, regFlushPart
, lblFlushPart
, ®Size
);
1737 addrGoto
= sqlite3VdbeAddOp0(v
, OP_Goto
);
1739 /* Start of "flush_partition" */
1740 sqlite3VdbeResolveLabel(v
, lblFlushPart
);
1741 sqlite3VdbeAddOp2(v
, OP_Once
, 0, sqlite3VdbeCurrentAddr(v
)+2);
1742 sqlite3VdbeAddOp2(v
, OP_OpenDup
, csrLead
, pMWin
->iEphCsr
);
1744 /* Initialize the accumulator register for each window function to NULL */
1745 regArg
= windowInitAccum(pParse
, pMWin
);
1747 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, regCtr
);
1748 sqlite3VdbeAddOp2(v
, OP_Rewind
, csrLead
, lblEmpty
);
1749 sqlite3VdbeAddOp2(v
, OP_Rewind
, pMWin
->iEphCsr
, lblEmpty
);
1752 int addr
= sqlite3VdbeCurrentAddr(v
);
1753 windowAggStep(pParse
, pMWin
, csrLead
, 0, regArg
, regSize
);
1754 sqlite3VdbeAddOp2(v
, OP_Next
, csrLead
, addr
);
1755 sqlite3VdbeAddOp2(v
, OP_Rewind
, csrLead
, lblEmpty
);
1757 addrNext
= sqlite3VdbeCurrentAddr(v
);
1759 if( pOrderBy
&& (pMWin
->eEnd
==TK_CURRENT
|| pMWin
->eStart
==TK_CURRENT
) ){
1760 int bCurrent
= (pMWin
->eStart
==TK_CURRENT
);
1761 int addrJump
= 0; /* Address of OP_Jump below */
1762 if( pMWin
->eType
==TK_RANGE
){
1763 int iOff
= pMWin
->nBufferCol
+ (pPart
? pPart
->nExpr
: 0);
1764 int regPeer
= pMWin
->regPart
+ (pPart
? pPart
->nExpr
: 0);
1765 KeyInfo
*pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
, pOrderBy
, 0, 0);
1766 for(k
=0; k
<nPeer
; k
++){
1767 sqlite3VdbeAddOp3(v
, OP_Column
, csrLead
, iOff
+k
, regNewPeer
+k
);
1769 addr
= sqlite3VdbeAddOp3(v
, OP_Compare
, regNewPeer
, regPeer
, nPeer
);
1770 sqlite3VdbeAppendP4(v
, (void*)pKeyInfo
, P4_KEYINFO
);
1771 addrJump
= sqlite3VdbeAddOp3(v
, OP_Jump
, addr
+2, 0, addr
+2);
1772 sqlite3VdbeAddOp3(v
, OP_Copy
, regNewPeer
, regPeer
, nPeer
-1);
1775 windowReturnRows(pParse
, pMWin
, regCtr
, regGosub
, addrGosub
,
1776 (bCurrent
? regArg
: 0), (bCurrent
? regSize
: 0)
1778 if( addrJump
) sqlite3VdbeJumpHere(v
, addrJump
);
1782 windowAggStep(pParse
, pMWin
, csrLead
, 0, regArg
, regSize
);
1784 sqlite3VdbeAddOp2(v
, OP_AddImm
, regCtr
, 1);
1785 sqlite3VdbeAddOp2(v
, OP_Next
, csrLead
, addrNext
);
1787 windowReturnRows(pParse
, pMWin
, regCtr
, regGosub
, addrGosub
, 0, 0);
1789 sqlite3VdbeResolveLabel(v
, lblEmpty
);
1790 sqlite3VdbeAddOp1(v
, OP_ResetSorter
, pMWin
->iEphCsr
);
1791 sqlite3VdbeAddOp1(v
, OP_Return
, regFlushPart
);
1793 /* Jump to here to skip over flush_partition */
1794 sqlite3VdbeJumpHere(v
, addrGoto
);
1799 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1802 ** if( new partition ){
1803 ** AggFinal (xFinalize)
1805 ** ResetSorter eph-table
1807 ** else if( new peer ){
1808 ** AggFinal (xValue)
1810 ** ResetSorter eph-table
1813 ** Insert (record into eph-table)
1814 ** sqlite3WhereEnd()
1815 ** AggFinal (xFinalize)
1818 ** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
1820 ** As above, except take no action for a "new peer". Invoke
1821 ** the sub-routine once only for each partition.
1823 ** RANGE BETWEEN CURRENT ROW AND CURRENT ROW
1825 ** As above, except that the "new peer" condition is handled in the
1826 ** same way as "new partition" (so there is no "else if" block).
1828 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1830 ** As above, except assume every row is a "new peer".
1832 static void windowCodeDefaultStep(
1839 Window
*pMWin
= p
->pWin
;
1840 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1842 int iSubCsr
= p
->pSrc
->a
[0].iCursor
;
1843 int nSub
= p
->pSrc
->a
[0].pTab
->nCol
;
1844 int reg
= pParse
->nMem
+1;
1845 int regRecord
= reg
+nSub
;
1846 int regRowid
= regRecord
+1;
1848 ExprList
*pPart
= pMWin
->pPartition
;
1849 ExprList
*pOrderBy
= pMWin
->pOrderBy
;
1851 assert( pMWin
->eType
==TK_RANGE
1852 || (pMWin
->eStart
==TK_UNBOUNDED
&& pMWin
->eEnd
==TK_CURRENT
)
1855 assert( (pMWin
->eStart
==TK_UNBOUNDED
&& pMWin
->eEnd
==TK_CURRENT
)
1856 || (pMWin
->eStart
==TK_UNBOUNDED
&& pMWin
->eEnd
==TK_UNBOUNDED
)
1857 || (pMWin
->eStart
==TK_CURRENT
&& pMWin
->eEnd
==TK_CURRENT
)
1858 || (pMWin
->eStart
==TK_CURRENT
&& pMWin
->eEnd
==TK_UNBOUNDED
&& !pOrderBy
)
1861 if( pMWin
->eEnd
==TK_UNBOUNDED
){
1865 pParse
->nMem
+= nSub
+ 2;
1867 /* Martial the row returned by the sub-select into an array of
1869 for(k
=0; k
<nSub
; k
++){
1870 sqlite3VdbeAddOp3(v
, OP_Column
, iSubCsr
, k
, reg
+k
);
1873 /* Check if this is the start of a new partition or peer group. */
1874 if( pPart
|| pOrderBy
){
1875 int nPart
= (pPart
? pPart
->nExpr
: 0);
1878 int nPeer
= (pOrderBy
? pOrderBy
->nExpr
: 0);
1881 int regNewPart
= reg
+ pMWin
->nBufferCol
;
1882 KeyInfo
*pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
, pPart
, 0, 0);
1883 addr
= sqlite3VdbeAddOp3(v
, OP_Compare
, regNewPart
, pMWin
->regPart
,nPart
);
1884 sqlite3VdbeAppendP4(v
, (void*)pKeyInfo
, P4_KEYINFO
);
1885 addrJump
= sqlite3VdbeAddOp3(v
, OP_Jump
, addr
+2, 0, addr
+2);
1886 windowAggFinal(pParse
, pMWin
, 1);
1888 addrGoto
= sqlite3VdbeAddOp0(v
, OP_Goto
);
1893 int regNewPeer
= reg
+ pMWin
->nBufferCol
+ nPart
;
1894 int regPeer
= pMWin
->regPart
+ nPart
;
1896 if( addrJump
) sqlite3VdbeJumpHere(v
, addrJump
);
1897 if( pMWin
->eType
==TK_RANGE
){
1898 KeyInfo
*pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
, pOrderBy
, 0, 0);
1899 addr
= sqlite3VdbeAddOp3(v
, OP_Compare
, regNewPeer
, regPeer
, nPeer
);
1900 sqlite3VdbeAppendP4(v
, (void*)pKeyInfo
, P4_KEYINFO
);
1901 addrJump
= sqlite3VdbeAddOp3(v
, OP_Jump
, addr
+2, 0, addr
+2);
1905 windowAggFinal(pParse
, pMWin
, pMWin
->eStart
==TK_CURRENT
);
1906 if( addrGoto
) sqlite3VdbeJumpHere(v
, addrGoto
);
1909 sqlite3VdbeAddOp2(v
, OP_Rewind
, pMWin
->iEphCsr
,sqlite3VdbeCurrentAddr(v
)+3);
1910 sqlite3VdbeAddOp2(v
, OP_Gosub
, regGosub
, addrGosub
);
1911 sqlite3VdbeAddOp2(v
, OP_Next
, pMWin
->iEphCsr
, sqlite3VdbeCurrentAddr(v
)-1);
1913 sqlite3VdbeAddOp1(v
, OP_ResetSorter
, pMWin
->iEphCsr
);
1915 v
, OP_Copy
, reg
+pMWin
->nBufferCol
, pMWin
->regPart
, nPart
+nPeer
-1
1918 if( addrJump
) sqlite3VdbeJumpHere(v
, addrJump
);
1921 /* Invoke step function for window functions */
1922 windowAggStep(pParse
, pMWin
, -1, 0, reg
, 0);
1924 /* Buffer the current row in the ephemeral table. */
1925 if( pMWin
->nBufferCol
>0 ){
1926 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, reg
, pMWin
->nBufferCol
, regRecord
);
1928 sqlite3VdbeAddOp2(v
, OP_Blob
, 0, regRecord
);
1929 sqlite3VdbeAppendP4(v
, (void*)"", 0);
1931 sqlite3VdbeAddOp2(v
, OP_NewRowid
, pMWin
->iEphCsr
, regRowid
);
1932 sqlite3VdbeAddOp3(v
, OP_Insert
, pMWin
->iEphCsr
, regRecord
, regRowid
);
1934 /* End the database scan loop. */
1935 sqlite3WhereEnd(pWInfo
);
1937 windowAggFinal(pParse
, pMWin
, 1);
1938 sqlite3VdbeAddOp2(v
, OP_Rewind
, pMWin
->iEphCsr
,sqlite3VdbeCurrentAddr(v
)+3);
1939 sqlite3VdbeAddOp2(v
, OP_Gosub
, regGosub
, addrGosub
);
1940 sqlite3VdbeAddOp2(v
, OP_Next
, pMWin
->iEphCsr
, sqlite3VdbeCurrentAddr(v
)-1);
1944 ** Allocate and return a duplicate of the Window object indicated by the
1945 ** third argument. Set the Window.pOwner field of the new object to
1948 Window
*sqlite3WindowDup(sqlite3
*db
, Expr
*pOwner
, Window
*p
){
1951 pNew
= sqlite3DbMallocZero(db
, sizeof(Window
));
1953 pNew
->zName
= sqlite3DbStrDup(db
, p
->zName
);
1954 pNew
->pFilter
= sqlite3ExprDup(db
, p
->pFilter
, 0);
1955 pNew
->pPartition
= sqlite3ExprListDup(db
, p
->pPartition
, 0);
1956 pNew
->pOrderBy
= sqlite3ExprListDup(db
, p
->pOrderBy
, 0);
1957 pNew
->eType
= p
->eType
;
1958 pNew
->eEnd
= p
->eEnd
;
1959 pNew
->eStart
= p
->eStart
;
1960 pNew
->pStart
= sqlite3ExprDup(db
, p
->pStart
, 0);
1961 pNew
->pEnd
= sqlite3ExprDup(db
, p
->pEnd
, 0);
1962 pNew
->pOwner
= pOwner
;
1969 ** Return a copy of the linked list of Window objects passed as the
1972 Window
*sqlite3WindowListDup(sqlite3
*db
, Window
*p
){
1975 Window
**pp
= &pRet
;
1977 for(pWin
=p
; pWin
; pWin
=pWin
->pNextWin
){
1978 *pp
= sqlite3WindowDup(db
, 0, pWin
);
1980 pp
= &((*pp
)->pNextWin
);
1987 ** sqlite3WhereBegin() has already been called for the SELECT statement
1988 ** passed as the second argument when this function is invoked. It generates
1989 ** code to populate the Window.regResult register for each window function and
1990 ** invoke the sub-routine at instruction addrGosub once for each row.
1991 ** This function calls sqlite3WhereEnd() before returning.
1993 void sqlite3WindowCodeStep(
1994 Parse
*pParse
, /* Parse context */
1995 Select
*p
, /* Rewritten SELECT statement */
1996 WhereInfo
*pWInfo
, /* Context returned by sqlite3WhereBegin() */
1997 int regGosub
, /* Register for OP_Gosub */
1998 int addrGosub
/* OP_Gosub here to return each row */
2000 Window
*pMWin
= p
->pWin
;
2002 /* There are three different functions that may be used to do the work
2003 ** of this one, depending on the window frame and the specific built-in
2004 ** window functions used (if any).
2006 ** windowCodeRowExprStep() handles all "ROWS" window frames, except for:
2008 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
2010 ** The exception is because windowCodeRowExprStep() implements all window
2011 ** frame types by caching the entire partition in a temp table, and
2012 ** "ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW" is easy enough to
2013 ** implement without such a cache.
2015 ** windowCodeCacheStep() is used for:
2017 ** RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
2019 ** It is also used for anything not handled by windowCodeRowExprStep()
2020 ** that invokes a built-in window function that requires the entire
2021 ** partition to be cached in a temp table before any rows are returned
2022 ** (e.g. nth_value() or percent_rank()).
2024 ** Finally, assuming there is no built-in window function that requires
2025 ** the partition to be cached, windowCodeDefaultStep() is used for:
2027 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
2028 ** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
2029 ** RANGE BETWEEN CURRENT ROW AND CURRENT ROW
2030 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
2032 ** windowCodeDefaultStep() is the only one of the three functions that
2033 ** does not cache each partition in a temp table before beginning to
2036 if( pMWin
->eType
==TK_ROWS
2037 && (pMWin
->eStart
!=TK_UNBOUNDED
||pMWin
->eEnd
!=TK_CURRENT
||!pMWin
->pOrderBy
)
2039 windowCodeRowExprStep(pParse
, p
, pWInfo
, regGosub
, addrGosub
);
2042 int bCache
= 0; /* True to use CacheStep() */
2044 if( pMWin
->eStart
==TK_CURRENT
&& pMWin
->eEnd
==TK_UNBOUNDED
){
2047 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
2048 FuncDef
*pFunc
= pWin
->pFunc
;
2049 if( (pFunc
->funcFlags
& SQLITE_FUNC_WINDOW_SIZE
)
2050 || (pFunc
->xSFunc
==nth_valueStepFunc
)
2051 || (pFunc
->xSFunc
==first_valueStepFunc
)
2052 || (pFunc
->xSFunc
==leadStepFunc
)
2053 || (pFunc
->xSFunc
==lagStepFunc
)
2061 /* Otherwise, call windowCodeDefaultStep(). */
2063 windowCodeCacheStep(pParse
, p
, pWInfo
, regGosub
, addrGosub
);
2065 windowCodeDefaultStep(pParse
, p
, pWInfo
, regGosub
, addrGosub
);