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 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
261 p
->nTotal
= sqlite3_value_int64(apArg
[0]);
265 p
->nValue
= p
->nStep
;
269 static void percent_rankInvFunc(
270 sqlite3_context
*pCtx
,
272 sqlite3_value
**apArg
275 static void percent_rankValueFunc(sqlite3_context
*pCtx
){
277 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
280 double r
= (double)(p
->nValue
-1) / (double)(p
->nTotal
-1);
281 sqlite3_result_double(pCtx
, r
);
283 sqlite3_result_double(pCtx
, 0.0);
290 ** Implementation of built-in window function cume_dist(). Assumes that
291 ** the window frame has been set to:
293 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
295 static void cume_distStepFunc(
296 sqlite3_context
*pCtx
,
298 sqlite3_value
**apArg
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 p
= (struct NtileCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
351 p
->nParam
= sqlite3_value_int64(apArg
[0]);
352 p
->nTotal
= sqlite3_value_int64(apArg
[1]);
354 sqlite3_result_error(
355 pCtx
, "argument of ntile must be a positive integer", -1
362 static void ntileInvFunc(
363 sqlite3_context
*pCtx
,
365 sqlite3_value
**apArg
368 static void ntileValueFunc(sqlite3_context
*pCtx
){
370 p
= (struct NtileCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
371 if( p
&& p
->nParam
>0 ){
372 int nSize
= (p
->nTotal
/ p
->nParam
);
374 sqlite3_result_int64(pCtx
, p
->iRow
);
376 i64 nLarge
= p
->nTotal
- p
->nParam
*nSize
;
377 i64 iSmall
= nLarge
*(nSize
+1);
378 i64 iRow
= p
->iRow
-1;
380 assert( (nLarge
*(nSize
+1) + (p
->nParam
-nLarge
)*nSize
)==p
->nTotal
);
383 sqlite3_result_int64(pCtx
, 1 + iRow
/(nSize
+1));
385 sqlite3_result_int64(pCtx
, 1 + nLarge
+ (iRow
-iSmall
)/nSize
);
392 ** Context object for last_value() window function.
394 struct LastValueCtx
{
400 ** Implementation of last_value().
402 static void last_valueStepFunc(
403 sqlite3_context
*pCtx
,
405 sqlite3_value
**apArg
407 struct LastValueCtx
*p
;
408 p
= (struct LastValueCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
410 sqlite3_value_free(p
->pVal
);
411 p
->pVal
= sqlite3_value_dup(apArg
[0]);
413 sqlite3_result_error_nomem(pCtx
);
419 static void last_valueInvFunc(
420 sqlite3_context
*pCtx
,
422 sqlite3_value
**apArg
424 struct LastValueCtx
*p
;
425 p
= (struct LastValueCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
429 sqlite3_value_free(p
->pVal
);
434 static void last_valueValueFunc(sqlite3_context
*pCtx
){
435 struct LastValueCtx
*p
;
436 p
= (struct LastValueCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
438 sqlite3_result_value(pCtx
, p
->pVal
);
441 static void last_valueFinalizeFunc(sqlite3_context
*pCtx
){
442 struct LastValueCtx
*p
;
443 p
= (struct LastValueCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
445 sqlite3_result_value(pCtx
, p
->pVal
);
446 sqlite3_value_free(p
->pVal
);
452 ** No-op implementations of nth_value(), first_value(), lead() and lag().
453 ** These are all implemented inline using VDBE instructions.
455 static void nth_valueStepFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**a
){}
456 static void nth_valueInvFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**ap
){}
457 static void nth_valueValueFunc(sqlite3_context
*pCtx
){}
458 static void first_valueStepFunc(sqlite3_context
*p
, int n
, sqlite3_value
**ap
){}
459 static void first_valueInvFunc(sqlite3_context
*p
, int n
, sqlite3_value
**ap
){}
460 static void first_valueValueFunc(sqlite3_context
*pCtx
){}
461 static void leadStepFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**ap
){}
462 static void leadInvFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**ap
){}
463 static void leadValueFunc(sqlite3_context
*pCtx
){}
464 static void lagStepFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**ap
){}
465 static void lagInvFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**ap
){}
466 static void lagValueFunc(sqlite3_context
*pCtx
){}
468 #define WINDOWFUNC(name,nArg,extra) { \
469 nArg, (SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0, \
470 name ## StepFunc, name ## ValueFunc, name ## ValueFunc, \
471 name ## InvFunc, #name \
474 #define WINDOWFUNCF(name,nArg,extra) { \
475 nArg, (SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0, \
476 name ## StepFunc, name ## FinalizeFunc, name ## ValueFunc, \
477 name ## InvFunc, #name \
481 ** Register those built-in window functions that are not also aggregates.
483 void sqlite3WindowFunctions(void){
484 static FuncDef aWindowFuncs
[] = {
485 WINDOWFUNC(row_number
, 0, 0),
486 WINDOWFUNC(dense_rank
, 0, 0),
487 WINDOWFUNC(rank
, 0, 0),
488 WINDOWFUNC(percent_rank
, 0, SQLITE_FUNC_WINDOW_SIZE
),
489 WINDOWFUNC(cume_dist
, 0, SQLITE_FUNC_WINDOW_SIZE
),
490 WINDOWFUNC(ntile
, 1, SQLITE_FUNC_WINDOW_SIZE
),
491 WINDOWFUNCF(last_value
, 1, 0),
492 WINDOWFUNC(nth_value
, 2, 0),
493 WINDOWFUNC(first_value
, 1, 0),
494 WINDOWFUNC(lead
, 1, 0), WINDOWFUNC(lead
, 2, 0), WINDOWFUNC(lead
, 3, 0),
495 WINDOWFUNC(lag
, 1, 0), WINDOWFUNC(lag
, 2, 0), WINDOWFUNC(lag
, 3, 0),
497 sqlite3InsertBuiltinFuncs(aWindowFuncs
, ArraySize(aWindowFuncs
));
501 ** This function is called immediately after resolving the function name
502 ** for a window function within a SELECT statement. Argument pList is a
503 ** linked list of WINDOW definitions for the current SELECT statement.
504 ** Argument pFunc is the function definition just resolved and pWin
505 ** is the Window object representing the associated OVER clause. This
506 ** function updates the contents of pWin as follows:
508 ** * If the OVER clause refered to a named window (as in "max(x) OVER win"),
509 ** search list pList for a matching WINDOW definition, and update pWin
510 ** accordingly. If no such WINDOW clause can be found, leave an error
513 ** * If the function is a built-in window function that requires the
514 ** window to be coerced (see "BUILT-IN WINDOW FUNCTIONS" at the top
515 ** of this file), pWin is updated here.
517 void sqlite3WindowUpdate(
519 Window
*pList
, /* List of named windows for this SELECT */
520 Window
*pWin
, /* Window frame to update */
521 FuncDef
*pFunc
/* Window function definition */
523 if( pWin
->zName
&& pWin
->eType
==0 ){
525 for(p
=pList
; p
; p
=p
->pNextWin
){
526 if( sqlite3StrICmp(p
->zName
, pWin
->zName
)==0 ) break;
529 sqlite3ErrorMsg(pParse
, "no such window: %s", pWin
->zName
);
532 pWin
->pPartition
= sqlite3ExprListDup(pParse
->db
, p
->pPartition
, 0);
533 pWin
->pOrderBy
= sqlite3ExprListDup(pParse
->db
, p
->pOrderBy
, 0);
534 pWin
->pStart
= sqlite3ExprDup(pParse
->db
, p
->pStart
, 0);
535 pWin
->pEnd
= sqlite3ExprDup(pParse
->db
, p
->pEnd
, 0);
536 pWin
->eStart
= p
->eStart
;
537 pWin
->eEnd
= p
->eEnd
;
538 pWin
->eType
= p
->eType
;
540 if( pFunc
->funcFlags
& SQLITE_FUNC_WINDOW
){
541 sqlite3
*db
= pParse
->db
;
543 sqlite3ErrorMsg(pParse
,
544 "FILTER clause may only be used with aggregate window functions"
547 if( pFunc
->xSFunc
==row_numberStepFunc
|| pFunc
->xSFunc
==ntileStepFunc
){
548 sqlite3ExprDelete(db
, pWin
->pStart
);
549 sqlite3ExprDelete(db
, pWin
->pEnd
);
550 pWin
->pStart
= pWin
->pEnd
= 0;
551 pWin
->eType
= TK_ROWS
;
552 pWin
->eStart
= TK_UNBOUNDED
;
553 pWin
->eEnd
= TK_CURRENT
;
556 if( pFunc
->xSFunc
==dense_rankStepFunc
|| pFunc
->xSFunc
==rankStepFunc
557 || pFunc
->xSFunc
==percent_rankStepFunc
|| pFunc
->xSFunc
==cume_distStepFunc
559 sqlite3ExprDelete(db
, pWin
->pStart
);
560 sqlite3ExprDelete(db
, pWin
->pEnd
);
561 pWin
->pStart
= pWin
->pEnd
= 0;
562 pWin
->eType
= TK_RANGE
;
563 pWin
->eStart
= TK_UNBOUNDED
;
564 pWin
->eEnd
= TK_CURRENT
;
571 ** Context object passed through sqlite3WalkExprList() to
572 ** selectWindowRewriteExprCb() by selectWindowRewriteEList().
574 typedef struct WindowRewrite WindowRewrite
;
575 struct WindowRewrite
{
581 ** Callback function used by selectWindowRewriteEList(). If necessary,
582 ** this function appends to the output expression-list and updates
583 ** expression (*ppExpr) in place.
585 static int selectWindowRewriteExprCb(Walker
*pWalker
, Expr
*pExpr
){
586 struct WindowRewrite
*p
= pWalker
->u
.pRewrite
;
587 Parse
*pParse
= pWalker
->pParse
;
592 if( pExpr
->pWin
==0 ){
596 for(pWin
=p
->pWin
; pWin
; pWin
=pWin
->pNextWin
){
597 if( pExpr
->pWin
==pWin
){
598 assert( pWin
->pOwner
==pExpr
);
605 case TK_AGG_FUNCTION
:
607 Expr
*pDup
= sqlite3ExprDup(pParse
->db
, pExpr
, 0);
608 p
->pSub
= sqlite3ExprListAppend(pParse
, p
->pSub
, pDup
);
610 assert( ExprHasProperty(pExpr
, EP_Static
)==0 );
611 ExprSetProperty(pExpr
, EP_Static
);
612 sqlite3ExprDelete(pParse
->db
, pExpr
);
613 ExprClearProperty(pExpr
, EP_Static
);
614 memset(pExpr
, 0, sizeof(Expr
));
616 pExpr
->op
= TK_COLUMN
;
617 pExpr
->iColumn
= p
->pSub
->nExpr
-1;
618 pExpr
->iTable
= p
->pWin
->iEphCsr
;
630 static int selectWindowRewriteSelectCb(Walker
*pWalker
, Select
*pSelect
){
636 ** Iterate through each expression in expression-list pEList. For each:
639 ** * aggregate function, or
640 ** * window function with a Window object that is not a member of the
641 ** linked list passed as the second argument (pWin)
643 ** Append the node to output expression-list (*ppSub). And replace it
644 ** with a TK_COLUMN that reads the (N-1)th element of table
645 ** pWin->iEphCsr, where N is the number of elements in (*ppSub) after
646 ** appending the new one.
648 static void selectWindowRewriteEList(
651 ExprList
*pEList
, /* Rewrite expressions in this list */
652 ExprList
**ppSub
/* IN/OUT: Sub-select expression-list */
655 WindowRewrite sRewrite
;
657 memset(&sWalker
, 0, sizeof(Walker
));
658 memset(&sRewrite
, 0, sizeof(WindowRewrite
));
660 sRewrite
.pSub
= *ppSub
;
661 sRewrite
.pWin
= pWin
;
663 sWalker
.pParse
= pParse
;
664 sWalker
.xExprCallback
= selectWindowRewriteExprCb
;
665 sWalker
.xSelectCallback
= selectWindowRewriteSelectCb
;
666 sWalker
.u
.pRewrite
= &sRewrite
;
668 (void)sqlite3WalkExprList(&sWalker
, pEList
);
670 *ppSub
= sRewrite
.pSub
;
674 ** Append a copy of each expression in expression-list pAppend to
675 ** expression list pList. Return a pointer to the result list.
677 static ExprList
*exprListAppendList(
678 Parse
*pParse
, /* Parsing context */
679 ExprList
*pList
, /* List to which to append. Might be NULL */
680 ExprList
*pAppend
/* List of values to append. Might be NULL */
684 int nInit
= pList
? pList
->nExpr
: 0;
685 for(i
=0; i
<pAppend
->nExpr
; i
++){
686 Expr
*pDup
= sqlite3ExprDup(pParse
->db
, pAppend
->a
[i
].pExpr
, 0);
687 pList
= sqlite3ExprListAppend(pParse
, pList
, pDup
);
688 if( pList
) pList
->a
[nInit
+i
].sortOrder
= pAppend
->a
[i
].sortOrder
;
695 ** If the SELECT statement passed as the second argument does not invoke
696 ** any SQL window functions, this function is a no-op. Otherwise, it
697 ** rewrites the SELECT statement so that window function xStep functions
698 ** are invoked in the correct order as described under "SELECT REWRITING"
699 ** at the top of this file.
701 int sqlite3WindowRewrite(Parse
*pParse
, Select
*p
){
704 Vdbe
*v
= sqlite3GetVdbe(pParse
);
705 sqlite3
*db
= pParse
->db
;
706 Select
*pSub
= 0; /* The subquery */
707 SrcList
*pSrc
= p
->pSrc
;
708 Expr
*pWhere
= p
->pWhere
;
709 ExprList
*pGroupBy
= p
->pGroupBy
;
710 Expr
*pHaving
= p
->pHaving
;
713 ExprList
*pSublist
= 0; /* Expression list for sub-query */
714 Window
*pMWin
= p
->pWin
; /* Master window object */
715 Window
*pWin
; /* Window object iterator */
722 /* Create the ORDER BY clause for the sub-select. This is the concatenation
723 ** of the window PARTITION and ORDER BY clauses. Then, if this makes it
724 ** redundant, remove the ORDER BY from the parent SELECT. */
725 pSort
= sqlite3ExprListDup(db
, pMWin
->pPartition
, 0);
726 pSort
= exprListAppendList(pParse
, pSort
, pMWin
->pOrderBy
);
727 if( pSort
&& p
->pOrderBy
){
728 if( sqlite3ExprListCompare(pSort
, p
->pOrderBy
, -1)==0 ){
729 sqlite3ExprListDelete(db
, p
->pOrderBy
);
734 /* Assign a cursor number for the ephemeral table used to buffer rows.
735 ** The OpenEphemeral instruction is coded later, after it is known how
736 ** many columns the table will have. */
737 pMWin
->iEphCsr
= pParse
->nTab
++;
739 selectWindowRewriteEList(pParse
, pMWin
, p
->pEList
, &pSublist
);
740 selectWindowRewriteEList(pParse
, pMWin
, p
->pOrderBy
, &pSublist
);
741 pMWin
->nBufferCol
= (pSublist
? pSublist
->nExpr
: 0);
743 /* Append the PARTITION BY and ORDER BY expressions to the to the
744 ** sub-select expression list. They are required to figure out where
745 ** boundaries for partitions and sets of peer rows lie. */
746 pSublist
= exprListAppendList(pParse
, pSublist
, pMWin
->pPartition
);
747 pSublist
= exprListAppendList(pParse
, pSublist
, pMWin
->pOrderBy
);
749 /* Append the arguments passed to each window function to the
750 ** sub-select expression list. Also allocate two registers for each
751 ** window function - one for the accumulator, another for interim
753 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
754 pWin
->iArgCol
= (pSublist
? pSublist
->nExpr
: 0);
755 pSublist
= exprListAppendList(pParse
, pSublist
, pWin
->pOwner
->x
.pList
);
757 Expr
*pFilter
= sqlite3ExprDup(db
, pWin
->pFilter
, 0);
758 pSublist
= sqlite3ExprListAppend(pParse
, pSublist
, pFilter
);
760 pWin
->regAccum
= ++pParse
->nMem
;
761 pWin
->regResult
= ++pParse
->nMem
;
762 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regAccum
);
765 /* If there is no ORDER BY or PARTITION BY clause, and the window
766 ** function accepts zero arguments, and there are no other columns
767 ** selected (e.g. "SELECT row_number() OVER () FROM t1"), it is possible
768 ** that pSublist is still NULL here. Add a constant expression here to
769 ** keep everything legal in this case.
772 pSublist
= sqlite3ExprListAppend(pParse
, 0,
773 sqlite3ExprAlloc(db
, TK_INTEGER
, &sqlite3IntTokens
[0], 0)
777 pSub
= sqlite3SelectNew(
778 pParse
, pSublist
, pSrc
, pWhere
, pGroupBy
, pHaving
, pSort
, 0, 0
780 p
->pSrc
= sqlite3SrcListAppend(db
, 0, 0, 0);
781 assert( p
->pSrc
|| db
->mallocFailed
);
783 p
->pSrc
->a
[0].pSelect
= pSub
;
784 sqlite3SrcListAssignCursors(pParse
, p
->pSrc
);
785 if( sqlite3ExpandSubquery(pParse
, &p
->pSrc
->a
[0]) ){
788 pSub
->selFlags
|= SF_Expanded
;
789 p
->selFlags
&= ~SF_Aggregate
;
790 sqlite3SelectPrep(pParse
, pSub
, 0);
793 sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, pMWin
->iEphCsr
, pSublist
->nExpr
);
795 sqlite3SelectDelete(db
, pSub
);
797 if( db
->mallocFailed
) rc
= SQLITE_NOMEM
;
804 ** Free the Window object passed as the second argument.
806 void sqlite3WindowDelete(sqlite3
*db
, Window
*p
){
808 sqlite3ExprDelete(db
, p
->pFilter
);
809 sqlite3ExprListDelete(db
, p
->pPartition
);
810 sqlite3ExprListDelete(db
, p
->pOrderBy
);
811 sqlite3ExprDelete(db
, p
->pEnd
);
812 sqlite3ExprDelete(db
, p
->pStart
);
813 sqlite3DbFree(db
, p
->zName
);
814 sqlite3DbFree(db
, p
);
819 ** Free the linked list of Window objects starting at the second argument.
821 void sqlite3WindowListDelete(sqlite3
*db
, Window
*p
){
823 Window
*pNext
= p
->pNextWin
;
824 sqlite3WindowDelete(db
, p
);
830 ** The argument expression is an PRECEDING or FOLLOWING offset. The
831 ** value should be a non-negative integer. If the value is not a
832 ** constant, change it to NULL. The fact that it is then a non-negative
833 ** integer will be caught later. But it is important not to leave
834 ** variable values in the expression tree.
836 static Expr
*sqlite3WindowOffsetExpr(Parse
*pParse
, Expr
*pExpr
){
837 if( 0==sqlite3ExprIsConstant(pExpr
) ){
838 sqlite3ExprDelete(pParse
->db
, pExpr
);
839 pExpr
= sqlite3ExprAlloc(pParse
->db
, TK_NULL
, 0, 0);
845 ** Allocate and return a new Window object describing a Window Definition.
847 Window
*sqlite3WindowAlloc(
848 Parse
*pParse
, /* Parsing context */
849 int eType
, /* Frame type. TK_RANGE or TK_ROWS */
850 int eStart
, /* Start type: CURRENT, PRECEDING, FOLLOWING, UNBOUNDED */
851 Expr
*pStart
, /* Start window size if TK_PRECEDING or FOLLOWING */
852 int eEnd
, /* End type: CURRENT, FOLLOWING, TK_UNBOUNDED, PRECEDING */
853 Expr
*pEnd
/* End window size if TK_FOLLOWING or PRECEDING */
857 /* Parser assures the following: */
858 assert( eType
==TK_RANGE
|| eType
==TK_ROWS
);
859 assert( eStart
==TK_CURRENT
|| eStart
==TK_PRECEDING
860 || eStart
==TK_UNBOUNDED
|| eStart
==TK_FOLLOWING
);
861 assert( eEnd
==TK_CURRENT
|| eEnd
==TK_FOLLOWING
862 || eEnd
==TK_UNBOUNDED
|| eEnd
==TK_PRECEDING
);
863 assert( (eStart
==TK_PRECEDING
|| eStart
==TK_FOLLOWING
)==(pStart
!=0) );
864 assert( (eEnd
==TK_FOLLOWING
|| eEnd
==TK_PRECEDING
)==(pEnd
!=0) );
867 /* If a frame is declared "RANGE" (not "ROWS"), then it may not use
868 ** either "<expr> PRECEDING" or "<expr> FOLLOWING".
870 if( eType
==TK_RANGE
&& (pStart
!=0 || pEnd
!=0) ){
871 sqlite3ErrorMsg(pParse
, "RANGE must use only UNBOUNDED or CURRENT ROW");
876 ** starting boundary type may not occur earlier in the following list than
877 ** the ending boundary type:
879 ** UNBOUNDED PRECEDING
883 ** UNBOUNDED FOLLOWING
885 ** The parser ensures that "UNBOUNDED PRECEDING" cannot be used as an ending
886 ** boundary, and than "UNBOUNDED FOLLOWING" cannot be used as a starting
889 if( (eStart
==TK_CURRENT
&& eEnd
==TK_PRECEDING
)
890 || (eStart
==TK_FOLLOWING
&& (eEnd
==TK_PRECEDING
|| eEnd
==TK_CURRENT
))
892 sqlite3ErrorMsg(pParse
, "unsupported frame delimiter for ROWS");
896 pWin
= (Window
*)sqlite3DbMallocZero(pParse
->db
, sizeof(Window
));
897 if( pWin
==0 ) goto windowAllocErr
;
899 pWin
->eStart
= eStart
;
901 pWin
->pEnd
= sqlite3WindowOffsetExpr(pParse
, pEnd
);
902 pWin
->pStart
= sqlite3WindowOffsetExpr(pParse
, pStart
);
906 sqlite3ExprDelete(pParse
->db
, pEnd
);
907 sqlite3ExprDelete(pParse
->db
, pStart
);
912 ** Attach window object pWin to expression p.
914 void sqlite3WindowAttach(Parse
*pParse
, Expr
*p
, Window
*pWin
){
919 if( p
->flags
& EP_Distinct
){
920 sqlite3ErrorMsg(pParse
,
921 "DISTINCT is not supported for window functions");
925 sqlite3WindowDelete(pParse
->db
, pWin
);
930 ** Return 0 if the two window objects are identical, or non-zero otherwise.
931 ** Identical window objects can be processed in a single scan.
933 int sqlite3WindowCompare(Parse
*pParse
, Window
*p1
, Window
*p2
){
934 if( p1
->eType
!=p2
->eType
) return 1;
935 if( p1
->eStart
!=p2
->eStart
) return 1;
936 if( p1
->eEnd
!=p2
->eEnd
) return 1;
937 if( sqlite3ExprCompare(pParse
, p1
->pStart
, p2
->pStart
, -1) ) return 1;
938 if( sqlite3ExprCompare(pParse
, p1
->pEnd
, p2
->pEnd
, -1) ) return 1;
939 if( sqlite3ExprListCompare(p1
->pPartition
, p2
->pPartition
, -1) ) return 1;
940 if( sqlite3ExprListCompare(p1
->pOrderBy
, p2
->pOrderBy
, -1) ) return 1;
946 ** This is called by code in select.c before it calls sqlite3WhereBegin()
947 ** to begin iterating through the sub-query results. It is used to allocate
948 ** and initialize registers and cursors used by sqlite3WindowCodeStep().
950 void sqlite3WindowCodeInit(Parse
*pParse
, Window
*pMWin
){
952 Vdbe
*v
= sqlite3GetVdbe(pParse
);
953 int nPart
= (pMWin
->pPartition
? pMWin
->pPartition
->nExpr
: 0);
954 nPart
+= (pMWin
->pOrderBy
? pMWin
->pOrderBy
->nExpr
: 0);
956 pMWin
->regPart
= pParse
->nMem
+1;
957 pParse
->nMem
+= nPart
;
958 sqlite3VdbeAddOp3(v
, OP_Null
, 0, pMWin
->regPart
, pMWin
->regPart
+nPart
-1);
961 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
962 FuncDef
*p
= pWin
->pFunc
;
963 if( (p
->funcFlags
& SQLITE_FUNC_MINMAX
) && pWin
->eStart
!=TK_UNBOUNDED
){
964 /* The inline versions of min() and max() require a single ephemeral
965 ** table and 3 registers. The registers are used as follows:
967 ** regApp+0: slot to copy min()/max() argument to for MakeRecord
968 ** regApp+1: integer value used to ensure keys are unique
969 ** regApp+2: output of MakeRecord
971 ExprList
*pList
= pWin
->pOwner
->x
.pList
;
972 KeyInfo
*pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
, pList
, 0, 0);
973 pWin
->csrApp
= pParse
->nTab
++;
974 pWin
->regApp
= pParse
->nMem
+1;
976 if( pKeyInfo
&& pWin
->pFunc
->zName
[1]=='i' ){
977 assert( pKeyInfo
->aSortOrder
[0]==0 );
978 pKeyInfo
->aSortOrder
[0] = 1;
980 sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, pWin
->csrApp
, 2);
981 sqlite3VdbeAppendP4(v
, pKeyInfo
, P4_KEYINFO
);
982 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, pWin
->regApp
+1);
984 else if( p
->xSFunc
==nth_valueStepFunc
|| p
->xSFunc
==first_valueStepFunc
){
985 /* Allocate two registers at pWin->regApp. These will be used to
986 ** store the start and end index of the current frame. */
987 assert( pMWin
->iEphCsr
);
988 pWin
->regApp
= pParse
->nMem
+1;
989 pWin
->csrApp
= pParse
->nTab
++;
991 sqlite3VdbeAddOp2(v
, OP_OpenDup
, pWin
->csrApp
, pMWin
->iEphCsr
);
993 else if( p
->xSFunc
==leadStepFunc
|| p
->xSFunc
==lagStepFunc
){
994 assert( pMWin
->iEphCsr
);
995 pWin
->csrApp
= pParse
->nTab
++;
996 sqlite3VdbeAddOp2(v
, OP_OpenDup
, pWin
->csrApp
, pMWin
->iEphCsr
);
1002 ** A "PRECEDING <expr>" (bEnd==0) or "FOLLOWING <expr>" (bEnd==1) has just
1003 ** been evaluated and the result left in register reg. This function generates
1004 ** VM code to check that the value is a non-negative integer and throws
1005 ** an exception if it is not.
1007 static void windowCheckFrameOffset(Parse
*pParse
, int reg
, int bEnd
){
1008 static const char *azErr
[] = {
1009 "frame starting offset must be a non-negative integer",
1010 "frame ending offset must be a non-negative integer"
1012 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1013 int regZero
= sqlite3GetTempReg(pParse
);
1014 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, regZero
);
1015 sqlite3VdbeAddOp2(v
, OP_MustBeInt
, reg
, sqlite3VdbeCurrentAddr(v
)+2);
1017 sqlite3VdbeAddOp3(v
, OP_Ge
, regZero
, sqlite3VdbeCurrentAddr(v
)+2, reg
);
1019 sqlite3VdbeAddOp2(v
, OP_Halt
, SQLITE_ERROR
, OE_Abort
);
1020 sqlite3VdbeAppendP4(v
, (void*)azErr
[bEnd
], P4_STATIC
);
1021 sqlite3ReleaseTempReg(pParse
, regZero
);
1025 ** Return the number of arguments passed to the window-function associated
1026 ** with the object passed as the only argument to this function.
1028 static int windowArgCount(Window
*pWin
){
1029 ExprList
*pList
= pWin
->pOwner
->x
.pList
;
1030 return (pList
? pList
->nExpr
: 0);
1034 ** Generate VM code to invoke either xStep() (if bInverse is 0) or
1035 ** xInverse (if bInverse is non-zero) for each window function in the
1036 ** linked list starting at pMWin. Or, for built-in window functions
1037 ** that do not use the standard function API, generate the required
1040 ** If argument csr is greater than or equal to 0, then argument reg is
1041 ** the first register in an array of registers guaranteed to be large
1042 ** enough to hold the array of arguments for each function. In this case
1043 ** the arguments are extracted from the current row of csr into the
1044 ** array of registers before invoking OP_AggStep or OP_AggInverse
1046 ** Or, if csr is less than zero, then the array of registers at reg is
1047 ** already populated with all columns from the current row of the sub-query.
1049 ** If argument regPartSize is non-zero, then it is a register containing the
1050 ** number of rows in the current partition.
1052 static void windowAggStep(
1054 Window
*pMWin
, /* Linked list of window functions */
1055 int csr
, /* Read arguments from this cursor */
1056 int bInverse
, /* True to invoke xInverse instead of xStep */
1057 int reg
, /* Array of registers */
1058 int regPartSize
/* Register containing size of partition */
1060 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1062 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
1063 int flags
= pWin
->pFunc
->funcFlags
;
1065 int nArg
= windowArgCount(pWin
);
1069 for(i
=0; i
<nArg
; i
++){
1070 sqlite3VdbeAddOp3(v
, OP_Column
, csr
, pWin
->iArgCol
+i
, reg
+i
);
1073 if( flags
& SQLITE_FUNC_WINDOW_SIZE
){
1075 regArg
= regPartSize
;
1077 sqlite3VdbeAddOp2(v
, OP_SCopy
, regPartSize
, reg
+nArg
);
1082 assert( !(flags
& SQLITE_FUNC_WINDOW_SIZE
) );
1083 regArg
= reg
+ pWin
->iArgCol
;
1086 if( (pWin
->pFunc
->funcFlags
& SQLITE_FUNC_MINMAX
)
1087 && pWin
->eStart
!=TK_UNBOUNDED
1089 int addrIsNull
= sqlite3VdbeAddOp1(v
, OP_IsNull
, regArg
);
1092 sqlite3VdbeAddOp2(v
, OP_AddImm
, pWin
->regApp
+1, 1);
1093 sqlite3VdbeAddOp2(v
, OP_SCopy
, regArg
, pWin
->regApp
);
1094 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, pWin
->regApp
, 2, pWin
->regApp
+2);
1095 sqlite3VdbeAddOp2(v
, OP_IdxInsert
, pWin
->csrApp
, pWin
->regApp
+2);
1097 sqlite3VdbeAddOp4Int(v
, OP_SeekGE
, pWin
->csrApp
, 0, regArg
, 1);
1099 sqlite3VdbeAddOp1(v
, OP_Delete
, pWin
->csrApp
);
1100 sqlite3VdbeJumpHere(v
, sqlite3VdbeCurrentAddr(v
)-2);
1102 sqlite3VdbeJumpHere(v
, addrIsNull
);
1103 }else if( pWin
->regApp
){
1104 assert( pWin
->pFunc
->xSFunc
==nth_valueStepFunc
1105 || pWin
->pFunc
->xSFunc
==first_valueStepFunc
1107 assert( bInverse
==0 || bInverse
==1 );
1108 sqlite3VdbeAddOp2(v
, OP_AddImm
, pWin
->regApp
+1-bInverse
, 1);
1109 }else if( pWin
->pFunc
->xSFunc
==leadStepFunc
1110 || pWin
->pFunc
->xSFunc
==lagStepFunc
1115 if( pWin
->pFilter
){
1117 assert( nArg
==pWin
->pOwner
->x
.pList
->nExpr
);
1119 regTmp
= sqlite3GetTempReg(pParse
);
1120 sqlite3VdbeAddOp3(v
, OP_Column
, csr
, pWin
->iArgCol
+nArg
,regTmp
);
1122 regTmp
= regArg
+ nArg
;
1124 addrIf
= sqlite3VdbeAddOp3(v
, OP_IfNot
, regTmp
, 0, 1);
1127 sqlite3ReleaseTempReg(pParse
, regTmp
);
1130 if( pWin
->pFunc
->funcFlags
& SQLITE_FUNC_NEEDCOLL
){
1132 pColl
= sqlite3ExprNNCollSeq(pParse
, pWin
->pOwner
->x
.pList
->a
[0].pExpr
);
1133 sqlite3VdbeAddOp4(v
, OP_CollSeq
, 0,0,0, (const char*)pColl
, P4_COLLSEQ
);
1135 sqlite3VdbeAddOp3(v
, bInverse
? OP_AggInverse
: OP_AggStep
,
1136 bInverse
, regArg
, pWin
->regAccum
);
1137 sqlite3VdbeAppendP4(v
, pWin
->pFunc
, P4_FUNCDEF
);
1138 sqlite3VdbeChangeP5(v
, (u8
)nArg
);
1139 if( addrIf
) sqlite3VdbeJumpHere(v
, addrIf
);
1145 ** Generate VM code to invoke either xValue() (bFinal==0) or xFinalize()
1146 ** (bFinal==1) for each window function in the linked list starting at
1147 ** pMWin. Or, for built-in window-functions that do not use the standard
1148 ** API, generate the equivalent VM code.
1150 static void windowAggFinal(Parse
*pParse
, Window
*pMWin
, int bFinal
){
1151 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1154 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
1155 if( (pWin
->pFunc
->funcFlags
& SQLITE_FUNC_MINMAX
)
1156 && pWin
->eStart
!=TK_UNBOUNDED
1158 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regResult
);
1159 sqlite3VdbeAddOp1(v
, OP_Last
, pWin
->csrApp
);
1161 sqlite3VdbeAddOp3(v
, OP_Column
, pWin
->csrApp
, 0, pWin
->regResult
);
1162 sqlite3VdbeJumpHere(v
, sqlite3VdbeCurrentAddr(v
)-2);
1164 sqlite3VdbeAddOp1(v
, OP_ResetSorter
, pWin
->csrApp
);
1166 }else if( pWin
->regApp
){
1169 sqlite3VdbeAddOp2(v
, OP_AggFinal
, pWin
->regAccum
, windowArgCount(pWin
));
1170 sqlite3VdbeAppendP4(v
, pWin
->pFunc
, P4_FUNCDEF
);
1171 sqlite3VdbeAddOp2(v
, OP_Copy
, pWin
->regAccum
, pWin
->regResult
);
1172 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regAccum
);
1174 sqlite3VdbeAddOp3(v
, OP_AggValue
, pWin
->regAccum
, windowArgCount(pWin
),
1176 sqlite3VdbeAppendP4(v
, pWin
->pFunc
, P4_FUNCDEF
);
1183 ** This function generates VM code to invoke the sub-routine at address
1184 ** lblFlushPart once for each partition with the entire partition cached in
1185 ** the Window.iEphCsr temp table.
1187 static void windowPartitionCache(
1189 Select
*p
, /* The rewritten SELECT statement */
1190 WhereInfo
*pWInfo
, /* WhereInfo to call WhereEnd() on */
1191 int regFlushPart
, /* Register to use with Gosub lblFlushPart */
1192 int lblFlushPart
, /* Subroutine to Gosub to */
1193 int *pRegSize
/* OUT: Register containing partition size */
1195 Window
*pMWin
= p
->pWin
;
1196 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1197 int iSubCsr
= p
->pSrc
->a
[0].iCursor
;
1198 int nSub
= p
->pSrc
->a
[0].pTab
->nCol
;
1201 int reg
= pParse
->nMem
+1;
1202 int regRecord
= reg
+nSub
;
1203 int regRowid
= regRecord
+1;
1205 *pRegSize
= regRowid
;
1206 pParse
->nMem
+= nSub
+ 2;
1208 /* Martial the row returned by the sub-select into an array of
1210 for(k
=0; k
<nSub
; k
++){
1211 sqlite3VdbeAddOp3(v
, OP_Column
, iSubCsr
, k
, reg
+k
);
1213 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, reg
, nSub
, regRecord
);
1215 /* Check if this is the start of a new partition. If so, call the
1216 ** flush_partition sub-routine. */
1217 if( pMWin
->pPartition
){
1219 ExprList
*pPart
= pMWin
->pPartition
;
1220 int nPart
= pPart
->nExpr
;
1221 int regNewPart
= reg
+ pMWin
->nBufferCol
;
1222 KeyInfo
*pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
, pPart
, 0, 0);
1224 addr
= sqlite3VdbeAddOp3(v
, OP_Compare
, regNewPart
, pMWin
->regPart
,nPart
);
1225 sqlite3VdbeAppendP4(v
, (void*)pKeyInfo
, P4_KEYINFO
);
1226 sqlite3VdbeAddOp3(v
, OP_Jump
, addr
+2, addr
+4, addr
+2);
1228 sqlite3VdbeAddOp3(v
, OP_Copy
, regNewPart
, pMWin
->regPart
, nPart
-1);
1229 sqlite3VdbeAddOp2(v
, OP_Gosub
, regFlushPart
, lblFlushPart
);
1232 /* Buffer the current row in the ephemeral table. */
1233 sqlite3VdbeAddOp2(v
, OP_NewRowid
, pMWin
->iEphCsr
, regRowid
);
1234 sqlite3VdbeAddOp3(v
, OP_Insert
, pMWin
->iEphCsr
, regRecord
, regRowid
);
1236 /* End of the input loop */
1237 sqlite3WhereEnd(pWInfo
);
1239 /* Invoke "flush_partition" to deal with the final (or only) partition */
1240 sqlite3VdbeAddOp2(v
, OP_Gosub
, regFlushPart
, lblFlushPart
);
1244 ** Invoke the sub-routine at regGosub (generated by code in select.c) to
1245 ** return the current row of Window.iEphCsr. If all window functions are
1246 ** aggregate window functions that use the standard API, a single
1247 ** OP_Gosub instruction is all that this routine generates. Extra VM code
1248 ** for per-row processing is only generated for the following built-in window
1256 static void windowReturnOneRow(
1262 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1264 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
1265 FuncDef
*pFunc
= pWin
->pFunc
;
1266 if( pFunc
->xSFunc
==nth_valueStepFunc
1267 || pFunc
->xSFunc
==first_valueStepFunc
1269 int csr
= pWin
->csrApp
;
1270 int lbl
= sqlite3VdbeMakeLabel(v
);
1271 int tmpReg
= sqlite3GetTempReg(pParse
);
1272 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regResult
);
1274 if( pFunc
->xSFunc
==nth_valueStepFunc
){
1275 sqlite3VdbeAddOp3(v
, OP_Column
, pMWin
->iEphCsr
, pWin
->iArgCol
+1,tmpReg
);
1277 sqlite3VdbeAddOp2(v
, OP_Integer
, 1, tmpReg
);
1279 sqlite3VdbeAddOp3(v
, OP_Add
, tmpReg
, pWin
->regApp
, tmpReg
);
1280 sqlite3VdbeAddOp3(v
, OP_Gt
, pWin
->regApp
+1, lbl
, tmpReg
);
1282 sqlite3VdbeAddOp3(v
, OP_SeekRowid
, csr
, lbl
, tmpReg
);
1284 sqlite3VdbeAddOp3(v
, OP_Column
, csr
, pWin
->iArgCol
, pWin
->regResult
);
1285 sqlite3VdbeResolveLabel(v
, lbl
);
1286 sqlite3ReleaseTempReg(pParse
, tmpReg
);
1288 else if( pFunc
->xSFunc
==leadStepFunc
|| pFunc
->xSFunc
==lagStepFunc
){
1289 int nArg
= pWin
->pOwner
->x
.pList
->nExpr
;
1290 int iEph
= pMWin
->iEphCsr
;
1291 int csr
= pWin
->csrApp
;
1292 int lbl
= sqlite3VdbeMakeLabel(v
);
1293 int tmpReg
= sqlite3GetTempReg(pParse
);
1296 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regResult
);
1298 sqlite3VdbeAddOp3(v
, OP_Column
, iEph
, pWin
->iArgCol
+2, pWin
->regResult
);
1300 sqlite3VdbeAddOp2(v
, OP_Rowid
, iEph
, tmpReg
);
1302 int val
= (pFunc
->xSFunc
==leadStepFunc
? 1 : -1);
1303 sqlite3VdbeAddOp2(v
, OP_AddImm
, tmpReg
, val
);
1305 int op
= (pFunc
->xSFunc
==leadStepFunc
? OP_Add
: OP_Subtract
);
1306 int tmpReg2
= sqlite3GetTempReg(pParse
);
1307 sqlite3VdbeAddOp3(v
, OP_Column
, iEph
, pWin
->iArgCol
+1, tmpReg2
);
1308 sqlite3VdbeAddOp3(v
, op
, tmpReg2
, tmpReg
, tmpReg
);
1309 sqlite3ReleaseTempReg(pParse
, tmpReg2
);
1312 sqlite3VdbeAddOp3(v
, OP_SeekRowid
, csr
, lbl
, tmpReg
);
1314 sqlite3VdbeAddOp3(v
, OP_Column
, csr
, pWin
->iArgCol
, pWin
->regResult
);
1315 sqlite3VdbeResolveLabel(v
, lbl
);
1316 sqlite3ReleaseTempReg(pParse
, tmpReg
);
1319 sqlite3VdbeAddOp2(v
, OP_Gosub
, regGosub
, addrGosub
);
1323 ** Invoke the code generated by windowReturnOneRow() and, optionally, the
1324 ** xInverse() function for each window function, for one or more rows
1325 ** from the Window.iEphCsr temp table. This routine generates VM code
1328 ** while( regCtr>0 ){
1330 ** windowReturnOneRow()
1334 ** Next (Window.iEphCsr)
1337 static void windowReturnRows(
1339 Window
*pMWin
, /* List of window functions */
1340 int regCtr
, /* Register containing number of rows */
1341 int regGosub
, /* Register for Gosub addrGosub */
1342 int addrGosub
, /* Address of sub-routine for ReturnOneRow */
1343 int regInvArg
, /* Array of registers for xInverse args */
1344 int regInvSize
/* Register containing size of partition */
1347 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1348 windowAggFinal(pParse
, pMWin
, 0);
1349 addr
= sqlite3VdbeAddOp3(v
, OP_IfPos
, regCtr
, sqlite3VdbeCurrentAddr(v
)+2 ,1);
1351 sqlite3VdbeAddOp2(v
, OP_Goto
, 0, 0);
1352 windowReturnOneRow(pParse
, pMWin
, regGosub
, addrGosub
);
1354 windowAggStep(pParse
, pMWin
, pMWin
->iEphCsr
, 1, regInvArg
, regInvSize
);
1356 sqlite3VdbeAddOp2(v
, OP_Next
, pMWin
->iEphCsr
, addr
);
1358 sqlite3VdbeJumpHere(v
, addr
+1); /* The OP_Goto */
1362 ** Generate code to set the accumulator register for each window function
1363 ** in the linked list passed as the second argument to NULL. And perform
1364 ** any equivalent initialization required by any built-in window functions
1367 static int windowInitAccum(Parse
*pParse
, Window
*pMWin
){
1368 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1372 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
1373 FuncDef
*pFunc
= pWin
->pFunc
;
1374 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regAccum
);
1375 nArg
= MAX(nArg
, windowArgCount(pWin
));
1376 if( pFunc
->xSFunc
==nth_valueStepFunc
1377 || pFunc
->xSFunc
==first_valueStepFunc
1379 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, pWin
->regApp
);
1380 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, pWin
->regApp
+1);
1383 if( (pFunc
->funcFlags
& SQLITE_FUNC_MINMAX
) && pWin
->csrApp
){
1384 assert( pWin
->eStart
!=TK_UNBOUNDED
);
1385 sqlite3VdbeAddOp1(v
, OP_ResetSorter
, pWin
->csrApp
);
1386 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, pWin
->regApp
+1);
1389 regArg
= pParse
->nMem
+1;
1390 pParse
->nMem
+= nArg
;
1396 ** This function does the work of sqlite3WindowCodeStep() for all "ROWS"
1397 ** window frame types except for "BETWEEN UNBOUNDED PRECEDING AND CURRENT
1398 ** ROW". Pseudo-code for each follows.
1400 ** ROWS BETWEEN <expr1> PRECEDING AND <expr2> FOLLOWING
1403 ** if( new partition ){
1404 ** Gosub flush_partition
1406 ** Insert (record in eph-table)
1407 ** sqlite3WhereEnd()
1408 ** Gosub flush_partition
1412 ** OpenDup (iEphCsr -> csrStart)
1413 ** OpenDup (iEphCsr -> csrEnd)
1415 ** regStart = <expr1> // PRECEDING expression
1416 ** regEnd = <expr2> // FOLLOWING expression
1417 ** if( regStart<0 || regEnd<0 ){ error! }
1418 ** Rewind (csr,csrStart,csrEnd) // if EOF goto flush_partition_done
1419 ** Next(csrEnd) // if EOF skip Aggstep
1421 ** if( (regEnd--)<=0 ){
1422 ** AggFinal (xValue)
1424 ** Next(csr) // if EOF goto flush_partition_done
1425 ** if( (regStart--)<=0 ){
1426 ** AggInverse (csrStart)
1430 ** flush_partition_done:
1431 ** ResetSorter (csr)
1434 ** ROWS BETWEEN <expr> PRECEDING AND CURRENT ROW
1435 ** ROWS BETWEEN CURRENT ROW AND <expr> FOLLOWING
1436 ** ROWS BETWEEN UNBOUNDED PRECEDING AND <expr> FOLLOWING
1438 ** These are similar to the above. For "CURRENT ROW", intialize the
1439 ** register to 0. For "UNBOUNDED PRECEDING" to infinity.
1441 ** ROWS BETWEEN <expr> PRECEDING AND UNBOUNDED FOLLOWING
1442 ** ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
1444 ** Rewind (csr,csrStart,csrEnd) // if EOF goto flush_partition_done
1446 ** Next(csrEnd) // Exit while(1) at EOF
1450 ** AggFinal (xValue)
1452 ** Next(csr) // if EOF goto flush_partition_done
1453 ** if( (regStart--)<=0 ){
1454 ** AggInverse (csrStart)
1459 ** For the "CURRENT ROW AND UNBOUNDED FOLLOWING" case, the final if()
1460 ** condition is always true (as if regStart were initialized to 0).
1462 ** RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
1464 ** This is the only RANGE case handled by this routine. It modifies the
1465 ** second while( 1 ) loop in "ROWS BETWEEN CURRENT ... UNBOUNDED..." to
1469 ** AggFinal (xValue)
1473 ** Next(csr) // if EOF goto flush_partition_done
1474 ** if( new peer ) break;
1476 ** while( (regPeer--)>0 ){
1477 ** AggInverse (csrStart)
1482 ** ROWS BETWEEN <expr> FOLLOWING AND <expr> FOLLOWING
1484 ** regEnd = regEnd - regStart
1485 ** Rewind (csr,csrStart,csrEnd) // if EOF goto flush_partition_done
1487 ** Next(csrEnd) // if EOF fall-through
1488 ** if( (regEnd--)<=0 ){
1489 ** if( (regStart--)<=0 ){
1490 ** AggFinal (xValue)
1492 ** Next(csr) // if EOF goto flush_partition_done
1494 ** AggInverse (csrStart)
1498 ** ROWS BETWEEN <expr> PRECEDING AND <expr> PRECEDING
1500 ** Replace the bit after "Rewind" in the above with:
1502 ** if( (regEnd--)<=0 ){
1506 ** AggFinal (xValue)
1508 ** Next(csr) // if EOF goto flush_partition_done
1509 ** if( (regStart--)<=0 ){
1510 ** AggInverse (csr2)
1515 static void windowCodeRowExprStep(
1522 Window
*pMWin
= p
->pWin
;
1523 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1524 int regFlushPart
; /* Register for "Gosub flush_partition" */
1525 int lblFlushPart
; /* Label for "Gosub flush_partition" */
1526 int lblFlushDone
; /* Label for "Gosub flush_partition_done" */
1530 int csrStart
= pParse
->nTab
++;
1531 int csrEnd
= pParse
->nTab
++;
1532 int regStart
; /* Value of <expr> PRECEDING */
1533 int regEnd
; /* Value of <expr> FOLLOWING */
1540 assert( pMWin
->eStart
==TK_PRECEDING
1541 || pMWin
->eStart
==TK_CURRENT
1542 || pMWin
->eStart
==TK_FOLLOWING
1543 || pMWin
->eStart
==TK_UNBOUNDED
1545 assert( pMWin
->eEnd
==TK_FOLLOWING
1546 || pMWin
->eEnd
==TK_CURRENT
1547 || pMWin
->eEnd
==TK_UNBOUNDED
1548 || pMWin
->eEnd
==TK_PRECEDING
1551 /* Allocate register and label for the "flush_partition" sub-routine. */
1552 regFlushPart
= ++pParse
->nMem
;
1553 lblFlushPart
= sqlite3VdbeMakeLabel(v
);
1554 lblFlushDone
= sqlite3VdbeMakeLabel(v
);
1556 regStart
= ++pParse
->nMem
;
1557 regEnd
= ++pParse
->nMem
;
1559 windowPartitionCache(pParse
, p
, pWInfo
, regFlushPart
, lblFlushPart
, ®Size
);
1561 addrGoto
= sqlite3VdbeAddOp0(v
, OP_Goto
);
1563 /* Start of "flush_partition" */
1564 sqlite3VdbeResolveLabel(v
, lblFlushPart
);
1565 sqlite3VdbeAddOp2(v
, OP_Once
, 0, sqlite3VdbeCurrentAddr(v
)+3);
1567 sqlite3VdbeAddOp2(v
, OP_OpenDup
, csrStart
, pMWin
->iEphCsr
);
1568 sqlite3VdbeAddOp2(v
, OP_OpenDup
, csrEnd
, pMWin
->iEphCsr
);
1570 /* If either regStart or regEnd are not non-negative integers, throw
1572 if( pMWin
->pStart
){
1573 sqlite3ExprCode(pParse
, pMWin
->pStart
, regStart
);
1574 windowCheckFrameOffset(pParse
, regStart
, 0);
1577 sqlite3ExprCode(pParse
, pMWin
->pEnd
, regEnd
);
1578 windowCheckFrameOffset(pParse
, regEnd
, 1);
1581 /* If this is "ROWS <expr1> FOLLOWING AND ROWS <expr2> FOLLOWING", do:
1583 ** if( regEnd<regStart ){
1584 ** // The frame always consists of 0 rows
1585 ** regStart = regSize;
1587 ** regEnd = regEnd - regStart;
1589 if( pMWin
->pEnd
&& pMWin
->pStart
&& pMWin
->eStart
==TK_FOLLOWING
){
1590 assert( pMWin
->eEnd
==TK_FOLLOWING
);
1591 sqlite3VdbeAddOp3(v
, OP_Ge
, regStart
, sqlite3VdbeCurrentAddr(v
)+2, regEnd
);
1593 sqlite3VdbeAddOp2(v
, OP_Copy
, regSize
, regStart
);
1594 sqlite3VdbeAddOp3(v
, OP_Subtract
, regStart
, regEnd
, regEnd
);
1597 if( pMWin
->pEnd
&& pMWin
->pStart
&& pMWin
->eEnd
==TK_PRECEDING
){
1598 assert( pMWin
->eStart
==TK_PRECEDING
);
1599 sqlite3VdbeAddOp3(v
, OP_Le
, regStart
, sqlite3VdbeCurrentAddr(v
)+3, regEnd
);
1601 sqlite3VdbeAddOp2(v
, OP_Copy
, regSize
, regStart
);
1602 sqlite3VdbeAddOp2(v
, OP_Copy
, regSize
, regEnd
);
1605 /* Initialize the accumulator register for each window function to NULL */
1606 regArg
= windowInitAccum(pParse
, pMWin
);
1608 sqlite3VdbeAddOp2(v
, OP_Rewind
, pMWin
->iEphCsr
, lblFlushDone
);
1610 sqlite3VdbeAddOp2(v
, OP_Rewind
, csrStart
, lblFlushDone
);
1611 VdbeCoverageNeverTaken(v
);
1612 sqlite3VdbeChangeP5(v
, 1);
1613 sqlite3VdbeAddOp2(v
, OP_Rewind
, csrEnd
, lblFlushDone
);
1614 VdbeCoverageNeverTaken(v
);
1615 sqlite3VdbeChangeP5(v
, 1);
1617 /* Invoke AggStep function for each window function using the row that
1618 ** csrEnd currently points to. Or, if csrEnd is already at EOF,
1620 addrTop
= sqlite3VdbeCurrentAddr(v
);
1621 if( pMWin
->eEnd
==TK_PRECEDING
){
1622 addrIfPos1
= sqlite3VdbeAddOp3(v
, OP_IfPos
, regEnd
, 0 , 1);
1625 sqlite3VdbeAddOp2(v
, OP_Next
, csrEnd
, sqlite3VdbeCurrentAddr(v
)+2);
1627 addr
= sqlite3VdbeAddOp0(v
, OP_Goto
);
1628 windowAggStep(pParse
, pMWin
, csrEnd
, 0, regArg
, regSize
);
1629 if( pMWin
->eEnd
==TK_UNBOUNDED
){
1630 sqlite3VdbeAddOp2(v
, OP_Goto
, 0, addrTop
);
1631 sqlite3VdbeJumpHere(v
, addr
);
1632 addrTop
= sqlite3VdbeCurrentAddr(v
);
1634 sqlite3VdbeJumpHere(v
, addr
);
1635 if( pMWin
->eEnd
==TK_PRECEDING
){
1636 sqlite3VdbeJumpHere(v
, addrIfPos1
);
1640 if( pMWin
->eEnd
==TK_FOLLOWING
){
1641 addrIfPos1
= sqlite3VdbeAddOp3(v
, OP_IfPos
, regEnd
, 0 , 1);
1644 if( pMWin
->eStart
==TK_FOLLOWING
){
1645 addrIfPos2
= sqlite3VdbeAddOp3(v
, OP_IfPos
, regStart
, 0 , 1);
1648 windowAggFinal(pParse
, pMWin
, 0);
1649 windowReturnOneRow(pParse
, pMWin
, regGosub
, addrGosub
);
1650 sqlite3VdbeAddOp2(v
, OP_Next
, pMWin
->iEphCsr
, sqlite3VdbeCurrentAddr(v
)+2);
1652 sqlite3VdbeAddOp2(v
, OP_Goto
, 0, lblFlushDone
);
1653 if( pMWin
->eStart
==TK_FOLLOWING
){
1654 sqlite3VdbeJumpHere(v
, addrIfPos2
);
1657 if( pMWin
->eStart
==TK_CURRENT
1658 || pMWin
->eStart
==TK_PRECEDING
1659 || pMWin
->eStart
==TK_FOLLOWING
1661 int lblSkipInverse
= sqlite3VdbeMakeLabel(v
);;
1662 if( pMWin
->eStart
==TK_PRECEDING
){
1663 sqlite3VdbeAddOp3(v
, OP_IfPos
, regStart
, lblSkipInverse
, 1);
1666 if( pMWin
->eStart
==TK_FOLLOWING
){
1667 sqlite3VdbeAddOp2(v
, OP_Next
, csrStart
, sqlite3VdbeCurrentAddr(v
)+2);
1669 sqlite3VdbeAddOp2(v
, OP_Goto
, 0, lblSkipInverse
);
1671 sqlite3VdbeAddOp2(v
, OP_Next
, csrStart
, sqlite3VdbeCurrentAddr(v
)+1);
1674 windowAggStep(pParse
, pMWin
, csrStart
, 1, regArg
, regSize
);
1675 sqlite3VdbeResolveLabel(v
, lblSkipInverse
);
1677 if( pMWin
->eEnd
==TK_FOLLOWING
){
1678 sqlite3VdbeJumpHere(v
, addrIfPos1
);
1680 sqlite3VdbeAddOp2(v
, OP_Goto
, 0, addrTop
);
1682 /* flush_partition_done: */
1683 sqlite3VdbeResolveLabel(v
, lblFlushDone
);
1684 sqlite3VdbeAddOp1(v
, OP_ResetSorter
, pMWin
->iEphCsr
);
1685 sqlite3VdbeAddOp1(v
, OP_Return
, regFlushPart
);
1687 /* Jump to here to skip over flush_partition */
1688 sqlite3VdbeJumpHere(v
, addrGoto
);
1692 ** This function does the work of sqlite3WindowCodeStep() for cases that
1693 ** would normally be handled by windowCodeDefaultStep() when there are
1694 ** one or more built-in window-functions that require the entire partition
1695 ** to be cached in a temp table before any rows can be returned. Additionally.
1696 ** "RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING" is always handled by
1699 ** Pseudo-code corresponding to the VM code generated by this function
1700 ** for each type of window follows.
1702 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1706 ** OpenDup (iEphCsr -> csrLead)
1709 ** foreach row (csrLead){
1711 ** AggFinal (xValue)
1712 ** for(i=0; i<ctr; i++){
1718 ** AggStep (csrLead)
1722 ** AggFinal (xFinalize)
1723 ** for(i=0; i<ctr; i++){
1728 ** ResetSorter (csr)
1731 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1733 ** As above, except that the "if( new peer )" branch is always taken.
1735 ** RANGE BETWEEN CURRENT ROW AND CURRENT ROW
1737 ** As above, except that each of the for() loops becomes:
1739 ** for(i=0; i<ctr; i++){
1741 ** AggInverse (iEphCsr)
1745 ** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
1749 ** OpenDup (iEphCsr -> csrLead)
1751 ** foreach row (csrLead) {
1752 ** AggStep (csrLead)
1754 ** foreach row (iEphCsr) {
1758 ** RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
1762 ** OpenDup (iEphCsr -> csrLead)
1764 ** foreach row (csrLead){
1765 ** AggStep (csrLead)
1769 ** foreach row (csrLead){
1771 ** AggFinal (xValue)
1772 ** for(i=0; i<ctr; i++){
1774 ** AggInverse (iEphCsr)
1782 ** AggFinal (xFinalize)
1783 ** for(i=0; i<ctr; i++){
1788 ** ResetSorter (csr)
1791 static void windowCodeCacheStep(
1798 Window
*pMWin
= p
->pWin
;
1799 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1802 ExprList
*pPart
= pMWin
->pPartition
;
1803 ExprList
*pOrderBy
= pMWin
->pOrderBy
;
1804 int nPeer
= pOrderBy
? pOrderBy
->nExpr
: 0;
1807 int addrGoto
; /* Address of Goto used to jump flush_par.. */
1808 int addrNext
; /* Jump here for next iteration of loop */
1813 int regArg
; /* Register array to martial function args */
1816 int bReverse
= pMWin
->pOrderBy
&& pMWin
->eStart
==TK_CURRENT
1817 && pMWin
->eEnd
==TK_UNBOUNDED
;
1819 assert( (pMWin
->eStart
==TK_UNBOUNDED
&& pMWin
->eEnd
==TK_CURRENT
)
1820 || (pMWin
->eStart
==TK_UNBOUNDED
&& pMWin
->eEnd
==TK_UNBOUNDED
)
1821 || (pMWin
->eStart
==TK_CURRENT
&& pMWin
->eEnd
==TK_CURRENT
)
1822 || (pMWin
->eStart
==TK_CURRENT
&& pMWin
->eEnd
==TK_UNBOUNDED
)
1825 lblEmpty
= sqlite3VdbeMakeLabel(v
);
1826 regNewPeer
= pParse
->nMem
+1;
1827 pParse
->nMem
+= nPeer
;
1829 /* Allocate register and label for the "flush_partition" sub-routine. */
1830 regFlushPart
= ++pParse
->nMem
;
1831 lblFlushPart
= sqlite3VdbeMakeLabel(v
);
1833 csrLead
= pParse
->nTab
++;
1834 regCtr
= ++pParse
->nMem
;
1836 windowPartitionCache(pParse
, p
, pWInfo
, regFlushPart
, lblFlushPart
, ®Size
);
1837 addrGoto
= sqlite3VdbeAddOp0(v
, OP_Goto
);
1839 /* Start of "flush_partition" */
1840 sqlite3VdbeResolveLabel(v
, lblFlushPart
);
1841 sqlite3VdbeAddOp2(v
, OP_Once
, 0, sqlite3VdbeCurrentAddr(v
)+2);
1843 sqlite3VdbeAddOp2(v
, OP_OpenDup
, csrLead
, pMWin
->iEphCsr
);
1845 /* Initialize the accumulator register for each window function to NULL */
1846 regArg
= windowInitAccum(pParse
, pMWin
);
1848 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, regCtr
);
1849 sqlite3VdbeAddOp2(v
, OP_Rewind
, csrLead
, lblEmpty
);
1851 sqlite3VdbeAddOp2(v
, OP_Rewind
, pMWin
->iEphCsr
, lblEmpty
);
1852 VdbeCoverageNeverTaken(v
);
1855 int addr
= sqlite3VdbeCurrentAddr(v
);
1856 windowAggStep(pParse
, pMWin
, csrLead
, 0, regArg
, regSize
);
1857 sqlite3VdbeAddOp2(v
, OP_Next
, csrLead
, addr
);
1859 sqlite3VdbeAddOp2(v
, OP_Rewind
, csrLead
, lblEmpty
);
1860 VdbeCoverageNeverTaken(v
);
1862 addrNext
= sqlite3VdbeCurrentAddr(v
);
1864 if( pOrderBy
&& (pMWin
->eEnd
==TK_CURRENT
|| pMWin
->eStart
==TK_CURRENT
) ){
1865 int bCurrent
= (pMWin
->eStart
==TK_CURRENT
);
1866 int addrJump
= 0; /* Address of OP_Jump below */
1867 if( pMWin
->eType
==TK_RANGE
){
1868 int iOff
= pMWin
->nBufferCol
+ (pPart
? pPart
->nExpr
: 0);
1869 int regPeer
= pMWin
->regPart
+ (pPart
? pPart
->nExpr
: 0);
1870 KeyInfo
*pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
, pOrderBy
, 0, 0);
1871 for(k
=0; k
<nPeer
; k
++){
1872 sqlite3VdbeAddOp3(v
, OP_Column
, csrLead
, iOff
+k
, regNewPeer
+k
);
1874 addr
= sqlite3VdbeAddOp3(v
, OP_Compare
, regNewPeer
, regPeer
, nPeer
);
1875 sqlite3VdbeAppendP4(v
, (void*)pKeyInfo
, P4_KEYINFO
);
1876 addrJump
= sqlite3VdbeAddOp3(v
, OP_Jump
, addr
+2, 0, addr
+2);
1878 sqlite3VdbeAddOp3(v
, OP_Copy
, regNewPeer
, regPeer
, nPeer
-1);
1881 windowReturnRows(pParse
, pMWin
, regCtr
, regGosub
, addrGosub
,
1882 (bCurrent
? regArg
: 0), (bCurrent
? regSize
: 0)
1884 if( addrJump
) sqlite3VdbeJumpHere(v
, addrJump
);
1888 windowAggStep(pParse
, pMWin
, csrLead
, 0, regArg
, regSize
);
1890 sqlite3VdbeAddOp2(v
, OP_AddImm
, regCtr
, 1);
1891 sqlite3VdbeAddOp2(v
, OP_Next
, csrLead
, addrNext
);
1894 windowReturnRows(pParse
, pMWin
, regCtr
, regGosub
, addrGosub
, 0, 0);
1896 sqlite3VdbeResolveLabel(v
, lblEmpty
);
1897 sqlite3VdbeAddOp1(v
, OP_ResetSorter
, pMWin
->iEphCsr
);
1898 sqlite3VdbeAddOp1(v
, OP_Return
, regFlushPart
);
1900 /* Jump to here to skip over flush_partition */
1901 sqlite3VdbeJumpHere(v
, addrGoto
);
1906 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1909 ** if( new partition ){
1910 ** AggFinal (xFinalize)
1912 ** ResetSorter eph-table
1914 ** else if( new peer ){
1915 ** AggFinal (xValue)
1917 ** ResetSorter eph-table
1920 ** Insert (record into eph-table)
1921 ** sqlite3WhereEnd()
1922 ** AggFinal (xFinalize)
1925 ** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
1927 ** As above, except take no action for a "new peer". Invoke
1928 ** the sub-routine once only for each partition.
1930 ** RANGE BETWEEN CURRENT ROW AND CURRENT ROW
1932 ** As above, except that the "new peer" condition is handled in the
1933 ** same way as "new partition" (so there is no "else if" block).
1935 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1937 ** As above, except assume every row is a "new peer".
1939 static void windowCodeDefaultStep(
1946 Window
*pMWin
= p
->pWin
;
1947 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1949 int iSubCsr
= p
->pSrc
->a
[0].iCursor
;
1950 int nSub
= p
->pSrc
->a
[0].pTab
->nCol
;
1951 int reg
= pParse
->nMem
+1;
1952 int regRecord
= reg
+nSub
;
1953 int regRowid
= regRecord
+1;
1955 ExprList
*pPart
= pMWin
->pPartition
;
1956 ExprList
*pOrderBy
= pMWin
->pOrderBy
;
1958 assert( pMWin
->eType
==TK_RANGE
1959 || (pMWin
->eStart
==TK_UNBOUNDED
&& pMWin
->eEnd
==TK_CURRENT
)
1962 assert( (pMWin
->eStart
==TK_UNBOUNDED
&& pMWin
->eEnd
==TK_CURRENT
)
1963 || (pMWin
->eStart
==TK_UNBOUNDED
&& pMWin
->eEnd
==TK_UNBOUNDED
)
1964 || (pMWin
->eStart
==TK_CURRENT
&& pMWin
->eEnd
==TK_CURRENT
)
1965 || (pMWin
->eStart
==TK_CURRENT
&& pMWin
->eEnd
==TK_UNBOUNDED
&& !pOrderBy
)
1968 if( pMWin
->eEnd
==TK_UNBOUNDED
){
1972 pParse
->nMem
+= nSub
+ 2;
1974 /* Martial the row returned by the sub-select into an array of
1976 for(k
=0; k
<nSub
; k
++){
1977 sqlite3VdbeAddOp3(v
, OP_Column
, iSubCsr
, k
, reg
+k
);
1980 /* Check if this is the start of a new partition or peer group. */
1981 if( pPart
|| pOrderBy
){
1982 int nPart
= (pPart
? pPart
->nExpr
: 0);
1985 int nPeer
= (pOrderBy
? pOrderBy
->nExpr
: 0);
1988 int regNewPart
= reg
+ pMWin
->nBufferCol
;
1989 KeyInfo
*pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
, pPart
, 0, 0);
1990 addr
= sqlite3VdbeAddOp3(v
, OP_Compare
, regNewPart
, pMWin
->regPart
,nPart
);
1991 sqlite3VdbeAppendP4(v
, (void*)pKeyInfo
, P4_KEYINFO
);
1992 addrJump
= sqlite3VdbeAddOp3(v
, OP_Jump
, addr
+2, 0, addr
+2);
1994 windowAggFinal(pParse
, pMWin
, 1);
1996 addrGoto
= sqlite3VdbeAddOp0(v
, OP_Goto
);
2001 int regNewPeer
= reg
+ pMWin
->nBufferCol
+ nPart
;
2002 int regPeer
= pMWin
->regPart
+ nPart
;
2004 if( addrJump
) sqlite3VdbeJumpHere(v
, addrJump
);
2005 if( pMWin
->eType
==TK_RANGE
){
2006 KeyInfo
*pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
, pOrderBy
, 0, 0);
2007 addr
= sqlite3VdbeAddOp3(v
, OP_Compare
, regNewPeer
, regPeer
, nPeer
);
2008 sqlite3VdbeAppendP4(v
, (void*)pKeyInfo
, P4_KEYINFO
);
2009 addrJump
= sqlite3VdbeAddOp3(v
, OP_Jump
, addr
+2, 0, addr
+2);
2014 windowAggFinal(pParse
, pMWin
, pMWin
->eStart
==TK_CURRENT
);
2015 if( addrGoto
) sqlite3VdbeJumpHere(v
, addrGoto
);
2018 sqlite3VdbeAddOp2(v
, OP_Rewind
, pMWin
->iEphCsr
,sqlite3VdbeCurrentAddr(v
)+3);
2020 sqlite3VdbeAddOp2(v
, OP_Gosub
, regGosub
, addrGosub
);
2021 sqlite3VdbeAddOp2(v
, OP_Next
, pMWin
->iEphCsr
, sqlite3VdbeCurrentAddr(v
)-1);
2024 sqlite3VdbeAddOp1(v
, OP_ResetSorter
, pMWin
->iEphCsr
);
2026 v
, OP_Copy
, reg
+pMWin
->nBufferCol
, pMWin
->regPart
, nPart
+nPeer
-1
2029 if( addrJump
) sqlite3VdbeJumpHere(v
, addrJump
);
2032 /* Invoke step function for window functions */
2033 windowAggStep(pParse
, pMWin
, -1, 0, reg
, 0);
2035 /* Buffer the current row in the ephemeral table. */
2036 if( pMWin
->nBufferCol
>0 ){
2037 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, reg
, pMWin
->nBufferCol
, regRecord
);
2039 sqlite3VdbeAddOp2(v
, OP_Blob
, 0, regRecord
);
2040 sqlite3VdbeAppendP4(v
, (void*)"", 0);
2042 sqlite3VdbeAddOp2(v
, OP_NewRowid
, pMWin
->iEphCsr
, regRowid
);
2043 sqlite3VdbeAddOp3(v
, OP_Insert
, pMWin
->iEphCsr
, regRecord
, regRowid
);
2045 /* End the database scan loop. */
2046 sqlite3WhereEnd(pWInfo
);
2048 windowAggFinal(pParse
, pMWin
, 1);
2049 sqlite3VdbeAddOp2(v
, OP_Rewind
, pMWin
->iEphCsr
,sqlite3VdbeCurrentAddr(v
)+3);
2051 sqlite3VdbeAddOp2(v
, OP_Gosub
, regGosub
, addrGosub
);
2052 sqlite3VdbeAddOp2(v
, OP_Next
, pMWin
->iEphCsr
, sqlite3VdbeCurrentAddr(v
)-1);
2057 ** Allocate and return a duplicate of the Window object indicated by the
2058 ** third argument. Set the Window.pOwner field of the new object to
2061 Window
*sqlite3WindowDup(sqlite3
*db
, Expr
*pOwner
, Window
*p
){
2064 pNew
= sqlite3DbMallocZero(db
, sizeof(Window
));
2066 pNew
->zName
= sqlite3DbStrDup(db
, p
->zName
);
2067 pNew
->pFilter
= sqlite3ExprDup(db
, p
->pFilter
, 0);
2068 pNew
->pPartition
= sqlite3ExprListDup(db
, p
->pPartition
, 0);
2069 pNew
->pOrderBy
= sqlite3ExprListDup(db
, p
->pOrderBy
, 0);
2070 pNew
->eType
= p
->eType
;
2071 pNew
->eEnd
= p
->eEnd
;
2072 pNew
->eStart
= p
->eStart
;
2073 pNew
->pStart
= sqlite3ExprDup(db
, p
->pStart
, 0);
2074 pNew
->pEnd
= sqlite3ExprDup(db
, p
->pEnd
, 0);
2075 pNew
->pOwner
= pOwner
;
2082 ** Return a copy of the linked list of Window objects passed as the
2085 Window
*sqlite3WindowListDup(sqlite3
*db
, Window
*p
){
2088 Window
**pp
= &pRet
;
2090 for(pWin
=p
; pWin
; pWin
=pWin
->pNextWin
){
2091 *pp
= sqlite3WindowDup(db
, 0, pWin
);
2093 pp
= &((*pp
)->pNextWin
);
2100 ** sqlite3WhereBegin() has already been called for the SELECT statement
2101 ** passed as the second argument when this function is invoked. It generates
2102 ** code to populate the Window.regResult register for each window function and
2103 ** invoke the sub-routine at instruction addrGosub once for each row.
2104 ** This function calls sqlite3WhereEnd() before returning.
2106 void sqlite3WindowCodeStep(
2107 Parse
*pParse
, /* Parse context */
2108 Select
*p
, /* Rewritten SELECT statement */
2109 WhereInfo
*pWInfo
, /* Context returned by sqlite3WhereBegin() */
2110 int regGosub
, /* Register for OP_Gosub */
2111 int addrGosub
/* OP_Gosub here to return each row */
2113 Window
*pMWin
= p
->pWin
;
2115 /* There are three different functions that may be used to do the work
2116 ** of this one, depending on the window frame and the specific built-in
2117 ** window functions used (if any).
2119 ** windowCodeRowExprStep() handles all "ROWS" window frames, except for:
2121 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
2123 ** The exception is because windowCodeRowExprStep() implements all window
2124 ** frame types by caching the entire partition in a temp table, and
2125 ** "ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW" is easy enough to
2126 ** implement without such a cache.
2128 ** windowCodeCacheStep() is used for:
2130 ** RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
2132 ** It is also used for anything not handled by windowCodeRowExprStep()
2133 ** that invokes a built-in window function that requires the entire
2134 ** partition to be cached in a temp table before any rows are returned
2135 ** (e.g. nth_value() or percent_rank()).
2137 ** Finally, assuming there is no built-in window function that requires
2138 ** the partition to be cached, windowCodeDefaultStep() is used for:
2140 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
2141 ** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
2142 ** RANGE BETWEEN CURRENT ROW AND CURRENT ROW
2143 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
2145 ** windowCodeDefaultStep() is the only one of the three functions that
2146 ** does not cache each partition in a temp table before beginning to
2149 if( pMWin
->eType
==TK_ROWS
2150 && (pMWin
->eStart
!=TK_UNBOUNDED
||pMWin
->eEnd
!=TK_CURRENT
||!pMWin
->pOrderBy
)
2152 windowCodeRowExprStep(pParse
, p
, pWInfo
, regGosub
, addrGosub
);
2155 int bCache
= 0; /* True to use CacheStep() */
2157 if( pMWin
->eStart
==TK_CURRENT
&& pMWin
->eEnd
==TK_UNBOUNDED
){
2160 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
2161 FuncDef
*pFunc
= pWin
->pFunc
;
2162 if( (pFunc
->funcFlags
& SQLITE_FUNC_WINDOW_SIZE
)
2163 || (pFunc
->xSFunc
==nth_valueStepFunc
)
2164 || (pFunc
->xSFunc
==first_valueStepFunc
)
2165 || (pFunc
->xSFunc
==leadStepFunc
)
2166 || (pFunc
->xSFunc
==lagStepFunc
)
2174 /* Otherwise, call windowCodeDefaultStep(). */
2176 windowCodeCacheStep(pParse
, p
, pWInfo
, regGosub
, addrGosub
);
2178 windowCodeDefaultStep(pParse
, p
, pWInfo
, regGosub
, addrGosub
);
2183 #endif /* SQLITE_OMIT_WINDOWFUNC */