MySQL 8.4.3
Source Code Documentation
window.h
Go to the documentation of this file.
1/* Copyright (c) 2017, 2024, Oracle and/or its affiliates.
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License, version 2.0,
5 as published by the Free Software Foundation.
6
7 This program is designed to work with certain software (including
8 but not limited to OpenSSL) that is licensed under separate terms,
9 as designated in a particular file or component or in included license
10 documentation. The authors of MySQL hereby grant you an additional
11 permission to link the program and your derivative works with the
12 separately licensed software that they have either included with
13 the program or referenced in the documentation.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License, version 2.0, for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
23*/
24
25#ifndef WINDOWS_INCLUDED
26#define WINDOWS_INCLUDED
27
28#include <assert.h>
29#include <sys/types.h>
30#include <cstring> // std::memcpy
31
32#include "my_inttypes.h"
33#include "sql/enum_query_type.h"
34#include "sql/handler.h"
35#include "sql/mem_root_array.h"
36#include "sql/sql_array.h"
37#include "sql/sql_lex.h"
38#include "sql/sql_list.h"
39#include "sql/table.h"
40#include "sql/thr_malloc.h"
41
42/*
43 Some Window-related symbols must be known to sql_lex.h which is a frequently
44 included header.
45 To avoid that any change to window.h causes a recompilation of the whole
46 server, those symbols go into a separate header: sql/window_lex.h
47*/
48
49class Arg_comparator;
50class Cached_item;
51class Func_ptr;
52class Item;
53class Item_string;
54class Item_sum;
55class PT_border;
56class PT_frame;
57class PT_order_list;
58class PT_window;
59class String;
60class THD;
62template <class T>
63class mem_root_deque;
65
66/**
67 Position hints for the frame buffer are saved for these kind of row
68 accesses, cf. #Window::m_frame_buffer_positions.
69*/
71 WONT_UPDATE_HINT = -1, // special value when using restore_special_row
73 CURRENT = 1,
75 LAST_IN_FRAME = 3,
77 MISC_POSITIONS = 5 // NTH_VALUE, LEAD/LAG have dynamic indexes 5..N
78};
79
80/**
81 The number of windows is limited to avoid the stack blowing up
82 when constructing iterators recursively. There used to be no limit, but
83 it would be unsafe since QEP_shared::m_idx of tmp tables assigned for windows
84 would exceed the old range of its type plan_idx (int8). It
85 has now been widened, so the max number of windows could be increased
86 if need be, modulo other problems. We could also make it a system variable.
87*/
88constexpr int kMaxWindows = 127;
89
90/**
91 Represents the (explicit) window of a SQL 2003 section 7.11 <window clause>,
92 or the implicit (inlined) window of a window function call, or a reference to
93 a named window in a window function call (instead of the inlined definition)
94 before resolution. After resolving referencing instances become unused,
95 having been replaced with the window resolved to in the w.f. call.
96
97 @verbatim
98 Cf. 7.11 <window definition> and <existing window name>
99 6.10 <window name or specification> and
100 <in-line window specification>
101 5.4 <window name>
102 @endverbatim
103
104 See also PT_window (which wraps Window as a parse_tree_node), and the related
105 classes PT_frame, PT_border and PT_exclusion in parse_tree_nodes.
106
107 Currently includes both prepared query and execution state information.
108 The latter is marked as such for ease of separation later.
109*/
110class Window {
111 /*------------------------------------------------------------------------
112 *
113 * Variables stable during execution
114 *
115 *------------------------------------------------------------------------*/
116 protected:
117 Query_block *m_query_block; ///< The SELECT the window is on
118 PT_order_list *const m_partition_by; ///< <window partition clause>
119 PT_order_list *const m_order_by; ///< <window order clause>
120 ORDER *m_sorting_order; ///< merged partition/order by
121 PT_frame *const m_frame; ///< <window frame clause>
122 Item_string *m_name; ///< <window name>
123 /**
124 Position of definition in query's text, 1 for leftmost. References don't
125 count. Thus, anonymous windows in SELECT list, then windows of WINDOW
126 clause, then anonymous windows in ORDER BY.
127 */
129 Item_string *const m_inherit_from; ///< <existing window name>
130 /**
131 If true, m_name is an unbound window reference, other fields
132 are unused.
133 */
134 const bool m_is_reference;
135
136 /**
137 (At least) one window function needs to buffer frame rows for evaluation
138 i.e. it cannot be evaluated on the fly just from previous rows seen
139 */
141
142 /**
143 (At least) one window function needs the peer set of the current row to
144 evaluate the wf for the current row
145 */
147
148 /**
149 (At least) one window function (currently JSON_OBJECTAGG) needs the
150 last peer for the current row to evaluate the wf for the current row.
151 (This is used only during inversion/optimization)
152 */
154
155 /**
156 (At least) one window function needs the cardinality of the partition of
157 the current row to evaluate the wf for the current row
158 */
160
161 /**
162 The functions are optimizable with ROW unit. For example SUM is, MAX is
163 not always optimizable. Optimized means we can use the optimized evaluation
164 path in process_buffered_windowing_record which uses inversion to avoid
165 revisiting all frame rows for every row being evaluated.
166 */
168
169 /**
170 The functions are optimizable with RANGE unit. For example SUM is, MAX is
171 not always optimizable. Optimized means we can use the optimized evaluation
172 path in process_buffered_windowing_record which uses inversion to avoid
173 revisiting all frame rows for every row being evaluated.
174 */
176
177 /**
178 The aggregates (SUM, etc) can be evaluated once for a partition, since it
179 is static, i.e. all rows will have the same value for the aggregates, e.g.
180 ROWS/RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING.
181 */
183
184 /**
185 Window equires re-evaluation of the first row in optimized moving frame mode
186 e.g. FIRST_VALUE.
187 */
189
190 /**
191 Window requires re-evaluation of the last row in optimized moving frame mode
192 e.g. LAST_VALUE.
193 */
195
196 /**
197 The last window to be evaluated at execution time.
198 */
199 bool m_last;
200
201 public:
202 struct st_offset {
205 st_offset() : m_rowno(0), m_from_last(false) {}
206 /**
207 Used for sorting offsets in ascending order for faster traversal of
208 frame buffer tmp file
209 */
210 bool operator<(const st_offset &a) const { return m_rowno < a.m_rowno; }
211 };
212
214 int64 m_rowno; ///< negative values is LEAD
215 st_ll_offset() : m_rowno(INT_MIN64 /* uninitialized marker*/) {}
216 /**
217 Used for sorting offsets in ascending order for faster traversal of
218 frame buffer tmp file
219 */
220 bool operator<(const st_ll_offset &a) const { return m_rowno < a.m_rowno; }
221 };
222
223 struct st_nth {
225 m_offsets; ///< sorted set of NTH_VALUE offsets
226 };
227
228 struct st_lead_lag {
230 m_offsets; ///< sorted set of LEAD/LAG offsets
231 };
232
233 protected:
234 /**
235 Window requires re-evaluation of the Nth row in optimized moving frame mode
236 e.g. NTH_VALUE.
237 */
240
241 protected:
242 const Window *m_ancestor; ///< resolved from existing window name
243 List<Item_sum> m_functions; ///< window functions based on 'this'
245 m_partition_items; ///< items for the PARTITION BY columns
247 m_order_by_items; ///< items for the ORDER BY exprs.
248
249 /*------------------------------------------------------------------------
250 *
251 * Execution state variables
252 *
253 *------------------------------------------------------------------------*/
254 public:
255 /**
256 Cardinality of m_frame_buffer_positions if no NTH_VALUE, LEAD/LAG
257 */
258 static constexpr int FRAME_BUFFER_POSITIONS_CARD =
260
261 /**
262 Holds information about a position in the buffer frame as stored in a
263 temporary file (cf. m_frame_buffer). We save a number of such positions
264 to speed up lookup when we move the window frame, cf.
265 m_frame_buffer_positions
266 */
268 ///< The size of the file position is determined by handler::ref_length
270 ///< Row number in partition, 1-based
273 : m_position(position), m_rowno(rowno) {}
274 };
275
276 /**
277 Execution state: used iff m_needs_frame_buffering. Holds pointers to
278 positions in the file in m_frame_buffer. We use these saved positions to
279 avoid having to position to the first row in the partition and then
280 making many read calls to find the desired row. By repositioning to a
281 suitably(*) saved position we normally (**) need to do only one positioned
282 read and one ha_rdn_next call to get at a desired row.
283 @verbatim
284
285 [0] the first row in the partition: at the
286 beginning of a new partition that is the first row in the partition.
287 Its rowno == 1 by definition.
288 [1] position of the current row N (for jump-back to current row or next
289 current row in combo with ha_rnd_next)
290 [2] position of the current first row M in frame (for aggregation looping
291 jump-back)
292 [3] position of the current last row in a frame
293 [4] position and line number of the row last read
294 and optionally:
295 [5..X] positions of Nth row of X-5+1 NTH_VALUE functions invoked on window
296 [X+1..Y] position of last row of lead/lag functions invoked on window
297
298 @endverbatim
299 Pointers are lazily initialized if needed.
300
301 (*) We use the position closest below the desired position, cf logic in
302 read_frame_buffer_row.
303
304 (**) Unless we have a frame beyond the current row, in which case we need
305 to do some scanning for the first row in the partition.
306 Also NTH_VALUE with RANGE might sometimes needs to read several rows, since
307 the frame start can jump several rows ahead when the current row moves
308 forward.
309 */
311
312 /**
313 Sometimes we read one row too many, so that the saved position will
314 be too far out because we subsequently need to read an earlier (previous)
315 row of the same kind (reason). For such cases, we first save the
316 current position, read, and if we see we read too far, restore the old
317 position. See #save_pos and #restore_pos.
318 */
320
321 /**
322 See #m_tmp_pos
323 */
325 const int reason_index = static_cast<int>(reason);
326 m_tmp_pos.m_rowno = m_frame_buffer_positions[reason_index].m_rowno;
327 std::memcpy(m_tmp_pos.m_position,
328 m_frame_buffer_positions[reason_index].m_position,
329 frame_buffer()->file->ref_length);
330 }
331
332 /**
333 See #m_tmp_pos
334 */
337 m_tmp_pos.m_rowno == -1) {
338 // restore the more useful position of first in frame row instead of -1 in
339 // order to get the sliding window positions (first,last) started
341 }
342
343 const int reason_index = static_cast<int>(reason);
344 m_frame_buffer_positions[reason_index].m_rowno = m_tmp_pos.m_rowno;
345 std::memcpy(m_frame_buffer_positions[reason_index].m_position,
346 m_tmp_pos.m_position, frame_buffer()->file->ref_length);
347 }
348
349 /**
350 Copy frame buffer position hint from one to another.
351 */
354 const int from_index = static_cast<int>(from_reason);
355 const int to_index = static_cast<int>(to_reason);
356 m_frame_buffer_positions[to_index].m_rowno =
357 m_frame_buffer_positions[from_index].m_rowno;
358
359 std::memcpy(m_frame_buffer_positions[to_index].m_position,
360 m_frame_buffer_positions[from_index].m_position,
361 frame_buffer()->file->ref_length);
362 }
363
364 /**
365 Keys for m_special_rows_cache, for special
366 rows (see the comment on m_special_row_cache). Note that they are negative,
367 so that they will never collide with actual row numbers in the frame.
368 This allows us to treat them interchangeably with real row numbers
369 as function arguments; e.g., bring_back_frame_row() can restore either
370 a “normal” row from the frame, or one of the special rows, and does not
371 need to take in separate flags for the two.
372 TODO(Chaithra): We have only one special key. Do we need the enum?
373 Also m_special_rows_cache/cache_length/max_cache_length should be looked
374 into.
375 */
377 /**
378 We read an incoming row. We notice it is the start of a new
379 partition. We must thus process the just-finished partition, but that
380 processing uses this row's buffer; so, we save this row first, process
381 the partition, and restore it later.
382 */
384 // Insert new values here.
385 // And keep the ones below up to date.
388 };
389
390 protected:
391 /**
392 Execution state: used iff m_needs_frame_buffering. Holds the temporary
393 file (used for the frame buffering) parameters
394 */
396
397 /**
398 Holds whether this window should be “short-circuit”, ie., goes directly
399 to the query output instead of to a temporary table.
400 */
401 bool m_short_circuit = false;
402
403 /**
404 Execution state: used iff m_needs_frame_buffering. Holds the TABLE
405 object for the the temporary file used for the frame buffering.
406 */
408
409 /**
410 Execution state: The frame buffer tmp file is not truncated for each new
411 partition. We need to keep track of where a partition starts in case we
412 need to switch from heap to innodb tmp file on overflow, in order to
413 re-initialize m_frame_buffer_positions with the current partition's row 1
414 (which is the minimum hint required) as we cross over. This number is
415 incremented for each write.
416 */
418
419 /**
420 Execution state: Snapshot of m_frame_buffer_total_rows when we start a new
421 partition, i.e. for the first row in the first partition we will have a
422 value of 1.
423 */
425
426 /**
427 If >=1: the row with this number (1-based, relative to start of
428 partition) currently has its fields in the record buffer of the IN table
429 and of the OUT table. 0 means "unset".
430 Usable only with buffering. Set and read by bring_back_frame_row(), so
431 that multiple successive calls to it for same row do only one read from
432 FB (optimization).
433 */
435
436 /**
437 Holds a fixed number of copies of special rows; each copy can use up to
438 #m_special_rows_cache_max_length bytes. Special rows are those that are
439 not part of our frame, but that we need to store away nevertheless, because
440 they might be in the table's buffers, which we need for our own purposes
441 during window processing.
442 cf. the Special_keys enumeration.
443 */
445 /// Length of each copy in #m_special_rows_cache, in bytes
447 /// Maximum allocated size in #m_special_rows_cache
449
450 /**
451 Execution state: used iff m_needs_frame_buffering. Holds the row
452 number (in the partition) of the last row (hitherto) saved in the frame
453 buffer
454 */
456
457 /**
458 Execution state: used iff m_needs_peerset. Holds the rowno
459 for the last row in this peer set.
460 */
462
463 /**
464 Execution state: used iff m_needs_last_peer_in_frame. True if a row
465 leaving the frame is the last row in the peer set within the frame.
466 */
468
469 /**
470 Execution state: the current row number in the current partition.
471 Set in check_partition_boundary. Used while reading input rows, in contrast
472 to m_rowno_in_partition, which is used when processing buffered rows.
473 Cf. check_partition_boundary.
474 */
476
477 /**
478 Execution state: the current row starts a new partition.
479 Set in check_partition_boundary.
480 */
482
483 /**
484 Execution state: The number, in the current partition, of the last output
485 row, i.e. the row number of the last row hitherto evaluated and output to
486 the next phase.
487 */
489
490 /**
491 Execution state: The number of the row being visited for its contribution
492 to a window function, relative to the start of the partition. Note that
493 this will often be different from the current row for which we are
494 processing the window function, readying it for output. That is given by
495 \c m_rowno_in_partition, q.v. Contrast also with \c m_rowno_in_frame
496 which is frame relative.
497 */
499
500 /**
501 Execution state: the row number of the row we are looking at for evaluating
502 its contribution to some window function(s). It is relative to start of
503 the frame and 1-based. It is typically set after fetching a row from the
504 frame buffer using \c bring_back_frame_row and before calling
505 \c copy_funcs. Cf. also \c m_is_last_row_in_frame.
506 */
508
509 /**
510 Execution state: The row number of the current row being readied for
511 output within the partition. 1-based.
512 In \c process_buffered_windowing_record this is known as \c current_row.
513 */
515
516 /**
517 Execution state: for optimizable aggregates, cf. m_row_optimizable and
518 m_range_optimizable, we need to keep track of when we have computed the
519 first aggregate, since aggregates for rows 2..N are computed in an optimized
520 way by inverse aggregation of the row moving out of the frame.
521 */
523
524 /*------------------------------------------------------------------------
525 *
526 * RANGE boundary frame state variables.
527 *
528 *------------------------------------------------------------------------*/
529 public:
530 /*
531 For RANGE bounds, we need to be able to check if a given row is
532 before the lower bound, or after the upper bound, as we don't know
533 ahead of time how many rows to skip (unlike for ROW bounds).
534 Often, the lower and upper bounds are the same, as they are
535 inclusive.
536
537 We solve this by having an array of comparators of the type
538
539 value ⋛ <cache>(ref_value)
540
541 where ⋛ is a three-way comparator, and <cache>(ref_value) is an
542 Item_cache where we can store the value of the reference row
543 before we invoke the comparison. For instance, if we have a
544 row bound such as
545
546 ... OVER (ORDER BY a,b) FROM t1
547
548 we will have an array with the two comparators
549
550 t1.a ⋛ <cache>(a)
551 t1.b ⋛ <cache>(b)
552
553 and when we evaluate the frame bounds for a given row, we insert
554 the reference values in the caches and then do the comparison to
555 figure out if we're before, in or after the bound. As this is a
556 lexicographic comparison, we only need to evaluate the second
557 comparator if the first one returns equality.
558
559 The expressions on the right-hand side can be somewhat more
560 complicated; say that we have a window specification like
561
562 ... OVER (ORDER BY a RANGE BETWEEN 2 PRECEDING AND 3 FOLLOWING)
563
564 In this case, the lower bound and upper bound are different
565 (both arrays will always contain only a single element):
566
567 Lower: t1.a ⋛ <cache>(a) - 2
568 Upper: t1.a ⋛ <cache>(a) + 3
569
570 ie., there is an Item_func_plus or Item_func_minus with some
571 constant expression as the second argument.
572
573 The comparators for the lower bound is stored in [0], and for
574 the upper bound in [1].
575 */
577
578 /**
579 The logical ordering index (into LogicalOrderings) needed by this window's
580 PARTITION BY and ORDER BY clauses together (if any; else, 0). Used only by
581 the hypergraph join optimizer.
582 */
584
585 /**
586 Used temporarily by the hypergraph join optimizer to mark which windows
587 are referred to by a given ordering (so that one doesn't try to satisfy
588 a window's ordering by an ordering referring to that window).
589 */
590 bool m_mark;
591
592 protected:
593 /**
594 Execution state: the row number of the first row in a frame when evaluating
595 RANGE based frame bounds. When using RANGE bounds, we don't know a priori
596 when moving the frame which row number will be the next lower bound, but
597 we know it will have to be a row number higher than the lower bound of
598 the previous frame, since the bounds increase monotonically as long
599 as the frame bounds are static within the query (current limitation).
600 So, it makes sense to remember the first row number in a frame until
601 we have determined the start of the next frame.
602
603 If the frame for the previous current row in the partition was empty (cf.
604 "current_row" in process_buffered_windowing_record), this should point
605 to the next possible frame start. Relative to partition start, 1-based.
606 */
608
609 /**
610 Execution state: used for RANGE bounds frame evaluation
611 for the continued evaluation for current row > 2 in a partition.
612 If the frame for the current row visited (cf "current_row" in
613 process_buffered_windowing_record) was empty, the invariant
614
615 m_last_rowno_in_range_frame < m_first_rowno_in_range_frame
616
617 should hold after the visit. Relative to partition start. 1-based.
618 */
620
621 /**
622 Execution state. Only used for ROWS frame optimized MIN/MAX.
623 The (1-based) number in the partition of first row in the current frame.
624 */
626
627 /*------------------------------------------------------------------------
628 *
629 * Window function special behaviour toggles. These boolean flag influence
630 * the action taken when a window function is evaluated, i.e.
631 *
632 * Item_xxx::val_xxx
633 *
634 * They are set locally just before and after a call to evaluate functions,
635 * i.e.
636 *
637 * w.set_<toggle>(true)
638 * copy_<kind>_window_functions() [see process_buffered_windowing_record]
639 * w.set_<toggle>(false)
640 *
641 * to achieve a special semantic, since we cannot pass down extra parameters.
642 *
643 *------------------------------------------------------------------------*/
644
645 /**
646 Execution state: the current row is the last row in a window frame
647 For some aggregate functions, e.g AVG, we can save computation by not
648 evaluating the entire function value before the last row has been read.
649 For AVG, do the summation for each row in the frame, but the division only
650 for the last row, at which time the result is needed for the wf.
651 Probably only useful for ROW based or static frames.
652 For frame with peer set computation, determining the last row in the
653 peer set ahead of processing is not possible, so we use a pessimistic
654 assumption.
655 */
657
658 /**
659 Execution state: make frame wf produce a NULL (or 0 depending, e.g. if
660 COUNT) value because no rows are available for aggregation: e.g. for first
661 row in partition if frame is ROWS BETWEEN 2 PRECEDING and 1 PRECEDING has
662 no rows for which aggregation can happen
663 */
665
666 /**
667 Execution state: do inverse, e.g. subtract rather than add in aggregates.
668 Used for optimizing computation of sliding frames for eligible aggregates,
669 cf. Item_sum::check_wf_semantics.
670 */
672
673 /*------------------------------------------------------------------------
674 *
675 * Constructors
676 *
677 *------------------------------------------------------------------------*/
678 private:
679 /**
680 Generic window constructor, shared
681 */
683 PT_frame *frame, bool is_reference, Item_string *inherit)
685 m_partition_by(part),
686 m_order_by(ord),
688 m_frame(frame),
689 m_name(name),
690 m_def_pos(0),
691 m_inherit_from(inherit),
694 m_needs_peerset(false),
697 m_row_optimizable(true),
699 m_static_aggregates(false),
700 m_opt_first_row(false),
701 m_opt_last_row(false),
702 m_last(false),
706 m_tmp_pos(nullptr, -1),
717 m_partition_border(true),
722 m_aggregates_primed(false),
726 m_do_copy_null(false),
727 m_inverse_aggregation(false) {
728 m_opt_nth_row.m_offsets.init_empty_const();
729 m_opt_lead_lag.m_offsets.init_empty_const();
730 m_frame_buffer_positions.init_empty_const();
731 }
732
733 public:
734 /**
735 Reference to a named window. This kind is only used before resolution,
736 references to it being replaced by the referenced window object thereafter.
737 */
739 : Window(name, nullptr, nullptr, nullptr, true, nullptr) {}
740
741 /**
742 Unnamed window. If the window turns out to be named, the name will be set
743 later, cf. #set_name().
744 */
745 Window(PT_order_list *partition_by, PT_order_list *order_by, PT_frame *frame)
746 : Window(nullptr, partition_by, order_by, frame, false, nullptr) {}
747
748 /**
749 Unnamed window based on a named window. If the window turns out to be
750 named, the name will be set later, cf. #set_name().
751 */
752 Window(PT_order_list *partition_by, PT_order_list *order_by, PT_frame *frame,
753 Item_string *inherit)
754 : Window(nullptr, partition_by, order_by, frame, false, inherit) {}
755
756 /*------------------------------------------------------------------------
757 *
758 * Methods
759 *
760 *------------------------------------------------------------------------*/
761
762 /**
763 We have a named window. Now set its name. Used once, if at all, for a
764 window as part of parsing.
765 */
767
768 /**
769 After resolving an existing window name reference in a window definition,
770 we set the ancestor pointer to easy access later.
771 */
773
774 /**
775 Get the name of a window. Can be empty, cf. #printable_name which is not.
776 */
777 Item_string *name() const { return m_name; }
778
779 uint def_pos() const { return m_def_pos; } ///< @see #m_def_pos
780 void set_def_pos(uint pos) { m_def_pos = pos; } ///< @see #m_def_pos
781
782 /**
783 Get the frame, if any. SQL 2011 7.11 GR 1.b.i.6
784 */
785 const PT_frame *frame() const { return m_frame; }
786
787 /**
788 Get the ORDER BY, if any. That is, the first we find along
789 the ancestor chain. Uniqueness checked in #setup_windows1
790 SQL 2011 7.11 GR 1.b.i.5.A-C
791 */
793 const PT_order_list *o = m_order_by;
794 const Window *w = m_ancestor;
795
796 while (o == nullptr && w != nullptr) {
797 o = w->m_order_by;
798 w = w->m_ancestor;
799 }
800 return o;
801 }
802
803 /**
804 Get the first argument of the ORDER BY clause for this window
805 if any. "ORDER BY" is not checked in ancestor unlike
806 effective_order_by().
807 Use when the goal is to operate on the set of item clauses for
808 all windows of a query. When interrogating the effective order
809 by for a window (specified for it or inherited from another
810 window) use effective_order_by().
811 */
812 ORDER *first_order_by() const;
813
814 /**
815 Get partition, if any. That is, the partition if any, of the
816 root window. SQL 2011 7.11 GR 1.b.i.4.A-C
817 */
820 const Window *w = m_ancestor;
821 while (w != nullptr) {
822 if (w->m_ancestor == nullptr) {
823 /* root */
824 p = w->m_partition_by;
825 } else {
826 /* See #setup_windows for checking */
827 assert(w->m_partition_by == nullptr);
828 }
829 w = w->m_ancestor;
830 }
831 return p;
832 }
833 /**
834 Get the first argument of the PARTITION clause for this window
835 if any. "PARTITION BY" is not checked in ancestor unlike
836 effective_partition_by().
837 Use when the goal is to operate on the set of item clauses for
838 all windows of a query. When interrogating the effective
839 partition by for a window (specified for it or inherited from
840 another window) use effective_partition_by().
841 */
842 ORDER *first_partition_by() const;
843
844 /**
845 Get the list of functions invoked on this window.
846 */
848
849 /**
850 Concatenation of columns in PARTITION BY and ORDER BY.
851 Columns present in both list (redundancies) are eliminated, while
852 making sure the order of columns in the ORDER BY is maintained
853 in the merged list.
854
855 @param thd Optional. Session state. If not nullptr,
856 initialize the cache.
857
858 @param implicit_grouping Optional. If true, we won't sort (single row
859 result set). Presence implies thd != nullptr for
860 the first call when we lazily set up this
861 information. Succeeding calls return the cached
862 value.
863
864 @returns The start of the concatenated ordering expressions, or nullptr
865 */
866 ORDER *sorting_order(THD *thd = nullptr, bool implicit_grouping = false);
867
868 /**
869 Check that the semantic requirements for window functions over this
870 window are fulfilled, and accumulate evaluation requirements.
871 This is run at resolution.
872 */
873 bool check_window_functions1(THD *thd, Query_block *select);
874 /**
875 Like check_window_functions1() but contains checks which must wait until
876 the start of the execution phase.
877 */
878 bool check_window_functions2(THD *thd);
879
880 /**
881 For RANGE frames we need to do computations involving add/subtract and
882 less than, smaller than. To make this work across types, we construct
883 item trees to do the computations, so we can reuse all the special case
884 handling, e.g. for signed/unsigned int wrap-around, overflow etc.
885 */
886 bool setup_range_expressions(THD *thd);
887
888 /**
889 Return if this window represents an unresolved window reference seen
890 in a window function OVER clause.
891 */
892 bool is_reference() const { return m_is_reference; }
893
894 /**
895 Check if the just read input row marks the start of a new partition.
896 Sets the member variables:
897
898 m_partition_border and m_part_row_number
899
900 */
902
903 /**
904 Reset the current row's ORDER BY expressions when starting a new
905 peer set.
906 */
908
909 /**
910 Determine if the current row is not in the same peer set as the previous
911 row. Used for RANGE frame and implicit RANGE frame (the latter is used by
912 aggregates in the presence of ORDER BY).
913
914 The current row is in the same peer set if all ORDER BY columns
915 have the same value as in the previous row.
916
917 For JSON_OBJECTAGG only the first order by column needs to be
918 compared to check if a row is in peer set.
919
920 @param compare_all_order_by_items If true, compare all the order by items
921 to determine if a row is in peer set.
922 Else, compare only the first order by
923 item to determine peer set.
924
925 @return true if current row is in a new peer set
926 */
927 bool in_new_order_by_peer_set(bool compare_all_order_by_items = true);
928
929 /**
930 While processing buffered rows in RANGE frame mode we, determine
931 if the present row revisited from the buffer is before the row
932 being processed; i.e. the current row.
933
934 @return true if the present row is before the RANGE, i.e. not to
935 be included
936 */
937 bool before_frame() { return before_or_after_frame(true); }
938
939 ///< See before_frame()
940 bool after_frame() { return before_or_after_frame(false); }
941
942 /**
943 Check if we have read all the rows in a partition, possibly
944 having buffered them for further processing
945
946 @returns true if this is the case
947 */
949
950 void save_special_row(uint64 special_rowno, TABLE *t);
951 void restore_special_row(uint64 special_rowno, uchar *record);
952
953 /**
954 Resolve any named window to its definition
955 and update m_window to point to the definition instead
956 */
957 static bool resolve_reference(THD *thd, Item_sum *wf, PT_window **m_window);
958
959 /**
960 Semantic checking of windows. Run at resolution.
961
962 * Process any window inheritance, that is a window, that in its
963 specification refer to another named window.
964
965 Rules:
966 1) There should be no loops
967 2) The inheriting window can not specify partitioning
968 3) The inheriting window can not specify is already specify by
969 an ancestor.
970 4) An ancestor can not specify window framing clause.
971
972 Cf. SQL 2011 7.11 window clause SR 10-11.
973
974 * Check requirements to the window from its using window functions and
975 make a note of those so we know at execution time, for example if we need
976 to buffer rows to process the window functions, whether inversion
977 optimzation will be used for moving frames etc.
978
979 * Prepare the physical ordering lists used by sorting at execution time.
980
981 * Set up cached items for partition determination and for range/peer
982 determination based on order by columns.
983
984 * Check any frame semantics and for RANGE frames, set up bounds computation
985 item trees.
986
987 @param thd The session's execution thread
988 @param select The select for which we are doing windowing
989 @param ref_item_array The base ref items
990 @param tables The list of tables involved
991 @param fields The list of all fields, including hidden ones
992 @param windows The list of windows defined for this select
993
994 @return false if success, true if error
995 */
996 static bool setup_windows1(THD *thd, Query_block *select,
997 Ref_item_array ref_item_array, Table_ref *tables,
999 List<Window> *windows);
1000 /**
1001 Like setup_windows1() but contains operations which must wait until
1002 the start of the execution phase.
1003
1004 @param thd The session's execution thread
1005 @param windows The list of windows defined for this select
1006
1007 @return false if success, true if error
1008 */
1009 static bool setup_windows2(THD *thd, List<Window> *windows);
1010
1011 /**
1012 Check window definitions to remove unused windows. We do this
1013 only after syntactic and semantic checking for errors has been performed.
1014 Eliminate redundant sorts after unused windows are removed.
1015
1016 @param windows The list of windows defined for this select
1017 */
1018 static void eliminate_unused_objects(List<Window> *windows);
1019
1020 /**
1021 Resolve and set up the PARTITION BY or an ORDER BY list of a window.
1022
1023 @param thd The session's execution thread
1024 @param ref_item_array The base ref items
1025 @param tables The list of tables involved
1026 @param fields The list of all fields, including hidden ones
1027 @param o A list of order by expressions
1028 @param partition_order If true, o represent a windowing PARTITION BY,
1029 else it represents a windowing ORDER BY
1030 @returns false if success, true if error
1031 */
1032 bool resolve_window_ordering(THD *thd, Ref_item_array ref_item_array,
1033 Table_ref *tables,
1034 mem_root_deque<Item *> *fields, ORDER *o,
1035 bool partition_order);
1036 /**
1037 Return true if this window's name is not unique in windows
1038 */
1039 bool check_unique_name(const List<Window> &windows);
1040
1041 /**
1042 Specify that this window is to be evaluated after a given
1043 temporary table. This means that all expressions that have been
1044 materialized (as given by items_to_copy) will be replaced with the
1045 given temporary table fields. (If there are multiple materializations,
1046 this function must be called for each of them in order.)
1047
1048 Only the hypergraph join optimizer uses this currently; the old
1049 join optimizer instead uses Item_ref objects that point to the
1050 base slice, which is then replaced at runtime depending on which
1051 temporary table we are to evaluate from.
1052
1053 @param thd The session's execution thread.
1054 @param items_to_copy The expressions materialized in the temporary table.
1055 @param first True if this is the first temporary table applied to
1056 this window.
1057 */
1058 void apply_temp_table(THD *thd, const Func_ptr_array &items_to_copy,
1059 bool first);
1060
1061 /**
1062 Set up cached items for an partition or an order by list
1063 updating m_partition_items or m_order_by_items respectively.
1064
1065 @param thd The session's execution thread
1066 @param select The select for which we are doing windowing
1067 @param o The list of ordering expressions
1068 @param partition_order If true, o represents a partition order list,
1069 else an ORDER BY list.
1070
1071 @returns false if success, true if error
1072 */
1073 bool setup_ordering_cached_items(THD *thd, Query_block *select,
1074 const PT_order_list *o,
1075 bool partition_order);
1076
1077 /**
1078 Determine if the window had either a partition clause (inclusive) or a
1079 ORDER BY clause, either defined by itself or inherited from another window.
1080
1081 @return true if we have such a clause, which means we need to sort the
1082 input table before evaluating the window functions, unless it has
1083 been made redundant by a previous windowing step, cf.
1084 reorder_and_eliminate_sorts, or due to a single row result set,
1085 cf. Query_block::is_implicitly_grouped().
1086 */
1087 bool needs_sorting() const { return m_sorting_order != nullptr; }
1088
1089 /**
1090 If we cannot compute one of window functions without looking at succeeding
1091 rows, return true, else false.
1092 */
1094
1095 /**
1096 If we cannot compute one of window functions without looking at all
1097 rows in the peerset of the current row, return true, else
1098 false. E.g. CUME_DIST.
1099 */
1100 bool needs_peerset() const { return m_needs_peerset; }
1101
1102 /**
1103 If we cannot compute one of window functions without looking at all
1104 rows in the peerset of the current row in this frame, return true, else
1105 false. E.g. JSON_OBJECTAGG.
1106 */
1108 /**
1109 If we need to read the entire partition before we can evaluate
1110 some window function(s) on this window,
1111 @returns true if that is the case, else false
1112 */
1115 }
1116
1117 /**
1118 Return true if the set of window functions are all ROW unit optimizable.
1119 Only relevant if m_needs_buffering and m_row_optimizable are true.
1120 */
1122
1123 /**
1124 Return true if the set of window functions are all RANGE unit optimizable.
1125 Only relevant if m_needs_buffering and m_range_optimizable are true.
1126 */
1128
1129 /**
1130 Return true if the aggregates are static, i.e. the same aggregate values for
1131 all rows in partition. Only relevant if m_needs_buffering is true.
1132 */
1134
1135 /**
1136 See #m_opt_first_row
1137 */
1138 bool opt_first_row() const { return m_opt_first_row; }
1139
1140 /**
1141 See #m_opt_last_row
1142 */
1143 bool opt_last_row() const { return m_opt_last_row; }
1144
1145 /**
1146 See #m_last
1147 */
1148 bool is_last() const { return m_last; }
1149
1150 /**
1151 An override used by the hypergraph join optimizer only.
1152 */
1153 void set_is_last(bool last) { m_last = last; }
1154
1155 /**
1156 See #m_opt_nth_row
1157 */
1158 const st_nth &opt_nth_row() const { return m_opt_nth_row; }
1159
1160 /**
1161 See #m_opt_lead_lag
1162 */
1163 const st_lead_lag &opt_lead_lag() const { return m_opt_lead_lag; }
1164
1165 /**
1166 Getter for m_frame_buffer_param, q.v.
1167 */
1169
1170 /**
1171 Setter for m_frame_buffer_param, q.v.
1172 */
1174
1175 /**
1176 Getter for m_frame_buffer, q.v.
1177 */
1178 TABLE *frame_buffer() const { return m_frame_buffer; }
1179
1180 /**
1181 Setter for m_frame_buffer, q.v.
1182 */
1184
1185 bool short_circuit() const { return m_short_circuit; }
1188 }
1189
1190 /**
1191 Getter for m_part_row_number, q.v., the current row number within the
1192 partition.
1193 */
1195
1196 /**
1197 Allocate the cache for special rows
1198 @param thd thread handle
1199 @param out_tbl The table where this window function's value is written to
1200 @returns true if error.
1201 */
1202 bool make_special_rows_cache(THD *thd, TABLE *out_tbl);
1203
1204 /**
1205 See #m_last_row_output
1206 */
1208
1209 /**
1210 See #m_last_row_output
1211 */
1213
1214 /**
1215 See #m_rowno_being_visited
1216 */
1218
1219 /**
1220 See #m_rowno_being_visited
1221 */
1223
1224 /**
1225 See #m_last_rowno_in_cache
1226 */
1228
1229 /**
1230 See #m_last_rowno_in_cache
1231 */
1233
1234 /**
1235 See #m_last_rowno_in_range_frame
1236 */
1239 }
1240
1241 /**
1242 See #m_last_rowno_in_range_frame
1243 */
1246 }
1247
1248 /**
1249 See #m_last_rowno_in_peerset
1250 */
1252
1253 /**
1254 See #m_last_rowno_in_peerset
1255 */
1257
1258 /**
1259 See #m_is_last_row_in_peerset_within_frame
1260 */
1263 }
1264
1265 /**
1266 See #m_is_last_row_in_peerset_within_frame
1267 */
1270 }
1271
1272 /**
1273 See #m_do_copy_null
1274 */
1275 bool do_copy_null() const { return m_do_copy_null; }
1276
1277 /**
1278 See #m_do_copy_null
1279 */
1280 void set_do_copy_null(bool b) { m_do_copy_null = b; }
1281
1282 /**
1283 See #m_inverse_aggregation
1284 */
1285 bool do_inverse() const { return m_inverse_aggregation; }
1286
1287 /**
1288 See #m_inverse_aggregation
1289 */
1292 return *this;
1293 }
1294
1295 /**
1296 See #m_aggregates_primed
1297 */
1299
1300 /**
1301 See #m_aggregates_primed
1302 */
1304
1305 /**
1306 See #m_is_last_row_in_frame
1307 */
1309 return m_is_last_row_in_frame || m_query_block->m_table_list.elements == 0;
1310 }
1311
1312 /**
1313 See #m_is_last_row_in_frame
1314 */
1316
1317 /**
1318 Return the size of the frame in number of rows
1319 @returns frame size
1320 */
1321 // int64 frame_cardinality();
1322
1323 /**
1324 See #m_rowno_in_frame
1325 */
1327
1328 /**
1329 See #m_rowno_in_frame
1330 */
1332 m_rowno_in_frame = rowno;
1333 return *this;
1334 }
1335
1336 /**
1337 See #m_rowno_in_partition
1338 */
1340
1341 /**
1342 See #m_rowno_in_partition
1343 */
1345
1346 /**
1347 See #m_first_rowno_in_rows_frame
1348 */
1351 }
1352
1355 }
1356
1357 /**
1358 See #m_first_rowno_in_range_frame
1359 */
1362 }
1363
1364 /**
1365 See #m_first_rowno_in_range_frame
1366 */
1369 }
1370
1371 /**
1372 See #m_frame_buffer_total_rows
1373 */
1376 }
1377
1378 /**
1379 See #m_frame_buffer_total_rows
1380 */
1382
1383 /**
1384 See #m_frame_buffer_partition_offset
1385 */
1388 }
1389
1390 /**
1391 See #m_frame_buffer_partition_offset
1392 */
1395 }
1396
1397 /**
1398 See #m_row_has_fields_in_out_table
1399 */
1402 }
1403
1404 /**
1405 See #m_row_has_fields_in_out_table
1406 */
1409 }
1410
1411 /**
1412 Free up any resource used to process the window functions of this window,
1413 e.g. temporary files and in-memory data structures. Called when done
1414 with all window processing steps from Query_block::cleanup.
1415 */
1416 void cleanup();
1417
1418 /**
1419 Free structures that were set up during preparation of window functions
1420 */
1421 void destroy();
1422
1423 /**
1424 Reset window state for a new partition.
1425
1426 Reset the temporary storage used for window frames, typically when we find
1427 a new partition. The rows in the buffer are then no longer needed.
1428 */
1430
1431 /**
1432 Reset execution state for next call to JOIN::exec, cf. JOIN::reset,
1433 or using [Buffering]WindowingIterator::Init.
1434 */
1436
1437 /**
1438 Reset execution state for LEAD/LAG for the current row in partition.
1439 */
1440 void reset_lead_lag();
1441
1442 private:
1444
1445 /// Common function for all types of resetting
1447
1448 public:
1449 /**
1450 Reset the execution state for all window functions defined on this window.
1451 */
1452 void reset_all_wf_state();
1453
1454 const char *printable_name() const;
1455
1456 void print(const THD *thd, String *str, enum_query_type qt,
1457 bool expand_definition) const;
1458
1459 bool has_windowing_steps() const;
1460
1461 /**
1462 Compute sorting costs for windowing.
1463
1464 @param cost Cost of sorting result set once
1465 @param windows The set of windows
1466
1467 @returns the aggregated sorting costs of the windowing
1468 */
1469 static double compute_cost(double cost, const List<Window> &windows);
1470
1471 private:
1472 /**
1473 Common implementation of before_frame() and after_frame().
1474 @param before True if 'before' is wanted; false if 'after' is.
1475 */
1476 bool before_or_after_frame(bool before);
1477 void print_frame(const THD *thd, String *str, enum_query_type qt) const;
1478 void print_border(const THD *thd, String *str, PT_border *b,
1479 enum_query_type qt) const;
1480
1481 /**
1482 Reorder windows and eliminate redundant ordering. If a window has the
1483 same ordering requirements as another, we will move them next to each other
1484 in the evaluation sequence, so we can sort only once, i.e. before the
1485 first window step. This allows us to fulfill the guarantee given by
1486 SQL standard when it comes to repeatability of non-deterministic (partially
1487 ordered) result sets for windowing inside a query, cf. #equal_sort.
1488 If more than two have the same ordering, the same applies, we only sort
1489 before the first (sort equivalent) window. The hypergraph optimizer uses
1490 the interesting order framework instead, eliding all sorts eliminated by
1491 this function and possibly more.
1492
1493 Note that we do not merge windows that have the same ordering requirements,
1494 so we may still get the extra materialization and multiple rounds of
1495 buffering. Yet, we should get _correctness_, as long as materialization
1496 preserves row ordering (which it does for all of our supported temporary
1497 table types).
1498
1499 If the result set is implicitly grouped, we also skip any sorting for
1500 windows.
1501
1502 @param windows list of windows
1503 */
1504 static void reorder_and_eliminate_sorts(List<Window> *windows);
1505
1506 /**
1507 Return true of the physical[1] sort orderings for the two windows are the
1508 same, cf. guarantee of
1509 SQL 2014 4.15.15 Windowed tables bullet two: The windowing functions are
1510 computed using the same row ordering if they specify the same ordering.
1511
1512 Collation and null handling is not supported, so moot.
1513
1514 The two other bullet points are also covered by this test.
1515
1516 [1] After concatenating effective PARTITION BY and ORDER BY (including
1517 inheritance) expressions.
1518 */
1519 static bool equal_sort(Window *w1, Window *w2);
1520
1521 /**
1522 Check that a frame border is constant during execution and that it does
1523 not contain subqueries (relevant for INTERVAL only): implementation
1524 limitation.
1525
1526 @param thd Session thread
1527 @param border The border to check
1528
1529 @return false if OK, true if error
1530 */
1531 bool check_constant_bound(THD *thd, PT_border *border);
1532
1533 /**
1534 Check that frame borders are sane; resolution phase.
1535
1536 @param thd Session thread
1537
1538 @returns true if error
1539 */
1540 bool check_border_sanity1(THD *thd);
1541 /**
1542 Like check_border_sanity1() but contains checks which must wait until
1543 the start of the execution phase.
1544
1545 @param thd Session thread
1546
1547 @returns true if error
1548 */
1549 bool check_border_sanity2(THD *thd);
1550};
1551
1552/**
1553 Collects evaluation requirements from a window function,
1554 used by Item_sum::check_wf_semantics and its overrides.
1555*/
1557 /**
1558 Set to true if window function requires row buffering
1559 */
1561 /**
1562 Set to true if we need peerset for evaluation (e.g. CUME_DIST)
1563 */
1565 /**
1566 Set to true if we need last peer for evaluation within a frame
1567 (e.g. JSON_OBJECTAGG)
1568 */
1570 /**
1571 Set to true if we need FIRST_VALUE or optimized MIN/MAX
1572 */
1574 /**
1575 Set to true if we need LAST_VALUE or optimized MIN/MAX
1576 */
1578 Window::st_offset opt_nth_row; ///< Used if we have NTH_VALUE
1579 Window::st_ll_offset opt_ll_row; ///< Used if we have LEAD or LAG
1580 /**
1581 Set to true if we can compute a sliding window by a combination of
1582 undoing the contribution of rows going out of the frame and adding the
1583 contribution of rows coming into the frame. For example, SUM and AVG
1584 allows this, but MAX/MIN do not. Only applicable if the frame has ROW
1585 bounds unit.
1586 */
1588 /**
1589 Similar to row_optimizable but for RANGE frame bounds unit
1590 */
1592
1594 : needs_buffer(false),
1595 needs_peerset(false),
1597 opt_first_row(false),
1598 opt_last_row(false),
1599 row_optimizable(true),
1600 range_optimizable(true) {}
1601};
1602
1603#endif /* WINDOWS_INCLUDED */
Kerberos Client Authentication nullptr
Definition: auth_kerberos_client_plugin.cc:251
Definition: item_cmpfunc.h:140
A wrapper class which provides array bounds checking.
Definition: sql_array.h:47
This is used for segregating rows in groups (e.g.
Definition: item.h:6541
Helper class for copy_funcs(); represents an Item to copy from table to next tmp table.
Definition: temp_table_param.h:48
Definition: item.h:5442
Class Item_sum is the base class used for special expressions that SQL calls 'set functions'.
Definition: item_sum.h:399
Base class that is used to represent any kind of expression in a relational query.
Definition: item.h:936
Definition: sql_list.h:467
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:61
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:426
Parse tree node for a single of a window extent's borders, cf.
Definition: parse_tree_nodes.h:1376
Parse tree node for a window's frame, cf.
Definition: parse_tree_nodes.h:1464
Definition: parse_tree_nodes.h:233
Parse tree node for a window; just a shallow wrapper for class Window, q.v.
Definition: parse_tree_window.h:39
This class represents a query block, aka a query specification, which is a query consisting of a SELE...
Definition: sql_lex.h:1163
SQL_I_List< Table_ref > m_table_list
List of tables in FROM clause - use Table_ref::next_local to traverse.
Definition: sql_lex.h:1929
Using this class is fraught with peril, and you need to be very careful when doing so.
Definition: sql_string.h:167
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_lexer_thd.h:36
Definition: table.h:2864
Object containing parameters used when creating and using temporary tables.
Definition: temp_table_param.h:95
Represents the (explicit) window of a SQL 2003 section 7.11 <window clause>, or the implicit (inlined...
Definition: window.h:110
static bool equal_sort(Window *w1, Window *w2)
Return true of the physical[1] sort orderings for the two windows are the same, cf.
Definition: window.cc:738
int64 rowno_in_partition() const
See m_rowno_in_partition.
Definition: window.h:1339
Item_string *const m_inherit_from
<existing window name>
Definition: window.h:129
bool m_is_last_row_in_frame
Execution state: the current row is the last row in a window frame For some aggregate functions,...
Definition: window.h:656
bool m_row_optimizable
The functions are optimizable with ROW unit.
Definition: window.h:167
bool check_border_sanity2(THD *thd)
Like check_border_sanity1() but contains checks which must wait until the start of the execution phas...
Definition: window.cc:877
const bool m_is_reference
If true, m_name is an unbound window reference, other fields are unused.
Definition: window.h:134
bool needs_last_peer_in_frame() const
If we cannot compute one of window functions without looking at all rows in the peerset of the curren...
Definition: window.h:1107
void reset_order_by_peer_set()
Reset the current row's ORDER BY expressions when starting a new peer set.
Definition: window.cc:508
int64 last_rowno_in_range_frame() const
See m_last_rowno_in_range_frame.
Definition: window.h:1237
bool before_or_after_frame(bool before)
Common implementation of before_frame() and after_frame().
Definition: window.cc:541
void reset_all_wf_state()
Reset the execution state for all window functions defined on this window.
Definition: window.cc:1509
bool in_new_order_by_peer_set(bool compare_all_order_by_items=true)
Determine if the current row is not in the same peer set as the previous row.
Definition: window.cc:529
bool opt_last_row() const
See m_opt_last_row.
Definition: window.h:1143
int64 m_rowno_in_partition
Execution state: The row number of the current row being readied for output within the partition.
Definition: window.h:514
void set_last_rowno_in_range_frame(uint64 rno)
See m_last_rowno_in_range_frame.
Definition: window.h:1244
void set_def_pos(uint pos)
Definition: window.h:780
void apply_temp_table(THD *thd, const Func_ptr_array &items_to_copy, bool first)
Specify that this window is to be evaluated after a given temporary table.
Definition: window.cc:1530
Window & set_rowno_in_frame(int64 rowno)
See m_rowno_in_frame.
Definition: window.h:1331
int64 m_first_rowno_in_range_frame
Execution state: the row number of the first row in a frame when evaluating RANGE based frame bounds.
Definition: window.h:607
void reset_partition_state()
Reset window state for a new partition.
Definition: window.h:1429
Item_string * m_name
<window name>
Definition: window.h:122
Frame_buffer_position m_tmp_pos
Sometimes we read one row too many, so that the saved position will be too far out because we subsequ...
Definition: window.h:319
bool static_aggregates() const
Return true if the aggregates are static, i.e.
Definition: window.h:1133
int64 first_rowno_in_range_frame() const
See m_first_rowno_in_range_frame.
Definition: window.h:1367
bool after_frame()
Definition: window.h:940
int64 m_row_has_fields_in_out_table
If >=1: the row with this number (1-based, relative to start of partition) currently has its fields i...
Definition: window.h:434
void copy_pos(Window_retrieve_cached_row_reason from_reason, Window_retrieve_cached_row_reason to_reason)
Copy frame buffer position hint from one to another.
Definition: window.h:352
int64 m_frame_buffer_partition_offset
Execution state: Snapshot of m_frame_buffer_total_rows when we start a new partition,...
Definition: window.h:424
bool resolve_window_ordering(THD *thd, Ref_item_array ref_item_array, Table_ref *tables, mem_root_deque< Item * > *fields, ORDER *o, bool partition_order)
Resolve and set up the PARTITION BY or an ORDER BY list of a window.
Definition: window.cc:674
void restore_special_row(uint64 special_rowno, uchar *record)
Restore row special_rowno into record from in-memory copy.
Definition: window_iterators.cc:504
void set_row_has_fields_in_out_table(int64 rowno)
See m_row_has_fields_in_out_table.
Definition: window.h:1407
bool m_needs_peerset
(At least) one window function needs the peer set of the current row to evaluate the wf for the curre...
Definition: window.h:146
ORDER * m_sorting_order
merged partition/order by
Definition: window.h:120
const st_nth & opt_nth_row() const
See m_opt_nth_row.
Definition: window.h:1158
void set_first_rowno_in_range_frame(int64 rowno)
See m_first_rowno_in_range_frame.
Definition: window.h:1360
const Window * m_ancestor
resolved from existing window name
Definition: window.h:242
uint m_def_pos
Position of definition in query's text, 1 for leftmost.
Definition: window.h:128
Temp_table_param * m_frame_buffer_param
Execution state: used iff m_needs_frame_buffering.
Definition: window.h:395
const st_lead_lag & opt_lead_lag() const
See m_opt_lead_lag.
Definition: window.h:1163
bool aggregates_primed() const
See m_aggregates_primed.
Definition: window.h:1298
int64 row_has_fields_in_out_table() const
See m_row_has_fields_in_out_table.
Definition: window.h:1400
int64 m_is_last_row_in_peerset_within_frame
Execution state: used iff m_needs_last_peer_in_frame.
Definition: window.h:467
bool make_special_rows_cache(THD *thd, TABLE *out_tbl)
Allocate the cache for special rows.
Definition: window.cc:1322
size_t m_special_rows_cache_length[FBC_FIRST_KEY - FBC_LAST_KEY+1]
Length of each copy in m_special_rows_cache, in bytes.
Definition: window.h:446
void set_short_circuit(bool short_circuit)
Definition: window.h:1186
const PT_frame * frame() const
Get the frame, if any.
Definition: window.h:785
int64 m_part_row_number
Execution state: the current row number in the current partition.
Definition: window.h:475
PT_order_list *const m_order_by
<window order clause>
Definition: window.h:119
bool check_border_sanity1(THD *thd)
Check that frame borders are sane; resolution phase.
Definition: window.cc:804
int64 rowno_in_frame() const
Return the size of the frame in number of rows.
Definition: window.h:1326
static bool resolve_reference(THD *thd, Item_sum *wf, PT_window **m_window)
Resolve any named window to its definition and update m_window to point to the definition instead.
Definition: window.cc:429
void set_frame_buffer_param(Temp_table_param *p)
Setter for m_frame_buffer_param, q.v.
Definition: window.h:1173
bool short_circuit() const
Definition: window.h:1185
void set_frame_buffer(TABLE *tab)
Setter for m_frame_buffer, q.v.
Definition: window.h:1183
int64 frame_buffer_total_rows() const
See m_frame_buffer_total_rows.
Definition: window.h:1381
const PT_order_list * effective_partition_by() const
Get partition, if any.
Definition: window.h:818
Window(Item_string *name)
Reference to a named window.
Definition: window.h:738
bool needs_buffering() const
If we cannot compute one of window functions without looking at succeeding rows, return true,...
Definition: window.h:1093
int64 m_frame_buffer_total_rows
Execution state: The frame buffer tmp file is not truncated for each new partition.
Definition: window.h:417
bool check_window_functions2(THD *thd)
Like check_window_functions1() but contains checks which must wait until the start of the execution p...
Definition: window.cc:1277
bool m_do_copy_null
Execution state: make frame wf produce a NULL (or 0 depending, e.g.
Definition: window.h:664
bool m_opt_first_row
Window equires re-evaluation of the first row in optimized moving frame mode e.g.
Definition: window.h:188
bool m_inverse_aggregation
Execution state: do inverse, e.g.
Definition: window.h:671
bool m_range_optimizable
The functions are optimizable with RANGE unit.
Definition: window.h:175
bool m_static_aggregates
The aggregates (SUM, etc) can be evaluated once for a partition, since it is static,...
Definition: window.h:182
bool setup_ordering_cached_items(THD *thd, Query_block *select, const PT_order_list *o, bool partition_order)
Set up cached items for an partition or an order by list updating m_partition_items or m_order_by_ite...
Definition: window.cc:645
bool check_window_functions1(THD *thd, Query_block *select)
Check that the semantic requirements for window functions over this window are fulfilled,...
Definition: window.cc:122
Window(PT_order_list *partition_by, PT_order_list *order_by, PT_frame *frame)
Unnamed window.
Definition: window.h:745
static void eliminate_unused_objects(List< Window > *windows)
Check window definitions to remove unused windows.
Definition: window.cc:1026
bool check_unique_name(const List< Window > &windows)
Return true if this window's name is not unique in windows.
Definition: window.cc:630
ORDER * first_order_by() const
Get the first argument of the ORDER BY clause for this window if any.
Definition: window.cc:118
bool is_last_row_in_frame() const
See m_is_last_row_in_frame.
Definition: window.h:1308
void set_is_last_row_in_peerset_within_frame(bool value)
See m_is_last_row_in_peerset_within_frame.
Definition: window.h:1268
bool opt_first_row() const
See m_opt_first_row.
Definition: window.h:1138
bool m_needs_partition_cardinality
(At least) one window function needs the cardinality of the partition of the current row to evaluate ...
Definition: window.h:159
void set_name(Item_string *name)
We have a named window.
Definition: window.h:766
uchar * m_special_rows_cache
Holds a fixed number of copies of special rows; each copy can use up to m_special_rows_cache_max_leng...
Definition: window.h:444
static constexpr int FRAME_BUFFER_POSITIONS_CARD
Cardinality of m_frame_buffer_positions if no NTH_VALUE, LEAD/LAG.
Definition: window.h:258
static double compute_cost(double cost, const List< Window > &windows)
Compute sorting costs for windowing.
Definition: window.cc:1523
void set_is_last(bool last)
An override used by the hypergraph join optimizer only.
Definition: window.h:1153
int64 m_rowno_being_visited
Execution state: The number of the row being visited for its contribution to a window function,...
Definition: window.h:498
int64 first_rowno_in_rows_frame() const
Definition: window.h:1353
bool at_partition_border() const
Check if we have read all the rows in a partition, possibly having buffered them for further processi...
Definition: window.h:948
bool m_needs_last_peer_in_frame
(At least) one window function (currently JSON_OBJECTAGG) needs the last peer for the current row to ...
Definition: window.h:153
bool m_last
The last window to be evaluated at execution time.
Definition: window.h:199
void set_first_rowno_in_rows_frame(int64 rowno)
See m_first_rowno_in_rows_frame.
Definition: window.h:1349
const PT_order_list * effective_order_by() const
Get the ORDER BY, if any.
Definition: window.h:792
int64 m_rowno_in_frame
Execution state: the row number of the row we are looking at for evaluating its contribution to some ...
Definition: window.h:507
bool m_aggregates_primed
Execution state: for optimizable aggregates, cf.
Definition: window.h:522
Window(PT_order_list *partition_by, PT_order_list *order_by, PT_frame *frame, Item_string *inherit)
Unnamed window based on a named window.
Definition: window.h:752
Mem_root_array< Cached_item * > m_order_by_items
items for the ORDER BY exprs.
Definition: window.h:247
void set_ancestor(Window *a)
After resolving an existing window name reference in a window definition, we set the ancestor pointer...
Definition: window.h:772
void set_last_row_output(int64 rno)
See m_last_row_output.
Definition: window.h:1212
void save_special_row(uint64 special_rowno, TABLE *t)
Save row special_rowno in table t->record[0] to an in-memory copy for later restoration.
Definition: window_iterators.cc:486
int64 is_last_row_in_peerset_within_frame() const
See m_is_last_row_in_peerset_within_frame.
Definition: window.h:1261
bool needs_sorting() const
Determine if the window had either a partition clause (inclusive) or a ORDER BY clause,...
Definition: window.h:1087
st_lead_lag m_opt_lead_lag
Definition: window.h:239
bool before_frame()
While processing buffered rows in RANGE frame mode we, determine if the present row revisited from th...
Definition: window.h:937
void save_pos(Window_retrieve_cached_row_reason reason)
See m_tmp_pos.
Definition: window.h:324
int64 last_row_output() const
See m_last_row_output.
Definition: window.h:1207
bool setup_range_expressions(THD *thd)
For RANGE frames we need to do computations involving add/subtract and less than, smaller than.
Definition: window.cc:241
bool m_short_circuit
Holds whether this window should be “short-circuit”, ie., goes directly to the query output instead o...
Definition: window.h:401
void set_last_rowno_in_peerset(uint64 rno)
See m_last_rowno_in_peerset.
Definition: window.h:1256
Item_string * name() const
Get the name of a window.
Definition: window.h:777
int64 partition_rowno() const
Getter for m_part_row_number, q.v., the current row number within the partition.
Definition: window.h:1194
Query_block * m_query_block
The SELECT the window is on.
Definition: window.h:117
void reset_execution_state(Reset_level level)
Common function for all types of resetting.
Definition: window.cc:1373
ORDER * first_partition_by() const
Get the first argument of the PARTITION clause for this window if any.
Definition: window.cc:114
bool do_inverse() const
See m_inverse_aggregation.
Definition: window.h:1285
int64 m_first_rowno_in_rows_frame
Execution state.
Definition: window.h:625
void destroy()
Free structures that were set up during preparation of window functions.
Definition: window.cc:1352
static bool setup_windows1(THD *thd, Query_block *select, Ref_item_array ref_item_array, Table_ref *tables, mem_root_deque< Item * > *fields, List< Window > *windows)
Semantic checking of windows.
Definition: window.cc:1092
void set_rowno_being_visited(int64 rno)
See m_rowno_being_visited.
Definition: window.h:1222
size_t m_special_rows_cache_max_length
Maximum allocated size in m_special_rows_cache.
Definition: window.h:448
TABLE * frame_buffer() const
Getter for m_frame_buffer, q.v.
Definition: window.h:1178
const char * printable_name() const
Definition: window.cc:1502
TABLE * m_frame_buffer
Execution state: used iff m_needs_frame_buffering.
Definition: window.h:407
bool do_copy_null() const
See m_do_copy_null.
Definition: window.h:1275
Window & set_inverse(bool b)
See m_inverse_aggregation.
Definition: window.h:1290
void cleanup()
Free up any resource used to process the window functions of this window, e.g.
Definition: window.cc:1337
bool is_reference() const
Return if this window represents an unresolved window reference seen in a window function OVER clause...
Definition: window.h:892
bool m_partition_border
Execution state: the current row starts a new partition.
Definition: window.h:481
List< Item_sum > & functions()
Get the list of functions invoked on this window.
Definition: window.h:847
int64 m_last_rowno_in_peerset
Execution state: used iff m_needs_peerset.
Definition: window.h:461
void set_last_rowno_in_cache(uint64 rno)
See m_last_rowno_in_cache.
Definition: window.h:1232
void reset_lead_lag()
Reset execution state for LEAD/LAG for the current row in partition.
Definition: window.cc:1364
Temp_table_param * frame_buffer_param() const
Getter for m_frame_buffer_param, q.v.
Definition: window.h:1168
void reset_round()
Reset execution state for next call to JOIN::exec, cf.
Definition: window.h:1435
void set_frame_buffer_partition_offset(int64 offset)
See m_frame_buffer_partition_offset.
Definition: window.h:1386
int64 last_rowno_in_peerset() const
See m_last_rowno_in_peerset.
Definition: window.h:1251
bool optimizable_row_aggregates() const
Return true if the set of window functions are all ROW unit optimizable.
Definition: window.h:1121
Mem_root_array_YY< Frame_buffer_position > m_frame_buffer_positions
Execution state: used iff m_needs_frame_buffering.
Definition: window.h:310
int m_ordering_idx
The logical ordering index (into LogicalOrderings) needed by this window's PARTITION BY and ORDER BY ...
Definition: window.h:583
bool check_constant_bound(THD *thd, PT_border *border)
Check that a frame border is constant during execution and that it does not contain subqueries (relev...
Definition: window.cc:774
bool m_needs_frame_buffering
(At least) one window function needs to buffer frame rows for evaluation i.e.
Definition: window.h:140
bool is_last() const
See m_last.
Definition: window.h:1148
int64 m_last_rowno_in_cache
Execution state: used iff m_needs_frame_buffering.
Definition: window.h:455
Special_keys
Keys for m_special_rows_cache, for special rows (see the comment on m_special_row_cache).
Definition: window.h:376
@ FBC_LAST_KEY
Definition: window.h:387
@ FBC_FIRST_KEY
Definition: window.h:386
@ FBC_FIRST_IN_NEXT_PARTITION
We read an incoming row.
Definition: window.h:383
void print_frame(const THD *thd, String *str, enum_query_type qt) const
Definition: window.cc:1455
bool needs_peerset() const
If we cannot compute one of window functions without looking at all rows in the peerset of the curren...
Definition: window.h:1100
Reset_level
Definition: window.h:1443
@ RL_ROUND
Definition: window.h:1443
@ RL_PARTITION
Definition: window.h:1443
bool m_mark
Used temporarily by the hypergraph join optimizer to mark which windows are referred to by a given or...
Definition: window.h:590
Mem_root_array< Cached_item * > m_partition_items
items for the PARTITION BY columns
Definition: window.h:245
int64 m_last_rowno_in_range_frame
Execution state: used for RANGE bounds frame evaluation for the continued evaluation for current row ...
Definition: window.h:619
int64 m_last_row_output
Execution state: The number, in the current partition, of the last output row, i.e.
Definition: window.h:488
void print_border(const THD *thd, String *str, PT_border *b, enum_query_type qt) const
Definition: window.cc:1424
Bounds_checked_array< Arg_comparator > m_comparators[2]
Definition: window.h:576
uint def_pos() const
Definition: window.h:779
Window(Item_string *name, PT_order_list *part, PT_order_list *ord, PT_frame *frame, bool is_reference, Item_string *inherit)
Generic window constructor, shared.
Definition: window.h:682
PT_frame *const m_frame
<window frame clause>
Definition: window.h:121
void print(const THD *thd, String *str, enum_query_type qt, bool expand_definition) const
Definition: window.cc:1468
int64 rowno_being_visited() const
See m_rowno_being_visited.
Definition: window.h:1217
bool optimizable_range_aggregates() const
Return true if the set of window functions are all RANGE unit optimizable.
Definition: window.h:1127
void check_partition_boundary()
Check if the just read input row marks the start of a new partition.
Definition: window.cc:457
void set_rowno_in_partition(int64 rowno)
See m_rowno_in_partition.
Definition: window.h:1344
void restore_pos(Window_retrieve_cached_row_reason reason)
See m_tmp_pos.
Definition: window.h:335
bool has_windowing_steps() const
Definition: window.cc:1518
void set_frame_buffer_total_rows(int64 rows)
See m_frame_buffer_total_rows.
Definition: window.h:1374
int64 frame_buffer_partition_offset() const
See m_frame_buffer_partition_offset.
Definition: window.h:1393
void set_is_last_row_in_frame(bool b)
See m_is_last_row_in_frame.
Definition: window.h:1315
void set_aggregates_primed(bool b)
See m_aggregates_primed.
Definition: window.h:1303
st_nth m_opt_nth_row
Window requires re-evaluation of the Nth row in optimized moving frame mode e.g.
Definition: window.h:238
int64 last_rowno_in_cache() const
See m_last_rowno_in_cache.
Definition: window.h:1227
bool needs_partition_cardinality() const
If we need to read the entire partition before we can evaluate some window function(s) on this window...
Definition: window.h:1113
ORDER * sorting_order(THD *thd=nullptr, bool implicit_grouping=false)
Concatenation of columns in PARTITION BY and ORDER BY.
Definition: window.cc:394
List< Item_sum > m_functions
window functions based on 'this'
Definition: window.h:243
void set_do_copy_null(bool b)
See m_do_copy_null.
Definition: window.h:1280
PT_order_list *const m_partition_by
<window partition clause>
Definition: window.h:118
static void reorder_and_eliminate_sorts(List< Window > *windows)
Reorder windows and eliminate redundant ordering.
Definition: window.cc:754
bool m_opt_last_row
Window requires re-evaluation of the last row in optimized moving frame mode e.g.
Definition: window.h:194
static bool setup_windows2(THD *thd, List< Window > *windows)
Like setup_windows1() but contains operations which must wait until the start of the execution phase.
Definition: window.cc:1310
A (partial) implementation of std::deque allocating its blocks on a MEM_ROOT.
Definition: mem_root_deque.h:111
const char * p
Definition: ctype-mb.cc:1235
enum_query_type
Query type constants (usable as bitmap flags).
Definition: enum_query_type.h:31
Some integer typedefs for easier portability.
#define INT_MIN64
Definition: my_inttypes.h:75
unsigned char uchar
Definition: my_inttypes.h:52
int64_t int64
Definition: my_inttypes.h:68
uint64_t uint64
Definition: my_inttypes.h:69
thread_local MEM_ROOT ** THR_MALLOC
Definition: mysqld.cc:1557
static int record
Definition: mysqltest.cc:195
std::string str(const mysqlrouter::ConfigGenerator::Options::Endpoint &ep)
Definition: config_generator.cc:1081
Definition: os0file.h:89
Definition: table.h:286
Definition: table.h:1406
Holds information about a position in the buffer frame as stored in a temporary file (cf.
Definition: window.h:267
int64 m_rowno
Definition: window.h:271
uchar * m_position
< The size of the file position is determined by handler::ref_length
Definition: window.h:269
Frame_buffer_position(uchar *position, int64 rowno)
Definition: window.h:272
Definition: window.h:228
Mem_root_array_YY< st_ll_offset > m_offsets
sorted set of LEAD/LAG offsets
Definition: window.h:230
Definition: window.h:213
st_ll_offset()
Definition: window.h:215
int64 m_rowno
negative values is LEAD
Definition: window.h:214
bool operator<(const st_ll_offset &a) const
Used for sorting offsets in ascending order for faster traversal of frame buffer tmp file.
Definition: window.h:220
Definition: window.h:223
Mem_root_array_YY< st_offset > m_offsets
sorted set of NTH_VALUE offsets
Definition: window.h:225
Definition: window.h:202
bool operator<(const st_offset &a) const
Used for sorting offsets in ascending order for faster traversal of frame buffer tmp file.
Definition: window.h:210
st_offset()
Definition: window.h:205
bool m_from_last
Definition: window.h:204
int64 m_rowno
Definition: window.h:203
Collects evaluation requirements from a window function, used by Item_sum::check_wf_semantics and its...
Definition: window.h:1556
bool needs_buffer
Set to true if window function requires row buffering.
Definition: window.h:1560
bool needs_last_peer_in_frame
Set to true if we need last peer for evaluation within a frame (e.g.
Definition: window.h:1569
bool opt_first_row
Set to true if we need FIRST_VALUE or optimized MIN/MAX.
Definition: window.h:1573
bool range_optimizable
Similar to row_optimizable but for RANGE frame bounds unit.
Definition: window.h:1591
Window_evaluation_requirements()
Definition: window.h:1593
Window::st_offset opt_nth_row
Used if we have NTH_VALUE.
Definition: window.h:1578
bool opt_last_row
Set to true if we need LAST_VALUE or optimized MIN/MAX.
Definition: window.h:1577
bool row_optimizable
Set to true if we can compute a sliding window by a combination of undoing the contribution of rows g...
Definition: window.h:1587
bool needs_peerset
Set to true if we need peerset for evaluation (e.g.
Definition: window.h:1564
Window::st_ll_offset opt_ll_row
Used if we have LEAD or LAG.
Definition: window.h:1579
constexpr int kMaxWindows
The number of windows is limited to avoid the stack blowing up when constructing iterators recursivel...
Definition: window.h:88
Window_retrieve_cached_row_reason
Position hints for the frame buffer are saved for these kind of row accesses, cf.
Definition: window.h:70
Mem_root_array< Func_ptr > Func_ptr_array
Definition: window.h:63