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