本系列的内容主要翻译自Postgresql官方博客，为了便于理解，对于其中部分涉及到的知识，我在查阅相关资料的基础上做了补充。

原文: Indexes in PostgreSQL — 1

系列文章索引

介绍

这个系列的文章主要关注PostgreSQL中的索引。

每一个主题都可以从不同的方便来讲述。这里我们将会讨论使用数据库管理系统的开发人员感兴趣的几个问题：有哪些可以用的索引，为什么会有这么多不同种类的索引，怎么使用它们去加快查询速度。这些主题可以用几句话概括，但是我们希望好奇的开发者可以对内部的细节感兴趣，了解这些内部细节可以让你尊重他人的判断，也可以做出自己的决定。

开发一个新类型的索引不在这个系列范围之内，这需要有C语言编程的知识，而且相对于应用开发者，这更倾向于系统开发者的专业知识。出于同样的原因，我们不讨论编程接口，只关注有关怎么使用索引的内容。

在这篇文章中，我们将讨论与DDMS核心相关的通用索引引擎和单个索引访问方法(index access methods)的职责分配。在下篇文章中，我们将讨论访问方法接口(interface of the access method)和一些像类、操作符家族之类的关键概念。在这些虽然长但是很必要的内容后面，我们将会讨论几种索引的结构和应用:Hash、B-tree、GiST、SP-GiST、Gin、RUM、BRIN、Bloom。

索引

在PostgreSQL中，索引是一个主要用来加速数据获取的特殊的数据库对象。它们是辅助结构：每一个索引都会根据数据中的信息被删除或者重新创建。你可能偶尔听过这样的言论：数据库可以在没有索引的情况下工作，只不过运行的慢一点。然而，这并不完全对，索引还用于强制执行一些完整性约束。

到目前为止，PostgreSQL9.6内置了6种不同类型的索引，由于9.6版本的重大变化，还有多种索引可以通过添加拓展来获取。所以期待在将来新的类型的索引吧。

尽管不同类型的索引（也成为访问方法）之间都有差异，但是它们最终都会有一个key(例如被索引的列的值)和包含这个key的行相关联。每一行都被元组TID标识，TID是由文件中块的编号和这一行在这一块中的位置组成的。这说明，根据已知的键和一些相关的信息，我们可以快速读取那些包含我们感兴趣的信息的行，而无需扫描整个表。

这里的 块(Block) 和 页(Page) 是同一个东西，其默认大小为8kb。TID(8,100)代表的意思就是第9个Page的第101个item。什么是Page?

重要的是理解索引是以一定的维护成本来加快数据访问速度的。对于索引的数据的每一个操作，无论是插入、删除、还是更新，对应的索引也要更新，而且其更新是在同一个事务里的。但是，更新没有建立索引的表的字段不会导致索引的更新。这种技术被称为HOT(Heap-Only Tuples)

通用的索引引擎可以很容易让我们向系统中添加一个新的访问方法。其主要任务是从访问方法中获取TIDs，并且和它们一起工作。其中索引引擎负责的工作有

  • 从表中行的对应版本中读取数据
  • 通过TID或者使用预构建的位图(bitmap)批量获取行版本
  • 根据隔离级别，检查当前当前事务中行版本的可见性

在执行查询时候，会用到索引引擎。索引引擎会根据在优化阶段创建的计划来被调用。优化器需要经过整理和评估执行查询的不同方式，因此需要了解可能要用到的不同访问方法的能力。这个方法是否能够以所需的顺序返回数据，或者我们应该排序吗，这个方法能够用来搜索NULL值吗，这些都是优化器经常要解决的问题。

不仅优化器需要知道关于访问方法的相关信息。在创建索引的时候，系统也必须决定索引是否可以建立在表的哪几行上，索引是否可以确保唯一性。

因此每一个访问方法都必须提供有关自身的必要信息。在9.6版本以前，这些信息是记录在pg_am表中的。从9.6开始，这些数据被放在了一些特殊函数的内部(在下一篇文章中会讲到这个)。

剩下 的就是访问方法的任务了

  • 实现构建索引的算法，把数据映射到页面
  • 在索引中通过“索引字段 操作符 表达式”来搜索信息
  • 评估索引使用成本
  • 使用锁来正确进行并行处理
  • 生成WAL(write-ahead log)记录

预写日志 (WAL) 是确保数据完整性的标准方法。其核心概念是对数据文件（表和索引所在的位置）的更改必须仅在这些更改被记录后写入，即在描述更改的日志记录已刷新到永久存储之后。如果我们遵循这个过程，我们不需要在每次事务提交时将数据页刷新到磁盘。因为日志记录是顺序存储的，同步日志的成本远低于刷新数据页的成本。

索引引擎

索引引擎能够使数据库能够统一的使用各种访问方法，但是同时兼顾它们的特性。

主要扫描技术

索引扫描

我们可以不同的方式来使用索引提供的TIDs。让我们考虑下面这个例子

1
2
3
4
5
6
7
8
9
10
create table t(a integer, b text, c boolean);

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();
create index on t(a);

analyze t;  
#analyze命令会分析表中的数据生成统计信息，生成的信息会被优化器使用来生成执行计划

我们创建了包含3个字段的表，第一个字段是从1到100000的数字，并在这个字段上创建了索引。第2个字段上是除去不可打印字符的ASCII字符串，第3个字段大概有10%是true其余的是false。这些行以随机的顺序被插入到表中。

让我们先尝试用”a=1”来查询一个值。请注意这里的条件就是“索引字段 操作符 表达式”，其中操作符是”相等”，表达式是”1”。在大多数情况下，对于要使用的索引，其条件必须和这个相似

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

在这种情况下，优化器决定使用索引扫描。使用索引扫描，访问方法一个接一个的返回TID直到匹配的最后一行。索引引擎依次访问TID指示的行，获取行版本，根据多版本并发规则来检查其可见性，最后返回获取的数据。

位图(Bitmap)扫描

注，本节可以参考这个博客进行理解：Bitmap Scan In PostgreSQL

索引扫描在处理少数行的时候可以工作的很好。但是当行数增加的时候，经常会出现多次访问同一个Page。因此，优化器切换到Bitmap扫描

多次访问同一个表页面是指，比如访问方法先返回的TID为(1,1)，这时候索引引擎需要去加载第2个Page（编号从0开始，后同）去读取第2个Item；然后访问方法返回第二个TID为(2,2)，索引引擎就需要加载第3个Page，去读取第3个item；最后访问方法返回第三个TID为(1,2)，索引引擎就需要重新加载第2个Page去读取第3个item。这样就出现了重复IO读取。

看下面的例子

1
explain (costs off) select * from t where a <= 100;
1
2
3
4
5
6
7
             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 node)，然后根据这些TID来构建行版本位图。然后从表中读取行版本，每一个Page只会被读取一次。

比如说位图中记录了(1,1) (1,2)，索引引擎就加载第2个Page，然后读取第2个和第3个Item，即对同一个Page只需要读取一次。

注意第2步，条件会被重新检查。这是因为检索到的行数可能会非常大，从而超过RAM的大小(通过work_mem参数限制,默认为4MB)。这种情况下，bitmap只记录那些最少包含一条匹配数据的Page(例如对于(1,1) (1,2)，只记录一个1），这样的话，”有损”的Bitmap所需要的空间就会变少。但是当读取Page的时候，我们需要根据条件来重新检查这个Page中包含的行。注意，即使检索的行比较小，然后位图是“精确”位图(即精确记录了每一个TID，而不是只记录了Page)，”Recheck Cond”在计划中仍然会存在，虽然没有被真正执行。参考资料

如果查询条件中包含多个被索引的字段，位图扫描允许同时使用多个索引（如果优化器认为这样能够提升查询效率）。对于每一个索引条件，都会为其建立行版本的位图，然后对其执行按位布尔运算，如果是AND，执行布尔乘法，OR的话执行布尔加法。

例如

1
2
3
4
5
create index on t(b);

analyze t;

explain (costs off) select * from t where a <= 100 and b = 'a';
1
2
3
4
5
6
7
8
9
10
                    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)

这里有一个BitmapAnd 节点通过按位And操作连接了两个位图

位图扫描能够是我们避免重复访问同一个数据页。但是如果数据页中的数据的物理排序方式和索引记录完全相同呢？当然，我们不能依赖页面中数据的物理顺序。如果需要排序数据，我们必须在查询的时候明确指定ORDER BY子句。

但是，实际上“几乎所有的”数据都被排序的情况也是很有可能出现的：例如，如果行按照被需要的顺序添加并且不再改变。在这种情况下，构建一个位图就是多余的，一个常规的索引扫描就可以了（除非我们考虑加入多个索引的可能性）。

如果物理排序和索引记录的排序完全相同，即索引扫描时候返回的TID是有序的，比如依次返回(1,1)、(1,2)、(2,1)等等，这样，索引引擎基本上也是对每个Page只需要读取一次。

所以当选择一个访问方法时，计划器会查找一个特殊的统计，这个统计显示了物理行排序和逻辑排序的相关性。

1
select attname, correlation from pg_stats where tablename = 't';
1
2
3
4
5
6
 attname |  correlation  
---------+---------------
 c       |     0.9455042
 a       | -0.0051418496
 b       |     0.6685754
(3 rows)

上表就是通过analyze命令得出的。接近1表示高度相关，接近0表示无序分布。如果相关度比较高的话，相同的查询条件下，计划器可能就会选择使用索引扫描。

这里补充一个例子

1
2
3
4
5
6
7
8
9
create table t2(a integer, b text, c boolean);

insert into t2(a, b, c)
	select s.id, chr((32 + random() * 94)::integer), random() < 0.01
	from generate_series(1, 100000) as s(id)
	order by id;
create index on t2(a);

analyze t2;

和t表不同的是，这里插入的顺序是按照id的顺序插入的。

查看相关性

1
select attname, correlation from pg_stats where tablename = 't2';
1
2
3
4
5
6
 attname | correlation  
---------+--------------
 a       |            1
 b       | 0.0038782952
 c       |   0.98249215
(3 rows)

可以看到物理行排序和逻辑排序的相关性是1，就是完全相关的。此时再来执行下面的查询语句

1
explain (costs off) select * from t2 where a <= 100
1
2
3
4
5
           QUERY PLAN            
---------------------------------
 Index Scan using t2_a_idx on t2
   Index Cond: (a <= 100)
(2 rows)

可以看到，优化器使用了索引扫描，而不是位图扫描。

顺序扫描

我们应该注意到在非选择性条件（条件的选择性低）下，优化器更喜欢使用全表扫描。如下面的例子

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

这是因为条件的选择性越高，即匹配的行数少，索引就越有效。检索行数多，会增加读取索引页的成本。

顺序扫描比随机扫描更快。这尤其适用于机械硬盘，将磁头转到磁道上的机械操作要比读取数据本身花费的时间多得多。对于SSD，这种差异就比较小了。用“seq_page_cost”和“random_page_cost”这两个参数可以调整相应的设置。这两个参数既可以全局设置，也可以在表空间中设置，这样就可以适应不同的硬盘了。

用下面命令可以查看当前两个参数的值

1
2
3
show seq_page_cost;

show random_page_cost;

查询结果分别是1和4，即顺序扫描的代价是1，随机扫描的代价是4.

如果我们用下面的命令将random_page_cost值也设置为1

1
set random_page_cost to 1;

再执行下面的例子

1
explain (costs off) select * from t where a <= 40000;
1
2
3
4
5
          QUERY PLAN           
-------------------------------
 Index Scan using t_a_idx on t
   Index Cond: (a <= 40000)
(2 rows)

可以看到，这时候使用了索引扫描而不是顺序扫描了。

覆盖索引

通常，访问方法的主要任务是返回匹配行数据的TID，以便索引引擎能够读取必要的数据。但是如果索引中已经包含了查询的所有数据呢？这样的索引叫做覆盖，在这种情况下，优化器会使用index-only扫描

1
2
vacuum t;
explain (costs off) select a from t where a < 100;
1
2
3
4
5
             QUERY PLAN             
------------------------------------
 Index Only Scan using t_a_idx on t
   Index Cond: (a < 100)
(2 rows)

index-only这个名字给人的感觉是索引引擎不访问表，而是仅仅从访问方法中获取到所有的必要信息。但是事实并非如此，因此PostgreSQL中的索引不存储使我们能够判断行的可见性的信息。因此，访问方法返回的符合搜索条件的行的版本，而不管它们在当前事务中的可见性如何。

个人理解有两种情况会出现不可见的情况，第一种是大多数关系型数据库中都有多版本并发控制，即更新、删除操作都不会马上立即删除该行的旧版本，因为此行此时可能对别的事务仍然是可见的，其中对于更新来说会增加此行的新版本。但是旧版本对于后来的事务就是可不见了。第二种，是后面事务新增的行对先前开启的未结束的事务不可见。

然而，如果索引引擎每次都需要查看表的可见性，那么这种方法就和常规的索引扫描没有任何不同了。

为了解决这个问题，对于表，PostgreSQL维护了一个可见性映射（Visibility Map，以_vm结尾的数据库文件），在这个映射中，vacuuming 标记了只包含对所有事务可见的元组(近段时间没有更新的数据)的页面，以便所有的事务不管开始时间和隔离级别都能看到这些数据。如果索引返回的标识符和这些页面相关，就可以避免可见性检查。

因此，定期执行vacuuming 可以提高覆盖索引的效率。而且，优化器会考虑无效元组的数量，如果预测可见性检查的成本很高的话，会决定不使用仅索引扫描。

我们可以使用EXPLAIN ANALYZE来查看强制访问表的次数

1
explain (analyze, costs off) select a from t where a < 100;
1
2
3
4
5
6
7
8
9
                                  QUERY PLAN                                   
-------------------------------------------------------------------------------
 Index Only Scan using t_a_idx on t (actual time=0.007..0.019 rows=99 loops=1)
   Index Cond: (a < 100)
   Heap Fetches: 0
 Planning Time: 0.114 ms
 Execution Time: 0.038 ms
(5 rows)

在这个情况下，不需要去访问表(Heap Fetches: 0)，因为刚刚进行了vacuuming。通常来说，这个数字约接近0越好。

这里我们来做一个简单实验。

先执行下面的命令

1
explain (analyze, costs off) select a from t where a < 1000;
1
2
3
4
5
6
7
8
                                   QUERY PLAN                                   
--------------------------------------------------------------------------------
 Index Only Scan using t_a_idx on t (actual time=0.015..0.157 rows=982 loops=1)
   Index Cond: (a < 1000)
   Heap Fetches: 0
 Planning Time: 0.146 ms
 Execution Time: 0.214 ms
(5 rows)

可以看出此时使用的使仅索引扫描，而且Heap Fetches为0

然后执行下面的更新命令，

1
update t set a = a + 1;

此条更新命令会使行版本数量增加一倍，此时再执行下面的语句

1
explain (analyze, costs off) select a from t where a < 1000;
1
2
3
4
5
6
7
8
                                   QUERY PLAN                                   
--------------------------------------------------------------------------------
 Index Only Scan using t_a_idx on t (actual time=0.007..5.224 rows=973 loops=1)
   Index Cond: (a < 1000)
   Heap Fetches: 1946
 Planning Time: 0.127 ms
 Execution Time: 5.278 ms
(5 rows)

可以看到，Heap Fetches的数量变成了1946。

由于默认情况下，autovacuum是开启状态，即数据库会自动执行vacuum，因此，不断执行同样的命令，可以看到Heap Fetches逐渐变小，直到变为0为止。

快速多次执行更新命令

1
update t set a = a + 1;

由于每次执行都会导致无效的行版本变多，如果无效的行版本变多，优化器就会放弃使用覆盖索引

1
explain (analyze, costs off) select a from t where a < 1000;
1
2
3
4
5
6
7
8
9
10
                                   QUERY PLAN                                    
---------------------------------------------------------------------------------
 Bitmap Heap Scan on t (actual time=0.379..5.690 rows=926 loops=1)
   Recheck Cond: (a < 1000)
   Heap Blocks: exact=339
   ->  Bitmap Index Scan on t_a_idx (actual time=0.272..0.273 rows=2776 loops=1)
         Index Cond: (a < 1000)
 Planning Time: 0.121 ms
 Execution Time: 5.759 ms
(7 rows)

如上，可以看出经过若干次更新以后，优化器使用了位图扫描。

NULL

NULL值在关系型数据库中表示一个不存在的或者未知的值。

但是特殊的值需要特殊的处理。一个常规的布尔表达式就开始具有了三元性；NULL值是否应该小于或者大于一个常规的值（这需要一个特殊的排序结构：NULLS FIRST或者NULLS LAST）；聚合函数是否应该考虑NULL值；计划器也需要特殊的统计。

从索引的角度来说，也不清楚是否需要对NULL值进行索引。如果NULL值没有被索引的话，索引就会更加紧凑一些。但是如果NULL值被索引的话，我们就能够针对像”索引字段 IS [NOT] NULL”这样的条件使用索引，而且也可以对没有条件的查询使用覆盖索引(因为没有条件的话，查询必须返回包括NULL值在内的所有行)。

对于每一个获取方法，开发者必须做出决定是否索引NULL值。但是作为一条规则，NULL值会被索引。

多列索引

为了支持多字段条件，可以使用多列索引。例如，我们可以在我们的表中创建一个包含两个字段的索引

1
2
3
create index on t(a,b);

analyze t;

优化器可能更倾向于使用这个联合索引而不是使用连接位图，因为此时我们不需要辅助操作(例如BitmapAnd)就可以很容易的获得TIDs。

1
explain (costs off) select * from t where a <= 100 and b = 'a';
1
2
3
4
5
           QUERY PLAN            
---------------------------------
 Index Scan using t2_a_idx on t2
   Index Cond: (a <= 100)
(2 rows)

多列索引也可以在只使用索引中从第一个字段开始的若干个字段作为条件的时候来加速查询，例如对于多列索引(a,b)，用a来做查询条件；对于多列索引(a,b,c)，用a或者a、b做查询条件。如下

由于已经在a上创建了索引，此时测试a会优先使用其单列索引。因此重新创建一个(b,a)索引，然后来测试只有b条件下的执行情况

1
2
3
4
5
create index on t(b,a);

analyze t;

explain (costs off) select * from t where b = 'abc';
1
2
3
4
5
           QUERY PLAN            
---------------------------------
 Index Scan using t_b_a_idx on t
   Index Cond: (b = 'abc'::text)
(2 rows)

一般情况下，如果条件查询中没有包含第一个字段，则索引不会生效。但是某些情况下，计划器可能会认为使用索引要比顺序扫描快。这一点在BTREE一章会具体展开。

表达式上的索引

我们已经提到了搜索条件必须看起来像“索引字段 操作符 表达式”。下面的例子，将不会使用索引，因为条件中使用的是包含字段名称的表达式，而不是字段本身。

1
explain (costs off) select * from t where lower(b) = 'a';

如果不太可能重写查询，可以在表达式上建立索引（功能索引）

1
2
3
4
5
create index on t(lower(b));

analyze t;

explain (costs off) select * from t where lower(b) = 'a';
1
2
3
4
5
6
7
                 QUERY PLAN                 
--------------------------------------------
 Bitmap Heap Scan on t
   Recheck Cond: (lower(b) = 'a'::text)
   ->  Bitmap Index Scan on t_lower_idx
         Index Cond: (lower(b) = 'a'::text)
(4 rows)

功能索引没有建立在表的字段上，而是在一个任意的表达式上。优化器将会在像“索引表达式 操作符 表达式”这种查询的时候考虑使用功能索引。如果索引的表达式计算的代价很昂贵的话，那么索引的更新也会消耗相当多的资源。

另外就是，PG为被索引的表达式收集了单独的统计信息。我们可以通过”pg_stats”通过索引名称来了解这个统计信息

1
\d t
1
2
3
4
5
6
7
8
9
10
11
                 Table "public.t"
 Column |  Type   | Collation | Nullable | Default 
--------+---------+-----------+----------+---------
 a      | integer |           |          | 
 b      | text    |           |          | 
 c      | boolean |           |          | 
Indexes:
    "t_a_idx" btree (a)
    "t_b_a_idx" btree (b, a)
    "t_b_idx" btree (b)
    "t_lower_idx" btree (lower(b))
1
select * from pg_stats where tablename = 't_lower_idx';
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 schemaname |  tablename  | attname | inherited | null_frac | avg_width | n_distinct |                                                                     
most_common_vals                                                                      |                                                                    
                                                                                                                                                           
                                                                                                                       most_common_freqs                   
                                                                                                                                                           
                                                                                                                                                           
             | histogram_bounds | correlation | most_common_elems | most_common_elem_freqs | elem_count_histogram 
------------+-------------+---------+-----------+-----------+-----------+------------+---------------------------------------------------------------------
--------------------------------------------------------------------------------------+--------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------------------------------------------------
-------------+------------------+-------------+-------------------+------------------------+----------------------
 public     | t_lower_idx | lower   | f         |         0 |         5 |         69 | {n,f,o,k,u,y,p,j,w,s,c,g,v,h,r,t,e,q,l,d,z,i,x,m,b,a,),.,>,^,%,!,@,`
,=,(,3,7,/,_,4,|,"\"",$,],+,&,-,:,2,5,"{",?,6,8,9,",",#,;,"\\",*,0,"}",[,1,<,'," ",~} | {0.022333333,0.0223,0.0219,0.0218,0.021766666,0.021633333,0.0215333
33,0.021433333,0.0214,0.021366667,0.021333333,0.0213,0.021233333,0.021133333,0.021066668,0.021033334,0.020866666,0.020866666,0.020766666,0.020733334,0.0207
,0.020566666,0.020533333,0.0205,0.0204,0.0196,0.012133333,0.012,0.011833333,0.011633334,0.011466667,0.011433333,0.0114,0.0114,0.011333333,0.0112333335,0.01
12,0.0112,0.011066667,0.011033333,0.010966667,0.010933333,0.010833333,0.010833333,0.010766666,0.010733333,0.0107,0.0107,0.0107,0.0107,0.0106,0.010566667,0.
0105,0.0105,0.010366667,0.010366667,0.010333333,0.010266666,0.010266666,0.010266666,0.0101666665,0.01,0.009666666,0.0096,0.0095,0.009466667,0.0083,0.0056,0
.0053333333} |                  | -0.37644938 |                   |                        | 
(1 row)

如果有有必要，可以像修改常规的表的字段那样，去修改直方图篮子的数量（但是请注意，列的名字取决于被索引的表达式）。

1
\d t_lower_idx
1
2
3
4
5
    Index "public.t_lower_idx"
 Column | Type | Key? | Definition 
--------+------+------+------------
 lower  | text | yes  | lower(b)
btree, for table "public.t"
1
alter index t_lower_idx alter column "lower" set statistics 69;
局部索引

有时候只需要对表的一部分进行索引。这通常于高度不均匀的分布有关：通过索引可以很容易找到一个不经常出现的值，但是如果去找一个经常在表中出现的值，计划器可能会更倾向于使用全表扫描。

1
2
3
4
5
create index on t(c);

analyze t;

explain (costs off) select * from t where c;
1
2
3
4
5
          QUERY PLAN           
-------------------------------
 Index Scan using t_c_idx on t
   Index Cond: (c = true)
(2 rows)
1
explain (costs off) select * from t where not c;
1
2
3
4
5
    QUERY PLAN     
-------------------
 Seq Scan on t
   Filter: (NOT c)
(2 rows)

因为有99%的C值为假，因此，优化器会使用全表扫描来查找C值。

索引的大小是87个页面(这个数量会根据数据库的版本等原因而不同)

1
select relpages from pg_class where relname='t_c_idx';
1
2
3
4
 relpages 
----------
       87
(1 row)

但是既然C列只有1%的值为真，因此索引中的99%的数据从来不会被使用(即c为false的情况)。这种情况下，我们可以使用局部索引：

1
2
3
create index on t(c) where c;

analyze t;

此时索引的大小被减到了2(这个数量会根据数据库的版本等原因而不同，但是比上面的值笑了很多)

1
select relpages from pg_class where relname='t_c_idx1';
1
2
3
4
 relpages 
----------
        2
(1 row)

有时候，索引的大小会显著影响到索引的性能

排序

如果访问方法以某种顺序返回了行标识符，这个可以为优化器提供额外的选项来执行查询。

我们可以扫描表然后排序数据

1
2
3
set enable_indexscan=off;

explain (costs off) select * from t order by a;
1
2
3
4
5
6
     QUERY PLAN      
---------------------
 Sort
   Sort Key: a
   ->  Seq Scan on t
(3 rows)

上面是先全表扫描了t，然后根据a来排序

但是通过索引，我们可以很容易的按照顺序来读取数据。

1
2
3
set enable_indexscan=on;

explain (costs off) select * from t order by a;
1
2
3
4
          QUERY PLAN          
-------------------------------
 Index Scan using t_a_idx on t
(1 row)

这个在我用的PostgreSQL 13.3没有复现此结果，我测试的结果仍然是全表扫描。如下图所示

仍使用全表扫描

目前所有的访问方法只有”Bree”树支持返回排序数据，这一点我们后续会讨论这个索引。

并发构建

通常构建一个索引需要对表的share锁。这个锁允许从表中读取数据，但是禁止在构建索引的时候去修改表这一个

我们可以验证这一点。下面是例子

在会话1中执行下面查询

1
2
3
BRGIN;

create index on t(a);

因为在我们的例子中，创建索引的速度很快，所以这里使用了事务。

然后在会话2中来查询锁

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

可以看到在表T上有一个共享锁。然后别忘了关闭会话1中的事务。

如果我们的表很大，而且又很频繁的进行插入、更新、删除等操作的时候，代价就会变的很大。因为修改数据的进程需要等待索引去释放锁。

这种情况下，我们可以使用并发创建一个索引

注意是并发不是并行，并发和并行是不同的意思，举个例子，一个人做a，一个人同时做b，这个叫做并发；两个人同时做a这件事情，这个叫并行。

1
create index concurrently on t(a);

这个命令将表锁定在SHARE UPDATE EXCLUSIVE 模式下，在这种模式下，允许读取和更新数据（但是禁止更新表结构、以及在此表上并发清理、分析或者建立另外一个索引）。

当然这么做有其不好的一面：

  1. 索引速度会变慢，因为其需要遍历两次表；并且需要等待修改数据的并行事务完成。

    在并发索引构建中，索引实际上是在一个事务中进入系统目录，然后在另外两个事务中进行两次表扫描。在每次表扫描之前，索引构建必须等待已修改表的现有事务终止。在第二次扫描之后，索引构建必须等待在第二次扫描之前具有快照的任何事务终止。然后最后可以将索引标记为可以使用，并且 CREATE INDEX 命令终止。然而，即便如此，索引也可能无法立即用于查询：在最坏的情况下，只要在索引构建开始之前存在事务，就不能使用它

  2. 并发构建索引时，可能会出现死锁或者违反唯一约束。然后，尽管此索引是无效的，但是页已经被建立了，。这样的索引必须被删除并且重新建立。无效的索引会在\d命令输出的结果中被标记为INVALID。下面的查询会返回这些无效索引的完整列表

    1
    2
    select indexrelid::regclass index_name, indrelid::regclass table_name
    from pg_index where not indisvalid;
    1
    2
    3
    4
     index_name | table_name
    ------------+------------
     t_a_idx    | t
    (1 row)

    这个不一定能复现。