PostgreSQL索引(1) – 简介
本文翻译自Egor Rogov的英文博客，且已征得Egor Rogov的同意。译者做了少量修改，并添加了少量内容。
审校：纪昀红，中国人民大学信息学院在读博士生。
本系列文章将介绍PostgreSQL（后文简称PG）的索引。
横看成岭侧成峰，远近高低各不同。任何事物都有多个角度，我们将从数据库使用者、应用程序开发者的角度研究PG的索引，讨论他们应该关心的问题。索引有哪些种类？为什么会有这么多不同的种类？如何使用索引才能加速查询？这个话题或许可以使用简练的文字加以概括，但我们希望开发者能够深挖一些，对索引的内部实现细节有所了解，做到知其然，且知其所以然。遇到问题可以自己分析并得出结论，避免生搬硬套前人的经验。
本系列文章不讨论如何实现新的索引类型，这需要C语言的编程知识和系统程序员的专业知识。也不讨论索引的编程接口，而是聚焦在已有索引类型的一些重要知识点。
本文将讨论PG内核中通用索引引擎和存取方法（Access Method, 下面简称AM）的责任划分，以及索引引擎的功能。下篇讨论AM的接口和其它重要的概念，比如classes、operator families。从第三篇开始将依次研究Hash、B-tree、GiST、 SP-GiST、GIN、RUM、BRIN、Bloom的索引的结构和应用场景。
1. 索引
在PG中，索引是一种主要用来加速访问的数据库对象。它们是一种辅助的结构：每个索引被删除之后，都可以根据基表中的信息进行重建。有时你可能听说即使数据库没有索引也可以工作，只是慢一些而已。但事实并非如此，因为某些一致性约束需要用索引实现。
PG 9.6内置了6种不同的索引，再加一种可以通过extension（插件）获得的索引 —— 感谢PG 9.6的重大改进。期待在不久的将来可以有新的索引类型出现。
虽然不同索引类型(也被称为Access Method)之间存在各种差异，但是它们最终都把一个key（例如，索引列的值）和表中包含这个key的那行数据相关联。每行数据用TID（tuple id）表示，TID包含基表数据文件中的块号和这行数据在块内的位置。因此，只要知道一个key或它的一些信息，我们就可以快速在表中找到我们可能需要的那些行，而无需扫描整张表。
值得注意的时，虽然索引可以加速查询，但是维护索引也需要一些代价。对表进行插入、删除，修改时，此表对应的索引也都需要被更新，并且需要在同一个事务内。对表中的非索引列进行更新，可能不需要更新索引，这个技术被称为HOT（Heap-Only Tuples）。
PG的索引实现分为通用的索引引擎和具体的AM，索引引擎处在AM的上层，AM为索引引擎服务。解耦的目的是为了实现高扩展性，为了更方便地添加新的AM。扩展需要遵循一定的规则，索引引擎实现了一个接口，它主要的用途是从AM中获取TID，并且对它们进行处理：
- 从AM层获取一个TID、或一个表示候选TID的位图
- 使用TID从基表中获取一行数据
- 检查这行数据在当前隔离级别下对当前事务是否可见
如果优化器生成了使用索引的执行计划，则索引引擎参与查询的执行。优化器在生成计划时，会先生成多种候选计划，并且对各种候选计划计算执行代价，根据候选计划的代价选出最优计划。为了生成候选计划，优化器需要了解各种AM的属性。这个AM可以按所需的顺序返回数据吗？我们需要数据有序吗？这个AM可以查找NULL值吗？这些都是优化器经常需要考虑的问题。
不仅优化器需要了解AM的属性，当创建一个索引时，系统也必须知道能否在这些列上建立这个索引，以及这个索引是否有唯一性要求等。
所以，每个AM都必须提供关于它的一些属性信息。在PG 9.6之前，使用pg_am系统表保存这些信息，PG 9.6以后，这些信息下移到更深的层次（硬编码在PG内核代码中），需要使用专门的函数查询这些信息。我们将在下一篇进一步研究这些接口。
AM的其它作用：
- 实现索引的创建算法，并且将索引数据按页存放（为了让缓存区管理器统一处理每个索引）。
- 使用”indexed-field operator expression”形式的谓词条件在索引中进行查询
- 计算使用索引的代价。
- 对锁进行管理，以便支持并发处理
- 生成WAL日志
本文下面将研究通用索引引擎的功能，后续文章研究不同的AM。
2. 索引引擎
索引引擎可以使PG对各种AM进行统一处理，同时兼顾它们各自的特点。
2.1 常用扫描方法
2.1.1 索引扫描
考虑下面的例子：
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;
我们创建了一个包含a、b、c三列的表。其中，a列的值从1到100000，并且在a列上创建了一个索引（暂时不关心索引的类型）；b列的值是一些随机的可打印字符；c列的值中1%为true，其余为false。这些行以随机的顺序插入到表中（注意order by random()子句）。
使用a=1为条件查询此表。可以发现，这个条件符合这个形式：indexed-field operator expression。其中operater是“=”，expression（search key）是1。大多数情况下，符合这个形式的条件才能被索引使用。
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)
在这个例子中，优化器决定使用索引扫描。使用索引扫描时，AM一次只返回一个TID，直到最后一行符合条件的数据。索引引擎依次使用这些TID获取表中的行数据，检查这行数据是否对本事务可见。如果可见则向上层返回它所获取的数据，否则继续调用AM获取下一个TID。
2.1.2 位图扫描
当满足条件的数据行数很少时，使用索引扫描十分高效。但当满足条件的行数增加时，可能需要在多次访问同一个页面，并且在多个页面之间来回跳跃，而不是一次性将某个基表页面上满足条件的数据行全部读取出来，导致查询性能非最优。此时，优化器转而会使用位图扫描。
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)
AM首先查询到所有满足条件的TID(Bitmap Index Scan node)，并且利用这些TID构建位图。使用这个位图读取表中的行数据(Bitmap Heap Scan)，表中的每个页面最多只需要读取一次。
在第二个步骤中，索引条件可能需要重新检查 (Recheck Cond)。这由下面两个原因导致：
- 如果位图中的每一位只对应一行数据，可能导致位图无法在内存中容纳 (受限于work_mem参数)。在这种情况下，位图会自动（无法根据查询计划判断）被有损压缩，位图中的每一位会对应一个基表的数据页面。这种有损的位图占用的内存更少，但是当读取一个基表的数据页面时，我们需要重新检查页面中的每一行是否满足条件。本例中，实际执行时，使用的是精确位图（每位对应一行），Recheck Cond仍然显示在计划中，虽然执行时并不会真正的重新检查。
- 某些AM只能猜测出某行数据可能满足条件，但是不能确定结论。这种情况下，索引引擎执行时一定会重新检查。本例不属于这种情况。
如果条件涉及多个列，并且在这些列上都有索引，位图扫描可以同时使用这些索引（如果优化器认为这样更加高效）。对每个索引，生成一个位图，然后对这些位图做AND或OR的运算。
create index on t(b);
analyze t;
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)
上面的例子中BitmapAnd节点对两个位图按位做了AND操作。
位图扫描可以避免来回跳页的问题。但是如果数据在表中存放的物理顺序与索引记录的存放顺序相同呢？此时索引扫描是不是也可以避免来回跳页的问题？毫无疑问，我们不能完全依赖数据在页面中的物理顺序。如果数据需要排序，我们必须在sql语句中显式指定order by子句。但是，数据在物理存放顺序上几乎有序的场景确实存在。比如，数据按所需的顺序插入，并且插入之后没有被修改，或执行过cluster命令。在这些场景中，构造一个位图是多余的步骤，常规的索引扫描就已经很好。因此，当优化器选择AM时，会查询一个专门的统计信息项，它表示某列中数据行的物理顺序和逻辑顺序的相关性。
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，表示相关性越小，数据的存放顺序越混乱。
2.1.3 顺序扫描
当选择率很高（满足条件的行很多）时，优化器放弃索引扫描，转而去使用顺序扫描的决策是正确的。
explain (costs off) select * from t where a <= 40000;
QUERY PLAN
------------------------
Seq Scan on t
Filter: (a <= 40000)
(2 rows)
原因是：选择率越低，越适合使用索引扫描。随着满足条件行数的增加，扫描索引页面的代价越来越大。
顺序扫描比随机扫描更快，这使得代价估算变得更加复杂。对磁盘来说，更是这样，磁头的寻道时间远远高于读取数据的时间。这种现象在SSD上不明显。PG内核计算扫描代价时，会考虑两个参数，seq_page_cost和random_page_cost，这两个参数不但可以全局设置，还可以在表空间级别设置，这样可以适应不同的存储介质。
2.1.4 参数化路径
上面的例子都是单表的查询。当两张表join时，如果某个表在连接条件上有索引，则有可能生成参数化的路径。它的表现形式是：join的类型为Nestloop，内表使用索引，并且索引上有索引条件（而不是过滤条件）。如下所示。
create table t1(a int, b int);
create table t2(a int, b int);
create index on t2(a);
set enable_mergejoin=off;
set enable_hashjoin=off;
set enable_seqscan=off;
explain (costs off) select * from t1 join t2 on t1.a = t2.a;
QUERY PLAN
---------------------------------------
Nested Loop
-> Seq Scan on t1
-> Index Scan using t2_a_idx on t2
Index Cond: (a = t1.a)
(4 rows)
这种Join的主要执行流程是：
- Nestloop join算子依次读取t1中的每行数据
- Nestloop join算子把t1中每行数据的t1.a（此时t1.a是一个确定的值，可以当作const）通过参数传递给内表Index Scan算子
- Index Scan算子使用t2.a=const作为条件完成索引扫描
2.2 Covering Indexes
Covering indexes，有的资料翻译为覆盖索引。按规定，AM的主要任务给索引引擎返回符合条件行的TID，由索引引擎根据TID去表中读取这些行的数据。当索引中已经包含了查询所需的所有数据时，会怎样呢？这种索引被称作Covering，在这种情况下，优化器可以选择Index Only Scan：
vacuum t;
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)
这个名字具有一定迷惑性，它可能让人感觉AM可以提供所有的数据，索引引擎不再需要去访问基表。但事实并不完全是这样，因为PG中的索引没有保存用来判断可见性的信息。因此，AM直接给索引引擎返回一个满足条件的行数据，而不关心它是否对本事务可见。
然而，如果索引引擎每次判断行的可见性都需要访问基表的话，那么Index Only Scan和Index Scan就别无二致。
为了解决这个问题，PG维护了一个Visibility Map，Vacuum给符合下面要求的页面做一个标记。这些页面中的数据已经很久没有被更新过，因此这些数据对所有的事务都可见，无论事务何时开始，无论隔离级别是什么。如果AM返回的TID指向这些页面，则无需再判断可见性。
因此，适时的Vacuum可以提高Covering Index的性能。优化器也会考虑Dead Tuple的数量，当可见性判断开销太大时，会放弃Index Only Scan。
我们可以使用EXPLAIN ANALYZE看出因为判断可见性而被迫访问基表的次数：
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)
在这个例子中，没有去访问表 (Heap Fetches: 0)，因为刚刚做过Vacuum。通常来说，访问次数越少越好。
并非所有的索引都存储索引列的值和TID。如果AM不能返回精确的列值，则不能用作Index Only Scan，比如Hash索引。它将列值计算出一个Hash值存放在索引中，Hash的过程不可逆，因此无法获取原始的列值。
PG 11 增加了一个新特性：INCLUDE-indexes。如果一个唯一索引缺少一些列，使得它不能成为一些查询的Covering Index，应该怎么办？你不能简单的把这些列加到这个索引中，因为这会破坏索引的唯一性（允许在加列之前的索引上有重复值）。这个特性允许增加一些Non-Key列，这些列不会影响索引的唯一性，不能用作索引的搜索条件，但是可以在Index Only Scan中被使用。
2.3 NULL
NULL值在关系型数据库中扮演着重要的角色，因为它提供了一种表示不存在或未知值的方式。
但是这个特殊值需要被特殊处理。常规的布尔代数变成了三元（真、假、NULL）；我们不知道NULL比正常值大还是小（对排序来说，这需要特殊的考虑，NULLS FIRST和NULLS LAST）；聚集函数是否需要考虑NULL值也并不明显；优化器需要为NULL值保存特殊的统计信息，等等……
从索引支持的角度考虑，也不清楚是否应该索引这些NULL值。如果不索引NULL值，索引会比较紧凑。如果索引NULL值，我们就可以使用索引回答“indexed-field IS [NOT] NULL”这种查询，而且可以在不指定任何条件时被当做Covering Index（这种情况下，索引必须返回表中所有的数据，包括NULLs）。
对每种AM，开发者可以自行决策是否索引NULL。大多数AM中，NULL值会被索引。
2.4 多列索引
为了支持使用包含多个列的条件，可以使用多列索引。例如，我们可以使用表中的两个列建立一个索引：
create index on t(a,b);
analyze t;
优化器更可能倾向于使用这个索引，而不是使用两个位图，因为在这一个索引中就可以得到所需的TID，无需其它操作。
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)
如果一个条件中仅仅使用了一个多列索引中的部分列，并且使用了从第一个索引列开始的某些列，这个多列索引也可以被查询使用。
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索引时展开这个话题。
不是所有的AM都支持多列索引。
2.5 表达式索引
我们提到过，搜索条件必须要符合indexed-field operator expression的形式。在下面的例子中，索引不能被使用，因为它使用了一个包含索引列的表达式，而不是直接使用列名本身。
explain (costs off) select * from t where lower(b) = 'a';
QUERY PLAN
------------------------------------------
Seq Scan on t
Filter: (lower((b)::text) = 'a'::text)
(2 rows)
对这个语句来说，很容易将它改写成符合使用索引条件的语句。但是当某些查询不能被改写时，表达式索引（函数索引）就可以被派上用场。
create index on t(lower(b));
analyze t;
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)
函数索引不是建立表的某列上，而是建立在任意表达式上。优化器会对符合indexed-expression operator expression形式的条件尝试使用这种索引。如果这个表达式的计算非常耗费资源，更新索引时就需要消耗相当可观的资源。
请注意，表达式索引的统计信息会被单独的收集。我们可以使用索引的名字从pg_stats视图中查询：
\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))
select * from pg_stats where tablename = 't_lower_idx';
如果有必要，也可以改变直方图中bucket的数量，就像操作普通数据类型一样（注意列名可能因索引表达式的不同而不同）：
\d t_lower_idx
Index "public.t_lower_idx"
Column | Type | Definition
--------+------+------------
lower | text | lower(b)
btree, for table "public.t"
alter index t_lower_idx alter column "lower" set statistics 69;
PG 11可以使用一种更加清晰的方式控制索引的统计信息，语法为ALTER INDEX … SET STATISTICS。
2.6 部分索引
有时我们仅仅需要对表中部分数据建立索引。这在数据分布严重不均的情况下比较有用：使用索引查找出现频率较低的值，使用全表扫描查找出现频率较高的值。
我们可以在c列上建立一个索引：
create index on t(c);
analyze t;
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)
explain (costs off) select * from t where not c;
QUERY PLAN
-------------------
Seq Scan on t
Filter: (NOT c)
(2 rows)
索引占用了276个页面
select relpages from pg_class where relname='t_c_idx';
relpages
----------
276
(1 row)
但是因为c列只有1%的行为true，99%的索引并没有被使用。这种情况下，我们可以建立一个部分索引：
create index on t(c) where c;
analyze t;
索引占用的页面数减少到5个。
select relpages from pg_class where relname='t_c_idx1';
relpages
----------
5
(1 row)
有时候，空间占用和性能可能都很重要。
2.7 排序
如果一个AM可以按照某种顺序返回TID，就可以为优化器提供更多的选择来优化这个查询。
我们可以先扫描全表，然后排序：
set enable_indexscan=off;
explain (costs off) select * from t order by a;
QUERY PLAN
---------------------
Sort
Sort Key: a
-> Seq Scan on t
(3 rows)
我们也可以使用已经按需排序的索引直接读取数据：
set enable_indexscan=on;
explain (costs off) select * from t order by a;
QUERY PLAN
-------------------------------
Index Scan using t_a_idx on t
(1 row)
在所有的AM中，只有Btree索引可以返回有序的数据，所以我们将在介绍Btree索引时对此问题进行更详细的介绍。
2.8 并行创建
通常情况下，建立索引需要对表加Share锁。这个锁允许其它事务从表中读取数据，但是在索引创建期间禁止其它事务向表中插入数据。
我们可以在给表t建立索引期间，在另一个session进行下面的查询：
select mode, granted from pg_locks where relation = 't'::regclass;
mode | granted
-----------+---------
ShareLock | t
(1 row)
如果这个表特别大，并且需要经常进行增删改，事务长时间持有Share锁会变得不可接受，因为写事务必须长时间等待，直到Share锁被释放。
这种场景下，我们可以使用并行创建索引的功能：
create index concurrently on t(a);
这个命令对表加SHARE UPDATE EXCLUSIV锁，它允许表被读取和更新（仅仅禁止改变表定义、Vacuum、Analyze和同时在这个表上“并行创建”其它索引。请参考PG的4号锁）。
然而，这也有不利的一面。首先，这个索引会创建的比较慢。因为这个过程需要：
- 两次全表扫描，而不是一遍
- 等待索引创建期间的写事务结束。
其次，并行创建执行期间，可能会发生死锁，或者违反一致性约束。然而，索引还是会被创建出来，虽然这样的索引不能用。这种索引必须被手工删除或重建。在psql的\d命令的输出中，这些不能用的索引会被标记为INVALID，下面的sql语句可以查询到这种索引的完整列表：
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)