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