DWS 索引详解

1. 前言

• 适用版本：【8.1.3及以上】

本文主要介绍dws中支持的索引类型和使用场景，并对部分索引结构进行讲解，揭开索引的神秘面纱，最后对一些索引问题进行阐述。

2. 索引简介

索引是一组映射，Key是我们要搜索的元素，可以是一个属性(单列索引)也可以是多个属性(联合索引)，value是key所在的位置：TID。索引的作用是加快我们对特定属性的搜索速度，不用每次都将整个表扫描一遍，类似于书的目录。下表列出了常见的索引类型

2.1 常见索引介绍

2.1.1 btree

B-tree索引的行数据被组织成页面。叶子页面中的行数据，存放的是<key, TID>键值对。非叶子页面中存放的是<minvalue, childptr>键值对，childptr指向本页面的孩子页面（可以是叶子页面，也可是其它非叶子页面），minvalue是子页面中的最小值。

• B-tree是平衡树，有序存储索引KEY值和TID；
• 对于索引上的过滤条件，通过KEY快速找到对应的叶子节点，然后再通过TID找到实际记录；
• 索引中的数据以非递减的顺序存储（页之间以及页内都是这种顺序），同级的数据页由双向链表连接；
• 支持单列索引和复合（多列）索引，多列复合索引适用于多列组合查询，B-tree索引对于查询条件的顺序有要求；
• B-tree索引可以处理等值和范围查询；
• 索引页面不存储事务信息；

下图是一个整数列的索引btree结构

对于寻找数据n=49的情况，索引扫描。如图从root节点（4, 32,64）出发，根据从 32 ≤ 49 < 64 计算出子节点中的值范围，找到子节点（32,43,49），接下来，递归地重复相同的过程，直到我们到达一个叶节点（43,49)，从中可以获取所需的 TID。

可以看到上面有两个49，由于我们的数据存在重复值，且值可能存在不同的page中，所以上面读到叶节点（43,49）后，还继续往右读，找到另一个叶子节点（49,62）

2.1.2 psort

psort索引用于列存表的索引，它利用了列存表原有min\max稀疏索引的特性，通过局部排序，使得列存索引的效率大大提高。下面首先对列存及其min\max稀疏索引的原理进行简要介绍，再此基础上，进一步介绍psort索引的基本原理。

列存表的每一列会有一个CUDesc表 ，会记录每个 CU 的 min 和 max 值，这个min\max可以作为稀疏索引进行粗过滤， 但如果业务的数据模型较为离散，查询时通过 min 和 max 值去过滤 CU 会出现大量的 CU 误读取，例如每个 CU 的 min 和 max跨度都比较大时，可能导致所有CU都要去扫描，其查询效率接近全表扫描。针对此问题就引出了psort索引

Psort索引数据结构示意如下图所示：

基本原理：
在每批次插入数据时，取出某列的数据，排序之后，将该列数据存储在一个新的列存表记为CPsortIndexRel中，会存储每条数据和对应的tid信息。对改索引表有一个对应的CUDesc，会记录min/max，这里的CU相比原始的CU，每个批次的min/max不重叠，然后在查询的时候可以顺序扫描找到对应cu，进而在有序的cu内找到要过滤的数据。

例如对于查询 select * from … where c = 160

对索引表的Cudesc表进行顺序扫描，根据min/max能找到cu0_1 和cu1_1，接着对着两个cu进行查询，由于cu内的数据是有序的，可以采样二分法进行查询，最后在cu1_1中找到了160，找到其tid信息，就可以找到原始数据位置。

优点：

• 相比于之前的min\max稀疏索引而言，由于每个批次内的数据是有序的，因此利用psort索引的过滤效果大大提高，CU误读取的概率大大降低，因此点查询和小数据量查询的效率大大提高。
• 由于建立psort的过程中是对每个批次的数据分别排序，因此相比于Btree索引，排序的代价大大降低，每批次数据导入的效率较高。

缺点：

• 当批次数目较多时，利用psort误读取的可能性增大，效率下降，平均耗时增加。
• 在查找的过程中对索引的CUDesc表顺序扫描，因此效率远低于Btree的搜索。

2.1.3 gin

GIN索引结构是一个B-tree，它的每个节点是存储词素，每个词素指向多个tid，使用为list(posting list)或者b-tree(posting tree)存储这些tid，少的时候用list，多的时候用b-tree。适用于复合类型的元素查询，如array，text, json。

如图下面就是一个gin索引树，对于某些元素出现在多个数据行中，就会以list或者btree存储

create table ts(doc text, doc_tsv tsvector);
update ts set doc_tsv = to_tsvector(doc);
create index on ts using gin(doc_tsv);

下面输出的是ts表的doc分词情情况，第一列是doc的位置，最后一列是每个词对应该doc的index

下图对应着索引树示意图，整个索引结构为btree，例如对于farm这个词出现在多个位置，存储方式为btree

2.2 特殊类型

创建一个普通表：

DROP TABLE IF EXISTS customer_address;
CREATE TABLE customer_address
(
    ca_address_sk       INTEGER                  NOT NULL   ,
    ca_address_id       CHARACTER(16)            NOT NULL   ,
    ca_street_number    CHARACTER(10)                       ,
    ca_street_name      CHARACTER varying(60)               ,
    ca_street_type      CHARACTER(15)                       ,
    ca_suite_number     CHARACTER(10)                    
)
DISTRIBUTE BY HASH (ca_address_sk);
CREATE TABLE tpcds.customer_address_bak AS TABLE tpcds.customer_address; 

2.2.1 唯一索引

假如对ca_address_id列有唯一性要求，可以创建唯一索引，插入数据会进行唯一性检查

CREATE UNIQUE INDEX index_address_id ON customer_address_bak(ca_address_id);

2.2.2 多字段索引

假如用户需要经常查询表tpcds.customer_address_bak中ca_address_sk是5050，且ca_street_number小于1000的记录，使用以下命令进行查询。

SELECT ca_address_sk,ca_address_id FROM tpcds.customer_address_bak WHERE ca_address_sk = 5050 AND ca_street_number < 1000; 

使用以下命令在字段ca_address_sk和ca_street_number上定义一个多字段索引。

CREATE INDEX more_column_index ON tpcds.customer_address_bak(ca_address_sk ,ca_street_number ); 

2.2.3 部分索引

如果只需要查询ca_address_sk为5050的记录，可以创建部分索引来提升查询效率。

CREATE INDEX part_index ON tpcds.customer_address_bak(ca_address_sk) WHERE ca_address_sk = 5050; 

2.2.4 表达式索引

假如经常需要查询ca_street_number小于1000的信息，执行如下命令进行查询。

SELECT * FROM tpcds.customer_address_bak WHERE trunc(ca_street_number) < 1000; 

可以为上面的查询创建表达式索引

CREATE INDEX para_index ON tpcds.customer_address_bak (trunc(ca_street_number));

3. 索引的创建原则

索引可以提高数据的访问速度，但同时也增加了插入、更新和删除操作的处理时间。所以是否要为表增加索引，索引建立在哪些字段上，是创建索引前必须要考虑的问题。需要分析应用程序的业务处理、数据使用、经常被用作查询的条件或者被要求排序的字段来确定是否建立索引。

3.1 不同索引适用场景

• btree：B-tree索引使用一种类似于B+树的结构来存储数据的键值，通过这种结构能够快速的查找索引。btree适合支持比较查询以及查询范围。
• gin：GIN索引是倒排索引，可以处理包含多个键的值（比如数组）。
• gist：Gist索引适用于几何和地理等多维数据类型和集合数据类型。
• Psort：Psort索引。针对列存表进行局部排序索引。

行存表支持的索引类型：btree（行存表缺省值）、gin、gist。列存表支持的索引类型：Psort（列存表缺省值）、btree、gin。

说明：对于点查询场景，推荐建立btree索引。

3.2 索引列选择原则：

索引建立在数据库表中的某些列上。因此，在创建索引时，应该仔细考虑在哪些列上创建索引。

• 在经常需要搜索查询的列上创建索引，可以加快搜索的速度。

• 在作为主键的列上创建索引，强制该列的唯一性和组织表中数据的排列结构。

• 在经常使用连接的列上创建索引，这些列主要是一些外键，可以加快连接的速度。

• 在经常需要根据范围进行搜索的列上创建索引，因为索引已经排序，其指定的范围是连续的。

• 在经常需要排序的列上创建索引，因为索引已经排序，这样查询可以利用索引的排序，加快排序查询时间。

• 在经常使用WHERE子句的列上创建索引，加快条件的判断速度。

• 为经常出现在关键字ORDER BY、GROUP BY、DISTINCT后面的字段建立索引。

  说明：

  • 索引创建成功后，系统会自动判断何时引用索引。当系统认为使用索引比顺序扫描更快时，就会使用索引。
  • 索引创建成功后，必须和表保持同步以保证能够准确地找到新数据，这样就增加了数据操作的负荷。因此请定期删除无用的索引

4. bitmap index scan

bitmap索引是一种在基础索引上的二级索引，是为了解决普通索引进行的随机IO效率低的问题。位图索引扫描是将普通索引扫描中的随机IO，尽量转换成顺序IO，降低执行计划的代价。它首先访问索引数据，过滤出符合提交的数据的索引信息(CTID)，然后根据CTID来进行聚合和排序，将要访问数据页面有序化，同时数据访问的随机IO也转换成顺序IO。对于多索引列的情况，可以对命中的bitmap做位运算，过滤出要去真正查询的page

如下图，对a和b列有建立索引，查询时会对建立page的bitmap， 对两列索引命中后的bitmap进行与运算，就能得到最后要扫描的page，且page是排序过的，会进行顺序扫描

CREATE TABLE t1(a INTEGER, b INTEGER) DISTRIBUTE BY HASH(a);
INSERT INTO t1 SELECT generate_series(1, 100), generate_series(1, 100) FROM (VALUES(0)) tmp;
CREATE INDEX ON t1(a);
CREATE INDEX ON t1(b);

SET enable_seqscan = OFF;
SET enable_indexscan = OFF;

下面查询是走的bitmap index scan,可以看到生成了一个BitmapAnd算子，对两列的bitmap做与运算，确定出要扫描的page

test=# EXPLAIN(COSTS OFF, NODES OFF)
SELECT /*+ SET(force_bitmapand ON) */ COUNT(*) FROM t1 WHERE a = 3 AND b = 5;
                  QUERY PLAN                   
-----------------------------------------------
  id |              operation               
 ----+--------------------------------------
   1 | ->  Aggregate                        
   2 |    ->  Streaming (type: GATHER)      
   3 |       ->  Aggregate                  
   4 |          ->  Bitmap Heap Scan on t1  
   5 |             ->  BitmapAnd(6, 7)      
   6 |                ->  Bitmap Index Scan 
   7 |                ->  Bitmap Index Scan 
 
 Predicate Information (identified by plan id)
 ---------------------------------------------
   4 --Bitmap Heap Scan on t1
         Recheck Cond: ((b = 5) AND (a = 3))
   6 --Bitmap Index Scan
         Index Cond: (b = 5)
   7 --Bitmap Index Scan
         Index Cond: (a = 3)

5. 索引的可见性与可用性

许多索引都作为主键或唯一约束用于保证业务数据的准确性。但在业务执行过程中，索引可能会导致查询业务性能劣化。有时候就需要对索引设置为不可以用（UNUSABLE ）或者不可见（invisible）。

索引的可见性指的是该索引是否对CBO优化器可见，即CBO优化器在生成执行计划的时候是否考虑该索引,可以看作是索引的一个属性。如果一个索引设置为不可见。 默认情况下CBO优化器生成执行计划的时候，不再考虑该索引。与可见索引一样，执行DML操作时，数据库会相应维护索引的数据。

索引可用性是指改索引是否需要失效不再维护，正常情况下，索引都是可用的。当索引不可用(unusable)时, 执行后数据库将不再对被执行索引进行数据更新维护。想要被重新使用，需要重新rebuild索引，或者先drop再create。

• 设置为不可见：

​ ALTER INDEX … SET (invisible= on)语法，执行后，支持在保持索引数据更新的前提下，查询时使索引不可见。

• 设置为不可用：

​ ALTER INDEX … UNUSABLE，执行后，索引不可用，且不会更新

​ ALTER INDEX … REBUILD; 索引重新使用

下面举例来说明：

CREATE TABLE t1 (a int, b int) distribute by hash(a);
INSERT INTO t1 SELECT generate_series(1, 500), 1;
CREATE UNIQUE INDEX index_t1_a ON t1(a);

1.默认索引可见，查询的时候生成了index scan

test=# set enable_fast_query_shipping=off;
SET
test=# set ENABLE_SEQSCAN=off;
SET
test=# explain select * from t1 where a < 20;
                                  QUERY PLAN                                  
------------------------------------------------------------------------------
  id |           operation           | E-rows | E-memory | E-width | E-costs 
 ----+-------------------------------+--------+----------+---------+---------
   1 | ->  Streaming (type: GATHER)  |     20 |          |       8 | 12.45   
   2 |    ->  Bitmap Heap Scan on t1 |     20 | 1MB      |       8 | 6.45    
   3 |       ->  Bitmap Index Scan   |     20 | 1MB      |       0 | 4.33    
 
 Predicate Information (identified by plan id)
 ---------------------------------------------
   2 --Bitmap Heap Scan on t1
         Recheck Cond: (a < 20)
   3 --Bitmap Index Scan
         Index Cond: (a < 20)

2.对索引设置不可见，可以看到生成的计划就不走索引扫描了

test=# ALTER INDEX index_t1_a SET (invisible= on);
ALTER INDEX

test=# \d+ index_t1_a
        Index "public.index_t1_a"
 Column |  Type   | Definition | Storage 
--------+---------+------------+---------
 a      | integer | a          | plain
unique, btree, for table "public.t1"
Options: invisible=on

test=# explain select * from t1 where a < 20;
                                      QUERY PLAN                                      
--------------------------------------------------------------------------------------
  id |          operation           | E-rows | E-memory | E-width |     E-costs      
 ----+------------------------------+--------+----------+---------+------------------
   1 | ->  Streaming (type: GATHER) |     20 |          |       8 | 1000000000518.50 
   2 |    ->  Seq Scan on t1        |     20 | 1MB      |       8 | 1000000000512.50 
 
 Predicate Information (identified by plan id)
 ---------------------------------------------
   2 --Seq Scan on t1
         Filter: (a < 20)

3.设置为不可用，也不走索引扫描了

test=# ALTER INDEX index_t1_a UNUSABLE;
ALTER INDEX
test=# explain select * from t1 where a < 20;
                                      QUERY PLAN                                      
--------------------------------------------------------------------------------------
  id |          operation           | E-rows | E-memory | E-width |     E-costs      
 ----+------------------------------+--------+----------+---------+------------------
   1 | ->  Streaming (type: GATHER) |     20 |          |       8 | 1000000000518.50 
   2 |    ->  Seq Scan on t1        |     20 | 1MB      |       8 | 1000000000512.50 
 
 Predicate Information (identified by plan id)
 ---------------------------------------------
   2 --Seq Scan on t1
         Filter: (a < 20)
         

4.rebuild后又走索引扫描了

注意：如果失效后，插入了重复的数据，不会进行冲突检查，此后rebuild的时候会检查冲突

test=# ALTER INDEX index_t1_a REBUILD;
REINDEX
test=# explain select * from t1 where a < 20;
                                  QUERY PLAN                                  
------------------------------------------------------------------------------
  id |           operation           | E-rows | E-memory | E-width | E-costs 
 ----+-------------------------------+--------+----------+---------+---------
   1 | ->  Streaming (type: GATHER)  |     20 |          |       8 | 14.45   
   2 |    ->  Bitmap Heap Scan on t1 |     20 | 1MB      |       8 | 8.45    
   3 |       ->  Bitmap Index Scan   |     20 | 1MB      |       0 | 4.33    
 
 Predicate Information (identified by plan id)
 ---------------------------------------------
   2 --Bitmap Heap Scan on t1
         Recheck Cond: (a < 20)
   3 --Bitmap Index Scan
         Index Cond: (a < 20)

6. 索引的重建

数据库经过多次删除操作后，索引页面上的索引键将被删除，造成索引膨胀。例行重建索引，可有效的提高查询效率。

• 对于B-tree索引，例行重建索引可有效的提高查询效率。
  • 如果数据发生大量删除后，索引页面上的索引键将被删除，导致索引页面数量的减少，造成索引膨胀。重建索引可回收浪费的空间。
  • 新建的索引中逻辑结构相邻的页面，通常在物理结构中也是相邻的，所以一个新建的索引比更新了多次的索引访问速度要快。
• 对于非B-tree索引，不建议例行重建。

重建索引有以下两种方式：

• 先删除索引（DROP INDEX），再创建索引（CREATE INDEX）。

  在删除索引过程中，会在父表上增加一个短暂的排他锁，阻止相关读写操作。在创建索引过程中，会锁住写操作但是不会锁住读操作，此时读操作只能使用顺序扫描。

• 使用REINDEX语句重建索引。

  • 使用REINDEX TABLE语句重建索引，会在重建过程中增加排他锁，阻止相关读写操作。
  • 使用REINDEX INTERNAL TABLE语句重建desc表（包括）的索引，会在重建过程中增加排他锁，阻止相关读写操作。

假定在导入表“areaS”上的“area_id”字段上存在普通索引“areaS_idx”。重建索引有以下两种方式：

• 先删除索引（DROP INDEX），再创建索引（CREATE INDEX）

  1. 删除索引。

     DROP INDEX areaS_idx;
     

  2. 创建索引。

     CREATE INDEX areaS_idx ON areaS (area_id);
     

• 使用REINDEX重建索引。

  • 使用REINDEX TABLE语句重建索引。

    REINDEX TABLE areaS;
    

  • 使用REINDEX INTERNAL TABLE重建desc表（包括）的索引。

    REINDEX INTERNAL TABLE areaS;
    

7. 行存和列存表btree区别

列存表 B-tree 索引结构与行存表并无大的差别，列存表的 B-tree 索引在存储引擎侧是以行存形式组织。对于一般用于应对大数据批量分析性负载的列存储引擎来说，B-tree 索引有助于帮助列存储提升自身的点查效率，更好地适应混合负载。
行存储的 B-tree 索引数据中存储的是 key→ctid (键→行号)的映射，在列存储的场景下，这个映射依旧为 key→ctid。但列存储的结构并不能像行存储一样，通过ctid中的块号(block number)和偏移量(offset)直接找到此行数据在数据文件页面中的位置。列存储ctid中记录的是(cu_id，offset)，要通过 CUDesc 结构来进行查找。
在基于 B-tree 索引的扫描中，从索引中拿到 ctid 后，需要在对应的 CUDesc表中，根据 CUDesc 在 cu_id 列的索引找到对应的 CUDesc 记录，并由此打开对应的 CU 文件，根据偏移量找到数据。

此操作涉及大量的存储层性能开销，因此列存储的 B树索引，与列存储的其他操作一样，统一都会批量操作，会根据 B-tree 索引找到 ctid 的集合，然后对此集合进行排序，再批量地对排序后的 ctid 进行 CU 文件级别的查找与操作。这样可以做到顺序单调地进行索引遍历，大大减少了反复操作文件带来的 CPU 以及IO 开销。

8. 总结

本文主要介绍dws中支持的索引类型、使用场景以及创建原则。索引类型比较多，针对不同的场景选择不同的索引才能发挥的价值。同时索引也是双刃剑，索引页面占用额外空间，导致一定的磁盘膨胀，需要进行清理重建，而且索引扫描性能并不总是比顺序扫描性能更好，当不好的时候可以调整索引的可见性或者可用性。

9. 参考文档

1. PostgreSQL 14 Internals : Postgres Professional
2. Indexes in PostgreSQL — 4 (Btree)
3. 创建和管理索引
4. DWS 索引的正确“打开姿势”
5. OpenGauss 列存表btree索引