MySQL  8.0.27
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, 2021, Oracle and/or its affiliates.
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"
32 #include "my_table_map.h"
34 #include "sql/row_iterator.h"
35 #include "sql/sql_sort.h"
36 
37 class Filesort;
38 class QEP_TAB;
39 class THD;
40 
41 /**
42  An adapter that takes in another RowIterator and produces the same rows,
43  just in sorted order. (The actual sort happens in Init().) Unfortunately, it
44  is still bound to working off a TABLE object, which means that you can't
45  use it to e.g. sort the output of a join without materializing into a
46  temporary table first (ignoring that we currently have no Iterators for
47  joins).
48 
49  The primary reason for this is that we currently have no way of communicating
50  read sets through Iterators, and SortingIterator needs to add fields used in
51  ORDER BY to the read set for the appropriate tables. This could be mitigated
52  by e.g. sending in an unordered_set<Field *>, but we don't currently have
53  such a mechanism.
54  */
55 class SortingIterator final : public RowIterator {
56  public:
57  // Does not take ownership of "filesort", which must live for at least
58  // as long as SortingIterator lives (since Init() may be called multiple
59  // times). It _does_ take ownership of "source", and is responsible for
60  // calling Init() on it, but does not hold the memory.
61  // "examined_rows", if not nullptr, is incremented for each successful Read().
62  //
63  // num_rows_estimate is used only for whether we intend to use the priority
64  // queue optimization or not; if we estimate fewer rows than we can fit into
65  // RAM, we never use the priority queue.
68  ha_rows num_rows_estimate, table_map tables_to_get_rowid_for,
69  ha_rows *examined_rows);
70  ~SortingIterator() override;
71 
72  // Calls Init() on the source iterator, then does the actual sort.
73  // NOTE: If you call Init() again, SortingIterator will actually
74  // do a _new sort_, not just rewind the iterator. This is because a
75  // TABLE_REF we depend on may have changed so the produced record set could be
76  // different from what we had last time.
77  //
78  // Currently, this isn't a big problem performance-wise, since we never
79  // really sort the right-hand side of a join (we only sort the leftmost
80  // table or the final result, and we don't have merge joins). However,
81  // re-inits could very well happen in the case of a dependent subquery
82  // that needs ORDER BY with LIMIT, so for correctness, we really need
83  // the re-sort. Longer-term we should test whether the TABLE_REF is
84  // unchanged, and if so, just re-init the result iterator.
85  bool Init() override;
86 
87  int Read() override { return m_result_iterator->Read(); }
88 
89  void SetNullRowFlag(bool is_null_row) override;
90 
91  void UnlockRow() override { m_result_iterator->UnlockRow(); }
92 
93  /// Optional (when JOIN::destroy() runs, the iterator and its buffers
94  /// will be cleaned up anyway); used to clean up the buffers a little
95  /// bit earlier.
96  ///
97  /// When we get cached JOIN objects (prepare/optimize once) that can
98  /// live for a long time between queries, calling this will become more
99  /// important.
100  void CleanupAfterQuery();
101 
102  const Filesort *filesort() const { return m_filesort; }
103 
104  private:
105  int DoSort();
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 
130 
131  // Holds one out of all RowIterator implementations we need so that it is
132  // possible to initialize a RowIterator without heap allocations.
133  // (m_result_iterator typically points to this union, and is responsible for
134  // running the right destructor.)
135  //
136  // TODO: If we need to add TimingIterator directly on this iterator,
137  // switch to allocating it on the MEM_ROOT.
139  IteratorHolder() {} // NOLINT(modernize-use-equals-default)
140  ~IteratorHolder() {} // NOLINT(modernize-use-equals-default)
141 
149 };
150 
151 #endif // SQL_SORTING_ITERATOR_H_
Row iterators that scan a single table without reference to other tables or iterators.
A class wrapping misc buffers used for sorting.
Definition: sql_sort.h:177
Sorting related info.
Definition: filesort.h:51
Definition: sql_executor.h:256
A context for reading through a single table using a chosen access method: index read,...
Definition: row_iterator.h:60
THD * thd() const
Definition: row_iterator.h:190
Fetch the record IDs from a memory buffer, but the records themselves from the table on disk.
Definition: basic_row_iterators.h:205
Fetch the record IDs from a temporary file, then the records themselves from the table on disk.
Definition: basic_row_iterators.h:280
Definition: sql_sort.h:144
An adapter that takes in another RowIterator and produces the same rows, just in sorted order.
Definition: sorting_iterator.h:55
int Read() override
Read a single row.
Definition: sorting_iterator.h:87
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.cc:503
unique_ptr_destroy_only< RowIterator > m_source_iterator
Definition: sorting_iterator.h:113
const table_map m_tables_to_get_rowid_for
Definition: sorting_iterator.h:128
const ha_rows m_num_rows_estimate
Definition: sorting_iterator.h:127
int DoSort()
Definition: sorting_iterator.cc:524
unique_ptr_destroy_only< RowIterator > m_result_iterator
Definition: sorting_iterator.h:120
union SortingIterator::IteratorHolder m_result_iterator_holder
Filesort_info m_fs_info
Definition: sorting_iterator.h:123
const Filesort * filesort() const
Definition: sorting_iterator.h:102
Filesort * m_filesort
Definition: sorting_iterator.h:108
void ReleaseBuffers()
Definition: sorting_iterator.cc:424
bool Init() override
Initialize or reinitialize the iterator.
Definition: sorting_iterator.cc:438
ha_rows * m_examined_rows
Definition: sorting_iterator.h:129
void CleanupAfterQuery()
Optional (when JOIN::destroy() runs, the iterator and its buffers will be cleaned up anyway); used to...
Definition: sorting_iterator.cc:417
~SortingIterator() override
Definition: sorting_iterator.cc:412
void UnlockRow() override
Definition: sorting_iterator.h:91
SortingIterator(THD *thd, Filesort *filesort, unique_ptr_destroy_only< RowIterator > source, ha_rows num_rows_estimate, table_map tables_to_get_rowid_for, ha_rows *examined_rows)
Definition: sorting_iterator.cc:400
Sort_result m_sort_result
Definition: sorting_iterator.h:125
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_class.h:821
This file follows Google coding style, except for the name MEM_ROOT (which is kept for historical rea...
std::unique_ptr< T, Destroy_only< T > > unique_ptr_destroy_only
std::unique_ptr, but only destroying.
Definition: my_alloc.h:464
This file includes constants used by all storage engines.
my_off_t ha_rows
Definition: my_base.h:1138
uint64_t table_map
Definition: my_table_map.h:29
repeated Source source
Definition: replication_asynchronous_connection_failover.proto:41
Definition: sorting_iterator.h:138
IteratorHolder()
Definition: sorting_iterator.h:139
SortFileIterator< false > sort_file
Definition: sorting_iterator.h:146
SortFileIndirectIterator sort_file_indirect
Definition: sorting_iterator.h:147
SortBufferIterator< false > sort_buffer
Definition: sorting_iterator.h:143
SortFileIterator< true > sort_file_packed_addons
Definition: sorting_iterator.h:145
SortBufferIterator< true > sort_buffer_packed_addons
Definition: sorting_iterator.h:142
SortBufferIndirectIterator sort_buffer_indirect
Definition: sorting_iterator.h:144
~IteratorHolder()
Definition: sorting_iterator.h:140