PostgreSQL 19 preview - JOIN 计划大提速

本期播客

PostgreSQL 19 preview - JOIN 计划大提速

为了提升JOIN操作的结果集估算准确度, 优化器通常要用到JOIN两侧的列的MCV(高频值)的统计信息, 用来估算结果集的大小, 防止数据倾斜的情况. 但是以前的优化算法有问题, 在mcv的值的个数较少时没什么大事, 当值很多时笛卡尔积就很大, 影响优化器规划阶段的性能.

PostgreSQL 19 提交了一个补丁, 提升“具有大量 MCV 统计信息的大表连接时的查询规划”速度.

https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=057012b205a082ec930cd7bb7f6663516be011e2

Speed up eqjoinsel() with lots of MCV entries.      

If both sides of the operator have most-common-value statistics,      
eqjoinsel wants to check which MCVs have matches on the other side.      
Formerly it did this with a dumb compare-all-the-entries loop,      
which had O(N^2) behavior for long MCV lists.  When that code was      
written, twenty-plus years ago, that seemed tolerable; but nowadays      
people frequently use much larger statistics targets, so that the      
O(N^2) behavior can hurt quite a bit.      

To add insult to injury, when asked for semijoin semantics, the      
entire comparison loop was done over, even though we frequently      
know that it will yield exactly the same results.      

To improve matters, switch to using a hash table to perform the      
matching.  Testing suggests that depending on the data type, we may      
need up to about 100 MCVs on each side to amortize the extra costs      
of setting up the hash table and performing hash-value computations;      
so continue to use the old looping method when there are fewer MCVs      
than that.      

Also, refactor so that we don't repeat the matching work unless      
we really need to, which occurs only in the uncommon case where      
eqjoinsel_semi decides to truncate the set of inner MCVs it      
considers.  The refactoring also got rid of the need to use the      
presented operator's commutator.  Real-world operators that are      
using eqjoinsel should pretty much always have commutators, but      
at the very least this saves a few syscache lookups.      

Author: Ilia Evdokimov <[email protected]>      
Co-authored-by: David Geier <[email protected]>      
Reviewed-by: Tom Lane <[email protected]>      
Discussion: https://postgr.es/m/[email protected]      

这个补丁（commit 057012b205a082ec930cd7bb7f6663516be011e2）的目的是加速 PostgreSQL 中 eqjoinsel() 函数的执行，尤其是在处理包含大量“最常见值”（MCV）统计信息时。

以下是补丁的详细解读：

核心问题

eqjoinsel() 是 PostgreSQL 内部用于估算等值连接（Equality Join）选择性（selectivity）的函数。当连接两侧的列都具有 MCV（Most-Common-Value）统计信息时，该函数需要检查一侧的 MCV 列表中的值是否在另一侧的 MCV 列表中有匹配。

• 旧方法的问题： 以前的方法是使用一个简单的循环，对两侧的 MCV 条目进行两两比较。如果两侧的 MCV 列表长度分别为 N 和 M，最坏情况下性能是 **O(N*M)**，如果 N 约等于 M，则是 O(N²) 的行为。
• 影响： 二十多年前这段代码编写时，MCV 列表通常很短，O(N²) 的性能尚可接受。但现在用户经常使用更大的统计信息目标（statistics targets），导致 MCV 列表变得很长，O(N²) 的性能瓶颈变得非常明显。

补丁采取的优化措施

为了解决 O(N²) 的性能问题，补丁引入了哈希表（Hash Table）来进行匹配：

1. 引入哈希表： 将旧的 O(N²) 循环比较替换为使用哈希表进行匹配。哈希表通常能将查找时间复杂度降至接近 **O(N)**，显著提高效率。
2. 混合策略： 考虑到设置哈希表和计算哈希值本身也有开销，该补丁并没有对所有情况都使用哈希表。通过测试，当两侧的 MCV 条目数量小于约 100 时，继续使用旧的循环比较方法；只有当 MCV 数量达到或超过这个阈值时，才使用哈希表来摊销其额外成本。
3. 重构半连接/反半连接逻辑： 补丁对代码进行了重构，以避免在处理半连接（Semi-join）或反半连接（Anti-semi-join）语义时，重复执行整个匹配过程。只有在 eqjoinsel_semi 决定截断它考虑的内部 MCV 集合（这是不常见的情况）时，才会重复匹配工作。
4. 简化依赖： 重构还消除了对原始操作符的交换子（commutator）的依赖，这至少可以节省一些系统缓存查找（syscache lookups）。

涉及文件

• src/backend/utils/adt/selfuncs.c: 这是实现 eqjoinsel() 函数的主要文件，所有的优化逻辑都在这里。
• src/tools/pgindent/typedefs.list: 这是一个工具文件，用于代码格式化，可能只是加入了新的结构体或类型定义。

结论

这个补丁是一个性能优化补丁，通过将二次方时间复杂度（O(N²)）的 MCV 匹配逻辑改进为近似线性时间复杂度（O(N)）的哈希表查找，显著提升了 PostgreSQL 在处理具有大量 MCV 统计信息的大表连接时的查询规划速度。

为什么表连接查询规划时需要计算join两侧mcv值?

这是一个关于数据库查询优化器如何工作的关键问题。简而言之，查询规划器在计算表连接（Join）的选择性（Selectivity）和最终结果集大小（Cardinality）时，必须使用两侧的 MCV（Most-Common-Value，最常见值）统计信息，主要是为了应对数据倾斜。

以下是表连接查询规划时需要计算和匹配两侧 MCV 的主要原因：

1. 准确估算连接结果集大小 (Cardinality Estimation)

查询优化器的核心任务是找到执行查询的最快方法。要做到这一点，它必须准确预测每个操作（包括连接）的结果集大小（基数）。

• 基数估算是选择连接算法的关键： 准确的基数估算决定了优化器会选择哪种连接算法：
• 如果估计结果集很小，可能会选择嵌套循环连接 (Nested Loop Join)。
• 如果估计结果集很大，但数据可以有效地散列，可能会选择哈希连接 (Hash Join)。
• 如果数据已排序或易于排序，可能会选择归并连接 (Merge Join)。
• 如果估算错误，例如实际结果集很大但优化器却选择了效率低下的嵌套循环连接，查询性能会急剧下降。

2. 处理真实世界的数据倾斜 (Data Skew)

在现实世界的数据中，值的分布往往是不均匀的（即存在数据倾斜）。少数值可能占据了列中绝大多数的行。

• 没有 MCV 时的默认假设： 如果没有 MCV 统计信息，优化器通常会假设列中的值是均匀分布的。在这种均匀分布假设下，等值连接 A.col = B.col 的选择性公式通常是  。
• 均匀假设的失效： 如果连接键恰好是数据倾斜的，例如：表 A 和表 B 中都有一个值 'X'，它在两个表中都极为常见（高频值）。如果连接条件是 A.col = B.col，那么仅由值 'X' 匹配产生的行数就可能占到总连接结果的绝大部分。
• MCV 的作用： MCV 统计信息（以及它们各自的频率）专门捕获了这些高频值的分布。通过匹配两侧的 MCV 列表，优化器可以：
• 准确计算高频值的贡献： 对于每一个在两侧 MCV 列表中都存在的值  ，其贡献的选择性为  。
• 计算总选择性： 将所有匹配的 MCV 贡献相加，再加上剩余非 MCV 值的（通常是基于均匀假设的）贡献，得到一个远比单纯均匀假设准确的总选择性估计。

总结

计算并匹配两侧的 MCV 值是查询规划器用来将数据倾斜纳入考虑的关键步骤。它避免了因假设数据均匀分布而导致的严重基数估算错误，从而确保优化器能选择一个高效的、最接近最优的查询执行计划。

这个过程的效率（正如您提到的补丁所优化的那样）直接影响到查询编译时间，因为任何查询在执行前都必须经过这一步精确的估算。