关系型数据库的物理连接

在开发中常听到的 left join，Inner JOIN ，right join ，cross join 这些连接都是数据库的逻辑连接，那么数据库在执行这些连接的时候，数据库是如何在底层实现表的关联的呢？这就是物理连接
目前大部分关系型数据库支持3种物理连接(mysql 貌似到5.6未知仅支持嵌套连接)
数据库的物理连接：
数据库接两个表时候，会考虑3种方法：嵌套连接，合并连接，散列连接。3种方法的连接都有一个表被选为外表（只扫描一次），一个表被选为内表（坑内扫描多次）。如果查询连接了多个表，每次查询只能连接2各表，并保存把中间结果，用户连接另外的表。
1、嵌套连接：外表只扫描一次，而针对外表的每一行都需要扫描一次內表。（注意：连接不能用long或lob字段）
2、合并连接：合并连接需要一个等式连接词（A.col1=B.col1），还要求根据连接列对两个连接的表进行排序。合并连接內表和外表都只扫描一次，有时情况下需要再次扫描內表的部分值，例如，外表存在重复值的情况下。所以优化器通常选择重复值较少的表作为外表。
3、散列连接：散列连接需要一个或多个等式连接谓词，其中每个谓词的类型相同。char类型长度必须相同。decimal进度必须相同。散列连接可以处理多个等式谓词。对于散列连接，首先扫描內表（也称为构件表 build table），表中的行被复制到内存缓冲区。根据“散列键（hash key）”，这些缓冲区被分为几个分区，如果内存中没有足够的空间容纳整个表，则有些分区被写入磁盘上的临时表。然后扫描外表。然后扫描外表（探测表）。对于外表中的每一行，对连接列应用同意散列算法。如果所获得的散列键与行的散列键相匹配，读取分区里面的所有行并应用连接谓词。如果与探测表行匹配的分区在内存中，则读取分区并应用连接谓词将立即进行。如果分区被写入临时表，则探测行也别写入临时表。最后，匹配统一分区行和对应分区被一起处理。

优化器使用3种连接的场景：
嵌套连接：
对于被连接的数据子集较小的情况，nested loop连接是个较好的选择。nested loop就是扫描一个表，每读到一条记录，就根据索引去另一个表里面查找，没有索引一般就不会是 nested loops。
一般在nested loop中， 驱动表满足条件结果集不大，被驱动表的连接字段要有索引，这样就走nstedloop。如果驱动表返回记录太多，就不适合nested loops了。如果连接字段没有索引，则适合走hash join，因为不需要索引。
Inner table被Outer table驱动，outer table返回的每一行都要在inner table中检索到与之匹配的行。
Outer table: 小表、驱动表
Inner table: 被驱动表、大表

哈希连接： 哈希连接是做大数据集连接时的常用方式。优化器扫描小表（或数据源），利用连接键（也就是根据连接字段计算hash值）在内存中建立hash表，然后扫描大表，每读到一条记录就来探测hash表一次，找出与hash表匹配的行。
当小表可以全部放入内存中，其成本接近全表扫描两个表的成本之和。如果表很大不能完全放入内存，这时优化器会将它分割成若干不同的分区，不能放入内存的部分就把该分区写入磁盘的临时段，此时要有较大的临时段从而尽量提高I/O 的性能。临时段中的分区都需要换进内存做hash join。这时候成本接近于全表扫描小表+分区数*全表扫描大表的代价和。
至于两个表都进行分区，其好处是可以使用parallel query，就是多个进程同时对不同的分区进行join，然后再合并。但是复杂。
以下条件下hash join可能有优势：
两个巨大的表之间的连接。
在一个巨大的表和一个小表之间的连接。

合并连接：
对连接的每个表做table access full；
对table access full的结果按照连接键进行排序；
进行merge join对排序结果进行合并。
Sort merge join性能开销几乎都在前两步。相较于前两种连接，合并连接的速度最快的。但也看数据库的索引和数据量情况。

通常情况下河西连接的效果都比合并连接要好，然而如果行源已经被排过序，在执行合并连接时不需要再排序了，这时合并连接的性能会优于哈希连接。
在全表扫描比索引范围扫描再通过rowid进行表访问更可取的情况下，合并会比嵌套性能更佳。

各类关系型数据库都有相应参数可以强制指定那一种连接进行测试。。。