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