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 #include "filesort_utils.h"
24 #include "opt_costmodel.h"
25 #include "sql_const.h"
26 #include "sql_sort.h"
27 #include "table.h"
28
29 #include <algorithm>
30 #include <functional>
31 #include <vector>
32
33 PSI_memory_key key_memory_Filesort_buffer_sort_keys;
34
35 namespace {
36 /**
37 A local helper function. See comments for get_merge_buffers_cost().
38 */
get_merge_cost(ha_rows num_elements,ha_rows num_buffers,uint elem_size,const Cost_model_table * cost_model)39 double get_merge_cost(ha_rows num_elements, ha_rows num_buffers, uint elem_size,
40 const Cost_model_table *cost_model)
41 {
42 const double io_ops= static_cast<double>(num_elements * elem_size) / IO_SIZE;
43 const double io_cost= cost_model->io_block_read_cost(io_ops);
44 const double cpu_cost=
45 cost_model->key_compare_cost(num_elements * log((double) num_buffers) /
46 M_LN2);
47 return 2 * io_cost + cpu_cost;
48 }
49 }
50
51 /**
52 This is a simplified, and faster version of @see get_merge_many_buffs_cost().
53 We calculate the cost of merging buffers, by simulating the actions
54 of @see merge_many_buff. For explanations of formulas below,
55 see comments for get_merge_buffers_cost().
56 TODO: Use this function for Unique::get_use_cost().
57 */
get_merge_many_buffs_cost_fast(ha_rows num_rows,ha_rows num_keys_per_buffer,uint elem_size,const Cost_model_table * cost_model)58 double get_merge_many_buffs_cost_fast(ha_rows num_rows,
59 ha_rows num_keys_per_buffer,
60 uint elem_size,
61 const Cost_model_table *cost_model)
62 {
63 ha_rows num_buffers= num_rows / num_keys_per_buffer;
64 ha_rows last_n_elems= num_rows % num_keys_per_buffer;
65 double total_cost;
66
67 // Calculate CPU cost of sorting buffers.
68 total_cost=
69 num_buffers * cost_model->key_compare_cost(num_keys_per_buffer *
70 log(1.0 + num_keys_per_buffer)) +
71 cost_model->key_compare_cost(last_n_elems * log(1.0 + last_n_elems));
72
73 // Simulate behavior of merge_many_buff().
74 while (num_buffers >= MERGEBUFF2)
75 {
76 // Calculate # of calls to merge_buffers().
77 const ha_rows loop_limit= num_buffers - MERGEBUFF*3/2;
78 const ha_rows num_merge_calls= 1 + loop_limit/MERGEBUFF;
79 const ha_rows num_remaining_buffs=
80 num_buffers - num_merge_calls * MERGEBUFF;
81
82 // Cost of merge sort 'num_merge_calls'.
83 total_cost+=
84 num_merge_calls *
85 get_merge_cost(num_keys_per_buffer * MERGEBUFF, MERGEBUFF, elem_size,
86 cost_model);
87
88 // # of records in remaining buffers.
89 last_n_elems+= num_remaining_buffs * num_keys_per_buffer;
90
91 // Cost of merge sort of remaining buffers.
92 total_cost+=
93 get_merge_cost(last_n_elems, 1 + num_remaining_buffs, elem_size,
94 cost_model);
95
96 num_buffers= num_merge_calls;
97 num_keys_per_buffer*= MERGEBUFF;
98 }
99
100 // Simulate final merge_buff call.
101 last_n_elems+= num_keys_per_buffer * num_buffers;
102 total_cost+= get_merge_cost(last_n_elems, 1 + num_buffers, elem_size,
103 cost_model);
104 return total_cost;
105 }
106
107
alloc_sort_buffer(uint num_records,uint record_length)108 uchar *Filesort_buffer::alloc_sort_buffer(uint num_records, uint record_length)
109 {
110 DBUG_EXECUTE_IF("alloc_sort_buffer_fail",
111 DBUG_SET("+d,simulate_out_of_memory"););
112
113 /*
114 For subqueries we try to re-use the buffer, in order to save
115 expensive malloc/free calls. Both of the sizing parameters may change:
116 - num_records due to e.g. different statistics from the engine.
117 - record_length due to different buffer usage:
118 a heap table may be flushed to myisam, which allows us to sort by
119 <key, addon fields> rather than <key, rowid>
120 If we already have a buffer, but with wrong size, we simply delete it.
121 */
122 if (m_rawmem != NULL)
123 {
124 if (num_records != m_num_records ||
125 record_length != m_record_length)
126 free_sort_buffer();
127 }
128
129 m_size_in_bytes= ALIGN_SIZE(num_records * (record_length + sizeof(uchar*)));
130 if (m_rawmem == NULL)
131 m_rawmem= (uchar*) my_malloc(key_memory_Filesort_buffer_sort_keys,
132 m_size_in_bytes, MYF(0));
133 if (m_rawmem == NULL)
134 {
135 m_size_in_bytes= 0;
136 return NULL;
137 }
138 m_record_pointers= reinterpret_cast<uchar**>(m_rawmem)
139 + ((m_size_in_bytes / sizeof(uchar*)) - 1);
140 m_num_records= num_records;
141 m_record_length= record_length;
142 m_idx= 0;
143 return m_rawmem;
144 }
145
146 namespace {
147
148 /*
149 An inline function which does memcmp().
150 This one turns out to be pretty fast on all platforms, except sparc.
151 See the accompanying unit tests, which measure various implementations.
152 */
my_mem_compare(const uchar * s1,const uchar * s2,size_t len)153 inline bool my_mem_compare(const uchar *s1, const uchar *s2, size_t len)
154 {
155 assert(len > 0);
156 assert(s1 != NULL);
157 assert(s2 != NULL);
158 do {
159 if (*s1++ != *s2++)
160 return *--s1 < *--s2;
161 } while (--len != 0);
162 return false;
163 }
164
165 #define COMPARE(N) if (s1[N] != s2[N]) return s1[N] < s2[N]
166
my_mem_compare_longkey(const uchar * s1,const uchar * s2,size_t len)167 inline bool my_mem_compare_longkey(const uchar *s1, const uchar *s2, size_t len)
168 {
169 COMPARE(0);
170 COMPARE(1);
171 COMPARE(2);
172 COMPARE(3);
173 return memcmp(s1 + 4, s2 + 4, len - 4) < 0;
174 }
175
176
177 class Mem_compare :
178 public std::binary_function<const uchar*, const uchar*, bool>
179 {
180 public:
Mem_compare(size_t n)181 Mem_compare(size_t n) : m_size(n) {}
operator ()(const uchar * s1,const uchar * s2) const182 bool operator()(const uchar *s1, const uchar *s2) const
183 {
184 #ifdef __sun
185 // The native memcmp is faster on SUN.
186 return memcmp(s1, s2, m_size) < 0;
187 #else
188 return my_mem_compare(s1, s2, m_size);
189 #endif
190 }
191 private:
192 size_t m_size;
193 };
194
195 class Mem_compare_longkey :
196 public std::binary_function<const uchar*, const uchar*, bool>
197 {
198 public:
Mem_compare_longkey(size_t n)199 Mem_compare_longkey(size_t n) : m_size(n) {}
operator ()(const uchar * s1,const uchar * s2) const200 bool operator()(const uchar *s1, const uchar *s2) const
201 {
202 #ifdef __sun
203 // The native memcmp is faster on SUN.
204 return memcmp(s1, s2, m_size) < 0;
205 #else
206 return my_mem_compare_longkey(s1, s2, m_size);
207 #endif
208 }
209 private:
210 size_t m_size;
211 };
212
213 template <typename type>
try_reserve(std::pair<type *,ptrdiff_t> * buf,ptrdiff_t size)214 size_t try_reserve(std::pair<type*, ptrdiff_t> *buf, ptrdiff_t size)
215 {
216 *buf= std::get_temporary_buffer<type>(size);
217 if (buf->second != size)
218 {
219 std::return_temporary_buffer(buf->first);
220 return 0;
221 }
222 return buf->second;
223 }
224
225 } // namespace
226
sort_buffer(const Sort_param * param,uint count)227 void Filesort_buffer::sort_buffer(const Sort_param *param, uint count)
228 {
229 m_sort_keys= get_sort_keys();
230
231 if (count <= 1)
232 return;
233 if (param->sort_length == 0)
234 return;
235
236 // For priority queue we have already reversed the pointers.
237 if (!param->using_pq)
238 {
239 reverse_record_pointers();
240 }
241 std::pair<uchar**, ptrdiff_t> buffer;
242 if (radixsort_is_appliccable(count, param->sort_length) &&
243 try_reserve(&buffer, count))
244 {
245 radixsort_for_str_ptr(m_sort_keys, count, param->sort_length, buffer.first);
246 std::return_temporary_buffer(buffer.first);
247 return;
248 }
249 /*
250 std::stable_sort has some extra overhead in allocating the temp buffer,
251 which takes some time. The cutover point where it starts to get faster
252 than quicksort seems to be somewhere around 10 to 40 records.
253 So we're a bit conservative, and stay with quicksort up to 100 records.
254 */
255 if (count <= 100)
256 {
257 if (param->sort_length < 10)
258 {
259 std::sort(m_sort_keys, m_sort_keys + count,
260 Mem_compare(param->sort_length));
261 return;
262 }
263 std::sort(m_sort_keys, m_sort_keys + count,
264 Mem_compare_longkey(param->sort_length));
265 return;
266 }
267 // Heuristics here: avoid function overhead call for short keys.
268 if (param->sort_length < 10)
269 {
270 std::stable_sort(m_sort_keys, m_sort_keys + count,
271 Mem_compare(param->sort_length));
272 return;
273 }
274 std::stable_sort(m_sort_keys, m_sort_keys + count,
275 Mem_compare_longkey(param->sort_length));
276 }
277