## 1. 背景
对于连续的 JOIN，imci 的 join order 目前是直接翻译使用 mysql 优化器生成的 join order，但是翻译过程中没有保留 join 以及 join 的 children 的 cardinality （结果集大小）信息，而 join 的两个 children 的 cardinality 判断对 HashJoin 算子的影响比较大，且 imci 主要依赖 HashJoin 算子来进行 equal join 运算，因此我们现在尝试在翻译 mysql 优化器生成的执行计划时（Ast2Opt）拿到这个信息。
在 8013 版本的 mysql server 中，由于没有 hash join 的实现，主要依赖 index join + block nested loop join 的方式，在这种执行方式下，mysql 优化器在枚举生成 join 执行计划时，保留了许多 cardinality 的信息，而且也会尽量选择执行中间结果更小的执行计划，但是并不关心 join 的左右 children 的大小，而更关心每个表的 access path 选择（i.e., 访问这个表时能否用上索引，索引能否覆盖所需要的列，等），出于这个原因，在翻译执行计划时，是比较难拿到 join 的左右 children 的大小信息的。
在单机 IMCI 里，我们主要依赖 hashjoin 算法来实现 equal join 运算，而 hash join 算法分为 hash build + hash probe 两部分，从执行效率角度出发， 我们需要用更小的边来进行 hash build，用更大的边来进行 hash probe；目前由于优化器没有这个信息，目前我们是通过阻塞 hash join 两边 children 来拿到准确的大小的。
在 IMCI 多机形态中，枚举 hash join 的多机执行计划时也需要估计左右两边大小以选择 broadcast + round-robin partition 或者 hash repartition + hash repartition 的执行方式，目前没有这个信息，因此是没法做这个选择的。
## 2. 过渡方案
IMCI 的优化器还在开发中，目前看稳定可用还需要一定时间，而且在 HTAP 场景中 mysql 优化器也不能完全被替代，因此我们梳理了一下 mysql 的实现，尝试在翻译 mysql 优化器生成的执行计划中拿到预估的 cardinality 信息。
目前暂时的结论是：
1. 在某些场景中，是可以拿到 mysql 的 best join tree 的每个节点的 cardinality 估算的；
2. 根据前面一些客户场景的经验，很多 HTAP 场景的 query，是有非常多的 key 信息作为辅助的，这种情况下的 cardinality 估算是比较准确的；
3. 在没有可用的索引信息时，mysql 的 cardinality 估算采用启发式的方法估算，可能非常不准确，IMCI 还是需要采用阻塞的 join 的 children 的方式获得 hash join 左右表的大小；
4. TPCH 的 query，因为至少都有 PK，所以不少 query 的估计是比较准确的；多机的执行计划选择，可以暂时用得上；
## 3. mysql 如何表示一个 join tree
mysql 生成的 join tree 是一棵左深树，而且只有 left join 没有 right join，从 explain 的输出中，可以非常直观地看到这个 join tree 的形状，以及 join tree 中每个表的访问方式（access path / access method）。
mysql 的表的访问方式主要有如下几种（[https://dev.mysql.com/doc/internals/en/optimizer-determining-join-type.html](https://dev.mysql.com/doc/internals/en/optimizer-determining-join-type.html)）：
- **system**: 访问系统表；
- **const**: 访问常量表；常量表是指输出 0 或 1 行数据的表，目前看只有下面几种：
- 通过 (SELECT 1) 这种方式输出的表
- 优化时通过直接查询索引确定只有 0 或 1 行数据的表，比如 xxx inner join (select a from t1 where t1.pk = 1) 由于 t1.pk 是 primary key，优化器可以确定这个 select 只会输出 0 或 1 行；实际上 mysql 在优化过程中会直接执行这个 select 拿到一个准确的结果；
- 对于 scalar aggr 这种确定会输出一行的查询
- **eq_ref**: 通过等值条件访问 unique key (包括 primary key)；
- **ref**: 通过等值条件访问 non-unique key，且这个 key 不包含 NULL 值；
- **ref_or_null**: 与 ref 类似，但是 key 可以包含 NULL 值；
- **range**: 通过 BETWEEN, IN, >=, LIKE 等 range 条件访问索引
- **index**: 扫描覆盖索引；
- **ALL**: 全表扫描；与index 的区别应该是，ALL 是 clustered index 的 full index，index 可以是 clustered index 也可以是其他覆盖索引；
举例说明 1：
在这个例子中，这个 join 的执行方式是：
1. 通过 PRIMARY KEY 扫描 t1，取出所有列
2. 对于 t1 中的每一行，使用 t1.a 的值，通过 eq_ref 的访问方式（unique key 查询）访问 t2
举例说明 2:
在这个例子中，这个 join 的执行方式是：
1. 通过 PRIMARY KEY 扫描 t1，取出 t1.a 列
2. 对于 t1 中的每一行，使用 t1.a 的值，通过 eq_ref 的访问方式（unique key 查询）访问 t2
这个例子与上面例子 1 的区别是 t1 的访问方式：一个是 ALL 访问方式，一个是 INDEX 访问方式。这个区别的原因是，前者是 SELECT * ，需要输出全表，因此是 ALL 访问方式；后者是 SELECT COUNT(1)，只需要 t1.a 来访问 t2，因此是 INDEX 的访问方式；
举例说明 3:
在这个例子中，这个 join 的执行方式是：
1. 通过 PRIMARY KEY 扫描 t1，取出所有列
2. 通过 t1.b = 2 过滤 t1 的行，如果符合条件则回到步骤 1，否则继续下一步
3. 对于 t1 中没有过滤掉的行，使用 t1.a 的值，通过 eq_ref 的访问方式（unique key 查询）访问 t2
4. 对于 3 中匹配的行，使用 t2.b = 2 过滤，如果符合条件，则输出
举例说明 4:
在这个例子中，这个 join 的执行方式是：
1. 通过 PRIMARY KEY 扫描 t1，取出 t1.a 列
2. 对于 t1 中的每一行，使用 t1.a 的值，通过 eq_ref 的访问方式（unique key 查询）访问 t2；如果不命中则回到 1，如果命中则继续下一步
3. 对于 2 中命中的行，使用 t1.a 的值，通过 eq_ref 的访问方式（unique key 查询）访问 t3
## 3. mysql 如何优化生成一个 join tree
mysql 优化器的优化生成最佳 join order 的方式是 bottom-up 的动态规划算法，在搜索时，限制 join tree 是一棵左深树，而且可以通过 optimizer_search_depth 变量限制搜索的深度（因此不是完全的动态规划，而且一个贪心算法），搜索深度最大是 64（因此搜索过程中可以使用 uint64_t 来表示很多表/索引）。
假设有 N 个表的连续 join，则这个深度优先的搜索过程可以用伪代码描述如下（[https://dev.mysql.com/doc/internals/en/optimizer-joins-access-methods.html](https://dev.mysql.com/doc/internals/en/optimizer-joins-access-methods.html)）：
```sql
init:
remaining_tables = {t1, ..., tn}; /* all tables referenced in a query */
partial_plan = NULL
partial_plan_cost = 0
best_plan_so_far = NULL
best_plan_so_far = infinite
procedure find_best(
partial_plan in, /* in, partial plan of tables-joined-so-far */
partial_plan_cost, /* in, cost of partial_plan */
remaining_tables, /* in, set of tables not referenced in partial_plan */
best_plan_so_far, /* in/out, best plan found so far */
best_plan_so_far_cost)/* in/out, cost of best_plan_so_far */
{
for each table T from remaining_tables
{
cost = calculate_cost_of_joining_T();
/* Add the cost to the cost so far. */
partial_plan_cost+= cost;
if (partial_plan_cost >= best_plan_so_far_cost)
/* partial_plan_cost already too great, stop search */
continue;
partial_plan= expand partial_plan by best_access_method;
remaining_tables= remaining_tables - table T;
if (remaining_tables is not an empty set)
{
find_best(partial_plan, partial_plan_cost,
remaining_tables,
best_plan_so_far, best_plan_so_far_cost);
}
else
{
best_plan_so_far_cost= partial_plan_cost;
best_plan_so_far= partial_plan;
}
}
}
```
目前 8013 中这块代码的入口是 Optimize_table_order::choose_table_order()；上面的 find_best() 函数对应代码里的 Optimize_table_order::best_extension_by_limited_search();
## 4. mysql best join tree 的关键信息
mysql 的优化是以 query block 为单位的，一个 query block （一个 SELECT）对应一个 SELECT_LEX。
> mysql AST 的表示可以看这个文档 [https://yuque.antfin-inc.com/nituizi/oncxfu/oqge5m#EdRoG](https://yuque.antfin-inc.com/nituizi/oncxfu/oqge5m#EdRoG)，以及 sql/sql_lex.h 内 class SELECT_LEX_UNIT 上方的注释
一个 SELECT_LEX 优化后对应一个 JOIN 对象，JOIN 对象里的 JOIN::qep_tab 数组即最佳 join order（QEP 即“query execution plan" 的意思）：
每个 QEP_TAB 内部都有一个 POSITION 对象，POSITION 里面包含了 join tree 中每一个 JOIN 的信息：
```sql
struct POSITION {
/**
对于前面的 join 结果中的一行，join 当前表时会输出多少行
*/
double rows_fetched;
/*
join 当前表后，输出的行里面，有多少能通过过滤条件
*/
float filter_effect;
/*
前面的 join 的结果集的预估大小
*/
double prefix_rowcount;
};
```
对于上面的例子 3 来说：
positions[0] 的信息是：
```sql
/*
单独一个表 t1 可以看作一个特殊的 join；
这个 row_fetch 是通过 ALL 方式访问 t1 的结果集大小；
*/
positions[0].rows_fetched = 2
/*
t1.b = 2 可以过滤掉一半的行
*/
positions[0].filter_effect = 50%
/*
prefix_rowcount =
last_table.prefix_rowcount * rows_fetched * filter_effect
*/
positions[0].prefix_rowcount = 2 * 50% = 1;
```
positions[1] 的信息是：
```sql
/*
对于前面的 JOIN （t1 表）的每一行，t2 表会输出 1 行（访问 t2 表是 eq_ref 的访问方式）；
*/
positions[1].rows_fetched = 1
/*
eq_ref 访问 t2 后，再使用 t2.b = 2 过滤，预估过滤后剩下 1/4 的行；
*/
positions[1].filter_effect = 25%
/*
prefix_rowcount =
last_table.prefix_rowcount * rows_fetched * filter_effect
*/
positions[1].prefix_rowcount
= positions[0].prefix_rowcount * positions[1].rows_fetched * positions[1].filter_effect
= 1 * 1 * 25%
= 0.25
```
对于下面的例子来说
positions 信息是：
```sql
positions[0].rows_fetched = 2
positions[0].filter_effect = 100%
positions[0].prefix_rowcount = 2 * 100% = 2;
positions[1].rows_fetched = 1;
positions[1].filter_effect = 33.33%
positions[1].prefix_rowcount = 2 * 1 * 33.33% = 0.66
positions[2].rows_fetch = 1;
positions[2].filter_effect = 33.33%
positions[2].prefix_rowcount = 0.66 * 1 * 33.33% = 0.22
```
## 5. 如何从 mysql best join tree 获取 cardinallity 估计
### 5.1 filter_effect && IMCI filter pushdown
以上面的 4. 中的最后一个例子为例：
对于这个例子来说，生成一棵这样的左深树：
```sql
filter_2
(t3.b > 0)
|
join_2
(t1.a eq_ref t3)
/ \
/ t3
filter_1
(t2.b > 0)
|
join_1
(t1.a eq_ref t2)
/ \
t1, index t2
```
对于这棵树来说，可以直接知道这些节点的结果集大小：
1. t1 的结果集大小，即 positions[0].rows_fetched = 2
2. join_1 的结果集大小，即 positions[0].prefix_rowcount * positions[1].rows_fetched = 2 * 1 = 2
3. filter_1 的结果集大小，即 positions[0].prefix_rowcount * positions[1].rows_fetched * positions[1].filter_effect = 2 * 1 * 33.33% = 0.66
4. join_2 的结果集大小，即 positions[1].prefix_rowcount * positions[2].rows_fetched = 0.66 * 1 = 0.66
5. filter_2 的结果集大小，即 positions[1].prefix_rowcount * positions[2].rows_fetched * positions[2].filter_effect = 0.66 * 1 * 33.33% = 0.22
因此，左深树的**所有 join 的左边的 children 的结果集大小，都是可以直接拿到的**，我们需要解决右边 children 的问题，i.e., 需要拿到 t2.b 的 output size；
在 IMCI 里，上面的左深树会被翻译成如下的左深树，即所有的 filter 都会被推到 table scan 上：
```sql
|
join_2
(t1.a eq_ref t3)
/ \
/ t3
/ (t3.b > 0)
join_1
(t1.a eq_ref t2)
/ \
t1, index t2
(t2.b > 0)
```
在这个例子里，positions[1].filter_effect 对应 t2.b > 0 的过滤效果，positions[2].filter_effect 对应 t3.b > 0 的过滤效果，因此，TableScan(t2), t2.b > 0 这个 table scan 的结果集等于 t2_size * positions[1].filter_effect；
> 在 mysql 优化器中，join 上方的 filter 的 filter_effect 与 join 自身的选择率没有相关性，i.e., join 上方的 filter_effect 可以直接应用在 t2 上；
对于这种 case 可以用这样的方式解决，拿到 mysql 优化器对整个 join tree 的所有节点的预估结果集大小。
当然，这个方案是存在几个问题的：
### 5.2 对于没有 key 信息，也没有 histogram 统计信息的列，mysql 优化器直接使用了几个 magic number 来估算选择率
比如下面 >= 的比较中（Item_func_ge 是实现 >= 的表达式）：
如果这个列没有 histogram 的统计信息，则默认返回 max((1/max_distinct_values), COND_FILTER_INEQUALITY)：
max_distinct_values 一般是表的大小，COND_FILTER_INEQUALITY 是 0.3333：
总共有 4 个默认值，其中 3 个 magic number。
当然，没有可用索引以及可用的统计信息时，直接使用 magic number 来估计，是业界比较常见的做法。
但是从 IMCI 的层面考虑，如果这个估算是不准确的，那么 IMCI 无法使用这个估算来进行 join 的左右表的大小判断。又由于 mysql 的 histogram 采集是默认不打开的，因此可以说，**在不使用索引的 join 的情况下，mysql 优化器吐出的结果集大小估算，是不可信的，imci 的执行器还是需要阻塞 hash join 的左右孩子**。
### 5.3 POSITION 中的 filter_effect 是可能带 join 条件的，直接使用 filter_effect 作为单表的选择率，会导致较低的估值
上文 5 中的例子，其实是简化的例子，在这个例子中的两个 join 的 filter_effect 都是**仅对应一个单表过滤条件**：
但是实际上 filter_effect 对应的选择率，是可以包含 join 条件，下面举例说明。
这个例子与上文 5.1 中的例子类似，查询也一样，不同的地方在于，这里 t3 是没有可用的 KEY 的，因此这个 3 表 join 的执行方式稍有不同：
1. 通过 primary key 扫描 t1，取出 t1.a 列
2. 通过 ALL 方式读 t1 的行，i.e., 全表扫描，然后用 nested loop join 的方式进行 join 运算，笛卡尔积，然后使用 t1.a = t3.a and t3.b > 0 过滤，优化器预估这个过滤条件的 filter_effect （选择率）是 20%；
3. 对于 2. 中没有被过滤的行，使用 t1.a 的值，通过 eq_ref 的访问方式（unique key 查询）访问 t2；
这个例子中的 SQL 与 5.1 中相同，因此在 IMCI 中，相同的 filter 会推到相同的表上。但是由于 t1 与 t3 是先笛卡尔积然后再应用 （t1.a = t3.a and t3.b > 0) 这个过滤条件，因此 t3 这个 position 上对应的 filter_effect 是（t1.a = t3.a and t3.b > 0) 的 filter_effect，因此这个选择率，与 TableScan(t3), t3.b > 0 的选择率是不一样的。
> 即使 t3 有可用 KEY，也能举出其他例子，比如 join 谓词是 (t1.a = t3.a and t1.b > t3.b and t3.c > 0），此时可能 t1.a = t3.a 是 eq_ref，(t1.b > t3.b and t3.c > 0) 对应 filter_effect。
所以，
- 严格来说，只有某些场景下，filter_effect 可以直接当作某个表的选择率；
- 在 join 的结果估算比较准确的情况下，将这种带 join 条件的 filter_effect 直接作为某个表的选择率，是一种 under estimate，可以做一点"补偿"，也未必不可行；
## 结论
暂时的结论是：
1. 在某些场景中，是可以拿到 mysql 的 best join tree 的每个节点的 cardinality 估算的；
2. 根据前面一些客户场景的经验，很多 HTAP 场景的 query，是有非常多的 key 信息作为辅助的，这种情况下的 cardinality 估算是比较准确的；
3. 在没有可用的索引信息时，mysql 的 cardinality 估算采用启发式的方法估算，可能非常不准确，IMCI 还是需要采用阻塞的 join 的 children 的方式获得 hash join 左右表的大小；
4. TPCH 的 query，因为至少都有 PK，所以不少 query 的估计是比较准确的；多机的执行计划选择，可以暂时用得上；
