PostgreSQL 索引-1.索引引擎

本文翻译自 https://habr.com/en/company/postgrespro/blog/441962/，已经得作者同意。

原文的概述部分拆分到了 <PostgreSQL 索引系列文章> 中，作为系列文章的概述。

索引

在 PostgreSQL 中，索引是一种特殊的数据库对象，主要用于加速数据访问。索引是一种辅助结构，每个索引都可以被删除并重建。你或许听过这种说法：DBMS 没有索引也可以正常运行，只是会慢一些。然而，并非如此，索引还可以强制执行一些完整性约束。

目前，PostgreSQL 9.6 支持 6 种内置索引类型，还有一种索引可以作为扩展。相信在不久的将来会支持更多的索引类型。

尽管所有索引类型都不尽相同，但每种索引最终都将一个 key（比如，被索引列的值）与表中包含该 key 的数据行相关联。每行数据都通过 TID（元组 id） 唯一标识，TID 中包含数据页在文件中的块号和数据行在块中的位置。也就是说，给定一个 key 或者其他一些关于该 key 的信息，我们可以快速读取那些包含我们感兴趣的信息的行，而无需扫描整张表。

索引以一定的维护成本加速了数据访问速度，理解这一点是很重要的。对于表中被索引数据的每个操作，无论插入、删除或更新，都需要在同一事务中更新该表的索引。需要注意的是，对于未在索引中的字段的更新并不会导致索引更新，这一技术称之为 HOT（Heap-Only Tuples）。

为了方便在系统中添加新的访问方法，PostgreSQL 实现了一套通用索引引擎接口，它的主要任务是从访问方法中获取 TID 并使用它们：

• 从数据行的对应版本中读取数据
• 使用 TID 或者预先构建的位图批量获取行版本 TID
• 结合隔离级别，检查该行在当前事务中的可见性

执行查询时会用到索引引擎。而执行查询所用的计划是在优化阶段由优化器生成的。优化器列举并评估执行查询的不同方法，它了解所有可能适用的访问方法的特性，比如该方法是否能够按照所需顺序返回数据，或者是否需要预先排序？该方法是否可以搜索 NULL 值？这些通常都是优化器解决的问题。

不仅仅只有优化器需要访问方法的信息。在构建索引时，系统必须考虑是否可以在多列上构建索引以及索引是否确保唯一性。

因此，每个访问方法都应该提供关于它们自身的所有必要的信息，低于 9.6 的版本使用 pg_am 系统表提供这些信息，而从 9.6 开始，被移动到了更深的层次，我们后续将进一步了解这个接口。

访问方法包含如下功能：

• 实现构建索引的算法并将数据映射到数据页上（以便 Buffer 缓冲管理器统一处理每个索引）
• 通过 “索引字段 操作符 表达式“ 这种形式的谓词在索引中检索信息
• 评估索引使用成本
• 管理并行处理需要获取的锁
• 生成 WAL（write-ahead log）记录

我们将首先介绍通用索引引擎的功能，随后介绍不同的访问方法。

索引引擎

索引引擎使 PostgreSQL 能够统一处理各种访问方法，但又兼顾到它们各自的特性。

主要表扫描方法

索引扫描（Index Scan）

使用索引提供的 TID，将使我们的查询处理流程有所不同。我们来看一个例子。

postgres=# create table t(a integer, b text, c boolean);
postgres=# insert into t(a,b,c)
  select s.id, chr((32+random()*94)::integer), random() < 0.01
  from generate_series(1,100000) as s(id)
  order by random();
postgres=# create index on t(a);
postgres=# analyze t;

我们创建一个有三个字段的表。第一个字段包含从 1 到 100000 的整数，并在该字段上创建索引。第二个字段包含各种除不可打印字符之外的 ASCII 字符，第三个字段包括一个逻辑值，大约 %1 的行这个字段是 true，其他均为 false。该表中的数据按照随机顺序插入。

让我们尝试用 a=1 这个条件选择一个值。注意，该条件类似 “索引字段 操作符 表达式“ 这种形式，操作符是 equal(=) ，表达式是 1 。多数情况下，如果要使用索引，查询条件必须符合这种形式才行。

postgres=# explain (costs off) select * from t where a = 1;
          QUERY PLAN          
-------------------------------
 Index Scan using t_a_idx on t
   Index Cond: (a = 1)
(2 rows)

在这个例子中，优化器决定使用索引扫描（Index Scan）。通过索引扫描，访问方法逐个返回 TID 值，直到最后一个满足条件的行。索引引擎通过 TID 依次访问表中的数据行，获取行版本，根据多版本并发规则检测其可见性，最后返回获取到的数据。

位图扫描（Bitmap Scan）

当我们处理的数据很少时，索引扫描往往表现很好。然而，随着检索行数的增加，很有可能多次访问相同的数据页，此时，优化器就会切换到位图扫描（bitmap scan）。

postgres=# explain (costs off) select * from t where a <= 100;
             QUERY PLAN            
------------------------------------
 Bitmap Heap Scan on t
   Recheck Cond: (a <= 100)
   ->  Bitmap Index Scan on t_a_idx
         Index Cond: (a <= 100)
(4 rows)

扫描方法首先返回所有满足条件的 TID（Bitmap Index Scan 节点），通过这些 TID 构建行版本的位图。然后从表中读取行版本（Bitmap Heap Scan），每个数据页仅需读一次。

注意，第二步中，可能会重建检查检索条件（Recheck Cond）。检索到的行数可能太大，以至于行版本的位图无法全部放在内存（由 work_mem 参数控制）。这种情况下，仅会为那些至少包含一个满足查询条件的行版本的数据页构建位图，这种 lossy （有损的）位图仅需较少的空间，但当读取一个数据页时，需要重新检查该页中的所有行，判断其是否满足查询条件。需要注意的是，即使返回较少的行，并且使用 exact 位图（如例子中所示）， Recheck Cond 还是会出现在计划中，尽管它实际并不会执行。

译者注： lossy 位图和 exact 位图

lossy 位图其实是基于页的位图，即某个数据页中有满足条件的数据，则将该页对应的bit位进行标记，而该页中具体那行数据是满足条件的则不予标记，文中也提到，满足条件的行特别多的时候，为每行数据都维护一个标记位需要内存较多，可能无法全部放在内存中。因此，在读取到某个有满足条件的数据的页时，需要遍历整个数据页，判断具体那些行是满足条件的。

exact 位图则是在数据比较少的情况下，对每一行数据进行标记，这样可以根据标记直接读取对应的行，无需再次检查是否满足条件。

如果查询条件涉及多个字段，且这些字段上都有索引，位图扫描可以同时使用多个索引（如果优化器认为这样查询比较高效）。对于每个索引，都会为其构建行版本的位图，然后执行位布尔乘法（如果表达式由 AND 连接）或布尔加法（如果表达式由 OR 连接）。例如：

postgres=# create index on t(b);
postgres=# analyze t;
postgres=# explain (costs off) select * from t where a <= 100 and b = 'a';
                    QUERY PLAN                    
--------------------------------------------------
 Bitmap Heap Scan on t
   Recheck Cond: ((a <= 100) AND (b = 'a'::text))
   ->  BitmapAnd
         ->  Bitmap Index Scan on t_a_idx
               Index Cond: (a <= 100)
         ->  Bitmap Index Scan on t_b_idx
               Index Cond: (b = 'a'::text)
(7 rows)

这里 BitmapAdd 节点对两个位图执行按位 and（与） 操作。

位图扫描使我们避免重复扫描同一个数据页。但如果数据页中数据的物理排序与索引记录完全相同会怎么样？毫无疑问，我们不能完全依赖数据页的物理顺序，如果需要对数据排序，我们必须在查询中显式指定 ORDER BY 。但实际情况是，几乎所有的数据都是排好序的：比如，如果数据行按序插入，且此后不再更改；或者执行了 CLUSTER 命令。在这种已经排好序的场景中，构建位图就没有太大必要，常规的索引扫描也同样好用（除非我们考虑到联合使用其他索引的可能性）。因此，在选择访问方法时，计划器会参考一个特殊的统计信息，即物理行排序和逻辑排序的相关性：

postgres=# select attname, correlation from pg_stats where tablename = 't';
 attname | correlation
---------+-------------
 b       |    0.533512
 c       |    0.942365
 a       | -0.00768816
(3 rows)

绝对值趋近于 1 表示相关性高（如列 c ），相反，值接近 0 说明相关性低，分布比较混乱（如列 a ）。

顺序扫描（Sequential Scan）

为使扫描方法的构图相对完整，我们再来介绍下顺序扫描。需要注意的是，在非选择性条件下，优化器将优先选择全表顺序扫描，而非使用索引。

译者注：这里的非选择性（non-selective）条件，指选择性低的条件。

postgres=# explain (costs off) select * from t where a <= 40000;
       QUERY PLAN      
------------------------
 Seq Scan on t
   Filter: (a <= 40000)
(2 rows)

查询条件选择性（selectivity）越高，使用索引的效果越好。选择性越高，意味着满足条件的行越少。随着检索行数的增加，读取索引页的代价也会随之增加。

顺序扫描比随机扫描更快，这尤其适用于硬盘，将磁头带到特定磁道的物理操作比读取数据本身更加耗时。对于 SSD，这种影响则不太明显。有两个参数用于设置顺序扫描和随机访问的代价， seq_page_cost 和 random_page_cost ，这两个参数不仅可以全局设置，还可以在表空间级别设置，这样我们就可以根据不同磁盘子系统的特性对其进行调整。

覆盖索引

通常，访问方法的主要任务是返回满足条件的行的唯一标识符，以便索引引擎从这些行中读取必要的数据。但如果索引已经包含了查询所需的所有数据呢？这样的索引我们称之为覆盖索引，这种情况下，优化器可以使用 index-only scan 。

postgres=# vacuum t;
postgres=# explain (costs off) select a from t where a < 100;
             QUERY PLAN            
------------------------------------
 Index Only Scan using t_a_idx on t
   Index Cond: (a < 100)
(2 rows)

Index Only Scan 这个名字给人一种感觉，即索引引擎仅通过访问方法就可以获取到所有需要的信息而完全不需要访问表，但事实并非如此。因为，在 PostgreSQL 中，索引并没有存储供我们判断可见性的信息，因此，访问方法只是返回满足条件的行，并不关心它在当前事务中的可见性。

然而，如果索引引擎每次都需要访问数据表来判断可见性，那这种扫描方式就与一般的索引扫描没有任何区别了。

为解决这个问题，PostgreSQL 为表维护了一个称之为 可见性映射（visibility map）的结构，在这个映射中，vacuum 将数据没有发生改变的页标记为对所有事务可见，注意这里的事务与其开始时间和隔离级别无关。如果索引返回的行的标识符与此类数据页相关（译者注：即索引返回的行所在的数据页对所有事务均可见），则无需对其进行可见性检测。

因此，定期 vacuum 可以提升覆盖索引的效率。另外，优化器会考虑死元组（dead tuples）的数量，如果预测到评估可见性的代价比较高，则不使用 index-only scan 。

我们可以使用 EXPLAIN ANALYZE 命令了解强制访问数据表的次数：

postgres=# explain (analyze, costs off) select a from t where a < 100;
                                  QUERY PLAN                                  
-------------------------------------------------------------------------------
 Index Only Scan using t_a_idx on t (actual time=0.025..0.036 rows=99 loops=1)
   Index Cond: (a < 100)
   Heap Fetches: 0
 Planning time: 0.092 ms
 Execution time: 0.059 ms
(5 rows)

本例中，vacuum 刚刚完成，因此不需要访问表（HeapFetches：0）。通常情况下，该值越接近 0 越好。

并非所有索引都将索引值和行标识符一起存储，如果索引无法返回数据，则不能将其用于 index-only sacn 。

PostgreSQL 11 引入一个新的特性：INCLUDE-索引。如果有一个唯一索引缺少一些列，使其不能作为某些查询的覆盖索引怎么办？你不能简单地给索引添加列，这可能破坏其唯一性。该特性允许索引包含其他 non-key 列，这些列不会影响唯一性，也不能用于搜索谓词，但可以用于 index-only scan 。该特性由我的同事 Anastasia Lubennikova 开发。

NULL

NULL 在关系数据库中扮演着非常重要的角色，通常用于表示不存在或者未知值。

但一个特殊的值往往需要特殊处理。常规的布尔代数变成了三元代数；不清楚 NULL 应该小于还是大于常规的值（这需要特殊的排序规则，NULL FIRST 和 NULL LAST）；不清楚聚合函数是否应该考虑 NULL；计划器需要特殊的统计信息……。

从索引支持的角度来看，我们也不清楚是否需要索引 NULL 值。如果不索引 NULL 值，索引可能更紧凑。但如果索引 NULL 值，我们就能够将索引用于 “索引列 IS [NOT] NULL” 之类的条件，而且在没有为表指定任何查询条件的情况下依然可以使用覆盖索引（此时索引必须返回表中的所有行，包括 NULL 值）。

对于每种访问方法，开发者都需要单独考虑其是否索引 NULL 值。一般而言，都会索引 NULL 值。

多列索引

为了支持包含多列的查询条件，可以使用 多列索引（multicolumn indexes） （译者住：通常也称之为复合索引、联合索引或者组合索引）。比如，我们可以在表的两个字段上创建索引：

postgres=# create index on t(a,b);
postgres=# analyze t;

优化器很可能更倾向于使用这个索引，而不是位图扫描。因为我们可以直接获取到需要的 TID 而无需任何辅助操作。

postgres=# explain (costs off) select * from t where a <= 100 and b = 'a';
                   QUERY PLAN                  
------------------------------------------------
 Index Scan using t_a_b_idx on t
   Index Cond: ((a <= 100) AND (b = 'a'::text))
(2 rows)

多列索引也可以用于条件中包含部分索引列的情况，但条件中包含的索引列需要从多列索引的第一个开始：

postgres=# explain (costs off) select * from t where a <= 100;
              QUERY PLAN              
--------------------------------------
 Bitmap Heap Scan on t
   Recheck Cond: (a <= 100)
   ->  Bitmap Index Scan on t_a_b_idx
         Index Cond: (a <= 100)
(4 rows)

通常情况下，如果条件没有使用第一个字段，将不会使用该索引。但有时优化器可能认为使用索引比顺序扫描更加高效。我们将在介绍 btree 索引时再展开这个话题。

并非所有的访问方法都支持在多列上构建索引。

表达式索引

我们已经提到，如果要使用索引，检索条件需要类似 “索引字段 操作符 表达式” 这种形式。在如下例子中，由于索引字段在表达式中，导致不会走索引：

postgres=# explain (costs off) select * from t where lower(b) = 'a';
                QUERY PLAN                
------------------------------------------
 Seq Scan on t
   Filter: (lower((b)::text) = 'a'::text)
(2 rows)

重写以上查询无需太多时间，将操作符左侧替换为列名即可。但如果不能重写，表达式索引（函数索引）就可以助我们一臂之力：

postgres=# create index on t(lower(b));
postgres=# analyze t;
postgres=# explain (costs off) select * from t where lower(b) = 'a';
                     QUERY PLAN                    
----------------------------------------------------
 Bitmap Heap Scan on t
   Recheck Cond: (lower((b)::text) = 'a'::text)
   ->  Bitmap Index Scan on t_lower_idx
         Index Cond: (lower((b)::text) = 'a'::text)
(4 rows)

函数索引不是建立在表的字段上，而是建立在任意表达式上。对于类似 “索引表达式 操作符 表达式“ 这样的条件，优化器将会考虑函数索引。如果计算索引表达式的代价较高，那更新索引也会使用相当可观的计算资源。

谨记，数据库系统会为索引表达式单独采集一些统计信息，我们可以通过索引名在 pg_stats 视图中了解这些信息：

postgres=# \d t
       Table "public.t"
 Column |  Type   | Modifiers
--------+---------+-----------
 a      | integer |
 b      | text    |
 c      | boolean |
Indexes:
    "t_a_b_idx" btree (a, b)
    "t_a_idx" btree (a)
    "t_b_idx" btree (b)
    "t_lower_idx" btree (lower(b))
postgres=# select * from pg_stats where tablename = 't_lower_idx';

如有必要，可以像控制常规数据字段的直方图篮（histogram baskets）数量一样，控制索引表达式的直方图篮数量（注意，列名因索引表达式而异）。

postgres=# \d t_lower_idx
 Index "public.t_lower_idx"
 Column | Type | Definition
--------+------+------------
 lower  | text | lower(b)
btree, for table "public.t"
postgres=# alter index t_lower_idx alter column "lower" set statistics 69;

PostgreSQL 11 引入了一种更加简洁的方法，通过在 ALTER INDEX ... SET STATISITICS 命令中指定列的序号来控制索引的统计目标。该特性由我的同时 Alexander Korotkov 和 Adrien Nayrat 开发。

部分索引

有时候只需要对表中一部分行建索引。这通常与严重的非均匀分布有关：通过索引查找不常出现的值是有意义的，但通过全表扫描更容易找到出现频率高的值。

我们可以在 c 列建一个索引，数据库将按照我们预期的运行：

postgres=# create index on t(c);
postgres=# analyze t;
postgres=# explain (costs off) select * from t where c;
          QUERY PLAN          
-------------------------------
 Index Scan using t_c_idx on t
   Index Cond: (c = true)
   Filter: c
(3 rows)
postgres=# explain (costs off) select * from t where not c;
    QUERY PLAN    
-------------------
 Seq Scan on t
   Filter: (NOT c)
(2 rows)

索引的大小是 276 个页：

postgres=# select relpages from pg_class where relname='t_c_idx';
 relpages
----------
      276
(1 row)

但由于 c 列仅有 %1 的行的值是 true，因此，99% 的索引实际从未使用过。此时，我们创建一个部分索引：

postgres=# create index on t(c) where c;
postgres=# analyze t;

索引的大小减少至 5 个页：

postgres=# select relpages from pg_class where relname='t_c_idx1';
 relpages
----------
        5
(1 row)

有时空间占用大小和性能上的差异可能意义重大。

排序

如果访问方法以特定的顺序返回行的标识符，将会给优化器执行查询提供其他的选项。

我们可以扫描表并对其进行排序：

postgres=# set enable_indexscan=off;
postgres=# explain (costs off) select * from t order by a;
     QUERY PLAN      
---------------------
 Sort
   Sort Key: a
   ->  Seq Scan on t
(3 rows)

但我们也可以通过索引扫描，以期望的顺序返回：

postgres=# set enable_indexscan=on;
postgres=# explain (costs off) select * from t order by a;
          QUERY PLAN          
-------------------------------
 Index Scan using t_a_idx on t
(1 row)

所有访问方法中，只有 B-tree 索引可以返回排好序的数据，后续介绍 B-tree 索引时再做详细分析。

并发创建

创建索引时，通常需要持有表的 SHARE 锁，该锁允许从表中读数据，但禁止任何修改。

我们可以在表 t 上创建索引，同时在另一个会话查询该表来验证：

postgres=# select mode, granted from pg_locks where relation = 't'::regclass;
   mode    | granted
-----------+---------
 ShareLock | t
(1 row)

如果表很大，且被频繁的更新、插入和删除，创建索引时，这些修改操作需要等很长时间的锁，这将是难以接受的。

这种情况下，我们可以并行创建索引：

postgres=# create index concurrently on t(a);

该命令会给表加 SHARE UPDATE EXCLUSIVE 锁，该锁允许读和更新（不允许修改表结构、并行vacuum，analyze 或者同时在该表上建另一个索引）。

然而，硬币总有两面。首先，并发构建索引的速度比普通构建要慢，原因在于需要做两次表扫描，而且还需要等其他并行事务完成对数据的修改。

其次，并行创建索引可能出现死锁或者违反唯一性约束，这样的索引不能使用，需要删除并重建。不可用的索引会在 psql 的 \d 命令中被标记为 INVALID ，如下所示：

postgres=# select indexrelid::regclass index_name, indrelid::regclass table_name
from pg_index where not indisvalid;
 index_name | table_name
------------+------------
 t_a_idx    | t
(1 row)