MySQL  8.0.19
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().
63  ha_rows *examined_rows);
64  ~SortingIterator() override;
65 
66  // Calls Init() on the source iterator, then does the actual sort.
67  // NOTE: If you call Init() again, SortingIterator will actually
68  // do a _new sort_, not just rewind the iterator. This is because a
69  // TABLE_REF we depend on may have changed so the produced record set could be
70  // different from what we had last time.
71  //
72  // Currently, this isn't a big problem performance-wise, since we never
73  // really sort the right-hand side of a join (we only sort the leftmost
74  // table or the final result, and we don't have merge joins). However,
75  // re-inits could very well happen in the case of a dependent subquery
76  // that needs ORDER BY with LIMIT, so for correctness, we really need
77  // the re-sort. Longer-term we should test whether the TABLE_REF is
78  // unchanged, and if so, just re-init the result iterator.
79  bool Init() override;
80 
81  int Read() override { return m_result_iterator->Read(); }
82 
83  void SetNullRowFlag(bool is_null_row) override {
84  m_result_iterator->SetNullRowFlag(is_null_row);
85  }
86 
87  void UnlockRow() override { m_result_iterator->UnlockRow(); }
88 
89  std::vector<Child> children() const override {
90  return std::vector<Child>{{m_source_iterator.get(), ""}};
91  }
92 
93  std::vector<std::string> DebugString() const override;
94 
95  /// Optional (when JOIN::destroy() runs, the iterator and its buffers
96  /// will be cleaned up anyway); used to clean up the buffers a little
97  /// bit earlier.
98  ///
99  /// When we get cached JOIN objects (prepare/optimize once) that can
100  /// live for a long time between queries, calling this will become more
101  /// important.
102  void CleanupAfterQuery();
103 
104  private:
105  int DoSort(QEP_TAB *qep_tab);
106  void ReleaseBuffers();
107 
109 
110  // The iterator we are reading records from. We don't read from it
111  // after Init() is done, but we may read from the TABLE it wraps,
112  // so we don't destroy it until our own destructor.
114 
115  // The actual iterator of sorted records, populated in Init();
116  // Read() only proxies to this. Always points to one of the members
117  // in m_result_iterator_holder; the type can be different depending on
118  // e.g. whether the sort result fit into memory or not, whether we are
119  // using packed addons, etc..
121 
122  // Holds the buffers for m_sort_result.
124 
126 
128 
129  // Holds one out of all RowIterator implementations we need so that it is
130  // possible to initialize a RowIterator without heap allocations.
131  // (m_result_iterator typically points to this union, and is responsible for
132  // running the right destructor.)
133  //
134  // TODO: If we need to add TimingIterator directly on this iterator,
135  // switch to allocating it on the MEM_ROOT.
139 
147 };
148 
149 #endif // SQL_SORTING_ITERATOR_H_
SortingIterator::IteratorHolder::sort_file
SortFileIterator< false > sort_file
Definition: sorting_iterator.h:144
SortingIterator::IteratorHolder::sort_file_packed_addons
SortFileIterator< true > sort_file_packed_addons
Definition: sorting_iterator.h:143
THD
Definition: sql_class.h:764
SortingIterator::IteratorHolder
Definition: sorting_iterator.h:136
SortingIterator::UnlockRow
void UnlockRow() override
Definition: sorting_iterator.h:87
basic_row_iterators.h
SortingIterator::~SortingIterator
~SortingIterator() override
Definition: sorting_iterator.cc:465
my_base.h
sql_sort.h
SortingIterator::children
std::vector< Child > children() const override
List of zero or more iterators which are direct children of this one.
Definition: sorting_iterator.h:89
SortBufferIndirectIterator
Fetch the record IDs from a memory buffer, but the records themselves from the table on disk.
Definition: basic_row_iterators.h:207
SortingIterator::m_source_iterator
unique_ptr_destroy_only< RowIterator > m_source_iterator
Definition: sorting_iterator.h:113
SortingIterator::SortingIterator
SortingIterator(THD *thd, Filesort *filesort, unique_ptr_destroy_only< RowIterator > source, ha_rows *examined_rows)
Definition: sorting_iterator.cc:457
row_iterator.h
SortingIterator::m_result_iterator
unique_ptr_destroy_only< RowIterator > m_result_iterator
Definition: sorting_iterator.h:120
SortingIterator::DebugString
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:666
QEP_TAB
Definition: sql_executor.h:417
SortFileIndirectIterator
Fetch the record IDs from a temporary file, then the records themselves from the table on disk.
Definition: basic_row_iterators.h:272
SortingIterator::Init
bool Init() override
Initialize or reinitialize the iterator.
Definition: sorting_iterator.cc:491
unique_ptr_destroy_only
std::unique_ptr< T, Destroy_only< T > > unique_ptr_destroy_only
std::unique_ptr, but only destroying.
Definition: my_alloc.h:408
Filesort
Sorting related info.
Definition: filesort.h:49
SortBufferIterator< true >
my_alloc.h
SortingIterator::m_result_iterator_holder
union SortingIterator::IteratorHolder m_result_iterator_holder
SortingIterator::m_examined_rows
ha_rows * m_examined_rows
Definition: sorting_iterator.h:127
SortingIterator::m_sort_result
Sort_result m_sort_result
Definition: sorting_iterator.h:125
filesort
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:376
RowIterator
A context for reading through a single table using a chosen access method: index read,...
Definition: row_iterator.h:61
SortingIterator::ReleaseBuffers
void ReleaseBuffers()
Definition: sorting_iterator.cc:477
SortingIterator::m_filesort
Filesort * m_filesort
Definition: sorting_iterator.h:108
SortingIterator::DoSort
int DoSort(QEP_TAB *qep_tab)
Definition: sorting_iterator.cc:597
SortingIterator::SetNullRowFlag
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:83
SortingIterator::CleanupAfterQuery
void CleanupAfterQuery()
Optional (when JOIN::destroy() runs, the iterator and its buffers will be cleaned up anyway); used to...
Definition: sorting_iterator.cc:470
SortingIterator::IteratorHolder::sort_buffer_indirect
SortBufferIndirectIterator sort_buffer_indirect
Definition: sorting_iterator.h:142
SortingIterator
An adapter that takes in another RowIterator and produces the same rows, just in sorted order.
Definition: sorting_iterator.h:54
Sort_result
Definition: sql_sort.h:141
RowIterator::thd
THD * thd() const
Definition: row_iterator.h:254
SortingIterator::IteratorHolder::IteratorHolder
IteratorHolder()
Definition: sorting_iterator.h:137
SortingIterator::IteratorHolder::sort_buffer
SortBufferIterator< false > sort_buffer
Definition: sorting_iterator.h:141
SortingIterator::m_fs_info
Filesort_info m_fs_info
Definition: sorting_iterator.h:123
SortingIterator::IteratorHolder::~IteratorHolder
~IteratorHolder()
Definition: sorting_iterator.h:138
SortingIterator::IteratorHolder::sort_file_indirect
SortFileIndirectIterator sort_file_indirect
Definition: sorting_iterator.h:145
SortingIterator::IteratorHolder::sort_buffer_packed_addons
SortBufferIterator< true > sort_buffer_packed_addons
Definition: sorting_iterator.h:140
SortFileIterator< true >
Filesort_info
A class wrapping misc buffers used for sorting.
Definition: sql_sort.h:174
ha_rows
my_off_t ha_rows
Definition: my_base.h:1132
final
#define final(a, b, c)
Definition: hash.c:109
SortingIterator::Read
int Read() override
Read a single row.
Definition: sorting_iterator.h:81