本系列的内容主要翻译自Postgresql官方博客,为了便于理解,对于其中部分涉及到的知识,我在查阅相关资料的基础上做了补充。

原文: Indexes in PostgreSQL — 3(Hash)

系列文章索引

第一篇文章讲了Postgesql中的索引引擎,第二篇文章讲了Postgesql中的访问方法的接口,现在我们准备讨论具体的索引种类,让我们从哈希索引开始。

Hash

结构

一般理论

许多现在的编程语言都将哈希表作为一种基本的数据类型。从外部来看,一个哈希表看起来像一个常规的数组,它的索引可以是任何数据类型(例如字符串),而不仅仅是数字。PostgreSQL中的哈希索引的结构与此类似。那么它是怎么工作的呢?

通常,数据类型允许的值的范围是非常大的:例如在一个数据类型为text的列中可以有多少个不同的字符串呢?同时,在某个表的文本列中实际存储了多少个不同的值呢?通常是没有那么多的。

散列的思想是把任意一个数据类型的值和一个小的数字(从0到N-1)关联起来。像这样的关联就叫做哈希函数。通过哈希函数获取的数字可以用来被作为一个常规数组的索引,而这个数组中存放了表的行(TIDS)的引用。这个数组中的元素被称为哈希表桶(hash table bucket)。如果不同的行的索引的键值一样的话,这些行的TID都会被存储在同一个桶中。

哈希函数哈希的结果越均匀越好。但是再好的哈希函数也可能对不同的数据源计算出相同的结果-这个称为哈希碰撞。所以,一个桶可以存储对应不同键值的行的TID,因此,从索引中获取的值也需要被重新检查。

仅仅作为一个例子:我们能想到一个怎么样的字符串的哈希函数。让我们把桶的数量设置为256。然后,我们可以把字符串的第一个字符(这里只考虑单字节的字符)的编码作为桶的编号。这是一个好的哈希函数吗?显然不是。如果所有的字符串都是以相同的字符开始的,那么它们就会全部落在同一个桶里。因此数据就不均匀,所有的值都必须被重新检查,哈希就没有意义了。如果我们把所有字符的编码加起来然后除以256取模呢?这会好得多,但不是最理想的。如果你对PostgreSQL内部的哈希函数还兴趣的话,可以看一下hashfunc.c中hash_any()的定义

索引结构

让我们回到哈希索引。对于某种数据类型(索引键)的值,我们的任务是快速找到匹配的 TID。

当插入到索引中的时候,我们先通过哈希函数来计算key值。PostgreSQL中的哈希函数总是返回一个integer值,这个范围是 2^32,约等于400万个值。存储桶的数量初始是2,然后会动态的增加来适应数据的大小。桶编号可以使用位运算从哈希编码中计算出来,计算出来的结果就是我们要放置TID的桶。

即哈希函数返回的值不是放置TIDs的桶的编号,而是要通过位运算来计算出桶编号。

但是这还不够,因为匹配不同键的TID可以放进同一桶中。我们该怎么做呢?除了放置TID以外,也可以在桶中存储被索引的键值,但是这会增加索引的大小。为了节省空间,桶里面存储了键值的哈希编码。

当通过索引搜索的时候,我们先通过哈希函数计算出键值的哈希编码,然后通过哈希编码计算出桶编号。现在仍需要遍历这个桶里的内容,然后返回匹配哈希码的TID。由于存储的”Hash code - TID”是有序的,因此这个过程可以高效完成。

然而,两个不同的键值不仅可能出现在同一个桶中,甚至还可能会有相同的哈希编码-没有人能够消除这种冲突。因此,访问方法会要求通用索引引擎重新根据条件来检查每一个TID对应的数据(引擎可以和可见性检查一起执行此操作)。

将数据结构映射到页

如果我们从缓冲区缓存管理器的角度而不是从查询计划和执行的角度来看待索引的话,我们就能发现所有的信息和所有的索引行都必须被打包成页。这样的索引页被存储在缓冲区缓存,并且以和表页完全相同的方式从缓冲区中被驱逐。

哈希索引,如图所示,使用四种类型的页面(灰色矩形)

  • meta page page的编号为0,其中包含了索引的内部信息
  • Bucket pages 索引的主要页面,存储了像“Hash code - TID”对这样的数据。
  • Overflow pages 结构和bucket pages相同,在存储桶超出一个页面的时候使用。
  • bitmap pages 跟踪那些被清除的可以被其余桶重新使用的Overflow pages

向下箭头表示TID,即对表行的引用。

每次索引增加的时候,PostgreSQL会马上创建上次创建数量的两倍数量的存储桶。为了避免一次分配这种潜在的大量页面,在第10次分配的时候,会分成4次去完成。至于溢出页,它们只在被需要的时候去分配,并且被位图页跟踪。位图页也是根据需要分配的。

注意哈希索引的大小不能减小。如果我们删除了一些索引行,被分配的页面也不会返还给操作系统,但是可以在VACUUMING操作后重新被新数据使用。减小索引大小的唯一选项是通过REINDEX重新构建索引或者使用VACUUM FULL命令。

参考资料

Hash Index Internals

Re-Introducing Hash Indexes in PostgreSQL

Examples

让我们看看怎么创建哈希索引。这里我们不再自己创建表,而是使用航空运输演示数据库。这次我们使用的是航班表

1
create index on flights using hash(flight_no);

如果postgreSQL是10以前的版本,创建哈希索引会出现下面的警告

1
WARNING:  hash indexes are not WAL-logged and their use is discouraged

这是因为10以前的版本中,哈希索引不支持WAL日志,这意味着哈希索引在数据库崩溃后不能恢复,必须重新建立索引,因此不鼓励使用。但是10以后的版本解决了这个问题。

1
explain (costs off) select * from flights where flight_no = 'PG0001';
1
2
3
4
5
6
7
                     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)
散列语义

但是为什么哈希索引几乎从PostgreSQL诞生到9.6版本之前都是无法使用的呢?事情是这样的,数据库管理系统广泛使用散列算法(尤其是哈希连接和哈希分组),然后系统必须知道将哪个散列函数应用到哪个数据类型。但是这种对应关系不是静态的,不能一劳永逸的设置,因为PostgreSQL允许动态添加新的数据类型。这种关系是通过哈希的访问方法被存储起来,表现为辅助函数和操作符族的关联。操作符和操作符族

1
2
3
4
5
6
7
8
9
10
 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;
1
2
3
4
5
6
7
   opfamily_name    | opfamily_procedure
--------------------+--------------------
abstime_ops | hashint4
aclitem_ops | hash_aclitem
array_ops | hash_array
bool_ops | hashchar
...

尽管上面右列中的函数没有写在文档里,但它们可用于计算对应数据类型值的哈希码。

1
select hashtext('one');
1
2
3
4
  hashtext  
------------
1793019229
(1 row)
属性

现在我们来看看哈希索引的属性,这里我们还用上一篇讲到的查询方法来查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 amname |     name      | pg_indexam_has_property 
--------+---------------+-------------------------
hash | can_order | f
hash | can_unique | f
hash | can_multi_col | f
hash | can_exclude | t
hash | can_include | f


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

散列函数不保留顺序关系,从一个哈希值小于另外一个哈希值也无法得出键值的大小关系。因此,哈希索引只能用来进行相等比较:

1
2
3
4
5
6
7
8
9
10
 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;
1
2
3
4
5
6
opfamily_name |  opfamily_operator  
---------------+----------------------
abstime_ops | =(abstime,abstime)
aclitem_ops | =(aclitem,aclitem)
array_ops | =(anyarray,anyarray)
bool_ops | =(boolean,boolean)

因此哈希索引无法返回有序数据,出于同样原因,哈希索引不会操作NULL:等于操作对于NULL值没有意义。

既然哈希索引不存储键值,因此也不能用于index-only

哈希索引也不支持多列索引

内部

从版本 10 开始,可以通过“pageinspect”扩展查看哈希索引内部结构。

1
create extension pageinspect;

然后可以从mainPage中查询元组数量和最大桶数

1
select hash_page_type(get_raw_page('flights_flight_no_idx',0));
1
2
3
4
 hash_page_type 
----------------
metapage
(1 row)
1
2
select ntuples, maxbucket
from hash_metapage_info(get_raw_page('flights_flight_no_idx',0));
1
2
3
4
 ntuples | maxbucket 
---------+-----------
33121 | 127
(1 row)

一个bucket中活元组和死元组(可以被vacuumed)的数量

1
select hash_page_type(get_raw_page('flights_flight_no_idx',1));
1
2
3
4
hash_page_type
----------------
bucket
(1 row)
1
2
 select live_items, dead_items
from hash_page_stats(get_raw_page('flights_flight_no_idx',1));
1
2
3
4
 live_items | dead_items 
------------+------------
407 | 0
(1 row)

但是,如果不检查源代码,几乎不可能弄清楚所有可用字段的含义。如果你想这样做,你应该从 README 开始