1 /* Copyright (c) 2011, 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 "mock_field_long.h"
28 #include <vector>
29 #include <sstream>
30 #include <string>
31
32 #include "handler-t.h"
33 #include "fake_table.h"
34 #include "fake_range_opt_param.h"
35 #include "test_utils.h"
36
37 #include "opt_range.cc"
38 #include "parse_tree_helpers.h"
39
40 namespace opt_range_unittest {
41
42 using std::vector;
43 using std::string;
44
45 /**
46 Helper class to print which line a failing test was called from.
47 */
48 class TestFailLinePrinter
49 {
50 public:
TestFailLinePrinter(int line)51 explicit TestFailLinePrinter(int line) : m_line(line) {}
52 int m_line;
53 };
operator <<(std::ostream & s,const TestFailLinePrinter & v)54 std::ostream &operator<< (std::ostream &s, const TestFailLinePrinter &v)
55 {
56 return s << "called from line " << v.m_line;
57 }
58
59 /**
60 Keep in mind the following boolean algebra definitions and rules
61 when reading the tests in this file:
62
63 Operators:
64 & (and)
65 | (or)
66 ! (negation)
67
68 DeMorgans laws:
69 DM1: !(X & Y) <==> !X | !Y
70 DM2: !(X | Y) <==> !X & !Y
71
72 Boolean axioms:
73 A1 (associativity): X & (Y & Z) <==> (X & Y) & Z
74 X | (Y | Z) <==> (X | Y) | Z
75 A2 (commutativity): X & Y <==> Y & X
76 X | Y <==> Y | X
77 A3 (identity): X | false <==> X
78 X | true <==> true
79 X & false <==> false
80 X & true <==> X
81 A4 (distributivity): X | (Y & Z) <==> (X | Y) & (X | Z)
82 X & (Y | Z) <==> (X & Y) | (X & Z)
83 A5 (complements): X | !X <==> true
84 X & !X <==> false
85 A6 (idempotence of |): X | X <==> X
86 A7 (idempotence of &): X & X <==> X
87
88 Also note that the range optimizer follows a relaxed boolean algebra
89 where the result may be bigger than boolean algebra rules dictate.
90 @See get_mm_tree() for explanation.
91 */
92
93 using my_testing::Server_initializer;
94
95 class OptRangeTest : public ::testing::Test
96 {
97 protected:
OptRangeTest()98 OptRangeTest() : m_opt_param(NULL) {}
99
SetUp()100 virtual void SetUp()
101 {
102 initializer.SetUp();
103 init_sql_alloc(PSI_NOT_INSTRUMENTED,
104 &m_alloc, thd()->variables.range_alloc_block_size, 0);
105 }
106
TearDown()107 virtual void TearDown()
108 {
109 delete m_opt_param;
110
111 initializer.TearDown();
112 free_root(&m_alloc, MYF(0));
113 }
114
thd()115 THD *thd() { return initializer.thd(); }
116
117 /**
118 Create a table with the requested number of fields. All fields are
119 indexed.
120
121 @param nbr_fields The number of fields in the table
122 */
create_table_singlecol_idx(int nbr_fields)123 void create_table_singlecol_idx(int nbr_fields)
124 {
125 create_table(nbr_fields);
126 for (int i= 0; i < nbr_fields; i++)
127 m_opt_param->add_key(m_opt_param->table->field[i]);
128 m_field= m_opt_param->table->field;
129 }
130
131 /**
132 Create a table with the requested number of fields without
133 creating indexes.
134
135 @param nbr_fields The number of fields in the table
136 */
create_table(int nbr_fields,bool columns_nullable)137 void create_table(int nbr_fields, bool columns_nullable)
138 {
139 m_opt_param=
140 new Fake_RANGE_OPT_PARAM(thd(), &m_alloc, nbr_fields, columns_nullable);
141 m_field= m_opt_param->table->field;
142 }
143
144
create_table(int nbr_fields)145 void create_table(int nbr_fields) { create_table(nbr_fields, false); }
146
147 /*
148 The new_item_xxx are convenience functions for creating Item_func
149 descendents from Field's and ints without having to wrap them in
150 Item's and resolving them.
151 */
new_item(Field * field,int value)152 template<typename T> T *new_item(Field *field, int value)
153 {
154 T *item= new T(new Item_field(field), new Item_int(value));
155 Item *item_base= item;
156 item->fix_fields(thd(), &item_base);
157 return item;
158 }
159
new_item_lt(Field * field,int value)160 Item_func_lt *new_item_lt(Field *field, int value)
161 {
162 return new_item<Item_func_lt>(field, value);
163 }
164
new_item_gt(Field * field,int value)165 Item_func_gt *new_item_gt(Field *field, int value)
166 {
167 return new_item<Item_func_gt>(field, value);
168 }
169
new_item_equal(Field * field,int value)170 Item_func_equal *new_item_equal(Field *field, int value)
171 {
172 return new_item<Item_func_equal>(field, value);
173 }
174
new_item_xor(Field * field,int value)175 Item_func_xor *new_item_xor(Field *field, int value)
176 {
177 return new_item<Item_func_xor>(field, value);
178 }
179
new_item_between(Field * fld,int val1,int val2)180 Item_cond_and *new_item_between(Field *fld, int val1, int val2)
181 {
182 return new Item_cond_and(new_item_gt(fld, val1), new_item_lt(fld, val2));
183 }
184
new_item_ne(Field * fld,int val1)185 Item_cond_or *new_item_ne(Field *fld, int val1)
186 {
187 return new Item_cond_or(new_item_lt(fld, val1), new_item_gt(fld, val1));
188 }
189
190 /**
191 Utility funtion used to simplify creation of SEL_TREEs with
192 specified range predicate operators and values. Also verifies that
193 the created SEL_TREE has the expected range conditions.
194
195 @param type The type of range predicate operator requested
196 @param fld The field used in the range predicate
197 @param val1 The first value used in the range predicate
198 @param val2 The second value used in the range predicate.
199 Only used for range predicates that takes two
200 values (BETWEEN).
201 @param expected_result The range conditions the created SEL_TREE
202 is expected to consist of. The format of this
203 string is what opt_range.cc print_tree() produces.
204
205 @return SEL_TREE that has been verified to have expected range conditions.
206 */
207 // Undefined at end of this file
208 #define create_tree(i, er) \
209 do_create_tree(i, er, TestFailLinePrinter(__LINE__))
do_create_tree(Item * item,const char * expected_result,TestFailLinePrinter called_from_line)210 SEL_TREE *do_create_tree(Item *item, const char* expected_result,
211 TestFailLinePrinter called_from_line)
212 {
213 SEL_TREE *result= get_mm_tree(m_opt_param, item);
214 SCOPED_TRACE(called_from_line);
215 check_tree_result(result, SEL_TREE::KEY, expected_result);
216 return result;
217 }
218
219 /**
220 Utility funtion used to simplify creation of func items used as
221 range predicates.
222
223 @param type The type of range predicate operator requested
224 @param fld The field used in the range predicate
225 @param val1 The value used in the range predicate
226
227 @return Item for the specified range predicate
228 */
229 Item_func *create_item(Item_func::Functype type, Field *fld, int value);
230
231 /**
232 Create instance of Xor Item_func.
233
234 @param item1 first item for xor condition.
235 @param item2 second item for xor condition.
236
237 @return pointer to newly created instance of Xor Item.
238 */
239 Item_func_xor *create_xor_item(Item *item1, Item *item2);
240
241
242 /**
243 Check that the use_count of all SEL_ARGs in the SEL_TREE are
244 correct.
245
246 @param tree The SEL_TREE to check
247 */
248 void check_use_count(SEL_TREE *tree);
249 /**
250 Verify that a SEL_TREE has the type and conditions we expect it to
251 have.
252
253 @param tree The SEL_TREE to check
254 @param expected_type The type 'tree' is expected to have
255 @param expected_result The range conditions 'tree' is expected
256 to consist of. The format of this string
257 is what opt_range.cc print_tree() produces.
258 */
259 void check_tree_result(SEL_TREE *tree,
260 const SEL_TREE::Type expected_type,
261 const char* expected_result);
262 /**
263 Perform OR between two SEL_TREEs and verify that the result of the
264 OR operation is as expected.
265
266 @param tree1 First SEL_TREE that will be ORed
267 @param tree2 Second SEL_TREE that will be ORed
268 @param expected_type The type the ORed result is expected to have
269 @param expected_result The range conditions the ORed result is expected
270 to consist of. The format of this string
271 is what opt_range.cc print_tree() produces.
272
273 @return SEL_TREE result of the OR operation between tree1 and
274 tree2 that has been verified to have expected range
275 conditions.
276 */
277 // Undefined at end of this file
278 #define create_and_check_tree_or(t1, t2, et, er) \
279 do_create_and_check_tree_or(t1, t2, et, er, TestFailLinePrinter(__LINE__))
280 SEL_TREE *do_create_and_check_tree_or(SEL_TREE *tree1, SEL_TREE *tree2,
281 const SEL_TREE::Type expected_type,
282 const char* expected_result,
283 TestFailLinePrinter called_from_line);
284 /**
285 Perform AND between two SEL_TREEs and verify that the result of the
286 AND operation is as expected.
287
288 @param tree1 First SEL_TREE that will be ANDed
289 @param tree2 Second SEL_TREE that will be ANDed
290 @param expected_type The type the ANDed result is expected to have
291 @param expected_result The range conditions the ANDed result is expected
292 to consist of. The format of this string
293 is what opt_range.cc print_tree() produces.
294
295 @return SEL_TREE result of the AND operation between tree1 and
296 tree2 that has been verified to have expected range
297 conditions.
298 */
299 // Undefined at end of this file
300 #define create_and_check_tree_and(t1, t2, et, er) \
301 do_create_and_check_tree_and(t1, t2, et, er, TestFailLinePrinter(__LINE__))
302 SEL_TREE *do_create_and_check_tree_and(SEL_TREE *tree1, SEL_TREE *tree2,
303 const SEL_TREE::Type expected_type,
304 const char* expected_result,
305 TestFailLinePrinter called_from_line);
306
307 Server_initializer initializer;
308 MEM_ROOT m_alloc;
309
310 Fake_RANGE_OPT_PARAM *m_opt_param;
311 /*
312 Pointer to m_opt_param->table->field. Only valid if the table was
313 created by calling one of OptRangeTest::create_table*()
314 */
315 Field **m_field;
316 };
317
create_item(Item_func::Functype type,Field * fld,int value)318 Item_func* OptRangeTest::create_item(Item_func::Functype type,
319 Field *fld, int value)
320 {
321 Item_func *result;
322 switch (type)
323 {
324 case Item_func::GT_FUNC:
325 result= new Item_func_gt(new Item_field(fld), new Item_int(value));
326 break;
327 case Item_func::LT_FUNC:
328 result= new Item_func_lt(new Item_field(fld), new Item_int(value));
329 break;
330 case Item_func::MULT_EQUAL_FUNC:
331 result= new Item_equal(new Item_int(value), new Item_field(fld));
332 break;
333 case Item_func::XOR_FUNC:
334 result= new Item_func_xor(new Item_field(fld), new Item_int(value));
335 break;
336 default:
337 result= NULL;
338 assert(false);
339 return result;
340 }
341 Item *itm= static_cast<Item*>(result);
342 result->fix_fields(thd(), &itm);
343 return result;
344 }
345
346 Item_func_xor*
create_xor_item(Item * item1,Item * item2)347 OptRangeTest::create_xor_item(Item *item1, Item *item2)
348 {
349 Item_func_xor *xor_item= new Item_func_xor(item1, item2);
350 Item *itm= static_cast<Item*>(xor_item);
351 xor_item->fix_fields(thd(), &itm);
352 return xor_item;
353 }
354
check_use_count(SEL_TREE * tree)355 void OptRangeTest::check_use_count(SEL_TREE *tree)
356 {
357 for (uint i= 0; i < m_opt_param->keys; i++)
358 {
359 SEL_ARG *cur_range= tree->keys[i];
360 if (cur_range != NULL)
361 {
362 EXPECT_FALSE(cur_range->test_use_count(cur_range));
363 }
364 }
365
366 if (!tree->merges.is_empty())
367 {
368 List_iterator<SEL_IMERGE> it(tree->merges);
369 SEL_IMERGE *merge= it++;
370
371 for (SEL_TREE** current= merge->trees;
372 current != merge->trees_next;
373 current++)
374 check_use_count(*current);
375 }
376 }
377
378
check_tree_result(SEL_TREE * tree,const SEL_TREE::Type expected_type,const char * expected_result)379 void OptRangeTest::check_tree_result(SEL_TREE *tree,
380 const SEL_TREE::Type expected_type,
381 const char* expected_result)
382 {
383 EXPECT_EQ(expected_type, tree->type);
384 if (expected_type != SEL_TREE::KEY)
385 return;
386
387 char buff[512];
388 String actual_result(buff, sizeof(buff), system_charset_info);
389 actual_result.set_charset(system_charset_info);
390 actual_result.length(0);
391 print_tree(&actual_result, "result", tree, m_opt_param, false);
392 EXPECT_STREQ(expected_result, actual_result.c_ptr());
393 SCOPED_TRACE("check_use_count");
394 check_use_count(tree);
395 }
396
397
398 SEL_TREE *
do_create_and_check_tree_or(SEL_TREE * tree1,SEL_TREE * tree2,const SEL_TREE::Type expected_type,const char * expected_result,TestFailLinePrinter called_from_line)399 OptRangeTest::do_create_and_check_tree_or(SEL_TREE *tree1, SEL_TREE *tree2,
400 const SEL_TREE::Type expected_type,
401 const char* expected_result,
402 TestFailLinePrinter called_from_line)
403 {
404 {
405 // Check that tree use counts are OK before OR'ing
406 SCOPED_TRACE(called_from_line);
407 check_use_count(tree1);
408 check_use_count(tree2);
409 }
410
411 SEL_TREE *result= tree_or(m_opt_param, tree1, tree2);
412
413 // Tree returned from tree_or()
414 SCOPED_TRACE(called_from_line);
415 check_tree_result(result, expected_type, expected_result);
416
417 return result;
418 }
419
420
421 SEL_TREE *
do_create_and_check_tree_and(SEL_TREE * tree1,SEL_TREE * tree2,const SEL_TREE::Type expected_type,const char * expected_result,TestFailLinePrinter called_from_line)422 OptRangeTest::do_create_and_check_tree_and(SEL_TREE *tree1, SEL_TREE *tree2,
423 const SEL_TREE::Type expected_type,
424 const char* expected_result,
425 TestFailLinePrinter called_from_line)
426 {
427 {
428 // Check that tree use counts are OK before AND'ing
429 SCOPED_TRACE(called_from_line);
430 check_use_count(tree1);
431 check_use_count(tree2);
432 }
433
434 SEL_TREE *result= tree_and(m_opt_param, tree1, tree2);
435
436 // Tree returned from tree_and()
437 SCOPED_TRACE(called_from_line);
438 check_tree_result(result, expected_type, expected_result);
439
440 return result;
441 }
442
443
444 /*
445 Experiment with these to measure performance of
446 'new (thd->mem_root)' Foo vs. 'new Foo'.
447 With gcc 4.4.2 I see ~4% difference (in optimized mode).
448 */
449 const int num_iterations= 10;
450 const int num_allocs= 10;
451
TEST_F(OptRangeTest,AllocateExplicit)452 TEST_F(OptRangeTest, AllocateExplicit)
453 {
454 for (int ix= 0; ix < num_iterations; ++ix)
455 {
456 free_root(thd()->mem_root, MYF(MY_KEEP_PREALLOC));
457 for (int ii= 0; ii < num_allocs; ++ii)
458 new (thd()->mem_root) SEL_ARG;
459 }
460 }
461
TEST_F(OptRangeTest,AllocateImplicit)462 TEST_F(OptRangeTest, AllocateImplicit)
463 {
464 for (int ix= 0; ix < num_iterations; ++ix)
465 {
466 free_root(thd()->mem_root, MYF(MY_KEEP_PREALLOC));
467 for (int ii= 0; ii < num_allocs; ++ii)
468 new SEL_ARG;
469 }
470 }
471
472 /*
473 We cannot do EXPECT_NE(NULL, get_mm_tree(...))
474 because of limits in google test.
475 */
476 const SEL_TREE *null_tree= NULL;
477 const SEL_ARG *null_arg= NULL;
478
479
print_selarg_ranges(String * s,SEL_ARG * sel_arg,const KEY_PART_INFO * kpi)480 static void print_selarg_ranges(String *s, SEL_ARG *sel_arg,
481 const KEY_PART_INFO *kpi)
482 {
483 for (SEL_ARG *cur= sel_arg->first();
484 cur != &null_element;
485 cur= cur->right)
486 {
487 String current_range;
488 append_range(¤t_range, kpi, cur->min_value, cur->max_value,
489 cur->min_flag | cur->max_flag);
490
491 if (s->length() > 0)
492 s->append(STRING_WITH_LEN("\n"));
493
494 s->append(current_range);
495 }
496 }
497
498
TEST_F(OptRangeTest,SimpleCond)499 TEST_F(OptRangeTest, SimpleCond)
500 {
501 Fake_RANGE_OPT_PARAM opt_param(thd(), &m_alloc, 0, false);
502 EXPECT_NE(null_tree, get_mm_tree(&opt_param, new Item_int(42)));
503 }
504
505
506 /*
507 Exercise range optimizer without adding indexes
508 */
TEST_F(OptRangeTest,EqualCondNoIndexes)509 TEST_F(OptRangeTest, EqualCondNoIndexes)
510 {
511 Fake_RANGE_OPT_PARAM opt_param(thd(), &m_alloc, 1, false);
512 SEL_TREE *tree=
513 get_mm_tree(&opt_param, new_item_equal(opt_param.table->field[0], 42));
514 EXPECT_EQ(null_tree, tree);
515 }
516
517
518 /*
519 Exercise range optimizer with xor operator.
520 */
TEST_F(OptRangeTest,XorCondIndexes)521 TEST_F(OptRangeTest, XorCondIndexes)
522 {
523 create_table(1);
524
525 m_opt_param->add_key(m_field[0]);
526 /*
527 XOR is not range optimizible ATM and is treated as
528 always true. No SEL_TREE is therefore expected.
529 */
530 SEL_TREE *tree= get_mm_tree(m_opt_param, new_item_xor(m_field[0], 42));
531 EXPECT_EQ(null_tree, tree);
532 }
533
534
535 /*
536 Exercise range optimizer with xor and different type of operator.
537 */
TEST_F(OptRangeTest,XorCondWithIndexes)538 TEST_F(OptRangeTest, XorCondWithIndexes)
539 {
540 create_table(5);
541
542 m_opt_param->add_key(m_field[0]);
543 m_opt_param->add_key(m_field[1]);
544 m_opt_param->add_key(m_field[2]);
545 m_opt_param->add_key(m_field[3]);
546 m_opt_param->add_key(m_field[4]);
547
548 /*
549 Create SEL_TREE from "field1=7 AND (field1 XOR 42)". Since XOR is
550 not range optimizible (treated as always true), we get a tree for
551 "field1=7" only.
552 */
553 const char expected1[]= "result keys[0]: (7 <= field_1 <= 7)\n";
554
555 SEL_TREE *tree=
556 get_mm_tree(m_opt_param,
557 new Item_cond_and (new_item_xor(m_field[0], 42),
558 new_item_equal(m_field[0],7)));
559 SCOPED_TRACE("");
560 check_tree_result(tree, SEL_TREE::KEY, expected1);
561
562 /*
563 Create SEL_TREE from "(field1 XOR 0) AND (field1>14)". Since XOR
564 is not range optimizible (treated as always true), we get a tree
565 for "field1>14" only.
566 */
567 const char expected2[]= "result keys[0]: (14 < field_1)\n";
568
569 tree= get_mm_tree(m_opt_param,
570 new Item_cond_and (new_item_xor(m_field[0], 0),
571 new_item_gt(m_field[0], 14)));
572 SCOPED_TRACE("");
573 check_tree_result(tree, SEL_TREE::KEY, expected2);
574
575 /*
576 Create SEL_TREE from "(field1<0 AND field1>14) XOR
577 (field1>17)". Since XOR is not range optimizible (treated as
578 always true), we get a NULL tree.
579 */
580 tree= get_mm_tree(m_opt_param,
581 create_xor_item(new Item_cond_and
582 (new_item_lt(m_field[0], 0),
583 new_item_gt(m_field[0], 14)),
584 new_item_gt(m_field[0], 17)));
585 SCOPED_TRACE("");
586 EXPECT_EQ(null_tree, tree);
587
588 /*
589 Create SEL_TREE from
590 (field1<0 AND field2>14) AND
591 ((field3<0 and field4>14) XOR field5>17) ".
592 Since XOR is not range optimizible (treated as always true),
593 we get a tree for "field1<0 AND field2>14" only.
594 */
595 const char expected3[]=
596 "result keys[0]: (field_1 < 0)\n"
597 "result keys[1]: (14 < field_2)\n";
598
599 tree= get_mm_tree(m_opt_param,
600 new Item_cond_and(
601 new Item_cond_and
602 (new_item_lt(m_field[0], 0),
603 new_item_gt(m_field[1], 14)),
604 create_xor_item(
605 new Item_cond_and
606 (new_item_lt(m_field[2], 0),
607 new_item_gt(m_field[3], 14)),
608 new_item_gt(m_field[4], 17))));
609 SCOPED_TRACE("");
610 check_tree_result(tree, SEL_TREE::KEY, expected3);
611 }
612
613
614 /*
615 Exercise range optimizer with single column index
616 */
TEST_F(OptRangeTest,GetMMTreeSingleColIndex)617 TEST_F(OptRangeTest, GetMMTreeSingleColIndex)
618 {
619 // Create a single-column table with index
620 create_table_singlecol_idx(1);
621
622 // Expected result of next test:
623 const char expected[]= "result keys[0]: (42 <= field_1 <= 42)\n";
624 create_tree(new_item_equal(m_field[0], 42), expected);
625
626 // Expected result of next test:
627 const char expected2[]=
628 "result keys[0]: (42 <= field_1 <= 42) OR (43 <= field_1 <= 43)\n";
629 SEL_TREE *tree=
630 get_mm_tree(m_opt_param, new Item_cond_or(new_item_equal(m_field[0], 42),
631 new_item_equal(m_field[0], 43)));
632
633 SCOPED_TRACE("");
634 check_tree_result(tree, SEL_TREE::KEY, expected2);
635
636 // Expected result of next test:
637 const char expected3[]=
638 "result keys[0]: "
639 "(1 <= field_1 <= 1) OR (2 <= field_1 <= 2) OR "
640 "(3 <= field_1 <= 3) OR (4 <= field_1 <= 4) OR "
641 "(5 <= field_1 <= 5) OR (6 <= field_1 <= 6) OR "
642 "(7 <= field_1 <= 7) OR (8 <= field_1 <= 8)\n";
643 List<Item> or_list1;
644 or_list1.push_back(new_item_equal(m_field[0], 1));
645 or_list1.push_back(new_item_equal(m_field[0], 2));
646 or_list1.push_back(new_item_equal(m_field[0], 3));
647 or_list1.push_back(new_item_equal(m_field[0], 4));
648 or_list1.push_back(new_item_equal(m_field[0], 5));
649 or_list1.push_back(new_item_equal(m_field[0], 6));
650 or_list1.push_back(new_item_equal(m_field[0], 7));
651 or_list1.push_back(new_item_equal(m_field[0], 8));
652
653 tree= get_mm_tree(m_opt_param, new Item_cond_or(or_list1));
654 check_tree_result(tree, SEL_TREE::KEY, expected3);
655
656 // Expected result of next test:
657 const char expected4[]= "result keys[0]: (7 <= field_1 <= 7)\n";
658 tree= get_mm_tree(m_opt_param,
659 new Item_cond_and (new Item_cond_or(or_list1),
660 new_item_equal(m_field[0], 7)));
661 SCOPED_TRACE("");
662 check_tree_result(tree, SEL_TREE::KEY, expected4);
663
664 // Expected result of next test:
665 const char expected5[]=
666 "result keys[0]: "
667 "(1 <= field_1 <= 1) OR (3 <= field_1 <= 3) OR "
668 "(5 <= field_1 <= 5) OR (7 <= field_1 <= 7)\n";
669 List<Item> or_list2;
670 or_list2.push_back(new_item_equal(m_field[0], 1));
671 or_list2.push_back(new_item_equal(m_field[0], 3));
672 or_list2.push_back(new_item_equal(m_field[0], 5));
673 or_list2.push_back(new_item_equal(m_field[0], 7));
674 or_list2.push_back(new_item_equal(m_field[0], 9));
675
676 tree= get_mm_tree(m_opt_param,
677 new Item_cond_and(new Item_cond_or(or_list1),
678 new Item_cond_or(or_list2)));
679 SCOPED_TRACE("");
680 check_tree_result(tree, SEL_TREE::KEY, expected5);
681 }
682
683
684 /*
685 Exercise range optimizer with multiple column index
686 */
TEST_F(OptRangeTest,GetMMTreeMultipleSingleColIndex)687 TEST_F(OptRangeTest, GetMMTreeMultipleSingleColIndex)
688 {
689 // Create a single-column table without index
690 create_table(1);
691
692 // Add two indexes covering the same field
693 m_opt_param->add_key(m_field[0]);
694 m_opt_param->add_key(m_field[0]);
695
696 char buff[512];
697 String range_string(buff, sizeof(buff), system_charset_info);
698 range_string.set_charset(system_charset_info);
699
700 // Expected result of next test:
701 const char expected[]=
702 "result keys[0]: (42 <= field_1 <= 42)\n"
703 "result keys[1]: (42 <= field_1 <= 42)\n";
704 create_tree(new_item_equal(m_field[0], 42), expected);
705 }
706
707
708 /*
709 Exercise range optimizer with multiple single column indexes
710 */
TEST_F(OptRangeTest,GetMMTreeOneTwoColIndex)711 TEST_F(OptRangeTest, GetMMTreeOneTwoColIndex)
712 {
713 create_table(2);
714
715 m_opt_param->add_key(m_field[0], m_field[1]);
716
717 char buff[512];
718 String range_string(buff, sizeof(buff), system_charset_info);
719 range_string.set_charset(system_charset_info);
720
721 // Expected result of next test:
722 const char expected[]= "result keys[0]: (42 <= field_1 <= 42)\n";
723 create_tree(new_item_equal(m_field[0], 42), expected);
724
725 // Expected result of next test:
726 const char expected2[]=
727 "result keys[0]: (42 <= field_1 <= 42 AND 10 <= field_2 <= 10)\n";
728 SEL_TREE *tree=
729 get_mm_tree(m_opt_param,
730 new Item_cond_and(new_item_equal(m_field[0], 42),
731 new_item_equal(m_field[1], 10)));
732
733 range_string.length(0);
734 print_tree(&range_string, "result",tree , m_opt_param, false);
735 EXPECT_STREQ(expected2, range_string.c_ptr());
736 }
737
738
739 /*
740 Optimizer tracing should only print ranges for applicable keyparts,
741 except when argument for print_tree() parameter 'print_full' is true.
742 */
TEST_F(OptRangeTest,GetMMTreeNonApplicableKeypart)743 TEST_F(OptRangeTest, GetMMTreeNonApplicableKeypart)
744 {
745 create_table(3);
746
747 List<Field> index_list;
748 index_list.push_back(m_field[0]);
749 index_list.push_back(m_field[1]);
750 index_list.push_back(m_field[2]);
751 m_opt_param->add_key(index_list);
752
753
754 char buff[512];
755 String range_string(buff, sizeof(buff), system_charset_info);
756 range_string.set_charset(system_charset_info);
757
758 /*
759 Expected result is range only on first keypart. Third keypart is
760 not applicable because there are no predicates on the second
761 keypart.
762 */
763 const char expected1[]=
764 "result keys[0]: (42 <= field_1 <= 42)\n";
765 SEL_TREE *tree=
766 get_mm_tree(m_opt_param,
767 new Item_cond_and (new_item_equal(m_field[0], 42),
768 new_item_equal(m_field[2], 10)));
769 range_string.length(0);
770 print_tree(&range_string, "result", tree , m_opt_param, false);
771 EXPECT_STREQ(expected1, range_string.c_ptr());
772
773 /*
774 Same SEL_ARG tree, but print_full argument is now true.
775 Non-applicable key parts are also printed in this case.
776 */
777 const char expected1_printfull[]=
778 "result keys[0]: (42 <= field_1 <= 42 AND 10 <= field_3 <= 10)\n";
779
780 range_string.length(0);
781 print_tree(&range_string, "result", tree , m_opt_param, true);
782 EXPECT_STREQ(expected1_printfull, range_string.c_ptr());
783
784 /*
785 Expected result is range only on first keypart. Second keypart is
786 not applicable because the predicate on the first keypart does not
787 use an equality operator.
788 */
789 const char expected2[]=
790 "result keys[0]: (field_1 < 42)\n";
791
792 tree=
793 get_mm_tree(m_opt_param,
794 new Item_cond_and
795 (new_item_lt(m_field[0], 42),
796 new_item_equal(m_field[1], 10)));
797
798 range_string.length(0);
799 print_tree(&range_string, "result", tree , m_opt_param, false);
800 EXPECT_STREQ(expected2, range_string.c_ptr());
801
802 /*
803 Same SEL_ARG tree, but print_full argument is now true.
804 Non-applicable key parts are also printed in this case.
805 */
806 const char expected2_printfull[]=
807 "result keys[0]: (field_1 < 42 AND 10 <= field_2 <= 10)\n";
808 range_string.length(0);
809 print_tree(&range_string, "result", tree , m_opt_param, true);
810 EXPECT_STREQ(expected2_printfull, range_string.c_ptr());
811 }
812
813
814 /*
815 Exercise range optimizer with three single column indexes
816 */
TEST_F(OptRangeTest,treeAndSingleColIndex1)817 TEST_F(OptRangeTest, treeAndSingleColIndex1)
818 {
819 create_table_singlecol_idx(3);
820
821 // Expected outputs
822 // Single-field range predicates
823 const char expected_fld1[]= "result keys[0]: (10 < field_1 < 13)\n";
824 const char expected_fld2_1[]= "result keys[1]: (field_2 < 11)\n";
825 const char expected_fld2_2[]= "result keys[1]: (8 < field_2)\n";
826 const char expected_fld3[]= "result keys[2]: (20 < field_3 < 30)\n";
827
828 /*
829 Expected result when performing AND of:
830 "(field_1 BETWEEN 10 AND 13) & (field_2 < 11)"
831 */
832 const char expected_and1[]=
833 "result keys[0]: (10 < field_1 < 13)\n"
834 "result keys[1]: (field_2 < 11)\n";
835
836 /*
837 Expected result when performing AND of:
838 "((field_1 BETWEEN 10 AND 13) & (field_2 < 11))
839 &
840 (field_3 BETWEEN 20 AND 30)"
841 */
842 const char expected_and2[]=
843 "result keys[0]: (10 < field_1 < 13)\n"
844 "result keys[1]: (field_2 < 11)\n"
845 "result keys[2]: (20 < field_3 < 30)\n";
846
847 /*
848 Expected result when performing AND of:
849 "((field_1 BETWEEN 10 AND 13) &
850 (field_2 < 11) &
851 (field_3 BETWEEN 20 AND 30)
852 )
853 &
854 field_2 > 8"
855 */
856 const char expected_and3[]=
857 "result keys[0]: (10 < field_1 < 13)\n"
858 "result keys[1]: (8 < field_2 < 11)\n" // <- notice lower bound
859 "result keys[2]: (20 < field_3 < 30)\n";
860
861 SEL_TREE *tree_and=
862 create_and_check_tree_and
863 (create_and_check_tree_and
864 (create_tree(new_item_between(m_field[0], 10, 13), expected_fld1),
865 create_tree(new_item_lt(m_field[1], 11), expected_fld2_1),
866 SEL_TREE::KEY, expected_and1),
867 create_tree(new_item_between(m_field[2], 20, 30), expected_fld3),
868 SEL_TREE::KEY, expected_and2
869 );
870
871 /*
872 Testing Axiom 7: AND'ing a predicate already part of a SEL_TREE
873 has no effect.
874 */
875 create_and_check_tree_and(
876 tree_and,
877 create_tree(new_item_between(m_field[2], 20, 30), expected_fld3),
878 SEL_TREE::KEY, expected_and2 // conditions did not change
879 );
880
881 create_and_check_tree_and(tree_and,
882 create_tree(new_item_gt(m_field[1], 8),
883 expected_fld2_2),
884 SEL_TREE::KEY, expected_and3
885 );
886
887 }
888
889
890 /*
891 Exercise range optimizer with three single column indexes
892 */
TEST_F(OptRangeTest,treeOrSingleColIndex1)893 TEST_F(OptRangeTest, treeOrSingleColIndex1)
894 {
895 create_table_singlecol_idx(3);
896
897 // Expected outputs
898 // Single-field range predicates
899 const char expected_fld1[]= "result keys[0]: (10 < field_1 < 13)\n";
900 const char expected_fld2_1[]= "result keys[1]: (field_2 < 11)\n";
901 const char expected_fld2_2[]= "result keys[1]: (8 < field_2)\n";
902 const char expected_fld3[]= "result keys[2]: (20 < field_3 < 30)\n";
903
904 /*
905 Expected result when performing OR of:
906 "(field_1 Item_func::BETWEEN 10 AND 13) | (field_2 < 11)"
907 */
908 const char expected_or1[]=
909 "result contains the following merges\n"
910 "--- alternative 1 ---\n"
911 " merge_tree keys[0]: (10 < field_1 < 13)\n"
912 " merge_tree keys[1]: (field_2 < 11)\n";
913
914 /*
915 Expected result when performing OR of:
916 "((field_1 BETWEEN 10 AND 13) | (field_2 < 11))
917 |
918 (field_3 BETWEEN 20 AND 30)"
919 */
920 const char expected_or2[]=
921 "result contains the following merges\n"
922 "--- alternative 1 ---\n"
923 " merge_tree keys[0]: (10 < field_1 < 13)\n"
924 " merge_tree keys[1]: (field_2 < 11)\n"
925 " merge_tree keys[2]: (20 < field_3 < 30)\n";
926
927 SEL_TREE *tree_or2=
928 create_and_check_tree_or(
929 create_and_check_tree_or(
930 create_tree(new_item_between(m_field[0], 10, 13), expected_fld1),
931 create_tree(new_item_lt(m_field[1], 11), expected_fld2_1),
932 SEL_TREE::KEY, expected_or1),
933 create_tree(new_item_between(m_field[2], 20, 30), expected_fld3),
934 SEL_TREE::KEY, expected_or2
935 );
936
937 /*
938 Testing Axiom 6: OR'ing a predicate already part of a SEL_TREE
939 has no effect.
940 */
941 SEL_TREE *tree_or3=
942 create_and_check_tree_or(
943 tree_or2,
944 create_tree(new_item_between(m_field[2], 20, 30), expected_fld3),
945 SEL_TREE::KEY, expected_or2
946 );
947
948 /*
949 Perform OR of:
950 "((field_1 BETWEEN 10 AND 13) |
951 (field_2 < 11) |
952 (field_3 BETWEEN 20 AND 30)
953 ) |
954 (field_2 > 8)"
955
956 This is always TRUE due to
957 (field_2 < 11) | (field_2 > 8) <==> true
958 */
959 create_and_check_tree_or(
960 tree_or3,
961 create_tree(new_item_gt(m_field[1], 8), expected_fld2_2),
962 SEL_TREE::ALWAYS, ""
963 );
964 }
965
966 /*
967 Exercise range optimizer with three single column indexes
968 */
TEST_F(OptRangeTest,treeAndOrComboSingleColIndex1)969 TEST_F(OptRangeTest, treeAndOrComboSingleColIndex1)
970 {
971 create_table_singlecol_idx(3);
972
973 // Expected outputs
974 // Single-field range predicates
975 const char exected_fld1[]= "result keys[0]: (10 < field_1 < 13)\n";
976 const char exected_fld2[]= "result keys[1]: (field_2 < 11)\n";
977 const char exected_fld3[]= "result keys[2]: (20 < field_3 < 30)\n";
978
979 // What "exected_fld1 & exected_fld2" should produce
980 const char expected_and[]=
981 "result keys[0]: (10 < field_1 < 13)\n"
982 "result keys[1]: (field_2 < 11)\n";
983
984 /*
985 What "(exected_fld1 & exected_fld2) | exected_fld3" should
986 produce.
987
988 By Axiom 4 (see above), we have that
989 X | (Y & Z) <==> (X | Y) & (X | Z)
990
991 Thus:
992
993 ((field_1 BETWEEN 10 AND 13) & field_2 < 11) |
994 (field_3 BETWEEN 20 AND 30)
995
996 <==> (Axiom 4)
997
998 (field_1 BETWEEN ... | field_3 BETWEEN ...) &
999 (field_2 < ... | field_3 BETWEEN ...)
1000
1001 But the result above is not created. Instead the following, which
1002 is incorrect (reads more rows than necessary), is the result:
1003
1004 (field_1 BETWEEN ... | field_2 < 11 | field_3 BETWEEN ...)
1005 */
1006 const char expected_incorrect_or[]=
1007 "result contains the following merges\n"
1008 "--- alternative 1 ---\n"
1009 " merge_tree keys[0]: (10 < field_1 < 13)\n"
1010 " merge_tree keys[1]: (field_2 < 11)\n"
1011 " merge_tree keys[2]: (20 < field_3 < 30)\n";
1012
1013 create_and_check_tree_or(
1014 create_and_check_tree_and(
1015 create_tree(new_item_between(m_field[0], 10, 13), exected_fld1),
1016 create_tree(new_item_lt(m_field[1], 11), exected_fld2),
1017 SEL_TREE::KEY, expected_and
1018 ),
1019 create_tree(new_item_between(m_field[2], 20, 30), exected_fld3),
1020 SEL_TREE::KEY, expected_incorrect_or
1021 );
1022 }
1023
1024 /**
1025 Test for BUG#16164031
1026 */
TEST_F(OptRangeTest,treeAndOrComboSingleColIndex2)1027 TEST_F(OptRangeTest, treeAndOrComboSingleColIndex2)
1028 {
1029 create_table_singlecol_idx(3);
1030
1031 // Single-index predicates
1032 const char exp_f2_eq1[]= "result keys[1]: (1 <= field_2 <= 1)\n";
1033 const char exp_f2_eq2[]= "result keys[1]: (2 <= field_2 <= 2)\n";
1034 const char exp_f3_eq[]= "result keys[2]: (1 <= field_3 <= 1)\n";
1035 const char exp_f1_lt1[]= "result keys[0]: (field_1 < 256)\n";
1036
1037 // OR1: Result of OR'ing f2_eq with f3_eq
1038 const char exp_or1[]=
1039 "result contains the following merges\n"
1040 "--- alternative 1 ---\n"
1041 " merge_tree keys[1]: (1 <= field_2 <= 1)\n"
1042 " merge_tree keys[2]: (1 <= field_3 <= 1)\n";
1043
1044 // OR2: Result of OR'ing f1_lt with f2_eq
1045 const char exp_or2[]=
1046 "result contains the following merges\n"
1047 "--- alternative 1 ---\n"
1048 " merge_tree keys[0]: (field_1 < 256)\n"
1049 " merge_tree keys[1]: (2 <= field_2 <= 2)\n";
1050
1051 // AND1: Result of "OR1 & OR2"
1052 const char exp_and1[]=
1053 "result contains the following merges\n"
1054 "--- alternative 1 ---\n"
1055 " merge_tree keys[1]: (1 <= field_2 <= 1)\n"
1056 " merge_tree keys[2]: (1 <= field_3 <= 1)\n\n"
1057 "--- alternative 2 ---\n"
1058 " merge_tree keys[0]: (field_1 < 256)\n"
1059 " merge_tree keys[1]: (2 <= field_2 <= 2)\n";
1060
1061 SEL_TREE *tree_and1=
1062 create_and_check_tree_and(
1063 create_and_check_tree_or(
1064 create_tree(new_item_equal(m_field[1], 1), exp_f2_eq1),
1065 create_tree(new_item_equal(m_field[2], 1), exp_f3_eq),
1066 SEL_TREE::KEY, exp_or1),
1067 create_and_check_tree_or(
1068 create_tree(new_item_lt(m_field[0], 256), exp_f1_lt1),
1069 create_tree(new_item_equal(m_field[1], 2), exp_f2_eq2),
1070 SEL_TREE::KEY, exp_or2),
1071 SEL_TREE::KEY, exp_and1
1072 );
1073
1074 // OR3: Result of "AND1 | field3 = 1"
1075 const char exp_or3[]=
1076 "result contains the following merges\n"
1077 "--- alternative 1 ---\n"
1078 " merge_tree keys[1]: (1 <= field_2 <= 1)\n"
1079 " merge_tree keys[2]: (1 <= field_3 <= 1)\n\n"
1080 "--- alternative 2 ---\n"
1081 " merge_tree keys[0]: (field_1 < 256)\n"
1082 " merge_tree keys[1]: (2 <= field_2 <= 2)\n"
1083 " merge_tree keys[2]: (1 <= field_3 <= 1)\n";
1084
1085 SEL_TREE *tree_or3=
1086 create_and_check_tree_or(
1087 tree_and1,
1088 create_tree(new_item_equal(m_field[2], 1), exp_f3_eq),
1089 SEL_TREE::KEY, exp_or3
1090 );
1091
1092 // More single-index predicates
1093 const char exp_f1_lt2[]= "result keys[0]: (field_1 < 35)\n";
1094 const char exp_f1_gt2[]= "result keys[0]: (257 < field_1)\n";
1095 const char exp_f1_or[]= "result keys[0]: (field_1 < 35) OR (257 < field_1)\n";
1096
1097 // OR4: Result of "OR3 | exp_f1_or"
1098 const char exp_or4[]=
1099 "result contains the following merges\n"
1100 "--- alternative 1 ---\n"
1101 " merge_tree keys[1]: (1 <= field_2 <= 1)\n"
1102 " merge_tree keys[2]: (1 <= field_3 <= 1)\n"
1103 " merge_tree keys[0]: (field_1 < 35) OR (257 < field_1)\n\n"
1104 "--- alternative 2 ---\n"
1105 " merge_tree keys[0]: (field_1 < 256) OR (257 < field_1)\n"
1106 " merge_tree keys[1]: (2 <= field_2 <= 2)\n"
1107 " merge_tree keys[2]: (1 <= field_3 <= 1)\n";
1108
1109 SEL_TREE *tree_or4=
1110 create_and_check_tree_or(
1111 tree_or3,
1112 create_and_check_tree_or(
1113 create_tree(new_item_lt(m_field[0], 35), exp_f1_lt2),
1114 create_tree(new_item_gt(m_field[0], 257), exp_f1_gt2),
1115 SEL_TREE::KEY, exp_f1_or
1116 ),
1117 SEL_TREE::KEY, exp_or4
1118 );
1119
1120 // More single-index predicates
1121 const char exp_f1_neq[]= "result keys[0]: (field_1 < 255) OR (255 < field_1)\n";
1122 const char exp_f2_eq3[]= "result keys[1]: (3 <= field_2 <= 3)\n";
1123
1124 // AND2: Result of ANDing these two ^
1125 const char exp_and2[]=
1126 "result keys[0]: (field_1 < 255) OR (255 < field_1)\n"
1127 "result keys[1]: (3 <= field_2 <= 3)\n";
1128
1129 // OR5: Result of "OR4 | AND3"
1130 /*
1131 "(field_1 < 255) OR (255 < field_1)" is lost when performing this
1132 OR. This results in a bigger set than correct boolean algebra
1133 rules dictate. @See note about relaxed boolean algebra in
1134 get_mm_tree().
1135 */
1136 const char exp_or5[]=
1137 "result contains the following merges\n"
1138 "--- alternative 1 ---\n"
1139 " merge_tree keys[1]: (1 <= field_2 <= 1) OR (3 <= field_2 <= 3)\n"
1140 " merge_tree keys[2]: (1 <= field_3 <= 1)\n"
1141 " merge_tree keys[0]: (field_1 < 35) OR (257 < field_1)\n";
1142
1143 create_and_check_tree_or(
1144 tree_or4,
1145 create_and_check_tree_and(
1146 create_tree(new_item_ne(m_field[0], 255), exp_f1_neq),
1147 create_tree(new_item_equal(m_field[1], 3), exp_f2_eq3),
1148 SEL_TREE::KEY, exp_and2),
1149 SEL_TREE::KEY, exp_or5
1150 );
1151 }
1152
1153
1154 /**
1155 Test for BUG#16241773
1156 */
TEST_F(OptRangeTest,treeAndOrComboSingleColIndex3)1157 TEST_F(OptRangeTest, treeAndOrComboSingleColIndex3)
1158 {
1159 create_table_singlecol_idx(2);
1160
1161 // Single-index predicates
1162 const char exp_f1_eq10[]= "result keys[0]: (10 <= field_1 <= 10)\n";
1163 const char exp_f2_gtr20[]= "result keys[1]: (20 < field_2)\n";
1164
1165 const char exp_f1_eq11[]= "result keys[0]: (11 <= field_1 <= 11)\n";
1166 const char exp_f2_gtr10[]= "result keys[1]: (10 < field_2)\n";
1167
1168 // OR1: Result of ORing f1_eq10 and f2_gtr20
1169 const char exp_or1[]=
1170 "result contains the following merges\n"
1171 "--- alternative 1 ---\n"
1172 " merge_tree keys[0]: (10 <= field_1 <= 10)\n"
1173 " merge_tree keys[1]: (20 < field_2)\n";
1174
1175 // OR2: Result of ORing f1_eq11 and f2_gtr10
1176 const char exp_or2[]=
1177 "result contains the following merges\n"
1178 "--- alternative 1 ---\n"
1179 " merge_tree keys[0]: (11 <= field_1 <= 11)\n"
1180 " merge_tree keys[1]: (10 < field_2)\n";
1181
1182 // AND1: Result of ANDing OR1 and OR2
1183 const char exp_and1[]=
1184 "result contains the following merges\n"
1185 "--- alternative 1 ---\n"
1186 " merge_tree keys[0]: (10 <= field_1 <= 10)\n"
1187 " merge_tree keys[1]: (20 < field_2)\n\n"
1188 "--- alternative 2 ---\n"
1189 " merge_tree keys[0]: (11 <= field_1 <= 11)\n"
1190 " merge_tree keys[1]: (10 < field_2)\n";
1191
1192 SEL_TREE *tree_and1=
1193 create_and_check_tree_and(
1194 create_and_check_tree_or(
1195 create_tree(new_item_equal(m_field[0], 10), exp_f1_eq10),
1196 create_tree(new_item_gt(m_field[1], 20), exp_f2_gtr20),
1197 SEL_TREE::KEY, exp_or1),
1198 create_and_check_tree_or(
1199 create_tree(new_item_equal(m_field[0], 11), exp_f1_eq11),
1200 create_tree(new_item_gt(m_field[1], 10), exp_f2_gtr10),
1201 SEL_TREE::KEY, exp_or2),
1202 SEL_TREE::KEY, exp_and1
1203 );
1204
1205 const char exp_f2_eq5[]= "result keys[1]: (5 <= field_2 <= 5)\n";
1206 // OR3: Result of OR'ing AND1 with f2_eq5
1207 const char exp_or3[]=
1208 "result contains the following merges\n"
1209 "--- alternative 1 ---\n"
1210 " merge_tree keys[0]: (10 <= field_1 <= 10)\n"
1211 " merge_tree keys[1]: (5 <= field_2 <= 5) OR (20 < field_2)\n\n"
1212 "--- alternative 2 ---\n"
1213 " merge_tree keys[0]: (11 <= field_1 <= 11)\n"
1214 " merge_tree keys[1]: (5 <= field_2 <= 5) OR (10 < field_2)\n";
1215 SEL_TREE *tree_or3=
1216 create_and_check_tree_or(
1217 tree_and1,
1218 create_tree(new_item_equal(m_field[1], 5), exp_f2_eq5),
1219 SEL_TREE::KEY, exp_or3
1220 );
1221
1222 const char exp_f2_lt2[]= "result keys[1]: (field_2 < 2)\n";
1223 // OR4: Result of OR'ing OR3 with f2_lt2
1224 const char exp_or4[]=
1225 "result contains the following merges\n"
1226 "--- alternative 1 ---\n"
1227 " merge_tree keys[0]: (10 <= field_1 <= 10)\n"
1228 " merge_tree keys[1]: (field_2 < 2) OR "
1229 "(5 <= field_2 <= 5) OR (20 < field_2)\n\n"
1230 "--- alternative 2 ---\n"
1231 " merge_tree keys[0]: (11 <= field_1 <= 11)\n"
1232 " merge_tree keys[1]: (field_2 < 2) OR "
1233 "(5 <= field_2 <= 5) OR (10 < field_2)\n";
1234
1235 create_and_check_tree_or(
1236 tree_or3,
1237 create_tree(new_item_lt(m_field[1], 2), exp_f2_lt2),
1238 SEL_TREE::KEY, exp_or4
1239 );
1240 }
1241
1242
1243 /*
1244 Create SelArg with various single valued predicate
1245 */
TEST_F(OptRangeTest,SelArgOnevalue)1246 TEST_F(OptRangeTest, SelArgOnevalue)
1247 {
1248 Fake_TABLE fake_table(new Item_int(7));
1249 Field *field_long7= fake_table.field[0];
1250
1251 KEY_PART_INFO kpi;
1252 kpi.init_from_field(field_long7);
1253
1254 uchar range_val7[Fake_TABLE::DEFAULT_PACK_LENGTH];
1255 field_long7->get_key_image(range_val7, kpi.length, Field::itRAW);
1256
1257 SEL_ARG sel_arg7(field_long7, range_val7, range_val7);
1258 String range_string;
1259 print_selarg_ranges(&range_string, &sel_arg7, &kpi);
1260 const char expected[]= "7 <= field_1 <= 7";
1261 EXPECT_STREQ(expected, range_string.c_ptr());
1262
1263 sel_arg7.min_flag|= NO_MIN_RANGE;
1264 range_string.length(0);
1265 print_selarg_ranges(&range_string, &sel_arg7, &kpi);
1266 const char expected2[]= "field_1 <= 7";
1267 EXPECT_STREQ(expected2, range_string.c_ptr());
1268
1269 sel_arg7.max_flag= NEAR_MAX;
1270 range_string.length(0);
1271 print_selarg_ranges(&range_string, &sel_arg7, &kpi);
1272 const char expected3[]= "field_1 < 7";
1273 EXPECT_STREQ(expected3, range_string.c_ptr());
1274
1275 sel_arg7.min_flag= NEAR_MIN;
1276 sel_arg7.max_flag= NO_MAX_RANGE;
1277 range_string.length(0);
1278 print_selarg_ranges(&range_string, &sel_arg7, &kpi);
1279 const char expected4[]= "7 < field_1";
1280 EXPECT_STREQ(expected4, range_string.c_ptr());
1281
1282 sel_arg7.min_flag= 0;
1283 range_string.length(0);
1284 print_selarg_ranges(&range_string, &sel_arg7, &kpi);
1285 const char expected5[]= "7 <= field_1";
1286 EXPECT_STREQ(expected5, range_string.c_ptr());
1287 }
1288
1289
1290 /*
1291 Create SelArg with a between predicate
1292 */
TEST_F(OptRangeTest,SelArgBetween)1293 TEST_F(OptRangeTest, SelArgBetween)
1294 {
1295 Fake_TABLE fake_table(new Item_int(3), new Item_int(5));
1296 Field *field_long3= fake_table.field[0];
1297 Field *field_long5= fake_table.field[1];
1298
1299 KEY_PART_INFO kpi;
1300 kpi.init_from_field(field_long3);
1301
1302 uchar range_val3[Fake_TABLE::DEFAULT_PACK_LENGTH];
1303 field_long3->get_key_image(range_val3, kpi.length, Field::itRAW);
1304
1305 uchar range_val5[Fake_TABLE::DEFAULT_PACK_LENGTH];
1306 field_long5->get_key_image(range_val5, kpi.length, Field::itRAW);
1307
1308 SEL_ARG sel_arg35(field_long3, range_val3, range_val5);
1309
1310 String range_string;
1311 print_selarg_ranges(&range_string, &sel_arg35, &kpi);
1312 const char expected[]= "3 <= field_1 <= 5";
1313 EXPECT_STREQ(expected, range_string.c_ptr());
1314
1315 range_string.length(0);
1316 sel_arg35.min_flag= NEAR_MIN;
1317 print_selarg_ranges(&range_string, &sel_arg35, &kpi);
1318 const char expected2[]= "3 < field_1 <= 5";
1319 EXPECT_STREQ(expected2, range_string.c_ptr());
1320
1321 range_string.length(0);
1322 sel_arg35.max_flag= NEAR_MAX;
1323 print_selarg_ranges(&range_string, &sel_arg35, &kpi);
1324 const char expected3[]= "3 < field_1 < 5";
1325 EXPECT_STREQ(expected3, range_string.c_ptr());
1326
1327 range_string.length(0);
1328 sel_arg35.min_flag= 0;
1329 print_selarg_ranges(&range_string, &sel_arg35, &kpi);
1330 const char expected4[]= "3 <= field_1 < 5";
1331 EXPECT_STREQ(expected4, range_string.c_ptr());
1332
1333 range_string.length(0);
1334 sel_arg35.min_flag= NO_MIN_RANGE;
1335 sel_arg35.max_flag= 0;
1336 print_selarg_ranges(&range_string, &sel_arg35, &kpi);
1337 const char expected5[]= "field_1 <= 5";
1338 EXPECT_STREQ(expected5, range_string.c_ptr());
1339
1340 range_string.length(0);
1341 sel_arg35.min_flag= 0;
1342 sel_arg35.max_flag= NO_MAX_RANGE;
1343 print_selarg_ranges(&range_string, &sel_arg35, &kpi);
1344 const char expected6[]= "3 <= field_1";
1345 EXPECT_STREQ(expected6, range_string.c_ptr());
1346 }
1347
1348 /*
1349 Test SelArg::CopyMax
1350 */
TEST_F(OptRangeTest,CopyMax)1351 TEST_F(OptRangeTest, CopyMax)
1352 {
1353 Fake_TABLE fake_table(new Item_int(3), new Item_int(5));
1354 Field *field_long3= fake_table.field[0];
1355 Field *field_long5= fake_table.field[1];
1356
1357 KEY_PART_INFO kpi;
1358 kpi.init_from_field(field_long3);
1359
1360 uchar range_val3[Fake_TABLE::DEFAULT_PACK_LENGTH];
1361 field_long3->get_key_image(range_val3, kpi.length, Field::itRAW);
1362
1363 uchar range_val5[Fake_TABLE::DEFAULT_PACK_LENGTH];
1364 field_long5->get_key_image(range_val5, kpi.length, Field::itRAW);
1365
1366 SEL_ARG sel_arg3(field_long3, range_val3, range_val3);
1367 sel_arg3.min_flag= NO_MIN_RANGE;
1368 SEL_ARG sel_arg5(field_long5, range_val5, range_val5);
1369 sel_arg5.min_flag= NO_MIN_RANGE;
1370
1371 String range_string;
1372 print_selarg_ranges(&range_string, &sel_arg3, &kpi);
1373 const char expected[]= "field_1 <= 3";
1374 EXPECT_STREQ(expected, range_string.c_ptr());
1375
1376 range_string.length(0);
1377 print_selarg_ranges(&range_string, &sel_arg5, &kpi);
1378 const char expected2[]= "field_1 <= 5";
1379 EXPECT_STREQ(expected2, range_string.c_ptr());
1380
1381 /*
1382 Ranges now:
1383 -inf ----------------3-5----------- +inf
1384 sel_arg3: [-------------------->
1385 sel_arg5: [---------------------->
1386 Below: merge these two ranges into sel_arg3 using copy_max()
1387 */
1388 bool full_range= sel_arg3.copy_max(&sel_arg5);
1389 // The merged range does not cover all possible values
1390 EXPECT_FALSE(full_range);
1391
1392 range_string.length(0);
1393 print_selarg_ranges(&range_string, &sel_arg3, &kpi);
1394 const char expected3[]= "field_1 <= 5";
1395 EXPECT_STREQ(expected3, range_string.c_ptr());
1396
1397 range_string.length(0);
1398 sel_arg5.min_flag= 0;
1399 sel_arg5.max_flag= NO_MAX_RANGE;
1400 print_selarg_ranges(&range_string, &sel_arg5, &kpi);
1401 const char expected4[]= "5 <= field_1";
1402 EXPECT_STREQ(expected4, range_string.c_ptr());
1403
1404 /*
1405 Ranges now:
1406 -inf ----------------3-5----------- +inf
1407 sel_arg3: [---------------------->
1408 sel_arg5: <---------------]
1409 Below: merge these two ranges into sel_arg3 using copy_max()
1410 */
1411
1412 full_range= sel_arg3.copy_max(&sel_arg5);
1413 // The new range covers all possible values
1414 EXPECT_TRUE(full_range);
1415
1416 range_string.length(0);
1417 print_selarg_ranges(&range_string, &sel_arg3, &kpi);
1418 const char expected5[]= "field_1";
1419 EXPECT_STREQ(expected5, range_string.c_ptr());
1420 }
1421
1422 /*
1423 Test SelArg::CopyMin
1424 */
TEST_F(OptRangeTest,CopyMin)1425 TEST_F(OptRangeTest, CopyMin)
1426 {
1427 Fake_TABLE fake_table(new Item_int(3), new Item_int(5));
1428 Field *field_long3= fake_table.field[0];
1429 Field *field_long5= fake_table.field[1];
1430
1431 KEY_PART_INFO kpi;
1432 kpi.init_from_field(field_long3);
1433
1434 uchar range_val3[Fake_TABLE::DEFAULT_PACK_LENGTH];
1435 field_long3->get_key_image(range_val3, kpi.length, Field::itRAW);
1436
1437 uchar range_val5[Fake_TABLE::DEFAULT_PACK_LENGTH];
1438 field_long5->get_key_image(range_val5, kpi.length, Field::itRAW);
1439
1440 SEL_ARG sel_arg3(field_long3, range_val3, range_val3);
1441 sel_arg3.max_flag= NO_MAX_RANGE;
1442 SEL_ARG sel_arg5(field_long5, range_val5, range_val5);
1443 sel_arg5.max_flag= NO_MAX_RANGE;
1444
1445 String range_string;
1446 print_selarg_ranges(&range_string, &sel_arg3, &kpi);
1447 const char expected[]= "3 <= field_1";
1448 EXPECT_STREQ(expected, range_string.c_ptr());
1449
1450 range_string.length(0);
1451 print_selarg_ranges(&range_string, &sel_arg5, &kpi);
1452 const char expected2[]= "5 <= field_1";
1453 EXPECT_STREQ(expected2, range_string.c_ptr());
1454
1455 /*
1456 Ranges now:
1457 -inf ----------------3-5----------- +inf
1458 sel_arg3: <-----------------]
1459 sel_arg5: <---------------]
1460 Below: merge these two ranges into sel_arg3 using copy_max()
1461 */
1462 bool full_range= sel_arg5.copy_min(&sel_arg3);
1463 // The merged range does not cover all possible values
1464 EXPECT_FALSE(full_range);
1465
1466 range_string.length(0);
1467 print_selarg_ranges(&range_string, &sel_arg5, &kpi);
1468 const char expected3[]= "3 <= field_1";
1469 EXPECT_STREQ(expected3, range_string.c_ptr());
1470
1471 range_string.length(0);
1472 sel_arg3.max_flag= 0;
1473 sel_arg3.min_flag= NO_MIN_RANGE;
1474 print_selarg_ranges(&range_string, &sel_arg3, &kpi);
1475 const char expected4[]= "field_1 <= 3";
1476 EXPECT_STREQ(expected4, range_string.c_ptr());
1477
1478 /*
1479 Ranges now:
1480 -inf ----------------3-5----------- +inf
1481 sel_arg3: [-------------------->
1482 sel_arg5: <-----------------]
1483 Below: merge these two ranges into sel_arg5 using copy_min()
1484 */
1485
1486 full_range= sel_arg5.copy_min(&sel_arg3);
1487 // The new range covers all possible values
1488 EXPECT_TRUE(full_range);
1489
1490 range_string.length(0);
1491 print_selarg_ranges(&range_string, &sel_arg5, &kpi);
1492 const char expected5[]= "field_1";
1493 EXPECT_STREQ(expected5, range_string.c_ptr());
1494 }
1495
1496
1497 /*
1498 Test SelArg::KeyOr
1499 */
TEST_F(OptRangeTest,KeyOr1)1500 TEST_F(OptRangeTest, KeyOr1)
1501 {
1502 Fake_RANGE_OPT_PARAM opt_param(thd(), &m_alloc, 0, false);
1503
1504 Fake_TABLE fake_table(new Item_int(3), new Item_int(4));
1505 Field *field_long3= fake_table.field[0];
1506 Field *field_long4= fake_table.field[1];
1507
1508 KEY_PART_INFO kpi;
1509 kpi.init_from_field(field_long3);
1510
1511 uchar range_val3[Fake_TABLE::DEFAULT_PACK_LENGTH];
1512 field_long3->get_key_image(range_val3, kpi.length, Field::itRAW);
1513
1514 uchar range_val4[Fake_TABLE::DEFAULT_PACK_LENGTH];
1515 field_long4->get_key_image(range_val4, kpi.length, Field::itRAW);
1516
1517 SEL_ARG sel_arg_lt3(field_long3, range_val3, range_val3);
1518 sel_arg_lt3.part= 0;
1519 sel_arg_lt3.min_flag= NO_MIN_RANGE;
1520 sel_arg_lt3.max_flag= NEAR_MAX;
1521
1522 SEL_ARG sel_arg_gt3(field_long3, range_val3, range_val3);
1523 sel_arg_gt3.part= 0;
1524 sel_arg_gt3.min_flag= NEAR_MIN;
1525 sel_arg_gt3.max_flag= NO_MAX_RANGE;
1526
1527 SEL_ARG sel_arg_lt4(field_long4, range_val4, range_val4);
1528 sel_arg_lt4.part= 0;
1529 sel_arg_lt4.min_flag= NO_MIN_RANGE;
1530 sel_arg_lt4.max_flag= NEAR_MAX;
1531
1532 String range_string;
1533 print_selarg_ranges(&range_string, &sel_arg_lt3, &kpi);
1534 const char expected_lt3[]= "field_1 < 3";
1535 EXPECT_STREQ(expected_lt3, range_string.c_ptr());
1536
1537 range_string.length(0);
1538 print_selarg_ranges(&range_string, &sel_arg_gt3, &kpi);
1539 const char expected_gt3[]= "3 < field_1";
1540 EXPECT_STREQ(expected_gt3, range_string.c_ptr());
1541
1542 range_string.length(0);
1543 print_selarg_ranges(&range_string, &sel_arg_lt4, &kpi);
1544 const char expected_lt4[]= "field_1 < 4";
1545 EXPECT_STREQ(expected_lt4, range_string.c_ptr());
1546
1547
1548 /*
1549 Ranges now:
1550 -inf ----------------34----------- +inf
1551 sel_arg_lt3: [-------------------->
1552 sel_arg_gt3: <---------------]
1553 sel_arg_lt4: [--------------------->
1554 */
1555
1556 SEL_ARG *tmp= key_or(&opt_param, &sel_arg_lt3, &sel_arg_gt3);
1557
1558 /*
1559 Ranges now:
1560 -inf ----------------34----------- +inf
1561 tmp: [--------------------><---------------]
1562 sel_arg_lt4: [--------------------->
1563 */
1564 range_string.length(0);
1565 print_selarg_ranges(&range_string, tmp, &kpi);
1566 const char expected_merged[]=
1567 "field_1 < 3\n"
1568 "3 < field_1";
1569 EXPECT_STREQ(expected_merged, range_string.c_ptr());
1570
1571 SEL_ARG *tmp2= key_or(&opt_param, tmp, &sel_arg_lt4);
1572 EXPECT_EQ(null_arg, tmp2);
1573 }
1574
1575 /*
1576 Test SelArg::KeyOr (BUG#17619119)
1577 */
TEST_F(OptRangeTest,KeyOr2)1578 TEST_F(OptRangeTest, KeyOr2)
1579 {
1580 create_table(2);
1581
1582 m_opt_param->add_key(m_field[1]);
1583 m_opt_param->add_key(m_field[0], m_field[1]);
1584
1585 SEL_TREE *fld1_20= create_tree(new_item_equal(m_field[0], 20),
1586 "result keys[1]: (20 <= field_1 <= 20)\n");
1587
1588 /*
1589 Expected result when performing AND of:
1590 "(field_1 = 20) TREE_AND (field_2 = 1)"
1591 */
1592 SEL_TREE *tree_and1=
1593 create_and_check_tree_and(
1594 fld1_20,
1595 create_tree(new_item_equal(m_field[1], 1),
1596 "result keys[0]: (1 <= field_2 <= 1)\n" // range idx #1
1597 "result keys[1]: (1 <= field_2 <= 1)\n"), // range idx #2
1598 SEL_TREE::KEY,
1599 "result keys[0]: (1 <= field_2 <= 1)\n" // idx #1
1600 "result keys[1]: (20 <= field_1 <= 20 AND 1 <= field_2 <= 1)\n" // idx #2
1601 );
1602
1603 /*
1604 Expected result when performing AND of:
1605 "(field_1 = 4) TREE_AND (field_2 = 42)"
1606 */
1607 SEL_TREE *tree_and2=
1608 create_and_check_tree_and(
1609 create_tree(new_item_equal(m_field[0], 4),
1610 "result keys[1]: (4 <= field_1 <= 4)\n"),
1611 create_tree(new_item_equal(m_field[1], 42),
1612 "result keys[0]: (42 <= field_2 <= 42)\n" // range idx #1
1613 "result keys[1]: (42 <= field_2 <= 42)\n"), // range idx #2
1614 SEL_TREE::KEY,
1615 "result keys[0]: (42 <= field_2 <= 42)\n" // idx #1
1616 "result keys[1]: (4 <= field_1 <= 4 AND 42 <= field_2 <= 42)\n" // idx #2
1617 );
1618
1619 /*
1620 Expected result when performing OR of:
1621 "((field_1 = 20) AND (field_2 = 1))
1622 TREE_OR
1623 ((field_1 = 4) AND (field_2 = 42))"
1624 */
1625 SEL_TREE *tree_or1=
1626 create_and_check_tree_or(
1627 tree_and1,
1628 tree_and2,
1629 SEL_TREE::KEY,
1630 "result keys[0]: (1 <= field_2 <= 1) OR (42 <= field_2 <= 42)\n"
1631 "result keys[1]: "
1632 "(4 <= field_1 <= 4 AND 42 <= field_2 <= 42) OR "
1633 "(20 <= field_1 <= 20 AND 1 <= field_2 <= 1)\n"
1634 );
1635
1636 /*
1637 Expected result when performing OR of:
1638 "(field_1 > 13) TREE_OR (field_2 = 14)"
1639
1640 NOTE: if m_opt_param->remove_jump_scans was 'false', the merge
1641 would contain another alternative with this range as well:
1642 " merge_tree keys[1]: (14 <= field_2 <= 14)\n";
1643 */
1644 SEL_TREE *tree_or2=
1645 create_and_check_tree_or(
1646 create_tree(new_item_gt(m_field[0], 13),
1647 "result keys[1]: (13 < field_1)\n"),
1648 create_tree(new_item_equal(m_field[1], 14),
1649 "result keys[0]: (14 <= field_2 <= 14)\n" // range idx #1
1650 "result keys[1]: (14 <= field_2 <= 14)\n"), // range idx #2
1651 SEL_TREE::KEY,
1652 "result contains the following merges\n"
1653 "--- alternative 1 ---\n"
1654 " merge_tree keys[1]: (13 < field_1)\n"
1655 " merge_tree keys[0]: (14 <= field_2 <= 14)\n"
1656 );
1657
1658 /*
1659 Expected result when performing OR of:
1660 ((field_1 = 4) AND (field_2 = 42)) OR ((field_1 = 20) AND (field_2 = 1))
1661 TREE_OR
1662 ((field_1 > 13) OR (field_2 = 14)) <- merge
1663
1664 "field_1=20 AND field_2=1" from the first tree is removed by
1665 key_or() since it is covered by "field_1 > 13" from the second tree.
1666 */
1667 const char exp_or3[]=
1668 "result contains the following merges\n"
1669 "--- alternative 1 ---\n"
1670 " merge_tree keys[1]: (4 <= field_1 <= 4 AND 42 <= field_2 <= 42) OR "
1671 "(13 < field_1)\n"
1672 " merge_tree keys[0]: (14 <= field_2 <= 14)\n";
1673 create_and_check_tree_or(tree_or1, tree_or2, SEL_TREE::KEY, exp_or3);
1674
1675 /*
1676 fld1_20 was modified to reflect the AND in tree_and1 (and these
1677 trees are the same). They are no longer used, as reflected by
1678 use_count=0
1679 */
1680 EXPECT_EQ(fld1_20, tree_and1);
1681 EXPECT_EQ(0UL, fld1_20->keys[0]->use_count);
1682 EXPECT_EQ(null_arg, fld1_20->keys[0]->next_key_part);
1683
1684 EXPECT_EQ(0UL, fld1_20->keys[1]->use_count);
1685 EXPECT_NE(null_arg, fld1_20->keys[1]->next_key_part);
1686 EXPECT_EQ(0UL, fld1_20->keys[1]->next_key_part->use_count);
1687 }
1688
1689 class Mock_SEL_ARG : public SEL_ARG
1690 {
1691 private:
1692 ulong m_expected_use_count;
1693 public:
Mock_SEL_ARG(SEL_ARG * next_key_part_ptr,int use_count_arg)1694 Mock_SEL_ARG(SEL_ARG *next_key_part_ptr,
1695 int use_count_arg)
1696 :m_expected_use_count(use_count_arg)
1697 {
1698 next_key_part= next_key_part_ptr;
1699 make_root();
1700 }
1701
Mock_SEL_ARG(Type type_arg,int initial_use_count,int expected_use_count)1702 Mock_SEL_ARG(Type type_arg, int initial_use_count, int expected_use_count)
1703 : m_expected_use_count(expected_use_count)
1704 {
1705 make_root();
1706 type= type_arg;
1707 part= 1;
1708 left= NULL;
1709 use_count= initial_use_count;
1710 min_flag= 0;
1711 }
1712
1713 // Verify that use_count is as expected on destruction
~Mock_SEL_ARG()1714 ~Mock_SEL_ARG()
1715 {
1716 EXPECT_EQ (m_expected_use_count, use_count);
1717 }
1718 };
1719
1720
1721 /**
1722 @todo
1723 - Move some place it can be reused
1724 - Use varargs instead of copy-paste.
1725 */
new_Item_row(int a,int b)1726 Item_row *new_Item_row(int a, int b)
1727 {
1728 /*
1729 The Item_row CTOR doesn't store the reference to the list, hence
1730 it can live on the stack.
1731 */
1732 List<Item> items;
1733 items.push_front(new Item_int(b));
1734 return new Item_row(POS(), new Item_int(a), items);
1735 }
1736
1737
new_Item_row(int a,int b,int c)1738 Item_row *new_Item_row(int a, int b, int c)
1739 {
1740 /*
1741 The Item_row CTOR doesn't store the reference to the list, hence
1742 it can live on the stack.
1743 */
1744 List<Item> items;
1745 items.push_front(new Item_int(c));
1746 items.push_front(new Item_int(b));
1747 return new Item_row(POS(), new Item_int(a), items);
1748 }
1749
1750
1751 /// @todo Move some place it can be reused.
new_Item_row(Field ** fields,int count)1752 Item_row *new_Item_row(Field **fields, int count)
1753 {
1754 /*
1755 The Item_row CTOR doesn't store the reference to the list, hence
1756 it can live on the stack.
1757 */
1758 List<Item> items;
1759 for (int i= count - 1; i > 0; --i)
1760 items.push_front(new Item_field(fields[i]));
1761 return new Item_row(POS(), new Item_field(fields[0]), items);
1762 }
1763
1764
TEST_F(OptRangeTest,RowConstructorIn2)1765 TEST_F(OptRangeTest, RowConstructorIn2)
1766 {
1767 create_table(2);
1768
1769 m_opt_param->add_key();
1770
1771 // We build the expression (field_1, field_2) IN ((3, 4), (1, 2)) ...
1772 PT_item_list *all_args=
1773 new (current_thd->mem_root) PT_item_list;
1774 all_args->push_front(new_Item_row(1, 2));
1775 all_args->push_front(new_Item_row(3, 4));
1776 all_args->push_front(new_Item_row(m_opt_param->table->field, 2));
1777 Item *cond= new Item_func_in(POS(), all_args, false);
1778 Parse_context pc(thd(), thd()->lex->current_select());
1779 EXPECT_FALSE(cond->itemize(&pc, &cond));
1780
1781 // ... and resolve it.
1782 Item *item= cond;
1783 cond->fix_fields(thd(), &item);
1784
1785 SEL_TREE *sel_tree= get_mm_tree(m_opt_param, cond);
1786
1787 EXPECT_FALSE(sel_tree == NULL);
1788 EXPECT_EQ(key_map(1), sel_tree->keys_map);
1789
1790 const char *expected=
1791 "result keys[0]: "
1792 "(1 <= field_1 <= 1 AND 2 <= field_2 <= 2) OR "
1793 "(3 <= field_1 <= 3 AND 4 <= field_2 <= 4)\n";
1794 check_tree_result(sel_tree, SEL_TREE::KEY, expected);
1795 }
1796
1797
TEST_F(OptRangeTest,RowConstructorIn3)1798 TEST_F(OptRangeTest, RowConstructorIn3)
1799 {
1800 create_table(3);
1801
1802 m_opt_param->add_key();
1803
1804 // We build the expression (field_1, field_2) IN ((3, 4), (1, 2)) ...
1805 PT_item_list *all_args=
1806 new (current_thd->mem_root) PT_item_list;
1807 all_args->push_front(new_Item_row(1, 2, 3));
1808 all_args->push_front(new_Item_row(4, 5, 6));
1809 all_args->push_front(new_Item_row(m_opt_param->table->field, 3));
1810 Item *cond= new Item_func_in(POS(), all_args, false);
1811 Parse_context pc(thd(), thd()->lex->current_select());
1812 EXPECT_FALSE(cond->itemize(&pc, &cond));
1813
1814 // ... and resolve it.
1815 Item *item= cond;
1816 cond->fix_fields(thd(), &item);
1817
1818 SEL_TREE *sel_tree= get_mm_tree(m_opt_param, cond);
1819
1820 EXPECT_FALSE(sel_tree == NULL);
1821 EXPECT_EQ(key_map(1), sel_tree->keys_map);
1822
1823 const char *expected=
1824 "result keys[0]: "
1825 "(1 <= field_1 <= 1 AND 2 <= field_2 <= 2 AND 3 <= field_3 <= 3) OR "
1826 "(4 <= field_1 <= 4 AND 5 <= field_2 <= 5 AND 6 <= field_3 <= 6)\n";
1827
1828 check_tree_result(sel_tree, SEL_TREE::KEY, expected);
1829 }
1830
1831 /*
1832 Sets up a simplified tree to represent the interval list. The result
1833 is not a proper RB-tree: on the "left" side of 'root', only 'left'
1834 and 'parent' pointers are used, and on the "right" side of 'root'
1835 only 'right' and 'parent' pointers are used. In addition, the nodes
1836 are connected via 'next' linked list pointers.
1837
1838 This is sufficient for SEL_ARG's first() / last() /
1839 increment_use_count() functions to work.
1840
1841 The root node of the tree will not change by calling this function.
1842
1843 @param root The root of the tree that 'other' will be added to
1844 @param other SEL_ARG that will be added to the tree.
1845
1846 @note While it's perfectly fine for 'root' to be a tree of SEL_ARGs,
1847 'other' can currently only be a single SEL_ARG (i.e., it cannot
1848 refer to any other SEL_ARGs through next/prev/left/right)
1849 */
1850
build_interval_list(Mock_SEL_ARG * root,Mock_SEL_ARG * other)1851 void build_interval_list(Mock_SEL_ARG *root, Mock_SEL_ARG *other)
1852 {
1853 /*
1854 Keep the tree balanced by adding nodes to left and right of
1855 'root' in an alternating fashion
1856 */
1857 if (root->elements % 2)
1858 {
1859 SEL_ARG *add_to= root->first();
1860 add_to->left= other;
1861 other->next= add_to;
1862 other->parent= add_to;
1863 }
1864 else
1865 {
1866 SEL_ARG *add_to= root->last();
1867 add_to->next= other;
1868 add_to->right= other;
1869 other->parent= add_to;
1870 }
1871
1872 root->elements++;
1873 }
1874
1875
TEST_F(OptRangeTest,IncrementUseCount)1876 TEST_F(OptRangeTest, IncrementUseCount)
1877 {
1878 /*
1879 We build the following SEL_ARG graph, corresponding to the condition
1880 (kp11 = c AND (kp12 = c OR kp22 = c) AND kp3 = c) OR
1881 (kp12 = c AND (kp12 = c OR kp22 = c) AND kp3 = c)
1882
1883 [kp11*]---[kp21*]---[kp3*]
1884 | / | /
1885 [kp12]---/ [kp22]--/
1886
1887 Vertical lines = next/prev pointers
1888 Horizontal lines = next_key_part pointers
1889 * indicates that the SEL_ARG is root
1890 */
1891 Mock_SEL_ARG kp3(NULL, 4);
1892
1893 Mock_SEL_ARG kp21(&kp3, 2);
1894 Mock_SEL_ARG kp22(&kp3, 0);
1895 build_interval_list(&kp21, &kp22);
1896
1897 Mock_SEL_ARG kp11(&kp21, 0);
1898 Mock_SEL_ARG kp12(&kp21, 0);
1899 build_interval_list(&kp11, &kp12);
1900
1901 /*
1902 At this point, no one refers to this SEL_ARG graph, so the
1903 use_count is 0 for all roots. Below we check that
1904 increment_use_count() correctly updates use_count for the whole
1905 tree. The actual test that use_count is as expected is performed
1906 in ~Mock_SEL_ARG.
1907 */
1908 kp11.increment_use_count(1);
1909 }
1910
1911
TEST_F(OptRangeTest,IncrementUseCount2)1912 TEST_F(OptRangeTest, IncrementUseCount2)
1913 {
1914 /*
1915 We build the following SEL_ARG graph, corresponding to the condition
1916 (kp11 = c AND kp2 = c AND (kp31 = c OR kp32 = c)) OR
1917 (kp12 = c AND kp2 = c AND (kp31 = c OR kp32 = c))
1918
1919 [kp11*]---[kp2*]---[kp31*]
1920 | / |
1921 [kp12]---/ [kp32]
1922
1923 Vertical lines = next/prev pointers
1924 Horizontal lines = next_key_part pointers
1925 * indicates that the SEL_ARG is root
1926 */
1927
1928 Mock_SEL_ARG kp31(NULL, 2);
1929 Mock_SEL_ARG kp32(NULL, 0);
1930 build_interval_list(&kp31, &kp32);
1931
1932 Mock_SEL_ARG kp2(&kp31, 2);
1933
1934 Mock_SEL_ARG kp11(&kp2, 0);
1935 Mock_SEL_ARG kp12(&kp2, 0);
1936 build_interval_list(&kp11, &kp12);
1937
1938 /*
1939 At this point, no one refers to this SEL_ARG graph, so the
1940 use_count is 0 for all roots. Below we check that
1941 increment_use_count() correctly updates use_count for the whole
1942 tree. The actual test that use_count is as expected is performed
1943 in ~Mock_SEL_ARG.
1944
1945 */
1946 kp11.increment_use_count(1);
1947 }
1948
TEST_F(OptRangeTest,CombineAlways)1949 TEST_F(OptRangeTest, CombineAlways)
1950 {
1951 // Gets decremented in key_or() before being compared > 0, triggering
1952 // a assert in SEL_ARG::SEL_ARG(Type) unless the ALWAYS type is
1953 // handled.
1954 static const int INITIAL_USE_COUNT= 3;
1955
1956 RANGE_OPT_PARAM param; // Not really used
1957 {
1958 Mock_SEL_ARG always(SEL_ARG::ALWAYS, INITIAL_USE_COUNT, INITIAL_USE_COUNT),
1959 key_range(SEL_ARG::KEY_RANGE, INITIAL_USE_COUNT, INITIAL_USE_COUNT - 1);
1960 EXPECT_TRUE(key_or(¶m, &always, &key_range) == &always);
1961 }
1962 {
1963 Mock_SEL_ARG always(SEL_ARG::ALWAYS, INITIAL_USE_COUNT, INITIAL_USE_COUNT),
1964 key_range(SEL_ARG::KEY_RANGE, INITIAL_USE_COUNT, INITIAL_USE_COUNT - 1);
1965 EXPECT_TRUE(key_or(¶m, &key_range, &always) == &always);
1966 }
1967 {
1968 Mock_SEL_ARG always1(SEL_ARG::ALWAYS, INITIAL_USE_COUNT, INITIAL_USE_COUNT),
1969 always2(SEL_ARG::KEY_RANGE, INITIAL_USE_COUNT, INITIAL_USE_COUNT - 1);
1970 EXPECT_TRUE(key_or(¶m, &always1, &always2) == &always1);
1971 }
1972 {
1973 Mock_SEL_ARG always(SEL_ARG::ALWAYS, INITIAL_USE_COUNT, INITIAL_USE_COUNT),
1974 key_range(SEL_ARG::KEY_RANGE, INITIAL_USE_COUNT, INITIAL_USE_COUNT);
1975 EXPECT_TRUE(key_and(¶m, &key_range, &always, 0) == &key_range);
1976 }
1977 {
1978 Mock_SEL_ARG always(SEL_ARG::ALWAYS, INITIAL_USE_COUNT, INITIAL_USE_COUNT),
1979 key_range(SEL_ARG::KEY_RANGE, INITIAL_USE_COUNT, INITIAL_USE_COUNT);
1980 EXPECT_TRUE(key_and(¶m, &always, &key_range, 0) == &key_range);
1981 }
1982 }
1983
TEST_F(OptRangeTest,CombineAlways2)1984 TEST_F(OptRangeTest, CombineAlways2)
1985 {
1986 class Fake_sel_arg : public SEL_ARG
1987 {
1988 public:
1989 Fake_sel_arg(Type type_arg)
1990 {
1991 type= type_arg;
1992 part= 0;
1993 left= NULL;
1994 next= NULL;
1995 min_flag= max_flag= 0;
1996 set_endpoints(1, 2);
1997 next_key_part= NULL;
1998 make_root();
1999 // Gets decremented in key_or() before being compared > 0, triggering
2000 // a assert in SEL_ARG::SEL_ARG(Type) unless the ALWAYS type is
2001 // handled.
2002 use_count= 3;
2003 }
2004
2005 void add_next_key_part(SEL_ARG *next)
2006 {
2007 next_key_part= next;
2008 next->part= part + 1;
2009 }
2010 private:
2011 void set_endpoints(int min, int max)
2012 {
2013 set_endpoint(min, min_value_buff, &min_value);
2014 set_endpoint(max, max_value_buff, &max_value);
2015 }
2016 void set_endpoint(int value, char *buff, uchar **variable)
2017 {
2018 buff[0]= value;
2019 buff[1]= 0;
2020 *variable= reinterpret_cast<uchar*>(buff);
2021 }
2022 char min_value_buff[10], max_value_buff[10];
2023 };
2024
2025 class Fake_key_part_info : public KEY_PART_INFO
2026 {
2027 public:
2028 Fake_key_part_info(Mock_field_long *field_arg)
2029 {
2030 field= field_arg;
2031 length= 1;
2032 }
2033 };
2034
2035 RANGE_OPT_PARAM param;
2036 Fake_sel_arg always(SEL_ARG::ALWAYS), key_range(SEL_ARG::KEY_RANGE),
2037 other(SEL_ARG::KEY_RANGE);
2038 Mock_field_long field1("col_1");
2039 Mock_field_long field2("col_2");
2040 Fake_TABLE table(&field1, &field2);
2041 String res(1000), so_far(1000);
2042 Fake_key_part_info key_part_info[]= { Fake_key_part_info(&field1),
2043 Fake_key_part_info(&field2) };
2044
2045 always.add_next_key_part(&key_range);
2046 append_range_all_keyparts(NULL, &res, &so_far, &always, key_part_info,true);
2047
2048 // Let's make sure we built the expression we expected ...
2049 EXPECT_STREQ("(1 <= col_1 <= 2 AND 1 <= col_2 <= 2)", res.ptr());
2050
2051 EXPECT_TRUE(key_or(¶m, &always, &other) == &always);
2052 EXPECT_EQ((ulong) 2, other.use_count);
2053 EXPECT_EQ((ulong) 3, always.use_count);
2054 }
2055
TEST_F(OptRangeTest,AppendRange)2056 TEST_F(OptRangeTest, AppendRange)
2057 {
2058 String out(100);
2059 Mock_field_long field("my_field");
2060 Fake_TABLE table(&field);
2061 KEY_PART_INFO kp;
2062 kp.field= &field;
2063 kp.length= 1;
2064 uchar value= 42;
2065 append_range(&out, &kp, &value, &value, NEAR_MIN | NEAR_MAX);
2066 EXPECT_STREQ("42 < my_field < 42", out.c_ptr());
2067 }
2068
2069 }
2070
2071 #undef create_tree
2072 #undef create_and_check_tree_and
2073 #undef create_and_check_tree_or
2074