TiFlash 源码阅读(八)TiFlash 表达式的实现与设计
原文来源:https://tidb.net/blog/06dede75
TiFlash 是 TiDB 的分析引擎,是 TiDB HTAP 形态的关键组件,TiFlash 源码阅读系列文章将从源码层面介绍 TiFlash 的内部实现。在上一期的源码阅读中,大家应该对 TiFlash Proxy 模块的实现,即 TiFlash 副本是如何被添加以及获取数据有了一定的了解。
本文主要介绍的是 TiFlash 表达式的实现与设计,系统性地介绍了 TiFlash 表达式的基本概念,包括表达式体系,标量函数、聚合函数等,以期望读者能够对 TiFlash 的表达式计算有一个初步的了解。
本文作者:黄海升,TiFlash 研发工程师
表达式概要
表达式是承载 SQL 大部分逻辑的一个重要部分。SQL 中的表达式和编程语言中的表达式并没有差异。表达式可以大致分为函数、常量、列引用。如select a + 1 from table
中的 a + 1
是一个表达式,其中 +
是函数,1
是常量,a
是列引用。
在 SQL 中,表达式会归属在不同的算子里执行,以 select a + b from tests.t where c > 0
为例,大家可以从下图看到不同的表达式归属在哪些算子里。
-1668597032379.png)
表达式在 SQL 中如何划分出来,并且归属在哪些算子里,是由一套语法规则决定的。下图是 MySQL 8.0 Parser 的语法规则简图,里面大号粗体的是算子标识符,后面跟着的小号字段是归属这个算子的表达式。
-1668597047849.png)
在了解了什么是表达式之后,我们来了解一下表达式在 TiFlash 里执行的情况。
在 TiDB HTAP 的体系里,TiFlash 的表达式是由 TiDB 下推给 TiFlash 执行的。首先我们来回顾下 TiDB 计算下推 TiFlash 的流程。
-1668597080408.png)
TiDB 接收 MySQL Client 发送的 sql,经由 Parser 和 Optimizer 解析成算子,在之后将算子下推到 TiFlash 里执行。与此同时,算子内部的表达式也会跟随一起下推到 TiFlash 里执行。
如下图所示,如果某个算子带有 TiFlash 不支持的函数,就会导致一连串的算子都无法下推到 TiFlash 里执行。算子内部的表达式都可以下推执行,是算子下推的必要条件。
-1668597095213.png)
在算子和表达式下推到 TiFlash 后,TiFlash 会用向量化执行引擎来执行这些算子和表达式。在谈到 TiFlash 的向量化执行引擎之前,我们先来讲一下执行引擎的一个经典模型 Volcano Model。
-1668597110727.png)
Volcano Model 源自 1994 年的论文 Volcano-An Extensible and Parallel Query Evaluation System。Volcano Model 将 SQL 分解为若干个独立的 Operator,Operator 串联成一棵 Operator Tree。
如上图所示,从最源头的 Table Scan Operator 开始,一行一行地读取数据,Operator 处理后,传给上游 Operator。最终 Operator Tree 一行一行地输出结果。
下面是对 Operator 接口的一个简单的伪代码描述。
Volcano Model 提供了一个非常简洁的执行模型,在工程上也非常容易实现。但是 Volcano Model 在现代编译器和硬件下运行得慢。在后续几年了诞生了对 Volcano Model 的两个改进方案,Codegen 和 Vectorized。TiFlash 就是使用的 Vectorized 即向量化执行。
向量化执行与 Volcano Model 基本一致,区别在于 Block by Block。
-1668597157136.png)
Block 是若干 Row 组合在一起的数据块,Block 内部按 Column 保存数据。
这样设计的好处有几个:
虚函数调用的开销会被减小为 1 / (Block Size)。Volcano Model 中的 Operator 和表达式通常都是用多态来实现的,在其中就会引入虚函数调用。每次 Operator Tree 和内部的表达式被调用就是一系列的虚函数调用,在数据量大的情况下,虚函数开销甚至会成为一个不可忽视的点。Block by Block 可以让 Operator Tree 和内部的表达式的一次调用处理多行而不是一行数据,从而均摊了虚函数开销。
Cache Friendly。把会被连续处理的数据放在一个数据块里,提高在 Cache 上的空间局部性。
TiFlash 表达式体系 ExpressionActions
除了向量化执行外,TiFlash 在表达式执行上还有一套独立的执行体系ExpressionActions
, 不同于 TiDB 源自 Volcano Model 的 ExpressionTree
。
这两个表达式体系在逻辑语意上是一致的,仅仅在执行过程上有差别。
-1668597190943.png)
如上图所示,同样的表达式在 TiDB 和 TiFlash 里会分别在不同的表达式体系里执行。
接下来以(a + b) * (a + b)
为例子来讲述一下两个表达式体系执行的差异。
首先从 TiDB ExpressionTree
讲起。(a + b) * (a + b)
会被分解成一棵 Expression Tree,每一个 Expression 都是一个节点。从 Column Expression 和 Literal Expression 开始读取数据,遍历整棵 Expression Tree,最终得出表达式结果。
如下图所示,沿着图中的箭头方向,就可以从 Input 计算得出 (a + b) * (a + b)
的结果 Output。
-1668597312946.png)
在图中大家可以发现 (a + b) 这个子树出现了两次,也就意味着 (a + b) 本身执行了两次,那么可不可以复用 (a + b) 的计算结果,如下图所示连线? 哪怕这样就不是一棵树了。
-1668597335417.png)
事实上是可以的,这也是 TiFlash ExpressionActions
的设计初衷: 中间计算结果复用。
-1668597359794.png)
在 TiFlash ExpressionActions
下,中间计算的临时结果会作为 Column 会被写到 Block 里,同时我们会通过 Column Name 获取 Block 中对应的 Column。
如上图所示,沿右图箭头方向遍历 Expression Action,即可得出 (a + b) * (a + b)
的计算结果。可以看到,同样是 (a + b) * (a + b)
,TiFlashExpressionActions
里的 (a + b)
只计算了一次。下面是 ExpressionActions
的执行分解图,从左到右。大家可以对照一下分解图,大概了解一下 ExpressionActions
的执行过程。
-1668597475227.png)
-1668597500979.png)
-1668597512541.png)
接下来我们深入一下代码,从代码层面来了解一下 ExpressionActions
究竟做了些什么。
以上是 ExpressionActions
接口的简化代码。有三个主要方法:
execute
对
ExpressionAction::execute
的包装。用于执行表达式。
add
用于外部组装出一个 ExpressionActions。
ExpressionActions
会维护一个 Sample Block,在 Add Action 的过程中 Sample Block 会不断更新,模拟实际 Block 的变化情况。在 Add 的过程中,重复的 Action 会被跳过。重复 Action 的判断条件是,该 Action 的执行结果是否已经出现在 Sample Block 里了。
-1668597609084.png)
finalize
分析 Block 内的 Column 引用情况,在合适的位置插入 Remove Action 来移除无用的 Column。
在 Column 引用数归 0 的时候,就会插入对应 Column 的 Remove Action。
下图是 (a + b) * (a + b) 的引用数分析和 Remove Action 插入情况。
-1668597636037.png)
ExpressionAction
是 ExpressionAction
内部的执行单元。
ExpressionAction
有不同的 Type 用于对 Block 进行不同的处理
REMOVE_COLUMN
ADD_COLUMN
用于执行 Literal Expression,在 Block 插入一个 Const Column。
ADD_COLUMN
会在 Block 中插入一个 Column。对于 Literal,插入的会是 ColumnConst,即常量 Column。block.insert({added_column->cloneResized(block.rows()), result_type, result_name});
-1668597773207.png)
APPLY_FUNCTION
APPLY_FUNCTION
会读取 Block 中的 Argument Columns 传给IFunction
做计算。计算出结果 Column 后,插入到 Block
-1668597830481.png)
Column Expression 没有对应的 Action Type,直接执行 Block::getPositionByName 获取 Column 在 Block 里的下标。但是从 TiDB 获得的 Column Expression 计算得出的并不是 Column 在 Block 中的 Column Name,而是 Column 在 TiDB Schema 中的下标。所以 TiFlash 会维护 TiDB Schema (std::vector<String>) 来桥接 TiDB Column Index 和 TiFlash Column Name,如下图所示。
-1668597850775.png)
标量函数在 TiFlash 中的编译与执行
当 ExpressionAction
的 Type 为 APPLY_FUNCTION
时,ExpressionAction
内部会持有IFunction
。对ExpressionAction::execute
的调用都会转发给IFunction
执行。IFunction
是 TiFlash 向量化标量函数的基类。
-1668597881942.png)
首先我们从函数在 TiFlash 中的编译讲起。tipb
是 TiDB 与 TiFlash 之间的序列化协议,下图的tipb::Expr
等同是 TiDB 里的 Expression。
对于传入的一个 tipb::Expr
,首先分门别类,按照 Column,Literal,Function 分别处理。
如果是 Function,首先处理 Function 的所有参数。参数本身也是 tipb::Expr
,所以也会按照对应的tipb::Expr
处理流程处理。在处理完 Function 的所有参数后,就可以去构建IFunction
本身,然后塞入ExpressionAction
,返回处理结果。
-1668597908721.png)
TiDB 对函数的标识是 tipb::ScalarFuncSig
,而 TiFlash 使用 Function Name 作为函数的标识。在 TiFlash 里,我们会用映射表的形式将 tipb::ScalarFuncSig
映射成 Function Name。再根据 Function Name 找到对应的 TiFlash Function Builder。
-1668597974943.png)
对于窗口函数、聚合函数、distinct 聚合函数、标量函数都有各自的映射表。
拿到 Function Name 之后,我们就可以去找到 Function 对应的 Function Builder 去 Build 出 IFunction
实现。TiFlash 有两类 Function Builder: Default Function Builder 和 Special Function Builder。前者是用于处理大多数 Function,后者处理某些特殊情况。
-1668598018789.png)
Default Function Builder 的处理本身很简单,就是先处理所有的函数入参,然后调用 applyFunction
生成对应的 IFunction
实现。
对某些函数,有些特殊处理,这时就会使用到 Special Function Builder。
特殊处理的 Function Builder 会放在表里,遇到对应的函数,会转发过来。
下面是一些函数的特殊处理映射。
一个特殊的处理的情况是复用函数实现。某些函数可以由另一个函数来代理执行,比如
leftUTF8(str, len) = substrUTF8(str, 1, len)
。如果让 substrUTF8
来代理执行 leftUTF8
,那么就可以省掉leftUTF8
本身的开发实现工作。下面是leftUTF8(str, len) = substrUTF8(str, 1, len)
的代理实现代码。为substrUTF8
生成第二个参数1
后,将leftUTF8
的两个参数传入substrUTF8
,substrUTF8
就可以代理leftUTF8
执行。
接下来我们来看一下 IFunction
本身的接口。
IFunction
有三个主要方法
getName
: 返回 Function 的 Name,Name 是作为 TiFlash 向量化函数的唯一标识来使用。getReturnTypeImpl
: 负责做向量化函数的类型推导,因为输入参数数据类型的变化可能会导致输出数据类型变化。executeImpl
: 负责向量化函数的执行逻辑,这也是一个向量化函数的主体部分。一个 TiFlash 向量化函数够不够 ” 向量化 ”,够不够快也就看这里了。
接下来以 jsonLength(string)
为例子,讲一下向量化函数的执行
从 Block 中获取 Json Column
创建同等大小的 Json Length Column
Foreach Json Column,获取每一个行的 Json
调用
GetJsonLength(Json)
获取 Json Length,将结果插入 Json Length Column 中的对应位置。将 Json Length Column 插入到 Block 中,完成单次计算
-1668598153108.png)
前段时间 TiFlash 有个社区活动,号召大家来参与 TiFlash 函数下推的工作。
以上关于标量函数的内容在社区活动的两篇文章 TiFlash 函数下推必知必会 和 手把手教你实现 TiFlash 向量化函数 都有包含,大家可以通过这两篇文章了解更多关于 TiFlash 标量函数的内容。也欢迎小伙伴们也参与到 TiFlash 函数下推的工作中来。
聚合函数在 TiFlash 中的编译与执行
聚合函数不同于标量函数的点在于输入 m 行数据输出 n 行数据,且有 m >= n。
-1668598203330.png)
所以聚合函数不会使用 ExpressionActions 和 IFunction,而是有独立的执行体系。
聚合函数本身由 Aggregate 算子来执行,Aggregate 算子负责管理聚合函数的执行步骤,执行并发度等等。
Aggregate
算子的执行有两部分
前者
ExpressionActions
用于执行标量函数的部分。后者
Aggregator
用于执行聚合函数的部分。
如下图所示,对于select max(a+b)
,ExpressionActions
执行a+b
,Aggregator
执行max
。
-1668598230866.png)
下面详细来说一说 Aggregator
是如何执行聚合函数的。首先Aggregator
会多线程从 Input 读取 Block,调用executeOnBlock
写入 Thread LocalAggregatedDataVariants
。AggregatedDataVariants
内部会保存当前线程的部分聚合计算结果。在executeOnBlock
阶段完成后,Aggregator
会调用mergeAndConvertBlocks
将多个AggregatedDataVariants
合并成一个,输出最终聚合的结果给 Output。
-1668598259323.png)
Aggregator::executeOnBlock
会对每一个 Key 都会创建一个 Aggregate Data。
输入的 Row 会根据 Key 找到对应的 Aggregate Data, 调用 IAggregateFunction::add
,更新 Agg Function 保存在 Aggregate Data 里的聚合结果。
如下图所示,Row1 和 Row4 经由 Aggregate Function 计算后,更新 Key1 保存的 Aggregate Data;Row2 经由 Aggregate Function 计算后,更新 Key2 保存的 Aggregate Data;Row3 和 Row5 经由 Aggregate Function 计算后,更新 Key3 保存的 Aggregate Data。
-1668598298114.png)
在 executeOnBlock
完成后,每个线程都会有一个独立的 Aggregate Data。
在 mergeAndConvertBlocks
阶段会把其他 Aggregate Data 都合并到 Aggregate Data0 上面。
IAggregateFunction::merge
用于执行把所有线程计算的部分聚合结果聚合成一个最终聚合结果。
如下图所示,Aggregate Data 在合并的时候,同一个 Key 的数据会合并到一起,与其他 Key 互不干扰
-1668598328900.png)
IAggregateFunction
是聚合函数的实现基类。接下来我们来看一下 IAggregateFunction
本身的接口。
add
用于计算聚合结果并更新到place
上merge
用于将rhs
里的聚合结果合并到place
insertResultInto
用于将place
里保存的聚合结果输出成 Block
接下来我们以 Sum 这个聚合函数为例子来看一下聚合函数的执行过程。
实际的 Sum 实现带有很多优化,这里选择最简化的实现
对于 Sum,AggregateData 的实现是
AggregateFunctionSumData
,内部维护一个T Sum
保存聚合结果对于 Sum,
add
和merge
都是执行 += 操作。
下图是对 Sum 执行过程的一个简化描述图。
add
阶段,Aggregator
会从 Input
读取数据,执行 sum += input
,更新 Aggregate Data
里的聚合结果。在 add
完成后,会执行 sum0 += sum1
和 sum0 += sum2
,将聚合结果合并成一个。最终输出 sum0
作为最终结果。
-1668598387372.png)
版权声明: 本文为 InfoQ 作者【TiDB 社区干货传送门】的原创文章。
原文链接:【http://xie.infoq.cn/article/cb02e53dd2c929bd62a071152】。文章转载请联系作者。
评论