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 namespace {
25 /**
26 A local helper function. See comments for get_merge_buffers_cost().
27 */
get_merge_cost(ha_rows num_elements,ha_rows num_buffers,uint elem_size)28 double get_merge_cost(ha_rows num_elements, ha_rows num_buffers, uint elem_size)
29 {
30 return
31 2.0 * ((double) num_elements * elem_size) / IO_SIZE
32 + (double) num_elements * log((double) num_buffers) /
33 (TIME_FOR_COMPARE_ROWID * M_LN2);
34 }
35 }
36
37 /**
38 This is a simplified, and faster version of @see get_merge_many_buffs_cost().
39 We calculate the cost of merging buffers, by simulating the actions
40 of @see merge_many_buff. For explanations of formulas below,
41 see comments for get_merge_buffers_cost().
42 TODO: Use this function for Unique::get_use_cost().
43 */
get_merge_many_buffs_cost_fast(ha_rows num_rows,ha_rows num_keys_per_buffer,uint elem_size)44 double get_merge_many_buffs_cost_fast(ha_rows num_rows,
45 ha_rows num_keys_per_buffer,
46 uint elem_size)
47 {
48 ha_rows num_buffers= num_rows / num_keys_per_buffer;
49 ha_rows last_n_elems= num_rows % num_keys_per_buffer;
50 double total_cost;
51
52 // Calculate CPU cost of sorting buffers.
53 total_cost=
54 ( num_buffers * num_keys_per_buffer * log(1.0 + num_keys_per_buffer) +
55 last_n_elems * log(1.0 + last_n_elems) )
56 / TIME_FOR_COMPARE_ROWID;
57
58 // Simulate behavior of merge_many_buff().
59 while (num_buffers >= MERGEBUFF2)
60 {
61 // Calculate # of calls to merge_buffers().
62 const ha_rows loop_limit= num_buffers - MERGEBUFF*3/2;
63 const ha_rows num_merge_calls= 1 + loop_limit/MERGEBUFF;
64 const ha_rows num_remaining_buffs=
65 num_buffers - num_merge_calls * MERGEBUFF;
66
67 // Cost of merge sort 'num_merge_calls'.
68 total_cost+=
69 num_merge_calls *
70 get_merge_cost(num_keys_per_buffer * MERGEBUFF, MERGEBUFF, elem_size);
71
72 // # of records in remaining buffers.
73 last_n_elems+= num_remaining_buffs * num_keys_per_buffer;
74
75 // Cost of merge sort of remaining buffers.
76 total_cost+=
77 get_merge_cost(last_n_elems, 1 + num_remaining_buffs, elem_size);
78
79 num_buffers= num_merge_calls;
80 num_keys_per_buffer*= MERGEBUFF;
81 }
82
83 // Simulate final merge_buff call.
84 last_n_elems+= num_keys_per_buffer * num_buffers;
85 total_cost+= get_merge_cost(last_n_elems, 1 + num_buffers, elem_size);
86 return total_cost;
87 }
88
89 /*
90 alloc_sort_buffer()
91
92 Allocate buffer for sorting keys.
93 Try to reuse old buffer if possible.
94
95 @return
96 0 Error
97 # Pointer to allocated buffer
98 */
99
alloc_sort_buffer(uint num_records,uint record_length)100 uchar **Filesort_buffer::alloc_sort_buffer(uint num_records,
101 uint record_length)
102 {
103 size_t buff_size;
104 uchar **sort_keys, **start_of_data;
105 DBUG_ENTER("alloc_sort_buffer");
106 DBUG_EXECUTE_IF("alloc_sort_buffer_fail",
107 DBUG_SET("+d,simulate_out_of_memory"););
108
109 buff_size= ((size_t)num_records) * (record_length + sizeof(uchar*));
110
111 if (!m_idx_array.is_null())
112 {
113 /*
114 Reuse old buffer if exists and is large enough
115 Note that we don't make the buffer smaller, as we want to be
116 prepared for next subquery iteration.
117 */
118
119 sort_keys= m_idx_array.array();
120 if (buff_size > allocated_size)
121 {
122 /*
123 Better to free and alloc than realloc as we don't have to remember
124 the old values
125 */
126 my_free(sort_keys);
127 if (!(sort_keys= (uchar**) my_malloc(buff_size,
128 MYF(MY_THREAD_SPECIFIC))))
129 {
130 reset();
131 DBUG_RETURN(0);
132 }
133 allocated_size= buff_size;
134 }
135 }
136 else
137 {
138 if (!(sort_keys= (uchar**) my_malloc(buff_size, MYF(MY_THREAD_SPECIFIC))))
139 DBUG_RETURN(0);
140 allocated_size= buff_size;
141 }
142
143 m_idx_array= Idx_array(sort_keys, num_records);
144 m_record_length= record_length;
145 start_of_data= m_idx_array.array() + m_idx_array.size();
146 m_start_of_data= reinterpret_cast<uchar*>(start_of_data);
147
148 DBUG_RETURN(m_idx_array.array());
149 }
150
151
free_sort_buffer()152 void Filesort_buffer::free_sort_buffer()
153 {
154 my_free(m_idx_array.array());
155 m_idx_array.reset();
156 m_start_of_data= NULL;
157 }
158
159
sort_buffer(const Sort_param * param,uint count)160 void Filesort_buffer::sort_buffer(const Sort_param *param, uint count)
161 {
162 size_t size= param->sort_length;
163 if (count <= 1 || size == 0)
164 return;
165 uchar **keys= get_sort_keys();
166 uchar **buffer= NULL;
167 if (radixsort_is_appliccable(count, param->sort_length) &&
168 (buffer= (uchar**) my_malloc(count*sizeof(char*),
169 MYF(MY_THREAD_SPECIFIC))))
170 {
171 radixsort_for_str_ptr(keys, count, param->sort_length, buffer);
172 my_free(buffer);
173 return;
174 }
175
176 my_qsort2(keys, count, sizeof(uchar*), get_ptr_compare(size), &size);
177 }
178