【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，这两个参数可以自定义设置值用来简化算法的步骤，减少资源的消耗，但是也会相应的导致最后结果不精确，所以还是要按照个人需求进行设置。