MySQL  8.0.20
Source Code Documentation
sorting_iterator.h
Go to the documentation of this file.
1 #ifndef SQL_SORTING_ITERATOR_H_
2 #define SQL_SORTING_ITERATOR_H_
3 
4 /* Copyright (c) 2018, 2019, Oracle and/or its affiliates. All rights reserved.
5 
6  This program is free software; you can redistribute it and/or modify
7  it under the terms of the GNU General Public License, version 2.0,
8  as published by the Free Software Foundation.
9 
10  This program is also distributed with certain software (including
11  but not limited to OpenSSL) that is licensed under separate terms,
12  as designated in a particular file or component or in included license
13  documentation. The authors of MySQL hereby grant you an additional
14  permission to link the program and your derivative works with the
15  separately licensed software that they have included with MySQL.
16 
17  This program is distributed in the hope that it will be useful,
18  but WITHOUT ANY WARRANTY; without even the implied warranty of
19  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20  GNU General Public License, version 2.0, for more details.
21 
22  You should have received a copy of the GNU General Public License
23  along with this program; if not, write to the Free Software
24  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
25 
26 #include <memory>
27 #include <string>
28 #include <vector>
29 
30 #include "my_alloc.h"
31 #include "my_base.h"
33 #include "sql/row_iterator.h"
34 #include "sql/sql_sort.h"
35 
36 class Filesort;
37 class QEP_TAB;
38 class THD;
39 
40 /**
41  An adapter that takes in another RowIterator and produces the same rows,
42  just in sorted order. (The actual sort happens in Init().) Unfortunately, it
43  is still bound to working off a TABLE object, which means that you can't
44  use it to e.g. sort the output of a join without materializing into a
45  temporary table first (ignoring that we currently have no Iterators for
46  joins).
47 
48  The primary reason for this is that we currently have no way of communicating
49  read sets through Iterators, and SortingIterator needs to add fields used in
50  ORDER BY to the read set for the appropriate tables. This could be mitigated
51  by e.g. sending in an unordered_set<Field *>, but we don't currently have
52  such a mechanism.
53  */
55  public:
56  // Does not take ownership of "filesort", which must live for at least
57  // as long as SortingIterator lives (since Init() may be called multiple
58  // times). It _does_ take ownership of "source", and is responsible for
59  // calling Init() on it, but does not hold the memory.
60  // "examined_rows", if not nullptr, is incremented for each successful Read().
61  //
62  // qep_tab is used for two things: To fill in any old-style information schema
63  // tables before scanning, if needed, and to count the number of read rows
64  // (for SQL_CALC_FOUND_ROWS). If you need neither of these, you can pass
65  // nullptr.
68  ha_rows *examined_rows);
69  ~SortingIterator() override;
70 
71  // Calls Init() on the source iterator, then does the actual sort.
72  // NOTE: If you call Init() again, SortingIterator will actually
73  // do a _new sort_, not just rewind the iterator. This is because a
74  // TABLE_REF we depend on may have changed so the produced record set could be
75  // different from what we had last time.
76  //
77  // Currently, this isn't a big problem performance-wise, since we never
78  // really sort the right-hand side of a join (we only sort the leftmost
79  // table or the final result, and we don't have merge joins). However,
80  // re-inits could very well happen in the case of a dependent subquery
81  // that needs ORDER BY with LIMIT, so for correctness, we really need
82  // the re-sort. Longer-term we should test whether the TABLE_REF is
83  // unchanged, and if so, just re-init the result iterator.
84  bool Init() override;
85 
86  int Read() override { return m_result_iterator->Read(); }
87 
88  void SetNullRowFlag(bool is_null_row) override {
89  if (m_result_iterator == nullptr) {
90  // If we don't have a result yet, it will come up with the flag unset.
91  DBUG_ASSERT(is_null_row == false);
92  return;
93  }
94  m_result_iterator->SetNullRowFlag(is_null_row);
95  }
96 
97  void UnlockRow() override { m_result_iterator->UnlockRow(); }
98 
99  std::vector<Child> children() const override {
100  return std::vector<Child>{{m_source_iterator.get(), ""}};
101  }
102 
103  std::vector<std::string> DebugString() const override;
104 
105  /// Optional (when JOIN::destroy() runs, the iterator and its buffers
106  /// will be cleaned up anyway); used to clean up the buffers a little
107  /// bit earlier.
108  ///
109  /// When we get cached JOIN objects (prepare/optimize once) that can
110  /// live for a long time between queries, calling this will become more
111  /// important.
112  void CleanupAfterQuery();
113 
114  private:
115  int DoSort();
116  void ReleaseBuffers();
117 
120 
121  // The iterator we are reading records from. We don't read from it
122  // after Init() is done, but we may read from the TABLE it wraps,
123  // so we don't destroy it until our own destructor.
125 
126  // The actual iterator of sorted records, populated in Init();
127  // Read() only proxies to this. Always points to one of the members
128  // in m_result_iterator_holder; the type can be different depending on
129  // e.g. whether the sort result fit into memory or not, whether we are
130  // using packed addons, etc..
132 
133  // Holds the buffers for m_sort_result.
135 
137 
139 
140  // Holds one out of all RowIterator implementations we need so that it is
141  // possible to initialize a RowIterator without heap allocations.
142  // (m_result_iterator typically points to this union, and is responsible for
143  // running the right destructor.)
144  //
145  // TODO: If we need to add TimingIterator directly on this iterator,
146  // switch to allocating it on the MEM_ROOT.
150 
158 };
159 
160 #endif // SQL_SORTING_ITERATOR_H_
int DoSort()
Definition: sorting_iterator.cc:587
Fetch the record IDs from a memory buffer, but the records themselves from the table on disk...
Definition: basic_row_iterators.h:205
SortBufferIterator< false > sort_buffer
Definition: sorting_iterator.h:152
SortBufferIndirectIterator sort_buffer_indirect
Definition: sorting_iterator.h:153
QEP_TAB * m_qep_tab
Definition: sorting_iterator.h:119
~IteratorHolder()
Definition: sorting_iterator.h:149
A context for reading through a single table using a chosen access method: index read, scan, etc, use of cache, etc.
Definition: row_iterator.h:61
Row iterators that scan a single table without reference to other tables or iterators.
SortFileIterator< true > sort_file_packed_addons
Definition: sorting_iterator.h:154
SortingIterator(THD *thd, QEP_TAB *qep_tab, Filesort *filesort, unique_ptr_destroy_only< RowIterator > source, ha_rows *examined_rows)
Definition: sorting_iterator.cc:473
ha_rows * m_examined_rows
Definition: sorting_iterator.h:138
void SetNullRowFlag(bool is_null_row) override
Mark the current row buffer as containing a NULL row or not, so that if you read from it and the flag...
Definition: sorting_iterator.h:88
Fetch the record IDs from a temporary file, then the records themselves from the table on disk...
Definition: basic_row_iterators.h:270
void CleanupAfterQuery()
Optional (when JOIN::destroy() runs, the iterator and its buffers will be cleaned up anyway); used to...
Definition: sorting_iterator.cc:487
IteratorHolder()
Definition: sorting_iterator.h:148
This file includes constants used by all storage engines.
#define DBUG_ASSERT(A)
Definition: my_dbug.h:199
std::vector< std::string > DebugString() const override
Returns a short string (used for EXPLAIN FORMAT=tree) with user-readable information for this iterato...
Definition: sorting_iterator.cc:633
union SortingIterator::IteratorHolder m_result_iterator_holder
bool Init() override
Initialize or reinitialize the iterator.
Definition: sorting_iterator.cc:508
SortFileIterator< false > sort_file
Definition: sorting_iterator.h:155
Filesort_info m_fs_info
Definition: sorting_iterator.h:134
Definition: sorting_iterator.h:147
SortBufferIterator< true > sort_buffer_packed_addons
Definition: sorting_iterator.h:151
#define final(a, b, c)
Definition: hash.c:109
~SortingIterator() override
Definition: sorting_iterator.cc:482
std::vector< Child > children() const override
List of zero or more iterators which are direct children of this one.
Definition: sorting_iterator.h:99
THD * thd() const
Definition: row_iterator.h:254
unique_ptr_destroy_only< RowIterator > m_source_iterator
Definition: sorting_iterator.h:124
unique_ptr_destroy_only< RowIterator > m_result_iterator
Definition: sorting_iterator.h:131
void ReleaseBuffers()
Definition: sorting_iterator.cc:494
Definition: sql_executor.h:270
std::unique_ptr< T, Destroy_only< T > > unique_ptr_destroy_only
std::unique_ptr, but only destroying.
Definition: my_alloc.h:408
Definition: sql_sort.h:141
void UnlockRow() override
Definition: sorting_iterator.h:97
A class wrapping misc buffers used for sorting.
Definition: sql_sort.h:174
Sorting related info.
Definition: filesort.h:49
An adapter that takes in another RowIterator and produces the same rows, just in sorted order...
Definition: sorting_iterator.h:54
int Read() override
Read a single row.
Definition: sorting_iterator.h:86
Filesort * m_filesort
Definition: sorting_iterator.h:118
Sort_result m_sort_result
Definition: sorting_iterator.h:136
my_off_t ha_rows
Definition: my_base.h:1132
bool filesort(THD *thd, Filesort *filesort, RowIterator *source_iterator, Filesort_info *fs_info, Sort_result *sort_result, ha_rows *found_rows)
Sort a table.
Definition: filesort.cc:359
SortFileIndirectIterator sort_file_indirect
Definition: sorting_iterator.h:156
This file follows Google coding style, except for the name MEM_ROOT (which is kept for historical rea...
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_class.h:765