【GreatSQL 优化器 -05】条件过滤 condition_fanout_filter
作者：GreatSQL
- 2024-12-06 福建
本文字数：13230 字
阅读完需：约 43 分钟
【GreatSQL 优化器-05】条件过滤 condition_fanout_filter
一、condition_fanout_filter 介绍
GreatSQL 的优化器对于 join 的表需要根据行数和 cost 来确定最后哪张表先执行哪张表后执行，这里面就涉及到预估满足条件的表数据，condition_fanout_filter 会根据一系列方法计算出一个数据过滤百分比，这个比百分比就是 filtered 系数，这个值区间在[0,1]，值越小代表过滤效果越好。用这个系数乘以总的行数就可以得出最后需要扫描的表行数的数量，可以大幅节省开销和执行时间。
这个功能是由 OPTIMIZER_SWITCH_COND_FANOUT_FILTER这个OPTIMIZER_SWITCH 来控制的，默认是打开的。因此一般情况下不需要特意去关闭，但是如果遇到执行特别慢的一些情况可以考虑关闭。
下面用一个简单的例子来说明 condition_fanout_filter 是什么：
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');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);
复制代码
看到下面的 t3 的过滤百分比 46.66%，意味着两张表 join 一共 20 行，因为 t3 的过滤百分比为 46.66%，因此最后只需要读取 20*46.66%=9 行数据。
注意，这里没有建立直方图，因此结果不包含直方图过滤的因素，关于直方图后面会专门开一章讲。
greatsql> EXPLAIN SELECT * FROM t1 JOIN t3 ON t1.c1=t3.ccc1 OR t3.ccc1 <3;+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+--------------------------------------------+| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+--------------------------------------------+| 1 | SIMPLE | t1 | NULL | index | PRIMARY | idx2 | 11 | NULL | 4 | 100.00 | Using index || 1 | SIMPLE | t3 | NULL | ALL | idx3_1 | NULL | NULL | NULL | 5 | 46.66 | Using where; Using join buffer (hash join) |# 这里显示的值就是 t3 的过滤数据百分比+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+--------------------------------------------+
greatsql> EXPLAIN FORMAT=TREE SELECT * FROM t1 JOIN t3 ON t1.c1=t3.ccc1 OR t3.ccc1<3;+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+| EXPLAIN |+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+| -> Filter: ((t3.ccc1 = t1.c1) or (t3.ccc1 < 3)) (cost=3.65 rows=9) -> Inner hash join (no condition) (cost=3.65 rows=9) # 这里结果为读取9行数据，跟上面算出来的数据一致 -> Table scan on t3 (cost=0.12 rows=5) -> Hash -> Index scan on t1 using idx2 (cost=1.40 rows=4) |+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
复制代码
二、best_access_path 代码解释
condition_fanout_filte的计算在 best_access_path函数实现，用来预估不同 join 连接时候的 join 表的读取行数和可能的 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) {# 如果根据前面的结果keyuse_array数组有值的话，那么根据find_best_ref()函数先找出最优索引，按照索引的方式计算cost if (tab->keyuse() != nullptr && (table->file->ha_table_flags() & HA_NO_INDEX_ACCESS) == 0) best_ref = find_best_ref(tab, remaining_tables, idx, prefix_rowcount, &found_condition, &ref_depend_map, &used_key_parts); # 最主要计算下面3个值 pos->filter_effect = filter_effect = std:: (1.0, tab->found_records * calculate_condition_filter() / rows_after_filtering); pos->rows_fetched = rows_fetched = rows_after_filtering; pos->read_cost = scan_read_cost = calculate_scan_cost(); }
复制代码
下面是代码里面涉及的计算公式，这里是 keyuse_array 数组为空的情况，也就是扫描方式 "access_type" 非 "eq_ref" 和 "ref" 的情况，或者说是没有找到最优索引的情况。keyuse_array 数组有值的情况，在函数 find_best_ref()计算，结果有可能也走下面的计算方式，详细在后面的章节详细介绍。
表一，rows_after_filtering 计算方式
表二，calculate_condition_filter() 计算方式
注：filter 是条件过滤百分比，这个值区间在[0,1]，这个值越小代表过滤效果越好
表三，get_filtering_effect() 算出来的过滤系数
表四，calculate_scan_cost() 计算方式
表五 引擎计算相关
三、实际例子说明
接下来看一个例子来说明上面的代码。这里的例子不涉及 keyuse_array 数组有值的情况。
greatsql> SELECT * FROM t1 join t3 ON t1.c1=t3.ccc1 or t3.ccc1<3;+----+------+---------------------+------+------+| c1 | c2 | date1 | ccc1 | ccc2 |+----+------+---------------------+------+------+| 1 | 10 | 2021-03-25 16:44:00 | 1 | aa1 || 5 | 5 | 2024-03-25 16:44:00 | 1 | aa1 || 3 | 4 | 2023-03-27 16:44:00 | 1 | aa1 || 2 | 1 | 2022-03-26 16:44:00 | 1 | aa1 || 1 | 10 | 2021-03-25 16:44:00 | 2 | bb1 || 5 | 5 | 2024-03-25 16:44:00 | 2 | bb1 || 3 | 4 | 2023-03-27 16:44:00 | 2 | bb1 || 2 | 1 | 2022-03-26 16:44:00 | 2 | bb1 || 3 | 4 | 2023-03-27 16:44:00 | 3 | cc1 |+----+------+---------------------+------+------+
greatsql> EXPLAIN FORMAT=TREE SELECT * FROM t1 join t3 ON t1.c1=t3.ccc1 or t3.ccc1<3;+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+| EXPLAIN |+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+| -> Filter: ((t3.ccc1 = t1.c1) or (t3.ccc1 < 3)) (cost=3.65 rows=9) -> Inner hash join (no condition) (cost=3.65 rows=9) -> Table scan on t3 (cost=0.12 rows=5) -> Hash -> Index scan on t1 using idx2 (cost=1.40 rows=4) |+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
greatsql> SELECT * FROM INFORMATION_SCHEMA.OPTIMIZER_TRACE; "considered_execution_plans": [ { "plan_prefix": [ ], "table": "`t1`", "best_access_path": { "considered_access_paths": [ { "rows_to_scan": 4, "filtering_effect": [ ], "final_filtering_effect": 1, "access_type": "scan", "resulting_rows": 4,# 这个值就是rows_after_filtering "cost": 0.65, # 计算公式=read_cost(0.25)+cost_model->row_evaluate_cost(1 * rows_after_filtering) "chosen": true } ] }, "condition_filtering_pct": 100, # 这个值就是filter_effect * 100 "rows_for_plan": 4, # 这个值就是prefix_rowcount=rows_to_scan * filter_effect / 100 "cost_for_plan": 0.65, # 这个值就是prefix_cost=read_cost(0.25) + cm->row_evaluate_cost(prefix_rowcount=4) "rest_of_plan": [ { "plan_prefix": [ # 当前左连接表为t1 "`t1`" ], "table": "`t3`", # 右连接表为t3 "best_access_path": { "considered_access_paths": [ { "rows_to_scan": 5, "filtering_effect": [ ], "final_filtering_effect": 1, "access_type": "scan", "using_join_cache": true, "buffers_needed": 1, "resulting_rows": 5, # 这个值就是rows_after_filtering "cost": 2.25005, # 计算公式read_cost(0.25)+cost_model->row_evaluate_cost(prefix_rowcount * rows_after_filtering=4 * 5) "chosen": true } ] }, "condition_filtering_pct": 46.664, # 这个值计算过程见下面<<附录：t3的filter_effect值计算>> ※bug？用explain看到的和直接敲命令看到的不一样，前者46.664后者为100，而"rows_for_plan"会变为没有过滤的20 "rows_for_plan": 9.3328, # 这个值就是prefix_rowcount=4(上一张表的prefix_rowcount) * 5 * 46.664 / 100 "cost_for_plan": 2.90005, # 这个值就是prefix_cost=0.65(上一张表的prefix_cost)+read_cost(0.25) + cm->row_evaluate_cost(20=4*5) "chosen": true } ] }, { "plan_prefix": [ ], "table": "`t3`", "best_access_path": { "considered_access_paths": [ { "rows_to_scan": 5, "filtering_effect": [ ], "final_filtering_effect": 1, "access_type": "scan", "resulting_rows": 5, "cost": 0.75, # 计算公式read_cost(0.25)+5行*0.1 "chosen": true } ] }, "condition_filtering_pct": 100, "rows_for_plan": 5, # 这个值就是prefix_rowcount "cost_for_plan": 0.75, # 这个值就是prefix_cost "rest_of_plan": [ { "plan_prefix": [ # 当前左连接表为t3 "`t3`" ], "table": "`t1`", # 右连接表为t1 "best_access_path": { "considered_access_paths": [ { "rows_to_scan": 4, "filtering_effect": [ ], "final_filtering_effect": 1, "access_type": "scan", "using_join_cache": true, "buffers_needed": 1, "resulting_rows": 4, "cost": 3.00776, # 计算公式read_cost(1.007)+cost_model->row_evaluate_cost(prefix_rowcount * rows_after_filtering=5 * 4) "chosen": true } ] }, "condition_filtering_pct": 100, "rows_for_plan": 20, # 这个值就是prefix_rowcount=5(上一张表的prefix_rowcount) * 4 * 100 / 100 "cost_for_plan": 3.75776, # 这个值就是prefix_cost=0.75(上一张表的prefix_cost)+read_cost(1.007) + cm->row_evaluate_cost(20=5*4) "pruned_by_cost": true # 因为这里算出来的3.75776 > 2.90005，因此被裁剪掉了 } ] } ] }, { "attaching_conditions_to_tables": { # 添加一些附加条件 "original_condition": "((`t3`.`ccc1` = `t1`.`c1`) or (`t3`.`ccc1` < 3))", "attached_conditions_computation": [ ], "attached_conditions_summary": [ # t1作为驱动表，执行全表扫描，因此不需要任何条件 { "table": "`t1`", "attached": null }, { "table": "`t3`", "attached": "((`t3`.`ccc1` = `t1`.`c1`) or (`t3`.`ccc1` < 3))" # t3作为连接表，按照条件过滤 } ] } }, { "finalizing_table_conditions": [ { "table": "`t3`", "original_table_condition": "((`t3`.`ccc1` = `t1`.`c1`) or (`t3`.`ccc1` < 3))", "final_table_condition ": "((`t3`.`ccc1` = `t1`.`c1`) or (`t3`.`ccc1` < 3))" } ] }, { "refine_plan": [ { "table": "`t1`" }, { "table": "`t3`" } ] } ] } }, { "join_explain": { "select#": 1, "steps": [ ] } } ]} |
# 附录：t3的filter_effect值计算# 这个函数计算t1.c1=t3.ccc1和t3.ccc1<3的filter_effect值，计算过程见下面float Item_cond_or::get_filtering_effect(THD *thd, table_map filter_for_table, table_map read_tables, const MY_BITMAP *fields_to_ignore, double rows_in_table) { while ((item = it++)) { const float cur_filter = item->get_filtering_effect( thd, filter_for_table, read_tables, fields_to_ignore, rows_in_table); # 第一次：计算t1.c1=t3.ccc1，返回 1/5=20%，其中5是总行数。 # 第二次：计算t3.ccc1<3，返回COND_FILTER_INEQUALITY=0.333 # 最后的filter=0.2+0.333 - (0.2*0.333)=0.4664 filter = filter + cur_filter - (filter * cur_filter); } return filter;}
复制代码
下面把OPTIMIZER_SWITCH_COND_FANOUT_FILTER模式关闭看看执行效果什么变化
greatsql> explain SELECT /*+ set_var(optimizer_switch='condition_fanout_filter=off') */ * FROM t1 join t3 ON t1.c1=t3.ccc1 or t3.ccc1<3;+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+--------------------------------------------+| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+--------------------------------------------+| 1 | SIMPLE | t1 | NULL | index | PRIMARY | idx2 | 11 | NULL | 4 | 100.00 | Using index || 1 | SIMPLE | t3 | NULL | ALL | idx3_1 | NULL | NULL | NULL | 5 | 100.00 | Using where; Using join buffer (hash join) | # 看到这里选择了不做条件过滤，全表数据连接+----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+--------------------------------------------+
greatsql> EXPLAIN FORMAT=TREE SELECT /*+ set_var(optimizer_switch='condition_fanout_filter=off') */ * FROM t1 join t3 ON t1.c1=t3.ccc1 or t3.ccc1<3;+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+| EXPLAIN |+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+| -> Filter: ((t3.ccc1 = t1.c1) or (t3.ccc1 < 3)) (cost=3.65 rows=20)# 因为表里数据少，跟刚才比cost没有变化，但是要是数据大的话就很明显 -> Inner hash join (no condition) (cost=3.65 rows=20) # 这里变为了20行，意味着读取全部行数据 -> Table scan on t3 (cost=0.19 rows=5) -> Hash -> Index scan on t1 using idx2 (cost=1.40 rows=4) |+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
{ "considered_execution_plans": [ { "plan_prefix": [ ], "table": "`t1`", "best_access_path": { "considered_access_paths": [ { "rows_to_scan": 4, "access_type": "scan", "resulting_rows": 4, "cost": 1.4, "chosen": true } ] }, "condition_filtering_pct": 100, "rows_for_plan": 4, "cost_for_plan": 1.4, "rest_of_plan": [ { "plan_prefix": [ # 当前左连接表为t1 "`t1`" ], "table": "`t3`", "best_access_path": { "considered_access_paths": [ { "rows_to_scan": 5, "access_type": "scan", "using_join_cache": true, "buffers_needed": 1, "resulting_rows": 5, "cost": 2.25005, "chosen": true } ] }, "condition_filtering_pct": 100, # 这里的过滤系数变为100，说明不进行条件过滤，读取全部行 "rows_for_plan": 20, # 由上面的9行变为全部数据连接，20行数据 "cost_for_plan": 3.65005, "chosen": true } ] }, { "plan_prefix": [ ], "table": "`t3`", "best_access_path": { "considered_access_paths": [ { "rows_to_scan": 5, "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": [ { "rows_to_scan": 4, "access_type": "scan", "using_join_cache": true, "buffers_needed": 1, "resulting_rows": 4, "cost": 3.00776, "chosen": true } ] }, "condition_filtering_pct": 100, "rows_for_plan": 20, "cost_for_plan": 3.75776, "pruned_by_cost": true } ] } ] }, { "attaching_conditions_to_tables": { "original_condition": "((`t3`.`ccc1` = `t1`.`c1`) or (`t3`.`ccc1` < 3))", "attached_conditions_computation": [ ], "attached_conditions_summary": [ { "table": "`t1`", "attached": null }, { "table": "`t3`", "attached": "((`t3`.`ccc1` = `t1`.`c1`) or (`t3`.`ccc1` < 3))" } ] } }, { "finalizing_table_conditions": [ { "table": "`t3`", "original_table_condition": "((`t3`.`ccc1` = `t1`.`c1`) or (`t3`.`ccc1` < 3))", "final_table_condition ": "((`t3`.`ccc1` = `t1`.`c1`) or (`t3`.`ccc1` < 3))" } ] }, { "refine_plan": [ { "table": "`t1`" }, { "table": "`t3`" } ] } ] } }, { "join_explain": { "select#": 1, "steps": [ ] } } ]}
复制代码
现在把之前 03 的内容拿过来回顾一下当时的结果，看看为何是当时的结果。从下面结果可以看出，当存在 keyuse 的时候，优化器最后走哪条索引是通过 find_best_ref()函数来决定的。
greatsql> EXPLAIN SELECT * FROM t1 join t2 ON t1.c1=t2.cc1 and t1.c1<5;+----+-------------+-------+------------+--------+---------------+---------+---------+-----------+------+----------+-------------+| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |+----+-------------+-------+------------+--------+---------------+---------+---------+-----------+------+----------+-------------+| 1 | SIMPLE | t1 | NULL | range | PRIMARY | PRIMARY | 4 | NULL | 3 | 100.00 | Using where || 1 | SIMPLE | t2 | NULL | eq_ref | PRIMARY | PRIMARY | 4 | db1.t1.c1 | 1 | 100.00 | NULL | # t2这个结果看下面的解释+----+-------------+-------+------------+--------+---------------+---------+---------+-----------+------+----------+-------------+
{\ "considered_execution_plans": [\ {\ "plan_prefix": [\ ],\ "table": "`t1`",\ "best_access_path": {\ "considered_access_paths": [\ {\ "access_type": "ref",\ # t1表不选择"ref"方式，因为cost比"range"方式大 "index": "PRIMARY",\ "usable": false,\ "chosen": false\ },\ {\ "rows_to_scan": 3,\ "filtering_effect": [\ ],\ "final_filtering_effect": 1,\ "access_type": "range",\ # t1表最后选择了"range"方式进行扫描 "range_details": {\ "used_index": "PRIMARY"\ },\ "resulting_rows": 3,\ "cost": 0.860732,\ "chosen": true\ }\ ]\ },\ "condition_filtering_pct": 100,\ "rows_for_plan": 3,\ "cost_for_plan": 0.860732,\ "rest_of_plan": [\ "rest_of_plan": [\ {\ "plan_prefix": [\ "`t1`"\ ],\ "table": "`t2`",\ "best_access_path": {\ "considered_access_paths": [\ {\ "access_type": "eq_ref",\ # 在t1 join t2的连接方式里，判断用"eq_ref"方式扫描cost更小。这里通过find_best_ref()获取 "index": "PRIMARY",\ "rows": 1,\ "cost": 1.05,\ "chosen": true,\ "cause": "clustered_pk_chosen_by_heuristics"\ },\ {\ "access_type": "range",\ "range_details": {\ "used_index": "PRIMARY"\ },\ "chosen": false,\ "cause": "heuristic_index_cheaper"\ }\ ]\ },\ "condition_filtering_pct": 100,\ "rows_for_plan": 3,\ "cost_for_plan": 1.91073,\ "chosen": true\ }\ {\ "refine_plan": [\ # 根据最后比较结果，按照t1,t2方式连接cost最小，因此选择这种顺序进行join {\ "table": "`t1`"\ },\ {\ "table": "`t2`"\ }\ ]\ }\
复制代码
四、总结
从上面优化器最早的步骤我们认识了条件过滤condition_fanout_filter的定义以及使用方法，也学会了计算 join 时候的 cost，然后根据 cost 选择最优的连接顺序。回到开头提到的这个功能在一些场景有可能会带来选择错误的问题，这个下一期展开细讲。用这种过滤方法算出来的结果也不精确，GreatSQL 用了另一个功能直方图来做数据统计，让结果更加精确，这个直方图的分析放后面章节讲。
划线
评论
复制
发布于: 刚刚阅读数: 4
版权声明: 本文为 InfoQ 作者【GreatSQL】的原创文章。
原文链接:【http://xie.infoq.cn/article/4ed9f1829bfffdd5872cf5c03】。文章转载请联系作者。
GreatSQL
关注
GreatSQL社区 2023-01-31 加入
GreatSQL是由万里数据库维护的MySQL分支，专注于提升MGR可靠性及性能，支持InnoDB并行查询特性，是适用于金融级应用的MySQL分支版本。 社区：https://greatsql.cn/ Gitee: https://gitee.com/GreatSQL/GreatSQL
评论