MySQL JOIN简介

MySQL本身没有常规意义上的执行计划，一般情况就是通过JOIN和QEP_TAB这两个结构组成。QEP_TAB 的全称是Query Execution Plan Table，这个“Table“可以是物理表、内存表、常量表、子查询的结果表等等。作为整个单独JOIN执行计划载体之前还承担着整个执行路径的调用和流转，但是从8.0.20后，全面的生成了独立的Iterator执行器引擎模式。在8.0.22中，又引入了AccessPath概念，真正的生成了独立的执行计划，从而进一步做到了优化过程到树型执行计划，最后到Iterator载体在执行引擎中的执行。

MySQL原始的Join都是依赖于QEP_TAB列表，因为原来MySQL并不支持其他形态的Join结构，只支持左深树，那很容易直接使用数组来表示就可以了。优化器在生成执行计划只需要在QEP_TAB上增加JOIN的属性op_type，就可以递归去使用不同的Join方法和表访问方式了。

  // Operation between the previous QEP_TAB and this one.
  enum enum_op_type {
    // Regular nested loop.
    OT_NONE,

    // Aggregate (GROUP BY).
    OT_AGGREGATE,

    // Various temporary table operations, used at the end of the join.
    OT_MATERIALIZE,
    OT_AGGREGATE_THEN_MATERIALIZE,
    OT_AGGREGATE_INTO_TMP_TABLE,
    OT_WINDOWING_FUNCTION,

    // Block-nested loop (rewritten to hash join).
    OT_BNL,

    // Batch key access.
    OT_BKA
  } op_type = OT_NONE;

Hypergraph Join Optimizer

官方共分了11个Patch来提交对于Join优化器的增强，当然其中包含了对优化器和执行器分离更进一步重构，我们先来看看官方是怎么提交这样的重大重构的。

[Basic] 动态规划查询超图算法（DPhyp-Hypergraph partitioning algorithm） 官方首先实现了基于DPhyp的动态规划查询超图算法，论文可以搜索《Dynamic Programming Strikes Back》。数据库中关于Join ordering算法有很多，引用2，3中的作者已经做了详尽的解释。我这里只做简单的介绍。

每一个Query，都可以定义为一个无向Query Graph，包括查询中的所有关系R1，R2，…，Rn作为节点；连接谓词表达式作为边，如a1 = a2 （a1 ∈ Ri，a2 ∈ Rj）；连接谓词中包含常量会形成自边（self-edge），如a1 = const (a1 ∈ Ri)；大部分的自边在Join算法里是不考虑的，因为它会被下推下图。例如对于 select * from Student s, Attend a, Lecture l, Professor p where s.sno = a.asno and a.alno = l.lno and l.lpno = p.pno and p.pname = ‘Larson’，有如下Query Graph结构：

对于Join Tree，一般会有以下几种：left-deep tree、right-deep tree、zigzag tree和bushy tree。前三种是属于线性Join tree。MySQL之前采取左深树，为了考虑更好的支持Hash Join和NestLoop Join的选择，现在开始考虑Bushy Tree了。为了避免任何时候的笛卡尔积Join，线性Join的Join ordering算法通常很简单。那么为什么要引入复杂的Bushy Tree。假设定义Query(R1, R2, R3)有如下属性，y |R1| = 10, |R2| = 20, |R3| = 20, |R4| = 10, f1,2 = 0.01, f2,3 = 0.5, f3,4 = 0.01。||代表行数，fn,m代表Rn和Rm的选择率，可以看到Bushy Tree有更好的执行效率。

不过遗憾的是，Bushy Tree的搜索可能性非常大：

因此，原始左深树使用的Greedy Heuristics算法，在Bushy Tree下，计算Join Ordering通常使用动态规划算法（DPccp和DPhyp）。

DPccp的算法如下：

但是DPccp有很多限制：复杂谓词，涉及到多个表（R1，R2，R3）做为连接，例如：R1.a + R2.b + R3.c = R4.d + R5.e + R6.f ；只支持inner joins；因此引入了新的基于Hypergraph的算法DPhyp。见下一章详解