深入了解行业动态与专业知识
MySQL 在 8.0.18 中引入 hash join这是一个为 join 查询语句设计的高效算法。今天来介绍一下 hash join。1.简介首先我们建立两张表SQL 如下CREATE TABLE t1 (c1 INT, c2 INT); CREATE TABLE t2 (c1 INT, c2 INT);再给出一个连接查询 SQLSELECT * FROM t1 JOIN t2 ON t1.c1t2.c1;那 hash join 的执行过程是怎样的呢1.确定驱动表MySQL 会选择结果集较小的表作为驱动表将结果集加载到内存中2.以连接键为 hash key 构建 hash 表使用链表法解决 hash 冲突。3.对于非驱动表依次扫描每一行数据对 join 字段取 hash 值然后在 2 构建的 hash 表中查找这个 hash 值4.如果找到则对这个 hash 值所在的链表上每个值进行等值比较如果比较结果一致则结合两个表的相关字段生成结果集并输出5.如果找不到则继续扫描下一行。 整个过程如下图hash join 的时间复杂度是多少呢假如 t1 表的记录数是 M扫描 t1 表的时间复杂度是 o(M)t2 表的记录数是 N扫描 t2 表的时间复杂度是 o(N)hash 表查询的复杂度是 o(1)这样使用 hash join 查找的总时间复杂度是 o(M N)。2.优势在上面的例子中t1 表和 t2 表都没有加索引如果做 join 查询在 MySQL 8.0 以前会使用 BNL 算法。BNL 算法流程如下1.把 t1 表的数据读出放到 join_buffer2.扫描 t2 表中的每一行用 c1 字段值跟 join_buffer 中 t1 表的 c1 字段值做比较3.如果 c1 值一样则作为结果集返回如果不一样则继续扫描 t2 表下一行。join_buffer 是一个无序数组t2 表中的每一行都需要跟 t1 表的所有记录做比对。假如 t1 表的数据量是 Mt2 表的数据量是 N则需要比对的次数是 M * N也就是说时间复杂度是 o(M*N)。从时间复杂度可以明显看出 hash join 的优势。从 MySQL 8.0.20 开始不再支持 BNL 算法server 在原先使用 BNL 算法的地方使用 hash join。3.hash join 优化MySQL 8.0.18 引入 hash join主要用于 join 语句中有等值条件并且 join 条件中不能使用索引的场景。比如前面例子中的 join 语句t1 和 t2 的 c1 字段都没有索引SELECT * FROM t1 JOIN t2 ON t1.c1t2.c1;3.1 配置MySQL 8.0.18 版本中支持设置 hash_joinon 或 hash_joinoff 供优化器选择在 MySQL 8.0.19 及更高版本中这个设置不再生效server 会默认使用 hash join。3.2 连接条件优化优化一在 MySQL 8.0.20 以前如果 join 条件中存在一个非等值匹配的条件就会走 BNL 算法。MySQL 8.0.20 以后即使有非等值条件也会走 hash join。下面 SQL 来自官网mysql EXPLAIN FORMATTREE - SELECT * FROM t1 - JOIN t2 ON (t1.c1 t2.c1) - JOIN t3 ON (t2.c1 t3.c1)\G *************************** 1.row *************************** EXPLAIN: - Filter: (t1.c1 t3.c1) (cost1.05rows1) - Innerhashjoin (no condition) (cost1.05rows1) - Tablescanon t3 (cost0.35rows1) - Hash - Innerhashjoin (t2.c1 t1.c1) (cost0.70rows1) - Tablescanon t2 (cost0.35rows1) - Hash - Tablescanon t1 (cost0.35rows1)优化二即使 join 没有条件也会走 hash joinmysql EXPLAIN FORMATTREE - SELECT * - FROM t1 - JOIN t2 - WHERE t1.c2 50\G *************************** 1.row *************************** EXPLAIN: - Innerhashjoin (cost0.70rows1) - Tablescanon t2 (cost0.35rows1) - Hash - Filter: (t1.c2 50) (cost0.35rows1) - Tablescanon t1 (cost0.35rows1)优化三即使 join 条件中没有等值条件也会走 hash join。下面 5 个示例来自官网都会走 hash join。1.内连接无等值条件mysql EXPLAIN FORMATTREE SELECT * FROM t1 JOIN t2 ON t1.c1 t2.c1\G *************************** 1.row *************************** EXPLAIN: - Filter: (t1.c1 t2.c1) (cost4.70rows12) - Innerhashjoin (no condition) (cost4.70rows12) - Tablescanon t2 (cost0.08rows6) - Hash - Tablescanon t1 (cost0.85rows6)2.半连接mysql EXPLAIN FORMATTREE SELECT * FROM t1 - WHERE t1.c1 IN (SELECT t2.c2 FROM t2)\G *************************** 1.row *************************** EXPLAIN: - Hash semijoin (t2.c2 t1.c1) (cost0.70rows1) - Tablescanon t1 (cost0.35rows1) - Hash - Tablescanon t2 (cost0.35rows1)3.反连接mysql EXPLAIN FORMATTREE SELECT * FROM t2 - WHERE NOT EXISTS (SELECT * FROM t1 WHERE t1.c1 t2.c1)\G *************************** 1.row *************************** EXPLAIN: - Hash antijoin (t1.c1 t2.c1) (cost0.70rows1) - Tablescanon t2 (cost0.35rows1) - Hash - Tablescanon t1 (cost0.35rows1) 1rowinset, 1warning (0.00 sec) mysql SHOWWARNINGS\G *************************** 1.row *************************** Level: Note Code: 1276 Message: Fieldorreferencet3.t2.c1ofSELECT#2 was resolved in SELECT #14.左外连接mysql EXPLAIN FORMATTREE SELECT * FROM t1 LEFTJOIN t2 ON t1.c1 t2.c1\G *************************** 1.row *************************** EXPLAIN: - Lefthashjoin (t2.c1 t1.c1) (cost0.70rows1) - Tablescanon t1 (cost0.35rows1) - Hash - Tablescanon t2 (cost0.35rows1)5.右外连接mysql EXPLAIN FORMATTREE SELECT * FROM t1 RIGHTJOIN t2 ON t1.c1 t2.c1\G *************************** 1.row *************************** EXPLAIN: - Lefthashjoin (t1.c1 t2.c1) (cost0.70rows1) - Tablescanon t2 (cost0.35rows1) - Hash - Tablescanon t1 (cost0.35rows1)4.总结hash join 算法的出现对 join 语句的性能大幅提升MySQL 8.0.20 后对 hash join 的使用又做了进一步的优化使用更加便捷。
