除了单表的查询SQL语句，还有两大类相对复杂的SQL，多表JOIN和子查询语句，这就要在多张表上创建索引，难度相对提升不少。
接下来，我们就来关注JOIN的工作原理，了解JOIN实现的算法和应用场景。
JOIN连接算法
MySQL8.0版本支持两种JOIN算法用于表之间的关联：
- Nested Loop Join
- Hash Join
通常认为，在OLTP业务中，因为查询数据量小，语句相对简单，大多使用索引连接表之间的数据。这种情况下，优化器大多会用Nested Loop Join算法；而OLAP业务中的查询数量较大，关联的数量非常多，所以用Hash Join算法，直接扫描全表效率会更高。
注意：这里仅讨论最新的MySQL 8.0 版本中的JOIN连接算法，同时也推荐你在生产环境优先使用MySQL 8.0版本。
Nested Loop Join
Nested Loop Join 之间的表关联是使用索引进行匹配的，假设表R和S进行连接，其算法伪代码大致如下：
for each row r in R with matching condition:
lookup index idx_s on S where index_key = r
if (found)
send to client
在上述算法中，表 R 被称为驱动表，表 R 中通过 WHERE 条件过滤出的数据会在表 S 对应的索引上进行一一查询。如果驱动表 R 的数据量不大，上述算法非常高效。
接着，我们看一下，以下三种 JOIN 类型，驱动表各是哪张表：
SELECT ... FROM R LEFT JOIN S ON R.x = S.x WEHRE ... -- 驱动表就是左表 R
SELECT ... FROM R RIGHT JOIN S ON R.x = S.x WEHRE ... -- 驱动表就是右表 S
SELECT ... FROM R INNER JOIN S ON R.x = S.x WEHRE ... -- 驱动表可能是表 R，也可能是表 S,取决于谁需要查询的数据量越少，谁就是驱动表
看下面这个例子：
SELECT ... FROM R INNER JOIN S
ON R.x = S.x
WHERE R.y = ? AND S.z = ?
上面这条 SQL 语句是对表 R 和表 S 进行 INNER JOIN，其中关联的列是 x，WHERE 过滤条件分别过滤表 R 中的列 y 和表 S 中的列 z。那么这种情况下可以有以下两种选择：
伪代码
优化器一般认为，通过索引进行查询的效率都一样，所以Nested Loop Join算法主要要求驱动表的数量要尽可能少。所以如果WHERE R.y = ?过滤出的数据少，那么这条SQL语句先用表R上列y上的索引，筛选出数据，然后再使用表S上列x的索引进行关联，最后再通过WHERE S.z = ?过滤出最后数据。
为了深入理解优化器驱动表的选择，咱们先来看下面这条SQL：
SELECT COUNT (1)
FROM orders
INNER JOIN lineitem
ON orders.o_orderkey = lineitem.l_orderkey
WHERE orders.o_orderdate >= '1994-02-01' AND orders.o_orderdate <= '1994-03-01';
上面的表 orders 你比较熟悉，类似于电商中的订单表，在我们的示例数据库中记录总量有 600万条记录。
表 lineitem 是订单明细表，比如一个订单可以包含三件商品，这三件商品的具体价格、数量、商品供应商等详细信息，记录数约 2400 万。
上述 SQL 语句表示查询日期为 1994 年 2 月购买的商品数量总和，你通过命令 EXPLAIN 查看得到执行计划如下所示：
mysql> EXPLAIN FORMAT=tree SELECT COUNT(1) FROM orders INNER JOIN lineitem ON orders.o_orderkey = lineitem.l_orderkey WHERE orders.o_orderdate >= '1994-02-01' AND orders.o_orderdate <= '1994-03-01';
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| -> Aggregate: count(1)
-> Nested loop inner join (cost=220946.49 rows=570955)
-> Filter: ((orders.O_ORDERDATE >= DATE'1994-02-01') and (orders.O_ORDERDATE <= DATE'1994-03-01')) (cost=27545.32 rows=137136)
-> Index range scan on orders using idx_orderdate (cost=27545.32 rows=137136)
-> Index lookup on lineitem using PRIMARY (l_orderkey=orders.o_orderkey) (cost=0.99 rows=4)
|
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)
上面的执行计划步骤如下，表orders是驱动表：
- Index range scan on orders using idx_orderdate (cost=27545.32 rows=137136) ：使用索引 idx_orderdata 过滤出1994 年 2 月的订单数据，预估记录数超过 13 万。
- Index lookup on lineitem using PRIMARY (l_orderkey=orders.o_orderkey)：将第一步扫描的结果作为驱动表，然后将驱动表中的每行数据的 o_orderkey 值，在 lineitem 的主键索引中进行查找。
- Nested loop inner join (cost=115366.81 rows=549152)进行 JOIN 连接，匹配得到的输出结果。
- Aggregate: count(1)：统计得到最终的商品数量。
但若执行下面这条SQL，则执行计划就有了变化：
mysql> EXPLAIN FORMAT=tree SELECT COUNT(1) FROM orders INNER JOIN lineitem ON orders.o_orderkey = lineitem.l_orderkey WHERE orders.o_orderdate >= '1994-02-01' AND orders.o_orderdate <= '1994-03-01' AND lineitem.l_partkey = 620758;
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| -> Aggregate: count(1)
-> Nested loop inner join (cost=46.65 rows=2)
-> Index lookup on lineitem using idx_partkey (L_PARTKEY=620758) (cost=4.85 rows=38)
-> Filter: ((orders.O_ORDERDATE >= DATE'1994-02-01') and (orders.O_ORDERDATE <= DATE'1994-03-01')) (cost=1.00 rows=0)
-> Single-row index lookup on orders using PRIMARY (o_orderkey=lineitem.l_orderkey) (cost=1.00 rows=1)
|
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.01 sec)
上述 SQL 只是新增了一个条件 lineitem.l_partkey =620758，即查询 1994 年 2 月，商品编号为 620758 的商品购买量。
这时若仔细查看执行计划，会发现通过过滤条件 l_partkey = 620758 找到的记录大约只有 38 条，因此这时优化器选择表 lineitem 为驱动表。
Hash Join
MySQL中的第二种JOIN算法是Hash Join，用于两张表之间关联条件没有索引的情况。
有同学会提问，没有索引，创建索引不就可以了吗？或许可以，但：
- 如果有些列是低选择性的，那么创建索引再导入数据时要对数据排序，影响导入性能
- 二级索引会有回表问题，若筛选的数量比较大，则直接全表扫描会更快
对于OTAP业务查询来说，Hash Join是必不可少的功能，MySQL 8.0 版本开始支持Hash Join算法，加强了对于OLAP业务的支持。
所以如果你的查询数据量不是特别大，对于查询的响应实践要求为分钟级别，完全可以使用单个实例MySQL 8.0 来完成大数据的查询工作。
Hash Join算法的伪代码如下：
foreach row r in R with matching condition:
create hash table ht on r
foreach row s in S with matching condition:
search s in hash table ht:
if (found)
send to client
Hash Join会扫描关联的两张表：
- 首先会在扫描驱动表的过程中创建一张哈希表；
- 接着扫描第二张表时，会在哈希表中搜索每条关联的记录，如果找到就返回记录。
Hash Join 选择驱动表和 Nested Loop Join 算法大致一样，都是较小的表作为驱动表。如果驱动表比较大，创建的哈希表超过了内存的大小，MySQL 会自动把结果转储到磁盘。
为了演示 Hash Join，接下来，我们再来看一个 SQL：
SELECT
s_acctbal,
s_name,
n_name,
p_partkey,
p_mfgr,
s_address,
s_phone,
s_comment
FROM
part,
supplier,
partsupp,
nation,
region
WHERE
p_partkey = ps_partkey
AND s_suppkey = ps_suppkey
AND p_size = 15
AND p_type LIKE '%BRASS'
AND s_nationkey = n_nationkey
AND n_regionkey = r_regionkey
AND r_name = 'EUROPE';
上面这条 SQL 语句是要找出商品类型为 %BRASS，尺寸为 15 的欧洲供应商信息。
因为商品表part 不包含地区信息，所以要从关联表 partsupp 中得到商品供应商信息，然后再从供应商元数据表中得到供应商所在地区信息，最后在外表 region 连接，才能得到最终的结果。
最后的执行计划如下图所示：
执行计划
从上图可以发现，最早进行连接的是表supplier和nation，接着再和表pastsupp连接，然后和part表连接，再和表part连接，上述左右链接算法都是Nested Loop Join，这时的结果记录大概有79330条。
最后和表region进行关联，表region过滤得到结果5条，这时有两种选择：
- 在793300条记录上创建基于region索引，然后在内表通过索引进行查询；
- 对表region创建哈希表，793300条记录在哈希表中进行探测
选择1就是MySQL8.0 不支持Hash Join时优化器的处理方式，缺点是：如关联的数据量非常大，创建索引需要时间；其次可能需要回表，优化器大概率会选择直接扫描内表。
选择2只对大约5条记录的表region创建哈希索引，时间几乎可以忽略不计，其次直接选择对内表扫描，没有回表问题，很明显，MySQL8.0会选择Hash Join。
了解优化器的选择后，看一下命令EXPLAIN FORMAT=tree执行计划的结果：
mysql> EXPLAIN FORMAT=tree SELECT s_acctbal, s_name, n_name, p_partkey, p_mfgr, s_address, s_phone, s_comment FROM part, supplier, partsupp, nation, region WHERE p_partkey = ps_partkey AND s_suppkey = ps_suppkey AND p_size = 15 AND
p_type LIKE '%BRASS'
+------------------------------------------------------------------------------------------------------+
| EXPLAIN |
+------------------------------------------------------------------------------------------------------+
| -> Nested loop inner join (cost=110338.93 rows=78)
-> Nested loop inner join (cost=101518.04 rows=390)
-> Nested loop inner join (cost=92395.71 rows=390)
-> Inner hash join (no condition) (cost=83873.38 rows=98)
-> Filter: ((part.P_SIZE = 15) and (part.P_TYPE like '%BRASS')) (cost=83872.63 rows=8796)
-> Table scan on part (cost=83872.63 rows=791706)
-> Hash
-> Filter: (region.R_NAME = 'EUROPE') (cost=0.75 rows=1)
-> Table scan on region (cost=0.75 rows=5)
-> Index lookup on partsupp using PRIMARY (ps_partkey=part.p_partkey) (cost=0.96 rows=4)
-> Single-row index lookup on supplier using PRIMARY (s_suppkey=partsupp.PS_SUPPKEY) (cost=0.26 rows=1)
-> Filter: (nation.N_REGIONKEY = region.r_regionkey) (cost=0.25 rows=0)
-> Single-row index lookup on nation using PRIMARY (n_nationkey=supplier.S_NATIONKEY) (cost=0.25 rows=1)
|
+------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)
以上就是 MySQL 数据库中 JOIN 的实现原理和应用了。
因为很多开发同学在编写 JOIN 时存在困惑，所以接下来我就带你深入 OLTP 业务中的JOIN问题。
OLTP业务能不能写JOIN
OLTP 业务是海量并发，要求响应非常及时，在毫秒级别返回结果，如淘宝的电商业务、支付宝的支付业务、美团的外卖业务等。
如果 OLTP 业务的 JOIN 带有 WHERE 过滤条件，并且是根据主键、索引进行过滤，那么驱动表只有一条或少量记录，这时进行 JOIN 的开销是非常小的。
比如在淘宝的电商业务中，用户要查看自己的订单情况，其本质是在数据库中执行类似如下的 SQL 语句：
SELECT o_custkey, o_orderdate, o_totalprice, p_name FROM orders,lineitem, part
WHERE o_orderkey = l_orderkey
AND l_partkey = p_partkey
AND o_custkey = ?
ORDER BY o_orderdate DESC
LIMIT 30;
发现很多开发同学会以为上述 SQL 语句的 JOIN 开销非常大，因此认为拆成 3 条简单 SQL 会好一些，比如：
SELECT * FROM orders
WHERE o_custkey = ?
ORDER BY o_orderdate DESC;
SELECT * FROM lineitem
WHERE l_orderkey = ?;
SELECT * FROM part
WHERE p_part = ?
其实你完全不用人工拆分语句，因为你拆分的过程就是优化器的执行结果，而且优化器更可靠，速度更快，而拆成三条 SQL 的方式，本身网络交互的时间开销就大了 3 倍。
所以，放心写 JOIN，你要相信数据库的优化器比你要聪明，它更为专业。上述 SQL 的执行计划如下：
mysql> EXPLAIN FORMAT=tree SELECT o_custkey, o_orderdate, o_totalprice, p_name FROM orders,lineitem, part WHERE o_orderkey = l_orderkey AND l_partkey = p_partkey AND o_custkey = '147601' ORDER BY o_orderdate DESC LIMIT 30;
+----------------------------------------------------------------------------------------------------+
| EXPLAIN |
+----------------------------------------------------------------------------------------------------+
| -> Limit: 30 row(s) (cost=102.38 rows=30)
-> Nested loop inner join (cost=102.38 rows=79)
-> Nested loop inner join (cost=47.98 rows=79)
-> Index lookup on orders using idx_custkey_orderdate (O_CUSTKEY=147601; iterate backwards) (cost=20.89 rows=19)
-> Index lookup on lineitem using PRIMARY (l_orderkey=orders.o_orderkey) (cost=1.03 rows=4)
-> Single-row index lookup on part using PRIMARY (p_partkey=lineitem.L_PARTKEY) (cost=0.59 rows=1)
|
+---------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)
由于驱动表的数据是固定 30 条，因此不论表 orders、lineitem、part 的数据量有多大，哪怕是百亿条记录，由于都是通过主键进行关联，上述 SQL 的执行速度几乎不变。
所以，OLTP 业务完全可以大胆放心地写 JOIN，但是要确保 JOIN 的索引都已添加， DBA 们在业务上线之前一定要做 SQL Review，确保预期内的索引都已创建。
总结
MySQL数据库中支持JOIN连接的算法有Nested Loop Join和Hash Join两种，前者通常用于OLTP业务，后者用于OLAP业务，在OLTP业务中可以写JOIN，优化器会自动选择最优的执行计划。但若使用JOIN，要确保SQL的执行计划使用了正确的索引及索引覆盖，因此索引设计显得尤其重要，这也是DBA在架构设计方面的重要工作之一
网友评论