1/* Copyright (c) 2010, Oracle and/or its affiliates. All rights reserved.
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 as published by
5 the Free Software Foundation; version 2 of the License.
6
7 This program is distributed in the hope that it will be useful,
8 but WITHOUT ANY WARRANTY; without even the implied warranty of
9 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 GNU General Public License for more details.
11
12 You should have received a copy of the GNU General Public License
13 along with this program; if not, write to the Free Software
14 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1301 USA */
15
16#include "mariadb.h"
17#include "filesort_utils.h"
18#include "sql_const.h"
19#include "sql_sort.h"
20#include "table.h"
21
22
23namespace {
24/**
25 A local helper function. See comments for get_merge_buffers_cost().
26 */
27double get_merge_cost(ha_rows num_elements, ha_rows num_buffers, uint elem_size)
28{
29 return
30 2.0 * ((double) num_elements * elem_size) / IO_SIZE
31 + (double) num_elements * log((double) num_buffers) /
32 (TIME_FOR_COMPARE_ROWID * M_LN2);
33}
34}
35
36/**
37 This is a simplified, and faster version of @see get_merge_many_buffs_cost().
38 We calculate the cost of merging buffers, by simulating the actions
39 of @see merge_many_buff. For explanations of formulas below,
40 see comments for get_merge_buffers_cost().
41 TODO: Use this function for Unique::get_use_cost().
42*/
43double get_merge_many_buffs_cost_fast(ha_rows num_rows,
44 ha_rows num_keys_per_buffer,
45 uint elem_size)
46{
47 ha_rows num_buffers= num_rows / num_keys_per_buffer;
48 ha_rows last_n_elems= num_rows % num_keys_per_buffer;
49 double total_cost;
50
51 // Calculate CPU cost of sorting buffers.
52 total_cost=
53 ( num_buffers * num_keys_per_buffer * log(1.0 + num_keys_per_buffer) +
54 last_n_elems * log(1.0 + last_n_elems) )
55 / TIME_FOR_COMPARE_ROWID;
56
57 // Simulate behavior of merge_many_buff().
58 while (num_buffers >= MERGEBUFF2)
59 {
60 // Calculate # of calls to merge_buffers().
61 const ha_rows loop_limit= num_buffers - MERGEBUFF*3/2;
62 const ha_rows num_merge_calls= 1 + loop_limit/MERGEBUFF;
63 const ha_rows num_remaining_buffs=
64 num_buffers - num_merge_calls * MERGEBUFF;
65
66 // Cost of merge sort 'num_merge_calls'.
67 total_cost+=
68 num_merge_calls *
69 get_merge_cost(num_keys_per_buffer * MERGEBUFF, MERGEBUFF, elem_size);
70
71 // # of records in remaining buffers.
72 last_n_elems+= num_remaining_buffs * num_keys_per_buffer;
73
74 // Cost of merge sort of remaining buffers.
75 total_cost+=
76 get_merge_cost(last_n_elems, 1 + num_remaining_buffs, elem_size);
77
78 num_buffers= num_merge_calls;
79 num_keys_per_buffer*= MERGEBUFF;
80 }
81
82 // Simulate final merge_buff call.
83 last_n_elems+= num_keys_per_buffer * num_buffers;
84 total_cost+= get_merge_cost(last_n_elems, 1 + num_buffers, elem_size);
85 return total_cost;
86}
87
88/*
89 alloc_sort_buffer()
90
91 Allocate buffer for sorting keys.
92 Try to reuse old buffer if possible.
93
94 @return
95 0 Error
96 # Pointer to allocated buffer
97*/
98
99uchar **Filesort_buffer::alloc_sort_buffer(uint num_records,
100 uint record_length)
101{
102 size_t buff_size;
103 uchar **sort_keys, **start_of_data;
104 DBUG_ENTER("alloc_sort_buffer");
105 DBUG_EXECUTE_IF("alloc_sort_buffer_fail",
106 DBUG_SET("+d,simulate_out_of_memory"););
107
108 buff_size= ((size_t)num_records) * (record_length + sizeof(uchar*));
109 set_if_bigger(buff_size, record_length * MERGEBUFF2);
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
152void 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
160void 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