引言

本系列文章主要涉及PostgreSQL中的索引。

可以从不同角度考虑任何主题。我们将讨论使用DBMS的应用程序开发人员应该感兴趣的事项：可用的索引，为什么索引类型如此之多以及如何使用它们来加快查询速度。可以用较少的词来涵盖该主题，但是我们希望保密的是一位好奇的开发人员，他也对内部细节感兴趣，特别是因为对这些细节的理解不仅可以让您听从他人的判断，而且可以得出结论。你自己的。

新型索引的开发超出了范围。这需要了解C编程语言，并且属于系统程序员而非应用程序开发人员的专业知识。出于同样的原因，我们几乎不会讨论编程接口，而只会关注于使用即用型索引的重要事项。

在本文中，我们将讨论与DBMS核心相关的常规索引引擎和各个索引访问方法之间的职责分配，PostgreSQL使我们可以将其添加为扩展。在下一篇文章中，我们将讨论访问方法的接口以及诸如类和运算符系列之类的关键概念。经过漫长但必要的介绍之后，我们将考虑不同类型的索引的结构和应用的详细信息：哈希， B树， GiST ， SP-GiST ， GIN和RUM ， BRIN和Bloom 。

在开始之前，我要感谢Elena Indrupskaya将文章翻译成英文。
自原始出版物发布以来，情况有所变化。我对当前情况的评论是这样表示的。

指标

在PostgreSQL中，索引是特殊的数据库对象，主要用于加速数据访问。它们是辅助结构：可以删除每个索引，然后从表中的信息重新创建它们。有时您可能会听到，尽管缓慢，但是DBMS可以在没有索引的情况下运行。但是，事实并非如此，因为索引还用于强制执行某些完整性约束。

目前，PostgreSQL 9.6内置了六种不同类型的索引，并且由于版本9.6的重大更改，还有一个索引可以作为扩展使用。因此，在不久的将来可以期待新型的索引。

尽管索引类型（也称为访问方法）之间存在所有差异，但它们最终都会将一个键（例如，索引列的值）与包含该键的表行相关联。每行由TID（元组ID）标识，TID由文件中的块数和该行在块内的位置组成。也就是说，使用已知键或有关它的某些信息，我们可以快速读取可能包含我们感兴趣的信息的那些行，而无需扫描整个表。

重要的是要了解索引以一定的维护成本加快了数据访问速度。对于索引数据的每个操作，无论是插入，删除还是更新表行，也需要在同一事务中更新该表的索引。请注意，未建立索引的表字段的更新不会导致索引更新。这项技术称为HOT（仅堆元组）。

可扩展性带来一些影响。为了能够轻松地向系统添加新的访问方法，已经实现了通用索引引擎的接口。它的主要任务是从访问方法中获取TID并使用它们：

从表行的相应版本中读取数据。
使用预建位图按TID或批量获取行版本的TID。
考虑到其隔离级别，请检查当前事务的行版本的可见性。

索引引擎参与执行查询。根据在优化阶段创建的计划来调用它。优化器整理并评估执行查询的不同方式，应了解所有可能适用的访问方法的功能。该方法将能够按所需顺序返回数据，还是应该预期排序？我们可以使用这种方法搜索NULL吗？这些是优化器定期解决的问题。

不仅优化程序需要有关访问方法的信息。建立索引时，系统必须决定是否可以在多个列上建立索引以及该索引是否确保唯一性。

因此，每种访问方法都应提供有关其自身的所有必要信息。低于9.6的版本为此使用了“ pg_am”表，而从9.6版开始，则将数据移至更深层次的特殊功能内。我们将进一步熟悉该界面。

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

实现用于构建索引并将数据映射到页面的算法（以使缓冲区高速缓存管理器统一处理每个索引）。
通过谓词以“ 索引字段运算符表达式 ”形式在索引中搜索信息。
评估索引使用成本。
操作正确的并行处理所需的锁。
生成预写日志（WAL）记录。

我们将首先考虑通用索引引擎的功能，然后再考虑不同的访问方法。

索引引擎

索引引擎使PostgreSQL可以统一使用各种访问方法，但要考虑到它们的功能。

主要扫描技术

索引扫描

我们可以使用索引提供的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到100.000的数字，并且在此字段上创建索引（无论什么类型）。第二个字段包含各种ASCII字符，但不可打印的字符除外。最后，第三个字段包含一个逻辑值，该逻辑值对于大约1％的行为true，对于其余行为false。行以随机顺序插入表中。

让我们尝试通过条件“ a = 1”选择一个值。请注意，条件看起来像“ 索引字段运算符表达式 ”，其中运算符为“等于”， 表达式 （搜索关键字）为“ 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指示的表行，获取行版本，针对多版本并发规则检查其可见性，并返回获得的数据。

位图扫描

当我们只处理几个值时，索引扫描就可以正常工作。但是，随着检索到的行数的增加，它更有可能多次返回同一表页面。因此，优化器将切换到位图扫描 。

 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（位图索引扫描节点），然后根据这些TID构建行版本的位图。然后从表中读取行版本（位图堆扫描），每页仅读取一次。

请注意，在第二步中，可以重新检查条件（重新检查条件）。检索到的行数可能太大，以致行版本的位图无法完全适合RAM（受“ work_mem”参数限制）。在这种情况下，仅针对包含至少一个匹配行版本的页面构建位图。该“有损”位图需要较少的空间，但是在读取页面时，我们需要重新检查其中包含的每一行的条件。请注意，即使对于少量的检索行并因此是“精确的”位图（例如在我们的示例中），无论如何，“ Recheck Cond”步骤仍在计划中表示，尽管实际上并未执行。

如果对几个表字段施加了条件并为这些字段建立了索引，则位图扫描将允许同时使用多个索引（如果优化程序认为这有效）。对于每个索引，将构建行版本的位图，然后针对这些位图执行按位布尔乘法（如果表达式通过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)

在这里，BitmapAnd节点通过按位“和”运算将两个位图连接在一起。

位图扫描使我们能够避免重复访问同一数据页。但是，如果表页中的数据在物理上与索引记录的排序方式完全相同，该怎么办？毫无疑问，我们不能完全依靠页面中数据的物理顺序。如果需要排序的数据，我们必须在查询中明确指定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”）。

顺序扫描

为了完整显示图片，我们应该注意，在非选择条件下，优化器将更倾向于使用对整个表的顺序扫描而不是使用索引：

 postgres=# explain (costs off) select * from t where a <= 40000;

  QUERY PLAN ------------------------ Seq Scan on t Filter: (a <= 40000) (2 rows)

问题是条件选择性越高，索引工作越好，即与之匹配的行越少。检索到的行数的增加会增加读取索引页的开销。

顺序扫描比随机扫描更快，使情况更加复杂。这尤其适用于硬盘，在硬盘中，将磁头带到磁道上的机械操作比读取数据本身要花费更多的时间。对于SSD，这种影响不太明显。可以使用两个参数来考虑访问成本的差异：“ seq_page_cost”和“ random_page_cost”，我们不仅可以全局设置，而且可以在表空间级别设置这种方式，以适应不同磁盘子系统的特性。

覆盖指标

通常，访问方法的主要任务是返回匹配表行的标识符，以供索引引擎从这些行中读取必需的数据。但是，如果索引已经包含查询所需的所有数据怎么办？这样的索引称为Covering ，在这种情况下，优化器可以应用仅索引扫描 ：

 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)

该名称可能使人想到索引引擎根本不会访问表，而仅从访问方法获取所有必需的信息。但这并非完全如此，因为PostgreSQL中的索引不存储使我们能够判断行可见性的信息。因此，访问方法将返回与搜索条件匹配的行的版本，而不管它们在当前事务中是否可见。

但是，如果索引引擎每次都需要查看表中的可见性，则此扫描方法与常规索引扫描没有什么不同。

为了解决该问题，PostgreSQL对表维护了一个所谓的可见性图 ，其中清理功能标记页面的数据更改时间不足以使该数据对于所有事务可见，而不论启动时间和隔离级别如何。如果索引返回的行的标识符与此页面相关，则可以避免可见性检查。

因此，定期抽真空可提高覆盖指数的效率。此外，优化器考虑了死元组的数量，并且如果它预测可见性检查的开销成本很高，则可以决定不使用仅索引扫描。

我们可以使用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)

在这种情况下，不需要访问表（堆访存：0），因为吸尘刚刚完成。通常，此数字越接近零越好。

并非所有索引都将索引值与行标识符一起存储。如果访问方法无法返回数据，则不能将其用于仅索引扫描。

PostgreSQL 11引入了一个新功能：INCLUDE-indexes。如果有一个唯一索引缺少某些列以用作某些查询的覆盖索引，该怎么办？您不能简单地将列添加到索引，因为它将破坏其唯一性。该功能允许包括非关键列，这些列不会影响唯一性，并且不能在搜索谓词中使用，但仍可以提供仅索引扫描。该补丁是由我的同事Anastasia Lubennikova开发的。

空值

NULL作为表示不存在或未知值的便捷方法，在关系数据库中起着重要的作用。

但是要处理一个特殊的值。正则布尔代数变为三元；尚不清楚NULL是否应小于或大于常规值（这需要特殊的排序结构，即NULLS FIRST和NULLS LAST）；尚不清楚聚合函数是否应考虑NULL；计划者需要特殊的统计信息...

从索引支持的角度来看，还不清楚我们是否需要对这些值进行索引。如果未索引NULL，则索引可能会更紧凑。但是，如果为NULL编制了索引，我们将能够将索引用于诸如“ indexed-field IS [NOT] NULL”之类的条件，并且当根本不为该表指定任何条件时，也可以将其用作覆盖索引（因为在这种情况下，索引必须返回所有表行的数据，包括具有NULL的表行）。

对于每种访问方法，开发人员都会单独决定是否对NULL编制索引。但通常，它们确实会被索引。

几个领域的索引

为了支持多个字段的条件，可以使用多列索引 。例如，我们可以在表的两个字段上建立索引：

 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)

功能索引不是建立在表字段上，而是建立在任意表达式上。优化程序将针对“ indexed-expression运算符表达式 ”之类的条件考虑该索引。如果要索引的表达式的计算是一项昂贵的操作，则索引的更新也将需要大量的计算资源。

还请记住，已为索引表达式收集了单个统计信息。我们可以通过索引名称在“ pg_stats”视图中了解此统计信息：

 postgres=# \dt

  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';

如有必要，可以用与常规数据字段相同的方式控制直方图篮的数量（请注意，列名可能因索引表达式而异）：

 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 STATISTICS命令中指定列号，引入了一种更干净的方法来控制索引的统计目标。该补丁是由我的同事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)

所有访问方法中只有“ btree”可以返回排序后的数据，因此让我们开始更详细的讨论，直到考虑这种类型的索引。

并发建筑

通常，建立索引需要为表获取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模式，该模式允许读取和更新（仅禁止更改表结构，并且禁止同时清理，分析或在该表上建立另一个索引）。

但是，也有另一面。首先，索引的建立将比平时慢，这是因为跨表执行了两次而不是一次，并且还必须等待修改数据的并行事务完成。

其次，在同时建立索引的情况下，可能会发生死锁或违反唯一约束。但是，将建立索引，尽管该索引无法运行。必须删除并重建这样的索引。非操作索引在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)

继续阅读。

PostgreSQL中的索引-1

引言

指标