QuantumRealm

基本的 relation-level统计信息存储在系统目录的 pg_class 表中，包含以下数据：

• relation中的元组（记录）数量（reltuples）
• relation的大小，以页（page）为单位（relpages）
• 在可见性映射（visibility map）中被标记的页数（relallvisible）

下面是 flights 表对应的这些值：

1
2
3
4
5
6

=> SELECT reltuples, relpages, relallvisible
FROM pg_class WHERE relname = 'flights';
 reltuples | relpages | relallvisible 
−−−−−−−−−−−+−−−−−−−−−−+−−−−−−−−−−−−−−−
    214867 |     2624 |          2624 
(1 row)

如果查询未施加任何过滤条件，则 reltuples 的值将作为基数（cardinality）估计：

1
2
3
4
5

=> EXPLAIN SELECT * FROM flights;
							QUERY PLAN 
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− 
Seq Scan on flights (cost=0.00..4772.67 rows=214867 width=63)
(1 row)

统计信息是在表分析（无论是手动还是自动）过程中收集的。此外，由于基本统计信息至关重要，这些数据也会在其他操作中计算（如 VACUUM FULL 和 CLUSTER，以及 CREATE INDEX 和 REINDEX），并在常规 VACUUM 过程中进一步精化。

为了分析目的，会从表中随机抽取 300 × default_statistics_target 行进行采样。为了构建具有特定精度的统计信息，所需的样本量与被分析数据的总体量关系不大，因此表的大小不会被考虑在内。

抽样行是从同样数量的随机页（300 × default_statistics_target 页）中选出的。显然，如果表本身较小，则可能读取的页数更少，选取用于分析的行数也会相应减少。

对于大表，统计信息收集不会包含所有行，因此估算值可能与实际值存在偏差。这是完全正常的：如果数据在不断变化，统计信息本身也不可能始终准确。通常，只要估算精度在数量级上足够，即可用来选择合理的查询执行计划。

我们创建一个 flights 表的副本，并禁用 autovacuum，这样我们就可以控制自动分析（autoanalysis）的启动时间：

1

=> CREATE TABLE flights_copy(LIKE flights) WITH (autovacuum_enabled = false);

目前新表没有统计信息

1
2
3
4
5

=> SELECT reltuples, relpages, relallvisible FROM pg_class WHERE relname = 'flights_copy';
 reltuples | relpages | relallvisible
−−−−−−−−−−−+−−−−−−−−−−+−−−−−−−−−−−−−−−
        −1 |        0 |             0 
(1 row)

当 reltuples = −1 时，用于区分尚未分析的表和真正没有行的空表。

表创建后，很可能会马上插入一些行。由于优化器无法获知表的当前实际状态，它会假设该表包含 10 个页：

1
2
3
4
5

=> EXPLAIN SELECT * FROM flights_copy;
							QUERY PLAN 
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Seq Scan on flights_copy (cost=0.00..14.10 rows=410 width=170) 
(1 row)

行数的估算是基于单行的大小（在执行计划中显示为 width）。行宽通常是在分析过程中计算的平均值，但由于此时尚未收集任何统计信息，这里只是根据列的数据类型做出的近似估算。

现在，我们从 flights 表拷贝数据同时完成分析：

1
2

=> INSERT INTO flights_copy SELECT * FROM flights; INSERT 0 214867
=> ANALYZE flights_copy;

收集到的统计信息反映了实际的行数（表足够小，分析器可以对所有数据收集统计信息）：

1
2
3
4
5

=> SELECT reltuples, relpages, relallvisible FROM pg_class WHERE relname = 'flights_copy';
 reltuples | relpages | relallvisible 
−−−−−−−−−−−+−−−−−−−−−−+−−−−−−−−−−−−−−−
    214867 |     2624 |             0 
(1 row)

relallvisible 值用于估算 index-only scan 的成本。该值由 VACUUM 更新：

1
2
3
4
5
6

=> VACUUM flights_copy;
=> SELECT relallvisible FROM pg_class WHERE relname = 'flights_copy';
relallvisible 
−−−−−−−−−−−−−−−
          2624 
(1 row)

现在我们将行数翻倍，但不更新统计信息，检查查询计划中的基数估算：

1
2
3
4
5
6
7
8
9
10
11
12

=> INSERT INTO flights_copy SELECT * FROM flights; 
=> SELECT count(*) FROM flights_copy;
 count 
−−−−−−−−
429734 
(1 row)

=> EXPLAIN SELECT * FROM flights_copy;
							QUERY PLAN 
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Seq Scan on flights_copy (cost=0.00..9545.34 rows=429734 width=63) 
(1 row)

尽管 pg_class 中的数据已经过时，估算结果仍然准确：

1
2
3
4
5
6

=> SELECT reltuples, relpages
FROM pg_class WHERE relname = 'flights_copy';
 reltuples | relpages 
−−−−−−−−−−−+−−−−−−−−−−
    214867 |    2624 
(1 row)

问题在于，如果优化器发现 relpages 与实际文件大小之间存在差距，它可以通过比例调整 reltuples 的值来提高估算精度。由于文件大小相比 relpages 翻了一倍，优化器会调整估算的行数，同时假设数据密度保持不变：

1
2
3
4
5
6
7

=> SELECT reltuples *
(pg_relation_size('flights_copy') / 8192) / relpages AS tuples
FROM pg_class WHERE relname = 'flights_copy';
 tuples
−−−−−−−−
 429734
(1 row)

当然，这种调整并不总是有效（例如，如果删除了一些行，估算值将保持不变），但在某些情况下，它可以让优化器在下一次分析触发之前仍然保持合理的估算。

当使用简单查询协议时，每个命令（即使重复多次）都必须经历上述所有阶段：

1. parsing
2. transformation
3. planning
4. execution

但是，一次又一次地解析相同的查询是没有意义的。重复解析仅在常量上不同的查询也没有多大意义——解析树结构仍然保持不变。

简单查询协议的另一个缺点是客户端会立即收到整个结果，无论它可能包含多少行。

一般来说，使用 SQL 命令可以克服这些限制。要处理第一种情况，您可以在运行 EXECUTE 命令之前PREPARE查询；第二个问题可以通过使用 DECLARE 创建游标并通过 FETCH 返回行来解决。但在这种情况下，这些新创建的对象的命名必须由客户端处理，而服务器则需要解析额外命令的额外开销

扩展的客户端—服务器协议提供了一种替代方案，使得可以在协议本身的命令级别上，对各个算子执行阶段进行精确控制。

Preparation

在准备阶段，查询会像往常一样被解析并进行转换，但生成的解析树会保存在后端的内存中。

PostgreSQL 并不存在全局的查询缓存。这种架构的缺点是显而易见的：即使同一条查询已经被其他后端进程解析过，每个后端仍然必须重新解析其接收到的所有查询。但与此同时，这种设计也带来了一些好处。全局缓存由于需要加锁，很容易成为系统瓶颈。一个客户端如果频繁执行大量相似但不完全相同的小查询（例如仅常量不同的查询），会产生大量缓存访问流量，从而对整个实例的性能造成负面影响。在 PostgreSQL 中，查询是在各个后端本地解析的，因此不会对其他进程产生影响。

一条预处理（prepared）的查询可以带参数化。下面是一个使用 SQL 命令的简单示例（尽管这与协议层的预处理不完全相同，但最终效果是一样的）

1
2

=> PREPARE plane(text) AS
SELECT * FROM aircrafts WHERE aircraft_code = $1;

所有命名的预处理语句都显示在 pg_prepared_statements 视图中：

1
2
3
4
5
6
7

=> SELECT name, statement, parameter_types
FROM pg_prepared_statements \gx
−[ RECORD 1 ]−−−+−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− 
name            | plane
statement       | PREPARE plane(text) AS +
                | SELECT * FROM aircrafts WHERE aircraft_code = $1; 
parameter_types | {text}

这里不会显示任何未命名语句（即使用扩展查询协议或 PL/pgSQL 的语句）。其他后端准备的语句也不会显示：因为无法访问其他会话的内存。

Parameter Binding

在预处理语句被执行之前，必须先绑定实际的参数值。

1
2
3
4
5

=> EXECUTE plane('733');
aircraft_code | model | range 
−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−+−−−−−−− 
733            | Boeing 737−300 | 4200
(1 row)

在预处理语句中绑定参数，相比将字面量直接拼接到查询字符串中，其优势在于可以彻底杜绝 SQL 注入：绑定的参数值无法以任何方式修改已经构建完成的解析树。若不使用预处理语句而想达到同等的安全级别，就必须对来自不可信来源的每一个值进行非常谨慎的转义处理。

Planning and Execution

在执行预处理语句时，查询规划会基于实际的参数值来进行；随后生成的执行计划会交由执行器处理。

由于不同的参数值可能对应不同的最优执行计划，因此在规划阶段准确考虑具体参数值是非常重要的。举例来说，在查询价格较高的预订记录时，规划器会假定符合条件的行数不多，从而选择使用索引扫描。

1
2
3
4
5
6
7
8
9
10
11

=> CREATE INDEX ON bookings(total_amount);
=> EXPLAIN SELECT *
FROM bookings
WHERE total_amount > 1000000;
								QUERY PLAN 
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Bitmap Heap Scan on bookings (cost=86.49..9245.82 rows=4395 wid... 
	Recheck Cond: (total_amount > '1000000'::numeric)
	−> Bitmap Index Scan on bookings_total_amount_idx (cost=0.00....
Index Cond: (total_amount > '1000000'::numeric) 
(4 rows)

但如果给定的条件对所有预订记录都成立，那么使用索引就没有意义了，因为最终仍然需要扫描整张表。

1
2
3
4
5
6
7

=> EXPLAIN SELECT *
FROM bookings
WHERE total_amount > 100;
							QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Seq Scan on bookings (cost=0.00..39835.88 rows=2111110 width=21) Filter: (total_amount > '100'::numeric)
(2 rows)

在某些情况下，规划器可能会同时保留解析树和查询计划，以避免重复进行规划。由于这种计划不会考虑具体的参数值，因此被称为通用计划（generic plan），以区别于基于实际参数值生成的定制计划（custom plan）。

参数化预处理语句的前五次执行，优化过程始终依赖于实际的参数值；规划器会基于这些参数值计算定制计划（custom plan）的平均成本。从第六次执行开始，如果通用计划（generic plan）在平均意义上比定制计划更高效（同时考虑到每次都需要重新生成定制计划的额外开销），规划器就会保留通用计划并继续使用它，从而跳过后续的优化阶段。

一个显而易见的场景是：当查询不包含任何参数时，数据库可以使用通用计划而不会对性能造成影响

1
2
3
4
5
6
7

 => EXECUTE plane('763');
=> EXECUTE plane('773');
=> EXPLAIN EXECUTE plane('319');
							QUERY PLAN 
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− 
Seq Scan on aircrafts_data ml (cost=0.00..1.39 rows=1 width=52)
Filter: ((aircraft_code)::text = '319'::text) (2 rows)

在第五次执行之后，规划器会切换为通用计划（generic plan）：该计划与之前的定制计划并无差别，成本也相同，但后端只需构建一次即可，并且可以跳过优化阶段，从而降低规划开销。此时，EXPLAIN 命令显示参数是通过位置来引用的，而不再显示其具体取值。

1
2
3
4
5
6

 => EXECUTE plane('320');
=> EXPLAIN EXECUTE plane('321');
							QUERY PLAN 
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− 
Seq Scan on aircrafts_data ml (cost=0.00..1.39 rows=1 width=52)
Filter: ((aircraft_code)::text = $1) (2 rows)

“优化阶段”特指每次执行时基于参数值重新生成执行计划的那一部分工作。

我们可以很容易想象这样一种不利情况：前几次生成的 custom plan 比 generic plan 更昂贵；随后可能出现的更高效的 custom plan 却完全不会被考虑。此外，规划器比较的是估算成本而非实际执行成本，这也可能导致误判。

不过，如果规划器的自动决策出现偏差，你可以通过设置 plan_cache_mode 参数来覆盖自动选择，从而强制使用 generic plan 或 custom plan

1
2
3
4
5
6

=> SET plan_cache_mode = 'force_custom_plan';
=> EXPLAIN EXECUTE plane('CN1');
							QUERY PLAN 
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− 
Seq Scan on aircrafts_data ml (cost=0.00..1.39 rows=1 width=52)
Filter: ((aircraft_code)::text = 'CN1'::text) (2 rows)

除了其他信息之外，pg_prepared_statements 视图还显示了所选计划的统计信息：

1
2
3
4
5
6

=> SELECT name, generic_plans, custom_plans
FROM pg_prepared_statements;
name   | generic_plans | custom_plans 
−−−−−−−+−−−−−−−−−−−−−−−+−−−−−−−−−−−−−− 
plane  | 1             | 6
(1 row)

Getting the Results

扩展查询协议允许按批次而不是一次性检索数据。SQL 游标（cursor）几乎具有相同效果（唯一的区别是服务器需要做一些额外处理，而且规划器只会优化前 cursor_tuple_fraction 行的获取，而不是整个结果集）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

=> BEGIN;
=> DECLARE cur CURSOR FOR SELECT *
FROM aircrafts
ORDER BY aircraft_code;
=> FETCH 3 FROM cur;
aircraft_code  | model           | range 
−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−−+−−−−−−−
319            | Airbus A319−100 | 6700
320            | Airbus A320−200 | 5700
321            | Airbus A321−200 | 5600
(3 rows)
=> FETCH 2 FROM cur;
aircraft_code  | model          | range 
−−−−−−−−−−−−−−−+−−−−−−−−−−−−−−−−+−−−−−−− 
733            | Boeing 737−300 | 4200 
763            | Boeing 767−300 | 7900
=> COMMIT;
(2 rows) 

如果查询返回大量行，且客户端需要获取所有行，那么系统吞吐量高度依赖于批量大小（batch size）。批量包含的行数越多，每次访问服务器并获取响应时产生的通信开销就越小。然而，随着批量大小继续增加，这种优势会逐渐减弱：例如，将行一条条取出与每批取 10 行的差别非常明显，但将每批取 100 行与每批取 1000 行相比，性能提升就不那么显著了

参考书目

1. Egor Rogov, PostgreSQL 14 Internals, https://postgrespro.com/community/books/internals

1. Demo Database

前面章节中的示例都是基于只有几行数据的简单表。本章以及后面的章节要处理查询执行，在这方面对数据要求更高：我们需要行数多得多、彼此有关联的表。为了不在每个示例中都重新发明一个新的数据集，我选用了一个现成的演示数据库，它展示了俄罗斯的客运航空交通情况。这个数据库有多个版本；我们将使用 2017 年 8 月 15 日创建的较大版本。要安装这个版本，你需要从压缩包中解压出包含数据库副本的文件，然后在 psql 中运行这个文件。

在开发这个演示数据库时，我们尝试让它的模式（schema）足够简单，以便无需额外说明就能理解；同时，我们也希望它足够复杂，能够用来编写有意义的查询。数据库填充了贴近真实场景的数据，这使得示例更加全面，也更有趣味性。

这里我只会简要介绍主要的数据库对象；如果你想查看整个模式(schema)，可以参阅脚注中引用的完整描述。

主要的实体(entity)是 预订（booking），它对应于 bookings 表。一个预订可以包含多个乘客，每个乘客都有单独的电子机票（对应 tickets 表）。乘客本身不构成独立的实体；在我们的实验中，我们假设所有乘客都是唯一的

每张机票包含一个或多个航段（对应 ticket_flights 表）。一张机票之所以可能有多个航段，主要有两种情况：要么它是往返票，要么它包含联程航班。虽然数据库模式中没有相应的约束，但我们假设同一个预订（booking）中的所有机票都拥有相同的航段。

每个航班（flights 表）都从一个机场（airports 表）飞往另一个机场。具有相同航班号的航班拥有相同的出发地和目的地，但起飞日期不同。

routes 视图基于 flights 表构建；它展示的是与具体航班日期无关的航线信息。

在值机时，每位乘客都会被发放一张带有座位号的登机牌（boarding_passes 表）。乘客只能为机票中包含的航班办理值机。航班 + 座位 的组合必须唯一，因此不可能为同一个座位发放两张登机牌。

飞机上的座位数量（seats 表）以及这些座位在不同舱位之间的分布，取决于执行该航班的具体机型（aircrafts 表）。我们假设每一种机型只能有一种客舱布局。

有些表使用了代理主键（surrogate primary key），而另一些表使用了自然主键（natural key）（其中有些还是复合主键）。这样设计纯粹是为了演示，绝不是推荐的实践方式。

这个演示数据库可以看作是真实系统的一份转储：其中包含了某个过去时间点的数据快照。要查看这个时间，可以调用 bookings.now() 函数。在需要使用 now() 的真实查询场景中，你可以在演示查询里使用这个函数。

机场、城市和机型的名称存储在 airports_data 和 aircrafts_data 表中，并提供了两种语言：英文和俄文。为了构建本章的示例，我通常会查询实体关系图中显示的 airports 和 aircrafts 这两个视图；这些视图会根据 bookings.lang 参数的值来选择输出语言。不过在查询计划中，有些底层表的名称仍然可能会出现。

2. Simple Query Protoco

一种简单版本的客户端–服务器协议即可实现 SQL 查询的执行：客户端将查询文本发送给服务器，而服务器则返回完整的执行结果——无论结果包含多少行。发送到服务器的查询会经过几个阶段：解析（parse）→ 转换（transform）→ 计划（plan）→ 执行（execute）。

Parsing

首先，PostgreSQL 必须对查询文本进行解析（parse），以便理解需要执行的内容。

Lexical and syntactic analysis 词法分析器（lexer）会把查询文本拆分成一组词法单元（lexemes），例如关键字、字符串字面量、数字字面量等；而语法分析器（parser）会根据 SQL 的语言语法规则对这组词法单元进行验证。PostgreSQL 使用的是标准的解析工具，即 Flex 和 Bison。

解析后的查询会以抽象语法树（AST）的形式存储在后端进程的内存中。

例如，让我们来看下面这个查询：

1
2
3
4

SELECT schemaname, tablename
FROM pg_tables
WHERE tableowner = 'postgres'
ORDER BY tablename;

词法分析器从中识别出了 5 个关键字、5 个标识符、1 个字符串字面量，以及 3 个单字符词素（一个逗号、一个等号和一个分号）。语法分析器则使用这些词素来构建解析树，下面的插图展示了一个高度简化的解析树。树中每个节点旁的文字说明表示该节点对应查询中的哪一部分：

一个比较晦涩的缩写 RTE 代表 Range Table Entry（范围表项）。PostgreSQL 的源代码中使用 range table（范围表） 这个术语来指代表、子查询、连接结果——换句话说，指代 任何可以被 SQL 运算符处理的行集（set of rows）

语义分析（Semantic analysis） 的目的在于确认数据库中是否存在该查询按名称引用的表或其他对象，并检查用户是否拥有访问这些对象的权限。语义分析所需的全部信息都存储在 系统目录（system catalog） 中。

在获得解析树之后，语义分析器会对其进行进一步的重组，这包括：为解析树添加对具体数据库对象、数据类型以及其他信息的引用。

如果你启用了参数 debug_print_parse，就可以在服务器日志中看到完整的解析树，但这通常没有太大的实际意义。

Transformation

在下一阶段，查询会被转换（重写，rewrite）。

PostgreSQL 核心在多个场景下会使用查询转换。其中之一就是：
将解析树中 视图（view） 的名称替换为该视图底层查询（base query）对应的子树。

另一个使用转换的场景是行级安全（Row-Level Security, RLS） 的实现。
另外，递归查询中的 SEARCH 和 CYCLE 子句也会在此阶段被转换。

在上面的示例中，pg_tables 是一个视图；如果我们把它的定义直接展开写进查询文本，它将会是下面这样：

1
2
3
4
5
6
7
8
9
10
11
12
13

SELECT schemaname, tablename
FROM (-- pg_tables
    SELECT n.nspname AS schemaname,
        c.relname AS tablename,
        pg_get_userbyid(c.relowner) AS tableowner,
        ...
    FROM pg_class c
        LEFT JOIN pg_namespace n ON n.oid = c.relnamespace
        LEFT JOIN pg_tablespace t ON t.oid = c.reltablespace
    WHERE c.relkind = ANY (ARRAY['r'::char, 'p'::char])
)
WHERE tableowner = 'postgres'
ORDER BY tablename；

不过，服务器并不会处理查询的文本表示；所有操作都在解析树（parse tree）上完成。下图展示的是一个简化后的重写树（如果启用 debug_print_rewritten 参数，你可以在服务器日志中看到其完整版本）。

解析树只反映了查询的语法结构，但并不包含任何关于操作执行顺序的信息。

此外，PostgreSQL 还支持自定义转换，用户可以通过 rewrite rule（重写规则）系统来实现自己的查询重写逻辑。

规则系统（rule system）的支持曾被宣称为 Postgres 开发的主要目标之一；在最初实现规则系统时，Postgres 还只是一个学术项目，但之后规则系统已经多次被重新设计。规则系统非常强大，但也相当难以理解和调试。甚至有人提议直接把规则系统从 PostgreSQL 中移除，但这一想法并未得到一致认可。在大多数情况下，使用 触发器（trigger） 会比使用规则更加安全且容易。

Planning

SQL 是一种声明式语言：查询只说明要取什么数据，而不说明如何取。

任何查询都可以有多种执行路径。解析树中的每个操作都可能有多种完成方式：
例如，结果既可以通过全表扫描（读取整张表并过滤掉不需要的数据）得到，也可以通过索引扫描来找到所需行。数据集在连接时总是两两结合（pairwise joins），这意味着连接顺序存在大量组合，从而产生数量巨大的候选执行方案。此外，还有多种连接算法（join algorithms）：例如，执行器可以扫描第一个数据集的每一行，并在第二个数据集中查找匹配行；或者，先对两个数据集进行排序，再执行合并连接（merge join）。对每一种算法，都能找到其优于其他算法的使用场景。

最优计划与非最优计划的执行时间可能相差几个数量级，因此用于对解析后的查询进行优化的 计划器（planner） 是系统中最复杂的组件之一

Plan tree 执行计划同样以树结构表示，但其节点处理的是物理数据操作，而不是逻辑操作。

如果你想查看完整的计划树，可以启用 debug_print_plan 参数，将计划树输出到服务器日志中。但在实际工作中，通常只需要查看 EXPLAIN 命令显示的文本形式的执行计划就足够了。

下图突出展示了执行计划树中的主要节点。正是这些节点会出现在下面 EXPLAIN 命令的输出中。

暂时我们先关注以下两点：

• 这棵计划树中只包含了三个被查询表中的两个：规划器发现其中一个表对获取结果并非必需，于是将其从计划树中移除了。
• 对于计划树中的每个节点，规划器都会给出估算的成本（cost）以及预计要处理的行数（rows）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

=> EXPLAIN SELECT schemaname, tablename
FROM pg_tables
WHERE tableowner = 'postgres'
ORDER BY tablename;
QUERY PLAN
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
Sort (cost=21.03..21.04 rows=1 width=128)
  Sort Key: c.relname
  −> Nested Loop Left Join (cost=0.00..21.02 rows=1 width=128)
    Join Filter: (n.oid = c.relnamespace)
    −> Seq Scan on pg_class c (cost=0.00..19.93 rows=1 width=72)
        Filter: ((relkind = ANY ('{r,p}'::"char"[])) AND (pg_g...
    −> Seq Scan on pg_namespace n (cost=0.00..1.04 rows=4 wid...
(7 rows)

查询计划中的 Seq Scan 节点表示顺序扫描表数据，
而 Nested Loop 节点则表示连接（join）操作。

Plan search PostgreSQL 使用的是基于成本（cost-based）的优化器；它会遍历可能的执行计划，并估算执行这些计划所需的资源，例如 I/O 操作或 CPU 周期。这种估算会被归一化为一个数值，称为该计划的 cost（成本）。在所有被考虑的计划中，优化器最终会选择 成本最低的那个计划。

问题在于：潜在可用的执行计划数量会随着参与连接的表数呈指数级增长，因此即使针对相对简单的查询，也不可能把所有计划都枚举一遍。通常，规划器会使用动态规划（dynamic programming）算法并结合一些启发式规则（heuristics）来缩小搜索范围。这种方法使规划器能够在可接受的时间内，为包含大量表的查询找到数学上最优的执行计划。

准确的解决方案并不能保证所选计划确实是最佳计划，因为规划器使用简化的数学模型，可能缺乏可靠的输入数据

Managing the order of joins 查询可以通过某种结构方式来限制优化器的搜索范围（当然，这样做有可能错过最优执行计划）。

• 公共表表达式（CTE） 和主查询可以被分别优化；如果你想强制这种行为，可以使用 MATERIALIZED 子句。

• 在非 SQL 函数内部运行的子查询 总是会被单独优化。（SQL 函数有时可能会被 inline 到主查询中。）

• 如果你设置了 join_collapse_limit 并在查询中使用显式的 JOIN 语法，那么部分连接顺序会被查询的语法结构所固定；类似地，from_collapse_limit 对子查询有相同的效果。

最后一点可能需要解释一下。让我们来看一个示例：在 FROM 子句中列出表，但没有写任何显式 JOIN 的查询。

1
2
3

SELECT ...
FROM a, b, c, d, e
WHERE ..

在这种情况下，规划器必须考虑所有可能的连接（join）组合。该查询会由解析树中的如下部分来表示（示意性展示）。

在下一个示例中，连接（join）的结构由 JOIN 子句 明确定义。

1
2
3

SELECT ...
FROM a, b JOIN c ON ..., d, e
WHERE ...

解析树会反映出这种结构。

规划器通常会将连接树（join tree）扁平化，使其看起来与第一个示例中的结构类似。该算法会递归遍历整棵树，并将每个 JOINEXPR 节点替换为其包含元素的扁平列表。

然而，只有当生成的扁平列表元素数量不超过 join_collapse_limit 时，这种合并操作才会执行。在这个特定的例子中，如果 join_collapse_limit 的值小于五，JOINEXPR 节点将不会被合并。

对于查询优化器而言，这意味着：

• 表 B 必须与表 C 进行连接（或者反过来，C 必须与 B 连接；在这对表中的连接顺序没有限制）。
• 表 A、D、E 以及 B 和 C 连接的结果可以按任意顺序进行连接。

如果 join_collapse_limit 参数设置为 1，则显式 JOIN 子句中定义的顺序将被保留。

关于 FULL OUTER JOIN 的操作数，它们永远不会被合并（collapsed），无论 join_collapse_limit 参数的值是多少。

from_collapse_limit 参数以类似的方式控制子查询的扁平化。虽然子查询看起来不像 JOIN 子句，但在解析树（parse tree）层面上，这种相似性就很明显了

一个例子：

1
2
3
4
5
6
7

SELECT ... 
FROM a,
(
	SELECT ... FROM b, c WHERE ...
) bc,
d, e 
WHERE ...

对应的JOIN树如下所示。这里唯一的区别是，这棵树包含的是 FROMEXPR 节点，而不是 JOINEXPR（因此参数名如此命名）。

遗传查询优化（Genetic query optimization） 在将查询树扁平化之后，某一层可能包含过多的元素——无论是表还是中间连接结果，这些元素都需要单独进行优化。由于查询计划的生成时间会随着需要连接的数据集数量呈指数增长，因此plan时间可能会超出所有合理的范围。

如果启用了 geqo 参数，并且某一层的元素数量超过 geqo_threshold 的阈值，查询规划器将使用遗传算法来优化查询。相比动态规划，遗传算法的速度要快得多，但它无法保证找到的查询计划一定是最优的。因此，一条经验法则是通过减少需要优化的元素数量来避免使用遗传算法。

遗传算法有若干可配置参数，但在此不作详细介绍。

选择最佳执行计划 查询计划是否可以被认为是最优的，取决于特定客户端如何使用查询结果。如果客户端需要一次性获取完整结果（例如，用于生成报表），那么计划应当优化所有行的检索效率。但如果优先考虑尽快返回前几行（例如，用于屏幕显示），那么最优计划可能完全不同。

为了做出这个选择，PostgreSQL 会计算成本的两个组成部分：

1
2
3
4
5
6
7
8
9
10
11
12
13

=> EXPLAIN
SELECT schemaname, tablename FROM pg_tables
WHERE tableowner = 'postgres' ORDER BY tablename;
                      QUERY PLAN
------------------------------------------------------
Sort (cost=21.03..21.04 rows=1 width=128)
    Sort Key: c.relname
    −> Nested Loop Left Join (cost=0.00..21.02 rows=1 width=128)
        Join Filter: (n.oid = c.relnamespace)
        −> Seq Scan on pg_class c (cost=0.00..19.93 rows=1 width=72)
            Filter: ((relkind = ANY ('{r,p}'::"char"[])) AND (pg_g... 
        −> Seq Scan on pg_namespace n (cost=0.00..1.04 rows=4 wid..
(7 rows)

第一个组成部分（启动成本）表示节点执行前的准备开销；第二个组成部分（总成本）则包括获取查询结果过程中产生的所有开销。

有时人们会说启动成本是获取结果集第一行的开销，但这种说法并不完全准确。

为了挑选出首选执行计划，优化器会检查查询是否使用了游标（无论是通过 SQL 中的 DECLARE 命令，还是在 PL/pgSQL 中显式声明（explicitly））。如果没有使用游标，则默认客户端需要一次性获取完整结果，优化器会选择总成本最小的计划。

如果查询是通过游标执行的，则所选计划必须优化仅获取所有行中 cursor_tuple_fraction 部分的效率。更准确地说，PostgreSQL 会选择使以下表达式值最小的计划：

1

startup cost + cursor_tuple_fraction (total cost − startup cost)

** 成本估算概述 ** 要估算一个计划的总成本，必须对计划中的所有节点进行成本估算。节点的成本取决于其类型（显而易见，读取堆表数据的成本与排序操作的成本不同）以及节点处理的数据量（数据量越大，通常成本越高）。虽然节点类型是已知的，但数据量只能根据输入集的预计基数（节点接收的行数）以及节点的选择性（输出中剩余行的比例）来预测。这些计算依赖于收集到的统计信息，例如表的大小以及表列中数据的分布情况。

如果对每个节点的基数估计准确，计算出的成本很可能能够较好地反映实际成本。规划中主要的缺陷通常源于基数和选择性的估计不准确，这可能由以下原因造成：

1. 统计信息不准确或过时；
2. 无法使用统计信息；
3. （程度较轻）规划模型本身的不完善。

基数估计（Cardinality estimation） 要计算节点的基数，优化器必须递归地完成以下步骤：

1. 估算每个子节点的基数，并评估该节点将从子节点接收到的输入行数；
2. 估算节点的选择性(Selectivity)，即输出中剩余的输入行所占的比例。

节点的基数即这两个值的乘积。

选择性(Selectivity)用一个介于 0 到 1 之间的数表示。数值越小，选择性越高；反之，数值接近 1 表示选择性较低。乍一看可能不太直观，其含义是：高选择性条件会筛掉几乎所有行，而只排除少量行的条件则选择性低。

首先，优化器会估算定义数据访问方式的叶子节点的基数。这些计算依赖于收集到的统计信息，例如表的总大小。

过滤条件的选择性取决于条件的类型。在最简单的情况下，可以将其假设为一个常数值，尽管优化器会尽量利用所有可用信息来精确估算。通常，只需要掌握如何估算简单过滤条件即可；如果条件包含逻辑运算，其选择性则按照以下公式计算：

1
2

sel𝑥 𝑎𝑛𝒅 𝑦 = sel𝑥sel𝑦
sel𝑥 𝑜𝒓 𝑦  = 1−(1−sel𝑥)(1−sel𝑦) = sel𝑥+sel𝑦−sel𝑥sel𝑦

sel_X：满足条件 X 的行比例 sel_Y：满足条件 Y 的行比例 条件 X AND Y：满足两个条件的行，概率就是两者独立事件概率的乘积; (1 - sel_X)：不满足 X 的行比例, (1 - sel_Y)：不满足 Y 的行比例, (1 - sel_X)(1 - sel_Y)：同时不满足 X 和 Y 的行比例.所以 1 − (1 − sel_X)(1 − sel_Y) = 满足 X 或 Y 的行比例

不幸的是，上述公式假设谓词 X 和 Y 彼此独立。对于相关（correlated）的谓词，这类估算将不准确。

要估算 连接（join）的基数，优化器必须首先计算笛卡尔积的基数（即两个数据集基数的乘积），然后估算连接条件的选择性，这仍然取决于条件类型。

其他节点（如排序或聚合）的基数估算方式也类似。

需要注意的是：下层节点基数估算不准确，会影响后续所有计算，导致总成本估算不准确，从而选择了不理想的执行计划。更糟糕的是，优化器没有关于连接结果的统计信息，只能依赖表的统计信息。

成本估算 成本估算的过程同样是递归的。要计算一个子树的成本，需要先计算并累加其所有子节点的成本，然后再加上父节点自身的成本。

在估算节点成本时，PostgreSQL 会根据该节点执行的操作建立数学模型，并以已经估算好的节点基数作为输入。对于每个节点，都会计算 启动成本 和 总成本。

某些操作没有前置条件，因此可以立即执行，这类节点的启动成本为零。

而另一类操作则必须等待一些前置操作完成后才能执行。例如，排序节点通常需要等待其子节点返回所有数据后，才能进行自己的任务。这类节点的启动成本通常大于零：即使上层节点（或客户端）只需要输出中的一行，也必须支付这一成本。

优化器进行的所有计算都是估算值，可能与实际执行时间无关。它们的唯一目的，是在相同条件下对同一查询的不同执行计划进行比较。在其他情况下（尤其是不同查询之间），用成本来比较意义不大。例如，由于统计信息过时，成本可能被低估；在统计信息刷新后，计算出的成本可能上升，但由于估算更准确，服务器会选择更优的执行计划。

Execution

在查询优化阶段生成的执行计划现在必须被执行。

执行器（executor）会在后端内存中打开一个 portal，这是一个保存当前正在执行查询状态的对象。这个状态以一棵树的形式表示，结构与执行计划树相同。树中的各节点像流水线一样运作，彼此请求并传递行数据。

查询执行从根节点开始。以本例为例，根节点表示 排序（SORT）操作，它从子节点获取数据。在接收到所有行之后，根节点对数据进行排序，并将结果传递给客户端。

某些节点（如图示中的 NESTLOOP 节点）负责将来自不同来源的数据集进行连接。此类节点会从两个子节点拉取数据，并在收到满足连接条件的行对后立即向上层传递结果行（与排序不同，排序必须先获取所有行）。此时，节点的执行会暂停，直到其父节点请求下一行。如果查询只需要部分结果（例如包含 LIMIT 子句），该操作不会执行完整。

树中的两个 SEQSCAN 叶子节点负责表扫描。当父节点请求数据时，这些节点会从对应的表中获取下一行数据。

因此，一些节点不存储任何行，而是立即向上层传递数据；而其他节点（如 SORT）可能需要保留大量数据。为此，后端内存中会为其分配一个 work_mem 内存块；如果内存不足，多余的数据会溢写到磁盘上的临时文件。

一个执行计划可能包含多个需要数据存储的节点，因此 PostgreSQL 可能会分配多个 work_mem 大小的内存块。查询可使用的总 RAM 大小没有任何限制。

翻译来之

1. Egor Rogov, PostgreSQL 14 Internals, https://postgrespro.com/community/books/internals

关于全文搜索

全文搜索的目标是从提供的文档集中选择与搜索查询匹配的文档

为了进行搜索，文档会被转换为 tsvector 类型，该类型包含文档中的词素（lexemes）及其在文档中的位置。词素是将单词转换为适合搜索的格式。默认情况下，所有单词都会被标准化为小写，并去除其词尾。

“并去除其词尾”指的是在全文搜索中，对单词进行词干提取（stemming）或词形归一化（normalization）的过程。具体来说，这是将单词的词尾（如英语中的复数、时态、词性变化等）去除，提取出单词的词干（stem）或基本形式，以便在搜索时能够匹配同一词根的不同变体。例如：单词“running”、“ran”和“runs”都源自同一词根“run”。在全文搜索的处理中，这些单词可能会被归一化为“run”，即去除词尾变化，保留词干。搜索“run”时，系统不仅会匹配“run”，还会匹配“running”、“ran”和“runs”等形式，因为它们都被归一化为相同的词干“run”。

1
2
3
4
5
6
7
8
9
10

demo=# SET default_text_search_config = english;
SET
demo=# SELECT to_tsvector(
    'No one can tell me, nobody knows, ' ||
    'Where the wind comes from, where the wind goes.'
);
                             to_tsvector                              
----------------------------------------------------------------------
 'come':11 'goe':16 'know':7 'nobodi':6 'one':2 'tell':4 'wind':10,15
(1 row)

所谓的停用词（如“the”或“from”）会被过滤掉：这些词被认为出现频率过高，搜索它们无法返回有意义的搜索结果。当然，所有这些转换都是可以配置的。

查询由另一种类型表示：tsquery。任何查询都包含一个或多个通过逻辑连接符连接的词素：&（与）、|（或）、!（非）。你还可以使用括号来定义操作符的优先级。

1
2
3
4
5

demo=# SELECT to_tsquery('wind & (comes | goes)');
         to_tsquery          
-----------------------------
 'wind' & ( 'come' | 'goe' )
(1 row)

全文搜索中唯一使用的操作符是匹配操作符 @@：

1
2
3
4
5
6
7
8

demo=# SELECT amopopr::regoperator, oprcode::regproc, amopstrategy FROM pg_am am
JOIN pg_opclass opc ON opcmethod = am.oid JOIN pg_amop amop ON amopfamily = opcfamily JOIN pg_operator opr ON opr.oid = amopopr
WHERE amname = 'gist'
AND opcname = 'tsvector_ops' ORDER BY amopstrategy;
       amopopr        |   oprcode   | amopstrategy 
----------------------+-------------+--------------
 @@(tsvector,tsquery) | ts_match_vq |            1
(1 row)

该操作符判断文档是否满足查询条件。以下是一个示例：

1
2
3
4
5

demo=# SELECT to_tsvector('Where the wind comes from, where the wind goes') @@ to_tsquery('wind & coming');
 ?column? 
----------
 t
(1 row)

这绝不是对全文搜索的详尽描述，但这些信息应足以理解索引的基础知识。

Indexing tsvector Data

为了实现快速的全文搜索，必须使用索引来支持。索引的对象不是文档本身，而是 tsvector 值。这里有两种选择：一种是在表达式上构建索引并进行类型转换，另一种是添加一个单独的 tsvector 类型列并对该列进行索引。第一种方法的优点是不会浪费空间来存储 tsvector 值，因为这些值实际上并不需要直接存储。但这种方法比第二种方法慢，因为索引引擎需要重新检查访问方法返回的所有堆元组。这意味着对于每个重新检查的行，都需要再次计算 tsvector 值，而且正如我们很快会看到的，GiST 索引会重新检查所有行。

让我们构建一个简单的示例。我们将创建一个包含两列的表：第一列存储文档，第二列存储 tsvector 值。我们可以使用触发器来更新第二列，但更方便的做法是直接将该列声明为生成列。

1
2
3
4
5
6
7
8
9
10

CREATE TABLE ts(
    doc text,
    doc_tsv tsvector GENERATED ALWAYS AS (
         to_tsvector('pg_catalog.english', doc) 
    ) STORED
);
CREATE TABLE
demo=# CREATE INDEX ts_gist_idx ON ts
USING gist(doc_tsv);
CREATE INDEX

在上面的例子中，我使用了带有单一参数的 to_tsvector 函数，通过设置 default_text_search_config 参数来定义全文搜索配置。这种函数变体的波动性（volatility）类别是 STABLE，因为它隐式依赖于参数值。但在这里，我使用了另一种变体，显式指定配置；这种变体是 IMMUTABLE，可以用于生成表达式。

我们插入几行数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

demo=# INSERT INTO ts(doc) VALUES
('Old MacDonald had a farm'), ('And on his farm he had some cows'),
('Here a moo, there a moo'), ('Everywhere a moo moo'),
('Old MacDonald had a farm'), ('And on his farm he had some chicks'),
('Here a cluck, there a cluck'), ('Everywhere a cluck cluck'),
('Old MacDonald had a farm'),('And on his farm he had some pigs'),
('Here an oink, there an oink'),('Everywhere an oink oink')
RETURNING doc_tsv;
            doc_tsv             
--------------------------------
 'farm':5 'macdonald':2 'old':1
 'cow':8 'farm':4
 'moo':3,6
 'everywher':1 'moo':3,4
 'farm':5 'macdonald':2 'old':1
 'chick':8 'farm':4
 'cluck':3,6
 'cluck':3,4 'everywher':1
 'farm':5 'macdonald':2 'old':1
 'farm':4 'pig':8
 'oink':3,6
 'everywher':1 'oink':3,4
(12 rows)

因此，R 树不适合用于索引文档，因为边界框（bounding box）的概念对文档没有意义。因此，使用了其 RD 树（俄罗斯套娃，Russian Doll）变体。RD 树不使用边界框，而是使用边界集（bounding set），即一个包含其所有子集元素的集合。对于全文搜索，这样的集合包含文档的词素（lexemes），但在一般情况下，边界集可以是任意的。

在索引条目中表示边界集有几种方法。最简单的一种是列举集合中的所有元素。如下图所示

为了找到满足 DOC_TSV @@ TO_TSQUERY(‘COW’) 条件的文档，我们需要深入到那些已知包含“cow”词素的子节点的节点。

这种表示方式的问题显而易见。文档中的词素数量可能非常庞大，而页面大小是有限的。即使单个文档的独特词素数量不算太多，在树的较高层级中，它们的联合集仍然可能变得过大。

全文搜索使用了另一种解决方案，即更紧凑的签名树（signature tree）。对于那些熟悉布隆过滤器（Bloom filter）的人来说，这种解决方案应该很熟悉。

每个词素可以由其签名（signature）表示：一个特定长度的位字符串，其中只有一位被置为 1。置为 1 的位由词素的哈希函数决定。

文档的签名是对该文档中所有词素签名的按位或（bitwise OR）操作结果。

这种方法的优点显而易见：索引条目大小相同且相当小，因此索引非常紧凑。但也存在一些缺点。首先，无法执行仅索引扫描（index-only scan），因为索引不再存储索引键，每个返回的 TID（行标识）都必须通过表进行重新检查。此外，准确性也会受到影响：索引可能返回许多误报（false positives），这些误报需要在重新检查阶段过滤掉。

让我们再次看看 DOC_TSV @@ TO_TSQUERY(‘COW’) 条件。查询的签名（signature）以与文档相同的方式计算；在这个特定情况下，其签名等于 0000010。一致性函数（consistency function）必须找到所有签名中具有相同位被置位的子节点。

与前面的例子相比，这里需要扫描更多的节点，因为存在误报（false-positive）命中。由于签名的容量有限，在大型集合中，某些词素必然会具有相同的签名。在这个例子中，这样的词素是“cow”和“oink”。这意味着一个签名可能匹配多个不同的文档；在这里，查询的签名对应于三个文档。

误报会降低索引的效率，但不会以任何方式影响其正确性：因为假阴性（false negatives）被保证排除，所以不会遗漏所需的值。

显然，签名的实际大小要大得多。默认情况下，签名占用 123 字节（992 位），因此冲突的概率远低于本例中所示。如果需要，可以使用操作符类参数进一步将签名大小增加到大约 2000 字节。

1

CREATE INDEX ... USING gist(column tsvector_ops(siglen = 1024));

此外，如果值足够小（略小于页面大小的 1/16，对于标准页面大约是 500 字节），tsvector_ops 操作符类会在索引的叶子页面中存储 tsvector 值本身，而不是它们的签名。

为了了解索引在真实数据上的工作方式，我们可以使用 pgsql-hackers 邮件列表存档。该存档包含 356,125 封电子邮件，包括发送日期、主题、作者姓名和正文文本。让我们添加一个 tsvector 类型的列并构建索引。在这里，我将三个值（主题、作者和正文文本）组合成一个单一的向量，以展示文档可以动态生成，而不必存储在单一列中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

ALTER TABLE mail_messages ADD COLUMN tsv tsvector GENERATED ALWAYS AS ( to_tsvector(
'pg_catalog.english', subject||' '||author||' '||body_plain ) ) STORED;
NOTICE: word is too long to be indexed
DETAIL: Words longer than 2047 characters are ignored.
...
NOTICE: word is too long to be indexed
DETAIL: Words longer than 2047 characters are ignored. 
ALTER TABLE

CREATE INDEX mail_gist_idx ON mail_messages USING gist(tsv);
SELECT pg_size_pretty(pg_relation_size('mail_gist_idx'));
pg_size_pretty 
−−−−−−−−−−−−−−−−
127 MB 
(1 row)

在填充该列（tsv）的过程中，一些特别长的词因为长度太大被过滤掉了。但一旦索引构建完成，就可以用于搜索查询了。

1
2
3
4
5
6
7
8
9
10
11
12
13

demo=# EXPLAIN (analyze, costs off, timing off, summary off) SELECT *
FROM mail_messages
WHERE tsv @@ to_tsquery('magic & value');
                                  QUERY PLAN                                  
------------------------------------------------------------------------------
 Index Scan using mail_gist_idx on mail_messages (actual rows=898.00 loops=1)
   Index Cond: (tsv @@ to_tsquery('magic & value'::text))
   Rows Removed by Index Recheck: 7852
   Index Searches: 1
   Buffers: shared hit=27575 read=31875
 Planning:
   Buffers: shared hit=75 read=4
(7 rows)

除了满足条件的 898 行之外，访问方法还返回了另外 7852 行，这些行需要后续通过回检（recheck）来过滤。如果我们增加签名容量（signature capacity），准确性（也就是索引效率）会提高，但索引的大小也会随之增加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

demo=# DROP INDEX mail_messages_tsv_idx;
DROP INDEX
demo=# CREATE INDEX ON mail_messages
USING gist(tsv tsvector_ops(siglen=1024));
CREATE INDEX
demo=# SELECT pg_size_pretty(pg_relation_size('mail_messages_tsv_idx'));
 pg_size_pretty 
----------------
 241 MB
(1 row)

demo=# EXPLAIN (analyze, costs off, timing off, summary off) SELECT *
FROM mail_messages
WHERE tsv @@ to_tsquery('magic & value');
                                  QUERY PLAN                                  
------------------------------------------------------------------------------
 Index Scan using mail_gist_idx on mail_messages (actual rows=898.00 loops=1)
   Index Cond: (tsv @@ to_tsquery('magic & value'::text))
   Rows Removed by Index Recheck: 7852
   Index Searches: 1
   Buffers: shared hit=25968 read=33482
 Planning:
   Buffers: shared hit=3 read=2 dirtied=1
(7 rows)

Properties

我已经展示了访问方法的属性，其中大多数在所有操作符类中都是相同的。但是下面两个列级别的属性值得一提：

1
2
3
4
5
6
7
8
9

demo=# SELECT p.name, pg_index_column_has_property('mail_messages_tsv_idx', 1, p.name)
FROM unnest(array[
'returnable', 'distance_orderable'
]) p(name);
        name        | pg_index_column_has_property 
--------------------+------------------------------
 returnable         | f
 distance_orderable | f
(2 rows)

现在不可能进行 Index-only 扫描了，因为无法从签名中恢复出原始值。
不过在这个特定的场景下这是完全可以接受的：
tsvector 值只是用于搜索，我们真正需要的是文档本身（也就是实际的数据行）。
对于 tsvector_ops 类来说，也没有定义排序操作符

参考书目

1. Egor Rogov, PostgreSQL 14 Internals, https://postgrespro.com/community/books/internals

第一个示例涉及在平面上对点（或其他几何形状）进行索引。常规的B树无法用于这种数据类型，因为点没有定义比较运算符。显然，我们可以自己实现这样的运算符，但几何形状需要索引支持完全不同的操作。我将只讨论其中的两种：搜索特定区域内包含的对象和最近邻搜索。

R树在平面上绘制矩形；这些矩形合起来必须覆盖所有被索引的点。一个索引条目存储边界框，谓词可以定义如下：点位于该边界框内。

R树的根节点包含若干个大矩形（这些矩形可能会有重叠）。子节点包含较小的矩形，这些矩形适合其父节点；它们一起覆盖所有底层的点。

叶节点应该包含被索引的点本身，但GiST要求所有条目具有相同的数据类型；因此，叶节点的条目也由矩形表示，这些矩形被简化为点。

为了更好地可视化这种结构，我们来看一个基于机场坐标构建的R树的三个层次。在这个例子中，我已将演示数据库的机场表扩展到五千行。同时我还降低了fillfactor值使树的层次更深。默认值会给我们一个单层树。

1
2
3
4
5
6

demo=# CREATE TABLE airports_big AS select * from airports_data;
SELECT 104     
demo=# COPY airports_big FROM '/home/postgres/data/extra_airports.copy';
COPY 5413
demo=# CREATE INDEX airports_gist_idx ON airports_big USING gist(coordinates) WITH (fillfactor=10);
CREATE INDEX

在顶层，所有点都被包含在几个（可能部分重叠的）边界框中。

在下一层，大矩形被分割成较小的矩形。

最后，在树的底层，每个边界框包含的点数量与单个页面所能容纳的数量相同。

该索引使用point_ops操作符类，这是点数据唯一可用的操作符类。

矩形和其他几何形状可以以相同的方式进行索引，但索引存储的不是对象本身，而是其边界框。

Page Layout

可以通过 pageinspect 插件来学习Gist页

和B-Tree索引不同，Gist没有metapage，0号page就是gist的root节点。如果root节点分裂了，老root节点会被move到一个（或多个）单独的页，新root节点取代其位置

root页的内容如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

demo=# SELECT ctid, keys FROM gist_page_items(get_raw_page('airports_gist_idx', 0), 'airports_gist_idx' );
    ctid    |                                               keys                                               
------------+--------------------------------------------------------------------------------------------------
 (1,65535)  | (coordinates)=("(-75.47339630130001,-0.12295600026845932),(-179.876998901,-43.810001373291016)")
 (2,65535)  | (coordinates)=("(-62.919601,-0.14835),(-74.9615020752,-54.93109893798828)")
 (3,65535)  | (coordinates)=("(-39.253101348877,-17.652299880981),(-62.1693,-62.1907997131)")
 (4,65535)  | (coordinates)=("(-14.3937,-0.6994310021400452),(-61.8465003967,-16.706899642899998)")
 (5,65535)  | (coordinates)=("(22.4692001343,-2.7174999713897705),(10.674076080322266,-34.554901123)")
 (6,65535)  | (coordinates)=("(63.361,-2.3089799880981445),(22.9993000031,-34.0881601675)")
 (7,65535)  | (coordinates)=("(177.97799682617188,-31.94029998779297),(115.401596069,-46.8997)")
 (8,65535)  | (coordinates)=("(-79.3834991455,28.20170021057129),(-177.38099670410156,0.9785190224647522)")
 (9,65535)  | (coordinates)=("(-51.0722007751,19.96980094909668),(-78.7492,0.0506640002131)")
 (10,65535) | (coordinates)=("(128.707992554,-0.06239889934659004),(8.754380226135254,-30.83810043334961)")
 (11,65535) | (coordinates)=("(153.56199646,-0.8918330073356628),(130.6199951171875,-31.8885993958)")
 (12,65535) | (coordinates)=("(179.951004028,-0.547458),(154.67300415039062,-31.5382995605)")
 (13,65535) | (coordinates)=("(-153.7039948,71.285402),(-176.64599609375,51.87799835205078)")
 (14,65535) | (coordinates)=("(-128.576009,70.33080291750001),(-152.621994019,53.25429916379999)")
 (15,65535) | (coordinates)=("(-104.26300048828125,39.90879822),(-122.8130035,24.072700500499998)")
 (16,65535) | (coordinates)=("(-91.149597,37.9275016785),(-103.602996826,25.54949951171875)")
 (17,65535) | (coordinates)=("(-68.36340332030001,31.9512996674),(-90.25800323486328,18.25149917602539)")
 (18,65535) | (coordinates)=("(-2.269860029220581,31.9475002289),(-67.14849853515625,4.3790202140808105)")
 (19,65535) | (coordinates)=("(-115.78199768066,63.20940017700195),(-127.36699676513672,40.1506996155)")
 (20,65535) | (coordinates)=("(-96.6707992553711,62.462799072265625),(-114.903999329,37.649899)")
 (21,65535) | (coordinates)=("(-83.29579926,37.24570084),(-95.984596252441,32.30059814)")
 (22,65535) | (coordinates)=("(-83.3467025756836,48.06570053),(-96.38439941,37.74010086)")
 (23,65535) | (coordinates)=("(-78.31999969,47.697400654599996),(-83.072998,32.00999832)")
 (24,65535) | (coordinates)=("(-64.67859649658203,47.990799),(-77.98459625,32.36399841308594)")
 (25,65535) | (coordinates)=("(-74.5280990600586,79.9946975708),(-126.7979965209961,48.0532989502)")
 (26,65535) | (coordinates)=("(-13.746399879455566,82.51779937740001),(-72.2656021118164,32.697899)")
 (27,65535) | (coordinates)=("(25.3379993439,39.828335),(-9.35523,0.0226000007242)")
 (28,65535) | (coordinates)=("(1.7605600357100002,48.069499969499994),(-8.68138980865,40.471926)")
 (29,65535) | (coordinates)=("(1.954759955406189,62.0635986328125),(-9.653610229492188,48.447898864746094)")
 (30,65535) | (coordinates)=("(173.82899475097656,31.3253993988),(27.221700668300002,0.042386)")
 (31,65535) | (coordinates)=("(7.8790798,61.583599090576),(2.040833,32.38410186767578)")
 (32,65535) | (coordinates)=("(58.890499114990234,31.989853),(32.2400016784668,10.350000381469727)")
 (33,65535) | (coordinates)=("(89.4672012329,31.909400939941406),(60.3820991516,8.30148983002)")
 (34,65535) | (coordinates)=("(111.63999939,31.4281005859375),(90.30120086669922,8.09912014008)")
 (35,65535) | (coordinates)=("(169.852005,31.919701),(113.069999695,8.178509712219238)")
 (36,65535) | (coordinates)=("(17.439699172973633,52.59120178222656),(6.504444,32.6635017395)")
 (37,65535) | (coordinates)=("(31.1583003998,52.527000427246094),(17.828399658203125,32.096801757799994)")
 (38,65535) | (coordinates)=("(30.60810089111328,57.78390121459961),(6.57944011688,53.0475006104)")
 (39,65535) | (coordinates)=("(31.044900894165,78.246101379395),(6.0741000175476,58.0994987487793)")
 (40,65535) | (coordinates)=("(42.4826011658,61.88520050048828),(31.9197998046875,32.01139831542969)")
 (41,65535) | (coordinates)=("(75.634444,63.566898345947266),(43.025978088378906,32.056098938)")
 (42,65535) | (coordinates)=("(98.3414,73.51780700683594),(32.75080108642578,32.1)")
 (43,65535) | (coordinates)=("(122.853996,71.97810363769531),(100.0989990234375,32.1506)")
 (44,65535) | (coordinates)=("(177.74099731445312,71.697700500488),(123.48300170898438,32.482498)")
(44 rows)

To extract more detailed information, you can use the gevel extension,which is not included into the standard PostgreSQL distribution.

Operator Class

This query retrieves the list of support functions used by the point_ops operator class in a GiST (Generalized Search Tree) index within a PostgreSQL database

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

demo=# SELECT amprocnum, amproc::regproc
FROM pg_am am
JOIN pg_opclass opc ON opcmethod = am.oid
JOIN pg_amproc amop ON amprocfamily = opcfamily
WHERE amname = 'gist'
AND opcname = 'point_ops'
ORDER BY amprocnum;
 amprocnum |         amproc         
-----------+------------------------
         1 | gist_point_consistent
         2 | gist_box_union
         3 | gist_point_compress
         5 | gist_box_penalty
         6 | gist_box_picksplit
         7 | gist_box_same
         8 | gist_point_distance
         9 | gist_point_fetch
        11 | gist_point_sortsupport
(9 rows)

必需的函数：

1 consistency function used to traverse the tree during search（检查查询条件是否与索引条目一致）

2 union function that merges rectangles计算边界框的并集）

5 penalty function used to choose the subtree to descend to when inserting an entry （计算插入新条目的代价）

6 picksplit function that distributes entries between new pages after a page split（决定节点分裂方式）

7 same function that checks two keys for equality（比较索引条目是否相同）

point_ops 支持的操作符如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

demo=# SELECT amopopr::regoperator, amopstrategy AS  st, oprcode::regproc,
left(obj_description(opr.oid, 'pg_operator'),19) description
FROM pg_am am
        JOIN pg_opclass opc ON opcmethod = am.oid 
        JOIN pg_amop amop ON amopfamily = opcfamily 
        JOIN pg_operator opr ON opr.oid = amopopr
WHERE amname = 'gist'
AND opcname = 'point_ops' 
ORDER BY amopstrategy;
      amopopr      | st |       oprcode       |     description     
-------------------+----+---------------------+---------------------
 <<(point,point)   |  1 | point_left          | is left of
 >>(point,point)   |  5 | point_right         | is right of
 ~=(point,point)   |  6 | point_eq            | same as
 <<|(point,point)  | 10 | point_below         | is below
 |>>(point,point)  | 11 | point_above         | is above
 <->(point,point)  | 15 | point_distance      | distance between
 <@(point,box)     | 28 | on_pb               | point inside box
 <^(point,point)   | 29 | point_below         | deprecated, use <<|
 >^(point,point)   | 30 | point_above         | deprecated, use |>>
 <@(point,polygon) | 48 | pt_contained_poly   | is contained by
 <@(point,circle)  | 68 | pt_contained_circle | is contained by
(11 rows)

操作符的名字通常并不能准确反映其语义，因此这个查询还会显示底层函数的名称和它们的描述。无论具体形式如何，这些操作符都处理几何对象之间的相对位置关系（如在左侧、右侧、上方、下方、包含、被包含）以及它们之间的距离。
与 B-tree 相比，GiST 提供了更多的策略（strategy）。一些策略号在多种类型的索引中是通用的，而另一些则是通过公式计算出来的（例如，策略号 28、48 和 68 实际上代表相同的策略：对矩形、多边形和圆形来说都是“被包含”）。此外，GiST 还支持一些已经过时的操作符名称（例如 <<| 和 |>>）。
一个操作符类（operator class）可能只实现了部分可用的策略。举个例子：点类型的操作符类不支持“包含”这个策略，但这个策略在那些具有可度量面积的几何体操作符类（如 box_ops、poly_ops 和 circle_ops）中是可用的。

Search for Contained Elements

一个典型的可以通过索引加速的查询是返回指定区域内的所有点。例如，我们来查找距离莫斯科中心一度以内的所有机场：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

demo=# SELECT airport_code, airport_name->>'en'
FROM airports_big
WHERE coordinates <@ '<(37.622513,55.753220),1.0>'::circle;
 airport_code |              ?column?              
--------------+------------------------------------
 SVO          | Sheremetyevo International Airport
 VKO          | Vnukovo International Airport
 DME          | Domodedovo International Airport
 BKA          | Bykovo Airport
 ZIA          | Zhukovsky International Airport
 CKL          | Chkalovskiy Air Base
 OSF          | Ostafyevo International Airport
(7 rows)

demo=# EXPLAIN (costs off) SELECT airport_code
FROM airports_big
WHERE coordinates <@ '<(37.622513,55.753220),1.0>'::circle;
                               QUERY PLAN                                
-------------------------------------------------------------------------
 Bitmap Heap Scan on airports_big
   Recheck Cond: (coordinates <@ '<(37.622513,55.75322),1>'::circle)
   ->  Bitmap Index Scan on airports_gist_idx
         Index Cond: (coordinates <@ '<(37.622513,55.75322),1>'::circle)
(4 rows)

我们可以通过下图所示的一个简单示例来更仔细地查看这个操作符

如果以这种方式选择边界框，索引结构将如下所示：

包含操作符 <@ 用于判断某个点是否位于指定矩形内部。对于该操作符，其一致性函数（consistency function）会在索引条目的矩形与指定矩形有任何重合点时返回“是”。这意味着，对于叶子节点中的索引条目（它们通常是退化为点的矩形），该函数实际上是在判断这个点是否被指定的矩形所包含。

例如，假设我们要查找位于矩形 (1,2)–(4,7) 内部的点，该矩形在下图中以阴影表示：

搜索从根节点开始。目标矩形与索引项 (0,0)–(3,4) 有重叠，但与 (5,3)–(9,9) 没有重叠，这意味着我们不需要进入第二棵子树。
在下一层中，目标矩形与 (0,3)–(3,4) 有重叠，并且与 (0,0)–(3,2) 有接触（边界相交），所以我们需要检查这两个子树。
一旦到达叶子节点，我们只需遍历它们包含的所有点，并返回那些满足一致性函数的点

B-tree 的搜索总是只选择一个子节点进行查找。而 GiST 的搜索可能需要扫描多个子树，特别是当它们的边界框（bounding boxes）发生重叠时。

Nearest Neighbor Search

大多数索引支持的操作符（例如上一个例子中的 = 或 <@）通常被称为搜索操作符，因为它们在查询中定义了搜索条件。这类操作符是谓词，即它们返回一个逻辑值（真或假）。

但还有一类是排序操作符，它们返回的是参数之间的距离。这类操作符通常用于 ORDER BY 子句中，并且一般由具有 Distance Orderable 属性的索引所支持。该属性允许你快速找到指定数量的最近邻。这种类型的搜索被称为 k-NN（k 最近邻搜索）。

例如，我们可以查找最接近 Kostroma 的 10 个机场：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

demo=# SELECT airport_code, airport_name->>'en'
FROM airports_big
ORDER BY coordinates <-> '(40.926780,57.767943)'::point LIMIT 10;
 airport_code |                    ?column?                    
--------------+------------------------------------------------
 KMW          | Kostroma Sokerkino Airport
 IAR          | Tunoshna Airport
 IWA          | Ivanovo South Airport
 VGD          | Vologda Airport
 RYB          | Staroselye Airport
 GOJ          | Nizhny Novgorod Strigino International Airport
 CEE          | Cherepovets Airport
 CKL          | Chkalovskiy Air Base
 ZIA          | Zhukovsky International Airport
 BKA          | Bykovo Airport
(10 rows)

demo=# EXPLAIN (costs off) SELECT airport_code
FROM airports_big
ORDER BY coordinates <-> '(40.926780,57.767943)'::point LIMIT 5;
                            QUERY PLAN                             
-------------------------------------------------------------------
 Limit
   ->  Index Scan using airports_gist_idx on airports_big
         Order By: (coordinates <-> '(40.92678,57.767943)'::point)
(3 rows)

由于索引扫描是逐个返回结果，并且可以在任何时刻停止，因此前几个值可以非常快速地获取到。

如果没有索引支持，要实现高效的搜索将非常困难。我们将不得不先查找某个特定区域内的所有点，然后逐步扩大该区域，直到返回所需数量的结果。
这将需要多次索引扫描，更不用说还存在一个难题：如何选择初始区域的大小以及每次扩展的增量。

你可以在系统目录中查看操作符的类型（其中 “s” 表示搜索操作符，”o” 表示排序操作符）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

demo=# SELECT amopopr::regoperator, amoppurpose, amopstrategy FROM pg_am am
JOIN pg_opclass opc ON opcmethod = am.oid
JOIN pg_amop amop ON amopfamily = opcfamily WHERE amname = 'gist'
AND opcname = 'point_ops'
ORDER BY amopstrategy;
      amopopr      | amoppurpose | amopstrategy 
-------------------+-------------+--------------
 <<(point,point)   | s           |            1
 >>(point,point)   | s           |            5
 ~=(point,point)   | s           |            6
 <<|(point,point)  | s           |           10
 |>>(point,point)  | s           |           11
 <->(point,point)  | o           |           15
 <@(point,box)     | s           |           28
 <^(point,point)   | s           |           29
 >^(point,point)   | s           |           30
 <@(point,polygon) | s           |           48
 <@(point,circle)  | s           |           68
(11 rows)

为了支持这类查询，操作符类必须定义一个额外的支持函数：也就是距离函数（distance function），它会在索引项上被调用，用于计算该索引项中存储的值与另一个值之间的距离。

对于表示索引值的叶子节点元素，该函数必须返回与该值之间的距离。
如果是点（point）类型，这个距离就是常规的欧几里得距离，计算公式为：

1

d = sqrt((x₂-x₁)²+(y₂-y₁)²)

对于一个内部节点，其距离函数必须返回其所有子叶节点中可能距离的最小值。
由于扫描所有子节点的条目代价较高，该函数可以乐观地低估这个距离（以牺牲效率为代价），但绝不能返回一个较大的值——否则将会破坏搜索的正确性

因此，对于一个由边界框（bounding box）表示的内部节点，其与某个点之间的距离可以按照常规数学意义来理解：
要么是该点到矩形边界的最小距离；要么是 0（如果该点在矩形内部）。
这个值可以在无需遍历矩形中所有子点的情况下轻松计算出来，
并且它保证不会大于矩形中任意一个子点与该查询点之间的实际距离

我们考虑一下寻离点（6，8）最近的3个值

搜索从根节点开始，根节点包含两个边界框（bounding box）。指定查询点到矩形 (0,0)–(3,4) 的距离被计算为到该矩形的角点 (3,4) 的距离，即 5.0。到另一个矩形 (5,3)–(9,9) 的距离为 0.0。（这里我会将所有的距离值四舍五入保留到小数点后一位，这种精度对于这个示例来说已经足够。）

子节点会按照距离增大的顺序被遍历。因此，我们首先进入右子节点，该节点包含两个矩形：(5,3)–(8,5) 和 (6,6)–(9,9)。到第一个矩形的距离是 3.0，到第二个矩形的距离是 0.0。
再次地，我们选择右子树，并进入包含三个点的叶子节点：点 (6,6) 的距离为 2.0，点 (8,9) 的距离为 2.2，点 (9,7) 的距离为 3.2。

因此，我们已经找到了前两个点：(6,6) 和 (8,9)。但该节点中的第三个点距离（查询点）要大于矩形 (5,3)–(8,5) 的距离。

所以我们需要进入左子节点，该节点包含两个点。到点 (8,5) 的距离是 3.6， 到点 (5,3) 的距离是 5.1。结果发现，之前那个子节点中的点 (9,7) 比左子树中的任何点都更接近查询点 (6,8)，因此我们可以将它作为第三个返回结果。

这个例子说明了内部条目的距离函数必须满足的要求。由于到矩形 (5,3)–(8,5) 的距离减小（3.0 而不是 3.6），导致需要额外扫描一个节点，因此搜索效率下降；不过，算法本身仍然是正确的。

Insertion

当向 R 树中插入一个新键时，用于存放该键的节点是由penalty函数决定的：该节点的边界框（bounding box）大小应尽可能少地增加。

例如，点 (4,7) 将被插入到矩形 (5,3)–(9,9) 中，因为该矩形的面积只需增加 6 个单位；而如果插入到矩形 (0,0)–(3,4)，则其面积需要增加 12 个单位。在下一层（叶子层），该点也会按照相同的逻辑被加入到矩形 (6,6)–(9,9) 中。

假设一个页面最多可以容纳三个元素，那么当超出这个限制时，它必须被拆分成两个页面，
并且这些元素需要在新的页面之间重新分配。在这个示例中，分配结果看起来很明显，但在一般情况下，数据的分布并不那么简单。最重要的是，picksplit 函数会尽量减少边界框（bounding box）之间的重叠，目标是获得更小的矩形以及在页面之间均匀分布点。

Exclusion Constraints

GiST 索引也可以用于排除约束（exclusion constraints）。排除约束确保：对任意两条堆表元组来说，它们在某些操作符意义下的指定字段不能彼此匹配。要实现这一点，必须满足以下条件：

• 排除约束（exclusion constraint）必须由索引方法本身支持（即具备 Can Exclude 属性）。
• 所使用的操作符必须属于该索引方法的操作符类（operator class）；
• 操作符必须是可交换的：即满足 “a operator b = b operator a” 这个条件。

对于上面提到的 hash 和 btree 访问方法来说，唯一合适的操作符是等于（=）。这实际上使排除约束退化成了唯一约束，因而没有太大实际用途

GiST 方法还支持另外两种适用的策略：

• 重叠（overlapping）：由 && 操作符表示
• 相邻（adjacency）：由 -|- 操作符表示（该操作符主要用于区间）

我们来试试这个功能：创建一个约束，用于禁止机场之间距离太近。
这个条件可以这样表达：以机场坐标为圆心、指定半径的圆形不得彼此重叠。

1
2
3
4
5
6
7
8

demo=# ALTER TABLE airports_data ADD EXCLUDE USING gist (circle(coordinates,0.2) WITH &&);
ALTER TABLE
demo=# INSERT INTO airports_data(
airport_code, airport_name, city, coordinates, timezone
) VALUES (
'ZIA', '{}', '{"en": "Moscow"}', point(38.1517, 55.5533), 'Europe/Moscow');
ERROR:  conflicting key value violates exclusion constraint "airports_data_circle_excl"
DETAIL:  Key (circle(coordinates, 0.2::double precision))=(<(38.1517,55.5533),0.2>) conflicts with existing key (circle(coordinates, 0.2::double precision))=(<(37.90629959106445,55.40879821777344),0.2>).

当定义一个排除约束（exclusion constraint）时，系统会自动创建一个索引来强制执行该约束。在本例中，这个索引是一个基于表达式的 GiST 索引。

我们来看一个更复杂的例子。假设我们允许机场之间距离很近，但前提是这些机场属于同一个城市。一种可行的解决方案是定义一个新的完整性约束，表达如下：如果两个圆（以机场坐标为圆心）发生重叠（&&），且它们对应的城市名称不同（!=），则这种情况是不允许的。

尝试创建这样的约束会导致一个错误，因为对于 text 数据类型并没有可用的操作符类（operator class）。

1
2
3
4
5
6
7
8
9

demo=# ALTER TABLE airports_data
DROP CONSTRAINT airports_data_circle_excl;
ALTER TABLE
demo=# ALTER TABLE airports_data ADD EXCLUDE USING gist ( circle(coordinates,0.2) WITH &&,
(city->>'en') WITH !=
);
ERROR:  data type text has no default operator class for access method "gist"
HINT:  You must specify an operator class for the index or define a default operator class for the data type.
demo=# 

虽然 GiST 原生不支持 text 或 int 等有序类型，但借助 btree_gist 扩展，可以让这些类型也具备使用 GiST 进行等值/比较操作的能力，从而用于复杂约束（如排除约束）或混合类型索引。

1
2
3
4
5
6
7

demo=# CREATE EXTENSION btree_gist;
CREATE EXTENSION
demo=# ALTER TABLE airports_data ADD EXCLUDE USING gist ( circle(coordinates,0.2) WITH &&,
(city->>'en') WITH !=
);
ALTER TABLE
demo=# 

该约束已成功创建。现在我们无法添加名为 Zhukovsky 的机场（即使它属于同名城市），
因为它与莫斯科的几个机场之间的距离太近，违反了约束条件。

1
2
3
4
5
6
7
8

demo=# INSERT INTO airports_data(
airport_code, airport_name, city, coordinates, timezone
) VALUES (
'ZIA', '{}', '{"en": "Zhukovsky"}', point(38.1517, 55.5533), 'Europe/Moscow'
);
ERROR:  conflicting key value violates exclusion constraint "airports_data_circle_expr_excl"
DETAIL:  Key (circle(coordinates, 0.2::double precision), (city ->> 'en'::text))=(<(38.1517,55.5533),0.2>, Zhukovsky) conflicts with existing key (circle(coordinates, 0.2::double precision), (city ->> 'en'::text))=(<(37.90629959106445,55.40879821777344),0.2>, Moscow).
demo=# 

但是我们可以在莫斯科创建机场

1
2
3
4
5
6
7

demo=# INSERT INTO airports_data(
airport_code, airport_name, city, coordinates, timezone
) VALUES (
'ZIA', '{}', '{"en": "Moscow"}', point(38.1517, 55.5533), 'Europe/Moscow'
);
INSERT 0 1
demo=# 

需要注意的是，尽管 GiST 支持大于、小于和等于等操作符，但 B-tree 在这方面效率要高得多，尤其是在访问一段范围值时。因此，只有当确实有其他合理原因需要使用 GiST 索引时，
才有意义使用上面提到的 btree_gist 扩展技巧。

Properties

访问方法属性（Access Method Properties）以下是 GiST 访问方法的属性：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

demo=# 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 = 'gist';
 amname |     name      | pg_indexam_has_property 
--------+---------------+-------------------------
 gist   | can_order     | f
 gist   | can_unique    | f
 gist   | can_multi_col | t
 gist   | can_exclude   | t
 gist   | can_include   | t
(5 rows)

GiST 索引不支持唯一约束（Unique constraints）和排序（sorting）。GiST 索引可以通过额外的 INCLUDE 列来创建。正如我们所知，我们可以在多个列上构建索引，也可以将其用于完整性约束（integrity constraints）。

索引级别属性（Index-level properties）。这些属性是在索引层面定义的。

1
2
3
4
5
6
7
8
9
10
11

demo=# SELECT p.name, pg_index_has_property('airports_gist_idx', p.name) 
FROM unnest(array[
'clusterable', 'index_scan', 'bitmap_scan', 'backward_scan' 
]) p(name);
     name      | pg_index_has_property 
---------------+-----------------------
 clusterable   | t
 index_scan    | t
 bitmap_scan   | t
 backward_scan | f
(4 rows)

GiST 索引可以用于聚簇（clusterization）操作。在数据检索方式方面，GiST 支持常规（逐行）索引扫描和位图扫描（bitmap scan）。但 GiST 不支持反向扫描（backward scanning）。

列级别属性（Column-level properties）：大多数列属性是在访问方法（access method）级别定义的，并且保持不变。

1
2
3
4
5
6
7
8
9
10
11

demo=# SELECT p.name, pg_index_column_has_property('airports_gist_idx', 1, p.name)
FROM unnest(array[
'orderable', 'search_array', 'search_nulls'
]) p(name);
 
     name     | pg_index_column_has_property 
--------------+------------------------------
 orderable    | f
 search_array | f
 search_nulls | t
(3 rows)

所有与排序相关的属性都是禁用的。

GiST 索引允许 NULL 值存在，但处理效率并不高。一般认为，NULL 值不会扩展边界框（bounding box），所以这些值会被随机插入某个子树中。因此，在查询时需要遍历整棵 GiST 树来查找这些值。

不过，有少数列级属性是依赖于具体操作符类（operator class）的。

1
2
3
4
5
6
7
8
9

demo=# SELECT p.name, pg_index_column_has_property('airports_gist_idx', 1, p.name)
FROM unnest(array[
'returnable', 'distance_orderable'
]) p(name);
        name        | pg_index_column_has_property 
--------------------+------------------------------
 returnable         | t
 distance_orderable | t
(2 rows)

GiST 索引允许执行索引仅扫描（Index-only scan），因为叶子节点中保留了完整的索引键值。

正如前文所述，某些操作符类（operator class）提供了用于最近邻搜索的距离操作符。
对于 NULL 值，距离计算结果为 NULL，这种情况下这些值会排在最后返回（类似 B-tree 中的 NULLS LAST 语法）。

然而，对于范围类型（range types）而言，并不存在“距离操作符”（因为它们表示的是线段，也就是线性几何体，而不是面状几何体）。所以，当索引建立在这些类型上时，上述性质会有所不同。

1
2
3
4
5
6
7
8
9
10
11
12
13

demo=# CREATE TABLE reservations(during tsrange);
CREATE TABLE
demo=# CREATE INDEX ON reservations USING gist(during);
CREATE INDEX
demo=# SELECT p.name, pg_index_column_has_property('reservations_during_idx', 1, p.name)
FROM unnest(array[
'returnable', 'distance_orderable'
]) p(name);
        name        | pg_index_column_has_property 
--------------------+------------------------------
 returnable         | t
 distance_orderable | f
(2 rows)

参考书目

1. Egor Rogov, PostgreSQL 14 Internals, https://postgrespro.com/community/books/internals

Gist（Generalized Search Tree，广义搜索树）是一种访问方法(是一个索引框架)，本质上是对支持值之间相对位置关系的数据类型的平衡搜索树的一种泛化。B-tree 只能用于可排序的数据类型，即那些支持比较操作（比如大于、小于等）。对于这类类型，B-tree 的支持是非常高效的。而 Gist 则更为通用，它的操作符类（operator class）允许用户定义任意的数据分布规则，从而控制树的构造方式。因此，Gist 索引可以用于实现不同的数据结构，例如：

• R-tree（二维/多维空间数据）
• RD-tree（集合之间的相似性度量）
• 签名树（类似 Bloom filter 的结构，用于快速过滤模糊匹配，比如文本）

由于 PostgreSQL 的可扩展性，你可以通过实现索引引擎的接口，从零开始创建一个新的访问方法（access method）。但是，除了设计索引逻辑之外，你还需要定义页面布局、高效的锁策略，以及其它底层支持功能。这一切都需要强大的编程能力和大量的实现工作。Gist 简化了这项任务，它处理了所有低层次的技术细节，并提供了搜索算法的基础框架。如果你想让某个新的数据类型支持 Gist 方法，你只需要添加一个新的操作符类（operator class），其中包含大约十几个支持函数（support functions）。与 B-tree 的“简单”操作符类不同，Gist 的操作符类承载了主要的索引逻辑。因此，从这个角度看，Gist 可以被认为是构建新访问方法的一个框架。

每个属于叶子节点的条目（称为“叶子条目”）都包含一个谓词（逻辑条件）和一个指向堆中元组（heap tuple）的引用。索引键（index key）必须满足这个谓词；至于这个键是否直接出现在条目中并不重要。（叶子节点中每一项不是“具体的值”，而是“某种条件”——这个条件是能覆盖实际数据的逻辑表达式。）

每个内部节点中的条目（称为“内部条目”）也包含一个谓词，以及一个指向子节点的引用；子树中所有的数据都必须满足这个谓词。换句话说，内部节点条目的谓词是其所有子节点谓词的“并集”。GiST 的这个重要特性（即“内部节点的谓词是子节点谓词的并集”）实现了类似于 B-tree 中的简单排序（simple ranking）功能（GiST 通过组织谓词的包含关系，实现了类似于 B-tree 按顺序剪枝的搜索效率）。

GiST 树的搜索依赖于 一致性函数（consistency function），它是由操作符类（operator class）定义的一种支持函数。

一致性函数会在某个索引项上被调用，用来判断这个条目的谓词是否与搜索条件一致（即与“索引列的操作符表达式”是否可能匹配）。对于内部节点的条目，一致性函数用于判断是否需要进入对应的子树；对于叶子节点的条目，它用于判断这个索引键是否满足查询条件

搜索从根节点开始，这是树形结构中常见的做法。一致性函数（consistency function）决定哪些子节点需要继续遍历，哪些可以被跳过。然后对选中的每个子节点重复这一过程；与 B-tree 不同，GiST 可能会同时有多个符合条件的子节点。被一致性函数选中的叶子节点条目将作为查询结果返回

GiST 的搜索始终是深度优先的：算法会尽可能尽快到达叶子页面。这种策略对返回前几条结果（Top-N 查询）尤其有利。

在向 GiST 树中插入一个新值时，无法使用一致性函数（consistent()），因为我们需要精确选择一个子节点进行插入。插入逻辑依赖于 penalty() 函数，去评估每个候选子节点“因插入新值而造成的扩展代价”；最终选择 penalty 最小的子节点 来插入。

和B树索引一样，叶子结点没有空间会造成页面分裂（split），split需要两个函数，一个负责在新老节点之间分布数据，另一个函数则对两个谓词进行并集操作，以更新父节点的谓词

随着新值不断插入，已有的谓词会不断扩大，而这些谓词通常只有在页面分裂或整个索引重建时才会被缩小。因此，频繁更新 GiST 索引可能会导致其性能下降

参考书目

1. Egor Rogov, PostgreSQL 14 Internals, https://postgrespro.com/community/books/internals

1. Lehman–Yao B*-Trees

Lehman–Yao构造了一个供并发进程使用的数据结构。该数据结构是 Wedekind提出的 B*-树的一个简单变体（其基础是 Bayer 和 McCreight定义的 B 树）。
Lehman–Yao B*-树定义如下。

1.1 定义

1. Each path from the root to any leaf has the same length, h.
2. 内部节点（非 root、非叶子）至少要有 k + 1 个孩子（sons）。 (k is a tree parameter; 2k is the maximum number of elements in a node, neglecting the “high key,” which is explained below.)
3. root要么是页节点要么至少有两个孩子（sons）
4. 每个node最多有2k+1个孩子（sons）
5. Lehman–Yao B-tree中的所有数据的键（key）都存储在叶子节点中，叶子节点还包含指向数据库记录的指针（每一条记录都与一个 key 对应）。
   非叶子节点包含指针，以及用于沿着这些指针继续查找的 key 值（b+ tree）。

B*-树的节点看起来如图 1 所示。Ki 表示 key 域的实例Pi 表示指针。Pi 可以指向其他节点，或者——在叶子节点的情况下——指向与存储在叶子节点中的 key 值关联的记录。这种安排使得在我们的模型中，叶子节点和非叶子节点的结构基本相同。M 是一个标记，用于指示该节点是叶子节点，它占据了非叶子节点中第一个指针的位置。图 2 显示了一个 B*-树示例。

1.2 Sequencing（顺序规则）

1. 每个节点内部，key 按升序排列。
2. 在 B*-tree 中，有时会在非叶子节点追加一个额外的值，称为 “high key”（见图 3）。
3. 在任意节点 N 中，每个指针 Pi 指向一个子树 Ti（Pi 指向的节点为 Ti 的根）。Ti 中存储的 key 值被 Pi 左右的两个 key （Ki 和 Ki+1）界定。 这就给非叶子节点提供了一组 (pointer, value) 对

   1	key(Ti) ∈ (Ki-1, Ki]

   其中，k0 = -∞（在 N 中物理上不存在），K2k+1 = high key（如果存在），high key 提供了 Pi 指向的子树的上界，因此它也是以 N 为根的子树中所有值的上界。
   叶子节点 定义类似（见图 3）：Ki = 叶子中存储的 key；Pi = 指向对应记录的指针

1.3 Insertion Rule(插入规则)

1. 如果一个叶子节点的条目（entries）少于 2k 个，那么一个新的条目以及指向其对应记录的指针可以直接插入到该节点中。
2. 如果一个叶子节点已有 2k 个条目，则插入新的条目时，需要通过将该节点分裂为两个节点来进行，每个新节点包含原节点一半的条目。新的条目会被插入到这两个节点中的一个（在合适的位置）。由于其中一个节点是新创建的，因此必须在原单节点的父节点中插入一个新的指针。这个新的指针指向新节点；新的键值是对应于原节点拆分后左半部分的键值。此外，需要为这两个新节点分别设置高键（high key）。图 4 展示了一个节点分裂的示例。
3. 对非叶子节点的插入操作与叶子节点完全相同，只是指针指向的是子节点，而不是数据记录。

一个节点（按照上面给出的规则），如果条目数少于 2k，则称其为“安全节点”（就插入操作而言），因为插入可以通过对该节点的简单操作完成。同样，如果一个节点有 2k 个条目，则称其为“非安全节点”，因为必须进行分裂操作。对节点的删除操作也有类似的定义：如果删除可以在节点内完成而不会影响其他节点，则该节点称为“安全节点”；反之，如果删除会影响其他节点，则称为“非安全节点”。也就是说，如果节点的条目数多于 k + 1，则安全；如果恰好有 k + 1 条目，则非安全。

一个简单的例子就足以说明，对 B*-树进行并发操作的简单做法是错误的。
考虑图 5a 所示的 B*-树片段。假设有两个进程：一个搜索值 15，另一个插入值 9。插入操作应当导致树结构修改为图 5b 所示的样子。现在考虑下面这一系列操作：

问题在于，搜索操作首先返回指向 y 的指针（从 X 获得），然后才读取包含 y 的页面。在这两个操作之间，插入操作已经修改了树的结构。

2. Previous Approaches

前面的例子表明，对并发 B 树问题采取简单做法是行不通的：如果不防范并发操作带来的潜在问题，多个进程的操作可能导致结果不正确。为了更好地理解这个问题，我们在此简要概述一些已经提出的其他方法和解决方案。

针对并发 B 树问题的第一个解决方案是由 Samadi 提出的.他的做法是最直接的一种，并且是最早考虑并发问题的方法。该方案简单地使用信号量来独占锁定任何一次树结构修改可能经过的整条路径。这实际上锁定了受影响的最高节点所在的整个子树

Bayer 和 Schkolnick 提出的算法对 Samadi 的方法进行了实质性的改进。他们提出了一种用于 B*-树并发操作的方案；该方案包含一些参数，可以根据所需的并发程度和类型进行设置。
首先，修改操作会对树的上部节点加写者排他锁（writer-exclusion locks）（这种锁只排斥其他写者，而不会阻止读者）。
当需要真正进行修改操作时，会施加独占锁（exclusive locks），大多应用在树的下部节点。
这种对独占锁的稀疏使用提高了算法的并发性能。

Miller 和 Snyder [12] 研究了一种方案，该方案锁定树中一个有界大小的区域。该算法使用先导锁（pioneer locks）和跟随锁（follower locks），以防止其他进程进入当前进程正在修改的树区域。被锁定的区域沿树向上移动，同时执行相应的修改操作.在使用队列管理的锁策略的帮助下，沿树向下移动的读者可以“越过”被锁定的区域，从而避免死锁。这种算法与本文提出的算法的权衡在于：本文的算法锁定树的区域明显更小，但需要对普通的 B-tree 或 B*-tree 结构进行稍微的修改，以便支持并发。

Ellis [6] 提出了一种针对 2-3 树的并发解决方案。文中采用了几种方法以提高并发能力，并且（据称）这些方法可以很容易地推广到 B 树。
该论文应用了两种思想：一是在相反方向上对一组数据进行读写（由 Lamport [11] 提出）；二是允许数据结构暂时出现轻微退化，同时允许进程不必立即完成操作，可以将工作推迟到更合适的时间再执行。

Guibas 和 Sedgewick [6a] 提出了一种针对平衡树的统一“双色框架”（dichromatic framework）。这是一种研究平衡树的简化方法：它将所有平衡树方案归约为“带颜色”的二叉树的特例，并具有概念上的清晰性。这些作者利用他们的框架研究一种自上而下的并发锁定方案，其中包括在沿树向下访问时对“几乎满的”节点进行分裂。我们预计，他们的方案将锁定比我们的方案更多的节点（降低并发性），并且需要略多的存储空间。

另一种针对 B 树并发操作的方法目前正在由 Kwong 和 Wood [10] 进行研究。

3. Blink-Tree for Concurrency

B-link 树是一种在 B*-树基础上修改而成的结构，它在每个节点中增加了一个“链接（link）”指针字段（记作 P2k+1 ——见图 6）。
（B-link-tree 的发音是 “Blink-tree”。）

这个链接指针指向当前节点所在层的下一个节点；只有在该层最右侧的节点中，这个链接指针才是空指针（null）。这样的链接指针定义是自洽的，因为所有叶子节点都位于树的同一层。

因此，在 B-link 树中，同一层的所有节点都被连接成一条链表，如图 7 所示。

Link 指针的目的，是提供一种到达某个节点的额外途径。
当一个节点因为数据溢出而被分裂时，原来的单一节点会被两个新的节点取代。

在分裂后：

• 第一个新节点的 link 指针指向第二个新节点；

• 第二个新节点的 link 指针则保存了原来旧节点的 link 指针内容。

通常情况下，第一个新节点会占用旧节点在磁盘上的同一个物理页面。

设计这个方案的意图是：
因为这两个新节点被 link 指针连接起来，在父节点中的正确指针尚未更新之前，它们在功能上仍然等价于原来的那个单一节点。
Blink-tree 的精确查找与插入算法将在接下来的两个章节中给出。

对于树中的任意一个节点（处于某一层且不是该层的第一个节点），通常会有两种指针指向它：

来自其父节点的“子指针”（son pointer），以及

来自其左兄弟节点的 link 指针。

当一个节点被插入到树中时，这两个指针之中必定有一个会先被创建。
我们规定：在这两个指针中，link 指针必须最先存在。
也就是说，一个节点在树中出现时，可以暂时没有父节点的指针指向它，但必须已经有一个左兄弟指向它的 link 指针。

这种结构依然被定义为一个合法的树结构，因为新的“右兄弟”节点可以通过“左兄弟”到达。（这两个兄弟节点在功能上仍然可以视作一个节点。）

当然，为了保证良好的查找效率，来自父节点的指针必须尽快补上。

Link 指针的优势在于：它会在节点发生分裂时同步建立。
因此，即使针对新节点的常规树指针尚未全部更新完毕，link 指针仍可作为一种“临时修补”机制，使并发操作保持正确性。

当查找键大于节点的最大键值（由 high key 标识）时，这表明树结构已经发生变化，此时应通过 link 指针继续访问右兄弟节点。
虽然这种方式略低效一些（因为需要额外一次磁盘读取来跟随 link 指针），但它仍然是到达目标叶子节点的正确路径。

由于节点分裂本身属于例外情况，link 指针的实际使用频率应该非常低。

Blink-tree 结构的另一个优点是：在对树进行顺序遍历时，link 指针可以用于快速按“按层次优先（level-major）”的顺序检索树中的所有节点，或者，例如，只检索所有叶子节点。

4. THE SEARCH ALGORITHM

4.1 算法示意图（Algorithm Sketch）

要在树中查找一个值 v，搜索过程从根节点开始，沿树向下比较 v 与每个节点中的键值。在每个节点中，比较键值后，决定沿节点中哪条现有指针继续向下搜索，指示应沿该指针前往下一层节点，或直接到达叶子（记录）节点。

如果搜索过程中检查某个节点时，发现该节点中的最大值小于 v，则可以推断出当前节点发生了一些变化，而这些变化在搜索检查其父节点时尚未反映到父节点中。

这意味着当前节点已经被分裂成两个（或更多）新的节点。
此时，搜索必须纠正其在树中的位置错误：不再按照普通的父节点子指针（son pointer）前进，而是沿新分裂节点的 link 指针继续搜索。

搜索过程最终会到达 v 应该所在的叶子节点（如果 v 存在的话）。此时，该节点要么包含 v，要么不包含 v 且节点中的最大值大于 v。
因此，该算法能够正确地判断 v 是否存在于树中。

4.2 算法

搜索（Search）
该过程用于在树中查找一个值 𝑣。如果 𝑣 存在于树中，过程结束时：𝐴包含包含 𝑣 的节点 𝑡
包含指向与 𝑣 关联的记录的指针；如果 𝑣 不存在于树中，𝐴 将包含 𝑣 如果存在的话应该所在的节点。

1
2
3
4
5
6
7
8
9

Search(v):
    ...
    if v exists:
        A = 节点页 containing v
        t = 指向 v 的记录
    else:
        A = 节点页 where v would be
        t = null

下文算法中使用的符号在第 2 节中定义。
在此过程中，我们使用了一个辅助操作 scannode，其定义如下：

x <- scannode(u, A) denotes the operation of examining the tree node in memory block A for value u and returning the appropriate pointer from A (into x).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

procedure search(u)
current <- root;
A <- get(current);
while current is not a leaf do 
begin
  current <- scannode(u, A);
  A <- get(current) 
end;

while t <- scannode(u, A) = link ptr of A do
begin
  current + t ;
  A <- get(current)
end;

if v is in A then done “success” else done “failure”

请注意，这种搜索过程非常简单，其行为与非并发搜索完全相同，将 link 指针与其他指针同等对待。

还要注意，该过程不进行任何形式的加锁。
这与传统的数据库搜索算法形成对比（例如 Bayer 和 Schkolnick [3] 所述），在那些算法中，所有搜索操作都会对它们访问的节点进行读锁。

5. THE INSERTION ALGORITHM

5.1 算法示意图（Algorithm Sketch）

要在树中插入一个值 𝑢 我们执行的操作与前面描述的搜索过程类似。从根节点开始，沿树向下扫描，直到到达应该包含 𝑢 的叶子节点。同时，我们在下降过程中记录每一层中被访问过的最右节点。沿树的下降过程实际上就是在搜索 𝑢 的正确插入位置（比如称该节点为节点 𝑎 ）。

将值 u 插入叶子节点时，可能需要对该节点进行分裂（当节点不安全时）。
在这种情况下，我们对节点进行分裂（如图 8 所示），用两个新节点 a’（a 的新版本，写回同一磁盘页面）和 b’ 替换原来的节点 a。节点 a’ 和 b’ 的内容与原节点 a 相同，只是增加了值 u。随后，我们沿着先前记录的搜索路径回溯树的上层，在叶子节点的父节点中插入新节点 b’ 的条目以及 a’ 的新 high key。

死锁的避免是由锁定方案的良序性（well-ordering）所保证的，如下所示。
需要注意的是，当我们沿树向上回溯时，由于节点可能被分裂，我们必须插入新指针的节点可能并不是下降过程中经过的那个节点。换句话说，我们在下降过程中使用的旧节点可能已经被分裂；此时，正确的插入位置就在原预期插入位置右侧的某个节点。我们通过 link 指针 来找到这个节点。

5.2 算法

在下文的算法中，有些过程被视为原语操作（就像上文的 scannode 一样），因为它们容易实现，并且其具体操作对本文的目的而言并不重要。例如：

A <- node.insert (A, w, v) denotes the operation of inserting the pointer w and the value v into the node contained in A.
u <- allocate(2 newpage for B) denotes the operation of allocating a new page on the disk. The node contained in B will be written onto this page, using the pointer u.
“A, B <- rearrange old A, adding ..” denotes the operation of splitting A into two nodes, A and B, in core.

插入（Insert）。该算法负责将一个值 v（以及其关联的记录）插入到树中。当算法结束时，值 v 已成功插入到树中，并且在必要的情况下，算法会在从叶子向上回溯的过程中对相应的节点进行分裂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

procedure insert(v)
initialize stack;
current <- root;
A <- get(current);
while current is not a leaf do
begin
  t <-  current;
  current <- scannode( v, A);
  if new current was not link pointer in A then
    push(t);
  A <- get(current);
end;
lock(current);
A <- get(current);
move.right;
if v is in A then stop “v already exists in tree”;
w <- pointer to pages allocated for record associated with v; 
Doinsertion:
if A is safe then
begin
  A <-  node.insert(A, w, v); 
  put(A, current); 
  unLock(current);
end else begin
  u <- allocate(1 new page for B);
  A, B <- rearrange old A, adding v and w, to make 2 nodes,
    where (link ptr of A, link ptr of B) <- (u, link ptr of old A);
  y <- max value stored in new A;
  put(B, u)
  put(A, current); 
  oldnode <- current;
  v <- Y;
  w <- u;
  current <- pop(stack); 
  lock(current);
  A <- get(current); 
  move.right; 
  unlock(oldnode);
  goto Doinsertion
end

Move.right. This procedure, which is called by insert, follows link pointers at a given level, if necessary.

1
2
3
4
5
6
7
8

procedure move.right
while t <- scannode(u, A) is a link pointer of A do
begin
  lock(t); 
  unlock(current); 
  current <- t;
A <- get(current); 
end

需要注意的是，该过程在向上回溯树时是 逐层进行的。此外，同时最多只会锁定三个节点，而这种情况发生的频率相对较低：仅在插入分裂节点的指针时，需要沿 link 指针向右移动 的情况下才会出现。此时，被锁定的节点包括：

• 分裂节点的原始左半部分

• 分裂节点上一层的两个节点

在插入沿右链移动的过程中需要锁定它们。

与传统方法相比（即只有在确定节点为安全节点时才释放锁），这种做法在 锁粒度和并发性能上都有显著改进。

该算法的正确性依赖于以下事实：树结构的任何变化（即任何节点的分裂）都会伴随一个 link 指针。节点分裂时，条目总是被移动到树的右侧，在右侧的新节点可以通过 link 指针被访问到，从而保证树的结构在并发操作下仍然可达且正确。

具体来说，对于任何层级的一个对象（与某个值相关联），我们总能大致知道它的正确插入位置，即我们在该层搜索时经过的“记录节点”。如果该对象的正确插入位置发生了移动，这种移动方式是可预知的：也就是节点分裂向右，留下的 link 指针使得搜索或插入操作仍然能够找到它。因此，从旧的“预期”插入位置开始，始终可以访问到对象的正确插入位置。

6 CORRECTNESS PROOF

为了证明系统的正确性，我们需要证明以下两个命题对每个进程都成立：

1. 该进程不会发生死锁（定理 1）；
2. 当进程终止时，它已经正确地完成了所需的操作。
   更具体地说：

• 所有磁盘操作都保持树结构的正确性（定理 2）
• 除正在进行修改的进程之外，所有其他进程看到的树都是一致的（交互定理 3）。

6.1 无死锁性（Freedom from Deadlock ）

首先，我们开始证明系统不存在死锁。
为此，我们对节点施加一个顺序：跨层从下到上、同层从左到右。下面的引理（Lemma：一种 辅助性结论，用于证明后续更大、更重要的定理（Theorem））对这一点进行了严格定义。
引理 1 插入操作对节点加锁遵循一个良序（well-ordering：严格定义的、有序的顺序关系）关系
证明 考虑在树的节点集合上定义如下顺序关系（<）：

1. 在任意时刻 t，如果两个节点 a 和 b 与树根的距离不同（不在同一层级），那么当且仅当 b 离树根更近（处于更高层级）时，我们称 a < b。
2. 如果 a 和 b 与树根的距离相同（在同一层级），那么当且仅当 b 能通过从 a 开始沿着一条或多条链接指针到达（即 b 在 a 的右侧）时，我们称 a < b。

通过检查插入算法我们可以看到：如果在时间 t₀ 时 a < b，那么在所有 t > t₀ 的时间点都仍然有 a < b。因为节点创建过程只是把一个节点 x 分裂成两个新节点 x′ 和 x″，并且满足 x′ < x″，而且

1

y<x⟺y<x′

和

1

x<y⟺x′′<y

因此，这些节点形成了一个良序关系，插入者按照良序对节点加锁。一旦在某个节点上加锁，它不会再对该节点之下的任何节点加锁，也不会对同一层中位于左侧的节点加锁。
因此，插入者按照给定的良序对节点加锁。证毕。
由于插入者是唯一对节点加锁的过程，我们可以立即得到以下定理。

定理 1：无死锁性。 给定的系统不会产生死锁。

6.2 树结构修改的正确性

为了确保树结构的完整性，我们必须检查所有修改树结构的操作。首先，需要注意的是，树结构的修改只能通过 “put” 操作 来完成。插入过程中算法中有三个地方会执行 put 操作：

1. 对安全节点重写时使用 “put(A, current)”。
2. 对不安全节点的最右节点使用 “put(B, u)”。通过该操作，我们写入由节点分裂形成的两个新节点中的第二个节点。
3. 对不安全节点使用 “put(A, current)”。这里写入的是两个新节点中的第一个（最左节点）。实际上，我们重写了树中已存在的页面（节点），并修改该页面的链接指针，使其指向由 “put(B, …)” 写入的新节点。

注意，在算法中（针对不安全节点），“put(B, u)” 紧接在 “put(A, current)” 之前执行。我们将在下面的引理中证明，这种顺序实际上将两个 put 操作简化为本质上的一次操作。

引理 2. 操作 ‘put(B, u); put(A, current)’ 相当于对树结构的一次修改。
证明. 假设这两个操作分别写入节点 b 和 a。在执行 “put(B, u)” 时，没有其他节点指向正在写入的节点 b，因此该 put 操作对树结构没有影响。现在，当执行 “put(A, current)” 时，该操作修改了 current 指向的节点（节点 a）。修改内容包括将节点 a 的链接指针指向 b。此时，b 已经存在，并且 b 的链接指针指向与 a 的旧版本相同的节点。这样就实现了同时修改 a 并将 b 引入树结构。证毕。

定理 2. 所有 put 操作都能正确地修改树结构。
证明
case 1： 对安全节点执行 “put(A, current)”。该操作只修改树中一个已加锁的节点，因此树的正确性得到保持。
case 2： 对不安全节点执行 “put(B, u)”。该操作不会改变树结构。
case 3： 对不安全节点执行 “put(A, current)”。根据引理，该操作既修改了当前节点（比如 a），又将另一个节点（比如 b，通过 “put(B, u)” 写入）引入树结构。与情况 1 类似，节点 a 在执行 “put(A, current)” 时已加锁。本例的区别在于该节点是不安全的，需要分裂。但根据引理，我们可以通过一次操作完成，保持树结构的正确性。证毕

6.3 正确的交互

我们还需要证明，无论插入过程对树进行何种修改，其他进程仍能正确操作。
定理 3：交互定理。 插入过程的操作不会破坏其他进程操作的正确性。

为了证明该定理，我们首先考虑搜索过程与插入操作的交互情况，然后考虑两个插入过程的交互情况。一般来说，为了证明插入者的操作不会破坏其他进程的正确性，我们需要考虑该进程相对于该操作的行为。在所有情况下，该操作都是原子的。

假设插入者在时间 t0 对节点 a 执行一次 “put” 操作。考虑另一个进程在时间 t′从磁盘读取节点 a 的情况。由于假设 “get” 和 “put” 操作是不可分割的，要么 t′<t0​，要么 t0​ < t′。我们将在下面的引理中证明，后一种情况不会产生问题。

引理 3
如果进程 𝑃 在某个时间 𝑡′ > 𝑡0 读取节点 𝑎，其中 𝑡0 是插入进程 I 修改节点 𝑎 的时间，那么这一修改不会影响进程 𝑃 的正确性。

证明. 考虑进程 P 通过节点 a 的路径。进程 P 在到达节点 a 之前所经过的路径不会被插入进程 I 改变。此外，根据上面的定理 2，进程 I 对树结构所做的任何修改都会产生一个正确的树（well-ording）。因此，进程 P 在 a 节点开始的路径（在时间 t>t′t > t’t>t′）将无论修改如何都能正确执行。证毕。

为了便于将定理的证明分解成不同情况，这里列出在一个节点上对一个值可能执行的三种插入类型。

类型 1. 简单地将一个值及其关联指针添加到节点中。当节点是安全的（safe）时发生这种类型的插入。
类型 2. 对节点进行分裂，并将插入值放入分裂节点的左半部分。左半部分仍然是原来被分裂的节点。
类型 3. 类似地，对节点进行分裂，并将插入值放入分裂节点的右半部分。右半部分是新分配的节点。

现在我们开始定理的证明。我们注意到，定理的正确性涉及几个方面（情况），并将分别证明这些情况。

证明. 根据引理 3，只需考虑搜索或插入进程 𝑃 在插入进程 𝐼 修改节点之前开始读取该节点的情况。

第 1 部分. 考虑插入进程 I（在时间 t0 修改节点 n）与搜索进程 S（在时间 t′< t0读取节点 n）之间的交互。记 n′ 为修改后的节点。（本节的论证同样适用于另一插入进程 I′与进程 I 交互的情况，且 I′正在执行搜索。）需要考虑的操作顺序是：S 读取节点 n；然后 I 将节点 n 修改为 n′；然后 S 根据 n 的内容继续搜索。
考虑三种插入类型：

第2部分。接下来我们考虑插入进程 I 与另一个插入进程 I’ 的交互情况。进程 I’ 可能正在搜索用于插入的正确节点、回溯到另一层，或者实际尝试将一个值/指针对插入节点 n。如果 I’ 正在搜索一个用于插入值/指针对的节点，则该搜索行为与普通搜索进程完全相同。因此，证明与上文针对搜索进程的证明相同。

第3部分。如果 I’ 因为下层节点分裂而需要回溯上行树，则 I’ 需要回到上层以便将指针插入到分裂节点的新半部分。

• 回溯是使用在下降过程中记录在栈中的信息完成的。
• 在每一层，被压入栈的节点是该层被检查过的最右侧节点。
• 考虑在将某个节点 n 压入栈和回溯时再次访问该节点之间可能发生的情况：该节点可能已经分裂过一次或多次，这些分裂会在节点 n 的“右侧”产生新的节点。
• 由于节点 n 右侧的所有节点都可以通过 link 指针访问，因此插入算法能够找到适当的位置插入值。

第四部分。如果进程 I’ 试图在节点 n 上进行插入，它会尝试锁定该节点。但进程 I 已经持有节点 n 的锁。最终，I 会释放该锁，I’ 再锁定该节点并将其读入内存。根据上面的引理，该交互是正确的，因为 I’ 的读取发生在 I 的插入之前。节点 n 要么就是插入的正确位置——此时 I’ 会执行插入；要么搜索必须沿节点的 link 指针访问其右兄弟。

LiveLock

我们在此指出，我们的算法并不能完全避免活锁(LiveLock)的可能性（即某个进程无限运行）。
如果一个进程因为不断跟随其他进程创建的 link 指针而无法终止，就可能发生这种情况。
然而，根据以下观察，我们认为在实际实现中这种情况极不可能成为问题。
在多处理器系统中，如果该进程运行在相对非常慢的处理器上，这种情况可能发生。

(1) 在我们所知的大多数系统中，处理器的运行速度大致相当。
(2) 在 B 树中，节点的创建和删除只占很小的比例，因此即使是较慢的处理器，也不太可能因节点的创建或删除而遇到困难（也就是说，它只需要跟随少量的 link 指针）。
(3) 在树的任意给定层上，只能创建固定数量的节点，从而限制了较慢处理器需要“追赶”的量。

我们认为，这些想法结合起来可以使实际系统中进程发生活锁的概率几乎为零（除非涉及的进程速度差异极大）。模拟可以帮助我们验证系统在“合理”条件下能够正常工作，并帮助确定进程相对速度的可接受范围。

在进程速度确实存在极大差异的情况下，我们可能会引入一些额外机制来防止活锁。实现这种机制有多种选择。本文不讨论避免活锁的完整方法，但其中一种方法可能是为每个进程分配优先级，优先级可能基于进程的“存在时间”。这将保证每个进程最终会终止，因为它最终会成为最“老”的进程，从而成为拥有最高优先级的进程。

7. DELETION

一种处理删除操作的简单方法是允许叶子节点中的条目少于 K 个。对于非叶子节点则不需要这样做，因为删除操作仅会移除叶子节点中的键；非叶子节点中的键仅作为其对应指针的上界，它在删除过程中并不会被移除。

因此，为了从叶子节点中删除一个条目，我们对该节点执行的操作与插入操作（尤其是插入情况 1）非常类似。具体来说，我们首先搜索出值 u 所在的节点，然后锁定该节点，将其读入内存，对内存中的副本删除值 u 后再将节点重写回磁盘。有时，这样会导致节点中条目数量少于 K。
该算法的正确性证明与插入操作类似。例如，死锁自由性的证明非常简单，因为删除操作只需要锁定一个节点。对于操作的正确性，如果一个搜索进程在删除值 u 之前读取了节点，它仍然会报告节点中存在 u，这与序列化调度（搜索操作先于删除操作执行）是一致的，因此搜索结果仍然正确。

我们刚描述的这种删除处理方法比需要处理节点下溢（underflow）和合并（concatenation）的方案要简单得多。在假设插入操作发生频率高于删除操作的情况下，这种方法几乎不需要额外存储空间。

当然，在删除操作过多导致树节点存储利用率过低的情况下，可以执行批量重组（batch reorganization）或者全树锁定的下溢操作（underflow operation）来重新组织树结构，以保证空间的合理利用。

8. 锁定效率（LOCKING EFFICIENCY）

显然，在并发方案中，至少需要一个锁，以防止不同进程同时更新同一个节点。

上文给出的插入操作方案，在任何时刻对任意进程使用的锁数量最多是一个常数（最多三个）。这种情况仅在特定情况下发生：当插入进程刚刚向某个节点（叶子节点或非叶子节点）插入条目，并导致该节点分裂时。在回溯树的过程中，为了向新分裂节点的一半插入指针，插入进程发现旧的父节点已经不再是正确的插入位置，因此必须沿包含父节点的这一层节点进行链式查找，以找到正确的插入位置。在整个操作过程中，同时锁定三个节点。

在每个节点容量较大的 B*-树中，这种类型的锁定操作发生的频率非常低。因此，除非有大量并发进程运行，否则该结构的锁冲突概率极低。

这种系统的行为可以通过模拟进行量化，模拟参数包括并发进程数量、每个节点的容量，以及搜索、插入和删除操作的相对频率。这样的模拟不仅可以评估当前方案的性能，也可用于与其他并发控制方案进行比较。

9. SUMMARY AND CONCLUSIONS

B 树在维护大型数据库时被发现非常有用。并发操作这样的数据具有明显优势，因为它允许多个用户同时共享数据；而且在大规模数据库中，用户的数据需求通常不会产生冲突，因此并发访问是可行的。

本文给出了一个算法，可以在 B 树的一种变体上执行正确的并发操作。该算法的特点是任意进程在任何时刻只需使用少量常数个锁。算法本身非常直接，其流程与顺序执行的算法仅有轻微差别。（可以通过模拟来量化本文算法与顺序算法或其他并发算法相比的效率提升。）

这一性能的实现依赖于对数据结构的一个小改动，使得当一个进程的位置因其他进程的操作而失效时，能够进行恢复（参见 [8]）。

我们希望将这项工作扩展到更通用的并发数据库操作方案。理想的方案应当仅需对数据结构和顺序算法做极少量修改，同时能够保证当其他进程对数据结构做出改变使某进程的操作失效时，该进程能够正确恢复。

另一条未来研究方向是对算法的“并行化”：研究将一个（已充分理解的）顺序算法转换为并发算法的通用方法。目标是尽可能充分利用问题的并发特性，同时保证算法的正确性不受影响。

准备表数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

test=# create table users(id int generated always as identity primary key, name text);
CREATE TABLE

test=# select oid, relname, relfilenode from pg_class where relname = 'users';
  oid  | relname | relfilenode 
-------+---------+-------------
 40980 | users   |       40980

test=# select c.oid, c.relname, i.indisprimary from pg_class c join pg_index i on c.oid = i.indexrelid where i.indrelid = 'users'::regclass and i.indisprimary;
  oid  |  relname   | indisprimary 
-------+------------+--------------
 40986 | users_pkey | t
(1 row)

test=# select lp,lp_len,t_data from heap_page_items(get_raw_page('users', 0));
ERROR:  block number 0 is out of range for relation "users"
test=# select * from bt_page_items('users_pkey',1);
ERROR:  block number 1 is out of range
test=# ^C

insert values

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

test=# insert into users(name) values('jeffrey');
INSERT 0 1
test=# select lp,lp_len,t_data from heap_page_items(get_raw_page('users', 0));
 lp | lp_len |           t_data           
----+--------+----------------------------
  1 |     36 | \x01000000116a656666726579
(1 row)

test=# select * from bt_page_items('users_pkey',1);
 itemoffset | ctid  | itemlen | nulls | vars |          data           | dead | htid  | tids 
------------+-------+---------+-------+------+-------------------------+------+-------+------
          1 | (0,1) |      16 | f     | f    | 01 00 00 00 00 00 00 00 | f    | (0,1) | 
(1 row)

test=# select *  from page_header(get_raw_page('users', 0));
    lsn     | checksum | flags | lower | upper | special | pagesize | version | prune_xid 
------------+----------+-------+-------+-------+---------+----------+---------+-----------
 0/03F5E7A0 |        0 |     0 |    28 |  8152 |    8192 |     8192 |       4 |         0
(1 row)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

test=# insert into users(name) values('Ethan');
INSERT 0 1
test=# select *  from page_header(get_raw_page('users', 0));
    lsn     | checksum | flags | lower | upper | special | pagesize | version | prune_xid 
------------+----------+-------+-------+-------+---------+----------+---------+-----------
 0/03F62810 |        0 |     0 |    32 |  8112 |    8192 |     8192 |       4 |         0
(1 row)

test=# select lp,lp_len,t_data from heap_page_items(get_raw_page('users', 0));
 lp | lp_len |           t_data           
----+--------+----------------------------
  1 |     36 | \x01000000116a656666726579
  2 |     34 | \x020000000d457468616e
(2 rows)

test=# select * from bt_page_items('users_pkey',1);
 itemoffset | ctid  | itemlen | nulls | vars |          data           | dead | htid  | tids 
------------+-------+---------+-------+------+-------------------------+------+-------+------
          1 | (0,1) |      16 | f     | f    | 01 00 00 00 00 00 00 00 | f    | (0,1) | 
          2 | (0,2) |      16 | f     | f    | 02 00 00 00 00 00 00 00 | f    | (0,2) | 
(2 rows)

Prerequisites

To build OceanBase from source code, you need to install the C++ toolchain in your development environment first. If the C++ toolchain is not installed yet, you can follow the instructions in this document for installation.

1

apt-get install git wget rpm rpm2cpio cpio make build-essential binutils m4

Clone

Clone the source code to your development machine:

1

git clone https://github.com/oceanbase/oceanbase.git

Build

Build OceanBase from the source code in debug mode or release mode:

Debug mode

1

bash build.sh debug --init --make

Release mode

1

bash build.sh release --init --make

Run

Now that you built the observer binary, you can deploy an OceanBase instance with the obd.sh utility:

1
2

./tools/deploy/obd.sh prepare -p /tmp/obtest
./tools/deploy/obd.sh deploy -c ./tools/deploy/single.yaml

You can check the mysql_port in ./tools/deploy/single.yaml file to see the listening port. Normally, if you deploy with the root user, the OceanBase server will listen on port 10000, and the examples below are also based on this port.

Connect

You can use the official MySQL client to connect to OceanBase:

1

mysql -uroot -h127.0.0.1 -P10000

Alternatively, you can use the obclient to connect to OceanBase:

1

./deps/3rd/u01/obclient/bin/obclient -h127.0.0.1 -P10000 -uroot -Doceanbase -A

Shutdown

1

./tools/deploy/obd.sh destroy --rm -n single

SSTables：Sorted String Table ： 每个segment文件中key值是有序（根据key值排序）并且唯一的。sstable有如下优势：

• merge简单高效
• 因为有序，不需要维护所有记录的索引，可以是稀疏索引
• 因为有序，可以按block进行压缩同时维护索引，除了降低磁盘占用以外，还可以降低磁盘io

构建和管理SSTables

因为写入是无序的，所以我们需要在内存中借助于红黑树或者avl树等数据结构来保证：任意写入，有序读取.

构建步骤如下:

1. 当写入发生时，将写入的key-value加入内存平衡树（如红黑树）中，称为”memtable”
2. 当memtable增大到一定阈值后（a few megabytes），将memtable写入磁盘生成一个SSTable文件。新写入的SSTable成为数据库中最新的segment文件。 写入SSTable到磁盘时，写入可以继续写入新的memtable
3. 读请求来时，优先在memtable中查找，然后按顺序从新到老查找磁盘上的segment文件
4. 随着时间的推移，可以后台启动合并和压缩segment文件、丢弃或者覆盖掉老的文件

这种机制工作的很好，但是存在一个问题，如果数据库宕机了，内存中的memtable还没有来得及写入磁盘，可能造成数据丢失。可以通过一个单独的log文件来记录所有的操作，这个log的作用只是用于宕机恢复memtable，每当memtable被写入磁盘，相应的log文件就可以被丢弃了

用SSTables构建LSM-tree

LSM-Tree用于 LevelDB 和 RocksDB、嵌入其他应用的key-value存储引擎。参考：Google’s Bigtable paper

SSTables + log = “Log-Structured Merge-Tree ”

LSM-tree两种文件管理策略：

1. Size-Tiered Compaction（STC）

   • 基本思想
     “当某一层（或同一大小区间）的 SSTable 文件数达到阈值时，将它们合并成一个更大的文件。”
     也就是说，不是按“层级”，而是按“文件大小”来触发 compaction。

   • 结构示意
     MemTable → SSTable

   • 优点

     • 写放大低
       每条数据在被 flush 后只会参与少数几次合并；每次合并是“几块 → 一块”，合并次数较少。
     • 写入吞吐高
       flush 后直接落地；合并是批量异步进行；对写性能非常友好。

   • 缺点

     • 读放大高
       同一 key 可能存在于多个 SSTable 中；读时需要查多个文件（除非借助 Bloom Filter）。
     • 空间放大高
       合并不够积极；多个旧版本的数据同时存在；临时文件和重复 key 较多。

   • 应用场景
     适合写多读少的场景；比如日志系统、时间序列数据库（TSDB）、写入密集的监控系统Cassandra 默认采用 STCS（Size-Tiered Compaction Strategy）

2. Level Compaction（LC）
   这种策略是 LevelDB、RocksDB 采用的，更现代化。又叫 leveled compaction 或 分层压实。

   • 基本思想：
     数据被组织成多个层级（Level 0, Level 1, Level 2…），每一层都有固定大小的空间限制，同一层内文件的 key 范围 互不重叠。

   • 层次结构：
     Level 0: 多个小 SSTable，key 范围可能重叠。
     Level 1: 较大文件，key 范围不重叠。
     Level 2: 更大文件，key 范围不重叠。
     …

   • Compaction 逻辑：
     当某一层（如 Level 0）容量超标；就选择一个 SSTable（或一组）与下一层（如 Level 1）中 key 范围重叠的文件；合并、去重、重写为更大的 SSTable，放入下一层。

   • 优点

     • 读性能优异
       除 Level 0 外，其余层内文件 key 范围不重叠；读取某个 key 只需查找每层最多一个文件；查找代价从 O(n_files) 降到 O(levels)。
     • 空间利用率高
       去重及时；每层占用空间接近固定比例；不容易膨胀。

   • 缺点

     • 写放大高
       每条数据会多次参与合并（从 L0 → L1 → L2…）；每次都要重写到下一层； 磁盘写入量是原始写入的数倍。
     • Compaction 代价大
       大文件之间的合并非常消耗 I/O；RocksDB 必须限制后台 compaction 线程数量。

   • 应用场景
     适合读写比较均衡、查询多的系统；比如 RocksDB、LevelDB、TiKV、ClickHouse 的部分引擎。

性能优化

当查找的key在数据库中不存在时，LSM-Tree算法可能会变慢：在你确认key不存在之前，你需要检查所有memtable，所有sstable对应的磁盘文件。可以使用bloom filters：它可以检查key不在数据库中（每个sstable固化时，生成对应的bloom filter文件）