【GreatSQL 优化器 -04】贪婪搜索算法浅析
作者：GreatSQL
- 2024-11-22 福建
本文字数：6150 字
阅读完需：约 20 分钟
【GreatSQL 优化器-04】贪婪搜索算法浅析
一、贪婪搜索（greedy_search）介绍
GreatSQL 的优化器用greedy_search方法来枚举所有的表连接场景，然后从中根据最小 cost 来决定最佳连接顺序。这里面就涉及每种场景的 cost 计算方法，不同计算方法会导致不同的排序结果。
因为枚举所有 join 场景，当表数量很大的时候就有可能无穷无尽消耗系统资源，因此 GreatSQL 执行 greedy_search 的时候使用search_depth 和prune_level变量（分别对应 GreatSQL 中的 optimizer_search_depth 和 optimizer_prune_level 系统变量），防止无穷无尽的分析各种连接顺序的成本，如果连接表的个数小于search_depth，那么就继续穷举分析每一种连接顺序的 cost，否则只对与optimizer_search_depth 值相同数量的表进行穷举分析。该值越大，成本分析的越精确，越容易得到好的执行计划，但是消耗的时间也就越长，否则得到的可能不是最好的执行计划，但可以省掉很多分析连接成本的时间。设置合适的 prune_level 值可以裁剪掉一些不必要的深度，直接跟后面访问数量最少的表进行连接计算。
执行 greedy_search 复杂度可能是**O(N*N^search_depth/search_depth)**。如果 search_depth > N 那么算法的复杂度就是 **O(N!)**。通常优化器分析的复杂度都是 **O(N!)**。
下面用一个简单的例子来说明 greedy_search 是什么。
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);
-- 这里做了一个6张表的连接，这里面就涉及了greedy_search方法来决定哪张表先执行哪张表后执行-- 看下面最终结果是按照t1,t4,t2,t5,t3,t4顺序来执行连接的greatsql> EXPLAIN SELECT * FROM t3,t1,t2,t1 AS t4,t2 AS t5,t3 AS t6 WHERE t1.c1=t3.ccc1 and t2.cc1=t3.ccc1 and t1.c1=t4.c1 and t1.c1=t5.cc1 and t1.c1=t6.ccc1;+----+-------------+-------+------------+--------+---------------+---------+---------+-----------+------+----------+-------------+| 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 | t4 | NULL | eq_ref | PRIMARY | PRIMARY | 4 | db1.t1.c1 | 1 | 100.00 | NULL || 1 | SIMPLE | t2 | NULL | eq_ref | PRIMARY | PRIMARY | 4 | db1.t1.c1 | 1 | 100.00 | NULL || 1 | SIMPLE | t5 | NULL | eq_ref | PRIMARY | PRIMARY | 4 | db1.t1.c1 | 1 | 100.00 | NULL || 1 | SIMPLE | t3 | NULL | ref | idx3_1 | idx3_1 | 5 | db1.t1.c1 | 1 | 100.00 | NULL || 1 | SIMPLE | t6 | NULL | ref | idx3_1 | idx3_1 | 5 | db1.t1.c1 | 1 | 100.00 | NULL |+----+-------------+-------+------------+--------+---------------+---------+---------+-----------+------+----------+-------------+
复制代码
二、greedy_search 代码解释
bool JOIN::make_join_plan() { // Choose the table order based on analysis done so far. if (Optimize_table_order(thd, this, nullptr).choose_table_order()) return true;}
bool Optimize_table_order::choose_table_order() { // 先对所有表做一个排序，小表放前面 merge_sort(); if (straight_join) optimize_straight_join(join_tables); else { if (greedy_search(join_tables)) return true; }}
bool Optimize_table_order::greedy_search(table_map remaining_tables) { do { if (best_extension_by_limited_search(remaining_tables, idx, search_depth)) return true; // 如果层数没有超过规定大小，说明已经执行完枚举可以退出。如果超过了，说明不需要执行枚举连接，按照单独连接方式继续执行。 if (size_remain <= search_depth || use_best_so_far) { return false; } --size_remain; ++idx; }}
// 用current_search_depth来计数，每进行一次深度连接计算就减一，用来控制join连接枚举分析的层数。bool Optimize_table_order::best_extension_by_limited_search( table_map remaining_tables, uint idx, uint current_search_depth) { for (JOIN_TAB **pos = join->best_ref + idx; *pos && !use_best_so_far; pos++) { /* Find the best access method from 's' to the current partial plan */ // 该表之后的每个表遍历一遍，计算每种连接的cost best_access_path(s, remaining_tables, idx, false, idx ? (position - 1)->prefix_rowcount : 1.0, position); // 如果算完左连接cost比之前的还大，就不继续算下一张表，直接开始下一次连接计算 if (position->prefix_cost >= join->best_read && found_plan_with_allowed_sj) { trace_one_table.add("pruned_by_cost", true); continue; } // 打开裁剪模式的话 if (prune_level == 1) { // 如果当前计算出来的rowcount小于之前保存下来的best_rowcount，那么就替换best_rowcount值 if (best_rowcount > position->prefix_rowcount || best_cost > position->prefix_cost || (idx == join->const_tables && // 's' is the first table in the QEP s->table() == join->sort_by_table)) { best_rowcount = position->prefix_rowcount; best_cost = position->prefix_cost; } else // 否则就跳过剩下表的穷举搜索计算，直接用下一次连接继续计算 continue; } // current_search_depth还在层数允许范围内，递归继续进行下一次优化查询 if ((current_search_depth > 1) && remaining_tables_after) { if (prune_level == 1 && // 1) position->key != nullptr && // 2) position->rows_fetched <= 1.0) // 3) { // 如果连接左表cost比之前的大，那么会被裁剪 // 如果满足(EQ_)REF key的join方式并且本次找到的行数只有一行，那么就执行EQ_REF-joined连接计算 eq_ref_extension_by_limited_search(); } else // 继续执行下一张连接表的连接cost计算 best_extension_by_limited_search(remaining_tables_after, idx + 1, current_search_depth - 1)); } else // if ((current_search_depth > 1) && ... // 层数还有剩，后面没有表要连接了，那就保存当次计算结果以便下次做比较 { // 将这次计算出来的rowcount和read_cost存入prefix_rowcount和prefix_read_cost，方便下一次连接比较cost // 如果此次join的cost更小，那么保存到join->best_read 和 join->best_rowcount if (consider_plan(idx, &trace_one_table)) return true; } }}
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::min(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(); }
复制代码
优化器内部有一些优化可以根据需要自己重新定义行为，这就涉及到 optimizer_switch 开关的设置。详细可以设置的 optimizer_switch 如下表所示，以后每个专门开一期细讲。
附表：优化器涉及的 OPTIMIZER_SWITCH 表
三、实际例子说明
接下来看几个例子来说明上面的代码。
greatsql> EXPLAIN SELECT * FROM t3,t1,t2,t1 AS t4,t2 AS t5,t3 AS t6 WHERE t1.c1=t3.ccc1 and t2.cc1=t3.ccc1 AND t1.c1=t4.c1 AND t1.c1=t5.cc1 AND t1.c1=t6.ccc1;+----+-------------+-------+------------+--------+---------------+---------+---------+-----------+------+----------+-------------+| 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 | t4 | NULL | eq_ref | PRIMARY | PRIMARY | 4 | db1.t1.c1 | 1 | 100.00 | NULL || 1 | SIMPLE | t2 | NULL | eq_ref | PRIMARY | PRIMARY | 4 | db1.t1.c1 | 1 | 100.00 | NULL || 1 | SIMPLE | t5 | NULL | eq_ref | PRIMARY | PRIMARY | 4 | db1.t1.c1 | 1 | 100.00 | NULL || 1 | SIMPLE | t3 | NULL | ref | idx3_1 | idx3_1 | 5 | db1.t1.c1 | 1 | 100.00 | NULL || 1 | SIMPLE | t6 | NULL | ref | idx3_1 | idx3_1 | 5 | db1.t1.c1 | 1 | 100.00 | NULL |+----+-------------+-------+------------+--------+---------------+---------+---------+-----------+------+----------+-------------+
-- 看一下枚举顺序："`t1`" -> `t1` `t4` -> `t3` -> `t2` -> `t3` -> `t2` `t5` -> `t3` -> `t3` `t6` -- cost太大不继续计算下一张表，直接开始下一次连接计算 -> `t3` -> `t3` `t6` -> `t3` -> `t3` `t6` `t1` `t4` -> `t1` -> `t3` -> `t2` -> `t3` -> `t2` `t5` -> `t3` -> `t3` `t6` cost太大不继续计算下一张表，直接开始下一次连接计算 -> `t3` -> `t3` `t6` cost太大不继续计算下一张表，直接开始下一次连接计算后面类似，因为太多不写出来了。
-- 层数改为1，看看效果。greatsql> set optimizer_search_depth=1;
-- 发现表的连接顺序跟之前不一样了。greatsql> explain SELECT * FROM t3,t1,t2,t1 as t4,t2 as t5,t3 as t6 where t1.c1=t3.ccc1 and t2.cc1=t3.ccc1 and t1.c1=t4.c1 and t1.c1=t5.cc1 and t1.c1=t6.ccc1;+----+-------------+-------+------------+--------+---------------+---------+---------+-----------+------+----------+-------------+| 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 | t4 | NULL | eq_ref | PRIMARY | PRIMARY | 4 | db1.t1.c1 | 1 | 100.00 | NULL || 1 | SIMPLE | t3 | NULL | ref | idx3_1 | idx3_1 | 5 | db1.t1.c1 | 1 | 100.00 | NULL || 1 | SIMPLE | t2 | NULL | eq_ref | PRIMARY | PRIMARY | 4 | db1.t1.c1 | 1 | 100.00 | NULL || 1 | SIMPLE | t5 | NULL | eq_ref | PRIMARY | PRIMARY | 4 | db1.t1.c1 | 1 | 100.00 | NULL || 1 | SIMPLE | t6 | NULL | ref | idx3_1 | idx3_1 | 5 | db1.t1.c1 | 1 | 100.00 | NULL |+----+-------------+-------+------------+--------+---------------+---------+---------+-----------+------+----------+-------------+
`t1` cost最小，选这个继续走`t1` `t4``t3``t2``t2` `t5``t3` `t6``t1` -> `t1` `t4` -> `t3` -> `t2` -> `t2` `t5` -> `t3` `t6` cost最小，选这个继续走 -> `t3` `t6` -> `t2` `t5` -> `t3` `t6` -> `t2` -> `t2` `t5` -> `t3` `t6` -> `t3` -> `t2` -> `t2` `t5` -> `t3` `t6`
复制代码
四、总结
从上面优化器的步骤我们认识了贪婪算法的过程，知道了 2 个基本参数 search_depth 和 prune_level，这两个参数可以自定义设置值用来简化算法的步骤，减少资源的消耗，但是也会相应的导致最后结果不精确，所以还是要按照个人需求进行设置。
划线
评论
复制
发布于: 刚刚阅读数: 3
GreatSQL
关注
GreatSQL社区 2023-01-31 加入
GreatSQL是由万里数据库维护的MySQL分支，专注于提升MGR可靠性及性能，支持InnoDB并行查询特性，是适用于金融级应用的MySQL分支版本。 社区：https://greatsql.cn/ Gitee: https://gitee.com/GreatSQL/GreatSQL
评论