PostgreSQL洞察与知识汇总（一百五十三）｜【性能】将OR子句转换为ANY表达式
最编程
2024-10-14 11:10:53
...
目录结构
注：提前言明 本文借鉴了以下博主、书籍或网站的内容，其列表如下：
1、参考书籍：《PostgreSQL数据库内核分析》
2、参考书籍：《数据库事务处理的艺术：事务管理与并发控制》
3、PostgreSQL数据库仓库链接，点击前往
4、日本著名PostgreSQL数据库专家 铃木启修 网站主页，点击前往
5、参考书籍：《PostgreSQL中文手册》
6、参考书籍：《PostgreSQL指南：内幕探索》，点击前往
7、参考书籍：《事务处理 概念与技术》
1、本文内容全部来源于开源社区 GitHub和以上博主的贡献，本文也免费开源（可能会存在问题，评论区等待大佬们的指正）
2、本文目的：开源共享 抛砖引玉 一起学习
3、本文不提供任何资源 不存在任何交易 与任何组织和机构无关
4、大家可以根据需要自行 复制粘贴以及作为其他个人用途，但是不允许转载 不允许商用 （写作不易，还请见谅 ????）
5、本文内容基于PostgreSQL master源码开发而成
将 OR 子句转换为 ANY 表达式
- 文章快速说明索引
- 功能实现背景说明
- 功能实现源码解析
- or_to_any_transform_limit
- process_duplicate_ors
- transform_or_to_any
- 原理讲解
- 调试情况1
- 调试情况2
- 调试情况3
- 调试情况4
- 社区争议回退原因
文章快速说明索引
学习目标：
做数据库内核开发久了就会有一种 少年得志，年少轻狂 的错觉，然鹅细细一品觉得自己其实不算特别优秀 远远没有达到自己想要的。也许光鲜的表面掩盖了空洞的内在，每每想到于此，皆有夜半临渊如履薄冰之感。为了睡上几个踏实觉，即日起 暂缓其他基于PostgreSQL数据库的兼容功能开发，近段时间 将着重于学习分享Postgres的基础知识和实践内幕。
学习内容：（详见目录）
1、将 OR 子句转换为 ANY 表达式
学习时间：
2024年10月05日 12:16:59
学习产出：
1、PostgreSQL数据库基础知识回顾 1个
2、**** 技术博客 1篇
3、PostgreSQL数据库内核深入学习
注：下面我们所有的学习环境是Centos8+PostgreSQL master +Oracle19C+MySQL8.0
postgres=# select version();
version
------------------------------------------------------------------------------------------------------------
PostgreSQL 18devel on x86_64-pc-linux-gnu, compiled by gcc (GCC) 8.5.0 20210514 (Red Hat 8.5.0-21), 64-bit
(1 row)
postgres=#
#-----------------------------------------------------------------------------#
SQL> select * from v$version;
BANNER Oracle Database 19c EE Extreme Perf Release 19.0.0.0.0 - Production
BANNER_FULL Oracle Database 19c EE Extreme Perf Release 19.0.0.0.0 - Production Version 19.17.0.0.0
BANNER_LEGACY Oracle Database 19c EE Extreme Perf Release 19.0.0.0.0 - Production
CON_ID 0
#-----------------------------------------------------------------------------#
mysql> select version();
+-----------+
| version() |
+-----------+
| 8.0.27 |
+-----------+
1 row in set (0.06 sec)
mysql>
功能实现背景说明
大概描述一下此次的patch的内容，如下：
- 在优化的初步阶段，当我们仍在处理表达式树时，将
(expr op C1) OR (expr op C2) ...替换为expr op ANY(ARRAY[C1,C2, ...])- 这里 Cn 是第 n 个常量表达式，“
expr”是非常量表达式，“op”是一个返回布尔结果并具有通勤器的运算符commuter（用于表达式的常量和非常量部分的反向顺序的情况，如Cn op expr）- 有时它会导致计划不理想。这就是为什么有
or_to_any_transform_limitGUC。它指定触发 OR-to-ANY 转换的 OR 表达式中参数长度的阈值。通常，更多可分组的 OR 参数意味着转换获胜的可能性大于失败的可能性
postgres=# create table t1 (id int primary key, name text);
CREATE TABLE
postgres=#
postgres=# insert into t1 values (1, 'oracle');
INSERT 0 1
postgres=# insert into t1 values (2, 'mysql');
INSERT 0 1
postgres=# insert into t1 values (3, 'Sql Server');
INSERT 0 1
postgres=# insert into t1 values (4, 'postgresql');
INSERT 0 1
postgres=# select * from t1 where id = 2 or id = 4;
id | name
----+------------
2 | mysql
4 | postgresql
(2 rows)
postgres=#
postgres=# explain(costs off, verbose) select * from t1 where id = 2 or id = 4;
QUERY PLAN
----------------------------------------------
Bitmap Heap Scan on public.t1
Output: id, name
Recheck Cond: ((t1.id = 2) OR (t1.id = 4))
-> BitmapOr
-> Bitmap Index Scan on t1_pkey
Index Cond: (t1.id = 2)
-> Bitmap Index Scan on t1_pkey
Index Cond: (t1.id = 4)
(8 rows)
postgres=#
postgres=# explain(costs off, verbose) select * from t1 where id = ANY ('{2, 4}'::integer[]);
QUERY PLAN
--------------------------------------------------------
Bitmap Heap Scan on public.t1
Output: id, name
Recheck Cond: (t1.id = ANY ('{2,4}'::integer[]))
-> Bitmap Index Scan on t1_pkey
Index Cond: (t1.id = ANY ('{2,4}'::integer[]))
(5 rows)
postgres=#
然后看一下该patch的作用，如下：
postgres=# SET or_to_any_transform_limit = 1;
SET
postgres=# explain(costs off, verbose) select * from t1 where id = 2 or id = 4;
QUERY PLAN
--------------------------------------------------------
Bitmap Heap Scan on public.t1
Output: id, name
Recheck Cond: (t1.id = ANY ('{2,4}'::integer[]))
-> Bitmap Index Scan on t1_pkey
Index Cond: (t1.id = ANY ('{2,4}'::integer[]))
(5 rows)
postgres=#
postgres=# SET or_to_any_transform_limit = 2;
SET
postgres=# explain(costs off, verbose) select * from t1 where id = 2 or id = 4;
QUERY PLAN
--------------------------------------------------------
Bitmap Heap Scan on public.t1
Output: id, name
Recheck Cond: (t1.id = ANY ('{2,4}'::integer[]))
-> Bitmap Index Scan on t1_pkey
Index Cond: (t1.id = ANY ('{2,4}'::integer[]))
(5 rows)
postgres=#
postgres=# SET or_to_any_transform_limit = 3;
SET
postgres=# explain(costs off, verbose) select * from t1 where id = 2 or id = 4;
QUERY PLAN
----------------------------------------------
Bitmap Heap Scan on public.t1
Output: id, name
Recheck Cond: ((t1.id = 2) OR (t1.id = 4))
-> BitmapOr
-> Bitmap Index Scan on t1_pkey
Index Cond: (t1.id = 2)
-> Bitmap Index Scan on t1_pkey
Index Cond: (t1.id = 4)
(8 rows)
postgres=#
关于上面GUC参数的解释，如下：
设置 OR 表达式中参数的最小长度，超过该长度，规划器将尝试查找并将多个相似的 OR 表达式分组为 ANY 表达式。此转换的分组技术基于变量侧的等价性。这种表达式的一侧必须是常量子句，另一侧必须包含变量子句。默认值为 5。值 -1 完全禁用转换。
此 OR-to-ANY 转换的优点是查询规划和执行速度更快。在某些情况下，此转换还会导致更有效的计划，其中包含单个索引扫描而不是多个位图扫描。但是，当不同的 OR 参数更适合匹配不同的索引时，它也可能导致规划回归。当它们具有不同的匹配部分索引或查询中使用的其他列的分布不同时，可能会发生这种情况。通常，更多可分组的 OR 参数意味着转换获胜的可能性大于失败的可能性。
但是因为设计和实现上存在争议，目前该patch已回滚 如下：
不过本着内核开发人员学习的态度，我们还是看一下其内部的实现。(从社区的态度来看 后面说不定还会归来)
功能实现源码解析
or_to_any_transform_limit
首先看一下该GUC的定义，如下：
// src/backend/utils/misc/guc_tables.c
{
{"or_to_any_transform_limit", PGC_USERSET, QUERY_TUNING_OTHER,
gettext_noop("Set the minimum length of the list of OR clauses to attempt the OR-to-ANY transformation."),
gettext_noop("Once the limit is reached, the planner will try to replace expression like "
"'x=c1 OR x=c2 ..' to the expression 'x = ANY(ARRAY[c1,c2,..])'"),
GUC_EXPLAIN
},
&or_to_any_transform_limit,
5, -1, INT_MAX,
NULL, NULL, NULL
},
言简意赅：正如上面演示那样，设置 OR 子句列表的最小长度以尝试进行 OR 到 ANY 的转换。
process_duplicate_ors
接下来看一下今天学习的重点，如下：
// src/backend/optimizer/prep/prepqual.c
/*
* process_duplicate_ors
* Given a list of exprs which are ORed together, try to apply
* the inverse OR distributive law.
* 给定一个进行 “或” 运算的表达式列表，尝试应用逆 “或” 分配律。
*
* Returns the resulting expression (could be an AND clause, an OR
* clause, or maybe even a single subexpression).
* 返回结果表达式（可以是 AND 子句、OR 子句、甚至可能是单个子表达式）。
*/
static Expr *
process_duplicate_ors(List *orlist);
前置条件：关于这个函数的内部，请看 张树杰 博客：
- PostgreSQL代码分析，查询优化部分，process_duplicate_ors，点击前往
这里详细分析了每一行，我这里不再赘述。其中的示例，如下：
postgres=# create table ta(a int primary key);
CREATE TABLE
postgres=# create table tb(b int primary key);
CREATE TABLE
postgres=#
postgres=# create table tc(c int primary key);
CREATE TABLE
postgres=# create table td(d int primary key);
CREATE TABLE
postgres=#
postgres=# insert into ta values (1);
INSERT 0 1
postgres=# insert into tb values (1);
INSERT 0 1
postgres=# insert into tc values (1);
INSERT 0 1
postgres=# insert into td values (1);
INSERT 0 1
postgres=# insert into tb values (2);
INSERT 0 1
postgres=# insert into tc values (3);
INSERT 0 1
postgres=# insert into td values (4);
INSERT 0 1
postgres=# explain select * from ta, tb, tc, td WHERE (A=1 AND B=1) OR (A=1 AND C=1) OR (A=1 AND D=1);
QUERY PLAN
-----------------------------------------------------------------------------------------
Nested Loop (cost=0.15..331708934.17 rows=19499851 width=16)
Join Filter: ((tb.b = 1) OR (tc.c = 1) OR (td.d = 1))
-> Nested Loop (cost=0.15..81392.30 rows=6502500 width=12)
-> Nested Loop (cost=0.15..69.17 rows=2550 width=8)
-> Index Only Scan using ta_pkey on ta (cost=0.15..8.17 rows=1 width=4)
Index Cond: (a = 1)
-> Seq Scan on tb (cost=0.00..35.50 rows=2550 width=4)
-> Materialize (cost=0.00..48.25 rows=2550 width=4)
-> Seq Scan on tc (cost=0.00..35.50 rows=2550 width=4)
-> Materialize (cost=0.00..48.25 rows=2550 width=4)
-> Seq Scan on td (cost=0.00..35.50 rows=2550 width=4)
(11 rows)
postgres=#
函数流程解释 简要如下：
-
处理空 OR 列表：
- 如果传入的
orlist为空（没有子句），返回一个恒为FALSE的布尔常量，表示 OR 为空的情况。
- 如果传入的
-
处理单一子句：
- 如果
orlist只有一个子句，直接返回该子句，因为一个单独的OR子句不需要进一步简化。
- 如果
-
选择最短的 AND 子句作为参考：
- 遍历
orlist，找到最短的 AND 子句作为参考。如果我们发现一个不是 AND 的子句，我们可以将其视为一个单元素 AND 子句，该子句必然是最短的。
- 遍历
-
消除参考子句中的重复：
- 对参考子句进行去重，以确保参考列表中没有重复。
-
查找所有 OR 子句的共同条件：
- 遍历参考子句，检查每个参考子句是否存在于所有 OR 子句中。如果参考子句出现在所有 OR 子句中，则将其标记为“胜出者” (
winners)。
- 遍历参考子句，检查每个参考子句是否存在于所有 OR 子句中。如果参考子句出现在所有 OR 子句中，则将其标记为“胜出者” (
-
处理没有胜出者的情况：
- 如果没有共同的胜出子句，检查 OR 子句列表的长度。如果 OR 子句足够长，则尝试将其转换为 SAOP（
ScalarArrayOp: Scalar Array Op，即标量数组操作）。转换后返回优化后的 OR 子句列表。
- 如果没有共同的胜出子句，检查 OR 子句列表的长度。如果 OR 子句足够长，则尝试将其转换为 SAOP（
-
有胜出者的情况，生成由剩余子句组成的新 OR 列表：
- 生成一个新的 OR 列表，去除已在所有子句中胜出的条件。如果任何子句退化为空，则会出现类似 (A AND B) OR (A) 的情况，该情况可以简化为 A — 也就是说，OR 的其他分支中的附加条件无关紧要。请注意，由于我们使用
list_difference，因此 AND 子句中多次出现的获胜子句将被自动删除。
- 生成一个新的 OR 列表，去除已在所有子句中胜出的条件。如果任何子句退化为空，则会出现类似 (A AND B) OR (A) 的情况，该情况可以简化为 A — 也就是说，OR 的其他分支中的附加条件无关紧要。请注意，由于我们使用
-
再次尝试进行 SAOP 转换：
- 再次检查新生成的 OR 列表，如果其长度达到转换限制，则尝试将其转换为 SAOP。
-
处理特殊情况并构建最终的表达式：
- 如果新的 OR 列表不为空，则将其与胜出的子句合并。如果简化的 OR 不是退化的，则将其附加到获胜者列表中，正确处理一个元素的特殊情况（这真的会发生吗？）。此外，还要小心维护 AND/OR 平坦度，以防我们拉出子子 OR 子句。
-
最后 若winners列表长度为1返回该表达式；否则返回构造的 AND 子句，再次警惕单个元素和 AND/OR 平坦度。
接下来 不急着分析transform_or_to_any函数，我们对函数process_duplicate_ors调试一下：
第一个SQL，如下：
explain select * from ta, tb, tc, td WHERE (A=1 AND B=1) OR (A=1 AND C=1) OR (A=1 AND D=1);
如上，参考list这里选择的就是A=1 AND B=1，接下来就是winners list的获得：
该过程就是reference list中的每一个，都在orlist的元素中检查是否出现 是则进入winners list。否 则不再继续向下检查，直接跳过 如下：
因为这三个都是and子句，然后又因为winners list: A=1不为空。于是这里的list_difference将自动进行裁剪，如下：
裁剪拼接之后的neworlist，实际上就是：B=1、C=1和D=1。
最后先是以递归方式将嵌套的 OR 子句展平为单个 or 子句列表 B=1 or C=1 or D=1，然后以递归方式将嵌套的 AND 子句展平为单个 and 子句列表 (A=1) AND (B=1 or C=1 or D=1)。此刻的函数堆栈，如下：
process_duplicate_ors(List * orlist)
find_duplicate_ors(Expr * qual, _Bool is_check)
canonicalize_qual(Expr * qual, _Bool is_check)
preprocess_expression(PlannerInfo * root, Node * expr, int kind)
preprocess_qual_conditions(PlannerInfo * root, Node * jtnode)
subquery_planner(PlannerGlobal * glob, Query * parse, PlannerInfo * parent_root, _Bool hasRecursion, double tuple_fraction, SetOperationStmt * setops)
standard_planner(Query * parse, const char * query_string, int cursorOptions, ParamListInfo boundParams)
planner(Query * parse, const char * query_string, int cursorOptions, ParamListInfo boundParams)
pg_plan_query(Query * querytree, const char * query_string, int cursorOptions, ParamListInfo boundParams)
standard_ExplainOneQuery(Query * query, int cursorOptions, IntoClause * into, ExplainState * es, const char * queryString, ParamListInfo params, QueryEnvironment * queryEnv)
ExplainOneQuery(Query * query, int cursorOptions, IntoClause * into, ExplainState * es, const char * queryString, ParamListInfo params, QueryEnvironment * queryEnv)
ExplainQuery(ParseState * pstate, ExplainStmt * stmt, ParamListInfo params, DestReceiver * dest)
standard_ProcessUtility(PlannedStmt * pstmt, const char * queryString, _Bool readOnlyTree, ProcessUtilityContext context, ParamListInfo params, QueryEnvironment * queryEnv, DestReceiver * dest, QueryCompletion * qc)
ProcessUtility(PlannedStmt * pstmt, const char * queryString, _Bool readOnlyTree, ProcessUtilityContext context, ParamListInfo params, QueryEnvironment * queryEnv, DestReceiver * dest, QueryCompletion * qc)
PortalRunUtility(Portal portal, PlannedStmt * pstmt, _Bool isTopLevel, _Bool setHoldSnapshot, DestReceiver * dest, QueryCompletion * qc)
FillPortalStore(Portal portal, _Bool isTopLevel)
PortalRun(Portal portal, long count, _Bool isTopLevel, _Bool run_once, DestReceiver * dest, DestReceiver * altdest, QueryCompletion * qc)
exec_simple_query(const char * query_string)
...
第二个SQL，如下：
explain select * from ta, tb, tc WHERE (A=1 AND B=1) OR (A=1 AND C=1) OR (A=1);
如上，在选择reference list的时候，首先and子句A=1 AND B=1进入；第二段长度也是2 忽略；第三段更短 因此成为reference list: A=1。
然后在随后的winners获取的二级循环中 成功匹配：
接下来在剪枝中，发生了退化degenerate case 如下：
这种情况下 实际上原条件(A=1 AND B=1) OR (A=1 AND C=1) OR (A=1)与A=1效果一样，于是后期处理如下：
postgres=# explain select * from ta, tb, tc WHERE (A=1 AND B=1) OR (A=1 AND C=1) OR (A=1);
QUERY PLAN
-----------------------------------------------------------------------------------
Nested Loop (cost=0.15..81392.30 rows=6502500 width=12)
-> Nested Loop (cost=0.15..69.17 rows=2550 width=8)
-> Index Only Scan using ta_pkey on ta (cost=0.15..8.17 rows=1 width=4)
Index Cond: (a = 1)
-> Seq Scan on tb (cost=0.00..35.50 rows=2550 width=4)
-> Materialize (cost=0.00..48.25 rows=2550 width=4)
-> Seq Scan on tc (cost=0.00..35.50 rows=2550 width=4)
(7 rows)
postgres=#
上面两个都可以抽取出公共项，即：winners list不为空。接下来 看第三个SQL：
explain select * from ta, tb, tc, td WHERE (A=1 AND B=1) OR (A=1 AND C=1) OR (D=1);
如上，reference此时就只有一个，然后检查是否是winners list。因为第一个检查就未匹配，此时winners将是空，那么将进入如下逻辑：
// src/backend/optimizer/prep/prepqual.c
/*
* If no winners, we can't do OR-to-ANY transformation.
*/
if (winners == NIL)
{
/*
* Make an attempt to group similar OR clauses into SAOP if the list
* is lengthy enough.
*/
if (or_to_any_transform_limit >= 0 &&
list_length(orlist) >= or_to_any_transform_limit)
orlist = transform_or_to_any(orlist);
/* Transformation could group all OR clauses to a single SAOP */
return (list_length(orlist) == 1) ?
(Expr *) linitial(orlist) : make_orclause(orlist);
}
因为我们这里没有开or_to_any的转换，那么最终返回的表达式还是make_orclause(orlist)，保持了原样：
postgres=# explain select * from ta, tb, tc, td WHERE (A=1 AND B=1) OR (A=1 AND C=1) OR (D=1);
QUERY PLAN
-------------------------------------------------------------------------------------------
Nested Loop (cost=0.00..1057270004879.88 rows=16594374899 width=16)
Join Filter: (((ta.a = 1) AND (tb.b = 1)) OR ((ta.a = 1) AND (tc.c = 1)) OR (td.d = 1