哈希

本文翻译自 https://habr.com/en/company/postgrespro/blog/442776/，已经得作者同意。

我们在第一篇文章中介绍了 PostgreSQL 索引引擎，第二篇文章介绍了访问方法接口，现在开始讨论具体的索引类型，让我们从哈希索引开始。

哈希

结构

通用理论

许多现代编程语言都将哈希表作为基础数据类型。从使用者的角度来看，哈希表看起来像一个普通的数组，不同的是，其可以使用任意数据类型（比如字符串）作为索引而不仅仅是整数。PostgreSQL 中的哈希索引也是类似的结构，那它是如何工作的呢？

通常，数据类型允许的值的范围是很大的：设想文本类型的列可以存储多少不同的字符串？于此同时，某个具体的表中，文本类型的列实际存储的字符串又有多少呢？通常并不会很多。

哈希的思想就是将一个小的数值（从 0 到 N-1，共 N 个值）与任何数据类型的值相关联，这种关联通过 哈希函数实现。通过哈希函数获取到的值（哈希值）可以作为存储 TID 的数组的索引。该数组的元素称为哈希表桶 （hash table buckets），如果不同数据行有相同的索引值，则一个 bucket 可以存储多个 TID。

哈希函数越是能够均匀地按照桶来分配值，该 hash 函数就越好。但即便一个好的哈希函数，也难免会为不同的值生成相同的结果，这被称之为冲突_。因此，一个桶可以存储不同 key 对应的 TID，而从索引中读取到的 TID 则需要重新检测。

比如：我们能想到哪些字符串的 hash 函数呢？假设桶数为 256，我们可以取字符串的第一个字符作为其桶号，这是一个好的哈希函数么？显然不是：如果所有字符串都以相同的字符开头，所有字符串将落入同一个桶中，从桶中获取到的所有值都需要重新检测其是否满足条件，hash 将没有任何意义。如果我们把所有字符的编码加起来然后对 256 取模怎么样呢？这会好很多，但仍不理想。如果你对类似的哈希函数实现感兴趣，可以参考 hashfun.c 中 hash_any() 实现。

索引结构

让我们回到哈希索引。对于某个数据类型的值（索引的 key），我们的任务是快速找到匹配的 TID。

当插入索引时，用哈希函数为 key 计算一个哈希值（hash value）。PostgreSQL 中的 hash 函数总是返回一个 integer 类型的数值，有 2 ≈ 40亿个值。桶的初始数目为 2，会随着数据量动态增加。桶的编号可以通过哈希码（hash code）的位运算而来，该桶用于存放 TID。

但这还不够。因为匹配不同 key 的 TID 可以放在相同的桶里，那同一个桶中如何查找当前 key 的 TID 呢？除了 TID 之外，还可以将 key 的值存储在桶中，但这将极大地增加索引的大小，为了节省空间，并不存储 key，而是存储 key 的哈希码。

当通过 key 查询时，我们用哈希函数计算该 key 的哈希值并获取桶号。然后，遍历桶中的内容，返回与哈希码匹配的 TID。由于 hash code <-> TID 是有序的，因此桶内查询还是很高效的。

然而，两个不同的 key 不仅可能落在一个桶中，还可能有相同的四字节哈希码——没有人能避免这种冲突。因此，访问方法要求通用索引引擎验证每个 TID，即对每一个匹配的行重新检测其检索条件（引擎可以在可见性检测时执行此操作）。

将数据结构映射到页面

如果我们从 Buffer 缓存管理器（buffer cache manager）的角度而非从查询规划和执行的角度来看索引，那所有信息和索引行都必须保存在页面中。这样的索引页存储在 Buffer 缓存中，与数据表页采用相同的淘汰策略。

如上图所示，哈希索引使用四种类型的页（灰色长方形）：

Meta 页——第 0 页，包含索引的元信息。
Bucket 页——索引的主要数据页，数据以 hash code--ITD 对的形式存储。
Overflow 页——结构与 Bucket 页相同，当页面不足以容纳一个桶时使用。
Bitmap 页——跟踪当前没有在使用的 Overflow 页，这些页可以被其他桶重用。

从索引页中的元素开始的向下的箭头表示 TID，对应数据表中的行。

每次索引增加时，PostgreSQL 会立即创建两倍于最后一次创建的桶（页面）的数量的桶。为了避免同时分配大量数据页，在 PostgreSQL 10 中索引页的分配更加平滑。至于 overflow 页，它们是按需分配的，overflow 页由 bitmap 页跟踪其使用情况，bitmap 页也是按需分配的。

注意，哈希索引不能变小。如果我们删除了一些索引行，已经分配的数据页不会被回收，只能在 vacuum 之后被新数据重用。减小哈希索引大小的唯一方法是通过 REINDEX 或 VACUMM FULL 命令进行重建。

例子

我们来看看如何创建哈希索引。为了避免设计我自己的测试表，从现在开始，我们使用航空运输演示数据库，来看看航班表。

demo=# create index on flights using hash(flight_no);
WARNING:  hash indexes are not WAL-logged and their use is discouraged
CREATE INDEX
demo=# explain (costs off) select * from flights where flight_no = 'PG0001';
                     QUERY PLAN                     
----------------------------------------------------
 Bitmap Heap Scan on flights
   Recheck Cond: (flight_no = 'PG0001'::bpchar)
   ->  Bitmap Index Scan on flights_flight_no_idx
         Index Cond: (flight_no = 'PG0001'::bpchar)
(4 rows)

当前哈希索引的不足之处在于索引上的操作不会记录 WAL 日志（建索引时会有 WARNING 信息）。因此，哈希索引不能被恢复，且不参与主备复制。此外，哈希索引的通用性远低于 B-tree 索引，其效率也值得怀疑。因此，现在使用这样的索引是不切实际的。

不过，随着 PostgreSQL 10 发布，这些问题都已经解决了。在 PostgreSQL 10 中，哈希索引终于支持了 WAL 日志；此外，内存分配也进行了优化，并发工作也更加高效。

从 PostgreSQL 10 开始，已经全面支持哈希索引，可以没有任何约束的使用哈希索引。以上示例中的警告也不会再显示了。

哈希语义

为什么哈希索引从 PostgreSQL 诞生之初就有，但一直到 9.6 仍然处于不可用的状态？问题是数据库管理系统广泛使用哈希算法（特别是哈希连接和分组），系统必须清楚将哪个哈希函数应用于哪种数据类型，但这种对应关系不是静态的，PostgreSQL 允许添加新的数据类型，没有办法事先设置好这种对应关系。以下是哈希的访问方法，它通过运算符族和辅助函数的关联，表示这种对应关系。

demo=# select   opf.opfname as opfamily_name,
         amproc.amproc::regproc AS opfamily_procedure
from     pg_am am,
         pg_opfamily opf,
         pg_amproc amproc
where    opf.opfmethod = am.oid
and      amproc.amprocfamily = opf.oid
and      am.amname = 'hash'
order by opfamily_name,
         opfamily_procedure;
   opfamily_name    | opfamily_procedure
--------------------+-------------------- 
 abstime_ops        | hashint4
 aclitem_ops        | hash_aclitem
 array_ops          | hash_array
 bool_ops           | hashchar
...

尽管这些函数没有文档，但它们可以用于计算适当数据类型值得哈希码。例如 hashtext 函数可以用于 text_ops 运算符族。

demo=# select hashtext('one');
 hashtext  
-----------
 127722028
(1 row)
demo=# select hashtext('two');
 hashtext  
-----------
 345620034
(1 row)

属性

我们来看看哈希索引的属性。执行 PostgreSQL 索引-2 中查询属性的 SQL，结果如下：

     name      | pg_indexam_has_property
---------------+-------------------------
 can_order     | f
 can_unique    | f
 can_multi_col | f
 can_exclude   | t
     name      | pg_index_has_property
---------------+-----------------------
 clusterable   | f
 index_scan    | t
 bitmap_scan   | t
 backward_scan | t
        name        | pg_index_column_has_property 
--------------------+------------------------------
 asc                | f
 desc               | f
 nulls_first        | f
 nulls_last         | f
 orderable          | f
 distance_orderable | f
 returnable         | f
 search_array       | f
 search_nulls       | f

哈希函数不保证有序：如果一个 key 的哈希值小于另一个 key，不能对 key 本身的排序得出任何结论。因此，通常 hash 索引仅支持 equals 运算：

demo=# select   opf.opfname AS opfamily_name,
         amop.amopopr::regoperator AS opfamily_operator
from     pg_am am,
         pg_opfamily opf,
         pg_amop amop
where    opf.opfmethod = am.oid
and      amop.amopfamily = opf.oid
and      am.amname = 'hash'
order by opfamily_name,
         opfamily_operator;
 opfamily_name |  opfamily_operator  
---------------+----------------------
 abstime_ops   | =(abstime,abstime)
 aclitem_ops   | =(aclitem,aclitem)
 array_ops     | =(anyarray,anyarray)
 bool_ops      | =(boolean,boolean)
...

综上，哈希索引不能返回有序数据（ can_order ， orderable ）。哈希索引不能处理 NULL 值（ search_nulls），因为对 NULL 值执行 equals 操作没有意义。

由于哈希索引不存储 key（仅存储 key 的哈希码），它不能用于 index-only 访问（ returnable）。

哈希索引也不支持多列索引（ can_multi_col）。

内部结构

从 PostgreSQL 10 开始，可以通过 pageinspect 插件查看 hash 索引的内部结构。如下：

demo=# create extension pageinspect;

meta 页（我们获取索引中的行数和使用的最大 bucket 数）：

demo=# select hash_page_type(get_raw_page('flights_flight_no_idx',0));
 hash_page_type 
----------------
 metapage
(1 row)

demo=# select ntuples, maxbucket
from hash_metapage_info(get_raw_page('flights_flight_no_idx',0));
ntuples | maxbucket 
---------+-----------
   33121 |       127 
(1 row)

bucket 页（我们读取活元组和死元组的数量，死元组表示可以被 vacuum 清理掉的元组）：

demo=# select hash_page_type(get_raw_page('flights_flight_no_idx',1));
 hash_page_type
----------------
 bucket
(1 row)

demo=# select live_items, dead_items
from hash_page_stats(get_raw_page('flights_flight_no_idx',1));
 live_items | dead_items
------------+------------
        407 |          0
(1 row)

类似地，还可以查看其他索引页面的内容。但如果不看源码很难了解所有这些字段的含义，如果你对此感兴趣的话，可以从 README 开始。

PostgreSQL必知必会

PostgreSQL 索引-3.哈希

哈希

结构

通用理论

索引结构

将数据结构映射到页面

例子

哈希语义

属性

内部结构