【GreatSQL优化器-10】find_best_ref

一、find_best_ref介绍

GreatSQL的优化器对于join的表需要根据行数和cost来确定最后哪张表先执行哪张表后执行，这里面就涉及到预估满足条件的表数据，在keyuse_array数组有值的情况下，会用find_best_ref函数来通过索引进行cost和rows的估计，并且会找出最优的索引。这样就可能不会继续用后面的calculate_scan_cost()进行全表扫描计算cost，可以节省查询时间。

这个功能是对之前【优化器05-条件过滤】的补充功能，二者有可能一起用，也有可能只选择一种计算，要看具体条件。

下面用一个简单的例子来说明find_best_ref函数获得的结果。

 CREATE TABLE t1 (c1 INT PRIMARY KEY, c2 INT,date1 DATETIME); 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'); CREATE TABLE t2 (cc1 INT PRIMARY KEY, cc2 INT); INSERT INTO t2 VALUES (1,3),(2,1),(3,2),(4,3),(5,15); CREATE TABLE t3 (ccc1 INT, ccc2 varchar(100)); INSERT INTO t3 VALUES (1,'aa1'),(2,'bb1'),(3,'cc1'),(4,'dd1'),(null,'ee'); CREATE INDEX idx1 ON t1(c2); CREATE INDEX idx2 ON t1(c2,date1); CREATE INDEX idx2_1 ON t2(cc2); CREATE INDEX idx3_1 ON t3(ccc1); greatsql> SELECT * FROM t1 join t2 ON t1.c1=t2.cc1 and t1.c2<5; { "ref_optimizer_key_uses": [ 首先这里要有keyuse_array { "table": "`t1`", "field": "c1", "equals": "`t2`.`cc1`", "null_rejecting": true }, { "table": "`t2`", "field": "cc1", "equals": "`t1`.`c1`", "null_rejecting": true } ] }, "considered_execution_plans": [ { "plan_prefix": [ ], "table": "`t1`", "best_access_path": { "considered_access_paths": [ { "access_type": "ref", "index": "PRIMARY", "usable": false, "chosen": false }, { "rows_to_scan": 2, "filtering_effect": [ ], "final_filtering_effect": 1, "access_type": "range", "range_details": { "used_index": "idx2" }, "resulting_rows": 2, "cost": 0.660457, "chosen": true } ] }, "condition_filtering_pct": 100, "rows_for_plan": 2, "cost_for_plan": 0.660457, "rest_of_plan": [ { "plan_prefix": [ "`t1`" ], "table": "`t2`", "best_access_path": { "considered_access_paths": [ { "access_type": "eq_ref", "index": "PRIMARY", "rows": 1, 这里就是通过find_best_ref()获得的结果 "cost": 0.7, 这里就是通过find_best_ref()获得的结果 "chosen": true, "cause": "clustered_pk_chosen_by_heuristics" }, { "access_type": "scan", "chosen": false, "cause": "covering_index_better_than_full_scan" } ] }, "condition_filtering_pct": 100, "rows_for_plan": 2, "cost_for_plan": 1.36046, "chosen": true } ] }, { "plan_prefix": [ ], "table": "`t2`", "best_access_path": { "considered_access_paths": [ { "access_type": "ref", "index": "PRIMARY", "usable": false, "chosen": false }, { "rows_to_scan": 5, "filtering_effect": [ ], "final_filtering_effect": 1, "access_type": "scan", "resulting_rows": 5, "cost": 0.75, "chosen": true } ] }, "condition_filtering_pct": 100, "rows_for_plan": 5, "cost_for_plan": 0.75, "rest_of_plan": [ { "plan_prefix": [ "`t2`" ], "table": "`t1`", "best_access_path": { "considered_access_paths": [ { "access_type": "eq_ref", "index": "PRIMARY", "rows": 1, 这里就是通过find_best_ref()获得的结果 "cost": 5.5, 这里就是通过find_best_ref()获得的结果 "chosen": true, "cause": "clustered_pk_chosen_by_heuristics" }, { "rows_to_scan": 2, "filtering_effect": [ ], "final_filtering_effect": 1, "access_type": "range", "range_details": { "used_index": "idx2" }, "resulting_rows": 2, "cost": 3.30229, "chosen": true } ] }, "condition_filtering_pct": 100, "rows_for_plan": 10, "cost_for_plan": 4.05229, "pruned_by_cost": true } ] } ]

二、find_best_ref代码解释

find_best_ref的计算在best_access_path函数实现，用来在keyuse_array数组有值的时候，预估不同join连接时候的join表的读取行数和可能的cost，以及找出cost最低的索引。

 void Optimize_table_order::best_access_path(JOIN_TAB *tab, const table_map remaining_tables, const uint idx, bool disable_jbuf, const double prefix_rowcount, POSITION *pos) { if (tab->keyuse() != nullptr && (table->file->ha_table_flags() & HA_NO_INDEX_ACCESS) == 0 && (!table->set_counter())) best_ref = find_best_ref(tab, remaining_tables, idx, prefix_rowcount, &found_condition, &ref_depend_map, &used_key_parts); 接着会进行一系列判断来决定是否要继续用calculate_scan_cost()方式来进行估计cost，然后二者进行比较选取更小的cost。 具体见下面<<采用的rows和cost结果>>表 两个方式都会使用calculate_condition_filter()计算条件过滤百分比。 } Key_use *Optimize_table_order::find_best_ref() { ha_rows distinct_keys_est = tab->records() / MATCHING_ROWS_IN_OTHER_TABLE; // 遍历keyuse_array数组，按照索引进行计算行数和cost，选取最优的索引 for (Key_use *keyuse = tab->keyuse(); keyuse->table_ref == tab->table_ref;) { 如果是第一张表就跳过，因为第一张表不需要用索引扫描。 主要计算得出下面<<find_best_ref函数获得的结果>>表里的三个变量结果，用于找出最优索引。 } }

表：采用的rows和cost结果

采用的rows和cost结果	场景(以下任一个条件满足)
find_best_ref()的结果	find_best_ref()方式找到的行数和cost都小于之前estimate_rowcount计算的值
	生成了mm tree并且找到最优索引，并且range_scan()->type结果为ROWID_INTERSECTION
	没有生成mm tree但是找到最优索引
	force index方式
calculate_scan_cost()的结果	以上都不满足

表：find_best_ref函数获得的结果

函数结果	说明	值
cur_fanout	总共需要读取多少行	计算方式见表一
cur_read_cost	读的开销	计算方式见表二
best_ref	cost最低的索引	索引优先级见表五

表一：cur_fanout计算方式

场景		值	说明
唯一索引		1
索引覆盖所有涉及列并且条件是列等于常量	table->quick_keys有值	table->quick_rows
	table->quick_keys无值	tab->records() / distinct_keys_est	distinct_keys_est表示的是一张表对应一个索引值的行数有几行，计算方式见表三
索引覆盖所有涉及列并且条件不是列等于常量	keyinfo->has_records_per_key()	keyinfo->records_per_key	计算方式见表四
	!keyinfo->has_records_per_key()	((double)tab->records() / (double)distinct_keys_est * (1.0 + ((double)(table->s->max_key_length - keyinfo->key_length) / (double)table->s->max_key_length))); if (cur_fanout < 2.0) cur_fanout = 2.0
索引不能覆盖所有涉及列并且条件是列等于常量		table->quick_rows
索引不能覆盖所有涉及列并且条件不是列等于常量	当前用的索引keyinfo->has_records_per_key()	keyinfo->records_per_key	records_per_key表示的是一张表对应一个索引值的行数有几行，计算方式见表四
	当前用的索引没有keyinfo->has_records_per_key()	(x * (b-a) + a*c-b)/(c-1)	b = records matched by whole key a = records matched by first key part c = number of key parts in key x = used key parts (1 <= x <= c)

表二：cur_read_cost计算方式

场景	值
唯一索引	之前左连接表的行数卷积 * table->cost_model()->page_read_cost(1.0)
索引覆盖所有涉及列	prefix_rowcount * find_cost_for_ref(thd, table, key, cur_fanout, tab->worst_seeks)
索引不能覆盖所有涉及列	prefix_rowcount * find_cost_for_ref(thd, table, key, cur_fanout, tab->worst_seeks)

表三：distinct_keys_est计算方式

场景	值
初始值	tab->records() / 10
distinct_keys_est > keyuse->ref_table_rows	keyuse->ref_table_rows
distinct_keys_est < 10	10
tab->records() < distinct_keys_est	tab->records()

注：10是MATCHING_ROWS_IN_OTHER_TABLE

表四：keyuse->ref_table_rows计算方式

keyuse->used_tables	场景	值
PSEUDO_TABLE_BITS	只有一张表	max(tmp_table->file->stats.records, 100) 这里100是固定值
OUTER_REF_TABLE_BIT	有子查询的话只有一行满足	1

注：通过JOIN::optimize_keyuse()函数获得

表五：索引类型选择优先级

idx_type	优先级	说明	对应的access_type
CLUSTERED_PK	最高	primary key,优先级最高	eq_ref
UNIQUE	高	唯一索引	eq_ref
NOT_UNIQUE	低	非唯一索引	ref
FULLTEXT	最低	fulltext索引，优先级最低	ref

三、实际例子说明

接下来看一开始的例子来说明上面的代码：

 greatsql> SELECT * FROM t1 JOIN t2 ON t1.c1=t2.cc1 AND t1.c2<5; { "ref_optimizer_key_uses": [ { "table": "`t1`", "field": "c1", "equals": "`t2`.`cc1`", "null_rejecting": true }, { "table": "`t2`", "field": "cc1", "equals": "`t1`.`c1`", "null_rejecting": true } ] }, "considered_execution_plans": [ { "plan_prefix": [ ], "table": "`t1`", "best_access_path": { "considered_access_paths": [ { "access_type": "ref", 第一张表不考虑用ref扫描 "index": "PRIMARY", "usable": false, "chosen": false }, { "rows_to_scan": 2, 用非best_ref方式扫描 "filtering_effect": [ ], "final_filtering_effect": 1, "access_type": "range", "range_details": { "used_index": "idx2" }, "resulting_rows": 2, "cost": 0.660457, "chosen": true } ] }, "condition_filtering_pct": 100, "rows_for_plan": 2, "cost_for_plan": 0.660457, "rest_of_plan": [ { "plan_prefix": [ "`t1`" ], "table": "`t2`", "best_access_path": { "considered_access_paths": [ { "access_type": "eq_ref", "index": "PRIMARY", "rows": 1, eq_ref扫描固定只有一行 "cost": 0.7, 计算公式=0.5(cur_read_cost) + 2(上一张表的行数) * 1(这张表行数) * 0.1 "chosen": true, "cause": "clustered_pk_chosen_by_heuristics" }, { "access_type": "scan", 因为t2没有mm tree因此只能选择全表扫描，又因为之前的索引扫描更优，所以这里不选择全表扫描 "chosen": false, "cause": "covering_index_better_than_full_scan" } ] }, "condition_filtering_pct": 100, "rows_for_plan": 2, "cost_for_plan": 1.36046, "chosen": true } ] }, { "plan_prefix": [ ], "table": "`t2`", "best_access_path": { "considered_access_paths": [ { "access_type": "ref", 第一张表不考虑用ref扫描 "index": "PRIMARY", "usable": false, "chosen": false }, { "rows_to_scan": 5, "filtering_effect": [ ], "final_filtering_effect": 1, "access_type": "scan", "resulting_rows": 5, "cost": 0.75, "chosen": true } ] }, "condition_filtering_pct": 100, "rows_for_plan": 5, "cost_for_plan": 0.75, "rest_of_plan": [ { "plan_prefix": [ "`t2`" ], "table": "`t1`", "best_access_path": { "considered_access_paths": [ { "access_type": "eq_ref", "index": "PRIMARY", "rows": 1, eq_ref扫描固定只有一行 "cost": 5.5, 计算公式=5(cur_read_cost) + 5(上一张表的行数) * 1(这张表行数) * 0.1 "chosen": true, "cause": "clustered_pk_chosen_by_heuristics" }, { "rows_to_scan": 2, "filtering_effect": [ ], "final_filtering_effect": 1, "access_type": "range", 这里因为t1表有mm tree但是扫描方式不是ROWID_INTERSECTION所以还要继续用calculate_scan_cost来估计cost，然后跟上面用eq_ref方式扫描方式进行对比，看哪个更优 "range_details": { "used_index": "idx2" }, "resulting_rows": 2, "cost": 3.30229, 因为这里的cost更低，因此舍弃上面的eq_ref扫描方式改为range扫描方式 "chosen": true } ] }, "condition_filtering_pct": 100, "rows_for_plan": 10, "cost_for_plan": 4.05229, "pruned_by_cost": true } ] } ]

再看一个三张表连接的例子，可以看到eq_ref扫描方式也要估算条件过滤百分比，并且第一张表不用索引扫描，也就不需要执行find_best_ref函数。

 greatsql> SELECT * FROM t1 JOIN t2 JOIN t3 ON t1.c1=t2.cc1 AND t3.ccc1=t2.cc1 AND t1.c2<15 AND t1.c2=10; { "considered_execution_plans": [ { "plan_prefix": [ ], "table": "`t1`", "best_access_path": { "considered_access_paths": [ { "access_type": "ref", "index": "PRIMARY", "usable": false, "chosen": false }, { "access_type": "ref", "index": "idx1", "rows": 2, "cost": 0.7, "chosen": true }, { "access_type": "ref", "index": "idx2", "rows": 2, "cost": 0.450457, "chosen": true }, { "access_type": "range", "range_details": { "used_index": "idx2" }, "chosen": false, "cause": "heuristic_index_cheaper" } ] }, "condition_filtering_pct": 100, "rows_for_plan": 2, "cost_for_plan": 0.450457, "rest_of_plan": [ { "plan_prefix": [ "`t1`" ], "table": "`t2`", "best_access_path": { "considered_access_paths": [ { "access_type": "eq_ref", "index": "PRIMARY", "rows": 1, "cost": 0.7, "chosen": true, "cause": "clustered_pk_chosen_by_heuristics" }, { "access_type": "scan", "chosen": false, "cause": "covering_index_better_than_full_scan" } ] }, "condition_filtering_pct": 100, "rows_for_plan": 2, "cost_for_plan": 1.15046, "rest_of_plan": [ { "plan_prefix": [ "`t1`", "`t2`" ], "table": "`t3`", "best_access_path": { "considered_access_paths": [ { "access_type": "ref", "index": "idx3_1", "rows": 1, "cost": 0.7, "chosen": true }, { "rows_to_scan": 5, "filtering_effect": [ ], "final_filtering_effect": 1, "access_type": "scan", "using_join_cache": true, "buffers_needed": 1, "resulting_rows": 5, "cost": 1.25004, "chosen": false } ] }, "added_to_eq_ref_extension": true, "condition_filtering_pct": 100, "rows_for_plan": 2, "cost_for_plan": 1.85046, "chosen": true } ] } ] }, { "plan_prefix": [ ], "table": "`t2`", "best_access_path": { "considered_access_paths": [ { "access_type": "ref", "index": "PRIMARY", "usable": false, "chosen": false }, { "rows_to_scan": 5, "filtering_effect": [ ], "final_filtering_effect": 1, "access_type": "scan", "resulting_rows": 5, "cost": 0.75, "chosen": true } ] }, "condition_filtering_pct": 100, "rows_for_plan": 5, "cost_for_plan": 0.75, "rest_of_plan": [ { "plan_prefix": [ "`t2`" ], "table": "`t1`", "best_access_path": { "considered_access_paths": [ { "access_type": "eq_ref", "index": "PRIMARY", "rows": 1, "cost": 1.75, "chosen": true, "cause": "clustered_pk_chosen_by_heuristics" }, { "rows_to_scan": 2, "filtering_effect": [ ], "final_filtering_effect": 1, "access_type": "range", "range_details": { "used_index": "idx2" }, "resulting_rows": 2, "cost": 3.30229, "chosen": false } ] }, "condition_filtering_pct": 28.5714, 这里看到eq_ref扫描方式也要估算条件过滤百分比 "rows_for_plan": 1.42857, "cost_for_plan": 2.5, "pruned_by_cost": true }, { "plan_prefix": [ "`t2`" ], "table": "`t3`", "best_access_path": { "considered_access_paths": [ { "access_type": "ref", "index": "idx3_1", "rows": 1, "cost": 1.75, "chosen": true }, { "rows_to_scan": 5, "filtering_effect": [ ], "final_filtering_effect": 1, "access_type": "scan", "using_join_cache": true, "buffers_needed": 1, "resulting_rows": 5, "cost": 2.75004, "chosen": false } ] }, "condition_filtering_pct": 100, "rows_for_plan": 5, "cost_for_plan": 2.5, "pruned_by_cost": true } ] }, { "plan_prefix": [ ], "table": "`t3`", "best_access_path": { "considered_access_paths": [ { "access_type": "ref", "index": "idx3_1", "usable": false, "chosen": false }, { "rows_to_scan": 5, "filtering_effect": [ ], "final_filtering_effect": 1, "access_type": "scan", "resulting_rows": 5, "cost": 0.75, "chosen": true } ] }, "condition_filtering_pct": 100, "rows_for_plan": 5, "cost_for_plan": 0.75, "rest_of_plan": [ { "plan_prefix": [ "`t3`" ], "table": "`t1`", "best_access_path": { "considered_access_paths": [ { "access_type": "eq_ref", "index": "PRIMARY", "rows": 1, "cost": 1.75, "chosen": true, "cause": "clustered_pk_chosen_by_heuristics" }, { "rows_to_scan": 2, "filtering_effect": [ ], "final_filtering_effect": 1, "access_type": "range", "range_details": { "used_index": "idx2" }, "resulting_rows": 2, "cost": 3.30229, "chosen": false } ] }, "condition_filtering_pct": 28.5714, "rows_for_plan": 1.42857, "cost_for_plan": 2.5, "pruned_by_cost": true }, { "plan_prefix": [ "`t3`" ], "table": "`t2`", "best_access_path": { "considered_access_paths": [ { "access_type": "eq_ref", "index": "PRIMARY", "rows": 1, "cost": 1.75, "chosen": true, "cause": "clustered_pk_chosen_by_heuristics" }, { "access_type": "scan", "chosen": false, "cause": "covering_index_better_than_full_scan" } ] }, "condition_filtering_pct": 100, "rows_for_plan": 5, "cost_for_plan": 2.5, "pruned_by_cost": true } ] } ] },

四、总结

从上面优化器的步骤我们认识了find_best_ref()进行rows和cost估计的过程，以及知道了使用这个结果的条件。需要注意的是，只有"ref_optimizer_key_uses"项目有值的情况才有可能使用这个结果。