MySQL 9.0.0
Source Code Documentation
filesort_utils.h
Go to the documentation of this file.
1/* Copyright (c) 2010, 2024, Oracle and/or its affiliates.
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License, version 2.0,
5 as published by the Free Software Foundation.
6
7 This program is designed to work with certain software (including
8 but not limited to OpenSSL) that is licensed under separate terms,
9 as designated in a particular file or component or in included license
10 documentation. The authors of MySQL hereby grant you an additional
11 permission to link the program and your derivative works with the
12 separately licensed software that they have either included with
13 the program or referenced in the documentation.
14
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License, version 2.0, for more details.
19
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
23
24#ifndef FILESORT_UTILS_INCLUDED
25#define FILESORT_UTILS_INCLUDED
26
27#include <assert.h>
28#include <stddef.h>
29#include <sys/types.h>
30#include <memory>
31#include <utility>
32#include <vector>
33
34#include "map_helpers.h"
35#include "my_base.h" // ha_rows
36
37#include "my_inttypes.h"
38#include "mysql/service_mysql_alloc.h" // my_free
39#include "sql/sql_array.h" // Bounds_checked_array
40
42class Sort_param;
43
44/**
45 Buffer used for storing records to be sorted. The records are stored in
46 a series of buffers that are allocated incrementally, growing 50% each
47 time, similar to how a MEM_ROOT works. This allows the user to set a large
48 maximum buffer size without getting huge allocations for sorting small result
49 sets. It means that if you actually _do_ use the entire buffer, there will be
50 more allocations than one large allocation up-front, but this is a worthwhile
51 tradeoff (those allocation will tend to disappear into the cost of actually
52 getting all the rows and sorting them).
53
54 In addition, Filesort_buffer stores a vector of pointers to the beginning of
55 each record. It is these pointers that are actually sorted in filesort.
56 If the records are small, this can add up to overhead on top of the amount of
57 memory the user expected to use. We _do_ take already allocated pointers into
58 account when calculating how big a new block can be, so the amount of badness
59 is bounded:
60
61 Assume that we have set maximum record size to infinity, but that in
62 practice, they are are about the smallest size possible (4-byte sort key plus
63 4-byte rowid) and that we are on a 64-bit system. Then, the worst possible
64 overhead is that we use as much space on pointers as the size of the last
65 (largest) block. We can look at the two possible extremes:
66
67 - Smallest possible sort buffer (32 kB): 32 kB overhead.
68 - A huge sort buffer (x kB): If the last block is y kB, the total size will
69 be y + 2/3y + (2/3)²y + ... = 3y, which means the last block is 1/3 of the
70 total size. Thus, pointer overhead will be no worse than 33%.
71
72 In most practical cases, it will be much better than this. In particular,
73 even when allocating a block (where we don't yet know how many records will
74 fit), we allow space for the record pointers we'd need given maximum-sized
75 rows.
76
77 The buffer must be kept available for multiple executions of the
78 same sort operation, so one can call reset() for reuse. Again similar
79 to MEM_ROOT, this keeps the last (largest) block and discards the others.
80*/
82 public:
89
90 /** Sort me...
91 @return Number of records, after any deduplication
92 */
93 size_t sort_buffer(Sort_param *param, size_t num_input_rows,
94 size_t max_output_rows);
95
96 /**
97 Prepares the buffer for the next batch of records to process.
98 */
99 void reset();
100
101 /**
102 Where should the next record be stored?
103
104 If a block is returned, it is always at least "min_size" bytes long.
105 If the returned block is not large enough for your purposes,
106 call get_next_record_pointer() again with a larger value of min_size than
107 the size you got back. Just increasing the size by one byte is fine;
108 the class will still try to make exponentially larger blocks each time.
109
110 If there's no room for a record of the given size, returns nullptr.
111
112 After you've written data to the given record, call commit_used_memory()
113 with the number of bytes you've actually written. This ensures it will
114 not get reused for subsequent records.
115 */
117 assert(min_size != 0xFFFFFFFFu);
118 // See if we need to allocate a new block.
119 if (m_next_rec_ptr == nullptr ||
120 m_next_rec_ptr + min_size > m_current_block_end) {
121 if (allocate_block(min_size)) return Bounds_checked_array<uchar>();
122 }
123
124 // Allocate space within the current block.
127 }
128
129 void commit_used_memory(size_t num_bytes) {
131 m_next_rec_ptr += num_bytes;
132 }
133
134 /**
135 Removes any existing rows and allocates `num_records` maximum-sized rows
136 (call get_sorted_record() to get their pointers). This is somewhat more
137 efficient than calling reset() and then get_next_record_pointer()
138 repeatedly, as it guarantees that at most one allocation is needed.
139
140 @returns true on memory allocation error, including if the allocated
141 size would exceed max_size_in_bytes().
142 */
143 bool preallocate_records(size_t num_records);
144
145 size_t max_size_in_bytes() const { return m_max_size_in_bytes; }
146
147 /**
148 How much memory has been allocated (counting both the sort buffer and the
149 record pointers) at most since last call to clear_peak_memory_used().
150 Note in particular that reset() and free_sort_buffer() does _not_ zero this
151 counter.
152 */
153 size_t peak_memory_used() const {
155 return m_peak_memory_used;
156 }
157
158 /// See peak_memory_used.
160
161 /**
162 Set the memory limit for the sort buffer before starting to add records.
163 If trying to allocate space for a new row (in get_next_record_pointer)
164 would take us past the set limit, allocation will fail. Note that we can go
165 a bit over this limit due to having to store record pointers; see the class
166 comment.
167
168 @param max_size Maximum size of the sort buffer, in bytes.
169 @param record_length Worst-case size of each record, in bytes.
170 */
171 void set_max_size(size_t max_size, size_t record_length) {
172 m_max_size_in_bytes = max_size;
173 m_max_record_length = record_length;
174 }
175
176 /**
177 Frees all memory. Unlike reset(), which keeps one block for future use,
178 this actually releases all blocks. It is intended to release memory
179 in an error situation, for final shutdown, or if even the largest block
180 will not be large enough for future allocations.
181
182 You do not need to call this if you are destroying the object anyway.
183 */
184 void free_sort_buffer();
185
186 /**
187 Get the list of record pointers as a contiguous array. Will be invalidated
188 by calling get_next_record_pointer() or otherwise changing the number of
189 records.
190 */
192 if (m_record_pointers.empty()) return nullptr;
193 return m_record_pointers.data();
194 }
195
196 /**
197 Gets sorted record number ix. @see get_sort_keys()
198 Only valid after buffer has been sorted!
199 */
201 assert(ix < m_record_pointers.size());
202 return m_record_pointers[ix];
203 }
204
205 /**
206 Clears all rows, then returns a contiguous buffer of maximum size.
207 (This may or may not involve allocation.) This is for reusing the memory
208 for merge buffers, which requires the memory to be a single contiguous
209 chunk; one could in theory adjust merging to allow using multiple buffers
210 like sorting does, but once we need to merge, that means we've hit disk
211 anyway (or at the very least, need to talk to the OS' buffer cache),
212 and the cost of a single allocation is small compared to I/O.
213
214 If you use this memory area, you cannot also use the Filesort_buffer to
215 store sort records (get_next_record_pointer etc.); that would use the
216 same memory.
217
218 Can return nullptr, if allocation fails.
219 */
221
222 private:
223 /**
224 Allocate a new block with space for at least `num_bytes` bytes.
225
226 @returns true if the allocation failed (including if m_max_size_in_bytes
227 was exceeded).
228 */
229 bool allocate_block(size_t num_bytes);
230
231 /**
232 Allocate a new block of exactly `block_size` bytes, and sets it
233 as the current block. Does not check m_max_size_in_bytes.
234
235 @returns true if the allocation failed
236 */
237 bool allocate_sized_block(size_t num_bytes);
238
239 /// See m_peak_memory_used.
240 void update_peak_memory_used() const;
241
242 uchar *m_next_rec_ptr; ///< The next record will be inserted here.
243 uchar *m_current_block_end; ///< The limit of the current block, exclusive.
244
245 /// The memory blocks used for the actual data.
246 std::vector<unique_ptr_my_free<uchar[]>> m_blocks;
247
248 /// Pointer to the beginning of each record.
249 std::vector<uchar *> m_record_pointers;
250
251 size_t m_max_record_length; ///< Worst-case length of each record.
252
253 /// Maximum number of bytes we are allowed to allocate in all.
255
256 /**
257 The size of the current memory block (m_blocks.back()), in bytes
258 (or 0 if no block). If nothing has been allocated from the block yet,
259 the invariant m_next_rec_ptr + m_current_block_size == m_current_block_end
260 holds.
261 */
263
264 /**
265 The total size of all blocks except the current one, not including
266 record pointers. Used for bookkeeping how far away we are from
267 reaching m_max_size_in_bytes.
268 */
270
271 /**
272 The largest amount of total memory we've been using since last call to
273 clear_peak_memory_used(). This is updated lazily so that we don't need
274 to do the calculations for every record (and thus is mutable). The only
275 point where it _must_ be explicitly updated (by calling
276 update_peak_memory_used()), except when being asked for the value,
277 is right before we deallocate memory, as otherwise, there could be a peak
278 we had forgotten.
279 */
280 mutable size_t m_peak_memory_used{0};
281
282 // Privately movable, but not copyable.
285};
286
287#endif // FILESORT_UTILS_INCLUDED
Kerberos Client Authentication nullptr
Definition: auth_kerberos_client_plugin.cc:251
A wrapper class which provides array bounds checking.
Definition: sql_array.h:47
API for getting cost estimates for operations on table data.
Definition: opt_costmodel.h:242
Buffer used for storing records to be sorted.
Definition: filesort_utils.h:81
size_t m_max_record_length
Worst-case length of each record.
Definition: filesort_utils.h:251
size_t m_current_block_size
The size of the current memory block (m_blocks.back()), in bytes (or 0 if no block).
Definition: filesort_utils.h:262
uchar ** get_sort_keys()
Get the list of record pointers as a contiguous array.
Definition: filesort_utils.h:191
std::vector< uchar * > m_record_pointers
Pointer to the beginning of each record.
Definition: filesort_utils.h:249
void update_peak_memory_used() const
See m_peak_memory_used.
Definition: filesort_utils.cc:449
std::vector< unique_ptr_my_free< uchar[]> > m_blocks
The memory blocks used for the actual data.
Definition: filesort_utils.h:246
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 m_max_size_in_bytes
Maximum number of bytes we are allowed to allocate in all.
Definition: filesort_utils.h:254
size_t m_peak_memory_used
The largest amount of total memory we've been using since last call to clear_peak_memory_used().
Definition: filesort_utils.h:280
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
Filesort_buffer & operator=(Filesort_buffer &&rhs)=default
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
uchar * m_current_block_end
The limit of the current block, exclusive.
Definition: filesort_utils.h:243
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
Filesort_buffer & operator=(const Filesort_buffer &rhs)=delete
bool allocate_block(size_t num_bytes)
Allocate a new block with space for at least num_bytes bytes.
Definition: filesort_utils.cc:316
size_t max_size_in_bytes() const
Definition: filesort_utils.h:145
bool allocate_sized_block(size_t num_bytes)
Allocate a new block of exactly block_size bytes, and sets it as the current block.
Definition: filesort_utils.cc:399
size_t m_space_used_other_blocks
The total size of all blocks except the current one, not including record pointers.
Definition: filesort_utils.h:269
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 * m_next_rec_ptr
The next record will be inserted here.
Definition: filesort_utils.h:242
uchar * get_sorted_record(size_t ix)
Gets sorted record number ix.
Definition: filesort_utils.h:200
Filesort_buffer()
Definition: filesort_utils.h:83
There are several record formats for sorting:
Definition: sort_param.h:302
This file includes constants used by all storage engines.
Some integer typedefs for easier portability.
unsigned char uchar
Definition: my_inttypes.h:52