1 | wsl #如果没有安装，会安装 |
1 | PS C:\Users\gujinfei> wsl -l -v |
进入： %UserProfile% 目录，编辑或者增加 .wslconfig 文件
1 | [wsl2] |
1 | sudo apt install -y build-essential curl pkg-config libssl-dev |
1 | ssh-keygen -t ed25519 -C "[email protected]" |
本文为英文技术博客《Don’t give Postgres too much memory》的中文翻译。
原文作者：Tomas Vondra
原文链接：https://vondra.me/posts/dont-give-postgres-too-much-memory/
本文接近原文直译，仅做结构整理与术语统一，所有观点归原作者所有。
我时不时会被拉去排查一些与批处理（batch processing）相关的问题。
最近越来越常见的一种情况是：这些批处理进程会使用非常大的内存限制，尤其是：
maintenance_work_memwork_mem我猜不少 DBA 的思路是：
“内存越大越好。”
但他们往往没有意识到，这样做实际上可能会明显拖慢性能。
我用一个在测试 GIN 索引并行构建修复 时遇到的例子来说明这个问题。
这个 bug 本身并不复杂，也不算特别有意思，但它需要一个相当高的 maintenance_work_mem 才能复现 —— 最初的报告里使用了 20GB。
为了验证修复是否有效，我在：
maintenance_work_mem 设置组合下，反复执行 CREATE INDEX。
本来的目标只是检查是否还会失败，但我同时也记录了执行时间，并将结果画成了一张图。
测试运行在 Azure 上的一台 D96v4 实例：
这意味着：
并行化确实带来了明显收益：
使用 2 个 worker（包括 leader）
→ 性能提升约 1.8 倍
→ 接近理想加速比（因为索引构建的最后阶段仍然是串行的）
随着 worker 数量继续增加：
这完全符合预期。
真正令人意外的是图中展示的另一个趋势：
maintenance_work_mem越大，索引构建反而越慢。
具体表现为：
为什么会这样？
这很可能是多种因素共同作用的结果。
下面我解释两个我认为最重要的原因：
系统中的内存并不是“同一种速度”。
在 CPU 内部，存在一小块极快的缓存（L3 Cache），访问延迟非常低。
但这部分内存通常只有 32MB～128MB。
相比之下：
在索引构建过程中，通常会经历以下流程：
对于 GIN 索引 来说，这一步会把条目插入到一个哈希表中，这意味着：
大量随机内存访问
一旦这个哈希表的大小超过 L3 Cache，CPU 就不得不频繁访问主内存。
大致的访问代价是：
也就是说，慢了一个数量级。
因此：
往往是更优的策略。
即使需要处理更多批次，总体上仍然可能更快。
推荐阅读：
Ulrich Drepper，《What Every Programmer Should Know About Memory》（2007）
虽然年代久远，但内存层级的基本原理至今没有变化。
除了 CPU Cache，还有操作系统层面的因素。
当 GIN 的哈希表超过 maintenance_work_mem 限制时，数据会被写入临时文件。
这些文件不需要持久化保证，因此写入时只进入 page cache。
Linux 内核通过两个阈值控制脏页数量：
vm.dirty_background_ratio vm.dirty_ratio 理想状态下：
后台回写足够快，永远不会触及
vm.dirty_ratio
问题在于：
内核是否有“时间”去完成这些回写。
假设构建哈希表需要累积 8GB 数据，用时 1 分钟：
显然后者对系统更加友好。
以上所有分析，**同样适用于 work_mem**。
唯一的区别在于：
maintenance_work_mem CREATE INDEX、VACUUM 等）work_mem hash join、hash aggregate、sort 等）但底层原理完全一致：
我并不知道 maintenance_work_mem 或 work_mem 的“最佳值”是多少，这也不是这篇文章的重点。
重点在于：
盲目把内存参数调得很大，可能会显著伤害性能。
我的建议是：
pg_stats 视图中的 n_distinct 字段表示某一列中不同取值（distinct values）的数量。
如果 n_distinct 为负数，其绝对值表示该列中不同取值所占的比例，而不是实际的不同值个数。例如，−1 表示该列中所有值都是唯一的；−3 表示平均而言，每个不同的值大约出现在 3 行中。当估计的不同值数量超过表中总行数的 10% 时，分析器（analyzer）会使用这种“比例”的表示方式。
如果预期数据是均匀分布的，则会直接使用不同值的数量。例如，在估算 column = expression 这种条件的基数（cardinality）时，如果在规划阶段无法确定表达式的具体取值，查询规划器会假设该表达式可以以相同的概率取列中的任意一个值。
1 | => EXPLAIN SELECT * |
虽然理论学家对此不以为然，但 NULL 值在关系型数据库中仍然扮演着重要角色：它提供了一种方便的方式来表示某个值要么未知，要么不存在。
然而，特殊的值需要特殊处理。除了理论上的不一致性之外，还有许多实际问题需要考虑。常规的布尔逻辑被三值逻辑取代，因此 NOT IN 的行为可能出乎意料。对于 NULL 值应该被视为大于还是小于普通值也不明确（因此存在用于排序的 NULLS FIRST 和 NULLS LAST 子句）。是否需要在聚合函数中考虑 NULL 值也并不十分明显。严格来说，NULL 根本不是一个值，因此优化器在处理它们时需要额外的信息。
除了在表级收集的最基本的统计信息之外，分析器还会为表的每一列收集统计信息。这些数据存储在系统目录的 pg_statistic 表中，但你也可以通过 pg_stats 视图访问，这个视图以更方便的格式提供这些信息。
列级统计信息中包括 NULL 值的比例；在分析过程中计算，并以 null_frac 属性表示。
例如，当我们查询尚未起飞的航班时，可以依赖它们的起飞时间未定义（NULL）这一事实：
1 | => EXPLAIN SELECT * FROM flights WHERE actual_departure IS NULL; |
为了估算结果，优化器将表的总行数乘以 NULL 值的比例：
1 | => SELECT round(reltuples * s.null_frac) AS rows FROM pg_class |
以下是实际的行数：
1 | SELECT count(*) FROM flights WHERE actual_departure IS NULL; |
基本的 relation-level统计信息存储在系统目录的 pg_class 表中，包含以下数据：
下面是 flights 表对应的这些值：
1 | => SELECT reltuples, relpages, relallvisible |
如果查询未施加任何过滤条件，则 reltuples 的值将作为基数（cardinality）估计：
1 | => EXPLAIN SELECT * FROM flights; |
统计信息是在表分析（无论是手动还是自动）过程中收集的。此外，由于基本统计信息至关重要，这些数据也会在其他操作中计算（如 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 | => SELECT reltuples, relpages, relallvisible FROM pg_class WHERE relname = 'flights_copy'; |
当 reltuples = −1 时，用于区分尚未分析的表和真正没有行的空表。
表创建后，很可能会马上插入一些行。由于优化器无法获知表的当前实际状态，它会假设该表包含 10 个页：
1 | => EXPLAIN SELECT * FROM flights_copy; |
行数的估算是基于单行的大小（在执行计划中显示为 width）。行宽通常是在分析过程中计算的平均值，但由于此时尚未收集任何统计信息，这里只是根据列的数据类型做出的近似估算。
现在，我们从 flights 表拷贝数据同时完成分析：
1 | => INSERT INTO flights_copy SELECT * FROM flights; INSERT 0 214867 |
收集到的统计信息反映了实际的行数（表足够小，分析器可以对所有数据收集统计信息）：
1 | => SELECT reltuples, relpages, relallvisible FROM pg_class WHERE relname = 'flights_copy'; |
relallvisible 值用于估算 index-only scan 的成本。该值由 VACUUM 更新：
1 | => VACUUM flights_copy; |
现在我们将行数翻倍，但不更新统计信息，检查查询计划中的基数估算：
1 | => INSERT INTO flights_copy SELECT * FROM flights; |
尽管 pg_class 中的数据已经过时，估算结果仍然准确：
1 | => SELECT reltuples, relpages |
问题在于，如果优化器发现 relpages 与实际文件大小之间存在差距，它可以通过比例调整 reltuples 的值来提高估算精度。由于文件大小相比 relpages 翻了一倍，优化器会调整估算的行数，同时假设数据密度保持不变：
1 | => SELECT reltuples * |
当然，这种调整并不总是有效（例如，如果删除了一些行，估算值将保持不变），但在某些情况下，它可以让优化器在下一次分析触发之前仍然保持合理的估算。
当使用简单查询协议时，每个命令（即使重复多次）都必须经历上述所有阶段：
但是，一次又一次地解析相同的查询是没有意义的。重复解析仅在常量上不同的查询也没有多大意义——解析树结构仍然保持不变。
简单查询协议的另一个缺点是客户端会立即收到整个结果，无论它可能包含多少行。
一般来说，使用 SQL 命令可以克服这些限制。要处理第一种情况，您可以在运行 EXECUTE 命令之前PREPARE查询；第二个问题可以通过使用 DECLARE 创建游标并通过 FETCH 返回行来解决。但在这种情况下，这些新创建的对象的命名必须由客户端处理，而服务器则需要解析额外命令的额外开销
扩展的客户端—服务器协议提供了一种替代方案，使得可以在协议本身的命令级别上，对各个算子执行阶段进行精确控制。
在准备阶段，查询会像往常一样被解析并进行转换，但生成的解析树会保存在后端的内存中。
PostgreSQL 并不存在全局的查询缓存。这种架构的缺点是显而易见的：即使同一条查询已经被其他后端进程解析过，每个后端仍然必须重新解析其接收到的所有查询。但与此同时，这种设计也带来了一些好处。全局缓存由于需要加锁，很容易成为系统瓶颈。一个客户端如果频繁执行大量相似但不完全相同的小查询（例如仅常量不同的查询），会产生大量缓存访问流量，从而对整个实例的性能造成负面影响。在 PostgreSQL 中，查询是在各个后端本地解析的，因此不会对其他进程产生影响。
一条预处理（prepared）的查询可以带参数化。下面是一个使用 SQL 命令的简单示例（尽管这与协议层的预处理不完全相同，但最终效果是一样的）
1 | => PREPARE plane(text) AS |
所有命名的预处理语句都显示在 pg_prepared_statements 视图中：
1 | => SELECT name, statement, parameter_types |
这里不会显示任何未命名语句（即使用扩展查询协议或 PL/pgSQL 的语句）。其他后端准备的语句也不会显示：因为无法访问其他会话的内存。
在预处理语句被执行之前，必须先绑定实际的参数值。
1 | => EXECUTE plane('733'); |
在预处理语句中绑定参数，相比将字面量直接拼接到查询字符串中，其优势在于可以彻底杜绝 SQL 注入：绑定的参数值无法以任何方式修改已经构建完成的解析树。若不使用预处理语句而想达到同等的安全级别，就必须对来自不可信来源的每一个值进行非常谨慎的转义处理。
在执行预处理语句时，查询规划会基于实际的参数值来进行；随后生成的执行计划会交由执行器处理。
由于不同的参数值可能对应不同的最优执行计划，因此在规划阶段准确考虑具体参数值是非常重要的。举例来说，在查询价格较高的预订记录时，规划器会假定符合条件的行数不多，从而选择使用索引扫描。
1 | => CREATE INDEX ON bookings(total_amount); |
但如果给定的条件对所有预订记录都成立，那么使用索引就没有意义了，因为最终仍然需要扫描整张表。
1 | => EXPLAIN SELECT * |
在某些情况下，规划器可能会同时保留解析树和查询计划，以避免重复进行规划。由于这种计划不会考虑具体的参数值，因此被称为通用计划（generic plan），以区别于基于实际参数值生成的定制计划（custom plan）。
参数化预处理语句的前五次执行，优化过程始终依赖于实际的参数值；规划器会基于这些参数值计算定制计划（custom plan）的平均成本。从第六次执行开始，如果通用计划（generic plan）在平均意义上比定制计划更高效（同时考虑到每次都需要重新生成定制计划的额外开销），规划器就会保留通用计划并继续使用它，从而跳过后续的优化阶段。
一个显而易见的场景是：当查询不包含任何参数时，数据库可以使用通用计划而不会对性能造成影响
1 | => EXECUTE plane('763'); |
在第五次执行之后，规划器会切换为通用计划（generic plan）：该计划与之前的定制计划并无差别，成本也相同，但后端只需构建一次即可，并且可以跳过优化阶段，从而降低规划开销。此时，EXPLAIN 命令显示参数是通过位置来引用的，而不再显示其具体取值。
1 | => EXECUTE plane('320'); |
“优化阶段”特指每次执行时基于参数值重新生成执行计划的那一部分工作。
我们可以很容易想象这样一种不利情况：前几次生成的 custom plan 比 generic plan 更昂贵；随后可能出现的更高效的 custom plan 却完全不会被考虑。此外，规划器比较的是估算成本而非实际执行成本，这也可能导致误判。
不过，如果规划器的自动决策出现偏差，你可以通过设置 plan_cache_mode 参数来覆盖自动选择，从而强制使用 generic plan 或 custom plan
1 | => SET plan_cache_mode = 'force_custom_plan'; |
除了其他信息之外，pg_prepared_statements 视图还显示了所选计划的统计信息：
1 | => SELECT name, generic_plans, custom_plans |
扩展查询协议允许按批次而不是一次性检索数据。SQL 游标（cursor）几乎具有相同效果（唯一的区别是服务器需要做一些额外处理，而且规划器只会优化前 cursor_tuple_fraction 行的获取，而不是整个结果集）。
1 | => BEGIN; |
如果查询返回大量行，且客户端需要获取所有行，那么系统吞吐量高度依赖于批量大小（batch size）。批量包含的行数越多，每次访问服务器并获取响应时产生的通信开销就越小。然而，随着批量大小继续增加，这种优势会逐渐减弱：例如，将行一条条取出与每批取 10 行的差别非常明显，但将每批取 100 行与每批取 1000 行相比，性能提升就不那么显著了
前面章节中的示例都是基于只有几行数据的简单表。本章以及后面的章节要处理查询执行，在这方面对数据要求更高：我们需要行数多得多、彼此有关联的表。为了不在每个示例中都重新发明一个新的数据集，我选用了一个现成的演示数据库，它展示了俄罗斯的客运航空交通情况。这个数据库有多个版本；我们将使用 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 参数的值来选择输出语言。不过在查询计划中，有些底层表的名称仍然可能会出现。
一种简单版本的客户端–服务器协议即可实现 SQL 查询的执行：客户端将查询文本发送给服务器，而服务器则返回完整的执行结果——无论结果包含多少行。发送到服务器的查询会经过几个阶段：解析（parse）→ 转换（transform）→ 计划（plan）→ 执行（execute）。
首先，PostgreSQL 必须对查询文本进行解析（parse），以便理解需要执行的内容。
Lexical and syntactic analysis 词法分析器（lexer）会把查询文本拆分成一组词法单元（lexemes），例如关键字、字符串字面量、数字字面量等；而语法分析器（parser）会根据 SQL 的语言语法规则对这组词法单元进行验证。PostgreSQL 使用的是标准的解析工具，即 Flex 和 Bison。
解析后的查询会以抽象语法树（AST）的形式存储在后端进程的内存中。
例如，让我们来看下面这个查询：
1 | SELECT schemaname, tablename |
词法分析器从中识别出了 5 个关键字、5 个标识符、1 个字符串字面量，以及 3 个单字符词素（一个逗号、一个等号和一个分号）。语法分析器则使用这些词素来构建解析树，下面的插图展示了一个高度简化的解析树。树中每个节点旁的文字说明表示该节点对应查询中的哪一部分：
一个比较晦涩的缩写 RTE 代表 Range Table Entry（范围表项）。PostgreSQL 的源代码中使用 range table（范围表） 这个术语来指代表、子查询、连接结果——换句话说，指代 任何可以被 SQL 运算符处理的行集（set of rows）
语义分析（Semantic analysis） 的目的在于确认数据库中是否存在该查询按名称引用的表或其他对象，并检查用户是否拥有访问这些对象的权限。语义分析所需的全部信息都存储在 系统目录（system catalog） 中。
在获得解析树之后，语义分析器会对其进行进一步的重组，这包括：为解析树添加对具体数据库对象、数据类型以及其他信息的引用。
如果你启用了参数 debug_print_parse，就可以在服务器日志中看到完整的解析树，但这通常没有太大的实际意义。
在下一阶段，查询会被转换（重写，rewrite）。
PostgreSQL 核心在多个场景下会使用查询转换。其中之一就是：
将解析树中 视图（view） 的名称替换为该视图底层查询（base query）对应的子树。
另一个使用转换的场景是行级安全（Row-Level Security, RLS） 的实现。
另外，递归查询中的 SEARCH 和 CYCLE 子句也会在此阶段被转换。
在上面的示例中，pg_tables 是一个视图；如果我们把它的定义直接展开写进查询文本，它将会是下面这样：
1 | SELECT schemaname, tablename |
不过，服务器并不会处理查询的文本表示；所有操作都在解析树（parse tree）上完成。下图展示的是一个简化后的重写树（如果启用 debug_print_rewritten 参数，你可以在服务器日志中看到其完整版本）。
解析树只反映了查询的语法结构，但并不包含任何关于操作执行顺序的信息。
此外，PostgreSQL 还支持自定义转换，用户可以通过 rewrite rule（重写规则）系统来实现自己的查询重写逻辑。
规则系统（rule system）的支持曾被宣称为 Postgres 开发的主要目标之一；在最初实现规则系统时，Postgres 还只是一个学术项目，但之后规则系统已经多次被重新设计。规则系统非常强大，但也相当难以理解和调试。甚至有人提议直接把规则系统从 PostgreSQL 中移除，但这一想法并未得到一致认可。在大多数情况下，使用 触发器（trigger） 会比使用规则更加安全且容易。
SQL 是一种声明式语言：查询只说明要取什么数据，而不说明如何取。
任何查询都可以有多种执行路径。解析树中的每个操作都可能有多种完成方式：
例如，结果既可以通过全表扫描（读取整张表并过滤掉不需要的数据）得到，也可以通过索引扫描来找到所需行。数据集在连接时总是两两结合（pairwise joins），这意味着连接顺序存在大量组合，从而产生数量巨大的候选执行方案。此外，还有多种连接算法（join algorithms）：例如，执行器可以扫描第一个数据集的每一行，并在第二个数据集中查找匹配行；或者，先对两个数据集进行排序，再执行合并连接（merge join）。对每一种算法，都能找到其优于其他算法的使用场景。
最优计划与非最优计划的执行时间可能相差几个数量级，因此用于对解析后的查询进行优化的 计划器（planner） 是系统中最复杂的组件之一
Plan tree 执行计划同样以树结构表示，但其节点处理的是物理数据操作，而不是逻辑操作。
如果你想查看完整的计划树，可以启用 debug_print_plan 参数，将计划树输出到服务器日志中。但在实际工作中，通常只需要查看 EXPLAIN 命令显示的文本形式的执行计划就足够了。
下图突出展示了执行计划树中的主要节点。正是这些节点会出现在下面 EXPLAIN 命令的输出中。
暂时我们先关注以下两点：
1 | => EXPLAIN SELECT schemaname, tablename |
查询计划中的 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 | SELECT ... |
在这种情况下，规划器必须考虑所有可能的连接（join）组合。该查询会由解析树中的如下部分来表示（示意性展示）。
在下一个示例中，连接（join）的结构由 JOIN 子句 明确定义。
1 | SELECT ... |
解析树会反映出这种结构。
规划器通常会将连接树（join tree）扁平化，使其看起来与第一个示例中的结构类似。该算法会递归遍历整棵树，并将每个 JOINEXPR 节点替换为其包含元素的扁平列表。
然而，只有当生成的扁平列表元素数量不超过 join_collapse_limit 时，这种合并操作才会执行。在这个特定的例子中，如果 join_collapse_limit 的值小于五，JOINEXPR 节点将不会被合并。
对于查询优化器而言，这意味着：
如果 join_collapse_limit 参数设置为 1，则显式 JOIN 子句中定义的顺序将被保留。
关于 FULL OUTER JOIN 的操作数，它们永远不会被合并（collapsed），无论 join_collapse_limit 参数的值是多少。
from_collapse_limit 参数以类似的方式控制子查询的扁平化。虽然子查询看起来不像 JOIN 子句，但在解析树（parse tree）层面上，这种相似性就很明显了
一个例子：
1 | SELECT ... |
对应的JOIN树如下所示。这里唯一的区别是，这棵树包含的是 FROMEXPR 节点，而不是 JOINEXPR（因此参数名如此命名）。
遗传查询优化（Genetic query optimization） 在将查询树扁平化之后，某一层可能包含过多的元素——无论是表还是中间连接结果，这些元素都需要单独进行优化。由于查询计划的生成时间会随着需要连接的数据集数量呈指数增长，因此plan时间可能会超出所有合理的范围。
如果启用了 geqo 参数，并且某一层的元素数量超过 geqo_threshold 的阈值，查询规划器将使用遗传算法来优化查询。相比动态规划，遗传算法的速度要快得多，但它无法保证找到的查询计划一定是最优的。因此，一条经验法则是通过减少需要优化的元素数量来避免使用遗传算法。
遗传算法有若干可配置参数，但在此不作详细介绍。
选择最佳执行计划 查询计划是否可以被认为是最优的，取决于特定客户端如何使用查询结果。如果客户端需要一次性获取完整结果（例如，用于生成报表），那么计划应当优化所有行的检索效率。但如果优先考虑尽快返回前几行（例如，用于屏幕显示），那么最优计划可能完全不同。
为了做出这个选择，PostgreSQL 会计算成本的两个组成部分：
1 | => EXPLAIN |
第一个组成部分（启动成本）表示节点执行前的准备开销；第二个组成部分（总成本）则包括获取查询结果过程中产生的所有开销。
有时人们会说启动成本是获取结果集第一行的开销，但这种说法并不完全准确。
为了挑选出首选执行计划，优化器会检查查询是否使用了游标（无论是通过 SQL 中的 DECLARE 命令，还是在 PL/pgSQL 中显式声明（explicitly））。如果没有使用游标，则默认客户端需要一次性获取完整结果，优化器会选择总成本最小的计划。
如果查询是通过游标执行的，则所选计划必须优化仅获取所有行中 cursor_tuple_fraction 部分的效率。更准确地说，PostgreSQL 会选择使以下表达式值最小的计划：
1 | startup cost + cursor_tuple_fraction (total cost − startup cost) |
** 成本估算概述 ** 要估算一个计划的总成本，必须对计划中的所有节点进行成本估算。节点的成本取决于其类型（显而易见，读取堆表数据的成本与排序操作的成本不同）以及节点处理的数据量（数据量越大，通常成本越高）。虽然节点类型是已知的，但数据量只能根据输入集的预计基数（节点接收的行数）以及节点的选择性（输出中剩余行的比例）来预测。这些计算依赖于收集到的统计信息，例如表的大小以及表列中数据的分布情况。
如果对每个节点的基数估计准确，计算出的成本很可能能够较好地反映实际成本。规划中主要的缺陷通常源于基数和选择性的估计不准确，这可能由以下原因造成：
基数估计（Cardinality estimation） 要计算节点的基数，优化器必须递归地完成以下步骤：
节点的基数即这两个值的乘积。
选择性(Selectivity)用一个介于 0 到 1 之间的数表示。数值越小，选择性越高；反之，数值接近 1 表示选择性较低。乍一看可能不太直观，其含义是：高选择性条件会筛掉几乎所有行，而只排除少量行的条件则选择性低。
首先，优化器会估算定义数据访问方式的叶子节点的基数。这些计算依赖于收集到的统计信息，例如表的总大小。
过滤条件的选择性取决于条件的类型。在最简单的情况下，可以将其假设为一个常数值，尽管优化器会尽量利用所有可用信息来精确估算。通常，只需要掌握如何估算简单过滤条件即可；如果条件包含逻辑运算，其选择性则按照以下公式计算：
1 | 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 会根据该节点执行的操作建立数学模型，并以已经估算好的节点基数作为输入。对于每个节点，都会计算 启动成本 和 总成本。
某些操作没有前置条件，因此可以立即执行，这类节点的启动成本为零。
而另一类操作则必须等待一些前置操作完成后才能执行。例如，排序节点通常需要等待其子节点返回所有数据后，才能进行自己的任务。这类节点的启动成本通常大于零：即使上层节点（或客户端）只需要输出中的一行，也必须支付这一成本。
优化器进行的所有计算都是估算值，可能与实际执行时间无关。它们的唯一目的，是在相同条件下对同一查询的不同执行计划进行比较。在其他情况下（尤其是不同查询之间），用成本来比较意义不大。例如，由于统计信息过时，成本可能被低估；在统计信息刷新后，计算出的成本可能上升，但由于估算更准确，服务器会选择更优的执行计划。
在查询优化阶段生成的执行计划现在必须被执行。
执行器（executor）会在后端内存中打开一个 portal，这是一个保存当前正在执行查询状态的对象。这个状态以一棵树的形式表示，结构与执行计划树相同。树中的各节点像流水线一样运作，彼此请求并传递行数据。
查询执行从根节点开始。以本例为例，根节点表示 排序（SORT）操作，它从子节点获取数据。在接收到所有行之后，根节点对数据进行排序，并将结果传递给客户端。
某些节点（如图示中的 NESTLOOP 节点）负责将来自不同来源的数据集进行连接。此类节点会从两个子节点拉取数据，并在收到满足连接条件的行对后立即向上层传递结果行（与排序不同，排序必须先获取所有行）。此时，节点的执行会暂停，直到其父节点请求下一行。如果查询只需要部分结果（例如包含 LIMIT 子句），该操作不会执行完整。
树中的两个 SEQSCAN 叶子节点负责表扫描。当父节点请求数据时，这些节点会从对应的表中获取下一行数据。
因此，一些节点不存储任何行，而是立即向上层传递数据；而其他节点（如 SORT）可能需要保留大量数据。为此，后端内存中会为其分配一个 work_mem 内存块；如果内存不足，多余的数据会溢写到磁盘上的临时文件。
一个执行计划可能包含多个需要数据存储的节点，因此 PostgreSQL 可能会分配多个 work_mem 大小的内存块。查询可使用的总 RAM 大小没有任何限制。
全文搜索的目标是从提供的文档集中选择与搜索查询匹配的文档
为了进行搜索，文档会被转换为 tsvector 类型，该类型包含文档中的词素（lexemes）及其在文档中的位置。词素是将单词转换为适合搜索的格式。默认情况下，所有单词都会被标准化为小写，并去除其词尾。
“并去除其词尾”指的是在全文搜索中，对单词进行词干提取（stemming）或词形归一化（normalization）的过程。具体来说，这是将单词的词尾（如英语中的复数、时态、词性变化等）去除，提取出单词的词干（stem）或基本形式，以便在搜索时能够匹配同一词根的不同变体。例如：单词“running”、“ran”和“runs”都源自同一词根“run”。在全文搜索的处理中，这些单词可能会被归一化为“run”，即去除词尾变化，保留词干。搜索“run”时，系统不仅会匹配“run”，还会匹配“running”、“ran”和“runs”等形式，因为它们都被归一化为相同的词干“run”。
1 | demo=# SET default_text_search_config = english; |
所谓的停用词（如“the”或“from”）会被过滤掉：这些词被认为出现频率过高，搜索它们无法返回有意义的搜索结果。当然，所有这些转换都是可以配置的。
查询由另一种类型表示：tsquery。任何查询都包含一个或多个通过逻辑连接符连接的词素：&（与）、|（或）、!（非）。你还可以使用括号来定义操作符的优先级。
1 | demo=# SELECT to_tsquery('wind & (comes | goes)'); |
全文搜索中唯一使用的操作符是匹配操作符 @@：
1 | demo=# SELECT amopopr::regoperator, oprcode::regproc, amopstrategy FROM pg_am am |
该操作符判断文档是否满足查询条件。以下是一个示例：
1 | demo=# SELECT to_tsvector('Where the wind comes from, where the wind goes') @@ to_tsquery('wind & coming'); |
这绝不是对全文搜索的详尽描述，但这些信息应足以理解索引的基础知识。
为了实现快速的全文搜索，必须使用索引来支持。索引的对象不是文档本身，而是 tsvector 值。这里有两种选择：一种是在表达式上构建索引并进行类型转换，另一种是添加一个单独的 tsvector 类型列并对该列进行索引。第一种方法的优点是不会浪费空间来存储 tsvector 值，因为这些值实际上并不需要直接存储。但这种方法比第二种方法慢，因为索引引擎需要重新检查访问方法返回的所有堆元组。这意味着对于每个重新检查的行，都需要再次计算 tsvector 值，而且正如我们很快会看到的，GiST 索引会重新检查所有行。
让我们构建一个简单的示例。我们将创建一个包含两列的表：第一列存储文档，第二列存储 tsvector 值。我们可以使用触发器来更新第二列，但更方便的做法是直接将该列声明为生成列。
1 | CREATE TABLE ts( |
在上面的例子中，我使用了带有单一参数的 to_tsvector 函数，通过设置 default_text_search_config 参数来定义全文搜索配置。这种函数变体的波动性（volatility）类别是 STABLE，因为它隐式依赖于参数值。但在这里，我使用了另一种变体，显式指定配置；这种变体是 IMMUTABLE，可以用于生成表达式。
我们插入几行数据
1 | demo=# INSERT INTO ts(doc) VALUES |
因此，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 | ALTER TABLE mail_messages ADD COLUMN tsv tsvector GENERATED ALWAYS AS ( to_tsvector( |
在填充该列（tsv）的过程中，一些特别长的词因为长度太大被过滤掉了。但一旦索引构建完成，就可以用于搜索查询了。
1 | demo=# EXPLAIN (analyze, costs off, timing off, summary off) SELECT * |
除了满足条件的 898 行之外，访问方法还返回了另外 7852 行，这些行需要后续通过回检（recheck）来过滤。如果我们增加签名容量（signature capacity），准确性（也就是索引效率）会提高，但索引的大小也会随之增加。
1 | demo=# DROP INDEX mail_messages_tsv_idx; |
我已经展示了访问方法的属性，其中大多数在所有操作符类中都是相同的。但是下面两个列级别的属性值得一提：
1 | demo=# SELECT p.name, pg_index_column_has_property('mail_messages_tsv_idx', 1, p.name) |
现在不可能进行 Index-only 扫描了，因为无法从签名中恢复出原始值。
不过在这个特定的场景下这是完全可以接受的：
tsvector 值只是用于搜索，我们真正需要的是文档本身（也就是实际的数据行）。
对于 tsvector_ops 类来说，也没有定义排序操作符
第一个示例涉及在平面上对点（或其他几何形状）进行索引。常规的B树无法用于这种数据类型，因为点没有定义比较运算符。显然，我们可以自己实现这样的运算符，但几何形状需要索引支持完全不同的操作。我将只讨论其中的两种：搜索特定区域内包含的对象和最近邻搜索。
R树在平面上绘制矩形；这些矩形合起来必须覆盖所有被索引的点。一个索引条目存储边界框，谓词可以定义如下：点位于该边界框内。
R树的根节点包含若干个大矩形（这些矩形可能会有重叠）。子节点包含较小的矩形，这些矩形适合其父节点；它们一起覆盖所有底层的点。
叶节点应该包含被索引的点本身，但GiST要求所有条目具有相同的数据类型；因此，叶节点的条目也由矩形表示，这些矩形被简化为点。
为了更好地可视化这种结构，我们来看一个基于机场坐标构建的R树的三个层次。在这个例子中，我已将演示数据库的机场表扩展到五千行。同时我还降低了fillfactor值使树的层次更深。默认值会给我们一个单层树。
1 | demo=# CREATE TABLE airports_big AS select * from airports_data; |
在顶层，所有点都被包含在几个（可能部分重叠的）边界框中。
在下一层，大矩形被分割成较小的矩形。
最后，在树的底层，每个边界框包含的点数量与单个页面所能容纳的数量相同。
该索引使用point_ops操作符类，这是点数据唯一可用的操作符类。
矩形和其他几何形状可以以相同的方式进行索引，但索引存储的不是对象本身，而是其边界框。
可以通过 pageinspect 插件来学习Gist页
和B-Tree索引不同，Gist没有metapage，0号page就是gist的root节点。如果root节点分裂了，老root节点会被move到一个（或多个）单独的页，新root节点取代其位置
root页的内容如下：
1 | demo=# SELECT ctid, keys FROM gist_page_items(get_raw_page('airports_gist_idx', 0), 'airports_gist_idx' ); |
To extract more detailed information, you can use the gevel extension,which is not included into the standard PostgreSQL distribution.
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 | demo=# SELECT amprocnum, amproc::regproc |
必需的函数：
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 | demo=# SELECT amopopr::regoperator, amopstrategy AS st, oprcode::regproc, |
操作符的名字通常并不能准确反映其语义，因此这个查询还会显示底层函数的名称和它们的描述。无论具体形式如何，这些操作符都处理几何对象之间的相对位置关系（如在左侧、右侧、上方、下方、包含、被包含）以及它们之间的距离。
与 B-tree 相比，GiST 提供了更多的策略（strategy）。一些策略号在多种类型的索引中是通用的，而另一些则是通过公式计算出来的（例如，策略号 28、48 和 68 实际上代表相同的策略：对矩形、多边形和圆形来说都是“被包含”）。此外，GiST 还支持一些已经过时的操作符名称（例如 <<| 和 |>>）。
一个操作符类（operator class）可能只实现了部分可用的策略。举个例子：点类型的操作符类不支持“包含”这个策略，但这个策略在那些具有可度量面积的几何体操作符类（如 box_ops、poly_ops 和 circle_ops）中是可用的。
一个典型的可以通过索引加速的查询是返回指定区域内的所有点。例如，我们来查找距离莫斯科中心一度以内的所有机场：
1 | demo=# SELECT airport_code, airport_name->>'en' |
我们可以通过下图所示的一个简单示例来更仔细地查看这个操作符
如果以这种方式选择边界框，索引结构将如下所示：
包含操作符 <@ 用于判断某个点是否位于指定矩形内部。对于该操作符，其一致性函数（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）发生重叠时。
大多数索引支持的操作符（例如上一个例子中的 = 或 <@）通常被称为搜索操作符，因为它们在查询中定义了搜索条件。这类操作符是谓词，即它们返回一个逻辑值（真或假）。
但还有一类是排序操作符，它们返回的是参数之间的距离。这类操作符通常用于 ORDER BY 子句中，并且一般由具有 Distance Orderable 属性的索引所支持。该属性允许你快速找到指定数量的最近邻。这种类型的搜索被称为 k-NN（k 最近邻搜索）。
例如，我们可以查找最接近 Kostroma 的 10 个机场：
1 | demo=# SELECT airport_code, airport_name->>'en' |
由于索引扫描是逐个返回结果，并且可以在任何时刻停止，因此前几个值可以非常快速地获取到。
如果没有索引支持，要实现高效的搜索将非常困难。我们将不得不先查找某个特定区域内的所有点，然后逐步扩大该区域，直到返回所需数量的结果。
这将需要多次索引扫描，更不用说还存在一个难题：如何选择初始区域的大小以及每次扩展的增量。
你可以在系统目录中查看操作符的类型（其中 “s” 表示搜索操作符，”o” 表示排序操作符）。
1 | demo=# SELECT amopopr::regoperator, amoppurpose, amopstrategy FROM pg_am am |
为了支持这类查询，操作符类必须定义一个额外的支持函数：也就是距离函数（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），导致需要额外扫描一个节点，因此搜索效率下降；不过，算法本身仍然是正确的。
当向 R 树中插入一个新键时，用于存放该键的节点是由penalty函数决定的：该节点的边界框（bounding box）大小应尽可能少地增加。
例如，点 (4,7) 将被插入到矩形 (5,3)–(9,9) 中，因为该矩形的面积只需增加 6 个单位；而如果插入到矩形 (0,0)–(3,4)，则其面积需要增加 12 个单位。在下一层（叶子层），该点也会按照相同的逻辑被加入到矩形 (6,6)–(9,9) 中。
假设一个页面最多可以容纳三个元素，那么当超出这个限制时，它必须被拆分成两个页面，
并且这些元素需要在新的页面之间重新分配。在这个示例中，分配结果看起来很明显，但在一般情况下，数据的分布并不那么简单。最重要的是，picksplit 函数会尽量减少边界框（bounding box）之间的重叠，目标是获得更小的矩形以及在页面之间均匀分布点。
GiST 索引也可以用于排除约束（exclusion constraints）。排除约束确保：对任意两条堆表元组来说，它们在某些操作符意义下的指定字段不能彼此匹配。要实现这一点，必须满足以下条件：
对于上面提到的 hash 和 btree 访问方法来说，唯一合适的操作符是等于（=）。这实际上使排除约束退化成了唯一约束，因而没有太大实际用途
GiST 方法还支持另外两种适用的策略：
我们来试试这个功能：创建一个约束，用于禁止机场之间距离太近。
这个条件可以这样表达：以机场坐标为圆心、指定半径的圆形不得彼此重叠。
1 | demo=# ALTER TABLE airports_data ADD EXCLUDE USING gist (circle(coordinates,0.2) WITH &&); |
当定义一个排除约束（exclusion constraint）时，系统会自动创建一个索引来强制执行该约束。在本例中，这个索引是一个基于表达式的 GiST 索引。
我们来看一个更复杂的例子。假设我们允许机场之间距离很近，但前提是这些机场属于同一个城市。一种可行的解决方案是定义一个新的完整性约束，表达如下：如果两个圆（以机场坐标为圆心）发生重叠（&&），且它们对应的城市名称不同（!=），则这种情况是不允许的。
尝试创建这样的约束会导致一个错误，因为对于 text 数据类型并没有可用的操作符类（operator class）。
1 | demo=# ALTER TABLE airports_data |
虽然 GiST 原生不支持 text 或 int 等有序类型，但借助 btree_gist 扩展，可以让这些类型也具备使用 GiST 进行等值/比较操作的能力，从而用于复杂约束（如排除约束）或混合类型索引。
1 | demo=# CREATE EXTENSION btree_gist; |
该约束已成功创建。现在我们无法添加名为 Zhukovsky 的机场（即使它属于同名城市），
因为它与莫斯科的几个机场之间的距离太近，违反了约束条件。
1 | demo=# INSERT INTO airports_data( |
但是我们可以在莫斯科创建机场
1 | demo=# INSERT INTO airports_data( |
需要注意的是，尽管 GiST 支持大于、小于和等于等操作符，但 B-tree 在这方面效率要高得多，尤其是在访问一段范围值时。因此，只有当确实有其他合理原因需要使用 GiST 索引时，
才有意义使用上面提到的 btree_gist 扩展技巧。
访问方法属性（Access Method Properties）以下是 GiST 访问方法的属性：
1 | demo=# SELECT a.amname, p.name, pg_indexam_has_property(a.oid, p.name) |
GiST 索引不支持唯一约束（Unique constraints）和排序（sorting）。GiST 索引可以通过额外的 INCLUDE 列来创建。正如我们所知，我们可以在多个列上构建索引，也可以将其用于完整性约束（integrity constraints）。
索引级别属性（Index-level properties）。这些属性是在索引层面定义的。
1 | demo=# SELECT p.name, pg_index_has_property('airports_gist_idx', p.name) |
GiST 索引可以用于聚簇（clusterization）操作。在数据检索方式方面，GiST 支持常规（逐行）索引扫描和位图扫描（bitmap scan）。但 GiST 不支持反向扫描（backward scanning）。
列级别属性（Column-level properties）：大多数列属性是在访问方法（access method）级别定义的，并且保持不变。
1 | demo=# SELECT p.name, pg_index_column_has_property('airports_gist_idx', 1, p.name) |
所有与排序相关的属性都是禁用的。
GiST 索引允许 NULL 值存在，但处理效率并不高。一般认为，NULL 值不会扩展边界框（bounding box），所以这些值会被随机插入某个子树中。因此，在查询时需要遍历整棵 GiST 树来查找这些值。
不过，有少数列级属性是依赖于具体操作符类（operator class）的。
1 | demo=# SELECT p.name, pg_index_column_has_property('airports_gist_idx', 1, p.name) |
GiST 索引允许执行索引仅扫描（Index-only scan），因为叶子节点中保留了完整的索引键值。
正如前文所述，某些操作符类（operator class）提供了用于最近邻搜索的距离操作符。
对于 NULL 值，距离计算结果为 NULL，这种情况下这些值会排在最后返回（类似 B-tree 中的 NULLS LAST 语法）。
然而，对于范围类型（range types）而言，并不存在“距离操作符”（因为它们表示的是线段，也就是线性几何体，而不是面状几何体）。所以，当索引建立在这些类型上时，上述性质会有所不同。
1 | demo=# CREATE TABLE reservations(during tsrange); |
Gist（Generalized Search Tree，广义搜索树）是一种访问方法(是一个索引框架)，本质上是对支持值之间相对位置关系的数据类型的平衡搜索树的一种泛化。B-tree 只能用于可排序的数据类型，即那些支持比较操作（比如大于、小于等）。对于这类类型，B-tree 的支持是非常高效的。而 Gist 则更为通用，它的操作符类（operator class）允许用户定义任意的数据分布规则，从而控制树的构造方式。因此，Gist 索引可以用于实现不同的数据结构，例如：
由于 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 索引可能会导致其性能下降