PostgreSQL 18 preview - 使用扩展统计信息提高hash join bucket估算准确度

PostgreSQL 18 preview - 使用扩展统计信息提高hash join bucket估算准确度

PostgreSQL 18 这个提交旨在使用用户自定义统计信息(扩展统计信息)来改进 PostgreSQL 在哈希连接 (Hash Join) 中对桶 (bucket) 大小的估计，从而提高查询优化器的准确性，并最终提升查询性能。

例如下面的 CREATE STATISTICS extstat_sb_2 (ndistinct) ON x, y, z FROM sb_2;

+--  
+-- Extended statistics on sb_2 (x, y, z) improve a bucket size estimation,  
+-- and the optimizer may choose hash join.  
+--  
+CREATE TABLE sb_1 AS  
+  SELECT gs % 10 AS x, gs % 10 AS y, gs % 10 AS z  
+  FROM generate_series(1, 1e4) AS gs;  
+CREATE TABLE sb_2 AS  
+  SELECT gs % 49 AS x, gs % 51 AS y, gs % 73 AS z, 'abc' || gs AS payload  
+  FROM generate_series(1, 1e4) AS gs;  
+ANALYZE sb_1, sb_2;  
+-- During hash join estimation, the number of distinct values on each column  
+-- is calculated. The optimizer selects the smallest number of distinct values  
+-- and the largest hash bucket size. The optimizer decides that the hash
+-- bucket size is quite big because there are possibly many correlations.  
+EXPLAIN (COSTS OFF) -- Choose merge join  
+SELECT * FROM sb_1 a, sb_2 b WHERE a.x = b.x AND a.y = b.y AND a.z = b.z;  
+                         QUERY PLAN                            
+-------------------------------------------------------------  
+ Merge Join  
+   Merge Cond: ((a.z = b.z) AND (a.x = b.x) AND (a.y = b.y))  
+   ->  Sort  
+         Sort Key: a.z, a.x, a.y  
+         ->  Seq Scan on sb_1 a  
+   ->  Sort  
+         Sort Key: b.z, b.x, b.y  
+         ->  Seq Scan on sb_2 b  
+(8 rows)  
+  
+-- The ndistinct extended statistics on (x, y, z) provides more reliable value  
+-- of bucket size.  
+CREATE STATISTICS extstat_sb_2 (ndistinct) ON x, y, z FROM sb_2;  
+ANALYZE sb_2;  
+EXPLAIN (COSTS OFF) -- Choose hash join  
+SELECT * FROM sb_1 a, sb_2 b WHERE a.x = b.x AND a.y = b.y AND a.z = b.z;  
+                         QUERY PLAN                           
+------------------------------------------------------------  
+ Hash Join  
+   Hash Cond: ((a.x = b.x) AND (a.y = b.y) AND (a.z = b.z))  
+   ->  Seq Scan on sb_1 a  
+   ->  Hash  
+         ->  Seq Scan on sb_2 b  
+(5 rows)  
+  
+DROP TABLE sb_1, sb_2 CASCADE;  

https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=6bb6a62f3cc45624c601d5270673a17447734629

Use extended stats for precise estimation of bucket size inhash join  
author Alexander Korotkov <[email protected]>   
Mon, 10 Mar 2025 11:42:00 +0000 (13:42 +0200)  
committer Alexander Korotkov <[email protected]>   
Mon, 10 Mar 2025 11:42:01 +0000 (13:42 +0200)  
commit 6bb6a62f3cc45624c601d5270673a17447734629  
tree 89edafbedad663606841de35f3587696a0e47ba5 tree  
parent fae535da0ac2a8d0bb279cc66d62b0dcc4b5409b commit | diff  
Use extended stats for precise estimation of bucket size inhash join  
Recognizing the real-life complexity where columns in the table often have  
functional dependencies, PostgreSQL's estimation of the number of distinct  
values over a set of columns can be underestimated (or much rarely,  
overestimated) when dealing with multi-clause JOIN.  In the case of hash  
join, it can end up with a small number of predicted hash  buckets and, as  
a result, picking non-optimal merge join.  

To improve the situation, we introduce one additional stage of bucket size  
estimation - having two or more join clauses estimator lookup for extended  
statistics and use it for multicolumn estimation.  Clauses are grouped into  
lists, each containing expressions referencing the same relation.  The result  
of the multicolumn estimation made over such a list is combined with others  
according to the caller's logic.  Clauses that are not estimated are returned  
to the callerfor further estimation.  
Discussion: https://postgr.es/m/52257607-57f6-850d-399a-ec33a654457b%40postgrespro.ru  
Author: Andrei Lepikhov <[email protected]>  
Reviewed-by: Andy Fan <[email protected]>  
Reviewed-by: Tomas Vondra <[email protected]>  
Reviewed-by: Alena Rybakina <[email protected]>  
Reviewed-by: Alexander Korotkov <[email protected]>  

核心问题：

在哈希连接中，准确估计哈希桶的大小至关重要。 如果估计的桶数量太少，会导致哈希冲突增加，降低哈希连接的效率，甚至导致优化器错误地选择效率较低的归并连接 (Merge Join)。

PostgreSQL 在估计不同值的数量时，可能会遇到问题，尤其是在处理多列连接 (multi-clause JOIN) 时。 这是因为现实世界中，表中的列通常存在函数依赖关系 (functional dependencies)。 例如，一个城市对应一个邮政编码。 如果优化器没有考虑到这些依赖关系，它可能会低估（或极少数情况下高估）一组列中不同值的数量。

补丁的解决方案：

这个补丁引入了一个额外的阶段，用于估计哈希桶的大小，即使用扩展统计信息 (extended stats) 来更精确地估计桶的大小。

具体来说，它做了以下几点：

1. 扩展统计信息查找： 对于包含两个或更多连接子句 (join clauses) 的情况，补丁会查找扩展统计信息，并将其用于多列估计。 扩展统计信息可以捕捉列之间的相关性，从而提供更准确的估计。
2. 子句分组： 连接子句被分组到列表中，每个列表包含引用相同关系的表达式。 这样做是为了方便对同一关系中的多个列进行联合估计。
3. 多列估计： 对每个列表进行多列估计，得到该列表中不同值的数量。
4. 结果组合： 来自不同列表的多列估计结果会根据调用者的逻辑进行组合，以得到最终的桶大小估计。
5. 未估计的子句返回： 无法使用扩展统计信息估计的子句会返回给调用者，以便进行进一步的估计。

为什么这个补丁重要：

• 更精确的桶大小估计： 通过使用扩展统计信息，这个补丁可以更精确地估计哈希连接中的桶大小。
• 提高哈希连接的效率： 更精确的桶大小估计可以减少哈希冲突，提高哈希连接的效率。
• 更优的查询计划选择： 更准确的估计可以帮助优化器选择更优的查询计划，例如，避免错误地选择归并连接。
• 处理函数依赖关系： 这个补丁可以更好地处理列之间的函数依赖关系，从而提高估计的准确性。
• 提升查询性能： 最终，这个补丁可以提升查询性能，特别是对于涉及多列连接的查询。

总结：

这个补丁通过利用扩展统计信息来更精确地估计哈希连接中的桶大小，从而提高了 PostgreSQL 查询优化器的准确性，并最终提升了查询性能。 它特别关注处理列之间的函数依赖关系，这在现实世界的数据库中非常常见。