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