简介：随着数据规模的不断扩大，用户 SQL 的执行工夫越来越长，这不仅对数据库的优化能力提出更高的要求，并且对数据库的执行模式也提出了新的挑战。本文将介绍基于代价进行并行优化、并行执行的云数据库的并行查问引擎的关键问题和核心技术。
作者 | 智邻
起源 | 阿里技术公众号
一 背景
随着数据规模的不断扩大，用户 SQL 的执行工夫越来越长，这不仅对数据库的优化能力提出更高的要求，并且对数据库的执行模式也提出了新的挑战。随着数据库在云上的蓬勃发展，越来越多的传统用户迁徙到云上，享受云上弹性扩大的红利，然而随着业务的疾速扩张，却发现即便动静减少了很多资源，但 SQL 的执行工夫还是越来越慢，并没有随着资源的投入达到预期的成果。不言而喻，尽管新增了很多资源，但这些资源并没用被充分利用，很多传统的商业数据库，如 Oracle、SQL Server 等都提供对并行查问引擎的反对，以充分利用系统资源，达到减速 SQL 执行的成果。
本文次要介绍基于代价进行并行优化、并行执行的云数据库的并行查问引擎的关键问题和核心技术。
二 如何将查问并行起来
对于一个类 OLAP 的查问，不言而喻的是它通常是对大批量数据的查问，数据量大意味着数据远大于数据库的内存容量，大部分数据可能无奈缓存到数据库的缓冲区中，而必须在查问执行时才动静加载到缓冲区中，这样就会造成大量 IO 操作，而 IO 操作又是最耗时的，因而首先要思考的就是如何能减速 IO 操作。
因为硬件的限度，每次 IO 的耗时根本是固定的，尽管还有程序 IO 和随机 IO 的区别，但在 SSD 曾经流行的明天，两者的差别也在逐步靠近。那么还有没有其它形式能够减速 IO 呢? 显然并行 IO 是一个简单易行的办法，如果多个线程能够同时发动 IO，每个线程只读取局部数据，这样就能够疾速的将数据读到数据库的缓冲区中。
并行读取数据的示意如上图所示，每个 worker 代表一个线程，如果数据曾经有 partition 分区，能够每个线程读取一个 partition；也能够将全副数据按固定大小进行分片，比方按一个数据页面大小，而后每个线程以 Round-robin 模式轮询读取一个分片。
这里须要留神的是，按已有 partition 调配给不同 worker 可能会导致每个 worker 解决的数据不平均，而按 Round-robin 模式进行轮询，如果分片设置的比拟小，相对来说就比拟容易做到每个 worker 解决的数据比拟平均。
如果只是将数据读取到缓冲区中，而不是立刻进行后续解决，那么这些数据就会因缓冲区爆满导致数据被换出，从而失去减速 IO 的意义。因而，在并行读取数据的同时，必须同时并行的解决这些数据，这是并行查问减速的根底。
传统的优化器只能生成串行的执行打算，为了实现并行读取数据，同时并行处理数据，首先必须对现有的优化器进行革新，让优化器能够生成咱们须要的并行打算。比方抉择哪个表或哪些表能够并行读取，并且通过并行读取会带来足够的收益；或者哪些操作能够并行执行，并且能够带来足够的收益。
并不是说并行化革新肯定会有收益，比方对一个数据量很小的表，可能只是几行，如果也对它进行并行读取的话，并行执行所须要的多线程构建再加上线程间的数据同步等所须要的代价可能远大于所失去的收益，总体来说，并行执行会须要更多的资源和工夫，这就得失相当了。因而查问打算的并行化必须是基于代价的，否则可能会导致更重大的性能进化问题。
三 如何抉择并行扫描的表
抉择并行扫描的表是生成并行打算的重要根底，通过基于并行扫描代价的计算和比拟，抉择能够并行扫描的表作为候选，是并行执行打算迭代的第一步。基于新的并行代价，兴许会有更优的 JOIN 程序抉择，尤其是当参加 JOIN 的表的数量比拟多时，这须要更多额定的迭代空间，为避免优化过程耗费太多的工夫，放弃原有打算的 JOIN 程序是一个不错的抉择。另外，对于参加 JOIN 的每张表，因为表的拜访办法不同，比方全表扫描、Ref 索引扫描，Range 索引扫描等，这些都会影响到最终并行扫描的代价。
通常咱们抉择最大的那张表作为并行表，这样并行扫描的收益最大，当然也能够抉择多个表同时做并行扫描，前面会持续探讨更简单的状况。
上面以查问年度生产 TOP 10 的用户为例：
SELECT c.c_name, sum(o.o_totalprice) as s
FROM customer c, orders o
WHERE c.c_custkey = o.o_custkey
AND o_orderdate >= '1996-01-01'
AND o_orderdate <= '1996-12-31'
GROUP BY c.c_name
ORDER BY s DESC
LIMIT 10;其中 orders 表为订单表，数据很多，这类表也被称之为事实表，customer 表为客户表，数据绝对较少，这类表也被称之为维度表。那么此 SQL 的并行执行打算如下图所示：
从打算中能够看出 orders 表会做并行扫描，由 32 个 workers 线程来执行，每个 worker 只扫描 orders 表的一部分数据分片，而后与 customer 表按 o_custkey 做 index lookup 进行 JOIN，JOIN 的后果发送到一个 collector 组件，而后由 collector 组件持续做后续的 GROUP BY、ORDER BY 及 LIMIT 操作。
四 抉择多表并行的 JOIN
将一张表做并行扫描之后，就会想为什么只能抉择一张表？如果 SQL 中有 2 张或更多的 FACT 表，能不能能够将 FACT 表都做并行扫描呢？答案是当然能够。以上面 SQL 为例：
SELECT o.o_custkey, sum(l.l_extendedprice) as s
FROM orders o, lineitem l
WHERE o.o_custkey = l.l_orderkey
GROUP BY o.o_custkey
ORDER BY s
LIMIT 10;其中 orders 表和 lineitem 表都是数据量很大的事实表，此 SQL 的并行执行打算如下图所示：
从打算中能够看到 orders 表和 lineitem 表都会做并行扫描，都由 32 个 workers 线程来执行。那么多个表的并行是如何实现的呢？咱们以 2 个表为例，当 2 个表执行 JOIN 时，通常的 JOIN 形式有 Nested Loop JOIN、HASH JOIN 等，对于不同的 JOIN 形式，为保障后果的正确性，必须抉择正当的表扫描形式。
以 HASH JOIN 为例，对于串行执行的 HASH JOIN 来说，首先抉择一个表创立 HASH 表称之为 Build 表，而后读取另一个 Probe 表，计算 HASH，并在 Build 表中进行 HASH 匹配，若匹配胜利，输入后果，否则持续读取。如果改为并行 HASH JOIN，并行优化器会对串行执行的 HASH JOIN 进行并行化革新，使之成为并行 HASH JOIN，并行化革新的计划能够有以下两种解决方案。
计划一是将 2 个表都按 HASH key 进行分区，雷同 HASH 值的数据处于同一个分区内，由同一个线程执行 HASH JOIN。计划二是创立一个共享的 Build 表，由所有执行 HASH JOIN 的线程共享，而后每个线程并行读取属于本人线程的另外一个表的分片，再执行 HASH JOIN。最终抉择哪种计划，通过代价估算来决定。
图 2 并行 HASH JOIN 示意图
- 对于计划一，须要读取表中的所有数据，依据选中的 HASH key，对数据进行分区，并将数据发送到不同的解决线程中，这须要额定减少一个 Repartition 算子，负责依据分区规定将数据发送到不同的解决线程。
- 对于计划二，须要并行创立共享的 HASH build 表，当 build 表创立胜利后，每个线程读取 Probe 表的一个分片，别离执行 HASH JOIN，这里的分片并不需要依照 HASH key 进行分片，每个线程别离读取互不相交的分片即可。
五 剖析统计的简单算子的并行
对于一个剖析统计的需要，GROUP BY 操作是绕不开的操作，尤其对大量的 JOIN 后果再做 GROUP BY 操作，是整个 SQL 中最费时的一个过程，因而 GROUP BY 的并行也是并行查问引擎必须优先解决的问题。
以年度生产 TOP10 客户的 SQL 为例，对 GROUP BY 并行化后的并行执行打算如下图所示：
与之前的执行打算相比，新的执行打算中多了一个 collector 组件，总共有 2 个 collector 组件。首先咱们看第二行的 collector 组件，它的 extra 信息中有 2 条 ”Using temporary; Using filesort”，这示意它是对从 workers 接管到的数据执行 GROUP BY，而后再按 ORDER 排序，因为只有第一个 collector 组件在用户的 session 中，所以这个 collector 也是在 worker 中并行执行，也就是说并行的做 Group by 和 Order by 以及 Limit；而后看第一行的 collector 组件，它的 extra 信息中只有一条 ”Merge sort”，示意 session 线程对从 workers 接管到的数据执行一次 merge sort，而后将后果返回给用户。这里可能就有人会提出疑难，为什么 session 线程只做 merge sort 就能够实现 GROUP BY 操作呢？另外 LIMIT 在哪里呢？
首先答复第 2 个问题，因为 explain 打算显示的问题，在惯例模式下不显示 LIMIT 操作，但在 Tree 模式下会显示 LIMIT 操作。如下所示：
从 Tree 型打算树上能够分明的看到 LIMIT 操作有 2 处，一处在打算的顶端，也就是在 session 上，做完 limit 后将数据返回给用户；另外一处在打算树的两头地位，它其实是在 worker 线程的执行打算上，在每个 worker 线程中在排序实现后也会做一次 limit，这样就能够极大缩小 worker 返回给 session 线程的数据量，从而晋升整体性能。
上面来答复第一个问题，为什么 GROUP BY 只须要在 worker 线程上执行一次就能够保障后果的正确性。通常来说，每个 worker 只有所有数据的一个分片，只在一个数据分片上做 GROUP BY 是有极大的危险失去谬误的 GROUP BY 后果的，因为同一 GROUP 分组的数据可能不只是在本 WORKER 的数据分片上，也可能在其它 WORKER 的数据分片中，被其它 WORKER 所持有。然而如果咱们能够保障同一 GROUP 分组的数据肯定位于同一个数据分片，并且这个数据分片只被一个 WORKER 线程所持有，那么就能够保障 GROUP BY 后果的正确性。通过 Tree 型执行打算能够看到，在并行 JOIN 之后，将 JOIN 的后果按 GROUP 分组的 KEY 值: c.c_name 进行 Repartition 操作，将雷同分组的数据散发到雷同的 WORKER，从而保障每个 WORKER 领有的数据分片互不穿插，保障 GROUP BY 后果的正确性。
因为每个 WORKER 的 GROUP BY 操作曾经是最终后果，所以还能够将 ORDER BY 和 LIMIT 也下推到 WORKER 来执行，进一步晋升了并行执行的效率。
六 并行查问引擎对 TPCH 的线性减速
附图是一个并行查问引擎对 TPCH 的减速成果，TPC- H 中 100% 的 SQL 能够被减速，70% 的 SQL 减速比超过 8 倍，总和减速近 13 倍，Q6 和 Q12 减速甚至超过 32 倍。
七 总结
数据库是利用零碎的外围，而优化器是数据库的外围，优化器的好坏简直能够决定一个数据库产品的成败。开发一个全新的优化器，对任何团队都是一个微小的挑战，技术的复杂度暂且不提，就是想做到产品的足够稳固就是一个十分难以克服的艰难。因而即便传统商业数据库，也是在现有优化器的根底上不断改进，逐步减少对并行的反对，最终成为一个成熟的并行优化器。对 PolarDB 也是如此，在设计和开发并行查问引擎时，咱们充分利用现有优化器的技术积攒和实现根底，不断改进，一直打磨，最终造成了一个继续迭代的技术计划，以保障新的优化器的稳固运行和技术革新。
原文链接
本文为阿里云原创内容，未经容许不得转载。