1 /* Copyright (c) 2010, Oracle and/or its affiliates. All rights reserved.
2 Copyright (c) 2012, 2020, MariaDB
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; version 2 of the License.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; if not, write to the Free Software
15 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA */
16
17 #include "mariadb.h"
18 #include "filesort_utils.h"
19 #include "sql_const.h"
20 #include "sql_sort.h"
21 #include "table.h"
22
23
24 PSI_memory_key key_memory_Filesort_buffer_sort_keys;
25
26 namespace {
27 /**
28 A local helper function. See comments for get_merge_buffers_cost().
29 */
get_merge_cost(ha_rows num_elements,ha_rows num_buffers,uint elem_size)30 double get_merge_cost(ha_rows num_elements, ha_rows num_buffers, uint elem_size)
31 {
32 return
33 2.0 * ((double) num_elements * elem_size) / IO_SIZE
34 + (double) num_elements * log((double) num_buffers) /
35 (TIME_FOR_COMPARE_ROWID * M_LN2);
36 }
37 }
38
39 /**
40 This is a simplified, and faster version of @see get_merge_many_buffs_cost().
41 We calculate the cost of merging buffers, by simulating the actions
42 of @see merge_many_buff. For explanations of formulas below,
43 see comments for get_merge_buffers_cost().
44 TODO: Use this function for Unique::get_use_cost().
45 */
get_merge_many_buffs_cost_fast(ha_rows num_rows,ha_rows num_keys_per_buffer,uint elem_size)46 double get_merge_many_buffs_cost_fast(ha_rows num_rows,
47 ha_rows num_keys_per_buffer,
48 uint elem_size)
49 {
50 ha_rows num_buffers= num_rows / num_keys_per_buffer;
51 ha_rows last_n_elems= num_rows % num_keys_per_buffer;
52 double total_cost;
53
54 // Calculate CPU cost of sorting buffers.
55 total_cost=
56 ((num_buffers * num_keys_per_buffer * log(1.0 + num_keys_per_buffer) +
57 last_n_elems * log(1.0 + last_n_elems)) /
58 TIME_FOR_COMPARE_ROWID);
59
60 // Simulate behavior of merge_many_buff().
61 while (num_buffers >= MERGEBUFF2)
62 {
63 // Calculate # of calls to merge_buffers().
64 const ha_rows loop_limit= num_buffers - MERGEBUFF*3/2;
65 const ha_rows num_merge_calls= 1 + loop_limit/MERGEBUFF;
66 const ha_rows num_remaining_buffs=
67 num_buffers - num_merge_calls * MERGEBUFF;
68
69 // Cost of merge sort 'num_merge_calls'.
70 total_cost+=
71 num_merge_calls *
72 get_merge_cost(num_keys_per_buffer * MERGEBUFF, MERGEBUFF, elem_size);
73
74 // # of records in remaining buffers.
75 last_n_elems+= num_remaining_buffs * num_keys_per_buffer;
76
77 // Cost of merge sort of remaining buffers.
78 total_cost+=
79 get_merge_cost(last_n_elems, 1 + num_remaining_buffs, elem_size);
80
81 num_buffers= num_merge_calls;
82 num_keys_per_buffer*= MERGEBUFF;
83 }
84
85 // Simulate final merge_buff call.
86 last_n_elems+= num_keys_per_buffer * num_buffers;
87 total_cost+= get_merge_cost(last_n_elems, 1 + num_buffers, elem_size);
88 return total_cost;
89 }
90
91 /*
92 alloc_sort_buffer()
93
94 Allocate buffer for sorting keys.
95 Try to reuse old buffer if possible.
96
97 @return
98 0 Error
99 # Pointer to allocated buffer
100 */
101
alloc_sort_buffer(uint num_records,uint record_length)102 uchar *Filesort_buffer::alloc_sort_buffer(uint num_records,
103 uint record_length)
104 {
105 size_t buff_size;
106 DBUG_ENTER("alloc_sort_buffer");
107 DBUG_EXECUTE_IF("alloc_sort_buffer_fail",
108 DBUG_SET("+d,simulate_out_of_memory"););
109
110 buff_size= ALIGN_SIZE(num_records * (record_length + sizeof(uchar*)));
111
112 if (m_rawmem)
113 {
114 /*
115 Reuse old buffer if exists and is large enough
116 Note that we don't make the buffer smaller, as we want to be
117 prepared for next subquery iteration.
118 */
119 if (buff_size > m_size_in_bytes)
120 {
121 /*
122 Better to free and alloc than realloc as we don't have to remember
123 the old values
124 */
125 my_free(m_rawmem);
126 if (!(m_rawmem= (uchar*) my_malloc(key_memory_Filesort_buffer_sort_keys,
127 buff_size, MYF(MY_THREAD_SPECIFIC))))
128 {
129 m_size_in_bytes= 0;
130 DBUG_RETURN(0);
131 }
132 }
133 }
134 else
135 {
136 if (!(m_rawmem= (uchar*) my_malloc(key_memory_Filesort_buffer_sort_keys,
137 buff_size, MYF(MY_THREAD_SPECIFIC))))
138 {
139 m_size_in_bytes= 0;
140 DBUG_RETURN(0);
141 }
142
143 }
144
145 m_size_in_bytes= buff_size;
146 m_record_pointers= reinterpret_cast<uchar**>(m_rawmem) +
147 ((m_size_in_bytes / sizeof(uchar*)) - 1);
148 m_num_records= num_records;
149 m_record_length= record_length;
150 m_idx= 0;
151 DBUG_RETURN(m_rawmem);
152 }
153
154
free_sort_buffer()155 void Filesort_buffer::free_sort_buffer()
156 {
157 my_free(m_rawmem);
158 *this= Filesort_buffer();
159 }
160
161
sort_buffer(const Sort_param * param,uint count)162 void Filesort_buffer::sort_buffer(const Sort_param *param, uint count)
163 {
164 size_t size= param->sort_length;
165 m_sort_keys= get_sort_keys();
166
167 if (count <= 1 || size == 0)
168 return;
169
170 // don't reverse for PQ, it is already done
171 if (!param->using_pq)
172 reverse_record_pointers();
173
174 uchar **buffer= NULL;
175 if (!param->using_packed_sortkeys() &&
176 radixsort_is_appliccable(count, param->sort_length) &&
177 (buffer= (uchar**) my_malloc(PSI_INSTRUMENT_ME, count*sizeof(char*),
178 MYF(MY_THREAD_SPECIFIC))))
179 {
180 radixsort_for_str_ptr(m_sort_keys, count, param->sort_length, buffer);
181 my_free(buffer);
182 return;
183 }
184
185 my_qsort2(m_sort_keys, count, sizeof(uchar*),
186 param->get_compare_function(),
187 param->get_compare_argument(&size));
188 }
189