PostgreSQL 解析器如何选择要使用的连接类型？加入我们，参加关于连接理论的会议。
在上一篇文章中，我们提到 PostgreSQL 的出现是因为一些数学家想将集合论映射到文件系统。关于它是如何工作的，有很多解释。这种解释在今天仍然很重要，可以帮助我们理解 PostgreSQL 解析器如何选择连接方法或连接类型。
本文将概述 PostgreSQL 解析器选择连接类型的高级策略。 您可以期待后续文章，这些文章将更详细地解释不同类型的连接在何时何地有用，并提供最高的效率。
如果您不知道什么是集合论，或者不知道基本连接如何映射到集合论，那么已经有一些非常棒的文章。我们不会费心去重复那些已经写得很好的文章。本文将更实际地解释查询规划器如何处理 SQL 连接理论的复杂性。
数据库规划器的基本工作原理并不像您想象的那么复杂。目标是拆解 SQL 语句，并将其转换为一系列函数，这些函数将生成请求的结果。
让我们看一个相当简单的语句，它为我们提供了解析器使用的大多数元素
SELECT fields, cols, tuples, list, item
FROM relation
INNER JOIN _data
ON (relation.dataid) = (data.id)
WHERE criteria = 1 and more_criteria = 4在这个语句中，我们有一个称为“选择列表”的部分
SELECT 字段、列、元组、列表、项
这是要从物理数据存储中检索的项列表。
更重要的是，对于我们关于连接类型的讨论，我们有“扫描列表”
FROM relation
INNER JOIN _data这告诉解析器选择列表来自哪个存储。
然后我们有“条件列表”，它是
ON (relation.dataid) = (data.id)
WHERE criteria = 1 and more_criteria = 4条件列表将搜索范围缩小到调用方感兴趣的特定数据。
“扫描列表”中的每个实体都称为“扫描节点”。当我们从执行的角度来看待这个问题时，解析器可以通过多种方式从扫描节点中检索用户请求的数据（选择列表）
1. 检索所有数据并在内存中应用条件。
2. 扫描表，同时将条件直接应用于每一行。
3. 使用索引仅检索请求的数据。
4. 扫描表，同时使用索引来消除行。
5. 仅索引扫描（要求选择列表存在于索引中）。
6. 构建条件的哈希值，然后扫描数据并在内存中应用哈希值。
7. 我忘记提到的方法...
8. 开发人员一直在想出的更多方法...
现在，我们来谈谈与文章标题相关的魔力。解析器必须根据条件决定将数据关联在一起的最有效方式。
ON (relation.dataid) = (data.id)
它通过选择一种连接类型来做到这一点，这是一种用 C 语言编写的算法，用于执行检查，以查看数据是否确实以用户请求的方式相关联。
通常，我们认为这些条件是等值连接。这是基本关系模型中最常见的数据关联方式，但这远不是构建关系的唯一方式。数据可能属于某个范围、列表、分布、非等值，或者只是让所有内容都与其他所有内容匹配（笛卡尔积）。
为了简单和简洁起见，我们将在这里关注基于等值的连接。在后面的文章中，我们将讨论一些更复杂的连接类型。
PostgreSQL 中有四种基本连接类型。也就是说，有四种基本算法可以将一个集合中的数据与另一个集合中的数据进行匹配。
1. 嵌套循环
2. 哈希
3. 子查询
4. 合并
这些函数在 pg_catalog.pg_proc 中列出。这是系统表，其中驻留着 PostgreSQL 所有函数的实现。查询解析器在很大程度上是一种策略选择机制，它将您的查询映射到此表中的函数。
这些用于连接表的计算策略中的每一种都有其优点和缺点。我们经常被问到哪种方法“最好”。 如果对这个问题有一个明确的答案，“最差”的方法将从选项列表中删除。为什么 PostgreSQL 全球开发组 (PGDG) 会费心维护“糟糕”的选项？
更好的问题是，“哪种方法最适合这种情况？”。我们将在未来的文章中尝试就每种连接类型适用何处提出一些建议。现在，让我们看看解析器如何调用每个连接。
嵌套循环：以使用两个 for 循环（通常为 i，j）的最基本实现命名。 从根本上说，它是对所有行的穷举搜索。
哈希：创建一个查找表并使用它来一次匹配多个条件。
子查询：在辅助表中查找与主表匹配的值。
合并：通过先前排序的公共键将两个表连接在一起。
PostgreSQL 查询规划器将生成 *可以* 满足查询请求的所有扫描类型和连接类型组合的详尽列表。这可能是一个非常广泛的列表。然后，它将从列表中消除最昂贵的项目，直到只剩下一个完成查询的路径。
我们称之为“最小成本优化器”。其理念是，无论剩下什么，无论多么不可能，都是真理。
让我们来看看这个连接操作有多复杂。首先，不能保证扫描列表中的哪个表在算法中排在第一位。评估中排在第一位的表称为“驱动”表。
您可以有
digraph "G" {
node [shape=rectangle label="SCAN\nNode"]
a [label="JOIN\nNode"]
b [label="SCAN\nNode\n'relation'"]
c [color=blue style=filled label="SCAN\nNode\n'data'"]
a -> b;
a -> c;
}
或
digraph "G" {
node [shape=rectangle label="SCAN\nNode"]
a [label="JOIN\nNode"]
b [color=blue style=filled label="SCAN\nNode\n'relation'"]
c [label="SCAN\nNode\n'data'"]
a -> b;
a -> c;
}
这似乎并不重要，直到您意识到这种“驱动表”概念扩展到任意数量的关系。因此，连接顺序复杂度以 $N!$ 的速度上升。
在实践中，实现连接策略（它是数据库查询规划的核心）是查询解析器必须处理的最昂贵的事情之一。稍后，当我们开始查看各个连接类型的 EXPLAIN 计划时，您将看到这种效果。
涉及的表越多，复杂度就越高。这就是为什么 PostgreSQL 对连接中可以涉及多少关系有一个限制（默认情况下为 13 个扫描节点），然后规划器才会进入“遗传查询优化器”(GEQO) 模式的原因。
在这种模式下，关系仅从左到右评估一次。这大大减少了计划的数量，但也消除了一些非常好的计划，而没有真正评估它们。如果您曾经创建过一个非常复杂的查询，在添加一个表时突然表现不佳，那么您很可能已经招致了 GEQO 的愤怒。
geqo=on
geqo_threshold=12PostgreSQL 中的默认连接是 INNER JOIN。 OUTER JOIN 如果您想要集合中的所有元素，则必须指定。可以使用 EXISTS 子句完成半连接，并可以使用 EXCEPT、NOT IN 或 <> （不等于）完成反连接。
解析器在创建可能的计划列表之前还会执行一些其他排列。 这是由“查询重写器”完成的，它是一个尝试根据等效语句重写 SQL 的组件。
查询重写器可能会影响的一些内容是
1. 子查询也可以表示为连接
2. NOT IN（列表）也可以表示为 <> ANY（列表）
3. SQL 函数被拉入调用 SQL 中
4. 以及更多
它们可以通过将一种类型的连接转换为完全不同类型的连接来影响连接选择策略。
选择连接策略的大部分过程对调用者来说都是不可见的。使用 EXPLAIN 关键字，我们只能看到成本最低的优化过程的获胜者。所有其他执行计划都已从计划列表中删除。我们可以通过以不同形式手动重写查询来影响计划，这可以影响解析器做出不同的计划决策。
PostgreSQL 不实现查询提示，并且 PGDG 中有很多惯性来防止这种情况发生。查询提示是故意影响查询解析器而不更改查询文本的注释或语句。
在其他数据库系统中，它们用于有意选择特定的索引、评估和（本文的主题）连接类型。PGDG 出于多种原因避开了这个想法。首先，索引和连接的性能可能会在现场发生变化。
在特定数据量下，嵌套循环可能是合适的策略。随着数据的增长，这可能会积极地转变为哈希连接。由于多版本并发控制 (MVCC) 语义，索引和表会随着时间的推移而膨胀。
在设计中完美运行的索引在现场可能就不是那么完美了。即使用户在设计时使用特定技术提高了查询性能，也不能保证该技术在生产中仍然是最佳选择。而且通常不会。
还有一个反对查询提示的哲学论点。也就是说，查询解析器专门用于将声明性语言转换为命令性过程。整个想法是您声明您想要什么，并允许引擎决定提供指定结果的最佳方法。
“影响”解析器是对该系统的直接背叛。这使得对系统的任何未来改进都不再适用于您的情况，并且使查询规划器本身的任何改进都失效。
提供这些信息是为了让您对有关连接理论以及为什么选择特定连接的更多文章有所了解。最终目标是了解查询规划器做出特定选择的原因。为了实现这一目标，了解查询解析器如何实际执行做出选择的任务会很有帮助。
简而言之，查询被分解成映射到列表中函数的部分。成本最高的函数从列表中删除。剩下的表示为执行计划。执行计划被发送到执行器执行，结果被发送回调用者。
查看这篇文章，了解有关提高 PostgreSQL JOIN 性能的更多策略.
1. 这个 Stackoverflow 帖子在一个简单的问题上完全疯了：tsql - SQL Server 中的 LEFT JOIN 与 LEFT OUTER JOIN - Stack Overflow
2. 这篇博文很好地解释了集合论：集合论：数据库疯狂的方法 | 作者：Vaidehi Joshi | basecs | Medium