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 | */ |
147 | static 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 | } |
157 | static 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 | */ |
166 | struct 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 | */ |
178 | static 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 | } |
189 | static 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 | */ |
206 | struct NthValueCtx { |
207 | i64 nStep; |
208 | sqlite3_value *pValue; |
209 | }; |
210 | static 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 | } |
251 | static 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 | |
263 | static 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 | } |
279 | static 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 | */ |
297 | static 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 | } |
313 | static 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 | */ |
328 | static 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 | } |
341 | static 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 | } |
352 | static 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 | */ |
373 | static 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 | } |
386 | static 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 | } |
397 | static 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 | */ |
410 | struct 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 | */ |
422 | static 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 | } |
442 | static 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 | } |
453 | static 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 | */ |
480 | struct LastValueCtx { |
481 | sqlite3_value *pVal; |
482 | int nVal; |
483 | }; |
484 | |
485 | /* |
486 | ** Implementation of last_value(). |
487 | */ |
488 | static 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 | } |
506 | static 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 | } |
523 | static 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 | } |
530 | static 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 | */ |
548 | static const char row_numberName[] = "row_number" ; |
549 | static const char dense_rankName[] = "dense_rank" ; |
550 | static const char rankName[] = "rank" ; |
551 | static const char percent_rankName[] = "percent_rank" ; |
552 | static const char cume_distName[] = "cume_dist" ; |
553 | static const char ntileName[] = "ntile" ; |
554 | static const char last_valueName[] = "last_value" ; |
555 | static const char nth_valueName[] = "nth_value" ; |
556 | static const char first_valueName[] = "first_value" ; |
557 | static const char leadName[] = "lead" ; |
558 | static 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 | */ |
569 | static 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*/ |
579 | static 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 | */ |
610 | void 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 | |
631 | static 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 | */ |
659 | void 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 | */ |
734 | typedef struct WindowRewrite WindowRewrite; |
735 | struct 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 | */ |
748 | static 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 | } |
830 | static 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 | */ |
857 | static 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 | */ |
891 | static 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 | */ |
932 | static int (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 | |
941 | static 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 | */ |
957 | int 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 | */ |
1121 | void 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 | */ |
1132 | void 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 | */ |
1149 | void 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 | */ |
1164 | static 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 | */ |
1176 | Window *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 | |
1237 | windowAllocErr: |
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 | */ |
1248 | Window *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 | */ |
1275 | void 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 | */ |
1309 | void 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 | */ |
1332 | void 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 | */ |
1354 | int 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 | */ |
1388 | void 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 | */ |
1475 | static 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 | */ |
1522 | static 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 | |
1529 | typedef struct WindowCodeArg WindowCodeArg; |
1530 | typedef struct WindowCsrAndReg WindowCsrAndReg; |
1531 | |
1532 | /* |
1533 | ** See comments above struct WindowCodeArg. |
1534 | */ |
1535 | struct 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 | */ |
1595 | struct 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 | */ |
1614 | static 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 | */ |
1651 | static 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 | */ |
1768 | static 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 | */ |
1807 | static 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 | */ |
1913 | static 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 | */ |
1990 | static 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 | */ |
2022 | static 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 | */ |
2048 | static 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 | */ |
2094 | static 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 | */ |
2226 | static 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 = 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 | */ |
2375 | Window *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 | */ |
2408 | Window *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 | */ |
2430 | static 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 | */ |
2777 | void 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 | |