关于云计算:PolarDB-并行查询的前世今生

简介：本文会深刻介绍 PolarDB MySQL 在并行查问这一企业级查问减速个性上做的技术摸索、状态演进和相干组件的实现原理，所波及性能随 PolarDB MySQL 8.0.2 版本上线。

作者 | 遥凌
起源 | 阿里技术公众号

本文会深刻介绍 PolarDB MySQL 在并行查问这一企业级查问减速个性上做的技术摸索、状态演进和相干组件的实现原理，所波及性能随 PolarDB MySQL 8.0.2 版本上线。

一 背景

1 PolarDB

云的衰亡为古老而固执的数据库市场带来了新的倒退时机，据 Gartner 预测，到 2022 年，所有数据库中将有 75% 部署或迁徙到云平台，云原生数据库的诞生为各个数据库厂商、云服务供应商提供了弯道超车的绝好时机，看一下 AWS 在 Re:invent 2020 公布的 Babelfish，就能嗅到它在数据库市场的野心有多大。

AWS 在 2017 年发表的对于 Aurora 的这篇 paper[1]，引领了云原生关系型数据库的发展趋势，而作为国内最早布局云计算的厂商，阿里云也在 2018 年推出了本人的云原生关系数据库 PolarDB，和 Aurora 的理念统一，PolarDB 深度交融了云上基础设施，指标是在为客户提供云上特有的扩展性、弹性、高可用性的同时，可能具备更低的响应提早和更高的并发吞吐，其根本架构如下：

底层的分布式共享存储冲破了单机存储容量的限度，而且能够随用户的数据量增长主动弹性扩容，计算层则是一写多读的典型拓扑，利用 RDMA 提供的高速近程拜访能力来对消计算存储拆散带来的额定网络开销。

2 挑战

从上图能够看到，存储层将容许远大于单机的数据容量（目前是 128T），甚至线上会呈现一些用户，单表容量达到 xx T 的级别，这在基于 MySQL 主从复制的传统部署中是难以想象的。同时大量用户会有对业务数据的实时剖析诉求，如统计、报表等，但大家对 MySQL 的直观印象就是：小事务处理快，并发能力强，剖析能力弱，对于这些实时性剖析查问，该如何应答呢？

3 计划

首先要说的是，随着互联网的倒退，数据量的爆炸，肯定的数据分析能力、异构数据的解决能力开始成为事务型数据库的标配，MySQL 社区在 8.0 版本中也对本身的查询处理能力做了补强，包含对子查问的 transformation、hash join、window function 反对等，同时 PolarDB MySQL 优化器团队也做了大量工作来晋升对简单查问的解决能力，如统计信息加强、子查问更多样的 transformation、query cache 等。

并行查问 (Parallel Query) 是 PolarDB MySQL 在推出伊始就装备的查问减速性能，实质上它解决的就是一个最外围的问题：MySQL 的查问执行是单线程的，无奈充分利用古代多核大内存的硬件资源。通过多线程并行执行来升高包含 IO 以及 CPU 计算在内的解决工夫，来实现响应工夫的大幅降落。毕竟，对于用户来说，一条查问如果能够 1 分钟用 10 个核实现，总比 10 分钟用 1 个核实现更有意义。此外所有成熟的商业型数据库也都具备并行查问的能力。

二 并行查问介绍

1 个性

并行查问能够说是 PolarDB MySQL 在计算层最为重要复杂度也最高的性能组件，随着 PolarDB 的推出曾经线上稳固运行多年，而且始终在继续演进，它具备如下几个个性：

齐全基于 MySQL codebase，原生的 MySQL 100% 兼容，这里包含

• 语法兼容
• 类型兼容
• 行为兼容

0 附加老本，随产品公布就携带的性能

• 无需额定存储资源
• 无需额定计算节点

0 保护老本，应用和一般查问没有任何差异，只是响应变快了

• 随集群部署，开箱即用
• 对业务无侵入
• 繁多配置参数（并行度）

实时性剖析，PolarDB 原生的一部分，受惠于 REDO 物理复制的低提早

• 对立底层事务型数据
• 提交即可见

极致性能，随着 PQ 的不断完善，对于剖析型算子、简单查问构造的反对能力一直晋升

• 全算子并行
• 高效流水线
• 简单 SQL 构造反对

稳固牢靠，作为企业级个性，这个毋庸置疑

• 扩大 MySQL 测试体系
• 线上多年积攒
• 齐备诊断体系

下面这些听起来像是广告宣传词，但也的确是并行查问的外围竞争力。

2 演进

并行查问的性能是继续积攒起来的，从最后的 PQ1.0 到 PQ2.0，目前进入了跨节点并行的研发阶段并且很快会上线公布，这里咱们先不介绍跨节点并行能力，只关注已上线的状况。

PQ1.0

最早公布的并行查问能力，其根本的思路是计算的下推，将尽可能多的计算散发到多个 worker 上并行实现，这样像 IO 这样的重操作就能够同时进行，但和个别的 share-nothing 分布式数据库不同，因为底层共享存储，PolarDB 并行中对于数据的分片是逻辑而非物理的，每个 worker 都能够看到全量的表数据，对于逻辑分片前面执行器局部会介绍。

并行拆分的打算状态典型如下：

能够看到有这么几个特点：

• 执行模式是简略的 scatter-gather，也就是只有一个 plan slice，多个 worker 实现雷同的性能，汇总到 leader
• 尽可能的下推算子到 worker 上
• leader 负责实现无奈下推的计算

这个计划可能解决很多线上的慢查问问题，失去很好的减速成果，不过也存在着肯定的局限性

• 打算状态是繁多的，导致算子的并行形式繁多，比方 group by + aggregation，只能通过二阶段的汇集来实现：worker 先做 partial aggregation，leader 上做 final aggregation
• 一旦 leader 上实现汇集操作，后续如果有 distinct / window function / order by 等，都只能在 leader 上实现，造成单点瓶颈
• 如果存在数据歪斜，会使局部 worker 没有工作可做，导致并行扩展性差
• 此外实现上还有一些待欠缺的中央，例如大量算子不反对并行、一些简单的查问嵌套构造不反对并行

总得来说，PQ1.0 的并行状态和 PostgreSQL 社区的计划比拟像，还有改良空间，毕竟所有商业数据库的并行状态都要更灵便简单。

PQ2.0

PQ2.0 补救了下面说到的那些局限性，从执行模式上对齐了 Oracle/SQL Server，实现了更加弱小的多阶段并行。

打算状态典型如下：

第一眼看到的变动是这里存在多个 worker group，PQ2.0 的执行打算是多阶段的，打算会被拆分为若干片段(plan slice)，每个 slice 由一组 worker 并行实现，在 slice 之间通过 exchange 数据通道传递两头后果，并触发后续 slice 的流水线执行。其中一些补强的点包含：

• 全新的 Cost-based 并行优化器，基于统计信息和代价决定最优打算状态
• 全算子的并行反对，包含下面提到的简单的多层嵌套构造，也能够做到齐全的并行
• 引入 exchange 算子，也就是反对 shuffle/broadcast 这样的数据散发操作
• 引入肯定自适应能力，即便并行优化实现了，也能够依据资源负载状况做动静调整，如回退串行或升高并行度

这些扭转意味着什么呢？咱们来看一个简略且理论的例子：

SELECT t1.a, sum(t2.b)
FROM
t1 JOIN t2 ON t1.a = t2.a
JOIN t3 ON t2.c = t3.c
GROUP BY t1.a
ORDER BY t1.a
LIMIT 10;

对下面的简略查问，在通过优化后，PQ1.0 会生成图中的执行打算。

• 在 join 的表汇合中，寻找一个能够做逻辑分片的表做拆分，如果 3 个表都不足以拆分足够多的分片，那就选最多的那个，比方这里抉择了 t2，它可能拆出 12 个分片，但依然无奈满足并行度 16 的要求，导致有 4 个 worker 读不到数据而 idle。
• 汇集操作先在 worker 上做部分汇集，leader 上做汇总汇集，如果各个 worker 上分组的聚拢不佳，导致 leader 依然会收到来自上面的大量分组，leader 上就会依然有很重的汇集计算，leader 算的慢了，会来不及收 worker 数据，从而反压 worker 的执行速度，导致查问整体变慢。

而 PQ2.0 的执行打算如下

• 尽管依然只能在 t2 上做数据分片，但 12 个 worker 只须要实现 t1 join t2 这个操作，在 join 实现后个别数据量会收缩，通过 Shuffle(Repartition)将更多的两头后果散发到后续的 slice 中，从而以更高的并行度实现与 t3 的 join
• 各 worker 实现部分汇集后，如果分组仍很多，能够基于 group by key 做一次 Shuffle 来将数据打散到下一层 slice，下一组 worker 会并行实现较重的汇集操作，以及随后的 order by 部分排序，最终 leader 只须要做一次 merge sort 的汇总

这样就解决了单点瓶颈和数据量有余导致的扩展性问题，实现线性减速。

为什么线性扩大如此重要？

从上图能够看到，随着并行度的增长，E2E 的响应工夫是线性降落的，这对于客户有两个重要作用：

• 随着业务增长数据一直收缩，通过相应进步并行度来应用匹配的计算资源，来继续失去稳固可预期的查问性能
• 始终疾速的剖析工夫能够驱动疾速的业务决策，使企业在疾速变动的市场环境中放弃竞争力

完满的线性减速就是，Parallel RT = Serial RT / CPU cores，当然这并不事实

3 架构

并行查问组件的整体架构如下

外围局部包含在 3 层中，从上到下顺次是：

• Cost-based Parallel Optimizer，嵌入在 MySQL 的优化器框架中，实现并行优化局部
• Parallel Plan Generator，依据形象的并行打算形容，生成可供 worker 执行的物理执行打算
• Parallel Executor，并行执行器组件，包含一些算子内并行性能和数据散发性能等

具体每个组件的实现会在前面具体介绍

4 性能

因为是集体文章这里隐去了具体执行工夫（能够网上搜寻下），次要看下 PQ2.0 的查问减速能力，这里并行度是 32（可能有同学会奇怪为什么 Q6/Q12 的减速比超过了 32，前面会具体讲到）

总的数字是：100% 的 SQL 能够被减速，总和减速比是 18.8 倍。

5 应用形式

从易用性的角度，用户开启并行查问只须要设置一个参数：

set max_parallel_degree = xxx;

如果想查看并行执行打算，只须要和一般查问一样，执行 EXPLAIN / EXPLAIN FORMAT=TREE 即可。

Explain 做了必要的加强来显示并行相干的 information，包含代价、并行模式、散发形式等。

三 并行查问实现

下面是一些总体性的内容，没有什么技术细节，前面的章节会顺次 dive 到每个模块中介绍下。

1 并行优化器

在 PQ2.0 中，因为打算状态会变得更加多样，如果拆分打算只是依附简略规定和简略统计是很难失去最优解的，因而咱们从新实现了一套齐全基于 cost 的并行优化器。

根本的流程是在 MySQL 串行优化后，进一步做并行拆分，这里可能有同学纳闷为什么不像 Oracle 或 Greenplum 那样搞成一体化的，也就是在优化流程中对立思考串 / 并行的执行策略。起因在于，MySQL 的优化流程中，各个子步骤之间没有清晰的边界，而且深度递归的 join ordering 算法以及嵌入其中的 semi-join 优化策略抉择等，都使得代码逻辑与构造更加简单，很难在不大量侵入原生代码的前提下实现一体化优化，而一旦对社区代码毁坏重大，就没法 follow 社区后续的版本迭代，享受社区红利。

因而采纳了两步走的优化流程，这也是业界罕用的手法，如 Spark、CockroachDB、SQL Server PDW、Oceanbase 等都采纳了相似的计划。

代价模型的加强

既然是基于 cost 的优化，在过程中就必然要可能失去各个算子并行执行的代价信息。为此 PolarDB 也做了大量统计信息加强的工作：

• 统计信息自动更新
• 串行优化流程中做针对并行执行的补强，例如修改 table 扫描形式等，这也是下面性能数据中 Q6/Q12 会有超线性减速比的起因
• 全算子统计信息推导 + 代价计算，补充了一系列的 cost formula 和 cardinality estimation 推导机制

这里只能展现下统计信息加强带来的成果，收益的不止是并行查问，串行执行也会晋升。

自适应执行策略

在晚期版本中，串行优化和并行优化，并行优化和并行打算生成之间存在肯定的耦合性，导致的问题就是在开始并行优化后会无奈进化回串行，如果零碎中这样的查问并发较多，会同时占用很多 worker 线程导致 CPU 打爆。新的并行优化器解决了这个问题。

• 串行优化与并行优化解耦，并行优化会从新构建形象算子树，并以此为输出开始 enumeration
• 并行优化与并行打算生成解耦，优化的后果是打算子片段的形象形容，作为输入进行 plan generation

这样就使执行策略的灵活性成为可能，容许在资源有余状况下，要么退回串行，要么升高并行度，或者进入调度队列排队等资源。

基于代价的穷尽式枚举

这是一个比拟大的话题，概况来说，并行优化是一个自底向上，基于动静布局的穷尽式枚举过程，实现思路参考了 SQL Server PDW paper[2]，在过程中会针对每个算子，枚举可能的并行执行形式和数据散发形式，并基于输入数据的 phsical property(distribution + order)构建物理等价类，从而做部分剪枝，获取部分子问题的最优解并向下层传递，最终到 root operator 获取全局最优解。

下图是针对 t1 NLJ t2 这个算子，做枚举过程的一个简要示例：

在整体枚举实现后，打算空间中会产生一系列带有数据散发 Exchange Enforcer 的物理算子树，基于代价抉择最优树即可，而后以 Enforcer 作为子打算的切分点，能够构建出一系列的执行打算形象形容，输入到 plan generator 中。

2 并行打算生成

从工程实现角度，并行打算生成能够说是整个组件中复杂度最高，坑最多的局部。这里采纳了 physical plan clone 的机制来实现，也就是说，依据优化器生成的并行打算形容，从原始串行打算 clone 出各个打算片段的物理执行打算。

为什么要用这种形式呢？还是和 MySQL 自身机制相干，MySQL 的优化和执行是耦合在一起的，并没有一个清晰的边界，也就是在优化过程中构建了相干的执行构造。所以没有方法依据一个独立的打算形容，间接构建出各个物理执行构造，只能从串行打算中“clone”进去，这能够说是所有复杂度的本源。

MySQL 的执行构造非常复杂，expression(Item)和 query block(SELECT_LEX)的穿插援用，内外层查问的关联 (Item_ref) 等等，都使得这项工作难度大增，但在这个一直填坑不断完善的过程中，团队也对 MySQL 的优化执行构造有了很深刻的了解，还发现了社区不少 bug…

以上图中简略的查问为例

SELECT t1.a, sum(t2.b) sumb
FROM t1 join t2
ON t1.c = t2.c
GROUP BY t1.a
ORDER BY sumb;

尽管社区对执行器做了基于 Iterator model 的重构，但实质上，物理执行打算依然是由 QEP_TAB 组成的序列，其中 group by+aggr 由一个 tmp table1 实现，order by 由 tmp table2 实现。

在做 plan generation 时，有两个外围的操作：

• clone

依据串行 physical plan 和子 slice 的形容，将绝对应的构造 clone 到各个 worker 线程中，如上图右下局部，将在 worker 上执行的 t1 join t2 和下推的汇集操作 clone 了下来。

• refix

原始的串行打算须要转换为 leader 打算，因而要替掉不必要的执行构造并调整一些援用关系，如上图右上局部，因为 t1 join t2 和局部汇集操作曾经下推，leader 上须要去掉不必要的构造，并替换为从一个 collector table 中读取 worker 传递上来的数据，同时须要将后续步骤中援用的 t1/t2 表的构造转为援用 collector 表的对应构造。

这里只是举了最为简略的例子，还没有波及子查问和多阶段 plan，理论的工程实现老本要高很多。

3 并行执行器

PQ 实现了一系列算子内并行的机制，如对表的逻辑分区和并行扫描，parallel hash join 等，来使并行执行成为可能或进一步晋升性能，还有多样化的子查询处理机制等，这里选一些具备代表性的来介绍。

parallel scan

PolarDB 是共享存储的，所有数据对所有节点均可见，这和 sharding 的分布式系统有所不同，不同 worker 解决哪一部分数据无奈预先确定，因而采纳了逻辑分区的计划：

在 btree 这个 level，会将数据切分成很多小分片，不同 worker 负责不同分片来触发并行执行，这里有一些优化点：

• 尽量做细粒度的切分，使分片数 >> worker 数，而后 worker 之间通过 round robin 的形式去“抢”分片来执行，这样天然做到了能者多劳，防止因为数据分布 skew 导致的负载不平衡问题，这是 shared storage 零碎的一个人造劣势。
• 切分时能够不必 dive 到叶子节点，也就是以 page 作为最小分区单位，来减速初始分区速度。

parallel hash join

hash join 是社区 8.0 为减速剖析型查问所引入的性能，并随着版本演进对 semi hash/anti hash/left hash join 均做了反对，PolarDB 也引入了这些 patch 来实现残缺的 hash join 性能，并实现了多种并行执行策略。

parallel hash join 在 build/probe 两个阶段均做了并行反对

• build 阶段，多个 worker 向同一个共享的 lock-free hash table 中插入数据。
• probe 阶段，多个 worker 并行到 hash table 做搜寻。

两个阶段没有重叠，这样就实现了全阶段的并行，但 parallel hash join 也有本身的问题，例如共享 hash table 过大导致 spill to disk 问题，并行插入尽管无锁，但仍有“同步”原语带来的 cache invalidation。

partition hash join

partition hash join 则能够防止以上问题，但代价则是引入数据 shuffle 的开销：

如图所示，查问的执行过程分为了 3 个阶段

• build/probe 两侧都依据 join key 做 shuffle，将数据散发到指标 partition；
• 在每个 partition 内，build 侧各自构建小 hash table；
• 在每个 partition 内，probe 侧各自查找对应的 hash table；

这样就在各个 partition 内，实现了 co-located join，每个 hash table 都更小来防止落盘，此外也没有了 build 中的并发问题。

以上两个计划哪个更优？由并行优化器基于 Cost 决定。

子查问并行 – pushdown exec

• 这里子查问是表达式中的一部分，能够存在于 select list / where / having 等子句中。
• 对于相干子查问，惟一的并行形式是随外层依赖的数据（表）下推到 worker 中，在每个 worker 内残缺执行，但因为外层并行了，每个 worker 中子查问执行次数还是能够等比例缩小。

例如如下查问：

SELECT c1 FROM t1
WHERE EXISTS (SELECT c1 FROM t2 WHERE t2.a = t1.a     <= EXISTS subquery)
ORDER BY c1
LIMIT 10;

EXISTS 子查问残缺的 clone 到各个 worker 中，随着 WHERE 条件的 evaluation 重复触发执行。

子查问并行 – pushdown shared

这种并行形式的子查问能够是表达式的一部分，也能够是派生表(derived table)。

概况的来说，这种并行形式实用于非相干子查问，因而能够提前并行物化掉，造成一个长期后果表，后续外层在并行中，各 worker 援用该子查问时能够间接从表中并行读取后果数据。

例如如下查问

SELECT c1 FROM t1
WHERE t1.c2 IN (SELECT c2 FROM t2 WHERE t2.c1 < 15      <= IN subquery)
ORDER BY c1
LIMIT 10;

另外线上用户的报表类查问中，一种十分常见的 Query 模式就是 derived table 的多层嵌套，对于这类 SQL，pushdown shared 策略能够很好的晋升并行执行的性能，例如如下示例：

上图中每个色彩的方块，代表了一层 query block，这里就形成了多层 derived table 的嵌套逻辑，有些层中通过 UNION ALL 做了汇总，有些层则是多个表（包含 derived table）的 join，对于这样的查问，MySQL 会对每个 derived table 做必要的物化，在外层造成一个长期后果表参加后续计算，而 PQ2.0 对这种常见的查问模式做了更广泛的反对，当初每一层查问的执行都是并行实现的，力争达到线性的减速成果。

Exchanges

要生成高效灵便的执行打算，数据散发组件是必不可少的，目前 PolarDB 反对了 Shuffle/Broadcast/Gather 三种散发形式，实现上利用 lock-free shared ring buffer，做到流水线模式的高效数据传输。

下图展现了 Shuffle(Repartition)的根本状态

到这里，并行查问的线上版本性能及实现曾经大体介绍完了。

作为一款成熟的企业级性能个性，团队还实现了一整套欠缺的辅助工具集，来配合晋升产品的易用性，实现性能的可监控、可干涉、可反馈，但这里篇幅曾经很大了，就先不介绍了。

四 将来布局

这里说是将来布局并不确切因为团队曾经在跨节点并行上做了大量的工作并进入了开发周期的尾端，跨节点的并行会把针对海量数据的简单查问能力晋升到另一个程度：

• 买通节点间计算资源，实现更高的计算并行度
• 冲破单节点在 IO / CPU 上的瓶颈，充分利用分布式存储的高吞吐能力
• 联合全局节点治理与资源视图，均衡调度全局计算资源，实现负载平衡的同时保障查问性能
• 联合全局一致性视图，保障对事务性数据的正确读取

[1]https://www.allthingsdistribu…
[2]https://www.scinapse.io/paper…

原文链接
本文为阿里云原创内容，未经容许不得转载。