数据库 频道

TDSQL-C 并行查询探索 | DTCC 2022

  

按:本文是 DTCC 2022 云原生专场《TDSQL-C 并行查询探索》文字稿整理。在演示稿中有一些资料引用,这里单独抽出来便于参考。

    1. TDSQL-C 产品介绍 

      https://cloud.tencent.com/product/cynosdb

    2. 列存技术比较 Abadi, D. J., Madden, S. R., & Hachem, N. (2008, June). Column-stores vs. row-stores: how different are they really?

    3. TDSQL-C 并行查询用户手册 

      https://cloud.tencent.com/document/product/1003/81872

    4. TPC-H 规范  

      https://www.tpc.org/tpch/default5.asp

    5. 阿姆达罕定律 

      https://en.wikipedia.org/wiki/Amdahl%27s_law

    6. SQL 计算模型 Astrahan, M. M., & Chamberlin, D. D. (1975). Implementation of a structured English query language.

    7. 行迭代器 Graefe, G. (1994). Volcano - an extensible and parallel query evaluation system.

    8. 即时触发式并行调度 Graefe, G. (1990). Encapsulation of parallelism in the volcano query processing system.

    9. HASH 分区 Kitsuregawa, M., Nakayama, M., & Takagi, M. (1989, August). The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method.

    10. 可分解聚合函数 

      https://en.wikipedia.org/wiki/Aggregate_function

    11. 调度的控制流与数据流实现 Teeuw, W. B., & Blanken, H. M. (1993). Control versus data flow in parallel database machines

    12. CSP 交互模型 

      https://en.wikipedia.org/wiki/Communicating_sequential_processes

  以下是文字稿内容:

  主持人好,各位嘉宾下午好,很荣幸有这个机会向大家分享一下,我们近期在大查询性能上的一些工作。

  这次分享有几个环节:首先是云原生数据库产品的介绍,以及我们遇到的业务挑战,并做一些策略分析。然后,从用户视角来感受一下并行查询的功能使用和性能表现。然后,用一个简单的例子,演示并行查询如何进行加速,以及技术方案涉及的一些基本概念和数学定律。最后,梳理一下并行查询方案的技术要点,以及实践过程中所做的一些选择,并简单介绍一下未来的工作。

  

  Part 1. 产品简介

  虽然每个云厂商的叫法有点不一样,云上的关系数据库一般来说有四种形态。TDSQL-C 的定位是云原生数据库,它在架构上是基于物理日志复制和共享存储的高可用集群。

  

  云原生数据库,对于业务而言是非常友好的。MySQL 兼容性几乎是 100% 。除非是使用了云厂商特色的扩展功能,否则,业务可以自由迁入迁出,不会产生云厂商锁定。这可能是大家在选型时比较关注的一个点。另外,由于它采用了物理复制,数据同步性能很高,扩缩容也很方便,这就可以灵活控制成本。在现在的大环境中,成本还是一个很重要的东西。

  

  随着业务数据量增长,就产生了新的问题:需要处理的数据量比较大的查询(分析型查询),无法充分利用计算资源(空闲资源),响应时间会拉的比较长。这是因为传统 MySQL 中,SQL 处理是单线程的。我们一般说的并发,是指查询间并发,有多个CPU 核心就可以支持同时跑多条语句进行,但是一条 SQL 语句只能由同一个核来处理。

  分析型通常可以从三个方面优化。我们今天的主题是如何调动多个核心来加速同一个查询,称为查询内并发。并行查询,不管是单机的还是多机的,在本质上是做计算任务的拆解和分发,它没有去改变计算的形式,而是在现有架构基础上进行扩展性改造,通过投入更多资源来提高性能。所以,它不算是一个颠覆式创新,但是体验上是很平滑的,使用门槛很低。相对来说,其他两个方面,由于需要结合向量运算和列式存储,实现起来会比较重,使用门槛也会高一些,我们后续也会有相应的能力发布。并行查询和这些 AP 技术的加速效果是可以叠加的。

  在架构选择上,也有三种形态。其中 (a) 一般是分库分表,经过一些包装后,现在也叫透明分布式,(b) 是传统的双系统方案。但我们采用的是改造原生内核支持并行,业务使用和运维都比较简单。

  

  Part 2. 功能体验

  下面,我们来直观感受一下并行查询带来的变化。

  

  在使用时,要有一个“资源“的概念。一旦规划了核心资源,查询可以立即获得提速,不需要额外操作。

  我们可以看到执行计划发生了一些变化。并行计划会有多个线程协商完成,在边界处有一些特殊算子来支持数据交换,这里有 4 个核心各自独立扫描数据,计算结果汇总到用户线程返回汇总处理后返回给用户。除此之外,我们还可以从 process list 和系统指标里看到更多内容,这里就不展开了,大家可以查看左下方链接里的用户手册。

  

  OK ,这是单条语句演示,下面来看看整体表现。这里用的是 TPC-H 业务。TPC-H 是行业基准测试,里面有 22 条查询模拟一个分析型业务,这里面单表、多表、分组、聚合,排序,独立子查询、相关子查询都有。我没有去特别强调函数,因为我们技术方案上对函数是直接继承原生能力的,这个后面会进一步展开。

  这里是 16 并发性能数据。可以看到 22 条查询中加速效果各自都不同。大部分有比较好的加速效果,但是仍然有个别查询没有明显提升。并行查询加速分析,可以参考阿姆达罕定律。简单的讲,一个程序的加速效果,是由可并行部分的占比 p 决定的。p 越大加速效果越好。如果 p 很小,那么即使投入很多资源来提高局部加速比 s ,整体上也不会有很好的加速效果。所以,并行查询的加速效果,其实是跟业务相关的,每个业务语句都有不同的性能表现。当然,图中 p 值很小的那几条,我们在后续版本还会有相应的改进。

  

  Part 3. 并行原理

  OK 下面开始进入干货环节。先看一下技术原理。

  

  并行查询,本质上讲就是一个字,“拆“。任务拆细,数据集拆小。拆开了大家一起干,自然就干得快。当然,大家一起干,就需要一些协调,协调效率也是很关键的。

  这里用一个简单的聚合查询来演示并行查询。在图 1 里是 SQL 文本,还是个附加问题,可以先想想,稍后回答。在图 2 左边,我们看到,计算过程是对于每行都会更新聚合状态,这里借助了哈希表进行计数,所有行处理完了结果就出来了。在图 2 右侧的并行查询里,原始数据集被划分成两半,同时开始算,显然这部分计算速度就可以翻一倍,但是,后面还有一个汇总操作,所以,整体加速其实是到不了两倍的。在图 3 里,用算子和任务图的方式来表达了这个计算逻辑,我们可以看到,聚合运算和底下的数据访问都发生了变化,这就是拆任务和拆数据。同时,图 3 右边也是阿姆达罕定律的一个直观解读。

  那么,回到图 1 的附加问题。这个问题也是线上业务反馈比较多的。答案是两个都对。这本质上不是一个并行查询问题,而是业务程序与数据库之间的编程契约问题。这个契约就是SQL 标准,当然也有一些事实标准,我们知道,SQL 集合顺序是在语言标准里是未定义的。业务逻辑依赖于“未定义行为“,其实是比较危险的。类似的问题,大家在日常开发上也可能遇到,因为通用编程语言也有未定义行为,只不过是业务程序和编译器之间的编程契约。

  

  下面我们借一个稍微复杂一点的虚构查询来看看 SQL 计算模型。这个模型其实是分为三个层次的。图 1 中是原始 SQL 和标记,图 2 是其拆解形式,图 3 是图形化的计算结构。图 3 看上去比较复杂。但是这三个查询块的基本形式是一样的,我们只需要关注到数据的流动。查询块输入输出隐含了数据依赖关系。一般是从主查询开始计算,但如果有独立子查询,它不依赖主查询提供输入, MySQL 也可以先计算子查询。查询块内部是关系代数运算,数据自下而上流动。底层操作是集合迭代,每次行迭代都可能会计算一下表达式(函数),表达式数据也是自下而上流动。表达式计算又分普通函数和统计函数。sum count 这些统计函数比较特殊,我们在下一页展开。

  

  统计函数有什么特殊呢?我们知道 SQL 是声明式语言,从描述到实现的差异是很大的。普通表达式,例如 a+b ,是给一行算一个结果,数据随时可以流动。所以,虽然关系代数定义的是集合运算,但是这个集合是一个概念上的东西,不一定要有一个物理上的集合,基于一个行缓冲区就可以有多个运算,这称之为流水线。但统计函数不一样,它要读完整个集合才能出结果,这种称之为流水线断点,我们看到它需要两轮迭代,第一轮迭代读输入集合构造中间结果(例如,并行原理中的哈希表),第二轮迭代输出最终统计结果。

  显然,一个自然的任务划分方式,就是在迭代运算的边界上进行拆分,并重新建立输入和输出关系。

  

  那么,哪些计算是可以分解成更小的计算任务,从而并行地执行的呢?大体上分为关系运算和统计函数两类。

  关系运算里最常见的是条件过滤,显然子集过滤结果汇总起来就是整体过滤结果。连接操作还有更多优化空间。右边图里表示了对集合进行划分,连接操作可以基于子集运算结果合并而完成,但是两种划分方式,一种不限划分机制,另一种是用同一个哈希函数来进行划分。我们知道,哈希划分有个特点,就是可以筛选出相关数据,这可以让子问题更小,例如,原来 Ri 要和完整的 S 连接,现在只需要和 Si 连接。具体可以看 GRACE 论文里的 Figure 2 。

  当然,不同运算的拆解逻辑不一样,这个是由基本运算的语义决定的。这些内容也比较直观,这里就不过多展开了。

  

  Part 4. 技术方案

  基于这些原理,来看看具体方案。我们在方案选择上,主要考虑复用和扩展两个点。

  

  首先,要有一个调度框架来负责协调任务的执行顺序。我们从原始执行计划树上构造出来的一个任务图,表示了计算任务之间的依赖关系。显然,所有线程都要用同一个任务大图。

  协调线程负责下发任务,其他线程里面就是命令循环,负责执行任务和上报状态。注意这里协调线程是指一个角色,它可以是一个独立的线程,也可以是某个线程兼任的。用户线程是指跟客户端交互的线程,也是最开始的那个线程,它是前台线程,负责向客户端返结果,其他线程都是后台线程。

  因为任务执行过程中随时都有可能产生意外,需要中止整个调度,所以,这个调度执行框架要和 MySQL 异常处理框架整合在一起。

  

  前面的原理部分,大家应该还有印象,就是说大多数计算逻辑内部实现与并行其实没什么关系,我们其实只需要在任务边界上做好输入输出的对接,就可以把多个任务拼成一个逻辑上的大图,至于每个线程上是完整的大图还是大图的一部分,其实是一个实现问题。这种任务的表示,称为任务形态。通常有三种形态,最直观的是控制消息包含完整的物理描述结构,当然也可以用结构相同的图,用约定的标识来定位到任务,或者还原成 SQL 然后重走流程描述。我们采用的是第二种形态,这个主要是从代码复用上考虑,MySQL 工程设计上有点独特,物理结构拷贝的支持比较差,但是优化器已经有能力生成完整的结构,我们只需要干预优化器来产生相同的计算结构,然后做一些修改就可以了,当然,这个修改也是比较有挑战的。此外,这个干预能力还有复用到更多应用场景。第三种通常用在分库分表中间件里,因为中间件和数据库内核实现不一样,传递物理结构更麻烦。

  

  那么,第二种形态是如何达成的呢?我们知道优化过程是本质上是一个搜索过程,从搜索空间中的很多计算结构里找到最好的那个。只要判断逻辑是相同的,就能定位到同一个结果。这个判断逻辑会受到模型参数和一些数据的影响。所以,我们只需要把这些接口进行拦截,将结果缓存下来,新的优化过程里直接用这些缓存结果,就可以实现干预而产生相同的结果。

  

  然后,可以开始考虑并行流程了。简单地说,一条查询,要经过串行优化,产生一个计算结构,然后进行检测看看哪些运算逻辑支持并行,然后就要决定并行策略和任务边界,然后把任务数据重新对接好,就可以申请资源来调度执行了。用户手册中有控制各个模块的参数,这里就不展开了。前面说到我们要干预优化器,所以,这里优化环境就记录了如何干预。

  

  最后,我们来看看数据分区和数据交换两个基础模块。MySQL InnoDB 存储是 B+ 树,这是一颗平衡树,所以,分区其实就是在一个层级上,把元素都取出来,作为分区边界,如果不能够均匀地分给并行线程,那就将剩余的分区进行更低层次的划分,直到大家都有足够的事情可干,而且剩余部分又比较小。当然,这个划分逻辑是社区代码里自带的,我们只需要对它进行扩展,支持对子树进行划分,支持正反向扫描和不同的索引。

  

  数据交换本质上就是上下游线程之间收发数据。这里其实是一个数据网络,每个线程都有接入网络的算子,一边收发数据,一边用来和任务内部的计算逻辑进行对接。这种算子也称为“桥接”算子。

  

  Part 5. 展望

  最后,简单介绍一下未来的工作。

  我们在 AP 能力上,后续工作分为两个方向。

  一方面是扩大并行查询覆盖范围,做一些深度性能优化,以及支持行列混合调度,发挥各自的优势产生叠加效果。

  另一方面,对于 SQL 的使用,也会有一些工作来提高 SQL 执行过程的透明程度,便于问题分析和性能改进。这些工作也不限于并行查询,更重要的是对基础内核的改进,让数据的使用更加便利。

  

  这就是我今天的分享。谢谢大家。

0
相关文章