很多DBA都知道这句话，左表小右表大走索引链接，左表大右表小走hash连接，这在大多数情况下是对的，但是为什么？这次我们从算法复杂度的角度给出这个问题的答案。

事先声明，因为我们不知道数据库底层的hash算法，所以这次以java中的hashmap结构（即数组加红黑树的结构）模拟数据库底层的hash结构，以平衡二叉树模拟索引结构（为了方便计算），以SELECT * FROM A INNER JOIN B ON A.a = B.b为例，仅用以抛砖引玉，望周知。

一、NL-index-join

索引连接的计算过程可以描述为：

取出A表的第一行数据，拿出a列的值，遍历B表b列的索引，找到A.a = B.b的索引位置，然后根据rowid去B表的原位置找到对应的行，取出放到结果集缓存中，若未找到则进行下一步。
取出A表的第二行数据。。。。
这个过程相当于一个for循环（A表数据量为N，B表数据量为M）：
for (int i=1;i<=N;i++){
取出A表第i行数据，以及a列的值，
以a列的值为基准遍历B表的索引，找到索引位置与rowid，回表。
}
这个过程中，B表索引（以平衡二叉树模拟）的遍历效率是logM，那么整个过程的算法复杂度为NlogM。
整个计算过程相当于执行了一次A表的全表扫描+N次B表索引扫描以及回表，因此该方法的关键在于右表B的索引效率与回表消耗。最后输出的结果是以左表的索引顺序为准的。

二、Hash-join

我们以java经典的HashMap（数组+红黑树结构）模拟数据库hash后的散列结构，Hash桶的数量（数组长度）为X。

Hash连接的计算过程可以描述为：

1、构建hash桶，依次取出A表的数据行，以a列的值为基准计算出hash值，将这行数据放入HashMap中，这个过程在最理想情况下（每个hash桶高度一致），算法复杂度为Nlog(N/X)，最差情况下（所有数据都接到同一个红黑树下），算法复杂度为NlogN。（HashMap的构建过程可自行百度）
2、遍历B表，依次取出B表的数据行，以b列的值计算hash值，遍历对应hash值的红黑树，对比寻找满足A.a = B.b的数据，若找到则将A与B表对应的数据放入结果集缓存中，若未找到则进行下一个循环。这个过程最理想的情况下，算法复杂度为Mlog(N/X)，最差情况下，算法复杂度为MlogN。
3、整个过程的时间消耗分为：A表进行一次全表扫描并构建hash桶，B表进行全表扫描并根据hash值扫描M次HashMap。此过程的关键在于A表构建hash桶的速度。我们一般认为数据库的hash算法比较科学，hash冲突较少，取较为理想的算法复杂度，即算法复杂度和为：(N+M)*log(N/X)。最后输出的结果集是以B表扫描顺序为准。

三、结论

数据库ini参数中默认JOIN_HASH_SIZE参数为50万，当数据量大于50万时取X=50万，数据量小于50万时取X=数据量/10，将上述算法复杂度代入计算可得：

由上表可以看出，左表小右表大，索引链接消耗更小，左表大右表小，hash连接消耗小，两个表都大也是hash连接更快。