当前位置：首页 > 数据库 > 正文内容

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

邻居的猫1个月前 (12-09)数据库2008

【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_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_rowcount	join左表的行数，意味着多少行会被join到右表关于第一张表来说prefix_rowcount=1	第一张表：prefix_rowcount = rows_fetched * filter_effect 非第一张表：prefix_rowcount = 上一张表的prefix_rowcount * rows_fetched * filter_effect
prefix_cost	join左表的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_rows
keyuse_array有值(参阅前面<<优化器02>>)	REF扫描形式	tab->found_records * 0.75
以上都不契合。默许状况	全表行数	tab->found_records

表二，calculate_condition_filter() 核算办法

场景	值	阐明
满意条件的表的行数为0	filter = 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.05	filter = 0.05 / fanout	fanout是满意条件的表的行数

注：filter是条件过滤百分比，这个值区间在[0,1]，这个值越小代表过滤作用越好

表三，get_filtering_effect() 算出来的过滤系数

Item的系数	解说	系数	阐明
COND_FILTER_ALLPASS	Always true	1.0f	代表悉数数据都契合，悉数都要扫描
COND_FILTER_EQUALITY	col1 = col2	0.1f	代表预估10%数据契合条件
COND_FILTER_INEQUALITY	col1 > col2	0.3333f	代表预估1/3数据契合条件
COND_FILTER_BETWEEN	col1 BETWEEN a AND b	0.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数组有值的状况。

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是总行数。
    # 第2次：核算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) |
                                                                                            # 看到这儿挑选了不做条件过滤，