MySQL  8.0.27
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, 2021, 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 
34 class Addon_fields;
35 struct TABLE;
36 
37 /* Defines used by filesort and uniques */
38 
39 constexpr size_t MERGEBUFF = 7;
40 constexpr size_t MERGEBUFF2 = 15;
41 // Number of bytes used to store varlen key's length
42 constexpr 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  */
56 struct Merge_chunk {
57  public:
60  m_file_position(0),
63  m_rowcount(0),
64  m_mem_count(0),
65  m_max_keys(0) {}
66 
70 
72  const uchar *buffer_end() const { return m_buffer_end; }
73 
76  m_buffer_end = end;
77  }
80  assert(m_buffer_end == nullptr || end <= m_buffer_end);
81  m_buffer_end = end;
82  }
83 
85  uchar *current_key() const { return m_current_key; }
86  void advance_current_key(uint val) { m_current_key += val; }
87 
88  void decrement_rowcount(ha_rows val) { m_rowcount -= val; }
89  void set_rowcount(ha_rows val) { m_rowcount = val; }
90  ha_rows rowcount() const { return m_rowcount; }
91 
92  ha_rows mem_count() const { return m_mem_count; }
93  void set_mem_count(ha_rows val) { m_mem_count = val; }
95 
96  ha_rows max_keys() const { return m_max_keys; }
97  void set_max_keys(ha_rows val) { m_max_keys = val; }
98 
99  size_t buffer_size() const { return m_buffer_end - m_buffer_start; }
100 
101  /**
102  Tries to merge *this with *mc, returns true if successful.
103  The assumption is that *this is no longer in use,
104  and the space it has been allocated can be handed over to a
105  buffer which is adjacent to it.
106  */
108  if (mc->m_buffer_end == m_buffer_start) {
109  mc->m_buffer_end = m_buffer_end;
110  mc->m_max_keys += m_max_keys;
111  return true;
112  } else if (mc->m_buffer_start == m_buffer_end) {
113  mc->m_buffer_start = m_buffer_start;
114  mc->m_max_keys += m_max_keys;
115  return true;
116  }
117  return false;
118  }
119 
120  private:
121  uchar *m_current_key; ///< The current key for this chunk.
122  my_off_t m_file_position; ///< Current position in the file to be sorted.
123  uchar *m_buffer_start; ///< Start of main-memory buffer for this chunk.
124  uchar *m_buffer_end; ///< End of main-memory buffer for this chunk.
125  ha_rows m_rowcount; ///< Number of unread rows in this chunk.
126  ha_rows m_mem_count; ///< Number of rows in the main-memory buffer.
127  ha_rows m_max_keys; ///< If we have fixed-size rows:
128  /// max number of rows in buffer.
129 };
130 
132 
133 /*
134  The result of Unique or filesort; can either be stored on disk
135  (in which case io_cache points to the file) or in memory in one
136  of two ways. See sorted_result_in_fsbuf.
137 
138  Note if sort_result points into memory, it does _not_ own the sort buffer;
139  Filesort_info does.
140 
141  TODO: Clean up so that Filesort / Filesort_info / Filesort_buffer /
142  Sort_result have less confusing overlap.
143 */
144 class Sort_result {
145  public:
147 
148  bool has_result_in_memory() const {
150  }
151 
152  bool has_result() const {
154  }
155 
156  IO_CACHE *io_cache{nullptr};
157 
158  /**
159  If the entire result fits in memory, we skip the merge phase.
160  We may leave the result in the parent Filesort_info's filesort_buffer
161  (indicated by sorted_result_in_fsbuf), or we may strip away
162  the sort keys, and copy the sorted result into a new buffer.
163  Unique always uses the latter.
164  This new buffer is [sorted_result ... sorted_result_end]
165  @see save_index()
166  */
170 
171  ha_rows found_records{0}; ///< How many records in sort.
172 };
173 
174 /**
175  A class wrapping misc buffers used for sorting.
176  */
178  /// Buffer for sorting keys.
180 
181  public:
182  Merge_chunk_array merge_chunks; ///< Array of chunk descriptors
183 
184  Addon_fields *addon_fields{nullptr}; ///< Addon field descriptors.
185 
186  bool m_using_varlen_keys{false};
188 
189  Filesort_info(const Filesort_info &) = delete;
191 
193 
194  /** Sort filesort_buffer
195  @return Number of records, after any deduplication
196  */
197  size_t sort_buffer(Sort_param *param, size_t num_input_rows,
198  size_t max_output_rows) {
199  return filesort_buffer.sort_buffer(param, num_input_rows, max_output_rows);
200  }
201 
202  /**
203  Copies (unpacks) values appended to sorted fields from a buffer back to
204  their regular positions specified by the Field::ptr pointers.
205  @param tables Tables in the join; for NULL row flags.
206  @param buff Buffer which to unpack the value from.
207  */
208  template <bool Packed_addon_fields>
209  inline void unpack_addon_fields(const Mem_root_array<TABLE *> &tables,
210  uchar *buff);
211 
212  /**
213  Reads 'count' number of chunk descriptors into the merge_chunks array.
214  In case of error, the merge_chunks array will be empty.
215  @param chunk_file File containing the descriptors.
216  @param count Number of chunks to read.
217  */
218  void read_chunk_descriptors(IO_CACHE *chunk_file, uint count);
219 
220  /// Are we using "addon fields"?
221  bool using_addon_fields() const { return addon_fields != nullptr; }
222 
224 
226 
228  return filesort_buffer.get_next_record_pointer(min_size);
229  }
230 
231  void commit_used_memory(size_t num_bytes) {
233  }
234 
237  }
238 
240 
243  }
244 
245  void set_max_size(size_t max_size, size_t record_length) {
246  filesort_buffer.set_max_size(max_size, record_length);
247  }
248 
250 
251  bool preallocate_records(size_t num_records) {
252  return filesort_buffer.preallocate_records(num_records);
253  }
254 
255  size_t peak_memory_used() const { return filesort_buffer.peak_memory_used(); }
256 
257  size_t max_size_in_bytes() const {
259  }
260 
261  uint sort_length() const { return m_sort_length; }
262  bool using_varlen_keys() const { return m_using_varlen_keys; }
263 
264  void set_sort_length(uint val, bool is_varlen) {
265  m_sort_length = val;
266  m_using_varlen_keys = is_varlen;
267  }
268 };
269 
271 
272 /**
273  Put all room used by freed buffer to use in adjacent buffer.
274 
275  Note, that we can't simply distribute memory evenly between all buffers,
276  because new areas must not overlap with old ones.
277 */
278 template <typename Heap_type>
279 void reuse_freed_buff(Merge_chunk *old_top, Heap_type *heap) {
280  typename Heap_type::iterator it = heap->begin();
281  typename Heap_type::iterator end = heap->end();
282  for (; it != end; ++it) {
283  if (old_top->merge_freed_buff(*it)) return;
284  }
285  assert(0);
286 }
287 
288 #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
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 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
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
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
A class wrapping misc buffers used for sorting.
Definition: sql_sort.h:177
void free_sort_buffer()
Definition: sql_sort.h:249
Addon_fields * addon_fields
Addon field descriptors.
Definition: sql_sort.h:184
bool preallocate_records(size_t num_records)
Definition: sql_sort.h:251
uchar ** get_sort_keys()
Definition: sql_sort.h:239
void clear_peak_memory_used()
Definition: sql_sort.h:225
void commit_used_memory(size_t num_bytes)
Definition: sql_sort.h:231
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:192
bool using_addon_fields() const
Are we using "addon fields"?
Definition: sql_sort.h:221
Bounds_checked_array< uchar > get_contiguous_buffer()
Definition: sql_sort.h:241
void read_chunk_descriptors(IO_CACHE *chunk_file, uint count)
Reads 'count' number of chunk descriptors into the merge_chunks array.
Definition: filesort.cc:719
bool m_using_varlen_keys
Definition: sql_sort.h:186
void set_sort_length(uint val, bool is_varlen)
Definition: sql_sort.h:264
bool using_varlen_keys() const
Definition: sql_sort.h:262
Merge_chunk_array merge_chunks
Array of chunk descriptors.
Definition: sql_sort.h:182
Filesort_buffer filesort_buffer
Buffer for sorting keys.
Definition: sql_sort.h:179
uint m_sort_length
Definition: sql_sort.h:187
size_t sort_buffer(Sort_param *param, size_t num_input_rows, size_t max_output_rows)
Sort filesort_buffer.
Definition: sql_sort.h:197
size_t max_size_in_bytes() const
Definition: sql_sort.h:257
Filesort_info & operator=(const Filesort_info &)=delete
void reset()
Definition: sql_sort.h:223
void set_max_size(size_t max_size, size_t record_length)
Definition: sql_sort.h:245
uint sort_length() const
Definition: sql_sort.h:261
size_t peak_memory_used() const
Definition: sql_sort.h:255
Bounds_checked_array< uchar > get_next_record_pointer(size_t min_size)
Definition: sql_sort.h:227
Filesort_info(const Filesort_info &)=delete
uchar * get_sorted_record(uint idx)
Definition: sql_sort.h:235
There are several record formats for sorting:
Definition: sort_param.h:295
Definition: sql_sort.h:144
IO_CACHE * io_cache
Definition: sql_sort.h:156
bool has_result() const
Definition: sql_sort.h:152
unique_ptr_my_free< uchar > sorted_result
Definition: sql_sort.h:168
Sort_result()
Definition: sql_sort.h:146
uchar * sorted_result_end
Definition: sql_sort.h:169
bool has_result_in_memory() const
Definition: sql_sort.h:148
bool sorted_result_in_fsbuf
If the entire result fits in memory, we skip the merge phase.
Definition: sql_sort.h:167
ha_rows found_records
How many records in sort.
Definition: sql_sort.h:171
Dialog Client Authentication nullptr
Definition: dialog.cc:352
plugin_messages_callback mc
Definition: fido_client_plugin.cc:51
bool my_b_inited(const IO_CACHE *info)
Definition: my_sys.h:488
static void start(mysql_harness::PluginFuncEnv *env)
Definition: http_auth_backend_plugin.cc:165
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:1138
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:42
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:131
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:279
Bounds_checked_array< uchar > Sort_buffer
Definition: sql_sort.h:270
Definition: my_sys.h:340
Descriptor for a merge chunk to be sort-merged.
Definition: sql_sort.h:56
uchar * m_buffer_start
Start of main-memory buffer for this chunk.
Definition: sql_sort.h:123
void init_current_key()
Definition: sql_sort.h:84
bool merge_freed_buff(Merge_chunk *mc) const
Tries to merge *this with *mc, returns true if successful.
Definition: sql_sort.h:107
ha_rows m_rowcount
Number of unread rows in this chunk.
Definition: sql_sort.h:125
uchar * buffer_start()
Definition: sql_sort.h:71
void set_mem_count(ha_rows val)
Definition: sql_sort.h:93
void set_buffer_start(uchar *start)
Definition: sql_sort.h:78
void advance_current_key(uint val)
Definition: sql_sort.h:86
ha_rows mem_count() const
Definition: sql_sort.h:92
void set_file_position(my_off_t val)
Definition: sql_sort.h:68
void set_max_keys(ha_rows val)
Definition: sql_sort.h:97
void advance_file_position(my_off_t val)
Definition: sql_sort.h:69
my_off_t m_file_position
Current position in the file to be sorted.
Definition: sql_sort.h:122
ha_rows rowcount() const
Definition: sql_sort.h:90
Merge_chunk()
Definition: sql_sort.h:58
const uchar * buffer_end() const
Definition: sql_sort.h:72
void decrement_rowcount(ha_rows val)
Definition: sql_sort.h:88
uchar * current_key() const
Definition: sql_sort.h:85
void set_buffer(uchar *start, uchar *end)
Definition: sql_sort.h:74
my_off_t file_position() const
Definition: sql_sort.h:67
ha_rows decrement_mem_count()
Definition: sql_sort.h:94
void set_rowcount(ha_rows val)
Definition: sql_sort.h:89
void set_buffer_end(uchar *end)
Definition: sql_sort.h:79
size_t buffer_size() const
Definition: sql_sort.h:99
ha_rows max_keys() const
Definition: sql_sort.h:96
ha_rows m_max_keys
If we have fixed-size rows: max number of rows in buffer.
Definition: sql_sort.h:127
uchar * m_current_key
The current key for this chunk.
Definition: sql_sort.h:121
ha_rows m_mem_count
Number of rows in the main-memory buffer.
Definition: sql_sort.h:126
uchar * m_buffer_end
End of main-memory buffer for this chunk.
Definition: sql_sort.h:124
Definition: table.h:1394
unsigned int uint
Definition: uca-dump.cc:29