MySQL 9.1.0
Source Code Documentation
sql_sort.h
Go to the documentation of this file.
1#ifndef SQL_SORT_INCLUDED
2#define SQL_SORT_INCLUDED
3
4/* Copyright (c) 2000, 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 <assert.h>
28#include "map_helpers.h"
29#include "my_base.h" // ha_rows
30
31#include "my_sys.h"
32#include "sql/filesort_utils.h" // Filesort_buffer
33#include "sql/mem_root_array.h"
34
35class Addon_fields;
36struct TABLE;
37
38/* Defines used by filesort and uniques */
39
40constexpr size_t MERGEBUFF = 7;
41constexpr size_t MERGEBUFF2 = 15;
42// Number of bytes used to store varlen key's length
43constexpr size_t VARLEN_PREFIX = 4;
44
45/**
46 Descriptor for a merge chunk to be sort-merged.
47 A merge chunk is a sequence of pre-sorted records, written to a
48 temporary file. A Merge_chunk instance describes where this chunk is stored
49 in the file, and where it is located when it is in memory.
50
51 It is a POD because we read/write them from/to files (but note,
52 only m_file_position and m_rowcount are actually used in that
53 situation).
54
55 We have accessors (getters/setters) for all struct members.
56 */
58 public:
62
64 const uchar *buffer_end() const { return m_buffer_end; }
65 const uchar *valid_buffer_end() const { return m_valid_buffer_end; }
66
70 }
73 assert(m_buffer_end == nullptr || end <= m_buffer_end);
75 }
77 assert(end <= m_buffer_end);
79 }
80
82 uchar *current_key() const { return m_current_key; }
83 void advance_current_key(uint val) { m_current_key += val; }
84
86 void set_rowcount(ha_rows val) { m_rowcount = val; }
87 ha_rows rowcount() const { return m_rowcount; }
88
89 ha_rows mem_count() const { return m_mem_count; }
90 void set_mem_count(ha_rows val) { m_mem_count = val; }
92
93 ha_rows max_keys() const { return m_max_keys; }
94 void set_max_keys(ha_rows val) { m_max_keys = val; }
95
96 size_t buffer_size() const { return m_buffer_end - m_buffer_start; }
97
98 /**
99 Tries to merge *this with *mc, returns true if successful.
100 The assumption is that *this is no longer in use,
101 and the space it has been allocated can be handed over to a
102 buffer which is adjacent to it.
103 */
105 if (mc->m_buffer_end == m_buffer_start) {
106 mc->m_buffer_end = m_buffer_end;
107 mc->m_max_keys += m_max_keys;
108 return true;
109 } else if (mc->m_buffer_start == m_buffer_end) {
110 mc->m_buffer_start = m_buffer_start;
111 mc->m_max_keys += m_max_keys;
112 return true;
113 }
114 return false;
115 }
116
117 private:
118 /// The current key for this chunk.
120
121 /// Current position in the file to be sorted.
123
124 /// Start of main-memory buffer for this chunk.
126
127 /// End of main-memory buffer for this chunk.
128 uchar *m_buffer_end = nullptr;
129
130 /// End of actual, valid data for this chunk.
132
133 /// Number of unread rows in this chunk.
135
136 /// Number of rows in the main-memory buffer.
138
139 /// If we have fixed-size rows: max number of rows in buffer.
141};
142
144
145/*
146 The result of Unique or filesort; can either be stored on disk
147 (in which case io_cache points to the file) or in memory in one
148 of two ways. See sorted_result_in_fsbuf.
149
150 Note if sort_result points into memory, it does _not_ own the sort buffer;
151 Filesort_info does.
152
153 TODO: Clean up so that Filesort / Filesort_info / Filesort_buffer /
154 Sort_result have less confusing overlap.
155*/
157 public:
159
160 bool has_result_in_memory() const {
162 }
163
164 bool has_result() const {
166 }
167
169
170 /**
171 If the entire result fits in memory, we skip the merge phase.
172 We may leave the result in the parent Filesort_info's filesort_buffer
173 (indicated by sorted_result_in_fsbuf), or we may strip away
174 the sort keys, and copy the sorted result into a new buffer.
175 Unique always uses the latter.
176 This new buffer is [sorted_result ... sorted_result_end]
177 @see save_index()
178 */
182
183 ha_rows found_records{0}; ///< How many records in sort.
184};
185
186/**
187 A class wrapping misc buffers used for sorting.
188 */
190 /// Buffer for sorting keys.
192
193 public:
194 Merge_chunk_array merge_chunks; ///< Array of chunk descriptors
195
196 Addon_fields *addon_fields{nullptr}; ///< Addon field descriptors.
197
200
201 Filesort_info(const Filesort_info &) = delete;
203
205
206 /** Sort filesort_buffer
207 @return Number of records, after any deduplication
208 */
209 size_t sort_buffer(Sort_param *param, size_t num_input_rows,
210 size_t max_output_rows) {
211 return filesort_buffer.sort_buffer(param, num_input_rows, max_output_rows);
212 }
213
214 /**
215 Copies (unpacks) values appended to sorted fields from a buffer back to
216 their regular positions specified by the Field::ptr pointers.
217 @param tables Tables in the join; for NULL row flags.
218 @param buff Buffer which to unpack the value from.
219 */
220 template <bool Packed_addon_fields>
221 inline void unpack_addon_fields(const Mem_root_array<TABLE *> &tables,
222 uchar *buff);
223
224 /**
225 Reads 'count' number of chunk descriptors into the merge_chunks array.
226 In case of error, the merge_chunks array will be empty.
227 @param chunk_file File containing the descriptors.
228 @param count Number of chunks to read.
229 */
230 void read_chunk_descriptors(IO_CACHE *chunk_file, uint count);
231
232 /// Are we using "addon fields"?
233 bool using_addon_fields() const { return addon_fields != nullptr; }
234
236
238
241 }
242
243 void commit_used_memory(size_t num_bytes) {
245 }
246
249 }
250
252
255 }
256
257 void set_max_size(size_t max_size, size_t record_length) {
258 filesort_buffer.set_max_size(max_size, record_length);
259 }
260
262
263 bool preallocate_records(size_t num_records) {
264 return filesort_buffer.preallocate_records(num_records);
265 }
266
268
269 size_t max_size_in_bytes() const {
271 }
272
273 uint sort_length() const { return m_sort_length; }
274 bool using_varlen_keys() const { return m_using_varlen_keys; }
275
276 void set_sort_length(uint val, bool is_varlen) {
277 m_sort_length = val;
278 m_using_varlen_keys = is_varlen;
279 }
280};
281
283
284/**
285 Put all room used by freed buffer to use in adjacent buffer.
286
287 Note, that we can't simply distribute memory evenly between all buffers,
288 because new areas must not overlap with old ones.
289*/
290template <typename Heap_type>
291void reuse_freed_buff(Merge_chunk *old_top, Heap_type *heap) {
292 typename Heap_type::iterator it = heap->begin();
293 typename Heap_type::iterator end = heap->end();
294 for (; it != end; ++it) {
295 if (old_top->merge_freed_buff(*it)) return;
296 }
297 assert(0);
298}
299
300#endif /* SQL_SORT_INCLUDED */
Kerberos Client Authentication nullptr
Definition: auth_kerberos_client_plugin.cc:251
This class wraps information about usage of addon fields.
Definition: sort_param.h:129
Buffer used for storing records to be sorted.
Definition: filesort_utils.h:81
uchar ** get_sort_keys()
Get the list of record pointers as a contiguous array.
Definition: filesort_utils.h:191
void reset()
Prepares the buffer for the next batch of records to process.
Definition: filesort_utils.cc:249
bool preallocate_records(size_t num_records)
Removes any existing rows and allocates num_records maximum-sized rows (call get_sorted_record() to g...
Definition: filesort_utils.cc:277
Bounds_checked_array< uchar > get_next_record_pointer(size_t min_size)
Where should the next record be stored?
Definition: filesort_utils.h:116
size_t peak_memory_used() const
How much memory has been allocated (counting both the sort buffer and the record pointers) at most si...
Definition: filesort_utils.h:153
void clear_peak_memory_used()
See peak_memory_used.
Definition: filesort_utils.h:159
size_t sort_buffer(Sort_param *param, size_t num_input_rows, size_t max_output_rows)
Sort me...
Definition: filesort_utils.cc:131
void free_sort_buffer()
Frees all memory.
Definition: filesort_utils.cc:415
void commit_used_memory(size_t num_bytes)
Definition: filesort_utils.h:129
Bounds_checked_array< uchar > get_contiguous_buffer()
Clears all rows, then returns a contiguous buffer of maximum size.
Definition: filesort_utils.cc:437
size_t max_size_in_bytes() const
Definition: filesort_utils.h:145
void set_max_size(size_t max_size, size_t record_length)
Set the memory limit for the sort buffer before starting to add records.
Definition: filesort_utils.h:171
uchar * get_sorted_record(size_t ix)
Gets sorted record number ix.
Definition: filesort_utils.h:200
A class wrapping misc buffers used for sorting.
Definition: sql_sort.h:189
void free_sort_buffer()
Definition: sql_sort.h:261
Addon_fields * addon_fields
Addon field descriptors.
Definition: sql_sort.h:196
bool preallocate_records(size_t num_records)
Definition: sql_sort.h:263
void clear_peak_memory_used()
Definition: sql_sort.h:237
Filesort_info & operator=(const Filesort_info &)=delete
uchar ** get_sort_keys()
Definition: sql_sort.h:251
void commit_used_memory(size_t num_bytes)
Definition: sql_sort.h:243
void unpack_addon_fields(const Mem_root_array< TABLE * > &tables, uchar *buff)
Copies (unpacks) values appended to sorted fields from a buffer back to their regular positions speci...
Definition: sorting_iterator.cc:541
Filesort_info()
Definition: sql_sort.h:204
bool using_addon_fields() const
Are we using "addon fields"?
Definition: sql_sort.h:233
void read_chunk_descriptors(IO_CACHE *chunk_file, uint count)
Reads 'count' number of chunk descriptors into the merge_chunks array.
Definition: filesort.cc:709
bool m_using_varlen_keys
Definition: sql_sort.h:198
void set_sort_length(uint val, bool is_varlen)
Definition: sql_sort.h:276
bool using_varlen_keys() const
Definition: sql_sort.h:274
Merge_chunk_array merge_chunks
Array of chunk descriptors.
Definition: sql_sort.h:194
Filesort_buffer filesort_buffer
Buffer for sorting keys.
Definition: sql_sort.h:191
uint m_sort_length
Definition: sql_sort.h:199
size_t sort_buffer(Sort_param *param, size_t num_input_rows, size_t max_output_rows)
Sort filesort_buffer.
Definition: sql_sort.h:209
size_t max_size_in_bytes() const
Definition: sql_sort.h:269
uchar * get_sorted_record(uint idx)
Definition: sql_sort.h:247
Bounds_checked_array< uchar > get_contiguous_buffer()
Definition: sql_sort.h:253
void reset()
Definition: sql_sort.h:235
void set_max_size(size_t max_size, size_t record_length)
Definition: sql_sort.h:257
uint sort_length() const
Definition: sql_sort.h:273
size_t peak_memory_used() const
Definition: sql_sort.h:267
Bounds_checked_array< uchar > get_next_record_pointer(size_t min_size)
Definition: sql_sort.h:239
Filesort_info(const Filesort_info &)=delete
A typesafe replacement for DYNAMIC_ARRAY.
Definition: mem_root_array.h:426
There are several record formats for sorting:
Definition: sort_param.h:302
Definition: sql_sort.h:156
IO_CACHE * io_cache
Definition: sql_sort.h:168
bool has_result() const
Definition: sql_sort.h:164
unique_ptr_my_free< uchar > sorted_result
Definition: sql_sort.h:180
Sort_result()
Definition: sql_sort.h:158
uchar * sorted_result_end
Definition: sql_sort.h:181
bool has_result_in_memory() const
Definition: sql_sort.h:160
bool sorted_result_in_fsbuf
If the entire result fits in memory, we skip the merge phase.
Definition: sql_sort.h:179
ha_rows found_records
How many records in sort.
Definition: sql_sort.h:183
bool my_b_inited(const IO_CACHE *info)
Definition: my_sys.h:483
static void start(mysql_harness::PluginFuncEnv *env)
Definition: http_auth_backend_plugin.cc:180
std::unique_ptr< T, My_free_deleter > unique_ptr_my_free
std::unique_ptr, but with my_free as deleter.
Definition: map_helpers.h:97
This file includes constants used by all storage engines.
my_off_t ha_rows
Definition: my_base.h:1141
ulonglong my_off_t
Definition: my_inttypes.h:72
unsigned char uchar
Definition: my_inttypes.h:52
Common header for many mysys elements.
static int count
Definition: myisam_ftdump.cc:45
Cursor end()
A past-the-end Cursor.
Definition: rules_table_service.cc:192
constexpr size_t MERGEBUFF2
Definition: sql_sort.h:41
Bounds_checked_array< Merge_chunk > Merge_chunk_array
Definition: sql_sort.h:143
constexpr size_t MERGEBUFF
Definition: sql_sort.h:40
constexpr size_t VARLEN_PREFIX
Definition: sql_sort.h:43
void reuse_freed_buff(Merge_chunk *old_top, Heap_type *heap)
Put all room used by freed buffer to use in adjacent buffer.
Definition: sql_sort.h:291
Bounds_checked_array< uchar > Sort_buffer
Definition: sql_sort.h:282
Definition: my_sys.h:334
Descriptor for a merge chunk to be sort-merged.
Definition: sql_sort.h:57
const uchar * buffer_end() const
Definition: sql_sort.h:64
uchar * m_buffer_start
Start of main-memory buffer for this chunk.
Definition: sql_sort.h:125
void init_current_key()
Definition: sql_sort.h:81
bool merge_freed_buff(Merge_chunk *mc) const
Tries to merge *this with *mc, returns true if successful.
Definition: sql_sort.h:104
ha_rows m_rowcount
Number of unread rows in this chunk.
Definition: sql_sort.h:134
void set_mem_count(ha_rows val)
Definition: sql_sort.h:90
void set_buffer_start(uchar *start)
Definition: sql_sort.h:71
void advance_current_key(uint val)
Definition: sql_sort.h:83
ha_rows mem_count() const
Definition: sql_sort.h:89
void set_file_position(my_off_t val)
Definition: sql_sort.h:60
void set_max_keys(ha_rows val)
Definition: sql_sort.h:94
void advance_file_position(my_off_t val)
Definition: sql_sort.h:61
my_off_t m_file_position
Current position in the file to be sorted.
Definition: sql_sort.h:122
uchar * m_valid_buffer_end
End of actual, valid data for this chunk.
Definition: sql_sort.h:131
ha_rows rowcount() const
Definition: sql_sort.h:87
void decrement_rowcount(ha_rows val)
Definition: sql_sort.h:85
void set_valid_buffer_end(uchar *end)
Definition: sql_sort.h:76
void set_buffer(uchar *start, uchar *end)
Definition: sql_sort.h:67
my_off_t file_position() const
Definition: sql_sort.h:59
ha_rows decrement_mem_count()
Definition: sql_sort.h:91
void set_rowcount(ha_rows val)
Definition: sql_sort.h:86
void set_buffer_end(uchar *end)
Definition: sql_sort.h:72
size_t buffer_size() const
Definition: sql_sort.h:96
ha_rows max_keys() const
Definition: sql_sort.h:93
ha_rows m_max_keys
If we have fixed-size rows: max number of rows in buffer.
Definition: sql_sort.h:140
const uchar * valid_buffer_end() const
Definition: sql_sort.h:65
uchar * m_current_key
The current key for this chunk.
Definition: sql_sort.h:119
uchar * current_key() const
Definition: sql_sort.h:82
ha_rows m_mem_count
Number of rows in the main-memory buffer.
Definition: sql_sort.h:137
uchar * m_buffer_end
End of main-memory buffer for this chunk.
Definition: sql_sort.h:128
uchar * buffer_start()
Definition: sql_sort.h:63
Definition: table.h:1421
plugin_messages_callback mc
Definition: webauthn_client_plugin.cc:55