一、hash连接
数据库使用hash连接来连接较大的数据集。
优化器在内存中使用两个数据集中较小的一个在连接键上构建哈希表，使用确定性哈希函数在哈希表中指定存储每一行的位置。然后，数据库扫描较大的数据集，探测哈希表以查找满足连接条件的行。
二、优化器在什么时候会考虑使用hash连接？
通常，当必须连接相对大量的数据(或必须连接小表的很大一部分)，并且该连接是等值连接时，优化器会考虑hash连接。
当较小的数据集能够装入内存时，hash连接是最有效的。在这种情况下，开销被限制为对两个数据集的一次读取。
因为哈希表在PGA中，所以Oracle数据库可以在不加锁的情况下访问行。这种技术通过避免在数据库缓冲缓存中重复加锁和读取块的必要性，减少了逻辑I/O。
如果数据集无法全部放入内存，则数据库对行源进行分区，然后逐个分区进行连接。这可能会使用大量的排序区域内存，以及对临时表空间的I/O。这种方法可能依旧是最有效的，特别是当数据库使用并行查询服务器时。
二、hash连接是如何运作的呢？
hash算法接受一组输入，并应用确定性hash函数来生成随机hash值。在hash连接中，输入值是连接键。输出值是数组中的索引(槽)，也就是hash表。
1.hash表
为了说明hash表，假设数据库在departments和employees的连接中对hr.departments进行hash运算。连接键是department_id。
departments表的前五行如下所示：
SQL> select * from departments where rownum < 6;
DEPARTMENT_ID DEPARTMENT_NAME MANAGER_ID LOCATION_ID
------------- ------------------------------ ---------- -----------
10 Administration 200 1700
20 Marketing 201 1800
30 Purchasing 114 1700
40 Human Resources 203 2400
50 Shipping 121 1500
数据库对表中的每个department_id应用hash函数，为每个department_id生成一个hash值。在本例中，hash表有5个槽(可以更多或更少)。因为n是5，所以可能的hash值范围是从1到5。hash函数可能会为department_id生成以下值:
f(10) = 4
f(20) = 1
f(30) = 4
f(40) = 2
f(50) = 5
注意:hash函数恰好为部门10和部门30生成了相同的hash值4。这被称为hash冲突。在这种情况下，数据库使用链表结构将部门10和部门30的记录放在同一个槽中。从概念上讲，哈希表看起来如下:
1 20,Marketing,201,1800
2 40,Human Resources,203,2400
3
4 10,Administration,200,1700 -> 30,Purchasing,114,1700
5 50,Shipping,121,1500
2.hash连接：基本步骤
优化器在内存中使用较小的数据源在连接键上构建hash表，然后扫描较大的表以查找要连接的行。
基本步骤如下：
- （1）数据库对较小的数据集(称为构建表)执行完整扫描，然后对每行中的连接键应用hash函数，以在PGA中构建hash表。
伪代码表示如下所示：
FOR small_table_row IN (SELECT * FROM small_table)
LOOP
slot_number := HASH(small_table_row.join_key);
INSERT_HASH_TABLE(slot_number,small_table_row);
END LOOP;
- （2）数据库使用成本最低的访问机制探测第二个数据集(称为探测表)。
通常，数据库会对较小和较大的数据集执行完整扫描。该算法的伪代码看似如下:
FOR large_table_row IN (SELECT * FROM large_table)
LOOP
slot_number := HASH(large_table_row.join_key);
small_table_row = LOOKUP_HASH_TABLE(slot_number,large_table_row.join_key);
IF small_table_row FOUND
THEN
output small_table_row + large_table_row;
END IF;
END LOOP;
伪代码解释：对于从较大数据集中检索到的每一行，数据库会执行以下操作:
- a，对连接列应用相同的哈希函数，生成相应的hash值（hash表中的槽号）。
例如，探测hash表以找到部门ID为30的记录，数据库会对30应用哈希函数，然后生成哈希值为4。 - b、探测哈希表以确定该槽（通过a步骤中计算的hash值确定）中是否存在行。
如果不存在行，则数据库处理较大数据集中的下一行。如果存在行，则数据库继续执行下一步。 - c、检查连接列是否匹配。如果匹配，则数据库要么报告这些行，要么将它们传递给计划中的下一步，然后处理较大数据集中的下一行。
如果哈希表槽中存在多行，则数据库会遍历整个行链表，检查每一行。例如，如果部门30hash到槽4，则数据库检查每一行，直到找到30。
示例：某个应用程序查询oe.orders和oe.order_items表，在order_id列上进行连接操作。
SELECT o.customer_id, l.unit_price * l.quantity
FROM orders o, order_items l
WHERE l.order_id = o.order_id;
可能的执行计划如下:
--------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)|
--------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 665 | 13300 | 8 (25)|
|* 1 | HASH JOIN | | 665 | 13300 | 8 (25)|
| 2 | TABLE ACCESS FULL | ORDERS | 105 | 840 | 4 (25)|
| 3 | TABLE ACCESS FULL | ORDER_ITEMS | 665 | 7980 | 4 (25)|
--------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - access("L"."ORDER_ID"="O"."ORDER_ID")
由于orders表相对于order_items表较小(order_items表比orders表大6倍)，因此数据库对orders表进行hash处理。在hash连接中，构建表的数据集总是首先出现在操作列表中(步骤2)。在步骤3中，数据库对较大的order_items表执行一次完整扫描，然后探测哈希表中的每一行。
3.当hash表与PGA不合适时hash连接该如何运作呢？
在 Oracle 中，当哈希表与 PGA 不适合时，Oracle 会使用基于磁盘的哈希连接算法。这种算法可以在磁盘上创建临时文件来处理表的连接，从而避免在 PGA 中使用过多的内存。基于磁盘的哈希连接算法是 Oracle 中一种用于处理大型数据集的连接方法。与基于内存的哈希连接算法不同，基于磁盘的哈希连接算法可以将连接数据存储在磁盘上，从而避免在内存中使用过多的内存。
需要注意的是，基于磁盘的哈希连接算法需要频繁地将数据从磁盘读入内存和写入磁盘，因此它可能会导致较慢的性能。此外，由于需要使用磁盘临时文件，因此该算法可能会产生额外的 I/O 操作和磁盘空间占用。因此，该算法通常用于处理较大的数据集，而不是小型数据集。
4. 总结
现在就基于内存的hash连接算法和基于磁盘的连接算法的过程做一个概述。
（1）基于内存的hash连接算法
基于内存的哈希连接算法是 Oracle 中一种用于处理小到中型数据集的连接方法。该算法利用哈希表的快速查询能力，将两个表的数据集合并到一个结果集中。下面是基于内存的哈希连接算法的详细过程：
- a、对于表1，将连接列的值进行哈希处理，并将每行数据存储到哈希表中。哈希表中的每个条目都包含哈希值和一个指向该行数据的指针。
- b、对于表2，对连接列的值进行哈希处理，并将每行数据与哈希表进行匹配。如果存在匹配，则将表1和表2中相应的行连接起来，并将连接结果存储到结果集中。
- c、重复步骤2，直到表2中的所有行都与哈希表中的数据匹配完成。
- d、将结果集发送给客户端。
需要注意的是，基于内存的哈希连接算法需要足够的内存来存储哈希表和结果集。如果内存不足，则可能需要使用基于磁盘的哈希连接算法。此外，由于哈希表是基于哈希算法生成的，因此该算法对于相同的数据集可能会有不同的表现，因此必须谨慎评估其性能。
（2）基于磁盘的hash连接算法
基于磁盘的hash连接算法的详细过程如下：
- a、对于表1，将连接列的值进行哈希处理，并将每行数据存储到临时文件中，文件名为“Hash File 1”。这些文件将根据哈希值分配到多个文件中，以避免单个文件变得过大。哈希算法应该足够均匀，以确保将数据分配到多个文件中，并且每个文件的大小不会太大。
- b、对于表2，对连接列的值进行哈希处理，并将每行数据存储到另一个临时文件中，文件名为“Hash File 2”。同样，这些文件将根据哈希值分配到多个文件中。
- c、对于每个哈希文件，将文件按哈希值排序，并将哈希表加载到内存中。哈希表应该足够小，可以适应内存，并包含对哈希文件中每个哈希值的引用。
- d、遍历哈希文件2中的每个哈希值。对于每个哈希值，将哈希表1中具有相同哈希值的行读入内存，并将它们与哈希文件2中具有相同哈希值的行进行连接操作。连接结果将存储在内存中的结果集中。
- e、当连接结果集达到内存限制时，将其写入磁盘临时文件中。这个过程可能会多次进行，直到哈希文件2中的所有哈希值都被处理。
- f、对于连接结果集中的每个结果，将其发送给客户端。
- g、重复步骤d到f，直到哈希文件1中的所有哈希值都被处理。
- h、删除所有临时文件。
5、hash连接控制
USE_HASH提示指示优化器在将两个表连接在一起时使用hash连接。
更多信息请参考：https://docs.oracle.com/en/database/oracle/oracle-database/19/tgsql/joins.html
