【GreatSQL优化器-07】mm tree
【GreatSQL优化器-07】mm tree一、mm tree介绍
GreatSQL 的优化器主要用 mm tree 也就是 min-max tree 来确定条件的范围，然后根据不同索引的范围值来计算 cost，选取 cost 最小的索引来执行SQL。
下面用一个简单的例子来说明 mm tree 是什么。
greatsql> CREATE TABLE t1 (c1 INT PRIMARY KEY, c2 INT,date1 DATETIME);
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');
greatsql> CREATE TABLE t2 (cc1 INT PRIMARY KEY, cc2 INT);
greatsql> INSERT INTO t2 VALUES (1,3),(2,1),(3,2),(4,3),(5,15);
greatsql> CREATE TABLE t3 (ccc1 INT, ccc2 varchar(100));
greatsql> INSERT INTO t3 VALUES (1,'aa1'),(2,'bb1'),(3,'cc1'),(4,'dd1'),(null,'ee');
greatsql> CREATE INDEX idx1 ON t1(c2);
greatsql> CREATE INDEX idx2 ON t1(c2,date1);
greatsql> CREATE INDEX idx2_1 ON t2(cc2);
greatsql> CREATE INDEX idx3_1 ON t3(ccc1);
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);
"analyzing_range_alternatives": {
"range_scan_alternatives": [
{
"index": "idx1",
"ranges": [ # 这里面就是一个mm tree二叉树结果
"NULL < c2 < 6",
"6 <= c2 < 10",
"10 < c2 < 15"
],
"index_dives_for_eq_ranges": true,
"rowid_ordered": false,
"using_mrr": false,
"index_only": false,
"in_memory": 1,
"rows": 5,
"cost": 8.51,
"chosen": false,
"cause": "cost"
},
{
"index": "idx2",
"ranges": [ # 这里面就是一个mm tree二叉树结果
"NULL < c2 < 6",
"6 <= c2 < 10",
"10 < c2 < 15"
],
"index_dives_for_eq_ranges": true, # 用范围扫描来估计cost，这个涉及到index dives，下一期讲
"rowid_ordered": false,
"using_mrr": false,
"index_only": true,
"in_memory": 1,
"rows": 5, # 这里的意思是在 c2<15 范围内有5条记录
"cost": 0.761828,
"chosen": true
}
],
"analyzing_roworder_intersect": {
"usable": false,
"cause": "too_few_roworder_scans"
}
},
"chosen_range_access_summary": {
"range_access_plan": {
"type": "range_scan",
"index": "idx2",
"rows": 5,
"ranges": [
"NULL < c2 < 6",
"6 <= c2 < 10",
"10 < c2 < 15"
]
},
"rows_for_plan": 5,
"cost_for_plan": 0.761828,
"chosen": true
}
}
}
]
},最后生成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的红黑二叉树结构：
# 代码流程：make_join_plan --> estimate_rowcount --> get_quick_record_count --> test_quick_select
int test_quick_select() {
RANGE_OPT_PARAM param;
# 找出所有sql条件涉及的索引
if (setup_range_optimizer_param(thd, return_mem_root, temp_mem_root,
keys_to_use, table, query_block, ¶m)) {
return 0;
}
# 有condition条件的话，执行以下函数
get_mm_tree();
if(tree) {
# 用下面的函数来计算索引和范围对应的cost，这个下一期讲
get_key_scans_params();
}
}
SEL_TREE *get_mm_tree(THD *thd, RANGE_OPT_PARAM *param, table_map prev_tables,
table_map read_tables, table_map current_table,
bool remove_jump_scans, Item *cond) {
# 1、如果是Item::COND_ITEM的话，遍历所有参数
for (Item &item : *down_cast<Item_cond *>(cond)->argument_list()) {
get_mm_tree();
如果是and条件，tree = tree_and()
如果是OR条件，tree = tree_or()
}
# 2、如果非条件Item，见下表一
switch (cond_func->functype()) {
case Item_func::BETWEEN:
case Item_func::IN_FUNC:
case Item_func::MULT_EQUAL_FUNC:
default:
}
}相关注释怎么看，解释一下：
parent 黑
/ \
当前SEL_ARG 当前SEL_ARG红
/ \ / \
leftright 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的比较结果
Item type举例cmp结果操作cur_key2(10
页:
[1]