Join的实现方式有三种:Nested Loop Join、Merge Join、Hash Join。
Nested Loop Join
外部表(驱动表)每一行按照join条件匹配内部表(输入表)Merge Join
两个表按照关联字段排序,然后进行merge join操作:从每个表中取一条记录进行匹配,符合条件放入结果集,不符合则将关联字段小的记录抛弃,取下一条匹配。Hash Join
将记录小的表的关联字段作为hash key构造hash表,将列数据存储到hash列表中。扫描较大的表,得到关联字段的hash值扫描hash表是否有匹配的行。
overview:
Nested-Loop Join | Sort Merge Join | Hash Join | |
---|---|---|---|
定义 | 嵌套多重循环,外部表匹配内部表 | 两表排序,按join条件做归并 | 小表构造哈希表,大表匹配 |
分类 | simple/block nest-loop | ||
适用范围 | 驱动表记录少(<1万),内部表有索引,返回结果集小 | 无索引,数据有序,join条件不是\= | 两表数据量相差很大,join及union、groupby操作 |
MySQL只支持这种方式 | 因为要排序所以复杂度高,未排序情况下选择hash | hash表太大则需要分批读到内存 |
Nested-Loop Join
嵌套循环算法:从外部表中依次读取每行,每行与内部表进行匹配,内部表被扫描多次。二重循环。
两表连接,两表分别有m行和n行,复杂度是$O(m*n)$,
若内表通过索引扫描,复杂度是$O(m*\log n)$
step:
- 选择记录条数小的作为驱动表($m*\log n, m < n$)
- 驱动表循环
- 每行匹配内部表
Block Nested-Loop Join
非一行一行读取外部表,而是按块读取外部表,将多行缓存起来,从而见减少了内部表的访问次数。
step:
- 将驱动表放入缓存区
- 遍历内部表
- 每行匹配缓存区