SQL优化器程序--Join重排这个特性的基础概念和算法(sql优化常用的15种方法)

本文的目标是解释Join重排这个特性的基础概念和算法，如果想快速了解并在MaxCompute上使用这个特性，请直接跳到“总结”。

简介

Join重排是经典的SQL优化问题。考虑3个表的自然连接 A ⋈ B ⋈ C ，在不影响最终结果集的前提下，可以改变连接的顺序为下列：

1. A ⋈ C ⋈ B
2. B ⋈ A ⋈ C
3. B ⋈ C ⋈ A
4. C ⋈ A ⋈ B
5. C ⋈ B ⋈ A

熟悉SQL开发的读者会明白，这个顺序可能极大影响SQL执行的效率。打个比方，A，B，C的数据量各自是100条记录，如果A ⋈ C的数据量是1条记录，A ⋈ B是100条记录，显然A ⋈ B ⋈ C的效率低于A ⋈ C ⋈ B，因为前者的中间结果是100条记录，而后者是1条，并且最终结果的数据量是相同的。因此我们得到结论1。

结论1：Join的顺序影响中间结果的数据量，决定了Join的执行效率

另外一种影响Join效率的原因是Join算法。考虑Hash Join算法（对MaxCompute熟悉的读者可以理解为MapJoin），它提前把右边表的数据建立一张哈希表，循环获取左边表的记录查表做Join。假设建立哈希表的代价很大，且随数据量线性递增，那么我们总希望更小的数据集在右边。假设A表是100条记录，B表是10条记录，那么A ⋈ B优于B ⋈ A。因此我们得到结论2。

结论2：Join的顺序影响具体Join算法的效率，决定了Join的执行效率

综上所述，Join的顺序很大程度决定了Join的执行效率。这么看来，在开发SQL程序的时候，我们一定要仔细安排Join的顺序，让它达到最优的执行效率？不尽然。事实上，Join重排的难度如此之大，以至于手工调整是不现实的。主要的难度体现在两部分：

1. 穷举和验证最优方案的算法复杂度是指数级的（NP hard问题）
2. 获取某个Join的中间结果数据量的代价很大。我们不得不实际执行一遍Join才能获知中间结果数据量，每个Join都可能花费数小时甚至数天。

因此必须借助机器自动优化。在最新的MaxCompute SQL 2.0中，基于代价的优化器（Cost Based Optimizer，CBO）已经包含了Join重排的优化规则。在本文中，我们尝试从算法、代价计算、数据量估计等方方面面解释Join重排，也会包含一部分CBO的基本概念。

问题分类

Join树

在SQL优化器程序中表达的Join大部分时候是一棵二叉树。把Join节点作为二叉树的节点，可以构建一棵Join树。

例如，上述的A ⋈ B ⋈ C生成的逻辑执行计划（Algebrized Tree）如下：

编辑

生成的Join树如下：

至此一切都很完美，每个查询都是树，直到有一种奇怪的查询闯进了这个森林。考虑以下Join：

SELECT * FROM A JOIN B ON A.id = B.id JOIN C ON B.id = C.id

显然，通过A.id = B.id and B.id = C.id可以推出另一个Join，即C.id = A.id，这时的Join"树"是这样的：

编辑

这种形态称为 有环 的Join树。有环在Join重排算法里会非常复杂，大部分的算法不支持环。当然我们可以考虑随机删除某个Join操作，保证整个Join树 无环 ，但是这么做会损失一些优化的可能性。

Join树形态

上文提到的Join树在SQL的逻辑表达中通常是一个 偏树 。考虑A ⋈ B ⋈ C ⋈ D，这棵偏树的形态如下：

编辑

我们称这种Join树为 左深（Left-deep）树 ，对应的也有 右深树 。在单机／单任务数据库上，我们只考虑这种形态的Join树就可以做Join重排，但是在分布式环境，我们还要考虑 稠密（Bushy）树 ，如下图所示：

编辑

显然，如果有更多计算节点，AB和CD可以并行执行，从而降低整体响应时间。大部分的Join重排算法只能支持左深树，我们会在后续提到稠密树的增强算法。MaxCompute SQL 2.0支持了稠密树的重排算法。

笛卡尔积

区别于自然连接，笛卡尔积将两边的输入做两层循环的完全展开。部分Join重排算法不支持笛卡尔积。

综上，我们有“有／无环”，“左深／稠密树”，“支持／不支持笛卡尔积”这三类8种问题分类。

动态规划算法

终于到了Join重排算法了！希望之前的概念解释没有吓跑你。首先看 动态规划算法 ，这是一个非常自然的Join重排算法，它最早是由P. Griffiths Selinger etl在1979年提出 [Selinger79]，并使用在数据库鼻祖级的系统System R上。

动态规划保留所有可能的Join顺序，加入到CBO的执行计划选项（被称为Memo的一个数据结构）中，最后由代价模型选择最优的Join顺序。为了避免代价被反复计算，使用动态规划的算法记录局部最优的代价。

这是一种穷举（exhaustive）算法，但是我们通常提到的Join重排都不是穷举算法，因为它的复杂度实在是太高了！考虑n个输入自由组建一棵左深树或稠密树的所有可能性，它的复杂度是卡特兰数序列，下表是一个直观的例子：

输入数 n左深树 2^(n−1)稠密树 2^(n−1) * C(n − 1)1112223484840516224632134476484488128549129256366080105122489344

在MaxCompute中，我们最初利用了这个算法，因为它在理论上总能找到最优解（区别于后续我们提到的算法，理论上只能找到次优解），并且支持稠密树和笛卡尔积。为了降低它的复杂度，我们用了一些限制：

1. 不区分A ⋈ B和B ⋈ A（交换）
2. 仅处理n<=5的情况，当n>5时，分裂为多个n<=5的组分别做Join重排

截止本文，MaxCompute线上仍然使用以上限制的动态规划算法。你可以通过set odps.optimizer.cbo.rule.filter.white=pojr打开Join重排。但是，正如我们看到的，这个算法复杂度非常大，限制也非常多。我们在最新未发布的版本使用了启发式算法替换它。

启发式算法

为了降低动态规划算法的复杂度，我们必须在Join重排算法上就开始做剪枝，而不是把所有可能性都留下来。需要解释的是，启发式算法同样是建立在动态规划算法上的一种优化，而不是独立的自成一套。

既然要“启发”，就需要一个定义什么是 好 的Join。我们需要引入一个评估体系，被称为cost function（如果读者对CBO熟悉，这里的cost不是指CBO框架的代价，而仅仅是用于评估Join顺序好坏的一个公式，因为此时Join并没有build，我们无法获取准确的cost）。为了简化问题，接下来我们使用的cost function都等于Join的输出数据量（cardinality。有关cardinality的估计算法是另一个大话题，留到下一篇文章解释，此处请读者先假定我们有能力获取一个精确的cardinality）。选择执行计划的准则就是选择cost最小的那个。

最重要的启发式算法有贪婪算法和GOO算法两种。MaxCompute采用了增强的GOO算法。

贪婪算法

贪婪算法考虑逻辑执行计划，以输入为节点，每次选取cost最小的节点直到所有节点都被选取，从而组建一个左深树作为最后的Join重排顺序。贪婪算法只支持左深树。

最基础的贪婪算法的伪代码如下：

ø = {所有输入}

orders = {}

while ø != {}

n = ni of min(cost(orders ⋈ ni)) for ni in ø

orders = orders + n

ø = ø - n

return orders

实践中，这个算法很容易受到第一个输入选择的影响，因为首次选择节点，cost({} ⋈ ni)，还没有任何Join，这个cost被定义为ni的cardinality，小表会优先选择，这并不一定是最好的。因此一个改进的算法是在首次选择时，所有表都有机会，伪代码如下：

ø = {所有输入}

options = {}

for n in ø

orders = {n}

rest = ø - n

while rest != {}

n = ni of min(cost(orders ⋈ ni)) for ni in ø

orders = orders + n

ø = ø - n

options = options + orders

return i of min(cost(i)) for i in options

贪婪算法的好处是，它每次选择的一个Join都是可以实际执行的（区别于下文的GOO算法，选择的可能是一个中间Join），因此我们很容易计算cost。和所有的启发式算法一样，它只能获得次优解。考虑到它不支持稠密树，我们没有选择这个算法。

GOO算法

区别于贪婪算法以输入为节点，GOO（Greedy Operator Ordering）考虑Join树，以Join为节点。它循环选择一个节点，和已选择的所有节点尝试Join并选择代价最小的那个，生成一个新的节点，直到所有的节点都被选择了。

考虑A ⋈ B ⋈ C ⋈ D的例子，如果cost的估计结果是 A ⋈ B < C ⋈ D < B ⋈ C，GOO算法的执行过程如下图所示：

编辑

这个算法的复杂度比贪婪算法高，cost估计从实体的输入改为抽象的Join，难度更大，但是它的优势在于支持稠密树。MaxCompute最新的版本使用了这种算法。

KBZ算法

KBZ或IIKBZ是在cost function满足ASI（adjacent sequence interchange）条件下理论最优的启发式算法。因为MaxCompute无法满足ASI，且KBZ仅支持左深树，我们没有考虑KBZ算法。感兴趣的读者可以参考 [Ibaraki84]。

随机算法简介

我们之前讨论了动态规划算法，也讨论了启发式算法。这两种算法是两个极端，前者保留所有的Join形态，后者只保留唯一的Join形态，这是算法复杂度和最优解之间的tradeoff。实际操作中，这两个极端通常不是好的策略，我们希望有更折中的办法，这就是 随机算法 。

Random Walk算法 是最基础的随机算法。在次优解的基础上随机改变一些排序，尝试查找更优的方案。__Iterative Random Walk算法__ 做了改进，避免Random Walk生成的环。

折中的考量最后回到了基本的最优化问题上。数学上的一些算法也被应用于Join重排，讨论比较多的包括 模拟退火算法 和 基因算法 [Steinbrunn]。

为什么MySQL需要日志系统？

让我们从一个最基础的数据库操作说起：

// 用户消费100元 UPDATE account SET balance = balance - 100 WHERE id = 1;

这条简单的SQL语句，实际上给数据库带来了三大挑战：

• 可靠性问题：如果数据库突然宕机，这笔交易记录会不会丢失？一致性问题：如果用户要求退款，如何安全地回滚这笔交易？同步问题：如何确保其他数据库节点也正确记录了这笔交易？

为解决这些问题，MySQL设计了三种核心日志：

数据库操作 ──────────────────┐

↓ ┌─── Redo Log（临时记事本）

│ 记录："账户1减少100元" │

作用：确保交易记录不丢失 │

├─── Undo Log（原始凭证）

│ 记录："账户1原有500元" │ 作用：随时可以撤销交易 │

└─── Binlog（总账本） 记录："完整交易记录" 作用：用于数据同步和备份

编辑

二、重做日志（Redo Log）：数据库的"草稿纸"

1. 场景：会计小徐的烦恼

超市收银员小徐要记录1000笔交易。

传统方式（没有Redo Log）：

-- 每笔交易都要立即写入硬盘

UPDATE accounts SET balance = balance + 100; UPDATE products SET stock = stock - 1;

结果： ┌─────────────────────┐

│ ❌ 频繁随机写入硬盘 │

│ ❌ I/O效率极低 │

│ ❌ 系统性能下降 │

└─────────────────────┘

Redo Log的解决方案：

1. 先写入速记本（Redo Log）

┌────────────────────┐

│ 交易1: +100元,-1件 │

│ 交易2: +200元,-2件 │ ➜ 顺序写入，速度快

│ ... │

└────────────────────┘

2. 数据先放内存

┌────────────────┐

│ 内存中快速汇总 │ ➜ 响应迅速

└────────────────┘

3. 定期整理同步

┌────────────────┐

│ 批量写入硬盘 │ ➜ 提高效率

└────────────────┘

2. Redo Log工作原理详解

以顾客购买2箱牛奶为例：

// 顾客买了2箱牛奶（每箱100元） UPDATE accounts SET balance = balance + 200; UPDATE stock SET quantity = quantity - 2;

步骤1：速记本记录（Redo Log）

在Redo Log中记录交易信息：

交易编号时间操作类型表名修改内容状态

08K0109:01:01accountsbalance=1000balance=1200->

08K00T00209:01:01stockquantity=100quantity=98->

08K.OETH.PRO1115800109:01:01UPDATEaccounts账户余额+200已记录08K.PETH.PRO1114800209:01:01UPDATEstock牛奶库存-2已记录

特点：

• 顺序写入：像流水账，效率高记录简单：快速记录交易信息

步骤2：临时汇总（内存）

在内存中快速更新数据：

账户余额现金1200商品库存数量牛奶98

特点：

• 快速更新：客户立即看到结果数据在内存中：但断电会丢失

步骤3：持久化阶段，定期刷盘

在以下时机将数据写入硬盘：

• 营业员交接班时系统空闲时速记本快写满时固定时间间隔

Redo Log 工作流程图：

编辑

三、回滚日志（Undo Log）：数据库的"后悔药"

1. 场景：超市的退货处理

传统退货方式（没有Undo Log）：

现代方式（使用Undo Log）

• 找到原始购买记录确认购买价格是100元确认库存状态可以安全退货

2. Undo Log 工作原理详解

场景：用户下单扣款

// 顾客购买2箱牛奶

UPDATE accounts SET balance = balance + 200; // 收款200元

UPDATE stock SET quantity = quantity - 2; // 库存减2

交易记录阶段（Undo Log记录）

编号时间表名修改前数据修改后数据回滚指针08K0109:01:01accountsbalance=1000balance=1200-> 08K00T00209:01:01stockquantity=100quantity=98-> 08K.LETH.PRO11178T001T00309:05:30accountsbalance=1200balance=1000-> 08K02T00409:05:30stockquantity=98quantity=100-> T003

数据版本链（MVCC实现）：

牛奶库存记录的版本链： +-------------------------+ | 当前版本：98箱 | | 交易号：T002 | +-------------------------+ ↓ +-------------------------+ | 上一版本：100箱 | | 交易号：T001 | +-------------------------+ ↓ +-------------------------+ | 初始版本：100箱 | | 交易号：T000 | +-------------------------+

Undo Log 工作流程图：

编辑

3. Undo Log的两大作用

(1) 支持事务回滚

• 记录数据修改前的状态支持出错时回滚保证事务原子性

(2) 实现MVCC（多版本并发控制）

• 不同事务看到不同版本的数据提高并发性能避免加锁带来的性能问题

四、二进制日志（binlog）：数据库的"保险箱"

1. 场景：连锁超市的账务管理

小徐是连锁超市的总经理，每天要处理这些数据管理问题：

场景一：商品管理 总店：上架100种新商品 ┌─────────────────┐ │ 商品1: 牛奶 │ │ 商品2: 面包 │ ➜ 分店：一个个手动添加？ │ ...100条记录... │ └─────────────────┘ 场景二：数据安全 ┌─────────────────┐ │ 昨日销售数据 │ ➜ 系统崩溃，数据丢失！ └─────────────────┘ 场景三：变更追踪 老板：这个商品谁改的价格？ 小徐：¯\_(ツ)_/¯ 不知道...

而有了Binlog（二进制日志）后：

MySQL Binlog ├── 自动同步 │ 总店改价格 ──➜ 所有分店秒级更新 │ ├── 数据保护 │ 系统崩溃 ──➜ 从日志恢复数据 │ └── 操作追踪 谁改了价格？──➜ 查看变更历史

2. Binlog的记录格式：如何记录数据变更？

让我们看看Binlog是如何记录数据变更的：

-- 一笔简单的商品价格调整 UPDATE products SET price = 98 WHERE name = '牛奶';

这条SQL语句在Binlog中有三种不同的记录方式：

(1) STATEMENT格式：记录SQL语句

# 直接记录SQL UPDATE products SET price = price * 0.9 WHERE category = '饮品'; 优势：日志量小 风险：可能导致主从不一致（比如NOW()函数）

(2) ROW格式：记录数据变化

{ "before": {"id": 1, "name": "牛奶", "price": 100}, "after": {"id": 1, "name": "牛奶", "price": 90} } 优势：数据准确 特点：日志量较大

(3) MIXED格式：智能选择

# 根据SQL类型自动选择格式 简单UPDATE：使用STATEMENT 复杂函数：使用ROW

五、三大日志协同工作机制

以顾客购买2箱牛奶为例，操作内容如下：

• 更新库存（-2箱）更新账户（+200元）

1. 两阶段提交工作流程

(1) 第一阶段（Prepare）：

记录原始数据（Undo Log）：

• 库存：100箱账户：1000元

更新内存数据：

• 库存：98箱账户：1200元

记录操作状态（Redo Log）：

• 状态：准备中内容：库存-2，账户+200

(2) 第二阶段（Commit）：

记录交易信息（Binlog）：

• 时间：2025-04-14 09:00:00操作：售出牛奶2箱，收款200元

标记操作完成（Redo Log）：

• 状态：已完成

详细的执行流程表：

步骤操作日志类型内容状态1记录原数据Undo Log库存=100，余额=1000已记录2更新内存Buffer Pool库存=98，余额=1200已更新3预提交Redo Log更新操作记录prepare4记录变更Binlog交易详细信息已写入5最终提交Redo Log更新操作记录commit

两阶段提交流程图：

编辑

扩展问题

稠密树偏好

像MaxCompute这样的分布式系统下，我们更偏好生成稠密树，因为分布式系统可以并行执行那些在树中同深度的Join。怎样表达这样的偏好是一个难题。

在我们的实现中，我们对cost function施加一个深度的惩罚（例如，每一级深度施加30%的cost惩罚），我们通过“深度厌恶”这个想法来表达“稠密树偏好”。

Join 分组

在现实中，某些Join可以被合并在一个分组里实现。如果读者熟悉MaxCompute，容易理解有两类分组：

1. 对于Sorted Merge Join，当参与Join的每一路输入，Join key都是相同的，可以在一个task完成。
2. 对于Map Join，当大表是相同的，可以在一个map里完成。

显然，Join分组很大程度影响了代价，从而影响了最优顺序。我们在Join重排的实现会保留两种optional plan：合并的方案和不合并的方案，留给CBO框架去选择最优方案。

总结

这篇文档中，我们解释了Join重排这一优化的意义、概念和经典的几种算法。

1. 动态规划的算法总能找到最优方案，但是复杂度是最高的。
2. 启发式算法的复杂度最低，只能找到次优解。
3. 随机算法的效果是上面两种算法的折中。

MaxCompute最新的算法使用了启发式的GOO算法。在线上运行的MaxCompute还在使用受限的动态规划算法。从经典的数据仓库测试集TPC-H的测试发现，使用受限的动态规划算法可以帮助我们获得额外的8%以上的性能提升。

Join重排是一个较激进的优化规则，考虑到CBO无法完美估计数据量（这在我们的后续文章中解释），打开这个规则可能会产生worst plan。这个worst plan的比例经过我们线上实测是非常低的，但是我们仍然不得不默认关闭Join重排规则，你可以尝试设置odps.optimizer.cbo.rule.filter.white=pojr来打开某个query或project的Join重排特性。