1 /* Copyright (c) 2012, 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 Street, Fifth Floor, Boston, MA 02110-1301, USA */
22
23 // First include (the generated) my_config.h, to get correct platform defines.
24 #include "my_config.h"
25 #include <gtest/gtest.h>
26
27 #include "test_utils.h"
28
29 #include "sql_select.h"
30 #include "merge_sort.h"
31
32 #include <vector>
33
34 namespace join_tab_sort_unittest {
35
36 using my_testing::Server_initializer;
37 using my_testing::Mock_error_handler;
38
39 class JTSortTest : public ::testing::Test
40 {
41 protected:
SetUp()42 virtual void SetUp() { initializer.SetUp(); }
TearDown()43 virtual void TearDown() { initializer.TearDown(); }
44
45 Server_initializer initializer;
46 };
47
48
49 class MOCK_JOIN_TAB : public JOIN_TAB
50 {
51 public:
MOCK_JOIN_TAB(uint recs,uint table_no)52 MOCK_JOIN_TAB(uint recs, uint table_no) : JOIN_TAB()
53 {
54 found_records= recs;
55 set_qs(&m_shared);
56 this->set_table(&m_table);
57 m_table_list.set_tableno(table_no);
58 this->table_ref= &m_table_list;
59 }
60
61 TABLE m_table;
62 TABLE_LIST m_table_list;
63 QEP_shared m_shared;
64 };
65
operator <<(std::ostream & s,const MOCK_JOIN_TAB & jt)66 std::ostream &operator<<(std::ostream &s, const MOCK_JOIN_TAB &jt)
67 {
68 return s << "{"
69 << jt.found_records << ", "
70 << jt.m_table_list.map()
71 << "}";
72 }
73
74
TEST_F(JTSortTest,SimpleSortTest)75 TEST_F(JTSortTest, SimpleSortTest)
76 {
77 MOCK_JOIN_TAB jt1(UINT_MAX, 0);
78 MOCK_JOIN_TAB jt2(2, 0);
79 MOCK_JOIN_TAB jt3(1, 0);
80 MOCK_JOIN_TAB jt4(10, 0);
81 MOCK_JOIN_TAB jt5(5, 0);
82
83 MOCK_JOIN_TAB *arr[5];
84 arr[0]= &jt1;
85 arr[1]= &jt2;
86 arr[2]= &jt3;
87 arr[3]= &jt4;
88 arr[4]= &jt5;
89
90 insert_sort(arr, arr+5, Join_tab_compare_default());
91
92 EXPECT_EQ(1U, arr[0]->found_records);
93 EXPECT_EQ(2U, arr[1]->found_records);
94 EXPECT_EQ(5U, arr[2]->found_records);
95 EXPECT_EQ(10U, arr[3]->found_records);
96 EXPECT_EQ(UINT_MAX, arr[4]->found_records);
97
98 }
99
100
TEST_F(JTSortTest,SortFoundRecordsTest)101 TEST_F(JTSortTest, SortFoundRecordsTest)
102 {
103 const int num_tables= 50;
104 MOCK_JOIN_TAB *arr[num_tables];
105
106 for (int i= 0; i < num_tables; i++)
107 arr[i]= new MOCK_JOIN_TAB(i, 0);
108
109 // MERGE SORT
110 std::random_shuffle(arr, arr + 50);
111 merge_sort(arr, arr + num_tables, Join_tab_compare_default());
112 for (int i= 1; i < num_tables; i++)
113 EXPECT_TRUE(arr[i]->found_records > arr[i-1]->found_records);
114
115 // INSERT SORT
116 std::random_shuffle(arr, arr + 50);
117 insert_sort(arr, arr + num_tables, Join_tab_compare_default());
118 for (int i= 1; i < num_tables; i++)
119 EXPECT_TRUE(arr[i]->found_records > arr[i-1]->found_records);
120
121 for (int i= 0; i < num_tables; i++)
122 {
123 delete arr[i];
124 }
125 }
126
127
TEST_F(JTSortTest,SortDependsTest)128 TEST_F(JTSortTest, SortDependsTest)
129 {
130 const int num_tables= 50;
131 MOCK_JOIN_TAB *arr[num_tables];
132
133 /*
134 dependency has higher precedence than found_records, so the tables
135 shall be ordered with decreasing number of records in this test
136 */
137 for (int i= 0; i < num_tables; i++)
138 {
139 arr[i]= new MOCK_JOIN_TAB(i, i);
140 for (int j= i+1; j < num_tables; j++)
141 arr[i]->dependent|= 1ULL << j;
142 }
143
144 // MERGE SORT
145 std::random_shuffle(arr, arr + num_tables);
146 merge_sort(arr, arr + num_tables, Join_tab_compare_default());
147 for (int i= 1; i < num_tables; i++)
148 EXPECT_TRUE(arr[i]->found_records < arr[i-1]->found_records)
149 << "i: " << *(arr[i]) << " "
150 << "i-1: " << *(arr[i-1]);
151
152 // INSERT SORT
153 std::random_shuffle(arr, arr + num_tables);
154 insert_sort(arr, arr + num_tables, Join_tab_compare_default());
155 for (int i= 1; i < num_tables; i++)
156 EXPECT_TRUE(arr[i]->found_records < arr[i-1]->found_records);
157
158 for (int i= 0; i < num_tables; i++)
159 {
160 delete arr[i];
161 }
162 }
163
164
TEST_F(JTSortTest,SortKeyDependsTest)165 TEST_F(JTSortTest, SortKeyDependsTest)
166 {
167 const int num_tables= 50;
168 MOCK_JOIN_TAB *arr[num_tables];
169
170 /*
171 key_dependency has higher precedence than found_records, so the
172 tables shall be ordered with decreasing number of records in this
173 test
174 */
175 for (int i= 0; i < num_tables; i++)
176 {
177 arr[i]= new MOCK_JOIN_TAB(i, i);
178 for (int j= i+1; j < num_tables; j++)
179 arr[i]->key_dependent|= 1ULL << j;
180 }
181
182 // MERGE SORT
183 std::random_shuffle(arr, arr + num_tables);
184 merge_sort(arr, arr + num_tables, Join_tab_compare_default());
185 for (int i= 1; i < num_tables; i++)
186 EXPECT_TRUE(arr[i]->found_records < arr[i-1]->found_records);
187
188 // INSERT SORT
189 std::random_shuffle(arr, arr + num_tables);
190 insert_sort(arr, arr + num_tables, Join_tab_compare_default());
191 for (int i= 1; i < num_tables; i++)
192 EXPECT_TRUE(arr[i]->found_records < arr[i-1]->found_records);
193
194 for (int i= 0; i < num_tables; i++)
195 delete arr[i];
196 }
197
198 /*
199 Above, sorting for JOIN_TABs were tested. Below we check that the
200 sorting works for ints types as well.
201 */
202
203 class Int_compare_ptr :
204 public std::binary_function<const int*, const int*, bool>
205 {
206 public:
operator ()(const int * i1,const int * i2) const207 bool operator()(const int *i1, const int *i2) const
208 {
209 return *i1 < *i2;
210 }
211 };
212
213
TEST_F(JTSortTest,SortIntTest)214 TEST_F(JTSortTest, SortIntTest)
215 {
216 const uint ints_to_sort= 1000;
217
218 std::vector<int> arr;
219 std::vector<int*> arr_ptr;
220
221 arr.reserve(ints_to_sort);
222 arr_ptr.reserve(ints_to_sort);
223
224 for (uint i= 0; i < ints_to_sort; i++)
225 {
226 arr.push_back(i);
227 arr_ptr.push_back(&arr[i]);
228 }
229
230 EXPECT_TRUE(arr.size() == ints_to_sort);
231 EXPECT_TRUE(arr_ptr.size() == ints_to_sort);
232
233 // MERGE SORT
234 std::random_shuffle(&arr_ptr.front(), &arr_ptr.back() + 1);
235 merge_sort(&arr_ptr.front(), &arr_ptr.back() + 1, Int_compare_ptr());
236 for (uint i= 0; i < arr_ptr.size(); i++)
237 EXPECT_TRUE(*arr_ptr[i] == (int)i);
238
239 // INSERT SORT
240 std::random_shuffle(&arr_ptr.front(), &arr_ptr.back() + 1);
241 insert_sort(&arr_ptr.front(), &arr_ptr.back() + 1, Int_compare_ptr());
242 for (uint i= 0; i < arr_ptr.size(); i++)
243 EXPECT_TRUE(*arr_ptr[i] == (int)i);
244 }
245
246
TEST_F(JTSortTest,SortInt2Test)247 TEST_F(JTSortTest, SortInt2Test)
248 {
249 const uint ints_to_sort= 1000;
250
251 std::vector<int> arr;
252 std::vector<int*> arr_ptr;
253
254 arr.reserve(ints_to_sort);
255 arr_ptr.reserve(ints_to_sort);
256
257 for (uint i= 0; i < (ints_to_sort - 2); i++)
258 {
259 arr.push_back((i % 2) ? i : (i * -1));
260 arr_ptr.push_back(&arr[i]);
261 }
262
263 arr.push_back(INT_MAX32);
264 arr_ptr.push_back(&arr.back());
265
266 arr.push_back(INT_MIN32);
267 arr_ptr.push_back(&arr.back());
268
269 EXPECT_TRUE(arr.size() == ints_to_sort);
270 EXPECT_TRUE(arr_ptr.size() == ints_to_sort);
271
272 // MERGE SORT
273 std::random_shuffle(&arr_ptr.front(), &arr_ptr.back() + 1);
274 merge_sort(&arr_ptr.front(), &arr_ptr.back() + 1, Int_compare_ptr());
275 for (uint i= 1; i < arr_ptr.size(); i++)
276 EXPECT_TRUE(*arr_ptr[i-1] < *arr_ptr[i]);
277
278 // INSERT SORT
279 std::random_shuffle(&arr_ptr.front(), &arr_ptr.back() + 1);
280 insert_sort(&arr_ptr.front(), &arr_ptr.back() + 1, Int_compare_ptr());
281 for (uint i= 1; i < arr_ptr.size(); i++)
282 EXPECT_TRUE(*arr_ptr[i-1] < *arr_ptr[i]);
283 }
284
285 }
286