【GreatSQL优化器-05】条件过滤condition_fanout_filter

十念  论坛元老 | 2024-12-6 12:33:22 | 显示全部楼层 | 阅读模式
打印 上一主题 下一主题
楼主

主题 1036|帖子 1036|积分 3108

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要 登录 才可以下载或查看，没有账号？立即注册

x
【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 是什么：
  1. CREATE TABLE t1 (c1 INT PRIMARY KEY, c2 INT,date1 DATETIME);
  2. 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');
  3. CREATE TABLE t2 (cc1 INT PRIMARY KEY, cc2 INT);
  4. INSERT INTO t2 VALUES (1,3),(2,1),(3,2),(4,3),(5,15);
  5. # 为了查看过滤系数，需要创建一张没有主键的表用来做过滤估计。
  6. CREATE TABLE t3 (ccc1 INT, ccc2 varchar(100));
  7. INSERT INTO t3 VALUES (1,'aa1'),(2,'bb1'),(3,'cc1'),(4,'dd1'),(null,'ee');
  8. CREATE INDEX idx1 ON t1(c2);
  9. CREATE INDEX idx2 ON t1(c2,date1);
  10. CREATE INDEX idx2_1 ON t2(cc2);
  11. CREATE INDEX idx3_1 ON t3(ccc1);
复制代码
看到下面的 t3 的过滤百分比46.66%，意味着两张表 join 一共20行，因为 t3 的过滤百分比为 46.66%，因此最后只需要读取 20*46.66%=9 行数据。
留意，这里没有创建直方图，因此效果不包含直方图过滤的因素，关于直方图后面会专门开一章讲。
  1. greatsql> EXPLAIN SELECT * FROM t1 JOIN t3 ON t1.c1=t3.ccc1 OR t3.ccc1 <3;
  2. +----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+--------------------------------------------+
  3. | id | select_type | table | partitions | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra                                      |
  4. +----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+--------------------------------------------+
  5. |  1 | SIMPLE      | t1    | NULL       | index | PRIMARY       | idx2 | 11      | NULL |    4 |   100.00 | Using index                                |
  6. |  1 | SIMPLE      | t3    | NULL       | ALL   | idx3_1        | NULL | NULL    | NULL |    5 |    46.66 | Using where; Using join buffer (hash join) |
  7. # 这里显示的值就是 t3 的过滤数据百分比
  8. +----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+--------------------------------------------+
  10. greatsql> EXPLAIN FORMAT=TREE SELECT * FROM t1 JOIN t3 ON t1.c1=t3.ccc1 OR t3.ccc1<3;
  11. +---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
  12. | EXPLAIN                                                                                                                                                                                                                                                       |
  13. +---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
  14. | -> Filter: ((t3.ccc1 = t1.c1) or (t3.ccc1 < 3))  (cost=3.65 rows=9)
  15.     -> Inner hash join (no condition)  (cost=3.65 rows=9) # 这里结果为读取9行数据，跟上面算出来的数据一致
  16.         -> Table scan on t3  (cost=0.12 rows=5)
  17.         -> Hash
  18.             -> Index scan on t1 using idx2  (cost=1.40 rows=4)
  19. |
  20. +---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
复制代码
二、best_access_path代码解释

condition_fanout_filte的盘算在 best_access_path函数实现，用来预估差别 join 连接时候的 join 表的读取行数和可能的 cost。
  1. void Optimize_table_order::best_access_path(JOIN_TAB *tab,
  2.                                             const table_map remaining_tables,
  3.                                             const uint idx, bool disable_jbuf,
  4.                                             const double prefix_rowcount,
  5.                                             POSITION *pos) {
  6. # 如果根据前面的结果keyuse_array数组有值的话，那么根据find_best_ref()函数先找出最优索引，按照索引的方式计算cost
  7.   if (tab->keyuse() != nullptr &&
  8.       (table->file->ha_table_flags() & HA_NO_INDEX_ACCESS) == 0)
  9.     best_ref =
  10.         find_best_ref(tab, remaining_tables, idx, prefix_rowcount,
  11.                       &found_condition, &ref_depend_map, &used_key_parts);
  12.   # 最主要计算下面3个值
  13.   pos->filter_effect = filter_effect = std::  (1.0, tab->found_records * calculate_condition_filter() / rows_after_filtering);
  14.   pos->rows_fetched = rows_fetched = rows_after_filtering;
  15.   pos->read_cost = scan_read_cost = calculate_scan_cost();   
  16. }
复制代码
下面是代码里面涉及的盘算公式，这里是 keyuse_array 数组为空的情况，也就是扫描方式 "access_type" 非 "eq_ref" 和 "ref" 的情况，大概说是没有找到最优索引的情况。keyuse_array 数组有值的情况，在函数find_best_ref()盘算，效果有可能也走下面的盘算方式，具体在后面的章节具体介绍。
关键参数解释值rows_fetched总共需要读取多少行rows_after_filtering 见下表一filter_effect条件过滤百分比系数std::min(1.0, tab->found_records * calculate_condition_filter() / rows_after_filtering) 见下表一和二read_cost读的开销calculate_scan_cost() 见下表四prefix_rowcountjoin左表的行数，意味着多少行会被join到右表 对于第一张表来说prefix_rowcount=1第一张表：prefix_rowcount = rows_fetched * filter_effect 非第一张表：prefix_rowcount = 上一张表的prefix_rowcount * rows_fetched * filter_effectprefix_costjoin左表的cost，row_evaluate_cost()盘算公式=0.1 * 行数，0.1是读一行的开销第一张表：read_cost + cm->row_evaluate_cost(prefix_rowcount) 非第一张表：上一张表的prefix_cost + read_cost + cm->row_evaluate_cost(上一张表的prefix_rowcount*rows_fetched)表一，rows_after_filtering 盘算方式
场景解释值OPTIMIZER_SWITCH_COND_FANOUT_FILTER模式(默认ON)条件过滤模式开启tab->found_records * calculate_condition_filter() 见下表二table->quick_condition_rows != tab->found_records通过别的方法获取的表满足的行数table->quick_condition_rowskeyuse_array有值(参考前面)REF扫描模式tab->found_records * 0.75以上都不符合。默认情况全表行数tab->found_records表二，calculate_condition_filter() 盘算方式
场景值说明满足条件的表的行数为0filter = COND_FILTER_ALLPASS 见表三使用索引filter = filter * std::min(table->quick_rows[keyno] / tab->records() , 1.0)带有条件并且条件里涉及不含有索引的列filter = filter * Item_cond->get_filtering_effect() 见表三合并效果filter = max(filter, 1.0 / tab->records())(filter * fanout) < 0.05filter = 0.05 / fanoutfanout是满足条件的表的行数注：filter是条件过滤百分比，这个值区间在[0,1]，这个值越小代表过滤效果越好
表三，get_filtering_effect() 算出来的过滤系数
Item的系数解释系数说明COND_FILTER_ALLPASSAlways true1.0f代表全部数据都符合，全部都要扫描COND_FILTER_EQUALITYcol1 = col20.1f代表预估10%数据符合条件COND_FILTER_INEQUALITYcol1 > col20.3333f代表预估1/3数据符合条件COND_FILTER_BETWEENcol1 BETWEEN a AND b0.1111f代表预估1/9数据符合条件表四，calculate_scan_cost() 盘算方式
场景值说明如果是范围扫描prefix_rowcount * (tab->range_scan()->cost + cost_model->row_evaluate_cost(tab->found_records - *rows_after_filtering))非join buffer模式prefix_rowcount * (single_scan_read_cost + cost_model->row_evaluate_cost(tab->records() - *rows_after_filtering)) single_scan_read_cost盘算如下： force_index模式: table->file->read_cost(tab->ref().key, 1,tab->records() 见表五) 非force_index模式: table->file->table_scan_cost() 见表五join buffer模式(默认ON)buffer_count * (single_scan_read_cost+ cost_model->row_evaluate_cost(tab->records() - *rows_after_filtering)) buffer_count盘算如下： single_scan_read_cost盘算如下： 1.0 + ((double)cache_record_length(join, idx) * prefix_rowcount / thd->variables.join_buff_size force_index模式: table->file->read_cost(tab->ref().key, 1,tab->records()) 见表五 非force_index模式: table->file->table_scan_cost() 见表五默认这个模式打开表五 引擎盘算相关
场景值说明table->file->read_cost(index, ranges, rows)read_time(index, ranges, rows) *table->cost_model()->page_read_cost(1.0)index:index序号，ranges:range范围，rows:表行数table->file->table_scan_cost()(stats.data_file_length / IO_SIZE + 2) * table->cost_model()->page_read_cost(1.0)IO_SIZE=4096三、现实例子说明

接下来看一个例子来说明上面的代码。这里的例子不涉及keyuse_array数组有值的情况。
  1. greatsql> SELECT * FROM t1 join t3 ON t1.c1=t3.ccc1 or t3.ccc1<3;
  2. +----+------+---------------------+------+------+
  3. | c1 | c2   | date1               | ccc1 | ccc2 |
  4. +----+------+---------------------+------+------+
  5. |  1 |   10 | 2021-03-25 16:44:00 |    1 | aa1  |
  6. |  5 |    5 | 2024-03-25 16:44:00 |    1 | aa1  |
  7. |  3 |    4 | 2023-03-27 16:44:00 |    1 | aa1  |
  8. |  2 |    1 | 2022-03-26 16:44:00 |    1 | aa1  |
  9. |  1 |   10 | 2021-03-25 16:44:00 |    2 | bb1  |
  10. |  5 |    5 | 2024-03-25 16:44:00 |    2 | bb1  |
  11. |  3 |    4 | 2023-03-27 16:44:00 |    2 | bb1  |
  12. |  2 |    1 | 2022-03-26 16:44:00 |    2 | bb1  |
  13. |  3 |    4 | 2023-03-27 16:44:00 |    3 | cc1  |
  14. +----+------+---------------------+------+------+
  16. greatsql> EXPLAIN FORMAT=TREE SELECT * FROM t1 join t3 ON t1.c1=t3.ccc1 or t3.ccc1<3;
  17. +---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
  18. | EXPLAIN                                                                                                                                                                                                                                                       |
  19. +---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
  20. | -> Filter: ((t3.ccc1 = t1.c1) or (t3.ccc1 < 3))  (cost=3.65 rows=9)
  21.     -> Inner hash join (no condition)  (cost=3.65 rows=9)
  22.         -> Table scan on t3  (cost=0.12 rows=5)
  23.         -> Hash
  24.             -> Index scan on t1 using idx2  (cost=1.40 rows=4)
  25. |
  26. +---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
  28. greatsql> SELECT * FROM INFORMATION_SCHEMA.OPTIMIZER_TRACE;
  29.             "considered_execution_plans": [
  30.               {
  31.                 "plan_prefix": [
  32.                 ],
  33.                 "table": "`t1`",
  34.                 "best_access_path": {
  35.                   "considered_access_paths": [
  36.                     {
  37.                       "rows_to_scan": 4,
  38.                       "filtering_effect": [
  39.                       ],
  40.                       "final_filtering_effect": 1,
  41.                       "access_type": "scan",
  42.                       "resulting_rows": 4,# 这个值就是rows_after_filtering
  43.                       "cost": 0.65, # 计算公式=read_cost(0.25)+cost_model->row_evaluate_cost(1 * rows_after_filtering)
  44.                       "chosen": true
  45.                     }
  46.                   ]
  47.                 },
  48.                 "condition_filtering_pct": 100, # 这个值就是filter_effect * 100
  49.                 "rows_for_plan": 4, # 这个值就是prefix_rowcount=rows_to_scan * filter_effect / 100
  50.                 "cost_for_plan": 0.65, # 这个值就是prefix_cost=read_cost(0.25) + cm->row_evaluate_cost(prefix_rowcount=4)
  51.                 "rest_of_plan": [
  52.                   {
  53.                     "plan_prefix": [ # 当前左连接表为t1
  54.                       "`t1`"
  55.                     ],
  56.                     "table": "`t3`", # 右连接表为t3
  57.                     "best_access_path": {
  58.                       "considered_access_paths": [
  59.                         {
  60.                           "rows_to_scan": 5,
  61.                           "filtering_effect": [
  62.                           ],
  63.                           "final_filtering_effect": 1,
  64.                           "access_type": "scan",
  65.                           "using_join_cache": true,
  66.                           "buffers_needed": 1,
  67.                           "resulting_rows": 5, # 这个值就是rows_after_filtering
  68.                           "cost": 2.25005, # 计算公式read_cost(0.25)+cost_model->row_evaluate_cost(prefix_rowcount * rows_after_filtering=4 * 5)
  69.                           "chosen": true
  70.                         }
  71.                       ]
  72.                     },
  73.                     "condition_filtering_pct": 46.664, # 这个值计算过程见下面<<附录：t3的filter_effect值计算>> ※bug？用explain看到的和直接敲命令看到的不一样，前者46.664后者为100，而"rows_for_plan"会变为没有过滤的20
  74.                     "rows_for_plan": 9.3328, # 这个值就是prefix_rowcount=4(上一张表的prefix_rowcount) * 5 * 46.664 / 100
  75.                     "cost_for_plan": 2.90005, # 这个值就是prefix_cost=0.65(上一张表的prefix_cost)+read_cost(0.25) + cm->row_evaluate_cost(20=4*5)
  76.                     "chosen": true
  77.                   }
  78.                 ]
  79.               },
  80.               {
  81.                 "plan_prefix": [
  82.                 ],
  83.                 "table": "`t3`",
  84.                 "best_access_path": {
  85.                   "considered_access_paths": [
  86.                     {
  87.                       "rows_to_scan": 5,
  88.                       "filtering_effect": [
  89.                       ],
  90.                       "final_filtering_effect": 1,
  91.                       "access_type": "scan",
  92.                       "resulting_rows": 5,
  93.                       "cost": 0.75, # 计算公式read_cost(0.25)+5行*0.1
  94.                       "chosen": true
  95.                     }
  96.                   ]
  97.                 },
  98.                 "condition_filtering_pct": 100,
  99.                 "rows_for_plan": 5, # 这个值就是prefix_rowcount
  100.                 "cost_for_plan": 0.75, # 这个值就是prefix_cost
  101.                 "rest_of_plan": [
  102.                   {
  103.                     "plan_prefix": [ # 当前左连接表为t3
  104.                       "`t3`"
  105.                     ],
  106.                     "table": "`t1`", # 右连接表为t1
  107.                     "best_access_path": {
  108.                       "considered_access_paths": [
  109.                         {
  110.                           "rows_to_scan": 4,
  111.                           "filtering_effect": [
  112.                           ],
  113.                           "final_filtering_effect": 1,
  114.                           "access_type": "scan",
  115.                           "using_join_cache": true,
  116.                           "buffers_needed": 1,
  117.                           "resulting_rows": 4,
  118.                           "cost": 3.00776, # 计算公式read_cost(1.007)+cost_model->row_evaluate_cost(prefix_rowcount * rows_after_filtering=5 * 4)
  119.                           "chosen": true
  120.                         }
  121.                       ]
  122.                     },
  123.                     "condition_filtering_pct": 100,
  124.                     "rows_for_plan": 20, # 这个值就是prefix_rowcount=5(上一张表的prefix_rowcount) * 4 * 100 / 100
  125.                     "cost_for_plan": 3.75776, # 这个值就是prefix_cost=0.75(上一张表的prefix_cost)+read_cost(1.007) + cm->row_evaluate_cost(20=5*4)
  126.                     "pruned_by_cost": true # 因为这里算出来的3.75776 > 2.90005，因此被裁剪掉了
  127.                   }
  128.                 ]
  129.               }
  130.             ]
  131.           },
  132.           {
  133.             "attaching_conditions_to_tables": { # 添加一些附加条件
  134.               "original_condition": "((`t3`.`ccc1` = `t1`.`c1`) or (`t3`.`ccc1` < 3))",
  135.               "attached_conditions_computation": [
  136.               ],
  137.               "attached_conditions_summary": [ # t1作为驱动表，执行全表扫描，因此不需要任何条件
  138.                 {
  139.                   "table": "`t1`",
  140.                   "attached": null
  141.                 },
  142.                 {
  143.                   "table": "`t3`",
  144.                   "attached": "((`t3`.`ccc1` = `t1`.`c1`) or (`t3`.`ccc1` < 3))" #  t3作为连接表，按照条件过滤
  145.                 }
  146.               ]
  147.             }
  148.           },
  149.           {
  150.             "finalizing_table_conditions": [
  151.               {
  152.                 "table": "`t3`",
  153.                 "original_table_condition": "((`t3`.`ccc1` = `t1`.`c1`) or (`t3`.`ccc1` < 3))",
  154.                 "final_table_condition   ": "((`t3`.`ccc1` = `t1`.`c1`) or (`t3`.`ccc1` < 3))"
  155.               }
  156.             ]
  157.           },
  158.           {
  159.             "refine_plan": [
  160.               {
  161.                 "table": "`t1`"
  162.               },
  163.               {
  164.                 "table": "`t3`"
  165.               }
  166.             ]
  167.           }
  168.         ]
  169.       }
  170.     },
  171.     {
  172.       "join_explain": {
  173.         "select#": 1,
  174.         "steps": [
  175.         ]
  176.       }
  177.     }
  178.   ]
  179. } |           
  181. # 附录：t3的filter_effect值计算
  182. # 这个函数计算t1.c1=t3.ccc1和t3.ccc1<3的filter_effect值，计算过程见下面
  183. float Item_cond_or::get_filtering_effect(THD *thd, table_map filter_for_table,
  184.                                          table_map read_tables,
  185.                                          const MY_BITMAP *fields_to_ignore,
  186.                                          double rows_in_table) {
  187.   while ((item = it++)) {
  188.     const float cur_filter = item->get_filtering_effect(
  189.         thd, filter_for_table, read_tables, fields_to_ignore, rows_in_table);
  190.     # 第一次：计算t1.c1=t3.ccc1，返回 1/5=20%，其中5是总行数。
  191.     # 第二次：计算t3.ccc1<3，返回COND_FILTER_INEQUALITY=0.333
  192.     # 最后的filter=0.2+0.333 - (0.2*0.333)=0.4664
  193.     filter = filter + cur_filter - (filter * cur_filter);
  194.   }
  195.   return filter;
  196. }
复制代码
现在把之前03的内容拿过来回顾一下其时的效果，看看为何是其时的效果。从下面效果可以看出，当存在keyuse的时候，优化器最后走哪条索引是通过find_best_ref()函数来决定的。
[code]greatsql> EXPLAIN SELECT * FROM t1 join t2 ON t1.c1=t2.cc1 and t1.c1
回复

使用道具 举报

0 个回复

倒序浏览
返回列表

快速回复

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

十念

论坛元老
这个人很懒什么都没写!

楼主热帖

标签云

AI 运维 CIO 存储 服务器
微信订阅号
微信服务号
微信客服
小程序
H5
关于我们 商务合作 网站地图
©Copyright 2022-2024 杭州祥升科技有限公司 版权所有 浙ICP备20004199号
快速回复 返回顶部 返回列表