PostgreSQL Internals之路 Part-IV 第19章 索引访问方法

微信群：数据库Hacker,  已超200人，现在无法通过扫描直接加入。需要入群的朋友，请直接微信联系我(个人微信：_iihero)，标上您的全名_数据库Hacker作为备注即可。

19.1 索引及其扩展性

索引是数据库对象，主要服务于加速数据访问的目的。这些都是辅助结构：可以根据堆数据删除和重新创建任何索引。除了数据访问加速之外，索引还用于强制执行一些完整性约束。

PostgreSQL 的内核提供了六种内置的索引访问方法（索引类型）：

=> SELECT amname FROM pg_am WHERE amtype = 'i';
amname
−−−−−−−−
btree
hash
gist
gin
spgist
brin
(6 rows)

Postgre 的可扩展性意味着可以在不修改核心的情况下添加新的访问方法。一个这样的扩展（bloom 方法）包含在标准模块集中。

尽管各种索引类型之间存在差异，但它们最终都将键（例如索引列的值）与包含该键的堆元组进行匹配。元组由 6 字节元组 ID 或 TID 引用。知道键或键的一些信息，可以快速读取可能包含所需数据的元组，而无需扫描整个表。

为了确保一个新的访问方法可以作为扩展添加，PostgreSQL 实现了一个通用的索引引擎。它的主要目标是检索和处理由特定访问方法返回的数据：

• 从相应的堆元组中读取数据

• 根据特定快照检查元组可见性

• 重新检查条件，如果他们的评估方法是不确定的

索引引擎还参与在优化阶段建立的计划的执行。在评估各种执行路径时，优化器需要知道所有可能适用的访问方法的属性：该方法是否按照所需的顺序返回数据，或者我们是否需要单独的排序阶段？是否有可能立即返回几个第一个值，或者我们必须等待整个结果集被获取？等等......。

不仅仅是优化器需要知道访问方法的细节。索引创建提出了更多需要回答的问题：访问方法是否支持多列索引？这个索引能保证唯一性吗？

索引引擎允许使用多种访问方法；为了被支持，访问方法必须实现一个特定的接口来声明它的特性和属性。

访问方法用于描述下边这些任务：

• 实现创建索引的算法，也就是插入和删除索引项的算法
• 将索引项分散到各个页（进一步被缓冲缓存管理器处理）
• 实现 VACUUM 算法
• 获得锁，进而确保正确的处理并发操作
• 产生 WAL 记录
• 通过键来搜索索引数据
• 估计索引扫描成本

可扩展性还表现为添加新数据类型的能力，而访问方法事先对此一无所知。因此，访问方法必须定义自己的接口，以便插入任意数据类型。

为了在特定的访问方法中使用新的数据类型，您必须实现相应的接口------也就是说，提供可以与索引一起使用的操作符，以及可能的一些辅助支持函数。这样一组操作符和函数称为操作符类。

索引逻辑部分由访问方法本身实现，但其中一部分外包给操作符类。这种分布相当随意：虽然 B-树将所有逻辑连接到访问方法中，但其他一些方法可能只提供主框架，将所有实现细节留给特定的操作符类。同一种数据类型通常由多个操作符类支持，用户可以选择具有行为最合适的那个操作符。

以下是整体概要情况图的一小部分：

19.2 操作符种类及其家族

19.2.1 操作符种类

访问方法接口^[1]由操作符类^[2]实现，操作符类是由访问方法应用于特定数据类型的一组操作符和支持函数。

操作符的类存储在系统编目中的 pg_opclass 表中。下面的查询返回上述示例的完整数据：

=> SELECT amname, opcname, opcintype::regtype
	FROM pg_am am
	JOIN pg_opclass opc ON opcmethod = am.oid;
 amname |           opcname            |          opcintype
--------+------------------------------+-----------------------------
 btree  | array_ops                    | anyarray
 hash   | array_ops                    | anyarray
 btree  | bit_ops                      | bit
 btree  | bool_ops                     | boolean
 btree  | bpchar_ops                   | character
 hash   | bpchar_ops                   | character
 btree  | bytea_ops                    | bytea
 btree  | char_ops                     | "char"
 hash   | char_ops                     | "char"
 btree  | cidr_ops                     | inet
 hash   | cidr_ops                     | inet
 btree  | date_ops                     | date
 hash   | date_ops                     | date
 btree  | float4_ops                   | real
 hash   | float4_ops                   | real
 btree  | float8_ops                   | double precision
 hash   | float8_ops                   | double precision
 btree  | inet_ops                     | inet
 hash   | inet_ops                     | inet
 gist   | inet_ops                     | inet
 spgist | inet_ops                     | inet
 btree  | int2_ops                     | smallint
 hash   | int2_ops                     | smallint
 btree  | int4_ops                     | integer
 hash   | int4_ops                     | integer
 btree  | int8_ops                     | bigint
 hash   | int8_ops                     | bigint
 btree  | interval_ops                 | interval
 hash   | interval_ops                 | interval
...............
(177 rows)

在大多数情况下，我们不需要了解操作符类。我们只需创建一个默认使用某种操作符类的索引。

例如，以下是支持文本类型的 B-tree 操作符类。其中一个类总是被标记为默认类：

=> SELECT opcname, opcdefault
	FROM pg_am am
	JOIN pg_opclass opc ON opcmethod = am.oid
	WHERE amname = 'btree'
		AND opcintype = 'text'::regtype;

       opcname       | opcdefault
---------------------+------------
 text_ops            | t
 varchar_ops         | f
 text_pattern_ops    | f
 varchar_pattern_ops | f
(4 rows)

一个创建索引的典型的命令看起来如下：

CREATE INDEX ON aircrafts(model, range);

但它只是一个速记符号，扩展为以下语法：

CREATE INDEX ON aircrafts
USING btree -- the default access method
(
	model text_ops, -- the default operator class for text
	range int4_ops
				-- the default operator class for integer
);

如果希望使用不同类型的索引或实现某些自定义行为，则必须显式指定所需的访问方法或操作符类。

为特定访问方法和数据类型定义的每个操作符类必须包含一组操作符，这些操作符接受此类型的参数并实现此访问方法的语义。

例如，b 树访问方法定义了五个强制比较操作符。任何 b 树操作符类必须包含所有这五个：

=> SELECT opcname, amopstrategy, amopopr::regoperator
FROM pg_am am
JOIN pg_opfamily opf ON opfmethod = am.oid
JOIN pg_opclass opc ON opcfamily = opf.oid
JOIN pg_amop amop ON amopfamily = opcfamily
WHERE amname = 'btree'
AND opcname IN ('text_ops', 'text_pattern_ops')
AND amoplefttype = 'text'::regtype
AND amoprighttype = 'text'::regtype
ORDER BY opcname, amopstrategy;

     opcname      | amopstrategy |     amopopr
------------------+--------------+-----------------
 text_ops         |            1 | <(text,text)
 text_ops         |            2 | <=(text,text)
 text_ops         |            3 | =(text,text)
 text_ops         |            4 | >=(text,text)
 text_ops         |            5 | >(text,text)
 text_pattern_ops |            1 | ~<~(text,text)
 text_pattern_ops |            2 | ~<=~(text,text)
 text_pattern_ops |            3 | =(text,text)
 text_pattern_ops |            4 | ~>=~(text,text)
 text_pattern_ops |            5 | ~>~(text,text)
(10 rows)

访问方法所隐含的操作符的语义由策略数反映，表示为amopstrategy^[3]. 例如，b 树的策略 1 表示小于，2 表示小于或等于，等等。操作符本身可以有任意名称。

上面的例子展示了两种操作符。常规操作符和带有波浪的操作符之间的区别在于后者不考虑collation^[4](排序)并执行字符串的按位比较。然而，这两种风格都实现了相同的比较逻辑操作。

text_pattern_ops 操作符类设计用于解决在支持~~操作符（对应于 LIKE 操作符）方面的限制。在使用除 C 以外的任何排序规则的数据库中，此操作符不能在文本字段上使用常规索引：

=> SHOW lc_collate;
lc_collate
−−−−−−−−−−−−−
en_US.UTF−8
(1 row)
=> CREATE INDEX ON tickets(passenger_name);
=> EXPLAIN (costs off)
SELECT * FROM tickets WHERE passenger_name LIKE 'ELENA%';
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Seq Scan on tickets
Filter: (passenger_name ~~ 'ELENA%'::text)
(2 rows)

而使用 text_pattern_ops 操作符的索引的行为就不相同：

=> CREATE INDEX tickets_passenger_name_pattern_idx
ON tickets(passenger_name text_pattern_ops);
=> EXPLAIN (costs off)
SELECT * FROM tickets WHERE passenger_name LIKE 'ELENA%';
		QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Bitmap Heap Scan on tickets
	Filter: (passenger_name ~~ 'ELENA%'::text)
		−> Bitmap Index Scan on tickets_passenger_name_pattern_idx
		Index Cond: ((passenger_name ~>=~ 'ELENA'::text) AND
		(passenger_name ~<~ 'ELENB'::text))
(5 rows)

注意在索引条件下过滤器表达式是如何变化的。搜索现在只使用模板%之前的前缀，而在基于过滤器条件的重新检查期间过滤掉错误的命中。b 树访问方法的操作符类不提供用于比较模板的操作符，在这里应用 B-tree 的唯一方法是使用比较操作符重写此条件。text_pattern_ops 类的操作符不考虑排序，这就给了我们使用等效条件的机会^[5]。

如果满足以下两个先决条件，索引可以通过过滤器条件来加快访问速度：

1. 条件被写成“索引列运算符表达式”（如果运算符指定了一个可交换的对应物^[6]，条件也可以写成“表达式运算符索引列^[7]”）

2. 操作符属于索引声明中为索引列指定的操作符类。

例如，下面的查询可以使用索引：

=> EXPLAIN (costs off)
SELECT * FROM tickets WHERE 'ELENA BELOVA' = passenger_name;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Index Scan using tickets_passenger_name_idx on tickets
	Index Cond: (passenger_name = 'ELENA BELOVA'::text)
(2 rows)

在我本人的实验中，得到的是下边的结果：

                          QUERY PLAN
---------------------------------------------------------------
 Bitmap Heap Scan on tickets
   Recheck Cond: ('ELENA BELOVA'::text = passenger_name)
   ->  Bitmap Index Scan on tickets_passenger_name_pattern_idx
         Index Cond: (passenger_name = 'ELENA BELOVA'::text)
(4 rows)

注意 Index Cond 条件中参数的位置：在执行阶段，索引字段必须在左侧。当参数进行排列时，运算符将被交换运算符替换；在这种特殊情况下，它是相同的算子，因为相等关系是可交换的。

在下一个查询中，技术上不可能使用常规索引，因为条件中的列名被函数调用取代：

=> EXPLAIN (costs off)
SELECT * FROM tickets WHERE initcap(passenger_name) = 'Elena Belova';
                            QUERY PLAN
------------------------------------------------------------------
 Gather
   Workers Planned: 2
   ->  Parallel Seq Scan on tickets
         Filter: (initcap(passenger_name) = 'Elena Belova'::text)
(4 rows)

在这里，你可以使用表达式索引，使用表达式来代替具体列的访问：

=> CREATE INDEX ON tickets( (initcap(passenger_name)) );
=> EXPLAIN (costs off)
SELECT * FROM tickets WHERE initcap(passenger_name) = 'Elena Belova';
                              QUERY PLAN
----------------------------------------------------------------------
 Bitmap Heap Scan on tickets
   Recheck Cond: (initcap(passenger_name) = 'Elena Belova'::text)
   ->  Bitmap Index Scan on tickets_initcap_idx
         Index Cond: (initcap(passenger_name) = 'Elena Belova'::text)
(4 rows)

索引表达式只能依赖于堆元组值，并且必须不受数据库中存储的其他数据或配置参数（例如区域设置）的影响。换句话说，如果表达式包含任何函数调用，则这些函数必须为IMMUTABLE^[8]，并且它们必须遵守此易变类别。否则，对于同一个查询，索引扫描和堆扫描可能返回不同的结果。

除常规操作符外，操作符类还可以提供访问方法所需的支持函数^[9]。例如，btree 访问方法定义了五个支持函数，第一个（比较两个值）是必须的，而其他的都可以不用存在：

=> SELECT amprocnum, amproc::regproc
FROM pg_am am
JOIN pg_opfamily opf ON opfmethod = am.oid
JOIN pg_opclass opc ON opcfamily = opf.oid
JOIN pg_amproc amproc ON amprocfamily = opcfamily
WHERE amname = 'btree'
AND opcname = 'text_ops'
AND amproclefttype = 'text'::regtype
AND amprocrighttype = 'text'::regtype
ORDER BY amprocnum;

 amprocnum |       amproc
-----------+--------------------
         1 | bttextcmp
         2 | bttextsortsupport
         4 | btvarstrequalimage
(3 rows)

19.2.2 操作符类族

每个操作符类总是属于某个操作符族^[10]（列在 pg_opfamily 表的系统编目中）。一个类族可以包含几个以相同方式处理类似数据类型的类。

例如，integer_ops 家族包括几个用于整型数据类型的类，它们具有相同的语义，但大小不同：

=> SELECT opcname, opcintype::regtype
FROM pg_am am
JOIN pg_opfamily opf ON opfmethod = am.oid
JOIN pg_opclass opc ON opcfamily = opf.oid
WHERE amname = 'btree'
AND opfname = 'integer_ops';

 opcname  | opcintype
----------+-----------
 int2_ops | smallint
 int4_ops | integer
 int8_ops | bigint
(3 rows)

datetime_ops 家族包含处理日期的操作符类：

=> SELECT opcname, opcintype::regtype
FROM pg_am am
JOIN pg_opfamily opf ON opfmethod = am.oid
JOIN pg_opclass opc ON opcfamily = opf.oid
WHERE amname = 'btree'
AND opfname = 'datetime_ops';

     opcname     |          opcintype
-----------------+-----------------------------
 date_ops        | date
 timestamptz_ops | timestamp with time zone
 timestamp_ops   | timestamp without time zone
(3 rows)

虽然每个操作符类支持单一数据类型，但一个族可以包含用于不同数据类型的操作符类：

=> SELECT opcname, amopopr::regoperator
FROM pg_am am
JOIN pg_opfamily opf ON opfmethod = am.oid
JOIN pg_opclass opc ON opcfamily = opf.oid
JOIN pg_amop amop ON amopfamily = opcfamily
WHERE amname = 'btree'
AND opfname = 'integer_ops'
AND amoplefttype = 'integer'::regtype
AND amopstrategy = 1
ORDER BY opcname;

 opcname  |       amopopr
----------+---------------------
 int2_ops | <(integer,bigint)
 int2_ops | <(integer,smallint)
 int2_ops | <(integer,integer)
 int4_ops | <(integer,bigint)
 int4_ops | <(integer,smallint)
 int4_ops | <(integer,integer)
 int8_ops | <(integer,bigint)
 int8_ops | <(integer,smallint)
 int8_ops | <(integer,integer)
(9 rows)

由于将各种操作符分组到一个家族中，当索引用于涉及不同类型值的条件时，规划器可以不进行类型转换。

19.3 索引引擎接口

就像表访问方法一样，pg_am 表的 amhandler 列包含实现接口的函数的名称：

=> SELECT amname, amhandler FROM pg_am WHERE amtype = 'i';
 amname |  amhandler
--------+-------------
 btree  | bthandler
 hash   | hashhandler
 gist   | gisthandler
 gin    | ginhandler
 spgist | spghandler
 brin   | brinhandler
(6 rows)

这个函数用实际值填充接口结构^[11]中的占位符。其中一些函数负责与索引访问相关的单独任务（例如，它们可以执行索引扫描并返回堆元组），而其他函数则是索引引擎必须知道的索引方法属性。

所有属性分为三类：

• •访问方法属性
• •特定索引的属性
• •索引的列级属性

访问方法和索引级属性之间的区别是为将来提供的：现在，基于特定访问方法的所有索引在这两个级别上始终具有相同的属性。

19.3.1 访问方法属性

以下五个属性（PG11+)在访问方法级别定义（此处为 b-tree 方法所示）：

=> SELECT a.amname, p.name, pg_indexam_has_property(a.oid, p.name)
FROM pg_am a, unnest(array[
'can_order', 'can_unique', 'can_multi_col',
'can_exclude', 'can_include'
]) p(name)
WHERE a.amname = 'btree';

 amname |     name      | pg_indexam_has_property
--------+---------------+-------------------------
 btree  | can_order     | t
 btree  | can_unique    | t
 btree  | can_multi_col | t
 btree  | can_exclude   | t
 btree  | can_include   | t
(5 rows)

Can Order 接收已排序数据的能力。这个属性只在 B 树中支持。要得到所需排序的结果 ，你总要扫描表，并对获取的数据进行排序：

=> EXPLAIN (costs off)
SELECT * FROM seats ORDER BY seat_no;
       QUERY PLAN
-------------------------
 Sort
   Sort Key: seat_no
   ->  Seq Scan on seats
(3 rows)

但是如果有一个支持这个属性的索引，那么数据可以立即按照期望的顺序返回：

=> EXPLAIN (costs off)
SELECT * FROM seats ORDER BY aircraft_code;

              QUERY PLAN
--------------------------------------
 Index Scan using seats_pkey on seats
(1 row)

Can UniqUE支持唯一和主键约束。该属性只适用于 B 树。

每当唯一或主键约束定义完时，PostgreSQL 会自动创建唯一索引以支持此限制 。

=> INSERT INTO bookings(book_ref, book_date, total_amount)
VALUES ('000004', now(), 100.00);
ERROR:
duplicate key value violates unique constraint
"bookings_pkey"
DETAIL:
Key (book_ref)=(000004) already exists.

也就是说，如果仅仅创建一个惟一索引而不显式声明完整性约束，效果似乎是完全相同的：索引列将不允许重复。那么区别是什么呢？