Oracle 19C 哈希联接

原创 Asher.HU 2021-02-04

1630

数据库使用哈希联接来联接更大的数据集。

优化器使用两个数据集中的较小者在内存中的连接键上构建哈希表，并使用确定性哈希函数指定哈希表中存储每一行的位置。然后，数据库扫描较大的数据集，探测哈希表以查找满足联接条件的行。

当优化器考虑哈希联接时：通常，当必须联接相对大量的数据（或必须连接很大比例的小表）且联接为等联接时，优化器会考虑哈希联接。
哈希联接如何工作：哈希算法采用一组输入并应用确定性哈希函数以生成介于1和n之间的哈希值，其中n是哈希表的大小。
当哈希表不能完全容纳在PGA中时，哈希联接如何工作当哈希表不能完全容纳在PGA中时，数据库必须使用其他技术。在这种情况下，数据库使用临时空间来保存哈希表的部分（称为分区），有时还保留用于探测哈希表的较大表的部分。
哈希联接控件 : 该USE_HASH提示指示优化器在将两个表联接在一起时使用哈希联接。

9.2.2.1当优化器考虑哈希联接时

通常，当必须连接相对大量的数据（或必须连接很大比例的小表）且该连接为等值连接时，优化器会考虑使用哈希连接。

当较小的数据集适合内存时，散列连接的成本效益最高。在这种情况下，成本仅限于对两个数据集的一次读取。

由于哈希表位于PGA中，因此Oracle数据库可以访问行而无需将其锁存。此技术通过避免重复锁存和读取数据库缓冲区高速缓存中的块的必要性来减少逻辑I / O。

如果数据集不适合内存，则数据库将对行源进行分区，然后联接将逐个分区进行。这会占用大量的排序区域内存，并使用I / O到临时表空间。这种方法仍然是最具成本效益的，尤其是当数据库使用并行查询服务器时。

9.2.2.2哈希联接如何工作

哈希算法采用一组输入，并应用确定性哈希函数以生成介于1和n之间的哈希值，其中n是哈希表的大小。

在哈希联接中，输入值是联接键。输出值是数组（即哈希表）中的索引（插槽）。

哈希表 : 为了说明哈希表，假定数据库哈希hr.departments在departments和的联接中employees。连接键列为department_id。
哈希联接：基本步骤 : 优化器使用较小的数据源在内存中的联接键上构建哈希表，然后扫描较大的表以查找联接的行。

9.2.2.2.1哈希表

为了说明哈希表，假设数据库hr.departments在departments和的联接中哈希employees。连接键列为department_id。

的前5行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表中的每个哈希函数，从而为每个哈希表生成哈希值。在此示例中，哈希表有5个插槽（它可以有更多或更少）。因为n是5，所以可能的哈希值范围是从1到5。哈希函数可能会为部门ID生成以下值：

f(10) = 4
f(20) = 1
f(30) = 4
f(40) = 2
f(50) = 5

需要注意的是哈希函数恰巧产生相同的散列值4的部门10和30。这称为哈希冲突。在这种情况下，数据库将这些记录的部门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

9.2.2.2.2哈希联接：基本步骤

优化器使用较小的数据源在内存中的连接键上构建哈希表，然后扫描较大的表以查找连接的行。

基本步骤如下：

数据库对称为构建表的较小数据集执行全面扫描，然后将哈希函数应用于每行中的联接键，以在PGA中构建哈希表。
在伪代码中，该算法可能如下所示：
```
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;
```
数据库使用成本最低的访问机制来探查第二个数据集（称为探查表）。
通常，数据库对较小和较大的数据集都进行完全扫描。伪代码中的算法可能如下所示：
```
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;
```
对于从较大数据集检索的每一行，数据库执行以下操作：
1. 将相同的哈希函数应用于一个或多个联接列，以计算哈希表中相关插槽的数量。
  例如，为了探测哈希表中的部门ID 30，数据库将哈希函数应用于30，从而生成哈希值4。
2. 探测哈希表，以确定插槽中是否存在行。
  如果不存在任何行，则数据库将处理较大数据集中的下一行。如果存在行，那么数据库将继续进行下一步。
3. 检查一个或多个联接列是否匹配。如果发生匹配，则数据库将报告这些行或将它们传递到计划中的下一步，然后处理较大数据集中的下一行。
  如果哈希表插槽中存在多行，则数据库将遍历链接的行列表，并逐一检查。例如，如果部门30散列到slot 4，则数据库将检查每一行，直到找到为止30。

示例9-4哈希联接

应用程序查询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，而该表却小6倍，所以数据库散列为orders。在哈希联接中，构建表的数据集始终首先出现在操作列表中（步骤2）。在第3步中，数据库对较大的数据库执行完整扫描，order_items对每行的哈希表进行探测。

9.2.2.3当哈希表不适合PGA时，哈希联接的工作方式

当哈希表不完全适合PGA时，数据库必须使用其他技术。在这种情况下，数据库使用临时空间来保存哈希表的部分（称为分区），有时还保留用于探测哈希表的较大表的部分。

基本过程如下：

数据库对较小的数据集执行完整扫描，然后在PGA和磁盘上构建一个哈希桶阵列。
当PGA哈希区域填满时，数据库将在哈希表中找到最大的分区，并将其写入磁盘上的临时空间。数据库将磁盘上属于该磁盘分区的任何新行以及PGA中的所有其他行存储。因此，哈希表的一部分在内存中，一部分在磁盘上。
数据库在读取其他数据集时会经过第一遍。
对于每一行，数据库执行以下操作：
1. 将相同的哈希函数应用于一个或多个联接列，以计算相关哈希桶的数量。
2. 探测哈希表，以确定存储桶中的行中是否存在行。
  如果散列值指向内存中的一行，则数据库将完成连接并返回该行。但是，如果该值指向磁盘上的哈希分区，则数据库使用与原始数据集相同的分区方案，将该行存储在临时表空间中。
数据库逐个读取每个磁盘上的临时分区
数据库将每个分区行连接到相应的磁盘临时分区中的行。

9.2.2.4哈希联接控件

该USE_HASH提示指示优化器在将两个表联接在一起时使用哈希联接。

10104事件可以分析 hash 连接时的相关信息

「喜欢这篇文章，您的关注和赞赏是给作者最好的鼓励」

关注作者