【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"项目有值的情况才有可能使用这个结果。
