MySQL 9.2.0
Source Code Documentation
sorting_iterator.h
Go to the documentation of this file.
1#ifndef SQL_ITERATORS_SORTING_ITERATOR_H_
2#define SQL_ITERATORS_SORTING_ITERATOR_H_
3
4/* Copyright (c) 2018, 2024, 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 designed to work 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 either included with
16 the program or referenced in the documentation.
17
18 This program is distributed in the hope that it will be useful,
19 but WITHOUT ANY WARRANTY; without even the implied warranty of
20 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 GNU General Public License, version 2.0, for more details.
22
23 You should have received a copy of the GNU General Public License
24 along with this program; if not, write to the Free Software
25 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
26
27#include <memory>
28#include <span>
29#include <string>
30#include <vector>
31
32#include "my_alloc.h"
33#include "my_base.h"
34#include "my_table_map.h"
37#include "sql/sql_sort.h"
38
39class Filesort;
40class QEP_TAB;
41class THD;
42struct AccessPath;
43
44/**
45 An adapter that takes in another RowIterator and produces the same rows,
46 just in sorted order. (The actual sort happens in Init().) Unfortunately, it
47 is still bound to working off a TABLE object, which means that you can't
48 use it to e.g. sort the output of a join without materializing into a
49 temporary table first (ignoring that we currently have no Iterators for
50 joins).
51
52 The primary reason for this is that we currently have no way of communicating
53 read sets through Iterators, and SortingIterator needs to add fields used in
54 ORDER BY to the read set for the appropriate tables. This could be mitigated
55 by e.g. sending in an unordered_set<Field *>, but we don't currently have
56 such a mechanism.
57 */
58class SortingIterator final : public RowIterator {
59 public:
60 // Does not take ownership of "filesort", which must live for at least
61 // as long as SortingIterator lives (since Init() may be called multiple
62 // times). It _does_ take ownership of "source", and is responsible for
63 // calling Init() on it, but does not hold the memory.
64 // "examined_rows", if not nullptr, is incremented for each successful Read().
65 //
66 // num_rows_estimate is used only for whether we intend to use the priority
67 // queue optimization or not; if we estimate fewer rows than we can fit into
68 // RAM, we never use the priority queue.
71 std::span<AccessPath *> single_row_index_lookups,
72 ha_rows num_rows_estimate, table_map tables_to_get_rowid_for,
73 ha_rows *examined_rows);
74 ~SortingIterator() override;
75
76 // Calls Init() on the source iterator, then does the actual sort.
77 // NOTE: If you call Init() again, SortingIterator will actually
78 // do a _new sort_, not just rewind the iterator. This is because a
79 // Index_lookup we depend on may have changed so the produced record
80 // set could be different from what we had last time.
81 //
82 // Currently, this isn't a big problem performance-wise, since we never
83 // really sort the right-hand side of a join (we only sort the leftmost
84 // table or the final result, and we don't have merge joins). However,
85 // re-inits could very well happen in the case of a dependent subquery
86 // that needs ORDER BY with LIMIT, so for correctness, we really need
87 // the re-sort. Longer-term we should test whether the Index_lookup is
88 // unchanged, and if so, just re-init the result iterator.
89 bool Init() override;
90
91 int Read() override { return m_result_iterator->Read(); }
92
93 void SetNullRowFlag(bool is_null_row) override;
94
95 void UnlockRow() override { m_result_iterator->UnlockRow(); }
96
97 /// Optional (when JOIN::destroy() runs, the iterator and its buffers
98 /// will be cleaned up anyway); used to clean up the buffers a little
99 /// bit earlier.
100 ///
101 /// When we get cached JOIN objects (prepare/optimize once) that can
102 /// live for a long time between queries, calling this will become more
103 /// important.
104 void CleanupAfterQuery();
105
106 const Filesort *filesort() const { return m_filesort; }
107
108 private:
109 int DoSort();
110 void ReleaseBuffers();
111
113
114 // The iterator we are reading records from. We don't read from it
115 // after Init() is done, but we may read from the TABLE it wraps,
116 // so we don't destroy it until our own destructor.
118
119 // The actual iterator of sorted records, populated in Init();
120 // Read() only proxies to this. Always points to one of the members
121 // in m_result_iterator_holder; the type can be different depending on
122 // e.g. whether the sort result fit into memory or not, whether we are
123 // using packed addons, etc..
125
126 // Holds the buffers for m_sort_result.
128
130
131 // All the single-row index lookups that provide rows to this iterator.
132 std::span<AccessPath *> m_single_row_index_lookups;
133
137
138 // Holds one out of all RowIterator implementations we need so that it is
139 // possible to initialize a RowIterator without heap allocations.
140 // (m_result_iterator typically points to this union, and is responsible for
141 // running the right destructor.)
142 //
143 // TODO: If we need to add TimingIterator directly on this iterator,
144 // switch to allocating it on the MEM_ROOT.
146 IteratorHolder() {} // NOLINT(modernize-use-equals-default)
147 ~IteratorHolder() {} // NOLINT(modernize-use-equals-default)
148
156};
157
158#endif // SQL_ITERATORS_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:189
Sorting related info.
Definition: filesort.h:52
Definition: sql_executor.h:256
A context for reading through a single table using a chosen access method: index read,...
Definition: row_iterator.h:82
THD * thd() const
Definition: row_iterator.h:228
Fetch the record IDs from a memory buffer, but the records themselves from the table on disk.
Definition: basic_row_iterators.h:218
Fetch the records from a memory buffer.
Definition: basic_row_iterators.h:182
Fetch the record IDs from a temporary file, then the records themselves from the table on disk.
Definition: basic_row_iterators.h:293
Fetch the records from a tempoary file.
Definition: basic_row_iterators.h:259
Definition: sql_sort.h:156
An adapter that takes in another RowIterator and produces the same rows, just in sorted order.
Definition: sorting_iterator.h:58
int Read() override
Read a single row.
Definition: sorting_iterator.h:91
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:512
unique_ptr_destroy_only< RowIterator > m_source_iterator
Definition: sorting_iterator.h:117
const table_map m_tables_to_get_rowid_for
Definition: sorting_iterator.h:135
const ha_rows m_num_rows_estimate
Definition: sorting_iterator.h:134
int DoSort()
Definition: sorting_iterator.cc:533
unique_ptr_destroy_only< RowIterator > m_result_iterator
Definition: sorting_iterator.h:124
union SortingIterator::IteratorHolder m_result_iterator_holder
Filesort_info m_fs_info
Definition: sorting_iterator.h:127
Filesort * m_filesort
Definition: sorting_iterator.h:112
void ReleaseBuffers()
Definition: sorting_iterator.cc:425
std::span< AccessPath * > m_single_row_index_lookups
Definition: sorting_iterator.h:132
bool Init() override
Initialize or reinitialize the iterator.
Definition: sorting_iterator.cc:439
ha_rows * m_examined_rows
Definition: sorting_iterator.h:136
void CleanupAfterQuery()
Optional (when JOIN::destroy() runs, the iterator and its buffers will be cleaned up anyway); used to...
Definition: sorting_iterator.cc:418
~SortingIterator() override
Definition: sorting_iterator.cc:413
SortingIterator(THD *thd, Filesort *filesort, unique_ptr_destroy_only< RowIterator > source, std::span< AccessPath * > single_row_index_lookups, ha_rows num_rows_estimate, table_map tables_to_get_rowid_for, ha_rows *examined_rows)
Definition: sorting_iterator.cc:401
const Filesort * filesort() const
Definition: sorting_iterator.h:106
void UnlockRow() override
Definition: sorting_iterator.h:95
Sort_result m_sort_result
Definition: sorting_iterator.h:129
For each client connection we create a separate thread with THD serving as a thread/connection descri...
Definition: sql_lexer_thd.h:36
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:480
This file includes constants used by all storage engines.
my_off_t ha_rows
Definition: my_base.h:1141
uint64_t table_map
Definition: my_table_map.h:30
repeated Source source
Definition: replication_asynchronous_connection_failover.proto:42
Access paths are a query planning structure that correspond 1:1 to iterators, in that an access path ...
Definition: access_path.h:238
Definition: sorting_iterator.h:145
IteratorHolder()
Definition: sorting_iterator.h:146
SortFileIterator< false > sort_file
Definition: sorting_iterator.h:153
SortFileIndirectIterator sort_file_indirect
Definition: sorting_iterator.h:154
SortBufferIterator< false > sort_buffer
Definition: sorting_iterator.h:150
SortFileIterator< true > sort_file_packed_addons
Definition: sorting_iterator.h:152
SortBufferIterator< true > sort_buffer_packed_addons
Definition: sorting_iterator.h:149
SortBufferIndirectIterator sort_buffer_indirect
Definition: sorting_iterator.h:151
~IteratorHolder()
Definition: sorting_iterator.h:147