What is hash join and how does it work in SQL Server?

Hash join is one of the three join types in execution plans in SQL Server. The other two are nested loops join and merge join.

Hash Join就是利用哈希算法作匹配的联接算法。简单来说,哈希算法分成两步,“构建哈希桶(Build hash bucket)”探测哈希桶中的值(Probe hash bucket)”。在“Build”阶段,SQL Server选择两个要做Join的数据集中的一个,根据记录的值建立起一张在内存中的Hash表。然后在“Probe”阶段,SQL Server选择另外一个数据集,将里面的记录值依次带入,返回符合条件可以做联接的行

In other words, SQL Server 选择两个需要join的表中的一个a,对于a中的每一个记录R1,计算其联接列的hash值,然后根据hash值将R1插入到hash bucket当中选择另外一张表b,对于b中的每一条记录R2,我们也计算其联接列的hash值,然后去hash bucket上查找。如果Hash bucket上有R1能够跟R2进行连接,那么就输出 (R1, R2) 的联接结果,可能有多个R1的记录。

那么,到底什么是HASH表?数据库中一个记录的HASH值又是如何被计算出来的呢?

Hash,一般翻译做“”散列,也有直接音译为哈希的,就是把任意长度的输入(又叫做预映射,pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数

HASH主要用于信息安全领域中加密算法,它把一些不同长度的信息转化成杂乱的128位的编码, 这些编码值叫做HASH也可以说,hash就是找到一种数据内容和数据存放地址之间的映射关系。

除了节省空间和通过加密提高安全性外,HASH还综合了数组(Array)和链表(Linked Lis)的优点。Array is a series of objects in the same size and type. It is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key. An array is stored so that the position of each element can be computed from its index tuple by a mathematical formula. The simplest type of data structure is a linear array, also called one-dimensional array. 因此,数组的特点是:寻址容易,插入和删除困难。Linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence。换句话说,链表的特点是:寻址困难,但插入和删除容易。而Hash table 则具备了两者的优点。How come

这主要是通过哈希的构造实现的。哈希表的具体构造方法有很多种,主要直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法。这里举除留余数法或除法散列法为例。具体做法是取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址
H(key)=key MOD p (p<=m)
如在下图中, 左边的0-15Array(数组),右边那些节点的数字则是Linked List中的元素。假定我们使用了HASH(key) % Entry [].length或者更具体点是 index = hash (key) % 16。并且进一步假定Hash (key=12) %16=12, Hash (key=28) %16=12, Hash (key=108) %16=12, Hash (key=140) %16=12。那么1228108以及140这些元素都会存储在数组下标为12的位

如果两个key通过hash % Entry[].length得到的index相同,会不会有覆盖的危险答案是肯定的。因此,无论哈希函数设计有多么精细,都会产生冲突现象,也就是2个关键字处理函数的结果映射在了同一位置上,但有一些方法可以避免冲突,如拉链法、多哈希法、开放地址法、建域法等。离题太远了,就此打住。希望本文帮助你更进一步了解SQL Server里的Hash Join是怎么回事。