【GreatSQL优化器-07】mm tree

【GreatSQL优化器-07】mm tree

一、mm tree介绍

GreatSQL 的优化器主要用 mm tree 也就是 min-max tree 来确定条件的范围，然后根据不同索引的范围值来计算 cost，选取 cost 最小的索引来实行SQL。
下面用一个简朴的例子来说明 mm tree 是什么。

1. greatsql> CREATE TABLE t1 (c1 INT PRIMARY KEY, c2 INT,date1 DATETIME);
2. greatsql> INSERT INTO t1 VALUES (1,10,'2021-03-25 16:44:00.123456'),(2,1,'2022-03-26 16:44:00.123456'),(3,4,'2023-03-27 16:44:00.123456'),(5,5,'2024-03-25 16:44:00.123456'),(7,null,'2020-03-25 16:44:00.123456'),(8,10,'2020-10-25 16:44:00.123456'),(11,16,'2023-03-25 16:44:00.123456');
3. greatsql> CREATE TABLE t2 (cc1 INT PRIMARY KEY, cc2 INT);
4. greatsql> INSERT INTO t2 VALUES (1,3),(2,1),(3,2),(4,3),(5,15);
5. greatsql> CREATE TABLE t3 (ccc1 INT, ccc2 varchar(100));
6. greatsql> INSERT INTO t3 VALUES (1,'aa1'),(2,'bb1'),(3,'cc1'),(4,'dd1'),(null,'ee');
7. greatsql> CREATE INDEX idx1 ON t1(c2);
8. greatsql> CREATE INDEX idx2 ON t1(c2,date1);
9. greatsql> CREATE INDEX idx2_1 ON t2(cc2);
10. greatsql> CREATE INDEX idx3_1 ON t3(ccc1);
12. greatsql> EXPLAIN SELECT * FROM t1 WHERE (c1=1 AND c2<10) OR (c2<6 AND date1 < '2023-03-27 16:44:00.123456') OR (c2>10 and c2<15 AND c1>0);
13.                   "analyzing_range_alternatives": {
14.                     "range_scan_alternatives": [
15.                       {
16.                         "index": "idx1",
17.                         "ranges": [ # 这里面就是一个mm tree二叉树结果
18.                           "NULL < c2 < 6",
19.                           "6 <= c2 < 10",
20.                           "10 < c2 < 15"
21.                         ],
22.                         "index_dives_for_eq_ranges": true,
23.                         "rowid_ordered": false,
24.                         "using_mrr": false,
25.                         "index_only": false,
26.                         "in_memory": 1,
27.                         "rows": 5,
28.                         "cost": 8.51,
29.                         "chosen": false,
30.                         "cause": "cost"
31.                       },
32.                       {
33.                         "index": "idx2",
34.                         "ranges": [ # 这里面就是一个mm tree二叉树结果
35.                           "NULL < c2 < 6",
36.                           "6 <= c2 < 10",
37.                           "10 < c2 < 15"
38.                         ],
39.                         "index_dives_for_eq_ranges": true, # 用范围扫描来估计cost，这个涉及到index dives，下一期讲
40.                         "rowid_ordered": false,
41.                         "using_mrr": false,
42.                         "index_only": true,
43.                         "in_memory": 1,
44.                         "rows": 5, # 这里的意思是在 c2<15 范围内有5条记录
45.                         "cost": 0.761828,
46.                         "chosen": true
47.                       }
48.                     ],
49.                     "analyzing_roworder_intersect": {
50.                       "usable": false,
51.                       "cause": "too_few_roworder_scans"
52.                     }
53.                   },
54.                   "chosen_range_access_summary": {
55.                     "range_access_plan": {
56.                       "type": "range_scan",
57.                       "index": "idx2",
58.                       "rows": 5,
59.                       "ranges": [
60.                         "NULL < c2 < 6",
61.                         "6 <= c2 < 10",
62.                         "10 < c2 < 15"
63.                       ]
64.                     },
65.                     "rows_for_plan": 5,
66.                     "cost_for_plan": 0.761828,
67.                     "chosen": true
68.                   }
69.                 }
70.               }
71.             ]
72.           },

复制代码

末了生成SEL_TREE，根据索引数量包含对应的SEL_ROOT，SEL_ROOT包含最小单元SEL_ARG，一个SEL_ARG就是一段范围，用key_range_flags来计算范围，见表二 SEL_ARG一组对象合成一个SEL_ROOT的图结构，内部通过SEL_ARG::next/prev来关联同一个索引列条件"OR"，通过next_key_part来关联不同索引列条件的"AND" tree_or操作涉及的比较函数见表三，表四。
原则就是把2个不同的范围进行比较按照结果进行合并操作，涉及的范围拼接因为太多不展开细讲，具体看函数tree.cc tree_or会对两个不同条件组的共同列做key_or处置惩罚，生成这个交集列的范围二叉树。即对不同or条件出现次数最多的列做查找范围操作。留意，如果末了某个索引的范围是全覆盖的话是不会生成这个索引的mm tree的。
SEL_ARG的红黑二叉树结构：

1. # 代码流程：make_join_plan --> estimate_rowcount --> get_quick_record_count --> test_quick_select
3. int test_quick_select() {
4.   RANGE_OPT_PARAM param;
5.   # 找出所有sql条件涉及的索引
6.   if (setup_range_optimizer_param(thd, return_mem_root, temp_mem_root,
7.                                   keys_to_use, table, query_block, &param)) {
8.     return 0;
9.   }
10.   # 有condition条件的话，执行以下函数
11.   get_mm_tree();
12.   if(tree) {
13.     # 用下面的函数来计算索引和范围对应的cost，这个下一期讲
14.     get_key_scans_params();
15.   }
16. }
18. SEL_TREE *get_mm_tree(THD *thd, RANGE_OPT_PARAM *param, table_map prev_tables,
19.                       table_map read_tables, table_map current_table,
20.                       bool remove_jump_scans, Item *cond) {
21. # 1、如果是Item::COND_ITEM的话，遍历所有参数
22.   for (Item &item : *down_cast<Item_cond *>(cond)->argument_list()) {
23.     get_mm_tree();
24.     如果是and条件，tree = tree_and()
25.     如果是OR条件，tree = tree_or()
26.   }
27. # 2、如果非条件Item，见下表一
28.   switch (cond_func->functype()) {
29.     case Item_func::BETWEEN:
30.     case Item_func::IN_FUNC:
31.     case Item_func::MULT_EQUAL_FUNC:
32.     default:
33.   }
34. }

复制代码

相关注释怎么看，表明一下：

1.               parent    黑
2.             /       \
3.     当前SEL_ARG    当前SEL_ARG  红
4.     /    \           /    \
5.   left  right     left    right  黑

复制代码

表一，Item_func对应的TREE操作
Item typeopItem_func::COND_AND_FUNCtree_andItem_func::COND_OR_FUNCtree_orItem_func::BETWEENnot between : tree_or between : tree_andItem_func::IN_FUNCnot in : tree_or in : tree_andItem_func::MULT_EQUAL_FUNCtree_andItem_func::NE_FUNCtree_or表二，SEL_ARG的key_range_flags
typeNO_MIN_RANGEfrom -infNO_MAX_RANGEto +infNEAR_MINX < keyNEAR_MAXX > keyUNIQUE_RANGEAND(keypart_i = const_i)，唯一索引，所有const_i非NULLEQ_RANGEAND(keypart_i = const_i)，所有const_i非空NULL_RANGEAND(keypart_i = const_i)，唯一索引，至少一个const_i为NULLGEOM_FLAGrtree index，使用ha_rkey_function::HA_READ_MBR_XXXSKIP_RANGE只用在NDB引擎SKIP_RECORDS_IN_RANGE可以跳过index divesDESC_FLAG索引是DESC倒序的表三，key_or的cmp_max_to_min的比较结果
[table][tr]Item type举例cmp结果操作[/tr][tr][td]cur_key2[/td][td](10