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