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