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

【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 计算方式