翻译：尚凯
审核：魏波
目录
1 介绍
2 索引
3 索引引擎
4 主要扫描技术
4.1 索引扫描
4.2 位图扫描
4.3 顺序扫描
4.4 仅索引扫描
介绍
本文主要关注PostgreSQL中的索引。
任何主题都可以从不同的角度考虑。我们将讨论应用程序开发人员使用DBMS感兴趣的点：可用的索引类型，为什么有这么多不同类型的索引，以及如何使用它们来加快查询。
这个主题也许可以用更少的篇幅来描述，但是我们希望作为一个好奇的开发人员，也可以对内部细节感兴趣，特别是了解这些细节不仅可以让您遵从他人的判断，还可以得出自己的结论。
新类型索引的开发超出了讨论范围。这需要了解C语言编程，并且属于系统程序员而不是应用程序开发人员的专业知识。出于同样的原因，我们不讨论编程接口，只关注使用索引相关的内容。
接下来，我们将讨论与DBMS核心相关的通用索引引擎和各个索引访问方法之间的职责分配，PostgreSQL允许我们将这些方法添加为扩展。在下一篇文章中，我们将讨论访问方法的接口和关键概念，如类和运算符。之后，将考虑不同类型索引的结构和应用的细节：Hash，B-tree，GiST，SP-GiST，GIN和RUM，BRIN和Bloom。
索引
在PostgreSQL中，索引是一种特殊的数据库对象，主要用于加速数据访问。索引是辅助结构：可以从表中的信息中删除和重新创建每个索引。索引还可用于强制执行某些完整性约束。
目前，PostgreSQL 9.6内置了六种不同类型的索引，并且由于版本9.6的重大更改，还提供了一个索引作为扩展。因此，预计不久的将来会出现新的索引类型。
尽管索引类型（也称为访问方法）之间存在差异，但它们最终都将一个键(例如，索引列的值)与包含该键的表的行关联起来。每一行由TID（元组id）标识，它由文件中的块数和块内行的位置组成。也就是说，使用已知键或有关它的一些信息，我们可以快速读取那些可能包含我们感兴趣的信息的行，而无需扫描整个表。
重要的是要理解索引以一定的维护成本加速数据访问。对于索引数据上的每个操作，无论是表行的插入，删除还是更新，都需要在同一个事务中更新该表的索引。请注意，更新尚未构建索引的表字段不会导致索引更新; 这种技术叫做HOT（Heap-Only Tuples）。
可扩展性带来一些影响。为了方便向系统添加新的访问方法，实现了通用索引引擎接口。它的主要任务是从访问方法中获取TID并使用它们：
• 从相应版本的表行中读取数据。
• 通过TID获取行版本TID，或使用预构建的位图批量获取行版本。
• 检查当前事务的行版本的可见性，同时考虑其隔离级别。
索引引擎参与执行查询。它是根据优化阶段创建的计划调用的。优化器对执行查询的不同方法进行排序和评估，应该了解所有可能适用的访问方法功能。该方法是否能够按所需的顺序返回数据，或者我们是否应该预期排序？我们可以使用此方法搜索NULL吗？这些是优化器经常要解决的问题。
不仅优化器需要有关访问方法的信息。在构建索引时，系统必须决定是否可以在多个列上构建索引，以及此索引是否确保唯一性。
因此，每种访问方法都应提供有关自身的所有必要信息。低于9.6的版本使用了pg_am表，而从版本9.6开始，数据移动到更深层的特殊函数中。我们将进一步了解这个接口。
剩下的就是访问方法的任务：
• 实现用于构建索引的算法，并将数据映射到页面中（以便缓冲区缓存管理器统一处理每个索引）。
• 通过“索引字段操作符表达式”形式的谓词在索引中搜索信息。
• 评估索引使用成本。
• 操纵正确并行处理所需的锁。
• 生成预写日志（WAL）记录。
我们将首先考虑通用索引引擎的功能，然后再考虑不同的访问方法。
索引引擎
索引引擎使PostgreSQL能够统一地处理各种访问方法，但要考虑它们的特性。
主要扫描技术
1.索引扫描
我们可以用不同的方法处理由索引提供的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.01from 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来选择一个值。请注意，条件看起来像“ 索引字段操作符表达式 ”，其中操作符为“相等”，表达式（搜索键）为“1”。在大多数情况下，要使用的索引，条件必须如此。
postgres=# explain (costs off) select * from t where a = 1;QUERY PLAN-------------------------------Index Scan using t_a_idx on tIndex Cond: (a = 1)(2 rows)
在这种情况下，优化器决定使用索引扫描。通过索引扫描，访问方法逐个返回TID值，直到达到最后一个匹配的行。索引引擎依次访问由TID指示的表行，获取行版本，检查其对多版本并发规则的可见性，并返回获得的数据。
2.位图扫描
当我们只处理几个值时，索引扫描工作正常。但是，随着检索到的行数增加，很有可能多次返回同一个表页。因此，优化器切换到位图扫描。
postgres=# explain (costs off) select * from t where a <= 100;QUERY PLAN------------------------------------Bitmap Heap Scan on tRecheck Cond: (a <= 100)-> Bitmap Index Scan on t_a_idxIndex Cond: (a <= 100)(4 rows)
访问方法首先返回所有与条件匹配的TID（位图索引扫描节点），并从这些TID构建行版本的位图。然后从表中读取行版本（位图堆扫描），每个页面只读取一次。
请注意，在第二步中，可能会重新检查条件（Recheck Cond）。对于行版本的位图来说，检索的行数可能太大，无法完全匹配RAM(受work_mem参数的限制)。在这种情况下，仅为包含至少一个匹配行版本的页面构建位图。
这个“有损”位图需要的空间更少，但在阅读页面时，我们需要重新检查其中包含的每一行的条件。请注意，即使对于少量检索到的行并因此“精确”位图（例如在我们的示例中），«RecheckCond»步骤仍然在计划中表示，尽管实际上并未执行。
如果对多个表字段施加条件并对这些字段建立索引，位图扫描允许同时使用多个索引（如果优化程序认为这样有效）。对于每个索引，构建行版本的位图，然后执行按位布尔乘法（如果表达式由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 tRecheck Cond: ((a <= 100) AND (b = 'a'::text))-> BitmapAnd-> Bitmap Index Scan on t_a_idxIndex Cond: (a <= 100)-> Bitmap Index Scan on t_b_idxIndex Cond: (b = 'a'::text)(7 rows)
这里BitmapAnd节点通过按位与操作连接两个位图。
位图扫描使我们能够避免重复访问相同的数据页。但是如果表页面中数据的物理排序方式与索引记录完全相同怎么办？毫无疑问，我们不能完全依赖页面中数据的物理顺序。如果需要排序数据，我们必须在查询中显式指定ORDER BY子句。但实际情况可能是“几乎所有”数据都被排序的情况：例如，如果按所需顺序添加行，并且在此之后或执行CLUSTER命令之后不进行更改。在这种情况下，构建位图是一个过度的步骤，常规索引扫描也同样好（除非我们考虑连接多个索引的可能性）。因此，在选择访问方法时，计划器会查看一个特殊的统计数据，该统计数据显示了物理行排序和列值逻辑排序之间的相关性:
postgres=# select attname, correlation from pg_stats where tablename = 't';attname | correlation---------+-------------b | 0.533512c | 0.942365a | -0.00768816(3 rows)
接近1的绝对值表示高相关性（对于列c），而接近于0的值则相反，表示混沌分布（列a）。
3.顺序扫描
在非选择性条件下，优化器将优先选择整个表的顺序扫描而不是使用索引：
postgres=# explain (costs off) select * from t where a <= 40000;QUERY PLAN------------------------Seq Scan on tFilter: (a <= 40000)(2 rows)
问题是条件选择性越高，索引就越好，也就是说，匹配它的行越少。检索行数的增长增加了读取索引页的开销成本。
顺序扫描比随机扫描更快，这使情况更加复杂。这特别适用于硬盘，在硬盘上，将磁头带到轨道的机械操作比读取数据本身花费更多的时间。SSD的效果不太明显。有两个参数可用于考虑访问成本的差异，seq_page_cost和random_page_cost，我们不仅可以在全局设置，还可以在表空间级别设置，这种方法可以调整不同磁盘子系统的特性。
4.仅索引扫描
通常，访问方法的主要任务是返回匹配表行的标识符，以便索引引擎从这些行读取必要的数据。但是，如果索引已包含查询所需的所有数据呢？这样的索引称为覆盖，在这种情况下，优化器可以应用仅索引扫描：
postgres=# vacuum t;postgres=# explain (costs off) select a from t where a < 100;QUERY PLAN------------------------------------Index Only Scan using t_a_idx on tIndex Cond: (a < 100)(2 rows)
此名称可能让人觉得索引引擎根本不访问该表，而是仅从访问方法获取所有必要信息。但事实并非如此，因为PostgreSQL中的索引并不存储使我们能够判断行可见性的信息。因此，访问方法返回与搜索条件匹配的行版本，而不考虑它们在当前事务中的可见性。
但是，如果索引引擎每次都需要查看表以获得可见性，那么这种扫描方法与常规索引扫描没有什么不同。
为解决这个问题，PostgreSQL为表维护了一个所谓的可见性映射，在这个映射中，不管起始时间和隔离级别如何，标记清理的页面中，如果数据更改的时间不够长，数据可被所有事务看到。如果索引返回的行的标识符与这样的页面相关，则可以避免可见性检查。
因此，定期vacuum可以提高覆盖指数的效率。此外，优化器会考虑死元组的数量，如果预测可见性检查的开销很高，则可以决定不使用仅索引扫描。
我们可以使用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: 0Planning time: 0.092 msExecution time: 0.059 ms(5 rows)
在这种情况下，不需要访问表（Heap Fetches：0），因为刚刚进行了vacuum操作。一般来说，这个数字越接近零越好。
并非所有索引都与行标识符一起存储索引值。如果访问方法无法返回数据，则不能将其用于仅索引扫描。
下期预告：
上文介绍了索引、索引类型及主要的扫描技术，后续将继续介绍与索引相关的内容，主要包括空值与索引、索引类型示例、索引与排序、并行创建。
原文请点击下方“阅读原文”获取，建议PC端阅读更佳！
