MySQL  8.0.27
Source Code Documentation
filesort_utils.h
Go to the documentation of this file.
1 /* Copyright (c) 2010, 2021, 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 
40 class Cost_model_table;
41 class 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  */
199  uchar *get_sorted_record(size_t ix) {
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:229
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
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
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
Filesort_buffer & operator=(const Filesort_buffer &rhs)=delete
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
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
Filesort_buffer & operator=(Filesort_buffer &&rhs)=default
Bounds_checked_array< uchar > get_contiguous_buffer()
Clears all rows, then returns a contiguous buffer of maximum size.
Definition: filesort_utils.cc:436
bool allocate_block(size_t num_bytes)
Allocate a new block with space for at least num_bytes bytes.
Definition: filesort_utils.cc:315
uchar ** get_sort_keys()
Get the list of record pointers as a contiguous array.
Definition: filesort_utils.h:190
uchar * get_sorted_record(size_t ix)
Gets sorted record number ix.
Definition: filesort_utils.h:199
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
Bounds_checked_array< uchar > get_next_record_pointer(size_t min_size)
Where should the next record be stored?
Definition: filesort_utils.h:115
uchar * m_next_rec_ptr
The next record will be inserted here.
Definition: filesort_utils.h:241
Filesort_buffer()
Definition: filesort_utils.h:82
There are several record formats for sorting:
Definition: sort_param.h:295
Dialog Client Authentication nullptr
Definition: dialog.cc:352
This file includes constants used by all storage engines.
Some integer typedefs for easier portability.
unsigned char uchar
Definition: my_inttypes.h:51