数据库多表连接⽅式介绍－HASH-JOIN
1.概述
  hash join是⼀种数据库在进⾏多表连接时的处理算法，对于多表连接还有两种⽐较常⽤的⽅式：sort merge-join 和 nested loop。为了⽐较清楚的介绍hash join的使⽤场景以及为何要引⼊这样⼀种连接算法，这⾥也会顺带简单介绍⼀下上⾯提到的两种join⽅式。
  连接⽅式是⼀个什么样的概念，或者说我们为何要有⽽且有好⼏种，对于不太了解数据库的⼈来讲可能这些是开头的疑惑。简单来讲，我们将数据存在不同的表中，⽽不同的表有着它们⾃⾝的表结构，不同表之间可以是有关联的，⼤部分实际使⽤中，不会仅仅只需要⼀张表的信息，⽐如需要从⼀个班级表中出杭州地区的学⽣，再⽤这个信息去检索成绩表中他们的数学成绩，如果没有多表连接，那只能⼿动将第⼀个表的信息查询出来作为第⼆个表的检索信息去查询最终的结果，可想⽽知这将会是多么繁琐。
  对于⼏个常见的数据库，像oracle,postgresql它们都是⽀持hash-join的，mysql并不⽀持。在这⽅⾯，oracle和pg都已经做的⽐较完善了，hash-join本⾝的实现并不是很复杂，但是它需要优化器的实现配合才能最⼤的发挥本⾝的优势，我觉得这才是最难的地⽅。
  多表连接的查询⽅式⼜分为以下⼏种：内连接，外连接和交叉连接。外连接⼜分为：左外连接，右外连
接和全外连接。对于不同的查询⽅式，使⽤相同的join算法也会有不同的代价产⽣，这个是跟其实现⽅式紧密相关的，需要考虑不同的查询⽅式如何实现，对于具体使⽤哪⼀种连接⽅式是由优化器通过代价的衡量来决定的，后⾯会简单介绍⼀下⼏种连接⽅式代价的计算。 hashjoin其实还有很多需要考虑和实现的地⽅，⽐如数据倾斜严重如何处理、内存放不下怎⽊办，hash如何处理冲突等，这些并不是本⽂介绍的重点，不再详述，每个拿出来都可以再讲⼀篇了。
  nested loop join
  嵌套循环连接，是⽐较通⽤的连接⽅式，分为内外表，每扫描外表的⼀⾏数据都要在内表中查与之相匹配的⾏，没有索引的复杂度是
O(N*M)，这样的复杂度对于⼤数据集是⾮常劣势的，⼀般来讲会通过索引来提升性能。　
  sort merge-join
  merge join需要⾸先对两个表按照关联的字段进⾏排序，分别从两个表中取出⼀⾏数据进⾏匹配，如果合适放⼊结果集；不匹配将较⼩的那⾏丢掉继续匹配另⼀个表的下⼀⾏，依次处理直到将两表的数据取完。merge join的很⼤⼀部分开销花在排序上，也是同等条件下差于hash join的⼀个主要原因。
2.原理和实现
  简单的对于两个表来讲，hash-join就算讲两表中的⼩表（称S）作为hash表，然后去扫描另⼀个表(称M)的每⼀⾏数据，⽤得出来的⾏数据根据连接条件去映射建⽴的hash表，hash表是放在内存中的，这样可以很快的得到对应的S表与M表相匹配的⾏。
  对于结果集很⼤的情况，merge-join需要对其排序效率并不会很⾼，⽽nested loop join是⼀种嵌套循环的查询⽅式⽆疑更不适合⼤数据集的连接，⽽hash-join正是为处理这种棘⼿的查询⽅式⽽⽣，尤其是对于⼀个⼤表和⼀个⼩表的情况，基本上只需要将⼤⼩表扫描⼀遍就可以得出最终的结果集。
  不过hash-join只适⽤于等值连接，对于>, <, <=, >=这样的查询连接还是需要nested loop这种通⽤的连接算法来处理。如果连接key本来就是有序的或者需要排序，那么可能⽤merge-join的代价会⽐hash-join更⼩，此时merge-join会更有优势。
  好了，废话说了不少了，来讲讲实现，拿⼀条简单的多表sql查询语句来举个栗⼦：select * from t1 join t2 on t1.c1 = t2.c1 where t1.c2 > t2.c2 and t1.c1 > 1。这样⼀条sql进⼊数据库系统中，它是如何被处理和解剖的呢？sql:⿁知道我都经历了些什么。。。
  1.背景知识
  1.第⼀步呢，它需要经历词法以及语法的解析，这部分的输出是⼀颗带有token结点的语法树。
  语法分析，顾名思义这部分只是语法层⾯的剖析，将⼀个string的sql语句处理成为⼀颗有着雏形结构的node tree，每个结点有它们⾃⾝的特殊标识，但是并没有分析和处理这个结点的具体含义和值。
  2. 第⼆步是语义分析和重写处理。
  重写的过程不同的数据库可能有不同的处理，有些可能是跟逻辑执⾏过程放在⼀起，有的则分开。
  这⼀步做完树的形状⼤体上是与语法分析树保持⼀致的，但是此时的结点都携带了⼀些具体的信息，以where后⾯的表达式为例，这颗中缀表达式每⼀个结点都有了⾃⾝的类型和特定的信息，并不关⼼值是什么，这步做完后进⼊改写过程，改写是⼀种逻辑优化⽅式，使得⼀些复杂的sql语句变得更简单或者更符合数据库的处理流程。
  3.优化器处理
  优化器的处理是⽐较复杂的，也是sql模块最难的地⽅，优化⽆⽌境，所以优化器没有最优只有更优。优化器需要考虑⽅⽅⾯⾯的因素既要做的通⽤型很强⼜要保证很强的优化能⼒和正确性。
  优化器最重要的作⽤莫过于路径选择了，对于多表连接如何确定表连接的顺序和连接⽅式，不同的数据库有着不同的处理⽅式，pg⽀持动态规划
算法，表数量过多的时候使⽤遗传算法。路径的确定⼜依赖于代价模型的实现，代价模型会维护⼀些统计信息，像列的最⼤值、最⼩值、NDV和DISTINCT值等，通过这些信息可以计算选择率从⽽进⼀步计算代价。
  回归到正⽂，使⽤哪⼀种连接⽅式就是在这⾥决定的，hash join 对⼤⼩表是有要求的，所以这⾥形成的计划是t1-t2还是t2-t1是不⼀样的，每种连接⽅式有着⾃⾝的代价计算⽅式。
  hash join的代价估算：
  COST = BUILD_COST + M_SCAN_COST + JOIN_CONDITION_COST + FILTER_COST
  简单来看，hash join的代价主要在于建⽴hash表、扫描M表、join条件连接和filter过滤，对于S表和M表都是只需要扫描⼀次即可，filter过滤是指t1.c2>t2.c2这样的条件过滤，对于t1.c1>1这样只涉及单表的条件会被下压，在做连接之前就被过滤了。
  优化器处理过后，会⽣成⼀颗执⾏计划树，真正的实现过程根据执⾏计划的流程操作数据，由低向上地递归处理并返回数据。
  2.hash join的实现
  hash join的实现分为build table也就是被⽤来建⽴hash map的⼩表和probe table，⾸先依次读取⼩表的数据，对于每⼀⾏数据根据连接条件⽣成⼀个hash map中的⼀个元組，数据缓存在内存中，如果内存放不下需要dump到外存。依次扫描探测表拿到每⼀⾏数据根据join condition⽣成hash key映射hash map中对应的元組，元組对应的⾏和探测表的这⼀⾏有着同样的hash key, 这时并不能确定这两⾏就是满⾜条件的数据，需要再次过⼀遍join condition和filter，满⾜条件的数据集返回需要的投影列。
  hash join实现的⼏个细节
  1.hash join本⾝的实现不要去判断哪个是⼩表，优化器⽣成执⾏计划时就已经确定了表的连接顺序，以左表为⼩表建⽴hash table，那对应的代价模型就会以左表作为⼩表来得出代价，这样根据代价⽣成的路径就是符合实现要求的。
  2.hash table的⼤⼩、需要分配多少个桶这个是需要在⼀开始就做好的，那分配多少是⼀个问题，分配太⼤会造成内存浪费，分配太⼩会导致桶数过⼩开链过长性能变差，⼀旦超过这⾥的内存限制，会考虑dump到外存，不同数据库有它们⾃⾝的实现⽅式。
  3.如何对数据hash，不同数据库有着⾃⼰的⽅式，不同的哈希⽅法也会对性能造成⼀定的影响。
3.pg和oracle实测
表结构
SQL>select*from or1;
A        B
---------- ----------
11
22
33
SQL>select*from or2;
A        B C
---------- ---------- --------------------
12 a
23 b
45 d
内连接
SQL>select*from or1 join or2 on or1.a = or2.a;
A        B          A      B C
---------- ---------- ---------- ---------- --------------------
1112 a
2223 b
SQL> explain plan for select*from or1 join or2 on or1.a = or2.a;
Explained.
SQL>SELECT plan_table_output FROM TABLE(DBMS_XPLAN.DISPLAY('PLAN_TABLE'));
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Plan hash value: 738363828
| Id  | Operation      | Name | Rows  | Bytes | Cost (%CPU)| Time      |
---------------------------------------------------------------------------
|0|SELECT STATEMENT  ||3|192|4  (0)|00:00:01|
|*1|  HASH JOIN||3|192|4  (0)|00:00:01|
|2|TABLE ACCESS FULL| OR1  |3|78|2  (0)|00:00:01|
|3|TABLE ACCESS FULL| OR2  |3|114|2  (0)|00:00:01|
---------------------------------------------------------------------------
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1- access("OR1"."A"="OR2"."A")
Note
-----
- dynamic statistics used: dynamic sampling (level=2)
19 rows selected.
左外连接，右外连接
SQL>select*from or1 left join or2 on or1.a = or2.a;
A        B          A      B C
---------- ---------- ---------- ---------- --------------------
1112 a
2223 b
33
SQL> explain plan for select*from or1 left join or2 on or1.a = or2.a;
Explained.
SQL>SELECT plan_table_output FROM TABLE(DBMS_XPLAN.DISPLAY('PLAN_TABLE')); PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Plan hash value: 1456425992
---------------------------------------------------------------------------
| Id  | Operation      | Name | Rows  | Bytes | Cost (%CPU)| Time      |
---------------------------------------------------------------------------
|0|SELECT STATEMENT  ||3|192|4  (0)|00:00:01|
|*1|  HASH JOIN OUTER||3|192|4  (0)|00:00:01|
|2|TABLE ACCESS FULL| OR1  |3|78|2  (0)|00:00:01|
|3|TABLE ACCESS FULL| OR2  |3|114|2  (0)|00:00:01|
---------------------------------------------------------------------------
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1- access("OR1"."A"="OR2"."A"(+))
sql left join 多表连接Note
-----
- dynamic statistics used: dynamic sampling (level=2)
19 rows selected.
全外连接
SQL>select*from or1 full join or2 on or1.a = or2.a;
A        B          A      B C
---------- ---------- ---------- ---------- --------------------
1112 a
2223 b
45 d
33
SQL>SELECT plan_table_output FROM TABLE(DBMS_XPLAN.DISPLAY('PLAN_TABLE')); PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
Plan hash value: 2943417606
--
| Id  | Operation          | Name    | Rows  | Bytes | Cost (%CPU)| Time
|
--------------------------------------------------------------------------------
--
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
|0|SELECT STATEMENT      ||3|192|4  (0)|00:00:01
|
|1|VIEW| VW_FOJ_0 |3|192|4  (0)|00:00:01
|
|*2|  HASH JOIN FULL OUTER||3|192|4  (0)|00:00:01 |
|3|TABLE ACCESS FULL| OR1    |3|78|2  (0)|00:00:01 |
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
|4|TABLE ACCESS FULL| OR2    |3|114|2  (0)|00:00:01 |
--------------------------------------------------------------------------------
-
-
Predicate Information (identified by operation id):
---------------------------------------------------
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------
2- access("OR1"."A"="OR2"."A")
Note
-----
- dynamic statistics used: dynamic sampling (level=2)
20 rows selected.
2.postgresql
表数据量
hudson=# select count(*) from hj1;
count
--------
200022
(1 row)
hudson=# select count(*) from hj2;
count
--------
200000
(1 row)
内连接
hudson=# explain select*from hj1 join hj2 on hj1.a=hj2.a;
QUERY PLAN
------------------------------------------------------------------------
Hash Join  (cost=7338.00..26467.34 rows=430732 width=51)
Hash Cond: (hj1.a = hj2.a)
->  Seq Scan on hj1  (cost=0.00..3467.22 rows=200022 width=25)
->  Hash  (cost=3470.00..3470.00 rows=200000 width=26)
->  Seq Scan on hj2  (cost=0.00..3470.00 rows=200000 width=26) (5 rows)
外连接
外连接使⽤⼤⼩表数据量差别⽐较⼤的两个表，可以清晰的看出hash join是以⼩表作为hash table的。hudson=# explain select * from hj1 full join hj3 on hj1.a=hj3.a;
QUERY PLAN
------------------------------------------------------------------------
Hash Full Join (cost=7335.50..8905.67 rows=200022 width=33)
Hash Cond: (hj3.a = hj1.a)
-> Seq Scan on hj3 (cost=0.00..32.60 rows=2260 width=8)
-> Hash (cost=3467.22..3467.22 rows=200022 width=25)
-> Seq Scan on hj1 (cost=0.00..3467.22 rows=200022 width=25)
(5 rows)
hudson=# explain select * from hj1 left join hj3 on hj1.a=hj3.a;
QUERY PLAN
------------------------------------------------------------------------
Hash Right Join (cost=7335.50..8905.67 rows=200022 width=33)
Hash Cond: (hj3.a = hj1.a)
-> Seq Scan on hj3 (cost=0.00..32.60 rows=2260 width=8)
-> Hash (cost=3467.22..3467.22 rows=200022 width=25)
-> Seq Scan on hj1 (cost=0.00..3467.22 rows=200022 width=25)
(5 rows)
hudson=# explain select * from hj1 right join hj3 on hj1.a=hj3.a;
QUERY PLAN
------------------------------------------------------------------------
Hash Left Join (cost=7335.50..8905.67 rows=5270 width=33)
Hash Cond: (hj3.a = hj1.a)
-
> Seq Scan on hj3 (cost=0.00..32.60 rows=2260 width=8)
-> Hash (cost=3467.22..3467.22 rows=200022 width=25)
-> Seq Scan on hj1 (cost=0.00..3467.22 rows=200022 width=25)
(5 rows)
可以看出，left join为了能够以⼩表建⽴hash table被转换为了right join，同样right join也被改写成left join。 

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。