Join操作

关系型数据库中，Join操作非常常见。正是由于对多表联合查询的支持，各个表之间的关系、关联，正是通过join实现。
Join操作可以理解为，将两张表，通过某一个字段，联合为一张表。

班级表中，记录了班级的班主任是谁。学生表中记录了学生的个人信息，已经学生所属哪个班级。以此可将学生和班级进行join，以此直接知道每个学生的班主任是谁。

Join的实现

粗暴循环遍历

也叫nested loop
这是最容易理解的方式。现在有两张表，如何根据一个字段，将两张表的数据关联起来？
很简单，只需要先取第一个表中的第一条数据，然后拿着这条数据，去找第二张表看是否存在即可。
通过一个O(N*M)的循环即可。

循环遍历几乎无需额外的内存空间，能够支持各种类型的join，并且这样做在数据量较小时是很有效的，SQL Server常常用数据量较小的表作为循环的外层，这样可以减少对内层表的总查询次数。
并且，如果join的字段，在内层表建立了索引，那么查询起来会更加高效。

但是这样的缺点也很明显，这种Join方式对数据表大小很敏感，如果内外层数据量相当，或者当数据库错误的选择了外层表的时候，开销增长将会很大。
它非常适合两个较小的数据集进行联合，或者至少外层表的数据量较小。

排序再查找

也叫Merge Join

这种方式的时间复杂度较低，为O(M+N)。
它的做法为：分别将两张表按照要join的字段进行排序，然后从两边各取一个值，进行比较，如果相等，则将对应的记录返回；
如果不等，则将较小的那条给丢弃，顺着查找下一个更大的，继续重复比较的过程，当任何一张表遍历完毕，则整个join过程完毕。

听起来要高效许多，但是这种方式局限性非常强

首先：
依赖排序操作，如果数据集较大，对其进行排序的开销是很大的。如果要join的字段本身具有索引，那么能够不耗费额外开销进行排序，此时选择merge join较为合适。
其次：
Merge Join 只能以值相等的方式进行join，对于多对多的对应关系，需要将表中已扫描的数据暂存起来，以防止下次还有重复数据。这就是一笔不小的额外开销。因此，如果字段具有唯一索引，那么就能够有效的减少cost

hash查找

Hash Join
在通常写代码时，面对粗暴的循环遍历，大家都能想到，通过建立hash表降低查询的时间开销，join操作也是如此：

首先遍历第一张表，生成一张hash table， 其次遍历第二张表，对每一条数据进行hash，然后从hash table中进行查找，如果存在，则说明匹配到了数据。

相比于排好序的merge join，会多一个计算hash的时间开销，但总体时间复杂度相比nest loop小很多。
这种方式对索引没有太大要求，因为它需要进行每一条记录hash计算，有没有索引帮助不大。
其次，对于并行优化友好，由于没有顺序要求，只是简单计算Hash值，那么多个线程，大家分一分，也很好做了

当然，也有其缺点：
它需要先在内存中建立hash table，这个过程既消耗CPU也消耗内存，并且join过程也需要不断进行hash比对，这个对CPU也是消耗。
在多个查询同时进行hash join的时候，会对数据库整体造成较大的负载。

总结

join方式有三种，SQL SERVER通过执行计划，进行预测，选择合适的join方式，在遇到查询慢时，可以通过执行计划查看具体的cost以及方式