1/*
2** 2018 May 08
3**
4** The author disclaims copyright to this source code. In place of
5** a legal notice, here is a blessing:
6**
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.
10**
11*************************************************************************
12*/
13#include "sqliteInt.h"
14
15#ifndef SQLITE_OMIT_WINDOWFUNC
16
17/*
18** SELECT REWRITING
19**
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
24** schema:
25**
26** CREATE TABLE t1(a, b, c, d, e, f, g);
27**
28** the statement:
29**
30** SELECT a+1, max(b) OVER (PARTITION BY c ORDER BY d) FROM t1 ORDER BY e;
31**
32** is transformed to:
33**
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
36** ) ORDER BY e;
37**
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:
42**
43** * FROM, WHERE, GROUP BY and HAVING clauses are all moved to
44** the sub-query.
45**
46** * ORDER BY, LIMIT and OFFSET remain part of the parent query.
47**
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.
52**
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:
56**
57** SELECT max(b) OVER (PARTITION BY c ORDER BY d),
58** min(e) OVER (PARTITION BY c ORDER BY d)
59** FROM t1;
60**
61** is transformed in the same way as the example above. However:
62**
63** SELECT max(b) OVER (PARTITION BY c ORDER BY d),
64** min(e) OVER (PARTITION BY a ORDER BY b)
65** FROM t1;
66**
67** Must be transformed to:
68**
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
72** ) ORDER BY c, d
73** ) ORDER BY e;
74**
75** so that both min() and max() may process rows in the order defined by
76** their respective window declarations.
77**
78** INTERFACE WITH SELECT.C
79**
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
84** sqlite3WhereEnd().
85**
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:
89**
90** * The results of all window-functions for the row are stored
91** in the associated Window.regResult registers.
92**
93** * The required terminal values are stored in the current row of
94** temp table Window.iEphCsr.
95**
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.
101**
102** BUILT-IN WINDOW FUNCTIONS
103**
104** This implementation features the following built-in window functions:
105**
106** row_number()
107** rank()
108** dense_rank()
109** percent_rank()
110** cume_dist()
111** ntile(N)
112** lead(expr [, offset [, default]])
113** lag(expr [, offset [, default]])
114** first_value(expr)
115** last_value(expr)
116** nth_value(expr, N)
117**
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:
130**
131** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
132**
133** See sqlite3WindowUpdate() for details.
134**
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.
139*/
140
141/*
142** Implementation of built-in window function row_number(). Assumes that the
143** window frame has been coerced to:
144**
145** ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
146*/
147static void row_numberStepFunc(
148 sqlite3_context *pCtx,
149 int nArg,
150 sqlite3_value **apArg
151){
152 i64 *p = (i64*)sqlite3_aggregate_context(pCtx, sizeof(*p));
153 if( p ) (*p)++;
154 UNUSED_PARAMETER(nArg);
155 UNUSED_PARAMETER(apArg);
156}
157static void row_numberValueFunc(sqlite3_context *pCtx){
158 i64 *p = (i64*)sqlite3_aggregate_context(pCtx, sizeof(*p));
159 sqlite3_result_int64(pCtx, (p ? *p : 0));
160}
161
162/*
163** Context object type used by rank(), dense_rank(), percent_rank() and
164** cume_dist().
165*/
166struct CallCount {
167 i64 nValue;
168 i64 nStep;
169 i64 nTotal;
170};
171
172/*
173** Implementation of built-in window function dense_rank(). Assumes that
174** the window frame has been set to:
175**
176** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
177*/
178static void dense_rankStepFunc(
179 sqlite3_context *pCtx,
180 int nArg,
181 sqlite3_value **apArg
182){
183 struct CallCount *p;
184 p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
185 if( p ) p->nStep = 1;
186 UNUSED_PARAMETER(nArg);
187 UNUSED_PARAMETER(apArg);
188}
189static void dense_rankValueFunc(sqlite3_context *pCtx){
190 struct CallCount *p;
191 p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
192 if( p ){
193 if( p->nStep ){
194 p->nValue++;
195 p->nStep = 0;
196 }
197 sqlite3_result_int64(pCtx, p->nValue);
198 }
199}
200
201/*
202** Implementation of built-in window function nth_value(). This
203** implementation is used in "slow mode" only - when the EXCLUDE clause
204** is not set to the default value "NO OTHERS".
205*/
206struct NthValueCtx {
207 i64 nStep;
208 sqlite3_value *pValue;
209};
210static void nth_valueStepFunc(
211 sqlite3_context *pCtx,
212 int nArg,
213 sqlite3_value **apArg
214){
215 struct NthValueCtx *p;
216 p = (struct NthValueCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));
217 if( p ){
218 i64 iVal;
219 switch( sqlite3_value_numeric_type(apArg[1]) ){
220 case SQLITE_INTEGER:
221 iVal = sqlite3_value_int64(apArg[1]);
222 break;
223 case SQLITE_FLOAT: {
224 double fVal = sqlite3_value_double(apArg[1]);
225 if( ((i64)fVal)!=fVal ) goto error_out;
226 iVal = (i64)fVal;
227 break;
228 }
229 default:
230 goto error_out;
231 }
232 if( iVal<=0 ) goto error_out;
233
234 p->nStep++;
235 if( iVal==p->nStep ){
236 p->pValue = sqlite3_value_dup(apArg[0]);
237 if( !p->pValue ){
238 sqlite3_result_error_nomem(pCtx);
239 }
240 }
241 }
242 UNUSED_PARAMETER(nArg);
243 UNUSED_PARAMETER(apArg);
244 return;
245
246 error_out:
247 sqlite3_result_error(
248 pCtx, "second argument to nth_value must be a positive integer", -1
249 );
250}
251static void nth_valueFinalizeFunc(sqlite3_context *pCtx){
252 struct NthValueCtx *p;
253 p = (struct NthValueCtx*)sqlite3_aggregate_context(pCtx, 0);
254 if( p && p->pValue ){
255 sqlite3_result_value(pCtx, p->pValue);
256 sqlite3_value_free(p->pValue);
257 p->pValue = 0;
258 }
259}
260#define nth_valueInvFunc noopStepFunc
261#define nth_valueValueFunc noopValueFunc
262
263static void first_valueStepFunc(
264 sqlite3_context *pCtx,
265 int nArg,
266 sqlite3_value **apArg
267){
268 struct NthValueCtx *p;
269 p = (struct NthValueCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));
270 if( p && p->pValue==0 ){
271 p->pValue = sqlite3_value_dup(apArg[0]);
272 if( !p->pValue ){
273 sqlite3_result_error_nomem(pCtx);
274 }
275 }
276 UNUSED_PARAMETER(nArg);
277 UNUSED_PARAMETER(apArg);
278}
279static void first_valueFinalizeFunc(sqlite3_context *pCtx){
280 struct NthValueCtx *p;
281 p = (struct NthValueCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));
282 if( p && p->pValue ){
283 sqlite3_result_value(pCtx, p->pValue);
284 sqlite3_value_free(p->pValue);
285 p->pValue = 0;
286 }
287}
288#define first_valueInvFunc noopStepFunc
289#define first_valueValueFunc noopValueFunc
290
291/*
292** Implementation of built-in window function rank(). Assumes that
293** the window frame has been set to:
294**
295** RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
296*/
297static void rankStepFunc(
298 sqlite3_context *pCtx,
299 int nArg,
300 sqlite3_value **apArg
301){
302 struct CallCount *p;
303 p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
304 if( p ){
305 p->nStep++;
306 if( p->nValue==0 ){
307 p->nValue = p->nStep;
308 }
309 }
310 UNUSED_PARAMETER(nArg);
311 UNUSED_PARAMETER(apArg);
312}
313static void rankValueFunc(sqlite3_context *pCtx){
314 struct CallCount *p;
315 p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
316 if( p ){
317 sqlite3_result_int64(pCtx, p->nValue);
318 p->nValue = 0;
319 }
320}
321
322/*
323** Implementation of built-in window function percent_rank(). Assumes that
324** the window frame has been set to:
325**
326** GROUPS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
327*/
328static void percent_rankStepFunc(
329 sqlite3_context *pCtx,
330 int nArg,
331 sqlite3_value **apArg
332){
333 struct CallCount *p;
334 UNUSED_PARAMETER(nArg); assert( nArg==0 );
335 UNUSED_PARAMETER(apArg);
336 p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
337 if( p ){
338 p->nTotal++;
339 }
340}
341static void percent_rankInvFunc(
342 sqlite3_context *pCtx,
343 int nArg,
344 sqlite3_value **apArg
345){
346 struct CallCount *p;
347 UNUSED_PARAMETER(nArg); assert( nArg==0 );
348 UNUSED_PARAMETER(apArg);
349 p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
350 p->nStep++;
351}
352static void percent_rankValueFunc(sqlite3_context *pCtx){
353 struct CallCount *p;
354 p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
355 if( p ){
356 p->nValue = p->nStep;
357 if( p->nTotal>1 ){
358 double r = (double)p->nValue / (double)(p->nTotal-1);
359 sqlite3_result_double(pCtx, r);
360 }else{
361 sqlite3_result_double(pCtx, 0.0);
362 }
363 }
364}
365#define percent_rankFinalizeFunc percent_rankValueFunc
366
367/*
368** Implementation of built-in window function cume_dist(). Assumes that
369** the window frame has been set to:
370**
371** GROUPS BETWEEN 1 FOLLOWING AND UNBOUNDED FOLLOWING
372*/
373static void cume_distStepFunc(
374 sqlite3_context *pCtx,
375 int nArg,
376 sqlite3_value **apArg
377){
378 struct CallCount *p;
379 UNUSED_PARAMETER(nArg); assert( nArg==0 );
380 UNUSED_PARAMETER(apArg);
381 p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
382 if( p ){
383 p->nTotal++;
384 }
385}
386static void cume_distInvFunc(
387 sqlite3_context *pCtx,
388 int nArg,
389 sqlite3_value **apArg
390){
391 struct CallCount *p;
392 UNUSED_PARAMETER(nArg); assert( nArg==0 );
393 UNUSED_PARAMETER(apArg);
394 p = (struct CallCount*)sqlite3_aggregate_context(pCtx, sizeof(*p));
395 p->nStep++;
396}
397static void cume_distValueFunc(sqlite3_context *pCtx){
398 struct CallCount *p;
399 p = (struct CallCount*)sqlite3_aggregate_context(pCtx, 0);
400 if( p ){
401 double r = (double)(p->nStep) / (double)(p->nTotal);
402 sqlite3_result_double(pCtx, r);
403 }
404}
405#define cume_distFinalizeFunc cume_distValueFunc
406
407/*
408** Context object for ntile() window function.
409*/
410struct NtileCtx {
411 i64 nTotal; /* Total rows in partition */
412 i64 nParam; /* Parameter passed to ntile(N) */
413 i64 iRow; /* Current row */
414};
415
416/*
417** Implementation of ntile(). This assumes that the window frame has
418** been coerced to:
419**
420** ROWS CURRENT ROW AND UNBOUNDED FOLLOWING
421*/
422static void ntileStepFunc(
423 sqlite3_context *pCtx,
424 int nArg,
425 sqlite3_value **apArg
426){
427 struct NtileCtx *p;
428 assert( nArg==1 ); UNUSED_PARAMETER(nArg);
429 p = (struct NtileCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));
430 if( p ){
431 if( p->nTotal==0 ){
432 p->nParam = sqlite3_value_int64(apArg[0]);
433 if( p->nParam<=0 ){
434 sqlite3_result_error(
435 pCtx, "argument of ntile must be a positive integer", -1
436 );
437 }
438 }
439 p->nTotal++;
440 }
441}
442static void ntileInvFunc(
443 sqlite3_context *pCtx,
444 int nArg,
445 sqlite3_value **apArg
446){
447 struct NtileCtx *p;
448 assert( nArg==1 ); UNUSED_PARAMETER(nArg);
449 UNUSED_PARAMETER(apArg);
450 p = (struct NtileCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));
451 p->iRow++;
452}
453static void ntileValueFunc(sqlite3_context *pCtx){
454 struct NtileCtx *p;
455 p = (struct NtileCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));
456 if( p && p->nParam>0 ){
457 int nSize = (p->nTotal / p->nParam);
458 if( nSize==0 ){
459 sqlite3_result_int64(pCtx, p->iRow+1);
460 }else{
461 i64 nLarge = p->nTotal - p->nParam*nSize;
462 i64 iSmall = nLarge*(nSize+1);
463 i64 iRow = p->iRow;
464
465 assert( (nLarge*(nSize+1) + (p->nParam-nLarge)*nSize)==p->nTotal );
466
467 if( iRow<iSmall ){
468 sqlite3_result_int64(pCtx, 1 + iRow/(nSize+1));
469 }else{
470 sqlite3_result_int64(pCtx, 1 + nLarge + (iRow-iSmall)/nSize);
471 }
472 }
473 }
474}
475#define ntileFinalizeFunc ntileValueFunc
476
477/*
478** Context object for last_value() window function.
479*/
480struct LastValueCtx {
481 sqlite3_value *pVal;
482 int nVal;
483};
484
485/*
486** Implementation of last_value().
487*/
488static void last_valueStepFunc(
489 sqlite3_context *pCtx,
490 int nArg,
491 sqlite3_value **apArg
492){
493 struct LastValueCtx *p;
494 UNUSED_PARAMETER(nArg);
495 p = (struct LastValueCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));
496 if( p ){
497 sqlite3_value_free(p->pVal);
498 p->pVal = sqlite3_value_dup(apArg[0]);
499 if( p->pVal==0 ){
500 sqlite3_result_error_nomem(pCtx);
501 }else{
502 p->nVal++;
503 }
504 }
505}
506static void last_valueInvFunc(
507 sqlite3_context *pCtx,
508 int nArg,
509 sqlite3_value **apArg
510){
511 struct LastValueCtx *p;
512 UNUSED_PARAMETER(nArg);
513 UNUSED_PARAMETER(apArg);
514 p = (struct LastValueCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));
515 if( ALWAYS(p) ){
516 p->nVal--;
517 if( p->nVal==0 ){
518 sqlite3_value_free(p->pVal);
519 p->pVal = 0;
520 }
521 }
522}
523static void last_valueValueFunc(sqlite3_context *pCtx){
524 struct LastValueCtx *p;
525 p = (struct LastValueCtx*)sqlite3_aggregate_context(pCtx, 0);
526 if( p && p->pVal ){
527 sqlite3_result_value(pCtx, p->pVal);
528 }
529}
530static void last_valueFinalizeFunc(sqlite3_context *pCtx){
531 struct LastValueCtx *p;
532 p = (struct LastValueCtx*)sqlite3_aggregate_context(pCtx, sizeof(*p));
533 if( p && p->pVal ){
534 sqlite3_result_value(pCtx, p->pVal);
535 sqlite3_value_free(p->pVal);
536 p->pVal = 0;
537 }
538}
539
540/*
541** Static names for the built-in window function names. These static
542** names are used, rather than string literals, so that FuncDef objects
543** can be associated with a particular window function by direct
544** comparison of the zName pointer. Example:
545**
546** if( pFuncDef->zName==row_valueName ){ ... }
547*/
548static const char row_numberName[] = "row_number";
549static const char dense_rankName[] = "dense_rank";
550static const char rankName[] = "rank";
551static const char percent_rankName[] = "percent_rank";
552static const char cume_distName[] = "cume_dist";
553static const char ntileName[] = "ntile";
554static const char last_valueName[] = "last_value";
555static const char nth_valueName[] = "nth_value";
556static const char first_valueName[] = "first_value";
557static const char leadName[] = "lead";
558static const char lagName[] = "lag";
559
560/*
561** No-op implementations of xStep() and xFinalize(). Used as place-holders
562** for built-in window functions that never call those interfaces.
563**
564** The noopValueFunc() is called but is expected to do nothing. The
565** noopStepFunc() is never called, and so it is marked with NO_TEST to
566** let the test coverage routine know not to expect this function to be
567** invoked.
568*/
569static void noopStepFunc( /*NO_TEST*/
570 sqlite3_context *p, /*NO_TEST*/
571 int n, /*NO_TEST*/
572 sqlite3_value **a /*NO_TEST*/
573){ /*NO_TEST*/
574 UNUSED_PARAMETER(p); /*NO_TEST*/
575 UNUSED_PARAMETER(n); /*NO_TEST*/
576 UNUSED_PARAMETER(a); /*NO_TEST*/
577 assert(0); /*NO_TEST*/
578} /*NO_TEST*/
579static void noopValueFunc(sqlite3_context *p){ UNUSED_PARAMETER(p); /*no-op*/ }
580
581/* Window functions that use all window interfaces: xStep, xFinal,
582** xValue, and xInverse */
583#define WINDOWFUNCALL(name,nArg,extra) { \
584 nArg, (SQLITE_FUNC_BUILTIN|SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0, \
585 name ## StepFunc, name ## FinalizeFunc, name ## ValueFunc, \
586 name ## InvFunc, name ## Name, {0} \
587}
588
589/* Window functions that are implemented using bytecode and thus have
590** no-op routines for their methods */
591#define WINDOWFUNCNOOP(name,nArg,extra) { \
592 nArg, (SQLITE_FUNC_BUILTIN|SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0, \
593 noopStepFunc, noopValueFunc, noopValueFunc, \
594 noopStepFunc, name ## Name, {0} \
595}
596
597/* Window functions that use all window interfaces: xStep, the
598** same routine for xFinalize and xValue and which never call
599** xInverse. */
600#define WINDOWFUNCX(name,nArg,extra) { \
601 nArg, (SQLITE_FUNC_BUILTIN|SQLITE_UTF8|SQLITE_FUNC_WINDOW|extra), 0, 0, \
602 name ## StepFunc, name ## ValueFunc, name ## ValueFunc, \
603 noopStepFunc, name ## Name, {0} \
604}
605
606
607/*
608** Register those built-in window functions that are not also aggregates.
609*/
610void sqlite3WindowFunctions(void){
611 static FuncDef aWindowFuncs[] = {
612 WINDOWFUNCX(row_number, 0, 0),
613 WINDOWFUNCX(dense_rank, 0, 0),
614 WINDOWFUNCX(rank, 0, 0),
615 WINDOWFUNCALL(percent_rank, 0, 0),
616 WINDOWFUNCALL(cume_dist, 0, 0),
617 WINDOWFUNCALL(ntile, 1, 0),
618 WINDOWFUNCALL(last_value, 1, 0),
619 WINDOWFUNCALL(nth_value, 2, 0),
620 WINDOWFUNCALL(first_value, 1, 0),
621 WINDOWFUNCNOOP(lead, 1, 0),
622 WINDOWFUNCNOOP(lead, 2, 0),
623 WINDOWFUNCNOOP(lead, 3, 0),
624 WINDOWFUNCNOOP(lag, 1, 0),
625 WINDOWFUNCNOOP(lag, 2, 0),
626 WINDOWFUNCNOOP(lag, 3, 0),
627 };
628 sqlite3InsertBuiltinFuncs(aWindowFuncs, ArraySize(aWindowFuncs));
629}
630
631static Window *windowFind(Parse *pParse, Window *pList, const char *zName){
632 Window *p;
633 for(p=pList; p; p=p->pNextWin){
634 if( sqlite3StrICmp(p->zName, zName)==0 ) break;
635 }
636 if( p==0 ){
637 sqlite3ErrorMsg(pParse, "no such window: %s", zName);
638 }
639 return p;
640}
641
642/*
643** This function is called immediately after resolving the function name
644** for a window function within a SELECT statement. Argument pList is a
645** linked list of WINDOW definitions for the current SELECT statement.
646** Argument pFunc is the function definition just resolved and pWin
647** is the Window object representing the associated OVER clause. This
648** function updates the contents of pWin as follows:
649**
650** * If the OVER clause refered to a named window (as in "max(x) OVER win"),
651** search list pList for a matching WINDOW definition, and update pWin
652** accordingly. If no such WINDOW clause can be found, leave an error
653** in pParse.
654**
655** * If the function is a built-in window function that requires the
656** window to be coerced (see "BUILT-IN WINDOW FUNCTIONS" at the top
657** of this file), pWin is updated here.
658*/
659void sqlite3WindowUpdate(
660 Parse *pParse,
661 Window *pList, /* List of named windows for this SELECT */
662 Window *pWin, /* Window frame to update */
663 FuncDef *pFunc /* Window function definition */
664){
665 if( pWin->zName && pWin->eFrmType==0 ){
666 Window *p = windowFind(pParse, pList, pWin->zName);
667 if( p==0 ) return;
668 pWin->pPartition = sqlite3ExprListDup(pParse->db, p->pPartition, 0);
669 pWin->pOrderBy = sqlite3ExprListDup(pParse->db, p->pOrderBy, 0);
670 pWin->pStart = sqlite3ExprDup(pParse->db, p->pStart, 0);
671 pWin->pEnd = sqlite3ExprDup(pParse->db, p->pEnd, 0);
672 pWin->eStart = p->eStart;
673 pWin->eEnd = p->eEnd;
674 pWin->eFrmType = p->eFrmType;
675 pWin->eExclude = p->eExclude;
676 }else{
677 sqlite3WindowChain(pParse, pWin, pList);
678 }
679 if( (pWin->eFrmType==TK_RANGE)
680 && (pWin->pStart || pWin->pEnd)
681 && (pWin->pOrderBy==0 || pWin->pOrderBy->nExpr!=1)
682 ){
683 sqlite3ErrorMsg(pParse,
684 "RANGE with offset PRECEDING/FOLLOWING requires one ORDER BY expression"
685 );
686 }else
687 if( pFunc->funcFlags & SQLITE_FUNC_WINDOW ){
688 sqlite3 *db = pParse->db;
689 if( pWin->pFilter ){
690 sqlite3ErrorMsg(pParse,
691 "FILTER clause may only be used with aggregate window functions"
692 );
693 }else{
694 struct WindowUpdate {
695 const char *zFunc;
696 int eFrmType;
697 int eStart;
698 int eEnd;
699 } aUp[] = {
700 { row_numberName, TK_ROWS, TK_UNBOUNDED, TK_CURRENT },
701 { dense_rankName, TK_RANGE, TK_UNBOUNDED, TK_CURRENT },
702 { rankName, TK_RANGE, TK_UNBOUNDED, TK_CURRENT },
703 { percent_rankName, TK_GROUPS, TK_CURRENT, TK_UNBOUNDED },
704 { cume_distName, TK_GROUPS, TK_FOLLOWING, TK_UNBOUNDED },
705 { ntileName, TK_ROWS, TK_CURRENT, TK_UNBOUNDED },
706 { leadName, TK_ROWS, TK_UNBOUNDED, TK_UNBOUNDED },
707 { lagName, TK_ROWS, TK_UNBOUNDED, TK_CURRENT },
708 };
709 int i;
710 for(i=0; i<ArraySize(aUp); i++){
711 if( pFunc->zName==aUp[i].zFunc ){
712 sqlite3ExprDelete(db, pWin->pStart);
713 sqlite3ExprDelete(db, pWin->pEnd);
714 pWin->pEnd = pWin->pStart = 0;
715 pWin->eFrmType = aUp[i].eFrmType;
716 pWin->eStart = aUp[i].eStart;
717 pWin->eEnd = aUp[i].eEnd;
718 pWin->eExclude = 0;
719 if( pWin->eStart==TK_FOLLOWING ){
720 pWin->pStart = sqlite3Expr(db, TK_INTEGER, "1");
721 }
722 break;
723 }
724 }
725 }
726 }
727 pWin->pWFunc = pFunc;
728}
729
730/*
731** Context object passed through sqlite3WalkExprList() to
732** selectWindowRewriteExprCb() by selectWindowRewriteEList().
733*/
734typedef struct WindowRewrite WindowRewrite;
735struct WindowRewrite {
736 Window *pWin;
737 SrcList *pSrc;
738 ExprList *pSub;
739 Table *pTab;
740 Select *pSubSelect; /* Current sub-select, if any */
741};
742
743/*
744** Callback function used by selectWindowRewriteEList(). If necessary,
745** this function appends to the output expression-list and updates
746** expression (*ppExpr) in place.
747*/
748static int selectWindowRewriteExprCb(Walker *pWalker, Expr *pExpr){
749 struct WindowRewrite *p = pWalker->u.pRewrite;
750 Parse *pParse = pWalker->pParse;
751 assert( p!=0 );
752 assert( p->pWin!=0 );
753
754 /* If this function is being called from within a scalar sub-select
755 ** that used by the SELECT statement being processed, only process
756 ** TK_COLUMN expressions that refer to it (the outer SELECT). Do
757 ** not process aggregates or window functions at all, as they belong
758 ** to the scalar sub-select. */
759 if( p->pSubSelect ){
760 if( pExpr->op!=TK_COLUMN ){
761 return WRC_Continue;
762 }else{
763 int nSrc = p->pSrc->nSrc;
764 int i;
765 for(i=0; i<nSrc; i++){
766 if( pExpr->iTable==p->pSrc->a[i].iCursor ) break;
767 }
768 if( i==nSrc ) return WRC_Continue;
769 }
770 }
771
772 switch( pExpr->op ){
773
774 case TK_FUNCTION:
775 if( !ExprHasProperty(pExpr, EP_WinFunc) ){
776 break;
777 }else{
778 Window *pWin;
779 for(pWin=p->pWin; pWin; pWin=pWin->pNextWin){
780 if( pExpr->y.pWin==pWin ){
781 assert( pWin->pOwner==pExpr );
782 return WRC_Prune;
783 }
784 }
785 }
786 /* no break */ deliberate_fall_through
787
788 case TK_AGG_FUNCTION:
789 case TK_COLUMN: {
790 int iCol = -1;
791 if( pParse->db->mallocFailed ) return WRC_Abort;
792 if( p->pSub ){
793 int i;
794 for(i=0; i<p->pSub->nExpr; i++){
795 if( 0==sqlite3ExprCompare(0, p->pSub->a[i].pExpr, pExpr, -1) ){
796 iCol = i;
797 break;
798 }
799 }
800 }
801 if( iCol<0 ){
802 Expr *pDup = sqlite3ExprDup(pParse->db, pExpr, 0);
803 if( pDup && pDup->op==TK_AGG_FUNCTION ) pDup->op = TK_FUNCTION;
804 p->pSub = sqlite3ExprListAppend(pParse, p->pSub, pDup);
805 }
806 if( p->pSub ){
807 int f = pExpr->flags & EP_Collate;
808 assert( ExprHasProperty(pExpr, EP_Static)==0 );
809 ExprSetProperty(pExpr, EP_Static);
810 sqlite3ExprDelete(pParse->db, pExpr);
811 ExprClearProperty(pExpr, EP_Static);
812 memset(pExpr, 0, sizeof(Expr));
813
814 pExpr->op = TK_COLUMN;
815 pExpr->iColumn = (iCol<0 ? p->pSub->nExpr-1: iCol);
816 pExpr->iTable = p->pWin->iEphCsr;
817 pExpr->y.pTab = p->pTab;
818 pExpr->flags = f;
819 }
820 if( pParse->db->mallocFailed ) return WRC_Abort;
821 break;
822 }
823
824 default: /* no-op */
825 break;
826 }
827
828 return WRC_Continue;
829}
830static int selectWindowRewriteSelectCb(Walker *pWalker, Select *pSelect){
831 struct WindowRewrite *p = pWalker->u.pRewrite;
832 Select *pSave = p->pSubSelect;
833 if( pSave==pSelect ){
834 return WRC_Continue;
835 }else{
836 p->pSubSelect = pSelect;
837 sqlite3WalkSelect(pWalker, pSelect);
838 p->pSubSelect = pSave;
839 }
840 return WRC_Prune;
841}
842
843
844/*
845** Iterate through each expression in expression-list pEList. For each:
846**
847** * TK_COLUMN,
848** * aggregate function, or
849** * window function with a Window object that is not a member of the
850** Window list passed as the second argument (pWin).
851**
852** Append the node to output expression-list (*ppSub). And replace it
853** with a TK_COLUMN that reads the (N-1)th element of table
854** pWin->iEphCsr, where N is the number of elements in (*ppSub) after
855** appending the new one.
856*/
857static void selectWindowRewriteEList(
858 Parse *pParse,
859 Window *pWin,
860 SrcList *pSrc,
861 ExprList *pEList, /* Rewrite expressions in this list */
862 Table *pTab,
863 ExprList **ppSub /* IN/OUT: Sub-select expression-list */
864){
865 Walker sWalker;
866 WindowRewrite sRewrite;
867
868 assert( pWin!=0 );
869 memset(&sWalker, 0, sizeof(Walker));
870 memset(&sRewrite, 0, sizeof(WindowRewrite));
871
872 sRewrite.pSub = *ppSub;
873 sRewrite.pWin = pWin;
874 sRewrite.pSrc = pSrc;
875 sRewrite.pTab = pTab;
876
877 sWalker.pParse = pParse;
878 sWalker.xExprCallback = selectWindowRewriteExprCb;
879 sWalker.xSelectCallback = selectWindowRewriteSelectCb;
880 sWalker.u.pRewrite = &sRewrite;
881
882 (void)sqlite3WalkExprList(&sWalker, pEList);
883
884 *ppSub = sRewrite.pSub;
885}
886
887/*
888** Append a copy of each expression in expression-list pAppend to
889** expression list pList. Return a pointer to the result list.
890*/
891static ExprList *exprListAppendList(
892 Parse *pParse, /* Parsing context */
893 ExprList *pList, /* List to which to append. Might be NULL */
894 ExprList *pAppend, /* List of values to append. Might be NULL */
895 int bIntToNull
896){
897 if( pAppend ){
898 int i;
899 int nInit = pList ? pList->nExpr : 0;
900 for(i=0; i<pAppend->nExpr; i++){
901 sqlite3 *db = pParse->db;
902 Expr *pDup = sqlite3ExprDup(db, pAppend->a[i].pExpr, 0);
903 if( db->mallocFailed ){
904 sqlite3ExprDelete(db, pDup);
905 break;
906 }
907 if( bIntToNull ){
908 int iDummy;
909 Expr *pSub;
910 pSub = sqlite3ExprSkipCollateAndLikely(pDup);
911 if( sqlite3ExprIsInteger(pSub, &iDummy) ){
912 pSub->op = TK_NULL;
913 pSub->flags &= ~(EP_IntValue|EP_IsTrue|EP_IsFalse);
914 pSub->u.zToken = 0;
915 }
916 }
917 pList = sqlite3ExprListAppend(pParse, pList, pDup);
918 if( pList ) pList->a[nInit+i].fg.sortFlags = pAppend->a[i].fg.sortFlags;
919 }
920 }
921 return pList;
922}
923
924/*
925** When rewriting a query, if the new subquery in the FROM clause
926** contains TK_AGG_FUNCTION nodes that refer to an outer query,
927** then we have to increase the Expr->op2 values of those nodes
928** due to the extra subquery layer that was added.
929**
930** See also the incrAggDepth() routine in resolve.c
931*/
932static int sqlite3WindowExtraAggFuncDepth(Walker *pWalker, Expr *pExpr){
933 if( pExpr->op==TK_AGG_FUNCTION
934 && pExpr->op2>=pWalker->walkerDepth
935 ){
936 pExpr->op2++;
937 }
938 return WRC_Continue;
939}
940
941static int disallowAggregatesInOrderByCb(Walker *pWalker, Expr *pExpr){
942 if( pExpr->op==TK_AGG_FUNCTION && pExpr->pAggInfo==0 ){
943 assert( !ExprHasProperty(pExpr, EP_IntValue) );
944 sqlite3ErrorMsg(pWalker->pParse,
945 "misuse of aggregate: %s()", pExpr->u.zToken);
946 }
947 return WRC_Continue;
948}
949
950/*
951** If the SELECT statement passed as the second argument does not invoke
952** any SQL window functions, this function is a no-op. Otherwise, it
953** rewrites the SELECT statement so that window function xStep functions
954** are invoked in the correct order as described under "SELECT REWRITING"
955** at the top of this file.
956*/
957int sqlite3WindowRewrite(Parse *pParse, Select *p){
958 int rc = SQLITE_OK;
959 if( p->pWin
960 && p->pPrior==0
961 && ALWAYS((p->selFlags & SF_WinRewrite)==0)
962 && ALWAYS(!IN_RENAME_OBJECT)
963 ){
964 Vdbe *v = sqlite3GetVdbe(pParse);
965 sqlite3 *db = pParse->db;
966 Select *pSub = 0; /* The subquery */
967 SrcList *pSrc = p->pSrc;
968 Expr *pWhere = p->pWhere;
969 ExprList *pGroupBy = p->pGroupBy;
970 Expr *pHaving = p->pHaving;
971 ExprList *pSort = 0;
972
973 ExprList *pSublist = 0; /* Expression list for sub-query */
974 Window *pMWin = p->pWin; /* Main window object */
975 Window *pWin; /* Window object iterator */
976 Table *pTab;
977 Walker w;
978
979 u32 selFlags = p->selFlags;
980
981 pTab = sqlite3DbMallocZero(db, sizeof(Table));
982 if( pTab==0 ){
983 return sqlite3ErrorToParser(db, SQLITE_NOMEM);
984 }
985 sqlite3AggInfoPersistWalkerInit(&w, pParse);
986 sqlite3WalkSelect(&w, p);
987 if( (p->selFlags & SF_Aggregate)==0 ){
988 w.xExprCallback = disallowAggregatesInOrderByCb;
989 w.xSelectCallback = 0;
990 sqlite3WalkExprList(&w, p->pOrderBy);
991 }
992
993 p->pSrc = 0;
994 p->pWhere = 0;
995 p->pGroupBy = 0;
996 p->pHaving = 0;
997 p->selFlags &= ~SF_Aggregate;
998 p->selFlags |= SF_WinRewrite;
999
1000 /* Create the ORDER BY clause for the sub-select. This is the concatenation
1001 ** of the window PARTITION and ORDER BY clauses. Then, if this makes it
1002 ** redundant, remove the ORDER BY from the parent SELECT. */
1003 pSort = exprListAppendList(pParse, 0, pMWin->pPartition, 1);
1004 pSort = exprListAppendList(pParse, pSort, pMWin->pOrderBy, 1);
1005 if( pSort && p->pOrderBy && p->pOrderBy->nExpr<=pSort->nExpr ){
1006 int nSave = pSort->nExpr;
1007 pSort->nExpr = p->pOrderBy->nExpr;
1008 if( sqlite3ExprListCompare(pSort, p->pOrderBy, -1)==0 ){
1009 sqlite3ExprListDelete(db, p->pOrderBy);
1010 p->pOrderBy = 0;
1011 }
1012 pSort->nExpr = nSave;
1013 }
1014
1015 /* Assign a cursor number for the ephemeral table used to buffer rows.
1016 ** The OpenEphemeral instruction is coded later, after it is known how
1017 ** many columns the table will have. */
1018 pMWin->iEphCsr = pParse->nTab++;
1019 pParse->nTab += 3;
1020
1021 selectWindowRewriteEList(pParse, pMWin, pSrc, p->pEList, pTab, &pSublist);
1022 selectWindowRewriteEList(pParse, pMWin, pSrc, p->pOrderBy, pTab, &pSublist);
1023 pMWin->nBufferCol = (pSublist ? pSublist->nExpr : 0);
1024
1025 /* Append the PARTITION BY and ORDER BY expressions to the to the
1026 ** sub-select expression list. They are required to figure out where
1027 ** boundaries for partitions and sets of peer rows lie. */
1028 pSublist = exprListAppendList(pParse, pSublist, pMWin->pPartition, 0);
1029 pSublist = exprListAppendList(pParse, pSublist, pMWin->pOrderBy, 0);
1030
1031 /* Append the arguments passed to each window function to the
1032 ** sub-select expression list. Also allocate two registers for each
1033 ** window function - one for the accumulator, another for interim
1034 ** results. */
1035 for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
1036 ExprList *pArgs;
1037 assert( ExprUseXList(pWin->pOwner) );
1038 assert( pWin->pWFunc!=0 );
1039 pArgs = pWin->pOwner->x.pList;
1040 if( pWin->pWFunc->funcFlags & SQLITE_FUNC_SUBTYPE ){
1041 selectWindowRewriteEList(pParse, pMWin, pSrc, pArgs, pTab, &pSublist);
1042 pWin->iArgCol = (pSublist ? pSublist->nExpr : 0);
1043 pWin->bExprArgs = 1;
1044 }else{
1045 pWin->iArgCol = (pSublist ? pSublist->nExpr : 0);
1046 pSublist = exprListAppendList(pParse, pSublist, pArgs, 0);
1047 }
1048 if( pWin->pFilter ){
1049 Expr *pFilter = sqlite3ExprDup(db, pWin->pFilter, 0);
1050 pSublist = sqlite3ExprListAppend(pParse, pSublist, pFilter);
1051 }
1052 pWin->regAccum = ++pParse->nMem;
1053 pWin->regResult = ++pParse->nMem;
1054 sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);
1055 }
1056
1057 /* If there is no ORDER BY or PARTITION BY clause, and the window
1058 ** function accepts zero arguments, and there are no other columns
1059 ** selected (e.g. "SELECT row_number() OVER () FROM t1"), it is possible
1060 ** that pSublist is still NULL here. Add a constant expression here to
1061 ** keep everything legal in this case.
1062 */
1063 if( pSublist==0 ){
1064 pSublist = sqlite3ExprListAppend(pParse, 0,
1065 sqlite3Expr(db, TK_INTEGER, "0")
1066 );
1067 }
1068
1069 pSub = sqlite3SelectNew(
1070 pParse, pSublist, pSrc, pWhere, pGroupBy, pHaving, pSort, 0, 0
1071 );
1072 SELECTTRACE(1,pParse,pSub,
1073 ("New window-function subquery in FROM clause of (%u/%p)\n",
1074 p->selId, p));
1075 p->pSrc = sqlite3SrcListAppend(pParse, 0, 0, 0);
1076 assert( pSub!=0 || p->pSrc==0 ); /* Due to db->mallocFailed test inside
1077 ** of sqlite3DbMallocRawNN() called from
1078 ** sqlite3SrcListAppend() */
1079 if( p->pSrc ){
1080 Table *pTab2;
1081 p->pSrc->a[0].pSelect = pSub;
1082 sqlite3SrcListAssignCursors(pParse, p->pSrc);
1083 pSub->selFlags |= SF_Expanded|SF_OrderByReqd;
1084 pTab2 = sqlite3ResultSetOfSelect(pParse, pSub, SQLITE_AFF_NONE);
1085 pSub->selFlags |= (selFlags & SF_Aggregate);
1086 if( pTab2==0 ){
1087 /* Might actually be some other kind of error, but in that case
1088 ** pParse->nErr will be set, so if SQLITE_NOMEM is set, we will get
1089 ** the correct error message regardless. */
1090 rc = SQLITE_NOMEM;
1091 }else{
1092 memcpy(pTab, pTab2, sizeof(Table));
1093 pTab->tabFlags |= TF_Ephemeral;
1094 p->pSrc->a[0].pTab = pTab;
1095 pTab = pTab2;
1096 memset(&w, 0, sizeof(w));
1097 w.xExprCallback = sqlite3WindowExtraAggFuncDepth;
1098 w.xSelectCallback = sqlite3WalkerDepthIncrease;
1099 w.xSelectCallback2 = sqlite3WalkerDepthDecrease;
1100 sqlite3WalkSelect(&w, pSub);
1101 }
1102 }else{
1103 sqlite3SelectDelete(db, pSub);
1104 }
1105 if( db->mallocFailed ) rc = SQLITE_NOMEM;
1106
1107 /* Defer deleting the temporary table pTab because if an error occurred,
1108 ** there could still be references to that table embedded in the
1109 ** result-set or ORDER BY clause of the SELECT statement p. */
1110 sqlite3ParserAddCleanup(pParse, sqlite3DbFree, pTab);
1111 }
1112
1113 assert( rc==SQLITE_OK || pParse->nErr!=0 );
1114 return rc;
1115}
1116
1117/*
1118** Unlink the Window object from the Select to which it is attached,
1119** if it is attached.
1120*/
1121void sqlite3WindowUnlinkFromSelect(Window *p){
1122 if( p->ppThis ){
1123 *p->ppThis = p->pNextWin;
1124 if( p->pNextWin ) p->pNextWin->ppThis = p->ppThis;
1125 p->ppThis = 0;
1126 }
1127}
1128
1129/*
1130** Free the Window object passed as the second argument.
1131*/
1132void sqlite3WindowDelete(sqlite3 *db, Window *p){
1133 if( p ){
1134 sqlite3WindowUnlinkFromSelect(p);
1135 sqlite3ExprDelete(db, p->pFilter);
1136 sqlite3ExprListDelete(db, p->pPartition);
1137 sqlite3ExprListDelete(db, p->pOrderBy);
1138 sqlite3ExprDelete(db, p->pEnd);
1139 sqlite3ExprDelete(db, p->pStart);
1140 sqlite3DbFree(db, p->zName);
1141 sqlite3DbFree(db, p->zBase);
1142 sqlite3DbFree(db, p);
1143 }
1144}
1145
1146/*
1147** Free the linked list of Window objects starting at the second argument.
1148*/
1149void sqlite3WindowListDelete(sqlite3 *db, Window *p){
1150 while( p ){
1151 Window *pNext = p->pNextWin;
1152 sqlite3WindowDelete(db, p);
1153 p = pNext;
1154 }
1155}
1156
1157/*
1158** The argument expression is an PRECEDING or FOLLOWING offset. The
1159** value should be a non-negative integer. If the value is not a
1160** constant, change it to NULL. The fact that it is then a non-negative
1161** integer will be caught later. But it is important not to leave
1162** variable values in the expression tree.
1163*/
1164static Expr *sqlite3WindowOffsetExpr(Parse *pParse, Expr *pExpr){
1165 if( 0==sqlite3ExprIsConstant(pExpr) ){
1166 if( IN_RENAME_OBJECT ) sqlite3RenameExprUnmap(pParse, pExpr);
1167 sqlite3ExprDelete(pParse->db, pExpr);
1168 pExpr = sqlite3ExprAlloc(pParse->db, TK_NULL, 0, 0);
1169 }
1170 return pExpr;
1171}
1172
1173/*
1174** Allocate and return a new Window object describing a Window Definition.
1175*/
1176Window *sqlite3WindowAlloc(
1177 Parse *pParse, /* Parsing context */
1178 int eType, /* Frame type. TK_RANGE, TK_ROWS, TK_GROUPS, or 0 */
1179 int eStart, /* Start type: CURRENT, PRECEDING, FOLLOWING, UNBOUNDED */
1180 Expr *pStart, /* Start window size if TK_PRECEDING or FOLLOWING */
1181 int eEnd, /* End type: CURRENT, FOLLOWING, TK_UNBOUNDED, PRECEDING */
1182 Expr *pEnd, /* End window size if TK_FOLLOWING or PRECEDING */
1183 u8 eExclude /* EXCLUDE clause */
1184){
1185 Window *pWin = 0;
1186 int bImplicitFrame = 0;
1187
1188 /* Parser assures the following: */
1189 assert( eType==0 || eType==TK_RANGE || eType==TK_ROWS || eType==TK_GROUPS );
1190 assert( eStart==TK_CURRENT || eStart==TK_PRECEDING
1191 || eStart==TK_UNBOUNDED || eStart==TK_FOLLOWING );
1192 assert( eEnd==TK_CURRENT || eEnd==TK_FOLLOWING
1193 || eEnd==TK_UNBOUNDED || eEnd==TK_PRECEDING );
1194 assert( (eStart==TK_PRECEDING || eStart==TK_FOLLOWING)==(pStart!=0) );
1195 assert( (eEnd==TK_FOLLOWING || eEnd==TK_PRECEDING)==(pEnd!=0) );
1196
1197 if( eType==0 ){
1198 bImplicitFrame = 1;
1199 eType = TK_RANGE;
1200 }
1201
1202 /* Additionally, the
1203 ** starting boundary type may not occur earlier in the following list than
1204 ** the ending boundary type:
1205 **
1206 ** UNBOUNDED PRECEDING
1207 ** <expr> PRECEDING
1208 ** CURRENT ROW
1209 ** <expr> FOLLOWING
1210 ** UNBOUNDED FOLLOWING
1211 **
1212 ** The parser ensures that "UNBOUNDED PRECEDING" cannot be used as an ending
1213 ** boundary, and than "UNBOUNDED FOLLOWING" cannot be used as a starting
1214 ** frame boundary.
1215 */
1216 if( (eStart==TK_CURRENT && eEnd==TK_PRECEDING)
1217 || (eStart==TK_FOLLOWING && (eEnd==TK_PRECEDING || eEnd==TK_CURRENT))
1218 ){
1219 sqlite3ErrorMsg(pParse, "unsupported frame specification");
1220 goto windowAllocErr;
1221 }
1222
1223 pWin = (Window*)sqlite3DbMallocZero(pParse->db, sizeof(Window));
1224 if( pWin==0 ) goto windowAllocErr;
1225 pWin->eFrmType = eType;
1226 pWin->eStart = eStart;
1227 pWin->eEnd = eEnd;
1228 if( eExclude==0 && OptimizationDisabled(pParse->db, SQLITE_WindowFunc) ){
1229 eExclude = TK_NO;
1230 }
1231 pWin->eExclude = eExclude;
1232 pWin->bImplicitFrame = bImplicitFrame;
1233 pWin->pEnd = sqlite3WindowOffsetExpr(pParse, pEnd);
1234 pWin->pStart = sqlite3WindowOffsetExpr(pParse, pStart);
1235 return pWin;
1236
1237windowAllocErr:
1238 sqlite3ExprDelete(pParse->db, pEnd);
1239 sqlite3ExprDelete(pParse->db, pStart);
1240 return 0;
1241}
1242
1243/*
1244** Attach PARTITION and ORDER BY clauses pPartition and pOrderBy to window
1245** pWin. Also, if parameter pBase is not NULL, set pWin->zBase to the
1246** equivalent nul-terminated string.
1247*/
1248Window *sqlite3WindowAssemble(
1249 Parse *pParse,
1250 Window *pWin,
1251 ExprList *pPartition,
1252 ExprList *pOrderBy,
1253 Token *pBase
1254){
1255 if( pWin ){
1256 pWin->pPartition = pPartition;
1257 pWin->pOrderBy = pOrderBy;
1258 if( pBase ){
1259 pWin->zBase = sqlite3DbStrNDup(pParse->db, pBase->z, pBase->n);
1260 }
1261 }else{
1262 sqlite3ExprListDelete(pParse->db, pPartition);
1263 sqlite3ExprListDelete(pParse->db, pOrderBy);
1264 }
1265 return pWin;
1266}
1267
1268/*
1269** Window *pWin has just been created from a WINDOW clause. Tokne pBase
1270** is the base window. Earlier windows from the same WINDOW clause are
1271** stored in the linked list starting at pWin->pNextWin. This function
1272** either updates *pWin according to the base specification, or else
1273** leaves an error in pParse.
1274*/
1275void sqlite3WindowChain(Parse *pParse, Window *pWin, Window *pList){
1276 if( pWin->zBase ){
1277 sqlite3 *db = pParse->db;
1278 Window *pExist = windowFind(pParse, pList, pWin->zBase);
1279 if( pExist ){
1280 const char *zErr = 0;
1281 /* Check for errors */
1282 if( pWin->pPartition ){
1283 zErr = "PARTITION clause";
1284 }else if( pExist->pOrderBy && pWin->pOrderBy ){
1285 zErr = "ORDER BY clause";
1286 }else if( pExist->bImplicitFrame==0 ){
1287 zErr = "frame specification";
1288 }
1289 if( zErr ){
1290 sqlite3ErrorMsg(pParse,
1291 "cannot override %s of window: %s", zErr, pWin->zBase
1292 );
1293 }else{
1294 pWin->pPartition = sqlite3ExprListDup(db, pExist->pPartition, 0);
1295 if( pExist->pOrderBy ){
1296 assert( pWin->pOrderBy==0 );
1297 pWin->pOrderBy = sqlite3ExprListDup(db, pExist->pOrderBy, 0);
1298 }
1299 sqlite3DbFree(db, pWin->zBase);
1300 pWin->zBase = 0;
1301 }
1302 }
1303 }
1304}
1305
1306/*
1307** Attach window object pWin to expression p.
1308*/
1309void sqlite3WindowAttach(Parse *pParse, Expr *p, Window *pWin){
1310 if( p ){
1311 assert( p->op==TK_FUNCTION );
1312 assert( pWin );
1313 p->y.pWin = pWin;
1314 ExprSetProperty(p, EP_WinFunc);
1315 pWin->pOwner = p;
1316 if( (p->flags & EP_Distinct) && pWin->eFrmType!=TK_FILTER ){
1317 sqlite3ErrorMsg(pParse,
1318 "DISTINCT is not supported for window functions"
1319 );
1320 }
1321 }else{
1322 sqlite3WindowDelete(pParse->db, pWin);
1323 }
1324}
1325
1326/*
1327** Possibly link window pWin into the list at pSel->pWin (window functions
1328** to be processed as part of SELECT statement pSel). The window is linked
1329** in if either (a) there are no other windows already linked to this
1330** SELECT, or (b) the windows already linked use a compatible window frame.
1331*/
1332void sqlite3WindowLink(Select *pSel, Window *pWin){
1333 if( pSel ){
1334 if( 0==pSel->pWin || 0==sqlite3WindowCompare(0, pSel->pWin, pWin, 0) ){
1335 pWin->pNextWin = pSel->pWin;
1336 if( pSel->pWin ){
1337 pSel->pWin->ppThis = &pWin->pNextWin;
1338 }
1339 pSel->pWin = pWin;
1340 pWin->ppThis = &pSel->pWin;
1341 }else{
1342 if( sqlite3ExprListCompare(pWin->pPartition, pSel->pWin->pPartition,-1) ){
1343 pSel->selFlags |= SF_MultiPart;
1344 }
1345 }
1346 }
1347}
1348
1349/*
1350** Return 0 if the two window objects are identical, 1 if they are
1351** different, or 2 if it cannot be determined if the objects are identical
1352** or not. Identical window objects can be processed in a single scan.
1353*/
1354int sqlite3WindowCompare(
1355 const Parse *pParse,
1356 const Window *p1,
1357 const Window *p2,
1358 int bFilter
1359){
1360 int res;
1361 if( NEVER(p1==0) || NEVER(p2==0) ) return 1;
1362 if( p1->eFrmType!=p2->eFrmType ) return 1;
1363 if( p1->eStart!=p2->eStart ) return 1;
1364 if( p1->eEnd!=p2->eEnd ) return 1;
1365 if( p1->eExclude!=p2->eExclude ) return 1;
1366 if( sqlite3ExprCompare(pParse, p1->pStart, p2->pStart, -1) ) return 1;
1367 if( sqlite3ExprCompare(pParse, p1->pEnd, p2->pEnd, -1) ) return 1;
1368 if( (res = sqlite3ExprListCompare(p1->pPartition, p2->pPartition, -1)) ){
1369 return res;
1370 }
1371 if( (res = sqlite3ExprListCompare(p1->pOrderBy, p2->pOrderBy, -1)) ){
1372 return res;
1373 }
1374 if( bFilter ){
1375 if( (res = sqlite3ExprCompare(pParse, p1->pFilter, p2->pFilter, -1)) ){
1376 return res;
1377 }
1378 }
1379 return 0;
1380}
1381
1382
1383/*
1384** This is called by code in select.c before it calls sqlite3WhereBegin()
1385** to begin iterating through the sub-query results. It is used to allocate
1386** and initialize registers and cursors used by sqlite3WindowCodeStep().
1387*/
1388void sqlite3WindowCodeInit(Parse *pParse, Select *pSelect){
1389 int nEphExpr = pSelect->pSrc->a[0].pSelect->pEList->nExpr;
1390 Window *pMWin = pSelect->pWin;
1391 Window *pWin;
1392 Vdbe *v = sqlite3GetVdbe(pParse);
1393
1394 sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pMWin->iEphCsr, nEphExpr);
1395 sqlite3VdbeAddOp2(v, OP_OpenDup, pMWin->iEphCsr+1, pMWin->iEphCsr);
1396 sqlite3VdbeAddOp2(v, OP_OpenDup, pMWin->iEphCsr+2, pMWin->iEphCsr);
1397 sqlite3VdbeAddOp2(v, OP_OpenDup, pMWin->iEphCsr+3, pMWin->iEphCsr);
1398
1399 /* Allocate registers to use for PARTITION BY values, if any. Initialize
1400 ** said registers to NULL. */
1401 if( pMWin->pPartition ){
1402 int nExpr = pMWin->pPartition->nExpr;
1403 pMWin->regPart = pParse->nMem+1;
1404 pParse->nMem += nExpr;
1405 sqlite3VdbeAddOp3(v, OP_Null, 0, pMWin->regPart, pMWin->regPart+nExpr-1);
1406 }
1407
1408 pMWin->regOne = ++pParse->nMem;
1409 sqlite3VdbeAddOp2(v, OP_Integer, 1, pMWin->regOne);
1410
1411 if( pMWin->eExclude ){
1412 pMWin->regStartRowid = ++pParse->nMem;
1413 pMWin->regEndRowid = ++pParse->nMem;
1414 pMWin->csrApp = pParse->nTab++;
1415 sqlite3VdbeAddOp2(v, OP_Integer, 1, pMWin->regStartRowid);
1416 sqlite3VdbeAddOp2(v, OP_Integer, 0, pMWin->regEndRowid);
1417 sqlite3VdbeAddOp2(v, OP_OpenDup, pMWin->csrApp, pMWin->iEphCsr);
1418 return;
1419 }
1420
1421 for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
1422 FuncDef *p = pWin->pWFunc;
1423 if( (p->funcFlags & SQLITE_FUNC_MINMAX) && pWin->eStart!=TK_UNBOUNDED ){
1424 /* The inline versions of min() and max() require a single ephemeral
1425 ** table and 3 registers. The registers are used as follows:
1426 **
1427 ** regApp+0: slot to copy min()/max() argument to for MakeRecord
1428 ** regApp+1: integer value used to ensure keys are unique
1429 ** regApp+2: output of MakeRecord
1430 */
1431 ExprList *pList;
1432 KeyInfo *pKeyInfo;
1433 assert( ExprUseXList(pWin->pOwner) );
1434 pList = pWin->pOwner->x.pList;
1435 pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pList, 0, 0);
1436 pWin->csrApp = pParse->nTab++;
1437 pWin->regApp = pParse->nMem+1;
1438 pParse->nMem += 3;
1439 if( pKeyInfo && pWin->pWFunc->zName[1]=='i' ){
1440 assert( pKeyInfo->aSortFlags[0]==0 );
1441 pKeyInfo->aSortFlags[0] = KEYINFO_ORDER_DESC;
1442 }
1443 sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pWin->csrApp, 2);
1444 sqlite3VdbeAppendP4(v, pKeyInfo, P4_KEYINFO);
1445 sqlite3VdbeAddOp2(v, OP_Integer, 0, pWin->regApp+1);
1446 }
1447 else if( p->zName==nth_valueName || p->zName==first_valueName ){
1448 /* Allocate two registers at pWin->regApp. These will be used to
1449 ** store the start and end index of the current frame. */
1450 pWin->regApp = pParse->nMem+1;
1451 pWin->csrApp = pParse->nTab++;
1452 pParse->nMem += 2;
1453 sqlite3VdbeAddOp2(v, OP_OpenDup, pWin->csrApp, pMWin->iEphCsr);
1454 }
1455 else if( p->zName==leadName || p->zName==lagName ){
1456 pWin->csrApp = pParse->nTab++;
1457 sqlite3VdbeAddOp2(v, OP_OpenDup, pWin->csrApp, pMWin->iEphCsr);
1458 }
1459 }
1460}
1461
1462#define WINDOW_STARTING_INT 0
1463#define WINDOW_ENDING_INT 1
1464#define WINDOW_NTH_VALUE_INT 2
1465#define WINDOW_STARTING_NUM 3
1466#define WINDOW_ENDING_NUM 4
1467
1468/*
1469** A "PRECEDING <expr>" (eCond==0) or "FOLLOWING <expr>" (eCond==1) or the
1470** value of the second argument to nth_value() (eCond==2) has just been
1471** evaluated and the result left in register reg. This function generates VM
1472** code to check that the value is a non-negative integer and throws an
1473** exception if it is not.
1474*/
1475static void windowCheckValue(Parse *pParse, int reg, int eCond){
1476 static const char *azErr[] = {
1477 "frame starting offset must be a non-negative integer",
1478 "frame ending offset must be a non-negative integer",
1479 "second argument to nth_value must be a positive integer",
1480 "frame starting offset must be a non-negative number",
1481 "frame ending offset must be a non-negative number",
1482 };
1483 static int aOp[] = { OP_Ge, OP_Ge, OP_Gt, OP_Ge, OP_Ge };
1484 Vdbe *v = sqlite3GetVdbe(pParse);
1485 int regZero = sqlite3GetTempReg(pParse);
1486 assert( eCond>=0 && eCond<ArraySize(azErr) );
1487 sqlite3VdbeAddOp2(v, OP_Integer, 0, regZero);
1488 if( eCond>=WINDOW_STARTING_NUM ){
1489 int regString = sqlite3GetTempReg(pParse);
1490 sqlite3VdbeAddOp4(v, OP_String8, 0, regString, 0, "", P4_STATIC);
1491 sqlite3VdbeAddOp3(v, OP_Ge, regString, sqlite3VdbeCurrentAddr(v)+2, reg);
1492 sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC|SQLITE_JUMPIFNULL);
1493 VdbeCoverage(v);
1494 assert( eCond==3 || eCond==4 );
1495 VdbeCoverageIf(v, eCond==3);
1496 VdbeCoverageIf(v, eCond==4);
1497 }else{
1498 sqlite3VdbeAddOp2(v, OP_MustBeInt, reg, sqlite3VdbeCurrentAddr(v)+2);
1499 VdbeCoverage(v);
1500 assert( eCond==0 || eCond==1 || eCond==2 );
1501 VdbeCoverageIf(v, eCond==0);
1502 VdbeCoverageIf(v, eCond==1);
1503 VdbeCoverageIf(v, eCond==2);
1504 }
1505 sqlite3VdbeAddOp3(v, aOp[eCond], regZero, sqlite3VdbeCurrentAddr(v)+2, reg);
1506 sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC);
1507 VdbeCoverageNeverNullIf(v, eCond==0); /* NULL case captured by */
1508 VdbeCoverageNeverNullIf(v, eCond==1); /* the OP_MustBeInt */
1509 VdbeCoverageNeverNullIf(v, eCond==2);
1510 VdbeCoverageNeverNullIf(v, eCond==3); /* NULL case caught by */
1511 VdbeCoverageNeverNullIf(v, eCond==4); /* the OP_Ge */
1512 sqlite3MayAbort(pParse);
1513 sqlite3VdbeAddOp2(v, OP_Halt, SQLITE_ERROR, OE_Abort);
1514 sqlite3VdbeAppendP4(v, (void*)azErr[eCond], P4_STATIC);
1515 sqlite3ReleaseTempReg(pParse, regZero);
1516}
1517
1518/*
1519** Return the number of arguments passed to the window-function associated
1520** with the object passed as the only argument to this function.
1521*/
1522static int windowArgCount(Window *pWin){
1523 const ExprList *pList;
1524 assert( ExprUseXList(pWin->pOwner) );
1525 pList = pWin->pOwner->x.pList;
1526 return (pList ? pList->nExpr : 0);
1527}
1528
1529typedef struct WindowCodeArg WindowCodeArg;
1530typedef struct WindowCsrAndReg WindowCsrAndReg;
1531
1532/*
1533** See comments above struct WindowCodeArg.
1534*/
1535struct WindowCsrAndReg {
1536 int csr; /* Cursor number */
1537 int reg; /* First in array of peer values */
1538};
1539
1540/*
1541** A single instance of this structure is allocated on the stack by
1542** sqlite3WindowCodeStep() and a pointer to it passed to the various helper
1543** routines. This is to reduce the number of arguments required by each
1544** helper function.
1545**
1546** regArg:
1547** Each window function requires an accumulator register (just as an
1548** ordinary aggregate function does). This variable is set to the first
1549** in an array of accumulator registers - one for each window function
1550** in the WindowCodeArg.pMWin list.
1551**
1552** eDelete:
1553** The window functions implementation sometimes caches the input rows
1554** that it processes in a temporary table. If it is not zero, this
1555** variable indicates when rows may be removed from the temp table (in
1556** order to reduce memory requirements - it would always be safe just
1557** to leave them there). Possible values for eDelete are:
1558**
1559** WINDOW_RETURN_ROW:
1560** An input row can be discarded after it is returned to the caller.
1561**
1562** WINDOW_AGGINVERSE:
1563** An input row can be discarded after the window functions xInverse()
1564** callbacks have been invoked in it.
1565**
1566** WINDOW_AGGSTEP:
1567** An input row can be discarded after the window functions xStep()
1568** callbacks have been invoked in it.
1569**
1570** start,current,end
1571** Consider a window-frame similar to the following:
1572**
1573** (ORDER BY a, b GROUPS BETWEEN 2 PRECEDING AND 2 FOLLOWING)
1574**
1575** The windows functions implmentation caches the input rows in a temp
1576** table, sorted by "a, b" (it actually populates the cache lazily, and
1577** aggressively removes rows once they are no longer required, but that's
1578** a mere detail). It keeps three cursors open on the temp table. One
1579** (current) that points to the next row to return to the query engine
1580** once its window function values have been calculated. Another (end)
1581** points to the next row to call the xStep() method of each window function
1582** on (so that it is 2 groups ahead of current). And a third (start) that
1583** points to the next row to call the xInverse() method of each window
1584** function on.
1585**
1586** Each cursor (start, current and end) consists of a VDBE cursor
1587** (WindowCsrAndReg.csr) and an array of registers (starting at
1588** WindowCodeArg.reg) that always contains a copy of the peer values
1589** read from the corresponding cursor.
1590**
1591** Depending on the window-frame in question, all three cursors may not
1592** be required. In this case both WindowCodeArg.csr and reg are set to
1593** 0.
1594*/
1595struct WindowCodeArg {
1596 Parse *pParse; /* Parse context */
1597 Window *pMWin; /* First in list of functions being processed */
1598 Vdbe *pVdbe; /* VDBE object */
1599 int addrGosub; /* OP_Gosub to this address to return one row */
1600 int regGosub; /* Register used with OP_Gosub(addrGosub) */
1601 int regArg; /* First in array of accumulator registers */
1602 int eDelete; /* See above */
1603 int regRowid;
1604
1605 WindowCsrAndReg start;
1606 WindowCsrAndReg current;
1607 WindowCsrAndReg end;
1608};
1609
1610/*
1611** Generate VM code to read the window frames peer values from cursor csr into
1612** an array of registers starting at reg.
1613*/
1614static void windowReadPeerValues(
1615 WindowCodeArg *p,
1616 int csr,
1617 int reg
1618){
1619 Window *pMWin = p->pMWin;
1620 ExprList *pOrderBy = pMWin->pOrderBy;
1621 if( pOrderBy ){
1622 Vdbe *v = sqlite3GetVdbe(p->pParse);
1623 ExprList *pPart = pMWin->pPartition;
1624 int iColOff = pMWin->nBufferCol + (pPart ? pPart->nExpr : 0);
1625 int i;
1626 for(i=0; i<pOrderBy->nExpr; i++){
1627 sqlite3VdbeAddOp3(v, OP_Column, csr, iColOff+i, reg+i);
1628 }
1629 }
1630}
1631
1632/*
1633** Generate VM code to invoke either xStep() (if bInverse is 0) or
1634** xInverse (if bInverse is non-zero) for each window function in the
1635** linked list starting at pMWin. Or, for built-in window functions
1636** that do not use the standard function API, generate the required
1637** inline VM code.
1638**
1639** If argument csr is greater than or equal to 0, then argument reg is
1640** the first register in an array of registers guaranteed to be large
1641** enough to hold the array of arguments for each function. In this case
1642** the arguments are extracted from the current row of csr into the
1643** array of registers before invoking OP_AggStep or OP_AggInverse
1644**
1645** Or, if csr is less than zero, then the array of registers at reg is
1646** already populated with all columns from the current row of the sub-query.
1647**
1648** If argument regPartSize is non-zero, then it is a register containing the
1649** number of rows in the current partition.
1650*/
1651static void windowAggStep(
1652 WindowCodeArg *p,
1653 Window *pMWin, /* Linked list of window functions */
1654 int csr, /* Read arguments from this cursor */
1655 int bInverse, /* True to invoke xInverse instead of xStep */
1656 int reg /* Array of registers */
1657){
1658 Parse *pParse = p->pParse;
1659 Vdbe *v = sqlite3GetVdbe(pParse);
1660 Window *pWin;
1661 for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
1662 FuncDef *pFunc = pWin->pWFunc;
1663 int regArg;
1664 int nArg = pWin->bExprArgs ? 0 : windowArgCount(pWin);
1665 int i;
1666
1667 assert( bInverse==0 || pWin->eStart!=TK_UNBOUNDED );
1668
1669 /* All OVER clauses in the same window function aggregate step must
1670 ** be the same. */
1671 assert( pWin==pMWin || sqlite3WindowCompare(pParse,pWin,pMWin,0)!=1 );
1672
1673 for(i=0; i<nArg; i++){
1674 if( i!=1 || pFunc->zName!=nth_valueName ){
1675 sqlite3VdbeAddOp3(v, OP_Column, csr, pWin->iArgCol+i, reg+i);
1676 }else{
1677 sqlite3VdbeAddOp3(v, OP_Column, pMWin->iEphCsr, pWin->iArgCol+i, reg+i);
1678 }
1679 }
1680 regArg = reg;
1681
1682 if( pMWin->regStartRowid==0
1683 && (pFunc->funcFlags & SQLITE_FUNC_MINMAX)
1684 && (pWin->eStart!=TK_UNBOUNDED)
1685 ){
1686 int addrIsNull = sqlite3VdbeAddOp1(v, OP_IsNull, regArg);
1687 VdbeCoverage(v);
1688 if( bInverse==0 ){
1689 sqlite3VdbeAddOp2(v, OP_AddImm, pWin->regApp+1, 1);
1690 sqlite3VdbeAddOp2(v, OP_SCopy, regArg, pWin->regApp);
1691 sqlite3VdbeAddOp3(v, OP_MakeRecord, pWin->regApp, 2, pWin->regApp+2);
1692 sqlite3VdbeAddOp2(v, OP_IdxInsert, pWin->csrApp, pWin->regApp+2);
1693 }else{
1694 sqlite3VdbeAddOp4Int(v, OP_SeekGE, pWin->csrApp, 0, regArg, 1);
1695 VdbeCoverageNeverTaken(v);
1696 sqlite3VdbeAddOp1(v, OP_Delete, pWin->csrApp);
1697 sqlite3VdbeJumpHere(v, sqlite3VdbeCurrentAddr(v)-2);
1698 }
1699 sqlite3VdbeJumpHere(v, addrIsNull);
1700 }else if( pWin->regApp ){
1701 assert( pFunc->zName==nth_valueName
1702 || pFunc->zName==first_valueName
1703 );
1704 assert( bInverse==0 || bInverse==1 );
1705 sqlite3VdbeAddOp2(v, OP_AddImm, pWin->regApp+1-bInverse, 1);
1706 }else if( pFunc->xSFunc!=noopStepFunc ){
1707 int addrIf = 0;
1708 if( pWin->pFilter ){
1709 int regTmp;
1710 assert( ExprUseXList(pWin->pOwner) );
1711 assert( pWin->bExprArgs || !nArg ||nArg==pWin->pOwner->x.pList->nExpr );
1712 assert( pWin->bExprArgs || nArg ||pWin->pOwner->x.pList==0 );
1713 regTmp = sqlite3GetTempReg(pParse);
1714 sqlite3VdbeAddOp3(v, OP_Column, csr, pWin->iArgCol+nArg,regTmp);
1715 addrIf = sqlite3VdbeAddOp3(v, OP_IfNot, regTmp, 0, 1);
1716 VdbeCoverage(v);
1717 sqlite3ReleaseTempReg(pParse, regTmp);
1718 }
1719
1720 if( pWin->bExprArgs ){
1721 int iOp = sqlite3VdbeCurrentAddr(v);
1722 int iEnd;
1723
1724 assert( ExprUseXList(pWin->pOwner) );
1725 nArg = pWin->pOwner->x.pList->nExpr;
1726 regArg = sqlite3GetTempRange(pParse, nArg);
1727 sqlite3ExprCodeExprList(pParse, pWin->pOwner->x.pList, regArg, 0, 0);
1728
1729 for(iEnd=sqlite3VdbeCurrentAddr(v); iOp<iEnd; iOp++){
1730 VdbeOp *pOp = sqlite3VdbeGetOp(v, iOp);
1731 if( pOp->opcode==OP_Column && pOp->p1==pMWin->iEphCsr ){
1732 pOp->p1 = csr;
1733 }
1734 }
1735 }
1736 if( pFunc->funcFlags & SQLITE_FUNC_NEEDCOLL ){
1737 CollSeq *pColl;
1738 assert( nArg>0 );
1739 assert( ExprUseXList(pWin->pOwner) );
1740 pColl = sqlite3ExprNNCollSeq(pParse, pWin->pOwner->x.pList->a[0].pExpr);
1741 sqlite3VdbeAddOp4(v, OP_CollSeq, 0,0,0, (const char*)pColl, P4_COLLSEQ);
1742 }
1743 sqlite3VdbeAddOp3(v, bInverse? OP_AggInverse : OP_AggStep,
1744 bInverse, regArg, pWin->regAccum);
1745 sqlite3VdbeAppendP4(v, pFunc, P4_FUNCDEF);
1746 sqlite3VdbeChangeP5(v, (u8)nArg);
1747 if( pWin->bExprArgs ){
1748 sqlite3ReleaseTempRange(pParse, regArg, nArg);
1749 }
1750 if( addrIf ) sqlite3VdbeJumpHere(v, addrIf);
1751 }
1752 }
1753}
1754
1755/*
1756** Values that may be passed as the second argument to windowCodeOp().
1757*/
1758#define WINDOW_RETURN_ROW 1
1759#define WINDOW_AGGINVERSE 2
1760#define WINDOW_AGGSTEP 3
1761
1762/*
1763** Generate VM code to invoke either xValue() (bFin==0) or xFinalize()
1764** (bFin==1) for each window function in the linked list starting at
1765** pMWin. Or, for built-in window-functions that do not use the standard
1766** API, generate the equivalent VM code.
1767*/
1768static void windowAggFinal(WindowCodeArg *p, int bFin){
1769 Parse *pParse = p->pParse;
1770 Window *pMWin = p->pMWin;
1771 Vdbe *v = sqlite3GetVdbe(pParse);
1772 Window *pWin;
1773
1774 for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
1775 if( pMWin->regStartRowid==0
1776 && (pWin->pWFunc->funcFlags & SQLITE_FUNC_MINMAX)
1777 && (pWin->eStart!=TK_UNBOUNDED)
1778 ){
1779 sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regResult);
1780 sqlite3VdbeAddOp1(v, OP_Last, pWin->csrApp);
1781 VdbeCoverage(v);
1782 sqlite3VdbeAddOp3(v, OP_Column, pWin->csrApp, 0, pWin->regResult);
1783 sqlite3VdbeJumpHere(v, sqlite3VdbeCurrentAddr(v)-2);
1784 }else if( pWin->regApp ){
1785 assert( pMWin->regStartRowid==0 );
1786 }else{
1787 int nArg = windowArgCount(pWin);
1788 if( bFin ){
1789 sqlite3VdbeAddOp2(v, OP_AggFinal, pWin->regAccum, nArg);
1790 sqlite3VdbeAppendP4(v, pWin->pWFunc, P4_FUNCDEF);
1791 sqlite3VdbeAddOp2(v, OP_Copy, pWin->regAccum, pWin->regResult);
1792 sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);
1793 }else{
1794 sqlite3VdbeAddOp3(v, OP_AggValue,pWin->regAccum,nArg,pWin->regResult);
1795 sqlite3VdbeAppendP4(v, pWin->pWFunc, P4_FUNCDEF);
1796 }
1797 }
1798 }
1799}
1800
1801/*
1802** Generate code to calculate the current values of all window functions in the
1803** p->pMWin list by doing a full scan of the current window frame. Store the
1804** results in the Window.regResult registers, ready to return the upper
1805** layer.
1806*/
1807static void windowFullScan(WindowCodeArg *p){
1808 Window *pWin;
1809 Parse *pParse = p->pParse;
1810 Window *pMWin = p->pMWin;
1811 Vdbe *v = p->pVdbe;
1812
1813 int regCRowid = 0; /* Current rowid value */
1814 int regCPeer = 0; /* Current peer values */
1815 int regRowid = 0; /* AggStep rowid value */
1816 int regPeer = 0; /* AggStep peer values */
1817
1818 int nPeer;
1819 int lblNext;
1820 int lblBrk;
1821 int addrNext;
1822 int csr;
1823
1824 VdbeModuleComment((v, "windowFullScan begin"));
1825
1826 assert( pMWin!=0 );
1827 csr = pMWin->csrApp;
1828 nPeer = (pMWin->pOrderBy ? pMWin->pOrderBy->nExpr : 0);
1829
1830 lblNext = sqlite3VdbeMakeLabel(pParse);
1831 lblBrk = sqlite3VdbeMakeLabel(pParse);
1832
1833 regCRowid = sqlite3GetTempReg(pParse);
1834 regRowid = sqlite3GetTempReg(pParse);
1835 if( nPeer ){
1836 regCPeer = sqlite3GetTempRange(pParse, nPeer);
1837 regPeer = sqlite3GetTempRange(pParse, nPeer);
1838 }
1839
1840 sqlite3VdbeAddOp2(v, OP_Rowid, pMWin->iEphCsr, regCRowid);
1841 windowReadPeerValues(p, pMWin->iEphCsr, regCPeer);
1842
1843 for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
1844 sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);
1845 }
1846
1847 sqlite3VdbeAddOp3(v, OP_SeekGE, csr, lblBrk, pMWin->regStartRowid);
1848 VdbeCoverage(v);
1849 addrNext = sqlite3VdbeCurrentAddr(v);
1850 sqlite3VdbeAddOp2(v, OP_Rowid, csr, regRowid);
1851 sqlite3VdbeAddOp3(v, OP_Gt, pMWin->regEndRowid, lblBrk, regRowid);
1852 VdbeCoverageNeverNull(v);
1853
1854 if( pMWin->eExclude==TK_CURRENT ){
1855 sqlite3VdbeAddOp3(v, OP_Eq, regCRowid, lblNext, regRowid);
1856 VdbeCoverageNeverNull(v);
1857 }else if( pMWin->eExclude!=TK_NO ){
1858 int addr;
1859 int addrEq = 0;
1860 KeyInfo *pKeyInfo = 0;
1861
1862 if( pMWin->pOrderBy ){
1863 pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pMWin->pOrderBy, 0, 0);
1864 }
1865 if( pMWin->eExclude==TK_TIES ){
1866 addrEq = sqlite3VdbeAddOp3(v, OP_Eq, regCRowid, 0, regRowid);
1867 VdbeCoverageNeverNull(v);
1868 }
1869 if( pKeyInfo ){
1870 windowReadPeerValues(p, csr, regPeer);
1871 sqlite3VdbeAddOp3(v, OP_Compare, regPeer, regCPeer, nPeer);
1872 sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
1873 addr = sqlite3VdbeCurrentAddr(v)+1;
1874 sqlite3VdbeAddOp3(v, OP_Jump, addr, lblNext, addr);
1875 VdbeCoverageEqNe(v);
1876 }else{
1877 sqlite3VdbeAddOp2(v, OP_Goto, 0, lblNext);
1878 }
1879 if( addrEq ) sqlite3VdbeJumpHere(v, addrEq);
1880 }
1881
1882 windowAggStep(p, pMWin, csr, 0, p->regArg);
1883
1884 sqlite3VdbeResolveLabel(v, lblNext);
1885 sqlite3VdbeAddOp2(v, OP_Next, csr, addrNext);
1886 VdbeCoverage(v);
1887 sqlite3VdbeJumpHere(v, addrNext-1);
1888 sqlite3VdbeJumpHere(v, addrNext+1);
1889 sqlite3ReleaseTempReg(pParse, regRowid);
1890 sqlite3ReleaseTempReg(pParse, regCRowid);
1891 if( nPeer ){
1892 sqlite3ReleaseTempRange(pParse, regPeer, nPeer);
1893 sqlite3ReleaseTempRange(pParse, regCPeer, nPeer);
1894 }
1895
1896 windowAggFinal(p, 1);
1897 VdbeModuleComment((v, "windowFullScan end"));
1898}
1899
1900/*
1901** Invoke the sub-routine at regGosub (generated by code in select.c) to
1902** return the current row of Window.iEphCsr. If all window functions are
1903** aggregate window functions that use the standard API, a single
1904** OP_Gosub instruction is all that this routine generates. Extra VM code
1905** for per-row processing is only generated for the following built-in window
1906** functions:
1907**
1908** nth_value()
1909** first_value()
1910** lag()
1911** lead()
1912*/
1913static void windowReturnOneRow(WindowCodeArg *p){
1914 Window *pMWin = p->pMWin;
1915 Vdbe *v = p->pVdbe;
1916
1917 if( pMWin->regStartRowid ){
1918 windowFullScan(p);
1919 }else{
1920 Parse *pParse = p->pParse;
1921 Window *pWin;
1922
1923 for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
1924 FuncDef *pFunc = pWin->pWFunc;
1925 assert( ExprUseXList(pWin->pOwner) );
1926 if( pFunc->zName==nth_valueName
1927 || pFunc->zName==first_valueName
1928 ){
1929 int csr = pWin->csrApp;
1930 int lbl = sqlite3VdbeMakeLabel(pParse);
1931 int tmpReg = sqlite3GetTempReg(pParse);
1932 sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regResult);
1933
1934 if( pFunc->zName==nth_valueName ){
1935 sqlite3VdbeAddOp3(v, OP_Column,pMWin->iEphCsr,pWin->iArgCol+1,tmpReg);
1936 windowCheckValue(pParse, tmpReg, 2);
1937 }else{
1938 sqlite3VdbeAddOp2(v, OP_Integer, 1, tmpReg);
1939 }
1940 sqlite3VdbeAddOp3(v, OP_Add, tmpReg, pWin->regApp, tmpReg);
1941 sqlite3VdbeAddOp3(v, OP_Gt, pWin->regApp+1, lbl, tmpReg);
1942 VdbeCoverageNeverNull(v);
1943 sqlite3VdbeAddOp3(v, OP_SeekRowid, csr, 0, tmpReg);
1944 VdbeCoverageNeverTaken(v);
1945 sqlite3VdbeAddOp3(v, OP_Column, csr, pWin->iArgCol, pWin->regResult);
1946 sqlite3VdbeResolveLabel(v, lbl);
1947 sqlite3ReleaseTempReg(pParse, tmpReg);
1948 }
1949 else if( pFunc->zName==leadName || pFunc->zName==lagName ){
1950 int nArg = pWin->pOwner->x.pList->nExpr;
1951 int csr = pWin->csrApp;
1952 int lbl = sqlite3VdbeMakeLabel(pParse);
1953 int tmpReg = sqlite3GetTempReg(pParse);
1954 int iEph = pMWin->iEphCsr;
1955
1956 if( nArg<3 ){
1957 sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regResult);
1958 }else{
1959 sqlite3VdbeAddOp3(v, OP_Column, iEph,pWin->iArgCol+2,pWin->regResult);
1960 }
1961 sqlite3VdbeAddOp2(v, OP_Rowid, iEph, tmpReg);
1962 if( nArg<2 ){
1963 int val = (pFunc->zName==leadName ? 1 : -1);
1964 sqlite3VdbeAddOp2(v, OP_AddImm, tmpReg, val);
1965 }else{
1966 int op = (pFunc->zName==leadName ? OP_Add : OP_Subtract);
1967 int tmpReg2 = sqlite3GetTempReg(pParse);
1968 sqlite3VdbeAddOp3(v, OP_Column, iEph, pWin->iArgCol+1, tmpReg2);
1969 sqlite3VdbeAddOp3(v, op, tmpReg2, tmpReg, tmpReg);
1970 sqlite3ReleaseTempReg(pParse, tmpReg2);
1971 }
1972
1973 sqlite3VdbeAddOp3(v, OP_SeekRowid, csr, lbl, tmpReg);
1974 VdbeCoverage(v);
1975 sqlite3VdbeAddOp3(v, OP_Column, csr, pWin->iArgCol, pWin->regResult);
1976 sqlite3VdbeResolveLabel(v, lbl);
1977 sqlite3ReleaseTempReg(pParse, tmpReg);
1978 }
1979 }
1980 }
1981 sqlite3VdbeAddOp2(v, OP_Gosub, p->regGosub, p->addrGosub);
1982}
1983
1984/*
1985** Generate code to set the accumulator register for each window function
1986** in the linked list passed as the second argument to NULL. And perform
1987** any equivalent initialization required by any built-in window functions
1988** in the list.
1989*/
1990static int windowInitAccum(Parse *pParse, Window *pMWin){
1991 Vdbe *v = sqlite3GetVdbe(pParse);
1992 int regArg;
1993 int nArg = 0;
1994 Window *pWin;
1995 for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
1996 FuncDef *pFunc = pWin->pWFunc;
1997 assert( pWin->regAccum );
1998 sqlite3VdbeAddOp2(v, OP_Null, 0, pWin->regAccum);
1999 nArg = MAX(nArg, windowArgCount(pWin));
2000 if( pMWin->regStartRowid==0 ){
2001 if( pFunc->zName==nth_valueName || pFunc->zName==first_valueName ){
2002 sqlite3VdbeAddOp2(v, OP_Integer, 0, pWin->regApp);
2003 sqlite3VdbeAddOp2(v, OP_Integer, 0, pWin->regApp+1);
2004 }
2005
2006 if( (pFunc->funcFlags & SQLITE_FUNC_MINMAX) && pWin->csrApp ){
2007 assert( pWin->eStart!=TK_UNBOUNDED );
2008 sqlite3VdbeAddOp1(v, OP_ResetSorter, pWin->csrApp);
2009 sqlite3VdbeAddOp2(v, OP_Integer, 0, pWin->regApp+1);
2010 }
2011 }
2012 }
2013 regArg = pParse->nMem+1;
2014 pParse->nMem += nArg;
2015 return regArg;
2016}
2017
2018/*
2019** Return true if the current frame should be cached in the ephemeral table,
2020** even if there are no xInverse() calls required.
2021*/
2022static int windowCacheFrame(Window *pMWin){
2023 Window *pWin;
2024 if( pMWin->regStartRowid ) return 1;
2025 for(pWin=pMWin; pWin; pWin=pWin->pNextWin){
2026 FuncDef *pFunc = pWin->pWFunc;
2027 if( (pFunc->zName==nth_valueName)
2028 || (pFunc->zName==first_valueName)
2029 || (pFunc->zName==leadName)
2030 || (pFunc->zName==lagName)
2031 ){
2032 return 1;
2033 }
2034 }
2035 return 0;
2036}
2037
2038/*
2039** regOld and regNew are each the first register in an array of size
2040** pOrderBy->nExpr. This function generates code to compare the two
2041** arrays of registers using the collation sequences and other comparison
2042** parameters specified by pOrderBy.
2043**
2044** If the two arrays are not equal, the contents of regNew is copied to
2045** regOld and control falls through. Otherwise, if the contents of the arrays
2046** are equal, an OP_Goto is executed. The address of the OP_Goto is returned.
2047*/
2048static void windowIfNewPeer(
2049 Parse *pParse,
2050 ExprList *pOrderBy,
2051 int regNew, /* First in array of new values */
2052 int regOld, /* First in array of old values */
2053 int addr /* Jump here */
2054){
2055 Vdbe *v = sqlite3GetVdbe(pParse);
2056 if( pOrderBy ){
2057 int nVal = pOrderBy->nExpr;
2058 KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pOrderBy, 0, 0);
2059 sqlite3VdbeAddOp3(v, OP_Compare, regOld, regNew, nVal);
2060 sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
2061 sqlite3VdbeAddOp3(v, OP_Jump,
2062 sqlite3VdbeCurrentAddr(v)+1, addr, sqlite3VdbeCurrentAddr(v)+1
2063 );
2064 VdbeCoverageEqNe(v);
2065 sqlite3VdbeAddOp3(v, OP_Copy, regNew, regOld, nVal-1);
2066 }else{
2067 sqlite3VdbeAddOp2(v, OP_Goto, 0, addr);
2068 }
2069}
2070
2071/*
2072** This function is called as part of generating VM programs for RANGE
2073** offset PRECEDING/FOLLOWING frame boundaries. Assuming "ASC" order for
2074** the ORDER BY term in the window, and that argument op is OP_Ge, it generates
2075** code equivalent to:
2076**
2077** if( csr1.peerVal + regVal >= csr2.peerVal ) goto lbl;
2078**
2079** The value of parameter op may also be OP_Gt or OP_Le. In these cases the
2080** operator in the above pseudo-code is replaced with ">" or "<=", respectively.
2081**
2082** If the sort-order for the ORDER BY term in the window is DESC, then the
2083** comparison is reversed. Instead of adding regVal to csr1.peerVal, it is
2084** subtracted. And the comparison operator is inverted to - ">=" becomes "<=",
2085** ">" becomes "<", and so on. So, with DESC sort order, if the argument op
2086** is OP_Ge, the generated code is equivalent to:
2087**
2088** if( csr1.peerVal - regVal <= csr2.peerVal ) goto lbl;
2089**
2090** A special type of arithmetic is used such that if csr1.peerVal is not
2091** a numeric type (real or integer), then the result of the addition
2092** or subtraction is a a copy of csr1.peerVal.
2093*/
2094static void windowCodeRangeTest(
2095 WindowCodeArg *p,
2096 int op, /* OP_Ge, OP_Gt, or OP_Le */
2097 int csr1, /* Cursor number for cursor 1 */
2098 int regVal, /* Register containing non-negative number */
2099 int csr2, /* Cursor number for cursor 2 */
2100 int lbl /* Jump destination if condition is true */
2101){
2102 Parse *pParse = p->pParse;
2103 Vdbe *v = sqlite3GetVdbe(pParse);
2104 ExprList *pOrderBy = p->pMWin->pOrderBy; /* ORDER BY clause for window */
2105 int reg1 = sqlite3GetTempReg(pParse); /* Reg. for csr1.peerVal+regVal */
2106 int reg2 = sqlite3GetTempReg(pParse); /* Reg. for csr2.peerVal */
2107 int regString = ++pParse->nMem; /* Reg. for constant value '' */
2108 int arith = OP_Add; /* OP_Add or OP_Subtract */
2109 int addrGe; /* Jump destination */
2110 int addrDone = sqlite3VdbeMakeLabel(pParse); /* Address past OP_Ge */
2111 CollSeq *pColl;
2112
2113 /* Read the peer-value from each cursor into a register */
2114 windowReadPeerValues(p, csr1, reg1);
2115 windowReadPeerValues(p, csr2, reg2);
2116
2117 assert( op==OP_Ge || op==OP_Gt || op==OP_Le );
2118 assert( pOrderBy && pOrderBy->nExpr==1 );
2119 if( pOrderBy->a[0].fg.sortFlags & KEYINFO_ORDER_DESC ){
2120 switch( op ){
2121 case OP_Ge: op = OP_Le; break;
2122 case OP_Gt: op = OP_Lt; break;
2123 default: assert( op==OP_Le ); op = OP_Ge; break;
2124 }
2125 arith = OP_Subtract;
2126 }
2127
2128 VdbeModuleComment((v, "CodeRangeTest: if( R%d %s R%d %s R%d ) goto lbl",
2129 reg1, (arith==OP_Add ? "+" : "-"), regVal,
2130 ((op==OP_Ge) ? ">=" : (op==OP_Le) ? "<=" : (op==OP_Gt) ? ">" : "<"), reg2
2131 ));
2132
2133 /* If the BIGNULL flag is set for the ORDER BY, then it is required to
2134 ** consider NULL values to be larger than all other values, instead of
2135 ** the usual smaller. The VDBE opcodes OP_Ge and so on do not handle this
2136 ** (and adding that capability causes a performance regression), so
2137 ** instead if the BIGNULL flag is set then cases where either reg1 or
2138 ** reg2 are NULL are handled separately in the following block. The code
2139 ** generated is equivalent to:
2140 **
2141 ** if( reg1 IS NULL ){
2142 ** if( op==OP_Ge ) goto lbl;
2143 ** if( op==OP_Gt && reg2 IS NOT NULL ) goto lbl;
2144 ** if( op==OP_Le && reg2 IS NULL ) goto lbl;
2145 ** }else if( reg2 IS NULL ){
2146 ** if( op==OP_Le ) goto lbl;
2147 ** }
2148 **
2149 ** Additionally, if either reg1 or reg2 are NULL but the jump to lbl is
2150 ** not taken, control jumps over the comparison operator coded below this
2151 ** block. */
2152 if( pOrderBy->a[0].fg.sortFlags & KEYINFO_ORDER_BIGNULL ){
2153 /* This block runs if reg1 contains a NULL. */
2154 int addr = sqlite3VdbeAddOp1(v, OP_NotNull, reg1); VdbeCoverage(v);
2155 switch( op ){
2156 case OP_Ge:
2157 sqlite3VdbeAddOp2(v, OP_Goto, 0, lbl);
2158 break;
2159 case OP_Gt:
2160 sqlite3VdbeAddOp2(v, OP_NotNull, reg2, lbl);
2161 VdbeCoverage(v);
2162 break;
2163 case OP_Le:
2164 sqlite3VdbeAddOp2(v, OP_IsNull, reg2, lbl);
2165 VdbeCoverage(v);
2166 break;
2167 default: assert( op==OP_Lt ); /* no-op */ break;
2168 }
2169 sqlite3VdbeAddOp2(v, OP_Goto, 0, addrDone);
2170
2171 /* This block runs if reg1 is not NULL, but reg2 is. */
2172 sqlite3VdbeJumpHere(v, addr);
2173 sqlite3VdbeAddOp2(v, OP_IsNull, reg2,
2174 (op==OP_Gt || op==OP_Ge) ? addrDone : lbl);
2175 VdbeCoverage(v);
2176 }
2177
2178 /* Register reg1 currently contains csr1.peerVal (the peer-value from csr1).
2179 ** This block adds (or subtracts for DESC) the numeric value in regVal
2180 ** from it. Or, if reg1 is not numeric (it is a NULL, a text value or a blob),
2181 ** then leave reg1 as it is. In pseudo-code, this is implemented as:
2182 **
2183 ** if( reg1>='' ) goto addrGe;
2184 ** reg1 = reg1 +/- regVal
2185 ** addrGe:
2186 **
2187 ** Since all strings and blobs are greater-than-or-equal-to an empty string,
2188 ** the add/subtract is skipped for these, as required. If reg1 is a NULL,
2189 ** then the arithmetic is performed, but since adding or subtracting from
2190 ** NULL is always NULL anyway, this case is handled as required too. */
2191 sqlite3VdbeAddOp4(v, OP_String8, 0, regString, 0, "", P4_STATIC);
2192 addrGe = sqlite3VdbeAddOp3(v, OP_Ge, regString, 0, reg1);
2193 VdbeCoverage(v);
2194 if( (op==OP_Ge && arith==OP_Add) || (op==OP_Le && arith==OP_Subtract) ){
2195 sqlite3VdbeAddOp3(v, op, reg2, lbl, reg1); VdbeCoverage(v);
2196 }
2197 sqlite3VdbeAddOp3(v, arith, regVal, reg1, reg1);
2198 sqlite3VdbeJumpHere(v, addrGe);
2199
2200 /* Compare registers reg2 and reg1, taking the jump if required. Note that
2201 ** control skips over this test if the BIGNULL flag is set and either
2202 ** reg1 or reg2 contain a NULL value. */
2203 sqlite3VdbeAddOp3(v, op, reg2, lbl, reg1); VdbeCoverage(v);
2204 pColl = sqlite3ExprNNCollSeq(pParse, pOrderBy->a[0].pExpr);
2205 sqlite3VdbeAppendP4(v, (void*)pColl, P4_COLLSEQ);
2206 sqlite3VdbeChangeP5(v, SQLITE_NULLEQ);
2207 sqlite3VdbeResolveLabel(v, addrDone);
2208
2209 assert( op==OP_Ge || op==OP_Gt || op==OP_Lt || op==OP_Le );
2210 testcase(op==OP_Ge); VdbeCoverageIf(v, op==OP_Ge);
2211 testcase(op==OP_Lt); VdbeCoverageIf(v, op==OP_Lt);
2212 testcase(op==OP_Le); VdbeCoverageIf(v, op==OP_Le);
2213 testcase(op==OP_Gt); VdbeCoverageIf(v, op==OP_Gt);
2214 sqlite3ReleaseTempReg(pParse, reg1);
2215 sqlite3ReleaseTempReg(pParse, reg2);
2216
2217 VdbeModuleComment((v, "CodeRangeTest: end"));
2218}
2219
2220/*
2221** Helper function for sqlite3WindowCodeStep(). Each call to this function
2222** generates VM code for a single RETURN_ROW, AGGSTEP or AGGINVERSE
2223** operation. Refer to the header comment for sqlite3WindowCodeStep() for
2224** details.
2225*/
2226static int windowCodeOp(
2227 WindowCodeArg *p, /* Context object */
2228 int op, /* WINDOW_RETURN_ROW, AGGSTEP or AGGINVERSE */
2229 int regCountdown, /* Register for OP_IfPos countdown */
2230 int jumpOnEof /* Jump here if stepped cursor reaches EOF */
2231){
2232 int csr, reg;
2233 Parse *pParse = p->pParse;
2234 Window *pMWin = p->pMWin;
2235 int ret = 0;
2236 Vdbe *v = p->pVdbe;
2237 int addrContinue = 0;
2238 int bPeer = (pMWin->eFrmType!=TK_ROWS);
2239
2240 int lblDone = sqlite3VdbeMakeLabel(pParse);
2241 int addrNextRange = 0;
2242
2243 /* Special case - WINDOW_AGGINVERSE is always a no-op if the frame
2244 ** starts with UNBOUNDED PRECEDING. */
2245 if( op==WINDOW_AGGINVERSE && pMWin->eStart==TK_UNBOUNDED ){
2246 assert( regCountdown==0 && jumpOnEof==0 );
2247 return 0;
2248 }
2249
2250 if( regCountdown>0 ){
2251 if( pMWin->eFrmType==TK_RANGE ){
2252 addrNextRange = sqlite3VdbeCurrentAddr(v);
2253 assert( op==WINDOW_AGGINVERSE || op==WINDOW_AGGSTEP );
2254 if( op==WINDOW_AGGINVERSE ){
2255 if( pMWin->eStart==TK_FOLLOWING ){
2256 windowCodeRangeTest(
2257 p, OP_Le, p->current.csr, regCountdown, p->start.csr, lblDone
2258 );
2259 }else{
2260 windowCodeRangeTest(
2261 p, OP_Ge, p->start.csr, regCountdown, p->current.csr, lblDone
2262 );
2263 }
2264 }else{
2265 windowCodeRangeTest(
2266 p, OP_Gt, p->end.csr, regCountdown, p->current.csr, lblDone
2267 );
2268 }
2269 }else{
2270 sqlite3VdbeAddOp3(v, OP_IfPos, regCountdown, lblDone, 1);
2271 VdbeCoverage(v);
2272 }
2273 }
2274
2275 if( op==WINDOW_RETURN_ROW && pMWin->regStartRowid==0 ){
2276 windowAggFinal(p, 0);
2277 }
2278 addrContinue = sqlite3VdbeCurrentAddr(v);
2279
2280 /* If this is a (RANGE BETWEEN a FOLLOWING AND b FOLLOWING) or
2281 ** (RANGE BETWEEN b PRECEDING AND a PRECEDING) frame, ensure the
2282 ** start cursor does not advance past the end cursor within the
2283 ** temporary table. It otherwise might, if (a>b). Also ensure that,
2284 ** if the input cursor is still finding new rows, that the end
2285 ** cursor does not go past it to EOF. */
2286 if( pMWin->eStart==pMWin->eEnd && regCountdown
2287 && pMWin->eFrmType==TK_RANGE
2288 ){
2289 int regRowid1 = sqlite3GetTempReg(pParse);
2290 int regRowid2 = sqlite3GetTempReg(pParse);
2291 if( op==WINDOW_AGGINVERSE ){
2292 sqlite3VdbeAddOp2(v, OP_Rowid, p->start.csr, regRowid1);
2293 sqlite3VdbeAddOp2(v, OP_Rowid, p->end.csr, regRowid2);
2294 sqlite3VdbeAddOp3(v, OP_Ge, regRowid2, lblDone, regRowid1);
2295 VdbeCoverage(v);
2296 }else if( p->regRowid ){
2297 sqlite3VdbeAddOp2(v, OP_Rowid, p->end.csr, regRowid1);
2298 sqlite3VdbeAddOp3(v, OP_Ge, p->regRowid, lblDone, regRowid1);
2299 VdbeCoverageNeverNull(v);
2300 }
2301 sqlite3ReleaseTempReg(pParse, regRowid1);
2302 sqlite3ReleaseTempReg(pParse, regRowid2);
2303 assert( pMWin->eStart==TK_PRECEDING || pMWin->eStart==TK_FOLLOWING );
2304 }
2305
2306 switch( op ){
2307 case WINDOW_RETURN_ROW:
2308 csr = p->current.csr;
2309 reg = p->current.reg;
2310 windowReturnOneRow(p);
2311 break;
2312
2313 case WINDOW_AGGINVERSE:
2314 csr = p->start.csr;
2315 reg = p->start.reg;
2316 if( pMWin->regStartRowid ){
2317 assert( pMWin->regEndRowid );
2318 sqlite3VdbeAddOp2(v, OP_AddImm, pMWin->regStartRowid, 1);
2319 }else{
2320 windowAggStep(p, pMWin, csr, 1, p->regArg);
2321 }
2322 break;
2323
2324 default:
2325 assert( op==WINDOW_AGGSTEP );
2326 csr = p->end.csr;
2327 reg = p->end.reg;
2328 if( pMWin->regStartRowid ){
2329 assert( pMWin->regEndRowid );
2330 sqlite3VdbeAddOp2(v, OP_AddImm, pMWin->regEndRowid, 1);
2331 }else{
2332 windowAggStep(p, pMWin, csr, 0, p->regArg);
2333 }
2334 break;
2335 }
2336
2337 if( op==p->eDelete ){
2338 sqlite3VdbeAddOp1(v, OP_Delete, csr);
2339 sqlite3VdbeChangeP5(v, OPFLAG_SAVEPOSITION);
2340 }
2341
2342 if( jumpOnEof ){
2343 sqlite3VdbeAddOp2(v, OP_Next, csr, sqlite3VdbeCurrentAddr(v)+2);
2344 VdbeCoverage(v);
2345 ret = sqlite3VdbeAddOp0(v, OP_Goto);
2346 }else{
2347 sqlite3VdbeAddOp2(v, OP_Next, csr, sqlite3VdbeCurrentAddr(v)+1+bPeer);
2348 VdbeCoverage(v);
2349 if( bPeer ){
2350 sqlite3VdbeAddOp2(v, OP_Goto, 0, lblDone);
2351 }
2352 }
2353
2354 if( bPeer ){
2355 int nReg = (pMWin->pOrderBy ? pMWin->pOrderBy->nExpr : 0);
2356 int regTmp = (nReg ? sqlite3GetTempRange(pParse, nReg) : 0);
2357 windowReadPeerValues(p, csr, regTmp);
2358 windowIfNewPeer(pParse, pMWin->pOrderBy, regTmp, reg, addrContinue);
2359 sqlite3ReleaseTempRange(pParse, regTmp, nReg);
2360 }
2361
2362 if( addrNextRange ){
2363 sqlite3VdbeAddOp2(v, OP_Goto, 0, addrNextRange);
2364 }
2365 sqlite3VdbeResolveLabel(v, lblDone);
2366 return ret;
2367}
2368
2369
2370/*
2371** Allocate and return a duplicate of the Window object indicated by the
2372** third argument. Set the Window.pOwner field of the new object to
2373** pOwner.
2374*/
2375Window *sqlite3WindowDup(sqlite3 *db, Expr *pOwner, Window *p){
2376 Window *pNew = 0;
2377 if( ALWAYS(p) ){
2378 pNew = sqlite3DbMallocZero(db, sizeof(Window));
2379 if( pNew ){
2380 pNew->zName = sqlite3DbStrDup(db, p->zName);
2381 pNew->zBase = sqlite3DbStrDup(db, p->zBase);
2382 pNew->pFilter = sqlite3ExprDup(db, p->pFilter, 0);
2383 pNew->pWFunc = p->pWFunc;
2384 pNew->pPartition = sqlite3ExprListDup(db, p->pPartition, 0);
2385 pNew->pOrderBy = sqlite3ExprListDup(db, p->pOrderBy, 0);
2386 pNew->eFrmType = p->eFrmType;
2387 pNew->eEnd = p->eEnd;
2388 pNew->eStart = p->eStart;
2389 pNew->eExclude = p->eExclude;
2390 pNew->regResult = p->regResult;
2391 pNew->regAccum = p->regAccum;
2392 pNew->iArgCol = p->iArgCol;
2393 pNew->iEphCsr = p->iEphCsr;
2394 pNew->bExprArgs = p->bExprArgs;
2395 pNew->pStart = sqlite3ExprDup(db, p->pStart, 0);
2396 pNew->pEnd = sqlite3ExprDup(db, p->pEnd, 0);
2397 pNew->pOwner = pOwner;
2398 pNew->bImplicitFrame = p->bImplicitFrame;
2399 }
2400 }
2401 return pNew;
2402}
2403
2404/*
2405** Return a copy of the linked list of Window objects passed as the
2406** second argument.
2407*/
2408Window *sqlite3WindowListDup(sqlite3 *db, Window *p){
2409 Window *pWin;
2410 Window *pRet = 0;
2411 Window **pp = &pRet;
2412
2413 for(pWin=p; pWin; pWin=pWin->pNextWin){
2414 *pp = sqlite3WindowDup(db, 0, pWin);
2415 if( *pp==0 ) break;
2416 pp = &((*pp)->pNextWin);
2417 }
2418
2419 return pRet;
2420}
2421
2422/*
2423** Return true if it can be determined at compile time that expression
2424** pExpr evaluates to a value that, when cast to an integer, is greater
2425** than zero. False otherwise.
2426**
2427** If an OOM error occurs, this function sets the Parse.db.mallocFailed
2428** flag and returns zero.
2429*/
2430static int windowExprGtZero(Parse *pParse, Expr *pExpr){
2431 int ret = 0;
2432 sqlite3 *db = pParse->db;
2433 sqlite3_value *pVal = 0;
2434 sqlite3ValueFromExpr(db, pExpr, db->enc, SQLITE_AFF_NUMERIC, &pVal);
2435 if( pVal && sqlite3_value_int(pVal)>0 ){
2436 ret = 1;
2437 }
2438 sqlite3ValueFree(pVal);
2439 return ret;
2440}
2441
2442/*
2443** sqlite3WhereBegin() has already been called for the SELECT statement
2444** passed as the second argument when this function is invoked. It generates
2445** code to populate the Window.regResult register for each window function
2446** and invoke the sub-routine at instruction addrGosub once for each row.
2447** sqlite3WhereEnd() is always called before returning.
2448**
2449** This function handles several different types of window frames, which
2450** require slightly different processing. The following pseudo code is
2451** used to implement window frames of the form:
2452**
2453** ROWS BETWEEN <expr1> PRECEDING AND <expr2> FOLLOWING
2454**
2455** Other window frame types use variants of the following:
2456**
2457** ... loop started by sqlite3WhereBegin() ...
2458** if( new partition ){
2459** Gosub flush
2460** }
2461** Insert new row into eph table.
2462**
2463** if( first row of partition ){
2464** // Rewind three cursors, all open on the eph table.
2465** Rewind(csrEnd);
2466** Rewind(csrStart);
2467** Rewind(csrCurrent);
2468**
2469** regEnd = <expr2> // FOLLOWING expression
2470** regStart = <expr1> // PRECEDING expression
2471** }else{
2472** // First time this branch is taken, the eph table contains two
2473** // rows. The first row in the partition, which all three cursors
2474** // currently point to, and the following row.
2475** AGGSTEP
2476** if( (regEnd--)<=0 ){
2477** RETURN_ROW
2478** if( (regStart--)<=0 ){
2479** AGGINVERSE
2480** }
2481** }
2482** }
2483** }
2484** flush:
2485** AGGSTEP
2486** while( 1 ){
2487** RETURN ROW
2488** if( csrCurrent is EOF ) break;
2489** if( (regStart--)<=0 ){
2490** AggInverse(csrStart)
2491** Next(csrStart)
2492** }
2493** }
2494**
2495** The pseudo-code above uses the following shorthand:
2496**
2497** AGGSTEP: invoke the aggregate xStep() function for each window function
2498** with arguments read from the current row of cursor csrEnd, then
2499** step cursor csrEnd forward one row (i.e. sqlite3BtreeNext()).
2500**
2501** RETURN_ROW: return a row to the caller based on the contents of the
2502** current row of csrCurrent and the current state of all
2503** aggregates. Then step cursor csrCurrent forward one row.
2504**
2505** AGGINVERSE: invoke the aggregate xInverse() function for each window
2506** functions with arguments read from the current row of cursor
2507** csrStart. Then step csrStart forward one row.
2508**
2509** There are two other ROWS window frames that are handled significantly
2510** differently from the above - "BETWEEN <expr> PRECEDING AND <expr> PRECEDING"
2511** and "BETWEEN <expr> FOLLOWING AND <expr> FOLLOWING". These are special
2512** cases because they change the order in which the three cursors (csrStart,
2513** csrCurrent and csrEnd) iterate through the ephemeral table. Cases that
2514** use UNBOUNDED or CURRENT ROW are much simpler variations on one of these
2515** three.
2516**
2517** ROWS BETWEEN <expr1> PRECEDING AND <expr2> PRECEDING
2518**
2519** ... loop started by sqlite3WhereBegin() ...
2520** if( new partition ){
2521** Gosub flush
2522** }
2523** Insert new row into eph table.
2524** if( first row of partition ){
2525** Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent)
2526** regEnd = <expr2>
2527** regStart = <expr1>
2528** }else{
2529** if( (regEnd--)<=0 ){
2530** AGGSTEP
2531** }
2532** RETURN_ROW
2533** if( (regStart--)<=0 ){
2534** AGGINVERSE
2535** }
2536** }
2537** }
2538** flush:
2539** if( (regEnd--)<=0 ){
2540** AGGSTEP
2541** }
2542** RETURN_ROW
2543**
2544**
2545** ROWS BETWEEN <expr1> FOLLOWING AND <expr2> FOLLOWING
2546**
2547** ... loop started by sqlite3WhereBegin() ...
2548** if( new partition ){
2549** Gosub flush
2550** }
2551** Insert new row into eph table.
2552** if( first row of partition ){
2553** Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent)
2554** regEnd = <expr2>
2555** regStart = regEnd - <expr1>
2556** }else{
2557** AGGSTEP
2558** if( (regEnd--)<=0 ){
2559** RETURN_ROW
2560** }
2561** if( (regStart--)<=0 ){
2562** AGGINVERSE
2563** }
2564** }
2565** }
2566** flush:
2567** AGGSTEP
2568** while( 1 ){
2569** if( (regEnd--)<=0 ){
2570** RETURN_ROW
2571** if( eof ) break;
2572** }
2573** if( (regStart--)<=0 ){
2574** AGGINVERSE
2575** if( eof ) break
2576** }
2577** }
2578** while( !eof csrCurrent ){
2579** RETURN_ROW
2580** }
2581**
2582** For the most part, the patterns above are adapted to support UNBOUNDED by
2583** assuming that it is equivalent to "infinity PRECEDING/FOLLOWING" and
2584** CURRENT ROW by assuming that it is equivilent to "0 PRECEDING/FOLLOWING".
2585** This is optimized of course - branches that will never be taken and
2586** conditions that are always true are omitted from the VM code. The only
2587** exceptional case is:
2588**
2589** ROWS BETWEEN <expr1> FOLLOWING AND UNBOUNDED FOLLOWING
2590**
2591** ... loop started by sqlite3WhereBegin() ...
2592** if( new partition ){
2593** Gosub flush
2594** }
2595** Insert new row into eph table.
2596** if( first row of partition ){
2597** Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent)
2598** regStart = <expr1>
2599** }else{
2600** AGGSTEP
2601** }
2602** }
2603** flush:
2604** AGGSTEP
2605** while( 1 ){
2606** if( (regStart--)<=0 ){
2607** AGGINVERSE
2608** if( eof ) break
2609** }
2610** RETURN_ROW
2611** }
2612** while( !eof csrCurrent ){
2613** RETURN_ROW
2614** }
2615**
2616** Also requiring special handling are the cases:
2617**
2618** ROWS BETWEEN <expr1> PRECEDING AND <expr2> PRECEDING
2619** ROWS BETWEEN <expr1> FOLLOWING AND <expr2> FOLLOWING
2620**
2621** when (expr1 < expr2). This is detected at runtime, not by this function.
2622** To handle this case, the pseudo-code programs depicted above are modified
2623** slightly to be:
2624**
2625** ... loop started by sqlite3WhereBegin() ...
2626** if( new partition ){
2627** Gosub flush
2628** }
2629** Insert new row into eph table.
2630** if( first row of partition ){
2631** Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent)
2632** regEnd = <expr2>
2633** regStart = <expr1>
2634** if( regEnd < regStart ){
2635** RETURN_ROW
2636** delete eph table contents
2637** continue
2638** }
2639** ...
2640**
2641** The new "continue" statement in the above jumps to the next iteration
2642** of the outer loop - the one started by sqlite3WhereBegin().
2643**
2644** The various GROUPS cases are implemented using the same patterns as
2645** ROWS. The VM code is modified slightly so that:
2646**
2647** 1. The else branch in the main loop is only taken if the row just
2648** added to the ephemeral table is the start of a new group. In
2649** other words, it becomes:
2650**
2651** ... loop started by sqlite3WhereBegin() ...
2652** if( new partition ){
2653** Gosub flush
2654** }
2655** Insert new row into eph table.
2656** if( first row of partition ){
2657** Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent)
2658** regEnd = <expr2>
2659** regStart = <expr1>
2660** }else if( new group ){
2661** ...
2662** }
2663** }
2664**
2665** 2. Instead of processing a single row, each RETURN_ROW, AGGSTEP or
2666** AGGINVERSE step processes the current row of the relevant cursor and
2667** all subsequent rows belonging to the same group.
2668**
2669** RANGE window frames are a little different again. As for GROUPS, the
2670** main loop runs once per group only. And RETURN_ROW, AGGSTEP and AGGINVERSE
2671** deal in groups instead of rows. As for ROWS and GROUPS, there are three
2672** basic cases:
2673**
2674** RANGE BETWEEN <expr1> PRECEDING AND <expr2> FOLLOWING
2675**
2676** ... loop started by sqlite3WhereBegin() ...
2677** if( new partition ){
2678** Gosub flush
2679** }
2680** Insert new row into eph table.
2681** if( first row of partition ){
2682** Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent)
2683** regEnd = <expr2>
2684** regStart = <expr1>
2685** }else{
2686** AGGSTEP
2687** while( (csrCurrent.key + regEnd) < csrEnd.key ){
2688** RETURN_ROW
2689** while( csrStart.key + regStart) < csrCurrent.key ){
2690** AGGINVERSE
2691** }
2692** }
2693** }
2694** }
2695** flush:
2696** AGGSTEP
2697** while( 1 ){
2698** RETURN ROW
2699** if( csrCurrent is EOF ) break;
2700** while( csrStart.key + regStart) < csrCurrent.key ){
2701** AGGINVERSE
2702** }
2703** }
2704** }
2705**
2706** In the above notation, "csr.key" means the current value of the ORDER BY
2707** expression (there is only ever 1 for a RANGE that uses an <expr> FOLLOWING
2708** or <expr PRECEDING) read from cursor csr.
2709**
2710** RANGE BETWEEN <expr1> PRECEDING AND <expr2> PRECEDING
2711**
2712** ... loop started by sqlite3WhereBegin() ...
2713** if( new partition ){
2714** Gosub flush
2715** }
2716** Insert new row into eph table.
2717** if( first row of partition ){
2718** Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent)
2719** regEnd = <expr2>
2720** regStart = <expr1>
2721** }else{
2722** while( (csrEnd.key + regEnd) <= csrCurrent.key ){
2723** AGGSTEP
2724** }
2725** while( (csrStart.key + regStart) < csrCurrent.key ){
2726** AGGINVERSE
2727** }
2728** RETURN_ROW
2729** }
2730** }
2731** flush:
2732** while( (csrEnd.key + regEnd) <= csrCurrent.key ){
2733** AGGSTEP
2734** }
2735** while( (csrStart.key + regStart) < csrCurrent.key ){
2736** AGGINVERSE
2737** }
2738** RETURN_ROW
2739**
2740** RANGE BETWEEN <expr1> FOLLOWING AND <expr2> FOLLOWING
2741**
2742** ... loop started by sqlite3WhereBegin() ...
2743** if( new partition ){
2744** Gosub flush
2745** }
2746** Insert new row into eph table.
2747** if( first row of partition ){
2748** Rewind(csrEnd) ; Rewind(csrStart) ; Rewind(csrCurrent)
2749** regEnd = <expr2>
2750** regStart = <expr1>
2751** }else{
2752** AGGSTEP
2753** while( (csrCurrent.key + regEnd) < csrEnd.key ){
2754** while( (csrCurrent.key + regStart) > csrStart.key ){
2755** AGGINVERSE
2756** }
2757** RETURN_ROW
2758** }
2759** }
2760** }
2761** flush:
2762** AGGSTEP
2763** while( 1 ){
2764** while( (csrCurrent.key + regStart) > csrStart.key ){
2765** AGGINVERSE
2766** if( eof ) break "while( 1 )" loop.
2767** }
2768** RETURN_ROW
2769** }
2770** while( !eof csrCurrent ){
2771** RETURN_ROW
2772** }
2773**
2774** The text above leaves out many details. Refer to the code and comments
2775** below for a more complete picture.
2776*/
2777void sqlite3WindowCodeStep(
2778 Parse *pParse, /* Parse context */
2779 Select *p, /* Rewritten SELECT statement */
2780 WhereInfo *pWInfo, /* Context returned by sqlite3WhereBegin() */
2781 int regGosub, /* Register for OP_Gosub */
2782 int addrGosub /* OP_Gosub here to return each row */
2783){
2784 Window *pMWin = p->pWin;
2785 ExprList *pOrderBy = pMWin->pOrderBy;
2786 Vdbe *v = sqlite3GetVdbe(pParse);
2787 int csrWrite; /* Cursor used to write to eph. table */
2788 int csrInput = p->pSrc->a[0].iCursor; /* Cursor of sub-select */
2789 int nInput = p->pSrc->a[0].pTab->nCol; /* Number of cols returned by sub */
2790 int iInput; /* To iterate through sub cols */
2791 int addrNe; /* Address of OP_Ne */
2792 int addrGosubFlush = 0; /* Address of OP_Gosub to flush: */
2793 int addrInteger = 0; /* Address of OP_Integer */
2794 int addrEmpty; /* Address of OP_Rewind in flush: */
2795 int regNew; /* Array of registers holding new input row */
2796 int regRecord; /* regNew array in record form */
2797 int regNewPeer = 0; /* Peer values for new row (part of regNew) */
2798 int regPeer = 0; /* Peer values for current row */
2799 int regFlushPart = 0; /* Register for "Gosub flush_partition" */
2800 WindowCodeArg s; /* Context object for sub-routines */
2801 int lblWhereEnd; /* Label just before sqlite3WhereEnd() code */
2802 int regStart = 0; /* Value of <expr> PRECEDING */
2803 int regEnd = 0; /* Value of <expr> FOLLOWING */
2804
2805 assert( pMWin->eStart==TK_PRECEDING || pMWin->eStart==TK_CURRENT
2806 || pMWin->eStart==TK_FOLLOWING || pMWin->eStart==TK_UNBOUNDED
2807 );
2808 assert( pMWin->eEnd==TK_FOLLOWING || pMWin->eEnd==TK_CURRENT
2809 || pMWin->eEnd==TK_UNBOUNDED || pMWin->eEnd==TK_PRECEDING
2810 );
2811 assert( pMWin->eExclude==0 || pMWin->eExclude==TK_CURRENT
2812 || pMWin->eExclude==TK_GROUP || pMWin->eExclude==TK_TIES
2813 || pMWin->eExclude==TK_NO
2814 );
2815
2816 lblWhereEnd = sqlite3VdbeMakeLabel(pParse);
2817
2818 /* Fill in the context object */
2819 memset(&s, 0, sizeof(WindowCodeArg));
2820 s.pParse = pParse;
2821 s.pMWin = pMWin;
2822 s.pVdbe = v;
2823 s.regGosub = regGosub;
2824 s.addrGosub = addrGosub;
2825 s.current.csr = pMWin->iEphCsr;
2826 csrWrite = s.current.csr+1;
2827 s.start.csr = s.current.csr+2;
2828 s.end.csr = s.current.csr+3;
2829
2830 /* Figure out when rows may be deleted from the ephemeral table. There
2831 ** are four options - they may never be deleted (eDelete==0), they may
2832 ** be deleted as soon as they are no longer part of the window frame
2833 ** (eDelete==WINDOW_AGGINVERSE), they may be deleted as after the row
2834 ** has been returned to the caller (WINDOW_RETURN_ROW), or they may
2835 ** be deleted after they enter the frame (WINDOW_AGGSTEP). */
2836 switch( pMWin->eStart ){
2837 case TK_FOLLOWING:
2838 if( pMWin->eFrmType!=TK_RANGE
2839 && windowExprGtZero(pParse, pMWin->pStart)
2840 ){
2841 s.eDelete = WINDOW_RETURN_ROW;
2842 }
2843 break;
2844 case TK_UNBOUNDED:
2845 if( windowCacheFrame(pMWin)==0 ){
2846 if( pMWin->eEnd==TK_PRECEDING ){
2847 if( pMWin->eFrmType!=TK_RANGE
2848 && windowExprGtZero(pParse, pMWin->pEnd)
2849 ){
2850 s.eDelete = WINDOW_AGGSTEP;
2851 }
2852 }else{
2853 s.eDelete = WINDOW_RETURN_ROW;
2854 }
2855 }
2856 break;
2857 default:
2858 s.eDelete = WINDOW_AGGINVERSE;
2859 break;
2860 }
2861
2862 /* Allocate registers for the array of values from the sub-query, the
2863 ** samve values in record form, and the rowid used to insert said record
2864 ** into the ephemeral table. */
2865 regNew = pParse->nMem+1;
2866 pParse->nMem += nInput;
2867 regRecord = ++pParse->nMem;
2868 s.regRowid = ++pParse->nMem;
2869
2870 /* If the window frame contains an "<expr> PRECEDING" or "<expr> FOLLOWING"
2871 ** clause, allocate registers to store the results of evaluating each
2872 ** <expr>. */
2873 if( pMWin->eStart==TK_PRECEDING || pMWin->eStart==TK_FOLLOWING ){
2874 regStart = ++pParse->nMem;
2875 }
2876 if( pMWin->eEnd==TK_PRECEDING || pMWin->eEnd==TK_FOLLOWING ){
2877 regEnd = ++pParse->nMem;
2878 }
2879
2880 /* If this is not a "ROWS BETWEEN ..." frame, then allocate arrays of
2881 ** registers to store copies of the ORDER BY expressions (peer values)
2882 ** for the main loop, and for each cursor (start, current and end). */
2883 if( pMWin->eFrmType!=TK_ROWS ){
2884 int nPeer = (pOrderBy ? pOrderBy->nExpr : 0);
2885 regNewPeer = regNew + pMWin->nBufferCol;
2886 if( pMWin->pPartition ) regNewPeer += pMWin->pPartition->nExpr;
2887 regPeer = pParse->nMem+1; pParse->nMem += nPeer;
2888 s.start.reg = pParse->nMem+1; pParse->nMem += nPeer;
2889 s.current.reg = pParse->nMem+1; pParse->nMem += nPeer;
2890 s.end.reg = pParse->nMem+1; pParse->nMem += nPeer;
2891 }
2892
2893 /* Load the column values for the row returned by the sub-select
2894 ** into an array of registers starting at regNew. Assemble them into
2895 ** a record in register regRecord. */
2896 for(iInput=0; iInput<nInput; iInput++){
2897 sqlite3VdbeAddOp3(v, OP_Column, csrInput, iInput, regNew+iInput);
2898 }
2899 sqlite3VdbeAddOp3(v, OP_MakeRecord, regNew, nInput, regRecord);
2900
2901 /* An input row has just been read into an array of registers starting
2902 ** at regNew. If the window has a PARTITION clause, this block generates
2903 ** VM code to check if the input row is the start of a new partition.
2904 ** If so, it does an OP_Gosub to an address to be filled in later. The
2905 ** address of the OP_Gosub is stored in local variable addrGosubFlush. */
2906 if( pMWin->pPartition ){
2907 int addr;
2908 ExprList *pPart = pMWin->pPartition;
2909 int nPart = pPart->nExpr;
2910 int regNewPart = regNew + pMWin->nBufferCol;
2911 KeyInfo *pKeyInfo = sqlite3KeyInfoFromExprList(pParse, pPart, 0, 0);
2912
2913 regFlushPart = ++pParse->nMem;
2914 addr = sqlite3VdbeAddOp3(v, OP_Compare, regNewPart, pMWin->regPart, nPart);
2915 sqlite3VdbeAppendP4(v, (void*)pKeyInfo, P4_KEYINFO);
2916 sqlite3VdbeAddOp3(v, OP_Jump, addr+2, addr+4, addr+2);
2917 VdbeCoverageEqNe(v);
2918 addrGosubFlush = sqlite3VdbeAddOp1(v, OP_Gosub, regFlushPart);
2919 VdbeComment((v, "call flush_partition"));
2920 sqlite3VdbeAddOp3(v, OP_Copy, regNewPart, pMWin->regPart, nPart-1);
2921 }
2922
2923 /* Insert the new row into the ephemeral table */
2924 sqlite3VdbeAddOp2(v, OP_NewRowid, csrWrite, s.regRowid);
2925 sqlite3VdbeAddOp3(v, OP_Insert, csrWrite, regRecord, s.regRowid);
2926 addrNe = sqlite3VdbeAddOp3(v, OP_Ne, pMWin->regOne, 0, s.regRowid);
2927 VdbeCoverageNeverNull(v);
2928
2929 /* This block is run for the first row of each partition */
2930 s.regArg = windowInitAccum(pParse, pMWin);
2931
2932 if( regStart ){
2933 sqlite3ExprCode(pParse, pMWin->pStart, regStart);
2934 windowCheckValue(pParse, regStart, 0 + (pMWin->eFrmType==TK_RANGE?3:0));
2935 }
2936 if( regEnd ){
2937 sqlite3ExprCode(pParse, pMWin->pEnd, regEnd);
2938 windowCheckValue(pParse, regEnd, 1 + (pMWin->eFrmType==TK_RANGE?3:0));
2939 }
2940
2941 if( pMWin->eFrmType!=TK_RANGE && pMWin->eStart==pMWin->eEnd && regStart ){
2942 int op = ((pMWin->eStart==TK_FOLLOWING) ? OP_Ge : OP_Le);
2943 int addrGe = sqlite3VdbeAddOp3(v, op, regStart, 0, regEnd);
2944 VdbeCoverageNeverNullIf(v, op==OP_Ge); /* NeverNull because bound <expr> */
2945 VdbeCoverageNeverNullIf(v, op==OP_Le); /* values previously checked */
2946 windowAggFinal(&s, 0);
2947 sqlite3VdbeAddOp2(v, OP_Rewind, s.current.csr, 1);
2948 VdbeCoverageNeverTaken(v);
2949 windowReturnOneRow(&s);
2950 sqlite3VdbeAddOp1(v, OP_ResetSorter, s.current.csr);
2951 sqlite3VdbeAddOp2(v, OP_Goto, 0, lblWhereEnd);
2952 sqlite3VdbeJumpHere(v, addrGe);
2953 }
2954 if( pMWin->eStart==TK_FOLLOWING && pMWin->eFrmType!=TK_RANGE && regEnd ){
2955 assert( pMWin->eEnd==TK_FOLLOWING );
2956 sqlite3VdbeAddOp3(v, OP_Subtract, regStart, regEnd, regStart);
2957 }
2958
2959 if( pMWin->eStart!=TK_UNBOUNDED ){
2960 sqlite3VdbeAddOp2(v, OP_Rewind, s.start.csr, 1);
2961 VdbeCoverageNeverTaken(v);
2962 }
2963 sqlite3VdbeAddOp2(v, OP_Rewind, s.current.csr, 1);
2964 VdbeCoverageNeverTaken(v);
2965 sqlite3VdbeAddOp2(v, OP_Rewind, s.end.csr, 1);
2966 VdbeCoverageNeverTaken(v);
2967 if( regPeer && pOrderBy ){
2968 sqlite3VdbeAddOp3(v, OP_Copy, regNewPeer, regPeer, pOrderBy->nExpr-1);
2969 sqlite3VdbeAddOp3(v, OP_Copy, regPeer, s.start.reg, pOrderBy->nExpr-1);
2970 sqlite3VdbeAddOp3(v, OP_Copy, regPeer, s.current.reg, pOrderBy->nExpr-1);
2971 sqlite3VdbeAddOp3(v, OP_Copy, regPeer, s.end.reg, pOrderBy->nExpr-1);
2972 }
2973
2974 sqlite3VdbeAddOp2(v, OP_Goto, 0, lblWhereEnd);
2975
2976 sqlite3VdbeJumpHere(v, addrNe);
2977
2978 /* Beginning of the block executed for the second and subsequent rows. */
2979 if( regPeer ){
2980 windowIfNewPeer(pParse, pOrderBy, regNewPeer, regPeer, lblWhereEnd);
2981 }
2982 if( pMWin->eStart==TK_FOLLOWING ){
2983 windowCodeOp(&s, WINDOW_AGGSTEP, 0, 0);
2984 if( pMWin->eEnd!=TK_UNBOUNDED ){
2985 if( pMWin->eFrmType==TK_RANGE ){
2986 int lbl = sqlite3VdbeMakeLabel(pParse);
2987 int addrNext = sqlite3VdbeCurrentAddr(v);
2988 windowCodeRangeTest(&s, OP_Ge, s.current.csr, regEnd, s.end.csr, lbl);
2989 windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 0);
2990 windowCodeOp(&s, WINDOW_RETURN_ROW, 0, 0);
2991 sqlite3VdbeAddOp2(v, OP_Goto, 0, addrNext);
2992 sqlite3VdbeResolveLabel(v, lbl);
2993 }else{
2994 windowCodeOp(&s, WINDOW_RETURN_ROW, regEnd, 0);
2995 windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 0);
2996 }
2997 }
2998 }else
2999 if( pMWin->eEnd==TK_PRECEDING ){
3000 int bRPS = (pMWin->eStart==TK_PRECEDING && pMWin->eFrmType==TK_RANGE);
3001 windowCodeOp(&s, WINDOW_AGGSTEP, regEnd, 0);
3002 if( bRPS ) windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 0);
3003 windowCodeOp(&s, WINDOW_RETURN_ROW, 0, 0);
3004 if( !bRPS ) windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 0);
3005 }else{
3006 int addr = 0;
3007 windowCodeOp(&s, WINDOW_AGGSTEP, 0, 0);
3008 if( pMWin->eEnd!=TK_UNBOUNDED ){
3009 if( pMWin->eFrmType==TK_RANGE ){
3010 int lbl = 0;
3011 addr = sqlite3VdbeCurrentAddr(v);
3012 if( regEnd ){
3013 lbl = sqlite3VdbeMakeLabel(pParse);
3014 windowCodeRangeTest(&s, OP_Ge, s.current.csr, regEnd, s.end.csr, lbl);
3015 }
3016 windowCodeOp(&s, WINDOW_RETURN_ROW, 0, 0);
3017 windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 0);
3018 if( regEnd ){
3019 sqlite3VdbeAddOp2(v, OP_Goto, 0, addr);
3020 sqlite3VdbeResolveLabel(v, lbl);
3021 }
3022 }else{
3023 if( regEnd ){
3024 addr = sqlite3VdbeAddOp3(v, OP_IfPos, regEnd, 0, 1);
3025 VdbeCoverage(v);
3026 }
3027 windowCodeOp(&s, WINDOW_RETURN_ROW, 0, 0);
3028 windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 0);
3029 if( regEnd ) sqlite3VdbeJumpHere(v, addr);
3030 }
3031 }
3032 }
3033
3034 /* End of the main input loop */
3035 sqlite3VdbeResolveLabel(v, lblWhereEnd);
3036 sqlite3WhereEnd(pWInfo);
3037
3038 /* Fall through */
3039 if( pMWin->pPartition ){
3040 addrInteger = sqlite3VdbeAddOp2(v, OP_Integer, 0, regFlushPart);
3041 sqlite3VdbeJumpHere(v, addrGosubFlush);
3042 }
3043
3044 s.regRowid = 0;
3045 addrEmpty = sqlite3VdbeAddOp1(v, OP_Rewind, csrWrite);
3046 VdbeCoverage(v);
3047 if( pMWin->eEnd==TK_PRECEDING ){
3048 int bRPS = (pMWin->eStart==TK_PRECEDING && pMWin->eFrmType==TK_RANGE);
3049 windowCodeOp(&s, WINDOW_AGGSTEP, regEnd, 0);
3050 if( bRPS ) windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 0);
3051 windowCodeOp(&s, WINDOW_RETURN_ROW, 0, 0);
3052 }else if( pMWin->eStart==TK_FOLLOWING ){
3053 int addrStart;
3054 int addrBreak1;
3055 int addrBreak2;
3056 int addrBreak3;
3057 windowCodeOp(&s, WINDOW_AGGSTEP, 0, 0);
3058 if( pMWin->eFrmType==TK_RANGE ){
3059 addrStart = sqlite3VdbeCurrentAddr(v);
3060 addrBreak2 = windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 1);
3061 addrBreak1 = windowCodeOp(&s, WINDOW_RETURN_ROW, 0, 1);
3062 }else
3063 if( pMWin->eEnd==TK_UNBOUNDED ){
3064 addrStart = sqlite3VdbeCurrentAddr(v);
3065 addrBreak1 = windowCodeOp(&s, WINDOW_RETURN_ROW, regStart, 1);
3066 addrBreak2 = windowCodeOp(&s, WINDOW_AGGINVERSE, 0, 1);
3067 }else{
3068 assert( pMWin->eEnd==TK_FOLLOWING );
3069 addrStart = sqlite3VdbeCurrentAddr(v);
3070 addrBreak1 = windowCodeOp(&s, WINDOW_RETURN_ROW, regEnd, 1);
3071 addrBreak2 = windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 1);
3072 }
3073 sqlite3VdbeAddOp2(v, OP_Goto, 0, addrStart);
3074 sqlite3VdbeJumpHere(v, addrBreak2);
3075 addrStart = sqlite3VdbeCurrentAddr(v);
3076 addrBreak3 = windowCodeOp(&s, WINDOW_RETURN_ROW, 0, 1);
3077 sqlite3VdbeAddOp2(v, OP_Goto, 0, addrStart);
3078 sqlite3VdbeJumpHere(v, addrBreak1);
3079 sqlite3VdbeJumpHere(v, addrBreak3);
3080 }else{
3081 int addrBreak;
3082 int addrStart;
3083 windowCodeOp(&s, WINDOW_AGGSTEP, 0, 0);
3084 addrStart = sqlite3VdbeCurrentAddr(v);
3085 addrBreak = windowCodeOp(&s, WINDOW_RETURN_ROW, 0, 1);
3086 windowCodeOp(&s, WINDOW_AGGINVERSE, regStart, 0);
3087 sqlite3VdbeAddOp2(v, OP_Goto, 0, addrStart);
3088 sqlite3VdbeJumpHere(v, addrBreak);
3089 }
3090 sqlite3VdbeJumpHere(v, addrEmpty);
3091
3092 sqlite3VdbeAddOp1(v, OP_ResetSorter, s.current.csr);
3093 if( pMWin->pPartition ){
3094 if( pMWin->regStartRowid ){
3095 sqlite3VdbeAddOp2(v, OP_Integer, 1, pMWin->regStartRowid);
3096 sqlite3VdbeAddOp2(v, OP_Integer, 0, pMWin->regEndRowid);
3097 }
3098 sqlite3VdbeChangeP1(v, addrInteger, sqlite3VdbeCurrentAddr(v));
3099 sqlite3VdbeAddOp1(v, OP_Return, regFlushPart);
3100 }
3101}
3102
3103#endif /* SQLITE_OMIT_WINDOWFUNC */
3104