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().
177 static void dense_rankStepFunc(
178 sqlite3_context
*pCtx
,
180 sqlite3_value
**apArg
183 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
184 if( p
) p
->nStep
= 1;
186 static void dense_rankInvFunc(
187 sqlite3_context
*pCtx
,
189 sqlite3_value
**apArg
192 static void dense_rankValueFunc(sqlite3_context
*pCtx
){
194 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
200 sqlite3_result_int64(pCtx
, p
->nValue
);
205 ** Implementation of built-in window function rank().
207 static void rankStepFunc(
208 sqlite3_context
*pCtx
,
210 sqlite3_value
**apArg
213 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
217 p
->nValue
= p
->nStep
;
221 static void rankInvFunc(
222 sqlite3_context
*pCtx
,
224 sqlite3_value
**apArg
227 static void rankValueFunc(sqlite3_context
*pCtx
){
229 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
231 sqlite3_result_int64(pCtx
, p
->nValue
);
237 ** Implementation of built-in window function percent_rank().
239 static void percent_rankStepFunc(
240 sqlite3_context
*pCtx
,
242 sqlite3_value
**apArg
247 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
250 p
->nTotal
= sqlite3_value_int64(apArg
[0]);
254 p
->nValue
= p
->nStep
;
258 static void percent_rankInvFunc(
259 sqlite3_context
*pCtx
,
261 sqlite3_value
**apArg
264 static void percent_rankValueFunc(sqlite3_context
*pCtx
){
266 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
269 double r
= (double)(p
->nValue
-1) / (double)(p
->nTotal
-1);
270 sqlite3_result_double(pCtx
, r
);
272 sqlite3_result_double(pCtx
, 100.0);
278 static void cume_distStepFunc(
279 sqlite3_context
*pCtx
,
281 sqlite3_value
**apArg
286 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
289 p
->nTotal
= sqlite3_value_int64(apArg
[0]);
294 static void cume_distInvFunc(
295 sqlite3_context
*pCtx
,
297 sqlite3_value
**apArg
300 static void cume_distValueFunc(sqlite3_context
*pCtx
){
302 p
= (struct CallCount
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
303 if( p
&& p
->nTotal
){
304 double r
= (double)(p
->nStep
) / (double)(p
->nTotal
);
305 sqlite3_result_double(pCtx
, r
);
310 ** Context object for ntile() window function.
313 i64 nTotal
; /* Total rows in partition */
314 i64 nParam
; /* Parameter passed to ntile(N) */
315 i64 iRow
; /* Current row */
319 ** Implementation of ntile(). This assumes that the window frame has
322 ** ROWS UNBOUNDED PRECEDING AND CURRENT ROW
324 static void ntileStepFunc(
325 sqlite3_context
*pCtx
,
327 sqlite3_value
**apArg
331 p
= (struct NtileCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
334 p
->nParam
= sqlite3_value_int64(apArg
[0]);
335 p
->nTotal
= sqlite3_value_int64(apArg
[1]);
337 sqlite3_result_error(
338 pCtx
, "argument of ntile must be a positive integer", -1
345 static void ntileInvFunc(
346 sqlite3_context
*pCtx
,
348 sqlite3_value
**apArg
351 static void ntileValueFunc(sqlite3_context
*pCtx
){
353 p
= (struct NtileCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
354 if( p
&& p
->nParam
>0 ){
355 int nSize
= (p
->nTotal
/ p
->nParam
);
357 sqlite3_result_int64(pCtx
, p
->iRow
);
359 i64 nLarge
= p
->nTotal
- p
->nParam
*nSize
;
360 i64 iSmall
= nLarge
*(nSize
+1);
361 i64 iRow
= p
->iRow
-1;
363 assert( (nLarge
*(nSize
+1) + (p
->nParam
-nLarge
)*nSize
)==p
->nTotal
);
366 sqlite3_result_int64(pCtx
, 1 + iRow
/(nSize
+1));
368 sqlite3_result_int64(pCtx
, 1 + nLarge
+ (iRow
-iSmall
)/nSize
);
375 ** Context object for last_value() window function.
377 struct LastValueCtx
{
383 ** Implementation of last_value().
385 static void last_valueStepFunc(
386 sqlite3_context
*pCtx
,
388 sqlite3_value
**apArg
390 struct LastValueCtx
*p
;
391 p
= (struct LastValueCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
393 sqlite3_value_free(p
->pVal
);
394 p
->pVal
= sqlite3_value_dup(apArg
[0]);
396 sqlite3_result_error_nomem(pCtx
);
402 static void last_valueInvFunc(
403 sqlite3_context
*pCtx
,
405 sqlite3_value
**apArg
407 struct LastValueCtx
*p
;
408 p
= (struct LastValueCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
412 sqlite3_value_free(p
->pVal
);
417 static void last_valueValueFunc(sqlite3_context
*pCtx
){
418 struct LastValueCtx
*p
;
419 p
= (struct LastValueCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
421 sqlite3_result_value(pCtx
, p
->pVal
);
424 static void last_valueFinalizeFunc(sqlite3_context
*pCtx
){
425 struct LastValueCtx
*p
;
426 p
= (struct LastValueCtx
*)sqlite3_aggregate_context(pCtx
, sizeof(*p
));
428 sqlite3_result_value(pCtx
, p
->pVal
);
429 sqlite3_value_free(p
->pVal
);
435 ** No-op implementations of nth_value(), first_value(), lead() and lag().
436 ** These are all implemented inline using VDBE instructions.
438 static void nth_valueStepFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**a
){}
439 static void nth_valueInvFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**ap
){}
440 static void nth_valueValueFunc(sqlite3_context
*pCtx
){}
441 static void first_valueStepFunc(sqlite3_context
*p
, int n
, sqlite3_value
**ap
){}
442 static void first_valueInvFunc(sqlite3_context
*p
, int n
, sqlite3_value
**ap
){}
443 static void first_valueValueFunc(sqlite3_context
*pCtx
){}
444 static void leadStepFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**ap
){}
445 static void leadInvFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**ap
){}
446 static void leadValueFunc(sqlite3_context
*pCtx
){}
447 static void lagStepFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**ap
){}
448 static void lagInvFunc(sqlite3_context
*pCtx
, int n
, sqlite3_value
**ap
){}
449 static void lagValueFunc(sqlite3_context
*pCtx
){}
451 #define WINDOWFUNC(name,nArg,extra) { \
452 nArg, (SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0, \
453 name ## StepFunc, name ## ValueFunc, name ## ValueFunc, \
454 name ## InvFunc, #name \
457 #define WINDOWFUNCF(name,nArg,extra) { \
458 nArg, (SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0, \
459 name ## StepFunc, name ## FinalizeFunc, name ## ValueFunc, \
460 name ## InvFunc, #name \
464 ** Register those built-in window functions that are not also aggregates.
466 void sqlite3WindowFunctions(void){
467 static FuncDef aWindowFuncs
[] = {
468 WINDOWFUNC(row_number
, 0, 0),
469 WINDOWFUNC(dense_rank
, 0, 0),
470 WINDOWFUNC(rank
, 0, 0),
471 WINDOWFUNC(percent_rank
, 0, SQLITE_FUNC_WINDOW_SIZE
),
472 WINDOWFUNC(cume_dist
, 0, SQLITE_FUNC_WINDOW_SIZE
),
473 WINDOWFUNC(ntile
, 1, SQLITE_FUNC_WINDOW_SIZE
),
474 WINDOWFUNCF(last_value
, 1, 0),
475 WINDOWFUNC(nth_value
, 2, 0),
476 WINDOWFUNC(first_value
, 1, 0),
477 WINDOWFUNC(lead
, 1, 0), WINDOWFUNC(lead
, 2, 0), WINDOWFUNC(lead
, 3, 0),
478 WINDOWFUNC(lag
, 1, 0), WINDOWFUNC(lag
, 2, 0), WINDOWFUNC(lag
, 3, 0),
480 sqlite3InsertBuiltinFuncs(aWindowFuncs
, ArraySize(aWindowFuncs
));
484 ** This function is called immediately after resolving the function name
485 ** for a window function within a SELECT statement. Argument pList is a
486 ** linked list of WINDOW definitions for the current SELECT statement.
487 ** Argument pFunc is the function definition just resolved and pWin
488 ** is the Window object representing the associated OVER clause. This
489 ** function updates the contents of pWin as follows:
491 ** * If the OVER clause refered to a named window (as in "max(x) OVER win"),
492 ** search list pList for a matching WINDOW definition, and update pWin
493 ** accordingly. If no such WINDOW clause can be found, leave an error
496 ** * If the function is a built-in window function that requires the
497 ** window to be coerced (see "BUILT-IN WINDOW FUNCTIONS" at the top
498 ** of this file), pWin is updated here.
500 void sqlite3WindowUpdate(
502 Window
*pList
, /* List of named windows for this SELECT */
503 Window
*pWin
, /* Window frame to update */
504 FuncDef
*pFunc
/* Window function definition */
508 for(p
=pList
; p
; p
=p
->pNextWin
){
509 if( sqlite3StrICmp(p
->zName
, pWin
->zName
)==0 ) break;
512 sqlite3ErrorMsg(pParse
, "no such window: %s", pWin
->zName
);
515 pWin
->pPartition
= sqlite3ExprListDup(pParse
->db
, p
->pPartition
, 0);
516 pWin
->pOrderBy
= sqlite3ExprListDup(pParse
->db
, p
->pOrderBy
, 0);
517 pWin
->pStart
= sqlite3ExprDup(pParse
->db
, p
->pStart
, 0);
518 pWin
->pEnd
= sqlite3ExprDup(pParse
->db
, p
->pEnd
, 0);
519 pWin
->eStart
= p
->eStart
;
520 pWin
->eEnd
= p
->eEnd
;
522 if( pFunc
->funcFlags
& SQLITE_FUNC_WINDOW
){
523 sqlite3
*db
= pParse
->db
;
525 sqlite3ErrorMsg(pParse
,
526 "FILTER clause may only be used with aggregate window functions"
529 if( pFunc
->xSFunc
==row_numberStepFunc
|| pFunc
->xSFunc
==ntileStepFunc
){
530 sqlite3ExprDelete(db
, pWin
->pStart
);
531 sqlite3ExprDelete(db
, pWin
->pEnd
);
532 pWin
->pStart
= pWin
->pEnd
= 0;
533 pWin
->eType
= TK_ROWS
;
534 pWin
->eStart
= TK_UNBOUNDED
;
535 pWin
->eEnd
= TK_CURRENT
;
538 if( pFunc
->xSFunc
==dense_rankStepFunc
|| pFunc
->xSFunc
==rankStepFunc
539 || pFunc
->xSFunc
==percent_rankStepFunc
|| pFunc
->xSFunc
==cume_distStepFunc
541 sqlite3ExprDelete(db
, pWin
->pStart
);
542 sqlite3ExprDelete(db
, pWin
->pEnd
);
543 pWin
->pStart
= pWin
->pEnd
= 0;
544 pWin
->eType
= TK_RANGE
;
545 pWin
->eStart
= TK_UNBOUNDED
;
546 pWin
->eEnd
= TK_CURRENT
;
553 ** Context object passed through sqlite3WalkExprList() to
554 ** selectWindowRewriteExprCb() by selectWindowRewriteEList().
556 typedef struct WindowRewrite WindowRewrite
;
557 struct WindowRewrite
{
563 ** Callback function used by selectWindowRewriteEList(). If necessary,
564 ** this function appends to the output expression-list and updates
565 ** expression (*ppExpr) in place.
567 static int selectWindowRewriteExprCb(Walker
*pWalker
, Expr
*pExpr
){
568 struct WindowRewrite
*p
= pWalker
->u
.pRewrite
;
569 Parse
*pParse
= pWalker
->pParse
;
574 if( pExpr
->pWin
==0 ){
578 for(pWin
=p
->pWin
; pWin
; pWin
=pWin
->pNextWin
){
579 if( pExpr
->pWin
==pWin
){
580 assert( pWin
->pOwner
==pExpr
);
587 case TK_AGG_FUNCTION
:
589 Expr
*pDup
= sqlite3ExprDup(pParse
->db
, pExpr
, 0);
590 p
->pSub
= sqlite3ExprListAppend(pParse
, p
->pSub
, pDup
);
592 assert( ExprHasProperty(pExpr
, EP_Static
)==0 );
593 ExprSetProperty(pExpr
, EP_Static
);
594 sqlite3ExprDelete(pParse
->db
, pExpr
);
595 ExprClearProperty(pExpr
, EP_Static
);
596 memset(pExpr
, 0, sizeof(Expr
));
598 pExpr
->op
= TK_COLUMN
;
599 pExpr
->iColumn
= p
->pSub
->nExpr
-1;
600 pExpr
->iTable
= p
->pWin
->iEphCsr
;
612 static int selectWindowRewriteSelectCb(Walker
*pWalker
, Select
*pSelect
){
618 ** Iterate through each expression in expression-list pEList. For each:
621 ** * aggregate function, or
622 ** * window function with a Window object that is not a member of the
623 ** linked list passed as the second argument (pWin)
625 ** Append the node to output expression-list (*ppSub). And replace it
626 ** with a TK_COLUMN that reads the (N-1)th element of table
627 ** pWin->iEphCsr, where N is the number of elements in (*ppSub) after
628 ** appending the new one.
630 static void selectWindowRewriteEList(
633 ExprList
*pEList
, /* Rewrite expressions in this list */
634 ExprList
**ppSub
/* IN/OUT: Sub-select expression-list */
637 WindowRewrite sRewrite
;
639 memset(&sWalker
, 0, sizeof(Walker
));
640 memset(&sRewrite
, 0, sizeof(WindowRewrite
));
642 sRewrite
.pSub
= *ppSub
;
643 sRewrite
.pWin
= pWin
;
645 sWalker
.pParse
= pParse
;
646 sWalker
.xExprCallback
= selectWindowRewriteExprCb
;
647 sWalker
.xSelectCallback
= selectWindowRewriteSelectCb
;
648 sWalker
.u
.pRewrite
= &sRewrite
;
650 (void)sqlite3WalkExprList(&sWalker
, pEList
);
652 *ppSub
= sRewrite
.pSub
;
656 ** Append a copy of each expression in expression-list pAppend to
657 ** expression list pList. Return a pointer to the result list.
659 static ExprList
*exprListAppendList(
660 Parse
*pParse
, /* Parsing context */
661 ExprList
*pList
, /* List to which to append. Might be NULL */
662 ExprList
*pAppend
/* List of values to append. Might be NULL */
666 int nInit
= pList
? pList
->nExpr
: 0;
667 for(i
=0; i
<pAppend
->nExpr
; i
++){
668 Expr
*pDup
= sqlite3ExprDup(pParse
->db
, pAppend
->a
[i
].pExpr
, 0);
669 pList
= sqlite3ExprListAppend(pParse
, pList
, pDup
);
670 if( pList
) pList
->a
[nInit
+i
].sortOrder
= pAppend
->a
[i
].sortOrder
;
677 ** If the SELECT statement passed as the second argument does not invoke
678 ** any SQL window functions, this function is a no-op. Otherwise, it
679 ** rewrites the SELECT statement so that window function xStep functions
680 ** are invoked in the correct order as described under "SELECT REWRITING"
681 ** at the top of this file.
683 int sqlite3WindowRewrite(Parse
*pParse
, Select
*p
){
686 Vdbe
*v
= sqlite3GetVdbe(pParse
);
687 sqlite3
*db
= pParse
->db
;
688 Select
*pSub
= 0; /* The subquery */
689 SrcList
*pSrc
= p
->pSrc
;
690 Expr
*pWhere
= p
->pWhere
;
691 ExprList
*pGroupBy
= p
->pGroupBy
;
692 Expr
*pHaving
= p
->pHaving
;
695 ExprList
*pSublist
= 0; /* Expression list for sub-query */
696 Window
*pMWin
= p
->pWin
; /* Master window object */
697 Window
*pWin
; /* Window object iterator */
704 /* Assign a cursor number for the ephemeral table used to buffer rows.
705 ** The OpenEphemeral instruction is coded later, after it is known how
706 ** many columns the table will have. */
707 pMWin
->iEphCsr
= pParse
->nTab
++;
709 selectWindowRewriteEList(pParse
, pMWin
, p
->pEList
, &pSublist
);
710 selectWindowRewriteEList(pParse
, pMWin
, p
->pOrderBy
, &pSublist
);
711 pMWin
->nBufferCol
= (pSublist
? pSublist
->nExpr
: 0);
713 /* Create the ORDER BY clause for the sub-select. This is the concatenation
714 ** of the window PARTITION and ORDER BY clauses. Append the same
715 ** expressions to the sub-select expression list. They are required to
716 ** figure out where boundaries for partitions and sets of peer rows. */
717 pSort
= sqlite3ExprListDup(db
, pMWin
->pPartition
, 0);
718 if( pMWin
->pOrderBy
){
719 pSort
= exprListAppendList(pParse
, pSort
, pMWin
->pOrderBy
);
721 pSublist
= exprListAppendList(pParse
, pSublist
, pSort
);
723 /* Append the arguments passed to each window function to the
724 ** sub-select expression list. Also allocate two registers for each
725 ** window function - one for the accumulator, another for interim
727 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
728 pWin
->iArgCol
= (pSublist
? pSublist
->nExpr
: 0);
729 pSublist
= exprListAppendList(pParse
, pSublist
, pWin
->pOwner
->x
.pList
);
731 Expr
*pFilter
= sqlite3ExprDup(db
, pWin
->pFilter
, 0);
732 pSublist
= sqlite3ExprListAppend(pParse
, pSublist
, pFilter
);
734 pWin
->regAccum
= ++pParse
->nMem
;
735 pWin
->regResult
= ++pParse
->nMem
;
736 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regAccum
);
739 pSub
= sqlite3SelectNew(
740 pParse
, pSublist
, pSrc
, pWhere
, pGroupBy
, pHaving
, pSort
, 0, 0
742 p
->pSrc
= sqlite3SrcListAppend(db
, 0, 0, 0);
743 assert( p
->pSrc
|| db
->mallocFailed
);
745 p
->pSrc
->a
[0].pSelect
= pSub
;
746 sqlite3SrcListAssignCursors(pParse
, p
->pSrc
);
747 if( sqlite3ExpandSubquery(pParse
, &p
->pSrc
->a
[0]) ){
750 pSub
->selFlags
|= SF_Expanded
;
751 p
->selFlags
&= ~SF_Aggregate
;
752 sqlite3SelectPrep(pParse
, pSub
, 0);
755 sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, pMWin
->iEphCsr
, pSublist
->nExpr
);
757 sqlite3SelectDelete(db
, pSub
);
759 if( db
->mallocFailed
) rc
= SQLITE_NOMEM
;
766 ** Free the Window object passed as the second argument.
768 void sqlite3WindowDelete(sqlite3
*db
, Window
*p
){
770 sqlite3ExprDelete(db
, p
->pFilter
);
771 sqlite3ExprListDelete(db
, p
->pPartition
);
772 sqlite3ExprListDelete(db
, p
->pOrderBy
);
773 sqlite3ExprDelete(db
, p
->pEnd
);
774 sqlite3ExprDelete(db
, p
->pStart
);
775 sqlite3DbFree(db
, p
->zName
);
776 sqlite3DbFree(db
, p
);
781 ** Free the linked list of Window objects starting at the second argument.
783 void sqlite3WindowListDelete(sqlite3
*db
, Window
*p
){
785 Window
*pNext
= p
->pNextWin
;
786 sqlite3WindowDelete(db
, p
);
792 ** Allocate and return a new Window object.
794 Window
*sqlite3WindowAlloc(
797 int eStart
, Expr
*pStart
,
800 Window
*pWin
= (Window
*)sqlite3DbMallocZero(pParse
->db
, sizeof(Window
));
804 pWin
->eStart
= eStart
;
807 pWin
->pStart
= pStart
;
809 sqlite3ExprDelete(pParse
->db
, pEnd
);
810 sqlite3ExprDelete(pParse
->db
, pStart
);
817 ** Attach window object pWin to expression p.
819 void sqlite3WindowAttach(Parse
*pParse
, Expr
*p
, Window
*pWin
){
822 if( pWin
) pWin
->pOwner
= p
;
824 sqlite3WindowDelete(pParse
->db
, pWin
);
829 ** Return 0 if the two window objects are identical, or non-zero otherwise.
830 ** Identical window objects can be processed in a single scan.
832 int sqlite3WindowCompare(Parse
*pParse
, Window
*p1
, Window
*p2
){
833 if( p1
->eType
!=p2
->eType
) return 1;
834 if( p1
->eStart
!=p2
->eStart
) return 1;
835 if( p1
->eEnd
!=p2
->eEnd
) return 1;
836 if( sqlite3ExprCompare(pParse
, p1
->pStart
, p2
->pStart
, -1) ) return 1;
837 if( sqlite3ExprCompare(pParse
, p1
->pEnd
, p2
->pEnd
, -1) ) return 1;
838 if( sqlite3ExprListCompare(p1
->pPartition
, p2
->pPartition
, -1) ) return 1;
839 if( sqlite3ExprListCompare(p1
->pOrderBy
, p2
->pOrderBy
, -1) ) return 1;
845 ** This is called by code in select.c before it calls sqlite3WhereBegin()
846 ** to begin iterating through the sub-query results. It is used to allocate
847 ** and initialize registers and cursors used by sqlite3WindowCodeStep().
849 void sqlite3WindowCodeInit(Parse
*pParse
, Window
*pMWin
){
851 Vdbe
*v
= sqlite3GetVdbe(pParse
);
852 int nPart
= (pMWin
->pPartition
? pMWin
->pPartition
->nExpr
: 0);
853 nPart
+= (pMWin
->pOrderBy
? pMWin
->pOrderBy
->nExpr
: 0);
855 pMWin
->regPart
= pParse
->nMem
+1;
856 pParse
->nMem
+= nPart
;
857 sqlite3VdbeAddOp3(v
, OP_Null
, 0, pMWin
->regPart
, pMWin
->regPart
+nPart
-1);
860 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
861 FuncDef
*p
= pWin
->pFunc
;
862 if( (p
->funcFlags
& SQLITE_FUNC_MINMAX
) && pWin
->eStart
!=TK_UNBOUNDED
){
863 /* The inline versions of min() and max() require a single ephemeral
864 ** table and 3 registers. The registers are used as follows:
866 ** regApp+0: slot to copy min()/max() argument to for MakeRecord
867 ** regApp+1: integer value used to ensure keys are unique
868 ** regApp+2: output of MakeRecord
870 ExprList
*pList
= pWin
->pOwner
->x
.pList
;
871 KeyInfo
*pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
, pList
, 0, 0);
872 pWin
->csrApp
= pParse
->nTab
++;
873 pWin
->regApp
= pParse
->nMem
+1;
875 if( pKeyInfo
&& pWin
->pFunc
->zName
[1]=='i' ){
876 assert( pKeyInfo
->aSortOrder
[0]==0 );
877 pKeyInfo
->aSortOrder
[0] = 1;
879 sqlite3VdbeAddOp2(v
, OP_OpenEphemeral
, pWin
->csrApp
, 2);
880 sqlite3VdbeAppendP4(v
, pKeyInfo
, P4_KEYINFO
);
881 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, pWin
->regApp
+1);
883 else if( p
->xSFunc
==nth_valueStepFunc
|| p
->xSFunc
==first_valueStepFunc
){
884 /* Allocate two registers at pWin->regApp. These will be used to
885 ** store the start and end index of the current frame. */
886 assert( pMWin
->iEphCsr
);
887 pWin
->regApp
= pParse
->nMem
+1;
888 pWin
->csrApp
= pParse
->nTab
++;
890 sqlite3VdbeAddOp2(v
, OP_OpenDup
, pWin
->csrApp
, pMWin
->iEphCsr
);
892 else if( p
->xSFunc
==leadStepFunc
|| p
->xSFunc
==lagStepFunc
){
893 assert( pMWin
->iEphCsr
);
894 pWin
->csrApp
= pParse
->nTab
++;
895 sqlite3VdbeAddOp2(v
, OP_OpenDup
, pWin
->csrApp
, pMWin
->iEphCsr
);
901 ** A "PRECEDING <expr>" (bEnd==0) or "FOLLOWING <expr>" (bEnd==1) has just
902 ** been evaluated and the result left in register reg. This function generates
903 ** VM code to check that the value is a non-negative integer and throws
904 ** an exception if it is not.
906 static void windowCheckFrameValue(Parse
*pParse
, int reg
, int bEnd
){
907 static const char *azErr
[] = {
908 "frame starting offset must be a non-negative integer",
909 "frame ending offset must be a non-negative integer"
911 Vdbe
*v
= sqlite3GetVdbe(pParse
);
912 int regZero
= sqlite3GetTempReg(pParse
);
913 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, regZero
);
914 sqlite3VdbeAddOp2(v
, OP_MustBeInt
, reg
, sqlite3VdbeCurrentAddr(v
)+2);
915 sqlite3VdbeAddOp3(v
, OP_Ge
, regZero
, sqlite3VdbeCurrentAddr(v
)+2, reg
);
916 sqlite3VdbeAddOp2(v
, OP_Halt
, SQLITE_ERROR
, OE_Abort
);
917 sqlite3VdbeAppendP4(v
, (void*)azErr
[bEnd
], P4_STATIC
);
918 sqlite3ReleaseTempReg(pParse
, regZero
);
922 ** Return the number of arguments passed to the window-function associated
923 ** with the object passed as the only argument to this function.
925 static int windowArgCount(Window
*pWin
){
926 ExprList
*pList
= pWin
->pOwner
->x
.pList
;
927 return (pList
? pList
->nExpr
: 0);
931 ** Generate VM code to invoke either xStep() (if bInverse is 0) or
932 ** xInverse (if bInverse is non-zero) for each window function in the
933 ** linked list starting at pMWin. Or, for built-in window functions
934 ** that do not use the standard function API, generate the required
937 ** If argument csr is greater than or equal to 0, then argument reg is
938 ** the first register in an array of registers guaranteed to be large
939 ** enough to hold the array of arguments for each function. In this case
940 ** the arguments are extracted from the current row of csr into the
941 ** array of registers before invoking OP_AggStep.
943 ** Or, if csr is less than zero, then the array of registers at reg is
944 ** already populated with all columns from the current row of the sub-query.
946 ** If argument regPartSize is non-zero, then it is a register containing the
947 ** number of rows in the current partition.
949 static void windowAggStep(
951 Window
*pMWin
, /* Linked list of window functions */
952 int csr
, /* Read arguments from this cursor */
953 int bInverse
, /* True to invoke xInverse instead of xStep */
954 int reg
, /* Array of registers */
955 int regPartSize
/* Register containing size of partition */
957 Vdbe
*v
= sqlite3GetVdbe(pParse
);
959 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
960 int flags
= pWin
->pFunc
->funcFlags
;
962 int nArg
= windowArgCount(pWin
);
966 for(i
=0; i
<nArg
; i
++){
967 sqlite3VdbeAddOp3(v
, OP_Column
, csr
, pWin
->iArgCol
+i
, reg
+i
);
970 if( flags
& SQLITE_FUNC_WINDOW_SIZE
){
972 regArg
= regPartSize
;
974 sqlite3VdbeAddOp2(v
, OP_SCopy
, regPartSize
, reg
+nArg
);
979 assert( !(flags
& SQLITE_FUNC_WINDOW_SIZE
) );
980 regArg
= reg
+ pWin
->iArgCol
;
983 if( (pWin
->pFunc
->funcFlags
& SQLITE_FUNC_MINMAX
)
984 && pWin
->eStart
!=TK_UNBOUNDED
987 sqlite3VdbeAddOp2(v
, OP_AddImm
, pWin
->regApp
+1, 1);
988 sqlite3VdbeAddOp2(v
, OP_SCopy
, regArg
, pWin
->regApp
);
989 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, pWin
->regApp
, 2, pWin
->regApp
+2);
990 sqlite3VdbeAddOp2(v
, OP_IdxInsert
, pWin
->csrApp
, pWin
->regApp
+2);
992 sqlite3VdbeAddOp4Int(v
, OP_SeekGE
, pWin
->csrApp
, 0, regArg
, 1);
993 sqlite3VdbeAddOp1(v
, OP_Delete
, pWin
->csrApp
);
994 sqlite3VdbeJumpHere(v
, sqlite3VdbeCurrentAddr(v
)-2);
996 }else if( pWin
->regApp
){
997 assert( pWin
->pFunc
->xSFunc
==nth_valueStepFunc
998 || pWin
->pFunc
->xSFunc
==first_valueStepFunc
1000 assert( bInverse
==0 || bInverse
==1 );
1001 sqlite3VdbeAddOp2(v
, OP_AddImm
, pWin
->regApp
+1-bInverse
, 1);
1002 }else if( pWin
->pFunc
->xSFunc
==leadStepFunc
1003 || pWin
->pFunc
->xSFunc
==lagStepFunc
1008 if( pWin
->pFilter
){
1010 assert( nArg
==pWin
->pOwner
->x
.pList
->nExpr
);
1012 regTmp
= sqlite3GetTempReg(pParse
);
1013 sqlite3VdbeAddOp3(v
, OP_Column
, csr
, pWin
->iArgCol
+nArg
,regTmp
);
1015 regTmp
= regArg
+ nArg
;
1017 addrIf
= sqlite3VdbeAddOp3(v
, OP_IfNot
, regTmp
, 0, 1);
1019 sqlite3ReleaseTempReg(pParse
, regTmp
);
1022 if( pWin
->pFunc
->funcFlags
& SQLITE_FUNC_NEEDCOLL
){
1024 pColl
= sqlite3ExprNNCollSeq(pParse
, pWin
->pOwner
->x
.pList
->a
[0].pExpr
);
1025 sqlite3VdbeAddOp4(v
, OP_CollSeq
, 0,0,0, (const char*)pColl
, P4_COLLSEQ
);
1027 sqlite3VdbeAddOp3(v
, OP_AggStep0
, bInverse
, regArg
, pWin
->regAccum
);
1028 sqlite3VdbeAppendP4(v
, pWin
->pFunc
, P4_FUNCDEF
);
1029 sqlite3VdbeChangeP5(v
, (u8
)nArg
);
1030 if( addrIf
) sqlite3VdbeJumpHere(v
, addrIf
);
1036 ** Generate VM code to invoke either xValue() (bFinal==0) or xFinalize()
1037 ** (bFinal==1) for each window function in the linked list starting at
1038 ** pMWin. Or, for built-in window-functions that do not use the standard
1039 ** API, generate the equivalent VM code.
1041 static void windowAggFinal(Parse
*pParse
, Window
*pMWin
, int bFinal
){
1042 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1045 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
1046 if( (pWin
->pFunc
->funcFlags
& SQLITE_FUNC_MINMAX
)
1047 && pWin
->eStart
!=TK_UNBOUNDED
1049 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regResult
);
1050 sqlite3VdbeAddOp1(v
, OP_Last
, pWin
->csrApp
);
1051 sqlite3VdbeAddOp3(v
, OP_Column
, pWin
->csrApp
, 0, pWin
->regResult
);
1052 sqlite3VdbeJumpHere(v
, sqlite3VdbeCurrentAddr(v
)-2);
1054 sqlite3VdbeAddOp1(v
, OP_ResetSorter
, pWin
->csrApp
);
1056 }else if( pWin
->regApp
){
1059 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regResult
);
1061 sqlite3VdbeAddOp2(v
, OP_AggFinal
, pWin
->regAccum
, windowArgCount(pWin
));
1062 sqlite3VdbeAppendP4(v
, pWin
->pFunc
, P4_FUNCDEF
);
1064 sqlite3VdbeAddOp2(v
, OP_Copy
, pWin
->regAccum
, pWin
->regResult
);
1065 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regAccum
);
1067 sqlite3VdbeChangeP3(v
, -1, pWin
->regResult
);
1074 ** This function generates VM code to invoke the sub-routine at address
1075 ** lblFlushPart once for each partition with the entire partition cached in
1076 ** the Window.iEphCsr temp table.
1078 static void windowPartitionCache(
1080 Select
*p
, /* The rewritten SELECT statement */
1081 WhereInfo
*pWInfo
, /* WhereInfo to call WhereEnd() on */
1082 int regFlushPart
, /* Register to use with Gosub lblFlushPart */
1083 int lblFlushPart
, /* Subroutine to Gosub to */
1084 int *pRegSize
/* OUT: Register containing partition size */
1086 Window
*pMWin
= p
->pWin
;
1087 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1088 int iSubCsr
= p
->pSrc
->a
[0].iCursor
;
1089 int nSub
= p
->pSrc
->a
[0].pTab
->nCol
;
1092 int reg
= pParse
->nMem
+1;
1093 int regRecord
= reg
+nSub
;
1094 int regRowid
= regRecord
+1;
1096 *pRegSize
= regRowid
;
1097 pParse
->nMem
+= nSub
+ 2;
1099 /* Martial the row returned by the sub-select into an array of
1101 for(k
=0; k
<nSub
; k
++){
1102 sqlite3VdbeAddOp3(v
, OP_Column
, iSubCsr
, k
, reg
+k
);
1104 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, reg
, nSub
, regRecord
);
1106 /* Check if this is the start of a new partition. If so, call the
1107 ** flush_partition sub-routine. */
1108 if( pMWin
->pPartition
){
1110 ExprList
*pPart
= pMWin
->pPartition
;
1111 int nPart
= pPart
->nExpr
;
1112 int regNewPart
= reg
+ pMWin
->nBufferCol
;
1113 KeyInfo
*pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
, pPart
, 0, 0);
1115 addr
= sqlite3VdbeAddOp3(v
, OP_Compare
, regNewPart
, pMWin
->regPart
,nPart
);
1116 sqlite3VdbeAppendP4(v
, (void*)pKeyInfo
, P4_KEYINFO
);
1117 sqlite3VdbeAddOp3(v
, OP_Jump
, addr
+2, addr
+4, addr
+2);
1118 sqlite3VdbeAddOp3(v
, OP_Copy
, regNewPart
, pMWin
->regPart
, nPart
-1);
1119 sqlite3VdbeAddOp2(v
, OP_Gosub
, regFlushPart
, lblFlushPart
);
1122 /* Buffer the current row in the ephemeral table. */
1123 sqlite3VdbeAddOp2(v
, OP_NewRowid
, pMWin
->iEphCsr
, regRowid
);
1124 sqlite3VdbeAddOp3(v
, OP_Insert
, pMWin
->iEphCsr
, regRecord
, regRowid
);
1126 /* End of the input loop */
1127 sqlite3WhereEnd(pWInfo
);
1129 /* Invoke "flush_partition" to deal with the final (or only) partition */
1130 sqlite3VdbeAddOp2(v
, OP_Gosub
, regFlushPart
, lblFlushPart
);
1134 ** Invoke the sub-routine at regGosub (generated by code in select.c) to
1135 ** return the current row of Window.iEphCsr. If all window functions are
1136 ** aggregate window functions that use the standard API, a single
1137 ** OP_Gosub instruction is all that this routine generates. Extra VM code
1138 ** for per-row processing is only generated for the following built-in window
1146 static void windowReturnOneRow(
1152 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1154 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
1155 FuncDef
*pFunc
= pWin
->pFunc
;
1156 if( pFunc
->xSFunc
==nth_valueStepFunc
1157 || pFunc
->xSFunc
==first_valueStepFunc
1159 int csr
= pWin
->csrApp
;
1160 int lbl
= sqlite3VdbeMakeLabel(v
);
1161 int tmpReg
= sqlite3GetTempReg(pParse
);
1162 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regResult
);
1164 if( pFunc
->xSFunc
==nth_valueStepFunc
){
1165 sqlite3VdbeAddOp3(v
, OP_Column
, pMWin
->iEphCsr
, pWin
->iArgCol
+1,tmpReg
);
1167 sqlite3VdbeAddOp2(v
, OP_Integer
, 1, tmpReg
);
1169 sqlite3VdbeAddOp3(v
, OP_Add
, tmpReg
, pWin
->regApp
, tmpReg
);
1170 sqlite3VdbeAddOp3(v
, OP_Gt
, pWin
->regApp
+1, lbl
, tmpReg
);
1171 sqlite3VdbeAddOp3(v
, OP_SeekRowid
, csr
, lbl
, tmpReg
);
1172 sqlite3VdbeAddOp3(v
, OP_Column
, csr
, pWin
->iArgCol
, pWin
->regResult
);
1173 sqlite3VdbeResolveLabel(v
, lbl
);
1174 sqlite3ReleaseTempReg(pParse
, tmpReg
);
1176 else if( pFunc
->xSFunc
==leadStepFunc
|| pFunc
->xSFunc
==lagStepFunc
){
1177 int nArg
= pWin
->pOwner
->x
.pList
->nExpr
;
1178 int iEph
= pMWin
->iEphCsr
;
1179 int csr
= pWin
->csrApp
;
1180 int lbl
= sqlite3VdbeMakeLabel(v
);
1181 int tmpReg
= sqlite3GetTempReg(pParse
);
1184 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regResult
);
1186 sqlite3VdbeAddOp3(v
, OP_Column
, iEph
, pWin
->iArgCol
+2, pWin
->regResult
);
1188 sqlite3VdbeAddOp2(v
, OP_Rowid
, iEph
, tmpReg
);
1190 int val
= (pFunc
->xSFunc
==leadStepFunc
? 1 : -1);
1191 sqlite3VdbeAddOp2(v
, OP_AddImm
, tmpReg
, val
);
1193 int op
= (pFunc
->xSFunc
==leadStepFunc
? OP_Add
: OP_Subtract
);
1194 int tmpReg2
= sqlite3GetTempReg(pParse
);
1195 sqlite3VdbeAddOp3(v
, OP_Column
, iEph
, pWin
->iArgCol
+1, tmpReg2
);
1196 sqlite3VdbeAddOp3(v
, op
, tmpReg2
, tmpReg
, tmpReg
);
1197 sqlite3ReleaseTempReg(pParse
, tmpReg2
);
1200 sqlite3VdbeAddOp3(v
, OP_SeekRowid
, csr
, lbl
, tmpReg
);
1201 sqlite3VdbeAddOp3(v
, OP_Column
, csr
, pWin
->iArgCol
, pWin
->regResult
);
1202 sqlite3VdbeResolveLabel(v
, lbl
);
1203 sqlite3ReleaseTempReg(pParse
, tmpReg
);
1206 sqlite3VdbeAddOp2(v
, OP_Gosub
, regGosub
, addrGosub
);
1210 ** Invoke the code generated by windowReturnOneRow() and, optionally, the
1211 ** xInverse() function for each window function, for one or more rows
1212 ** from the Window.iEphCsr temp table. This routine generates VM code
1215 ** while( regCtr>0 ){
1217 ** windowReturnOneRow()
1219 ** AggStep (xInverse)
1221 ** Next (Window.iEphCsr)
1224 static void windowReturnRows(
1226 Window
*pMWin
, /* List of window functions */
1227 int regCtr
, /* Register containing number of rows */
1228 int regGosub
, /* Register for Gosub addrGosub */
1229 int addrGosub
, /* Address of sub-routine for ReturnOneRow */
1230 int regInvArg
, /* Array of registers for xInverse args */
1231 int regInvSize
/* Register containing size of partition */
1234 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1235 windowAggFinal(pParse
, pMWin
, 0);
1236 addr
= sqlite3VdbeAddOp3(v
, OP_IfPos
, regCtr
, sqlite3VdbeCurrentAddr(v
)+2 ,1);
1237 sqlite3VdbeAddOp2(v
, OP_Goto
, 0, 0);
1238 windowReturnOneRow(pParse
, pMWin
, regGosub
, addrGosub
);
1240 windowAggStep(pParse
, pMWin
, pMWin
->iEphCsr
, 1, regInvArg
, regInvSize
);
1242 sqlite3VdbeAddOp2(v
, OP_Next
, pMWin
->iEphCsr
, addr
);
1243 sqlite3VdbeJumpHere(v
, addr
+1); /* The OP_Goto */
1247 ** Generate code to set the accumulator register for each window function
1248 ** in the linked list passed as the second argument to NULL. And perform
1249 ** any equivalent initialization required by any built-in window functions
1252 static int windowInitAccum(Parse
*pParse
, Window
*pMWin
){
1253 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1257 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
1258 FuncDef
*pFunc
= pWin
->pFunc
;
1259 sqlite3VdbeAddOp2(v
, OP_Null
, 0, pWin
->regAccum
);
1260 nArg
= MAX(nArg
, windowArgCount(pWin
));
1261 if( pFunc
->xSFunc
==nth_valueStepFunc
1262 || pFunc
->xSFunc
==first_valueStepFunc
1264 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, pWin
->regApp
);
1265 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, pWin
->regApp
+1);
1268 if( (pFunc
->funcFlags
& SQLITE_FUNC_MINMAX
) && pWin
->csrApp
){
1269 assert( pWin
->eStart
!=TK_UNBOUNDED
);
1270 sqlite3VdbeAddOp1(v
, OP_ResetSorter
, pWin
->csrApp
);
1271 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, pWin
->regApp
+1);
1274 regArg
= pParse
->nMem
+1;
1275 pParse
->nMem
+= nArg
;
1281 ** This function does the work of sqlite3WindowCodeStep() for all "ROWS"
1282 ** window frame types except for "BETWEEN UNBOUNDED PRECEDING AND CURRENT
1283 ** ROW". Pseudo-code for each follows.
1285 ** ROWS BETWEEN <expr1> PRECEDING AND <expr2> FOLLOWING
1288 ** if( new partition ){
1289 ** Gosub flush_partition
1291 ** Insert (record in eph-table)
1292 ** sqlite3WhereEnd()
1293 ** Gosub flush_partition
1297 ** OpenDup (iEphCsr -> csrStart)
1298 ** OpenDup (iEphCsr -> csrEnd)
1300 ** regStart = <expr1> // PRECEDING expression
1301 ** regEnd = <expr2> // FOLLOWING expression
1302 ** if( regStart<0 || regEnd<0 ){ error! }
1303 ** Rewind (csr,csrStart,csrEnd) // if EOF goto flush_partition_done
1304 ** Next(csrEnd) // if EOF skip Aggstep
1306 ** if( (regEnd--)<=0 ){
1307 ** AggFinal (xValue)
1309 ** Next(csr) // if EOF goto flush_partition_done
1310 ** if( (regStart--)<=0 ){
1311 ** AggStep (csrStart, xInverse)
1315 ** flush_partition_done:
1316 ** ResetSorter (csr)
1319 ** ROWS BETWEEN <expr> PRECEDING AND CURRENT ROW
1320 ** ROWS BETWEEN CURRENT ROW AND <expr> FOLLOWING
1321 ** ROWS BETWEEN UNBOUNDED PRECEDING AND <expr> FOLLOWING
1323 ** These are similar to the above. For "CURRENT ROW", intialize the
1324 ** register to 0. For "UNBOUNDED PRECEDING" to infinity.
1326 ** ROWS BETWEEN <expr> PRECEDING AND UNBOUNDED FOLLOWING
1327 ** ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
1329 ** Rewind (csr,csrStart,csrEnd) // if EOF goto flush_partition_done
1331 ** Next(csrEnd) // Exit while(1) at EOF
1335 ** AggFinal (xValue)
1337 ** Next(csr) // if EOF goto flush_partition_done
1338 ** if( (regStart--)<=0 ){
1339 ** AggStep (csrStart, xInverse)
1344 ** For the "CURRENT ROW AND UNBOUNDED FOLLOWING" case, the final if()
1345 ** condition is always true (as if regStart were initialized to 0).
1347 ** RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
1349 ** This is the only RANGE case handled by this routine. It modifies the
1350 ** second while( 1 ) loop in "ROWS BETWEEN CURRENT ... UNBOUNDED..." to
1354 ** AggFinal (xValue)
1358 ** Next(csr) // if EOF goto flush_partition_done
1359 ** if( new peer ) break;
1361 ** while( (regPeer--)>0 ){
1362 ** AggStep (csrStart, xInverse)
1367 ** ROWS BETWEEN <expr> FOLLOWING AND <expr> FOLLOWING
1369 ** regEnd = regEnd - regStart
1370 ** Rewind (csr,csrStart,csrEnd) // if EOF goto flush_partition_done
1372 ** Next(csrEnd) // if EOF fall-through
1373 ** if( (regEnd--)<=0 ){
1374 ** if( (regStart--)<=0 ){
1375 ** AggFinal (xValue)
1377 ** Next(csr) // if EOF goto flush_partition_done
1379 ** AggStep (csrStart, xInverse)
1383 ** ROWS BETWEEN <expr> PRECEDING AND <expr> PRECEDING
1385 ** Replace the bit after "Rewind" in the above with:
1387 ** if( (regEnd--)<=0 ){
1391 ** AggFinal (xValue)
1393 ** Next(csr) // if EOF goto flush_partition_done
1394 ** if( (regStart--)<=0 ){
1395 ** AggStep (csr2, xInverse)
1400 static void windowCodeRowExprStep(
1407 Window
*pMWin
= p
->pWin
;
1408 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1409 int regFlushPart
; /* Register for "Gosub flush_partition" */
1410 int lblFlushPart
; /* Label for "Gosub flush_partition" */
1411 int lblFlushDone
; /* Label for "Gosub flush_partition_done" */
1415 int csrStart
= pParse
->nTab
++;
1416 int csrEnd
= pParse
->nTab
++;
1417 int regStart
; /* Value of <expr> PRECEDING */
1418 int regEnd
; /* Value of <expr> FOLLOWING */
1425 assert( pMWin
->eStart
==TK_PRECEDING
1426 || pMWin
->eStart
==TK_CURRENT
1427 || pMWin
->eStart
==TK_FOLLOWING
1428 || pMWin
->eStart
==TK_UNBOUNDED
1430 assert( pMWin
->eEnd
==TK_FOLLOWING
1431 || pMWin
->eEnd
==TK_CURRENT
1432 || pMWin
->eEnd
==TK_UNBOUNDED
1433 || pMWin
->eEnd
==TK_PRECEDING
1436 /* Allocate register and label for the "flush_partition" sub-routine. */
1437 regFlushPart
= ++pParse
->nMem
;
1438 lblFlushPart
= sqlite3VdbeMakeLabel(v
);
1439 lblFlushDone
= sqlite3VdbeMakeLabel(v
);
1441 regStart
= ++pParse
->nMem
;
1442 regEnd
= ++pParse
->nMem
;
1444 windowPartitionCache(pParse
, p
, pWInfo
, regFlushPart
, lblFlushPart
, ®Size
);
1446 addrGoto
= sqlite3VdbeAddOp0(v
, OP_Goto
);
1448 /* Start of "flush_partition" */
1449 sqlite3VdbeResolveLabel(v
, lblFlushPart
);
1450 sqlite3VdbeAddOp2(v
, OP_Once
, 0, sqlite3VdbeCurrentAddr(v
)+3);
1451 sqlite3VdbeAddOp2(v
, OP_OpenDup
, csrStart
, pMWin
->iEphCsr
);
1452 sqlite3VdbeAddOp2(v
, OP_OpenDup
, csrEnd
, pMWin
->iEphCsr
);
1454 /* If either regStart or regEnd are not non-negative integers, throw
1456 if( pMWin
->pStart
){
1457 sqlite3ExprCode(pParse
, pMWin
->pStart
, regStart
);
1458 windowCheckFrameValue(pParse
, regStart
, 0);
1461 sqlite3ExprCode(pParse
, pMWin
->pEnd
, regEnd
);
1462 windowCheckFrameValue(pParse
, regEnd
, 1);
1465 /* If this is "ROWS <expr1> FOLLOWING AND ROWS <expr2> FOLLOWING", do:
1467 ** if( regEnd<regStart ){
1468 ** // The frame always consists of 0 rows
1469 ** regStart = regSize;
1471 ** regEnd = regEnd - regStart;
1473 if( pMWin
->pEnd
&& pMWin
->pStart
&& pMWin
->eStart
==TK_FOLLOWING
){
1474 assert( pMWin
->eEnd
==TK_FOLLOWING
);
1475 sqlite3VdbeAddOp3(v
, OP_Ge
, regStart
, sqlite3VdbeCurrentAddr(v
)+2, regEnd
);
1476 sqlite3VdbeAddOp2(v
, OP_Copy
, regSize
, regStart
);
1477 sqlite3VdbeAddOp3(v
, OP_Subtract
, regStart
, regEnd
, regEnd
);
1480 if( pMWin
->pEnd
&& pMWin
->pStart
&& pMWin
->eEnd
==TK_PRECEDING
){
1481 assert( pMWin
->eStart
==TK_PRECEDING
);
1482 sqlite3VdbeAddOp3(v
, OP_Le
, regStart
, sqlite3VdbeCurrentAddr(v
)+3, regEnd
);
1483 sqlite3VdbeAddOp2(v
, OP_Copy
, regSize
, regStart
);
1484 sqlite3VdbeAddOp2(v
, OP_Copy
, regSize
, regEnd
);
1487 /* Initialize the accumulator register for each window function to NULL */
1488 regArg
= windowInitAccum(pParse
, pMWin
);
1490 sqlite3VdbeAddOp2(v
, OP_Rewind
, pMWin
->iEphCsr
, lblFlushDone
);
1491 sqlite3VdbeAddOp2(v
, OP_Rewind
, csrStart
, lblFlushDone
);
1492 sqlite3VdbeChangeP5(v
, 1);
1493 sqlite3VdbeAddOp2(v
, OP_Rewind
, csrEnd
, lblFlushDone
);
1494 sqlite3VdbeChangeP5(v
, 1);
1496 /* Invoke AggStep function for each window function using the row that
1497 ** csrEnd currently points to. Or, if csrEnd is already at EOF,
1499 addrTop
= sqlite3VdbeCurrentAddr(v
);
1500 if( pMWin
->eEnd
==TK_PRECEDING
){
1501 addrIfPos1
= sqlite3VdbeAddOp3(v
, OP_IfPos
, regEnd
, 0 , 1);
1503 sqlite3VdbeAddOp2(v
, OP_Next
, csrEnd
, sqlite3VdbeCurrentAddr(v
)+2);
1504 addr
= sqlite3VdbeAddOp0(v
, OP_Goto
);
1505 windowAggStep(pParse
, pMWin
, csrEnd
, 0, regArg
, regSize
);
1506 if( pMWin
->eEnd
==TK_UNBOUNDED
){
1507 sqlite3VdbeAddOp2(v
, OP_Goto
, 0, addrTop
);
1508 sqlite3VdbeJumpHere(v
, addr
);
1509 addrTop
= sqlite3VdbeCurrentAddr(v
);
1511 sqlite3VdbeJumpHere(v
, addr
);
1512 if( pMWin
->eEnd
==TK_PRECEDING
){
1513 sqlite3VdbeJumpHere(v
, addrIfPos1
);
1517 if( pMWin
->eEnd
==TK_FOLLOWING
){
1518 addrIfPos1
= sqlite3VdbeAddOp3(v
, OP_IfPos
, regEnd
, 0 , 1);
1520 if( pMWin
->eStart
==TK_FOLLOWING
){
1521 addrIfPos2
= sqlite3VdbeAddOp3(v
, OP_IfPos
, regStart
, 0 , 1);
1523 windowAggFinal(pParse
, pMWin
, 0);
1524 windowReturnOneRow(pParse
, pMWin
, regGosub
, addrGosub
);
1525 sqlite3VdbeAddOp2(v
, OP_Next
, pMWin
->iEphCsr
, sqlite3VdbeCurrentAddr(v
)+2);
1526 sqlite3VdbeAddOp2(v
, OP_Goto
, 0, lblFlushDone
);
1527 if( pMWin
->eStart
==TK_FOLLOWING
){
1528 sqlite3VdbeJumpHere(v
, addrIfPos2
);
1531 if( pMWin
->eStart
==TK_CURRENT
1532 || pMWin
->eStart
==TK_PRECEDING
1533 || pMWin
->eStart
==TK_FOLLOWING
1535 int addrJumpHere
= 0;
1536 if( pMWin
->eStart
==TK_PRECEDING
){
1537 addrJumpHere
= sqlite3VdbeAddOp3(v
, OP_IfPos
, regStart
, 0 , 1);
1539 sqlite3VdbeAddOp2(v
, OP_Next
, csrStart
, sqlite3VdbeCurrentAddr(v
)+1);
1540 windowAggStep(pParse
, pMWin
, csrStart
, 1, regArg
, regSize
);
1542 sqlite3VdbeJumpHere(v
, addrJumpHere
);
1545 if( pMWin
->eEnd
==TK_FOLLOWING
){
1546 sqlite3VdbeJumpHere(v
, addrIfPos1
);
1548 sqlite3VdbeAddOp2(v
, OP_Goto
, 0, addrTop
);
1550 /* flush_partition_done: */
1551 sqlite3VdbeResolveLabel(v
, lblFlushDone
);
1552 sqlite3VdbeAddOp1(v
, OP_ResetSorter
, pMWin
->iEphCsr
);
1553 sqlite3VdbeAddOp1(v
, OP_Return
, regFlushPart
);
1555 /* Jump to here to skip over flush_partition */
1556 sqlite3VdbeJumpHere(v
, addrGoto
);
1560 ** This function does the work of sqlite3WindowCodeStep() for cases that
1561 ** would normally be handled by windowCodeDefaultStep() when there are
1562 ** one or more built-in window-functions that require the entire partition
1563 ** to be cached in a temp table before any rows can be returned. Additionally.
1564 ** "RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING" is always handled by
1567 ** Pseudo-code corresponding to the VM code generated by this function
1568 ** for each type of window follows.
1570 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1574 ** OpenDup (iEphCsr -> csrLead)
1577 ** foreach row (csrLead){
1579 ** AggFinal (xValue)
1580 ** for(i=0; i<ctr; i++){
1586 ** AggStep (csrLead)
1590 ** AggFinal (xFinalize)
1591 ** for(i=0; i<ctr; i++){
1596 ** ResetSorter (csr)
1599 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1601 ** As above, except that the "if( new peer )" branch is always taken.
1603 ** RANGE BETWEEN CURRENT ROW AND CURRENT ROW
1605 ** As above, except that each of the for() loops becomes:
1607 ** for(i=0; i<ctr; i++){
1609 ** AggStep (xInverse, iEphCsr)
1613 ** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
1617 ** OpenDup (iEphCsr -> csrLead)
1619 ** foreach row (csrLead) {
1620 ** AggStep (csrLead)
1622 ** foreach row (iEphCsr) {
1626 ** RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
1630 ** OpenDup (iEphCsr -> csrLead)
1632 ** foreach row (csrLead){
1633 ** AggStep (csrLead)
1637 ** foreach row (csrLead){
1639 ** AggFinal (xValue)
1640 ** for(i=0; i<ctr; i++){
1642 ** AggStep (xInverse, iEphCsr)
1650 ** AggFinal (xFinalize)
1651 ** for(i=0; i<ctr; i++){
1656 ** ResetSorter (csr)
1659 static void windowCodeCacheStep(
1666 Window
*pMWin
= p
->pWin
;
1667 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1670 ExprList
*pPart
= pMWin
->pPartition
;
1671 ExprList
*pOrderBy
= pMWin
->pOrderBy
;
1672 int nPeer
= pOrderBy
? pOrderBy
->nExpr
: 0;
1675 int addrGoto
; /* Address of Goto used to jump flush_par.. */
1676 int addrNext
; /* Jump here for next iteration of loop */
1681 int regArg
; /* Register array to martial function args */
1684 int bReverse
= pMWin
->pOrderBy
&& pMWin
->eStart
==TK_CURRENT
1685 && pMWin
->eEnd
==TK_UNBOUNDED
;
1687 assert( (pMWin
->eStart
==TK_UNBOUNDED
&& pMWin
->eEnd
==TK_CURRENT
)
1688 || (pMWin
->eStart
==TK_UNBOUNDED
&& pMWin
->eEnd
==TK_UNBOUNDED
)
1689 || (pMWin
->eStart
==TK_CURRENT
&& pMWin
->eEnd
==TK_CURRENT
)
1690 || (pMWin
->eStart
==TK_CURRENT
&& pMWin
->eEnd
==TK_UNBOUNDED
)
1693 lblEmpty
= sqlite3VdbeMakeLabel(v
);
1694 regNewPeer
= pParse
->nMem
+1;
1695 pParse
->nMem
+= nPeer
;
1697 /* Allocate register and label for the "flush_partition" sub-routine. */
1698 regFlushPart
= ++pParse
->nMem
;
1699 lblFlushPart
= sqlite3VdbeMakeLabel(v
);
1701 csrLead
= pParse
->nTab
++;
1702 regCtr
= ++pParse
->nMem
;
1704 windowPartitionCache(pParse
, p
, pWInfo
, regFlushPart
, lblFlushPart
, ®Size
);
1705 addrGoto
= sqlite3VdbeAddOp0(v
, OP_Goto
);
1707 /* Start of "flush_partition" */
1708 sqlite3VdbeResolveLabel(v
, lblFlushPart
);
1709 sqlite3VdbeAddOp2(v
, OP_Once
, 0, sqlite3VdbeCurrentAddr(v
)+2);
1710 sqlite3VdbeAddOp2(v
, OP_OpenDup
, csrLead
, pMWin
->iEphCsr
);
1712 /* Initialize the accumulator register for each window function to NULL */
1713 regArg
= windowInitAccum(pParse
, pMWin
);
1715 sqlite3VdbeAddOp2(v
, OP_Integer
, 0, regCtr
);
1716 sqlite3VdbeAddOp2(v
, OP_Rewind
, csrLead
, lblEmpty
);
1717 sqlite3VdbeAddOp2(v
, OP_Rewind
, pMWin
->iEphCsr
, lblEmpty
);
1720 int addr
= sqlite3VdbeCurrentAddr(v
);
1721 windowAggStep(pParse
, pMWin
, csrLead
, 0, regArg
, regSize
);
1722 sqlite3VdbeAddOp2(v
, OP_Next
, csrLead
, addr
);
1723 sqlite3VdbeAddOp2(v
, OP_Rewind
, csrLead
, lblEmpty
);
1725 addrNext
= sqlite3VdbeCurrentAddr(v
);
1727 if( pOrderBy
&& (pMWin
->eEnd
==TK_CURRENT
|| pMWin
->eStart
==TK_CURRENT
) ){
1728 int bCurrent
= (pMWin
->eStart
==TK_CURRENT
);
1729 int addrJump
= 0; /* Address of OP_Jump below */
1730 if( pMWin
->eType
==TK_RANGE
){
1731 int iOff
= pMWin
->nBufferCol
+ (pPart
? pPart
->nExpr
: 0);
1732 int regPeer
= pMWin
->regPart
+ (pPart
? pPart
->nExpr
: 0);
1733 KeyInfo
*pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
, pOrderBy
, 0, 0);
1734 for(k
=0; k
<nPeer
; k
++){
1735 sqlite3VdbeAddOp3(v
, OP_Column
, csrLead
, iOff
+k
, regNewPeer
+k
);
1737 addr
= sqlite3VdbeAddOp3(v
, OP_Compare
, regNewPeer
, regPeer
, nPeer
);
1738 sqlite3VdbeAppendP4(v
, (void*)pKeyInfo
, P4_KEYINFO
);
1739 addrJump
= sqlite3VdbeAddOp3(v
, OP_Jump
, addr
+2, 0, addr
+2);
1740 sqlite3VdbeAddOp3(v
, OP_Copy
, regNewPeer
, regPeer
, nPeer
-1);
1743 windowReturnRows(pParse
, pMWin
, regCtr
, regGosub
, addrGosub
,
1744 (bCurrent
? regArg
: 0), (bCurrent
? regSize
: 0)
1746 if( addrJump
) sqlite3VdbeJumpHere(v
, addrJump
);
1750 windowAggStep(pParse
, pMWin
, csrLead
, 0, regArg
, regSize
);
1752 sqlite3VdbeAddOp2(v
, OP_AddImm
, regCtr
, 1);
1753 sqlite3VdbeAddOp2(v
, OP_Next
, csrLead
, addrNext
);
1755 windowReturnRows(pParse
, pMWin
, regCtr
, regGosub
, addrGosub
, 0, 0);
1757 sqlite3VdbeResolveLabel(v
, lblEmpty
);
1758 sqlite3VdbeAddOp1(v
, OP_ResetSorter
, pMWin
->iEphCsr
);
1759 sqlite3VdbeAddOp1(v
, OP_Return
, regFlushPart
);
1761 /* Jump to here to skip over flush_partition */
1762 sqlite3VdbeJumpHere(v
, addrGoto
);
1767 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1770 ** if( new partition ){
1771 ** AggFinal (xFinalize)
1773 ** ResetSorter eph-table
1775 ** else if( new peer ){
1776 ** AggFinal (xValue)
1778 ** ResetSorter eph-table
1781 ** Insert (record into eph-table)
1782 ** sqlite3WhereEnd()
1783 ** AggFinal (xFinalize)
1786 ** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
1788 ** As above, except take no action for a "new peer". Invoke
1789 ** the sub-routine once only for each partition.
1791 ** RANGE BETWEEN CURRENT ROW AND CURRENT ROW
1793 ** As above, except that the "new peer" condition is handled in the
1794 ** same way as "new partition" (so there is no "else if" block).
1796 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1798 ** As above, except assume every row is a "new peer".
1800 static void windowCodeDefaultStep(
1807 Window
*pMWin
= p
->pWin
;
1808 Vdbe
*v
= sqlite3GetVdbe(pParse
);
1810 int iSubCsr
= p
->pSrc
->a
[0].iCursor
;
1811 int nSub
= p
->pSrc
->a
[0].pTab
->nCol
;
1812 int reg
= pParse
->nMem
+1;
1813 int regRecord
= reg
+nSub
;
1814 int regRowid
= regRecord
+1;
1816 ExprList
*pPart
= pMWin
->pPartition
;
1817 ExprList
*pOrderBy
= pMWin
->pOrderBy
;
1819 assert( pMWin
->eType
==TK_RANGE
1820 || (pMWin
->eStart
==TK_UNBOUNDED
&& pMWin
->eEnd
==TK_CURRENT
)
1823 assert( (pMWin
->eStart
==TK_UNBOUNDED
&& pMWin
->eEnd
==TK_CURRENT
)
1824 || (pMWin
->eStart
==TK_UNBOUNDED
&& pMWin
->eEnd
==TK_UNBOUNDED
)
1825 || (pMWin
->eStart
==TK_CURRENT
&& pMWin
->eEnd
==TK_CURRENT
)
1826 || (pMWin
->eStart
==TK_CURRENT
&& pMWin
->eEnd
==TK_UNBOUNDED
&& !pOrderBy
)
1829 if( pMWin
->eEnd
==TK_UNBOUNDED
){
1833 pParse
->nMem
+= nSub
+ 2;
1835 /* Martial the row returned by the sub-select into an array of
1837 for(k
=0; k
<nSub
; k
++){
1838 sqlite3VdbeAddOp3(v
, OP_Column
, iSubCsr
, k
, reg
+k
);
1841 /* Check if this is the start of a new partition or peer group. */
1842 if( pPart
|| pOrderBy
){
1843 int nPart
= (pPart
? pPart
->nExpr
: 0);
1846 int nPeer
= (pOrderBy
? pOrderBy
->nExpr
: 0);
1849 int regNewPart
= reg
+ pMWin
->nBufferCol
;
1850 KeyInfo
*pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
, pPart
, 0, 0);
1851 addr
= sqlite3VdbeAddOp3(v
, OP_Compare
, regNewPart
, pMWin
->regPart
,nPart
);
1852 sqlite3VdbeAppendP4(v
, (void*)pKeyInfo
, P4_KEYINFO
);
1853 addrJump
= sqlite3VdbeAddOp3(v
, OP_Jump
, addr
+2, 0, addr
+2);
1854 windowAggFinal(pParse
, pMWin
, 1);
1856 addrGoto
= sqlite3VdbeAddOp0(v
, OP_Goto
);
1861 int regNewPeer
= reg
+ pMWin
->nBufferCol
+ nPart
;
1862 int regPeer
= pMWin
->regPart
+ nPart
;
1864 if( addrJump
) sqlite3VdbeJumpHere(v
, addrJump
);
1865 if( pMWin
->eType
==TK_RANGE
){
1866 KeyInfo
*pKeyInfo
= sqlite3KeyInfoFromExprList(pParse
, pOrderBy
, 0, 0);
1867 addr
= sqlite3VdbeAddOp3(v
, OP_Compare
, regNewPeer
, regPeer
, nPeer
);
1868 sqlite3VdbeAppendP4(v
, (void*)pKeyInfo
, P4_KEYINFO
);
1869 addrJump
= sqlite3VdbeAddOp3(v
, OP_Jump
, addr
+2, 0, addr
+2);
1873 windowAggFinal(pParse
, pMWin
, pMWin
->eStart
==TK_CURRENT
);
1874 if( addrGoto
) sqlite3VdbeJumpHere(v
, addrGoto
);
1877 sqlite3VdbeAddOp2(v
, OP_Rewind
, pMWin
->iEphCsr
,sqlite3VdbeCurrentAddr(v
)+3);
1878 sqlite3VdbeAddOp2(v
, OP_Gosub
, regGosub
, addrGosub
);
1879 sqlite3VdbeAddOp2(v
, OP_Next
, pMWin
->iEphCsr
, sqlite3VdbeCurrentAddr(v
)-1);
1881 sqlite3VdbeAddOp1(v
, OP_ResetSorter
, pMWin
->iEphCsr
);
1883 v
, OP_Copy
, reg
+pMWin
->nBufferCol
, pMWin
->regPart
, nPart
+nPeer
-1
1886 if( addrJump
) sqlite3VdbeJumpHere(v
, addrJump
);
1889 /* Invoke step function for window functions */
1890 windowAggStep(pParse
, pMWin
, -1, 0, reg
, 0);
1892 /* Buffer the current row in the ephemeral table. */
1893 if( pMWin
->nBufferCol
>0 ){
1894 sqlite3VdbeAddOp3(v
, OP_MakeRecord
, reg
, pMWin
->nBufferCol
, regRecord
);
1896 sqlite3VdbeAddOp2(v
, OP_Blob
, 0, regRecord
);
1897 sqlite3VdbeAppendP4(v
, (void*)"", 0);
1899 sqlite3VdbeAddOp2(v
, OP_NewRowid
, pMWin
->iEphCsr
, regRowid
);
1900 sqlite3VdbeAddOp3(v
, OP_Insert
, pMWin
->iEphCsr
, regRecord
, regRowid
);
1902 /* End the database scan loop. */
1903 sqlite3WhereEnd(pWInfo
);
1905 windowAggFinal(pParse
, pMWin
, 1);
1906 sqlite3VdbeAddOp2(v
, OP_Rewind
, pMWin
->iEphCsr
,sqlite3VdbeCurrentAddr(v
)+3);
1907 sqlite3VdbeAddOp2(v
, OP_Gosub
, regGosub
, addrGosub
);
1908 sqlite3VdbeAddOp2(v
, OP_Next
, pMWin
->iEphCsr
, sqlite3VdbeCurrentAddr(v
)-1);
1912 ** Allocate and return a duplicate of the Window object indicated by the
1913 ** third argument. Set the Window.pOwner field of the new object to
1916 Window
*sqlite3WindowDup(sqlite3
*db
, Expr
*pOwner
, Window
*p
){
1919 pNew
= sqlite3DbMallocZero(db
, sizeof(Window
));
1921 pNew
->pFilter
= sqlite3ExprDup(db
, p
->pFilter
, 0);
1922 pNew
->pPartition
= sqlite3ExprListDup(db
, p
->pPartition
, 0);
1923 pNew
->pOrderBy
= sqlite3ExprListDup(db
, p
->pOrderBy
, 0);
1924 pNew
->eType
= p
->eType
;
1925 pNew
->eEnd
= p
->eEnd
;
1926 pNew
->eStart
= p
->eStart
;
1927 pNew
->pStart
= sqlite3ExprDup(db
, p
->pStart
, 0);
1928 pNew
->pEnd
= sqlite3ExprDup(db
, p
->pEnd
, 0);
1929 pNew
->pOwner
= pOwner
;
1936 ** sqlite3WhereBegin() has already been called for the SELECT statement
1937 ** passed as the second argument when this function is invoked. It generates
1938 ** code to populate the Window.regResult register for each window function and
1939 ** invoke the sub-routine at instruction addrGosub once for each row.
1940 ** This function calls sqlite3WhereEnd() before returning.
1942 void sqlite3WindowCodeStep(
1943 Parse
*pParse
, /* Parse context */
1944 Select
*p
, /* Rewritten SELECT statement */
1945 WhereInfo
*pWInfo
, /* Context returned by sqlite3WhereBegin() */
1946 int regGosub
, /* Register for OP_Gosub */
1947 int addrGosub
/* OP_Gosub here to return each row */
1949 Window
*pMWin
= p
->pWin
;
1951 /* There are three different functions that may be used to do the work
1952 ** of this one, depending on the window frame and the specific built-in
1953 ** window functions used (if any).
1955 ** windowCodeRowExprStep() handles all "ROWS" window frames, except for:
1957 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1959 ** The exception is because windowCodeRowExprStep() implements all window
1960 ** frame types by caching the entire partition in a temp table, and
1961 ** "ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW" is easy enough to
1962 ** implement without such a cache.
1964 ** windowCodeCacheStep() is used for:
1966 ** RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
1968 ** It is also used for anything not handled by windowCodeRowExprStep()
1969 ** that invokes a built-in window function that requires the entire
1970 ** partition to be cached in a temp table before any rows are returned
1971 ** (e.g. nth_value() or percent_rank()).
1973 ** Finally, assuming there is no built-in window function that requires
1974 ** the partition to be cached, windowCodeDefaultStep() is used for:
1976 ** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1977 ** RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
1978 ** RANGE BETWEEN CURRENT ROW AND CURRENT ROW
1979 ** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
1981 ** windowCodeDefaultStep() is the only one of the three functions that
1982 ** does not cache each partition in a temp table before beginning to
1985 if( pMWin
->eType
==TK_ROWS
1986 && (pMWin
->eStart
!=TK_UNBOUNDED
||pMWin
->eEnd
!=TK_CURRENT
||!pMWin
->pOrderBy
)
1988 windowCodeRowExprStep(pParse
, p
, pWInfo
, regGosub
, addrGosub
);
1991 int bCache
= 0; /* True to use CacheStep() */
1993 if( pMWin
->eStart
==TK_CURRENT
&& pMWin
->eEnd
==TK_UNBOUNDED
){
1996 for(pWin
=pMWin
; pWin
; pWin
=pWin
->pNextWin
){
1997 FuncDef
*pFunc
= pWin
->pFunc
;
1998 if( (pFunc
->funcFlags
& SQLITE_FUNC_WINDOW_SIZE
)
1999 || (pFunc
->xSFunc
==nth_valueStepFunc
)
2000 || (pFunc
->xSFunc
==first_valueStepFunc
)
2001 || (pFunc
->xSFunc
==leadStepFunc
)
2002 || (pFunc
->xSFunc
==lagStepFunc
)
2010 /* Otherwise, call windowCodeDefaultStep(). */
2012 windowCodeCacheStep(pParse
, p
, pWInfo
, regGosub
, addrGosub
);
2014 windowCodeDefaultStep(pParse
, p
, pWInfo
, regGosub
, addrGosub
);