标签
PostgreSQL , 10.0 , hash index
背景
hash index是PostgreSQL中一个非常老的索引访问方法，也是非常经典的索引。
hash index中存储的是索引字段的hash value，而不是原始值，btree索引中存储的是原始值。
因此，当字段非常大时，btree索引可能无法使用。
例如
postgres=# create table test_hash_btree(c1 text);
CREATE TABLE
postgres=# insert into test_hash_btree values (repeat(random()::text,10000));
INSERT 0 1
postgres=# create index idx on test_hash_btree (c1);
CREATE INDEX
postgres=# insert into test_hash_btree values (repeat(random()::text,100000));
ERROR: index row requires 19504 bytes, maximum size is 8191
postgres=# drop index idx;
DROP INDEX
postgres=# create index idx on test_hash_btree using hash(c1);
WARNING: hash indexes are not WAL-logged and their use is discouraged
CREATE INDEX
postgres=# insert into test_hash_btree values (repeat(random()::text,100000));
INSERT 0 1
postgres=# insert into test_hash_btree values (repeat(random()::text,10000000));
INSERT 0 1
这种情况下可以使用hash index，而正因为 hashindex中存储 的是哈希，所以它只能用作等值查询。
除非有一种哈希函数能保证哈希后的值和哈希前的值顺序具备一致性。否则hash index是无法支持排序、>,<,>=,<=的查询的。
哈希索引的结构
哈希索引包含4种页，meta page, primary bucket page, overflow page, bitmap page.
metapage（0号页） , 包含了HASH索引的控制信息，指导如何找到其他页面（每个bucket的primary page），以及当前存储概貌。其他索引的0号页基本都是这一个套路。
primary bucket page，hash index将存储划分为多个bucket（逻辑概念），每个bucket中包含若干page（每个bucket的page数量不需要一致），当插入数据时，根据计算得到的哈希，通过映射算法，映射到某个bucket，也就是说数据首先知道应该插入哪个bucket中，然后插入bucket中的primary page，如果primary page空间不足时，会扩展overflow page，数据写入overflow page.
在page中，数据是有序存储（TREE），page内支持二分查找(binary search)，而page与page之间是不保证顺序的，所以hash index不支持order by。
overflow page，是bucket里面的页，当primary page没有足够空间时，扩展的块称为overflow page.
bimap page，记录primary , overflow page是否为空可以被重用。
注意bucket, page都没有提供收缩功能，即无法从OS中收缩空间，但是提供了reuse(通过bitmap page跟踪）.
10.0 哈希索引增强
1. Cache Hash Index meta page
缓存hash index meta page页到backend process的私有内存中，减少meta page的访问。
2. Concurrent Hash Indexes
大幅提升查询性能，超过BTREE接近一倍。
Patch_Ver/Client count 1 8 16 32 64 72 80 88 96 128
HEAD-Btree 19397 122488 194433 344524 519536 527365 597368 559381 614321 609102
HEAD-Hindex 18539 141905 218635 363068 512067 522018 492103 484372 440265 393231
Patch 22504 146937 235948 419268 637871 637595 674042 669278 683704 639967
% improvement between HEAD-Hash index vs Patch and HEAD-Btree index vs
Patch-Hash index is:
Head-Hash vs Patch 21.38 3.5 7.9 15.47 24.56 22.14 36.97 38.17 55.29 62.74
Head-Btree vs. Patch 16.01 19.96 21.35 21.69 22.77 20.9 12.83 19.64 11.29 5.06
This data shows that patch improves the performance of hash index upto
62.74 and it also makes hash-index faster than btree-index by ~20% (most
client counts show the performance improvement in the range of 15~20%.
For the matter of comparison with btree, I think the impact of performance
improvement of hash index will be more when the data doesn't fit shared
buffers and the performance data for same is as below:
Data doesn't fits in shared buffers
scale_factor - 3000
shared_buffers - 8GB
Client_Count/Patch 16 64 96
Head-Btree 170042 463721 520656
Patch-Hash 227528 603594 659287
% diff 33.8 30.16 26.62
The performance with hash-index is ~30% better than Btree. Note, that for
now, I have not taken the data for HEAD- Hash index. I think there will
many more cases like when hash index is on char (20) column where the
performance of hash-index can be much better than btree-index for equal to
searches.
Note that this patch is a very-much WIP patch and I am posting it mainly to
facilitate the discussion. Currently, it doesn't have any code to perform
incomplete splits, the logic for locking/pins during Insert is yet to be
done and many more things
这个patch的讨论，详见邮件组，本文末尾URL。
PostgreSQL社区的作风非常严谨，一个patch可能在邮件组中讨论几个月甚至几年，根据大家的意见反复的修正，patch合并到master已经非常成熟，所以PostgreSQL的稳定性也是远近闻名的。
参考
https://commitfest.postgresql.org/13/715/
https://commitfest.postgresql.org/10/647/
src/backend/access/hash/README
