PostgreSQL中的索引(三) --Hash
许多现代编程语言都将哈希表作为基本数据类型。从表面上看，哈希表看起来像一个常规数组，使用任何数据类型(例如字符串)建立索引，而不仅是使用整数。PostgreSQL中的哈希索引也是以类似的方式构造的。这是如何运作的呢?
作为一个规则，数据类型允许的值范围非常大:在一个类型为«text»的列中，我们可以设想有多少不同的字符串?同时，在某个表的«text»的列中实际存储了多少不同的值?通常不会有那么多。
哈希的思想是将一个小数字(从0到N−1,N个值)与任意数据类型的值相关联。这样的关联称为哈希函数。获得的数字可以用作常规数组的索引，其中存储对表行(tid)的引用。这个数组的元素称为哈希表bucket——如果同一个索引值出现在不同的行中，那么一个bucket可以存储多个tid。
哈希函数越均匀地按桶分配原值，效果就越好。但即使是一个好的哈希函数，有时也会对不同的原值产生相同的结果——这叫做冲突。因此，一个bucket可以存储对应于不同键的TIDs，因此，需要重新检查从索引中获得的TIDs。
举个例子，我们能想到字符串的哈希函数是什么?让桶的数目为256。然后，以桶号为例，我们可以获取第一个字符的代码(假设采用单字节字符编码)。这是个好的哈希函数吗?显然不是:如果所有字符串都以相同的字符开头，那么它们都将进入一个bucket，因此一致性是不可能的，所有的值都需要重新检查，哈希就没有任何意义了。如果我们把所有字符的编码以256的模加起来会怎么样?这样会好得多，但还远远不够理想。如果您对PostgreSQL中这样一个哈希函数的内部特性感兴趣，请查看hashfunction.c中的hash_any()定义。
索引结构
让我们回到哈希索引。对于某种数据类型的值(索引键)，我们的任务是快速找到匹配的TID。
当插入到索引中时，让我们计算键的哈希函数。PostgreSQL中的哈希函数总是返回«integer»类型，其范围为2的32次方≈40亿个值。桶的数量最初等于两个，然后根据数据大小动态增加。桶数可以使用位算法从哈希码计算出来。这是我们要放TID的桶。
但是这是不够的，因为匹配不同键的TIDs可以放在同一个桶中。我们该怎么办?除了TID之外，还可以将键的原值存储在桶中，但是这将大大增加索引大小。为了节省空间，bucket存储的不是键值，而是键值的哈希代码。
在搜索索引时，我们计算键的哈希函数并获得桶号。现在剩下的工作是遍历bucket的内容，只返回具有适当哈希码的匹配tid。这是有效的，因为存储的«哈希码--TID»对是有序的。
然而，两个不同的键可能不仅进入了一个bucket，而且具有相同的四字节哈希码——冲突还未消除。因此，访问方法要求常规索引引擎通过重新检查表行中的条件来验证每个TID(引擎可以在进行可见性检查的同时执行此操作)。
将数据结构映射到页
如果我们从buffer cache管理器查看索引，而不是从查询计划和执行的角度来看，那么所有信息和所有索引行都必须打包到页中。这样的索引页存储在buffer cache中，并以与表页完全相同的方式从那里刷出。
如图所示，哈希索引使用了四种页面(灰色矩形):
·元数据页--零页号，它包含了索引内部的信息。
·桶页--索引的主要页，它将数据存储为«哈希码--TID»对。
·溢出页--结构与桶页相同，当一个页面不足以容纳一个桶时使用。
·位图页--跟踪当前清除的溢出页面，这些溢出页面可以被其他桶重用。
从索引页元素开始的向下箭头表示TIDs，即对表行的引用。
每次索引增加时，PostgreSQL会立即创建两倍于上次创建的桶(因此，页面也是如此)。为了避免一次分配大量的页面，version 10进行改进。至于溢出页，它们是在需要出现时分配的，并在位图页中跟踪，位图页也是在需要出现时分配的。
注意，哈希索引不能减小大小。如果我们删除一些索引行，分配的页将不会返回到操作系统，而只会在vacuuming后用于新数据。减少索引大小的唯一选项是使用REINDEX或VACUUM FULL命令从头重新构建。
示例
让我们看看哈希索引是如何创建的。为了避免设计自己的表，从现在开始，我们将使用air transport的演示数据库，这次我们将考虑flights表。
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中(创建索引时，PostgreSQL会发出警告)。因此，哈希索引在失败后无法恢复，并且不参与复制。此外，哈希索引的通用性远远低于«btree»，其效率也值得怀疑。所以现在使用这些索引是不切实际的。
然而，这种情况最早将在今年秋天(2017年)PostgreSQL的第10版发布后发生改变。在这个版本中，哈希索引最终支持写wal文件;此外，内存分配得到了优化，并发工作效率更高。
哈希的语义
但为什么哈希索引几乎从PostgreSQL诞生之初就存在到9.6无法使用?问题是DBMS广泛使用了哈希算法(特别是哈希连接和分组)，系统必须知道哪个哈希函数应用于哪个数据类型。但是这种通信不是静态的，也不能一次性地设置，因为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)
属性
让我们看看哈希索引的属性，其中该访问方法向系统提供关于自身的信息。上次我们提供了查询。
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
哈希函数不保留顺序关系:如果哈希函数的一个键值小于另一个键值，不可能得出键本身是如何排序的结论。因此，通常哈希索引只能支持«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»)。哈希索引不操作空值也是出于同样的原因:对于空值，«equals»操作没有意义(«search_nulls»)。
因为哈希索引不存储键(但只存储它们的哈希码)，所以它不能用于index-only访问(«returnable»)。
此访问方法也不支持多列索引(«can_multi_col»)。
内部原理
从version 10开始，可以通过“pageinspect”扩展来查看哈希索引的内部内容。这是它的样子:
demo=# create extension pageinspect;
元数据页(我们得到索引中的行数和最大使用桶数):
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)
一个桶页(我们得到live的元组和死元组的数量，也就是那些可以被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)
但是，如果不检查源代码，几乎不可能弄清所有可用字段的含义。
如果您希望这样做，您应该从https://git.postgresql.org/gitweb/?p=postgresql.git;a=blob;f=src/backend/access/hash/README;hb=HEAD开始。