BRIN索引的使用

TeleDB for ADB从3.20版本开始支持BRIN索引，针对点查有2-3倍的效率提升，使用方法如下：

set optimizer = off; -- 禁用GPORCA
set enable_seqscan = off; -- 禁用查询优化器使用顺序扫描计划
set hdw_enable_logicpart_opt = on; -- 启用logicpart优化功能
set hdw_enable_brin_sort = on; -- 启用brin功能
set hdw_partition_table_ignore_relabel = on;

-- 在表上建立索引
create index idx_brin_data_event_mock_zws01 on public.data_event_mock_zws01 using brin(serv_id);
-- 对表按照索引进行排序
cluster idx_brin_data_event_mock_zws01 on public.data_event_mock_zws01;

限制：

• 目前只支持行存ao表
• 只支持单索引

索引不适合频繁写入数据的表。可以在表数据写入完成后运行一次cluster。cluster会扫描一遍数据并对表按照索引进行排序，带来较大IO消耗。

BRIN索引原理

Block Range Index

Brin是Block Range Index的简写，顾名思义，索引记录的是存储数据块中的元组字段的最大值和最小值，用于过滤不符合条件的数据块。以下图为例，右边的堆表包含三个block，第一个block中有4个tuple，字段上的值分别是1、3、2、5。因此，与这个block相对应的Brin的元组就记录了block的最小值1，最大值5。同理，7、8、8、10的最小值是7，最大值是10；9、11、11、12的最小值是9，最大值是12。这样就获得了一个Brin索引。

在执行带有条件的查询时，就可以利用Brin记录的这些信息，找到相应的block，同时滤掉大部分block，从而起到Index的作用。Brin Index是一种非常直观简单的Index。

Brin的优势和劣势

下面我们再来看一下Brin Index的优势和劣势。

• 优势：对于B-tree Index这样的密集索引，对应数据表的每一条数据，索引里也会存在一条数据，也就是说B-tree Index里的条目数目，大体上和数据表里的条目数是相当的。它的大小和数据表是一个量级的。但是Brin就完全不同了，数据表中的一个block或者一组block只会在Brin里生成一个条目，因此占用空间会非常小。Brin的另一个优势是创建快。和B-tree Index一样，在创建brin的过程中，需要对表做一次完整的扫描。但是由于写需求很小，创建速度会快很多。
• 劣势：当然Brin Index也会有劣势。Brin Index只有在数据具有一定的分布特点时才有用。如果数据在索引字段上没有任何的分布特性，即它的空间分布和在索引字段上的值是没有任何关系，数据在空间上是完全随机分布的，这种情况下，Brin Index的效率会很低，因为能过滤掉的block将很少。如果数据具有一定的分布特性，索引字段上的值和物理分布具有一定的关联，这种情况下，Brin的效率将很高。

Brin的体积

接下来我们具体分析一下Brin的体积，下图我们以PostgreSQL上默认的一个情况来举例。
在PostgreSQL中，默认情况下，每20个heap block生成一个Brin的元组。
这样的情况下，对于一个有6~7列的不大不小的表，我们认为Brin Tuple有20个bytes左右的大小。此时Brin的体积情况如下：

• Brin Tuple：20bytes
• Block Range：8K*20=160K
• Brin比Heap小8000倍
• 1TB的Heap表只需要125M的Brin

从这些数据大家可以看出，Brin Index的体积非常小，比B-tree Index具有数量级上的优势。

Brin Scan

下面我们来探讨一下Brin在PostgreSQL的堆表中，到底是如何起作用的。ADB并不支持堆表，不过基本原理依然共通。

Brin里记录了每个 block的最大值和最小值。大家可能都了解，PostgreSQL有三种scan的类型。如果没有索引的话，它只能进行sequential scan，即全表顺序扫描。如果有Index就可以进行Index Scan，即从Index里查询，Index里记录了所有字段的值，同时记录了指向数据元组的Tuple ID。如果从Index里查到一个Tuple ID，就可以从表中拉出一条数据，这就是Index Scan。

PostgreSQL提供的第三种Scan的方式叫Bitmap Index Scan。即从索引里查到Tuple ID后，不马上去通过Tuple ID取出Tuple，而是用这个Tuple ID建立一个bitmap，bitmap的每一位就代表了Tuple在存储中的一个位置。查询结束后，就建立起了一整套的bitmap，接着通过bitmap再去存储内处理和查询，这就叫Bitmap Index Scan。Bitmap Index相对于Index Scan的劣势在于，它必须建立一个bitmap, 而 bitmap会产生一些代价。但Bitmap Index的好处在于它把对于数据存储的随机读取变成了顺序读取，在数据量比较大的时候具有一定优势。

如果每次Bitmap Index Scan都建立一个无损的bitmap，bitmap可能非常大。而bitmap是一个内存中的数据结构，如果太大将导致内存不够用，因此bitmap是可以压缩的，压缩的方式也十分简单。当一个block被命中的Tuple比较多时，就可以直接用一个bit来代表整个block，从而把bitmap压缩到很小。而由于Brin Index索引的单位是Block或一组Block，输出的Bitmap天然是压缩到最小的情况，因此Brin Index其实可以被看作是最极端压缩的情况。

例如下面的例子中，得到的bitmap就是1、1、0、0。该bitmap起到了索引应有的作用，4个block中过滤了2个block，因此只需要扫描2个block的数据。Brin Scan生成bitmap以后，就可以完全复用bitmap index scan的代码了。

select * from t where a > 1 and a < 8;

Index Update Delete

在讲完Brin是如何被创建出来和在IndexScan中是如何起作用之后，我们来看一下Brin Index在Insert、Update、Delete中是如何起作用的。Brin在维护更新的逻辑较为简单。由于每个元组代表一组Block索引字段的最大、最小值，如果Insert或者Update新的数据超出了最大、最小值的范围，则更新元组；如果落在Brin的范围区间内，则不需要进行任何操作；

而Delete预期范围是缩小的，但很难有方式来知晓是否真的缩小，例如范围是1~5，删除4，范围没有缩小；但如果删除值为5的Tuple，由于可能存在很多个Tuple值均为5，很难知晓是否范围缩小了。因此在Delete的时候，不需要做任何操作。

随着Insert、Update的操作的执行，Brin的范围会慢慢变大，因此在整个更新的过程中可能会损失一些性能。但是由于brin index本身就是一个不追求精确的Index，在索引和Bitmap Index Scan之后，还要用查询条件进行过滤，因此不会产生错误结果。

Brin Vacuum

由于PostgreSQL采用的是MVCC的更新模式，在更新的过程中会产生很多"垃圾"，而vacuum就是清理"垃圾"的操作。对于普通的vacuum，由于不需要做block之间的数据挪动，只是在Block内部清理一些"垃圾"，并且挪动一些Tuple，但仅限于Block内部的挪动。因此vacuum不需要做任何操作。

Vacuum full由于过程中需要做block之间的数据挪动，因此需要重建索引。

Brin Storage

下面我们来看一下Brin的存储情况。

Heap表中，block之间的存储结构是非常简单的，是由一个个连续的文件组成，里面存储连续的block。因此Brin的前半部分是一个数组结构，数组的下标对应着block number。数组的value是Tuple ID，指向存储有最大最小值的Tuple。

Brin在AO Table上的实现

对于包括ADB在内的擅长于OLAP场景的数据库，Update和Delete的应用场景较少，而sequential scan的场景非常多。堆表会存在两个问题，第一，由于堆表更擅长于update，它的每个block都不能装满；第二，堆表结构很难进行压缩，在同样数据量的情况下，堆表的占用空间很大。这两个缺点会导致在进行sequential scan的过程中，存储的IO非常大，因此堆表结构并不适合OLAP数据库。针对这种情况，ADB设计了一种紧凑的数据结构，即AppendOnly Table。

AppendOnly Table是一种紧凑的数据格式，适用于较少进行Update/Delete的场景。Tuple以紧凑的方式存储在变长的Block中，所以Block在写入存储后不能修改，只能向后追加新的Block，在实现并发Insert的过程中可能会出现冲突，为了实现并发Insert，每个AO表逻辑上被分为多个AoSeg，每个事务向一个特定的AoSeg追加数据，这就是AoTable的基本结构。

这种基本结构上在实现brin的过程中会遇到一些困难。AO表是一个变长的block，同时有多个AoSeg，这篇文章中我们假定有128个AoSeg。brin的前半部分是被称为Revmap的逻辑上的数组，它是一维的连续的结构，而AoTable是多个不连续的AoSeg，且里面的block不一样大，如何将brin的Revmap和AoSeg进行对应呢？

我们首先来看变长的block，这其实并不会构成问题。由于每个AoSeg里都存在block number，虽然block是变长的block，但可以在逻辑上通过tupleID进行对应。熟悉PostgreSQL的小伙伴都知道，tupleID是由两个部分组成，前面四字节是block number，后四个字节是block内部的偏移量。对于AppendOnly Table，有了tupleID后，可以通过前四个字节分出逻辑上的block，从而block number可以和Revmap里数组的项一一对应起来。

那么AoSeg的tupleID，或 tupleID对应的block number的取值范围是多少呢？由于tupleID是4个字节，因此它的取值范围天然是从0到2^32-1。如果是一个堆表，由于它的block都是连续的，所有的block number在整个取值范围只占据了开头的一段，从而很容易和一个连续的结构进行对应。但AoTable则截然不同。它这128个AoSeg并不是集中的占用了某一小段的取值范围，而是均匀的分布在整个的取值范围之上。

如下图所示，第一个AoSeg的取值范围是从0开始，第二个AoSeg的取值范围则是从从(2^32)÷128的位置开始。最后一个AoSeg起始的block
number是(2^32)÷128*127开始的。也就是所有的 block
number均匀的分散在整个的取值空间当中。如果我们用一个连续的物理结构和这样分散的block number去一一对应，中间就会出现很多的空洞。由于整体是一个数组，空洞也需要为它分配空间，这样的话，Revmap就会变得非常大：(2^32)*3。因此不管AoSeg内有多大的数据，只要最后一个AoSeg里有数据，就必须初始化一个24g大小的Revmap，这种做法是完全不能接受的，因此我们必须对这个结构进行一定的改进。

那么ADB的改进思路是什么呢？我们在Revmap这一层之上再加一个上层结构。因为Revmap这一层是一个逻辑的数组，存放在一个block里。而上层结构存储的就是这个block里的block number。下层结构则可以变成按需分配的结构，即只有真正的数据对应的block number，才会给它分配空间。因为上层结构记录的是Revmap的block中的block number，就会有近5000倍的压缩比。

这样的话，虽然会有一些空洞，Revmap依然会非常小：

• Upper Level：定长数据段，约为3.2MB
• RevMap：变长数据段，大小随数据表数据量变化，向后增长
• BrinTuples：存放Min Max的数据段，Page结构和Heap Page相同

改进后，整个Brin Index的空间占用会回到一个合理的区间。在这种结构下，upper_level_index和
revmap_offset可以根据以下几个公式进行计算：

• record_number = 2^32 ÷ TidNumPerPage
• upper_level_index = blocknum ÷ TidNumPerPage
• revmap_offset = blocknum % TidNumPerPage

这样就可以得到一个在AoTable上，同时空间占用较合理的Brin Index。

性能测试

那么，这样的Brin Index会有怎样的的性能表现呢？我们进行一组测试来看一下。

这个测试非常的简单：

create table aocs(a int, b int) with(appendonly=true, ORIENTATION = column); 
insert into aocs select i,i from generate_series(1,10000000)i;
create index abidx on aocs using brin(b) with(pages_per_range=1);

我们先创建一个AOCS表，这个表只有两列：a列和b列。接着在AOCS表里insert 1000万条数据，在某个字段上创建一个 brin index，进行性能上的对比。

首先进行一次等值的查询：

select gp_segment_id,* from ao where b=999999;

得到的结果如下：

• seqscan: 3957.205 ms
• brin-bitmapscan: 36.456 ms

从以上结果可以看出，使用index比不使用index结果有了质的飞跃。

第二个测试，我们将条件的选择率升高：

select gp_segment_id,* from ao where b > 1000000 and b < 1010000;

得到的结果如下：

• seqscan: 5757.855 ms
• brin-bitmapscan: 57.838 ms

在选择率提高至千分之一。我们可以看到seqscan仍然很慢，但brin耗时降低了。

第三个测试中，我们继续将选择率进行提高：

select gp_segment_id,* from ao where b > 1000000 and b < 2000000;

在百分之10的选择率下，得到的结果如下：

• seqscan: 6413.329 ms
• brin-bitmapscan: 2241.363 ms

此时，seqscan依然很慢，但brin性能有了进一步的提升。

再来看一下空间占用情况：

• ao: 180,198,032
• abidx-brin: 6,553,600

从这三个测试可以看到，在数据具有较好的分布特性的前提下，brin index都有较好的性能，空间占用也不大。