PostgreSQL13新特性解读-Btree索引去重Deduplication
PostgreSQL13新特性解读-Btree索引去重Deduplication
背景
PostgreSQL13.0于2020年9月24日正式release，13版本的PG带来很多优秀特性：比如索引的并行vacuum，增量排序，btree索引deduplication，异构分区表逻辑订阅等。在这里面最闪亮的特性非deduplication莫属。
该特性由Peter Geoghegan于2020年2月27日提交，参考下面这个页面
https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=0d861bbb702f8aa05c2a4e3f1650e7e8df8c8c27
下面我们来看看这个重磅特性。
Deduplication从字面意思也很好理解：“重复数据删除”，总的来说这个功能使得PG数据库有了新的方式去处理重复的索引键值，这大大减小了btree索引所占用的空间，提升了索引扫描的性能，deduplication涉及到底层索引存储结构的变更。
在实际的生产环境中的数据表中可能有大量的重复数据，在13版本之前，每一个重复的数据都会占用索引的一个叶子元组leaf，这些重复的key值在索引页面中重复存储，带来很大的空间浪费。PostgreSQL13引入deduplication技术，通过deduplicate_items 参数开启（默认开启），B-Tree索引可以为重复项使用一种特殊的、节省空间的表示形式。
索引结构
理解deduplication的工作原理之前我们先了解一下PG索引的结构，如下图所示：
索引元组的结构是Key=xxx,TID=(block=xxx,Offset=xxx)，其中key代表索引的键值，也就是索引指向真实元组的字段值，TID是一个指向数据元组的指针数据结构，它包含两部分，第一部分是block块号，也可以叫页面号，通过页面号定位到数据所在页面，第二部分是offset，代表元组在该页面的偏移量，这个偏移量实际上就是页面头结构中的linepointer的值，它是页面内指向真实元组的指针。
Deduplication
了解了索引结构，再来看看deduplication的原理。Deduplication的工作原理是定期将多组重复元组合并在一起，为每个组形成一个“posting list”。列键值key在此表示中只出现一次。后面是一个TID排序数组，指向表中的行。这样我们就能理解了，deduplication就是将重复项的key值只存储一次，然后该key对应的TID变为一个数组，这个数组分别记录了这些相同元组的块号和偏移量。这样就大大减少了索引的存储大小，索引扫描查询的响应时间也可以大大减少。
Deduplication对于CREATE INDEX和REINDEX来说也是有益的。从表中获取的排序输入中遇到的每一组重复的元组在添加到当前叶子节点之前被批量合并到一个“posting list”中。每个posting list元组都包含尽可能多的TID。这样无需经过索引的单条插入以及重复数据的合并过程。这种一次性批处理操作很适合索引的创建和重建，能大大加快索引的创建速度。
可能细心的同学可能会提出一个问题：对于大量重复数据使用deduplication会带来很大的收益，那么对于唯一索引会不会带来较大的性能损耗？答案是影响很小甚至没有影响。对于唯一索引，deduplication有特殊的处理，它通常可以直接跳到拆分叶页，从而避免在无用的deduplication过程中导致的性能损失。如果你还是担心这个问题，那么你可以选择在唯一索引上关闭deduplicate_items这个存储参数，这个参数是索引级别的存储参数，可以对不同索引设置不同的值。
Deduplication的另一个好处在于能够有效预防索引的膨胀，因为PG索引并不关心mvcc机制，也就是说一条元组经过若干次更新后对应的索引中也可能会插入新的行指向新版本的元组。这里为什么说是可能，而不是一定会产生新的索引元组？因为PG有HOT堆内元组技术解决这个问题，大体思路就是使用数据页面上的元组结构中的t_ctid指针指向新元组，这时就可以继续通过原有的索引行继续访问到新的元组。但是HOT技术使用场景是有限的，它的两个不适用的场景是跨页面以及索引的key值被修改。而在真实的生产环境中索引的一条元组的更改往往伴随着key值的更改，这样便不适用于HOT更新，索引页就需要插入新的数据，这是如果使用deduplication技术就可以将这些索引项合并，减小索引的大小。
另外一个有意思的话题是对于null值的处理，在我们的想象里，null值应该不能适用deduplication，其实不然。对于大量重复的空值，B-Tree索引去重同样有效，因为根据B-Tree运算符类的相等规则，NULL值永远不会相等。对于空值而言我们可以简单的把它理解成索引值域中的其他值。
当然deduplication对于一些特定的数据类型不适用，这是为了保证语义的安全性，因为某些数据类型在一些情况下做合并是不安全的。
实验
下面通过实验，来看看PG13中btree索引的变化。对比的PG版本为PG11.3和PG13.0，表test1所有列相同，表test2所有列不相同。先模拟插入数据，pg11和pg13分别操作：
test=# create table test1(id int);
CREATE TABLE
test=# create table test2(id int);
CREATE TABLEtest1中插入16777216条重复数据
test=# select count(*) from test1;
count
----------
16777216
(1 row)test2中插入16777216条不重复数据
test=# insert into test2 select generate_series(1,16777216);
INSERT 0 16777216分别创建索引
test=# create index on test1(id);
CREATE INDEX
test=# create index on test2(id);
CREATE INDEX索引大小对比
PG13
test=# \di+
List of relations
Schema | Name | Type | Owner | Table | Persistence | Size | Description
--------+--------------+-------+----------+-------+-------------+--------+-------------
public | test1_id_idx | index | postgres | test1 | permanent | 111 MB |
public | test2_id_idx | index | postgres | test2 | permanent | 359 MB |
(2 rows)PG11
test=# \di+
List of relations
Schema | Name | Type | Owner | Table | Size | Description
--------+--------------+-------+----------+-------+--------+-------------
public | test1_id_idx | index | postgres | test1 | 359 MB |
public | test2_id_idx | index | postgres | test2 | 359 MB |
(2 rows)可以看到在数据重复的情况下，pg13的索引大小不到pg11的三分之一，没有重复数据的情况下，两者索引大小一致。
