数据库计算引擎的优化技术:向量化执行与代码生成

2023-11-05

原文链接:https://zhuanlan.zhihu.com/p/100933389

阿尔德里竹

阿尔德里竹

作者:徐飞,李德竹

随着数据库软硬件技术的发展,经典的 SQL 计算引擎逐渐成为数据库系统的性能瓶颈,尤其是对于涉及到大量计算的 OLAP 场景。如何进一步提升 SQL 计算引擎的性能成为数据库从业者们的热门研究方向,无论是学术界还是工业界都对此作了大量的努力,而向量化执行与代码生成正是在这一过程中实践总结出来的两种有效方法,在新一代的数据库系统中,大多都能看到这两种技术的运用。本文主要对这两种技术的原理及好处进行简单的介绍。

SQL 中的计算

SQL 是一种声明式语言,用户通过 SQL 语句向数据库发起计算请求,SQL 中的计算主要包括两类:expression 级别的计算和 operator 级别的计算。以下面这条 SQL 为例:

select c1 + 100, c2 from t where c1 < 100 and c3 = 10

该 SQL 包含了 3 个 operator:tablescan,selection 和 projection,而每个 operator 内部又包含了各自的 expression,例如 selection 内部的 expression 为c1 < 100 and c3 = 10,projection 内部的 expression 则为c1 + 100c2

经典的 SQL 计算引擎

经典的 SQL 计算引擎在 expression 层面一般采用 expression tree 的模型来解释执行,而在 operator 层面则大多采用火山模型。

Expression 一般有如下定义:

class Expression {
        // 由于返回值类型是不定的,因此往往会用万能值对象包裹
        Datum eval(Row input); 
        Expression children[];
}

上述 SQL 中的 filter 条件对应的 expression tree 就如下图所示:

img

与 Expression tree 类似,在火山模型中,operator 也被组织为 operator tree 的形式,operator 之间则通过迭代器来串联。Operator 一般有如下定义:

class Operator {
        Row next();
        void open();
        void close();
        Operator children[];
}

在具体的 operator 中一般包含其需要计算的 expression,例如:

class Projection extends Operator {
        Expression projectionExprs[];
        Row next() {
                Row output = new Row(projectionExprs.length);
                Row input = children[0].next();
                for (int i = 0; i < projectionExprs.length; i++) {
                        output.set(i, projectionExprs[i].eval(input));
                }
                return output;
        }
}

这样上述 SQL 在数据库中实际上会被编译为如下的 operator tree:

img

火山模型的最大好处是实现简单,每个 operator 都只需要完成其自身特定的功能,operator 之间是完全解耦合的,SQL complier 只需要根据 SQL 的逻辑构造对应的 operator 然后将 operator 串联起来即可。

上面这套模型诞生于上世纪九十年代,对于那时候的数据库产品,IO 速度是远小于计算速度的,所以计算引擎上的提速对整体数据库的提速效果并不多,大部分数据库优化更偏向于怎么更快的读取数据,但是随着近年来数据库存储组件越来越快,数据库从业者们发现计算速度也逐渐成为了数据库的一个瓶颈。从 expression 和 operator 两个层面来看,经典的计算模型都显得有点笨重:

Expression层面:基于 expression tree 的解释执行往往使得一些看上去很简单的表达式执行起来很复杂,以上述 SQL 的 filter 条件为例:c1 < 100 and c3 = 10 这个过滤条件在数据库中会被转换为包含 7 个节点的 expression tree,对于表中的每行数据,这 7 个节点的 eval 函数都会被触发一次。而实际上,这个 expression tree 的效果与下面这段手写代码是等价的:

(input.getInt(0) < 100 && (input.getInt(2) == 10)

相比之下 expression tree 的解释执行就显得笨重很多。而且由于虚函数调用,即使是最简单的求值函数也基本无法被内联。

Operator 层面面临的问题与 Expression 类似,火山模型虽然带来了实现简单、干净的好处,但是每次计算一行结果都会有一个很长的 next 虚函数调用链(而且 operator next 函数中一般还会有一个 expression eval 的虚函数调用链)。虽然虚函数调用本身开销并不算特别大,但是仍需要花费一定的时间,而虚函数内部的操作可能就是一个简单的轻量级计算,而且每一行数据都需要若干次的虚函数调用,当数据量非常大的时候,这个开销就会变得十分可观。

除了虚函数带来的计算框架开销外,经典计算引擎还有一些其他缺点,试想上述 SQL 在火山模型中生成相应的 plan 后,其运行时的代码如下:

for(; Row row = plan.next(); row != null) {
        // send to client
}

其中 plan 即 operator tree 的 root 节点,对上述 SQL 来说就是 projection。

而如果手动写一段代码来实现上述 SQL 的话,其代码大概如下:

for(Row row in scanBuffer) {
        int c1 = row.getInt(0);
        int c3 = row.getInt(2);
        if (c1 < 100 && c3 == 10) {
                // construct new row and send to the client
        }
}

上述两段代码虽然都是一个 for 循环,但是对于第一段代码来说,for 循环里面是很深的虚函数调用,而第二段代码 for 循环里做的事则要简单的多。对 compiler 来说,越简单的代码越容易优化,在这个例子中,compiler 就可以通过将c1c3放在寄存器中来实现提速。

SQL 计算引擎的优化

从上面的介绍来看,经典 SQL 的计算引擎一个很大问题就是无论是 expression 还是 operator ,其计算的时候都大量使用到虚函数,由于每行数据都需要经过这一系列的运算,导致计算框架开销比较大,而且由于虚函数的大量使用,也影响了编译器的优化空间。在减小框架开销方面,两个常用的方法就是

  • 均摊开销
  • 消除开销

向量化执行与代码生成正是数据库从业者们在这两个方向上进行的努力。

向量化执行

向量化执行的思想就是均摊开销:假设每次通过 operator tree 生成一行结果的开销是 C 的话,经典模型的计算框架总开销就是 C * N,其中 N 为参与计算的总行数,如果把计算引擎每次生成一行数据的模型改为每次生成一批数据的话,因为每次调用的开销是相对恒定的,所以计算框架的总开销就可以减小到C * N / M,其中 M 是每批数据的行数,这样每一行的开销就减小为原来的 1 / M,当 M 比较大时,计算框架的开销就不会成为系统瓶颈了。除此之外,向量化执行还能给 compiler 带来更多的优化空间,因为引入向量化之后,实际上是将原来数据库运行时的一个大 for 循环拆成了两层 for 循环,内层的 for 循环通常会比较简单,对编译器来说也存在更大的优化可能性。举例来说,对于一个实现两个 int 相加的 expression,在向量化之前,其实现可能是这样的:

class ExpressionIntAdd extends Expression {
        Datum eval(Row input) {
                int left = input.getInt(leftIndex);
                int right = input.getInt(rightIndex);
                return new Datum(left+right);
        }
}

在向量化之后,其实现可能会变为这样:

class VectorExpressionIntAdd extends VectorExpression {
        int[] eval(int[] left, int[] right) {
                int[] ret = new int[input.length];
                for(int i = 0; i < input.length; i++) {
                        ret[i] = new Datum(left[i] + right[i]);
                }
                return ret;
        }
}

显然对比向量化之前的版本,向量化之后的版本不再是每次只处理一条数据,而是每次能处理一批数据,而且这种向量化的计算模式在计算过程中也具有更好的数据局部性。

代码生成

代码生成的思想是消除开销。代码生成可以在两个层面上进行,一个是 expression 层面,一个是 operator 层面,当然也可以同时在 expression 与 operator 层面进行代码生成。经典 SQL 计算引擎的一大缺点就是各种虚函数调用不但会带来很多额外的开销,而且还挤压了 compiler 的优化空间。代码生成可以直观的理解为在 SQL plan build 好之后,将 plan 中的代码进行一次逻辑上的内联。如果实现的好,代码生成能够将上述所说的火山模型代码转换为类似于手动优化的代码,显然和向量化执行一样,代码生成后的新代码也给编译器带来了更多的优化机会。与向量化执行相比,代码生成之后数据库运行时仍然是一个 for 循环,只不过这个循环内部的代码从简单的一个虚函数调用plan.next()展开成了一系列具体的运算逻辑,这样数据就不用再各个 operator 之间进行传递,而且有些数据还可以直接被存放在寄存器中,进一步提升系统性能。当然为了获取这些好处代码生成也付出了一定的代价,代码生成需要在 SQL 编译器编译获得 plan 之后进行额外的 code gen + jit ,对应到具体的工程实现也比向量化执行的难度要高一些。 举例来说,对于下面这条 query:

select *
from R1,
    (select R2.y, count(*)
    from R2
    where R2.x=3
    group by R2.y) R2
where R1.a=7 and R1.b=R2.y

通过代码生成技术,其执行过程会变成这样:

map<int, vector<Row>> hash_table_for_join;
map<int, int> hash_table_for_agg;
for(Row row in scanBuffer_R1) {
        int a = row.getInt(0);
        int b = row.getInt(1);
        if (a == 7) {
                // ignore the case when the key `b` doesn't exists for simplicity
                hash_table_for_join[b].push_back(row);
        }
}
for(Row row in scanBuffer_R2) {
        int x = row.getInt(0);
        int y = row.getInt(1);
        if (x == 3) {
                // ignore the case when the key `y` doesn't exists for simplicity
                hash_table_for_agg[y] = hash_table_for_agg[y] + 1;
        }
}
for (auto &v1 : hash_table_for_agg) {
        for (auto &v2 : hash_table_for_join) {
                if (v1.first == v2.first) {
                        // construct new row and send to the client
                }
        }
}

相比于传统的火山模型,上述执行过程不再以 operator 为核心,而是以数据为核心,其最大特征是将单一 operator 的执行逻辑分散在多个代码块中,模糊了 operator 之间的执行边界,从而大大降低了 operator 之间数据传递的开销。

总结

向量化执行和代码生成是现代数据库中常用的两种执行优化技术,本文通过几个案例简单地阐述了这两种技术的基本思想。这两种技术从不同角度提高了数据库 query 的执行效率,关于这两种技术更多详细的介绍可以参考这两篇论文:Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask, Efficiently Compiling Efficient Query Plans for Modern Hardware

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

数据库计算引擎的优化技术:向量化执行与代码生成 的相关文章

  • 软件测试工程师必备的10个测试技术体系(零基础入行测试必学)

    很多测试新手在刚开始学习软件测试的时候都不知道该如何开始 以及软件测试需要掌握哪些必备的知识点 以下是根据个人总结 粗略整理的一份软件测试学习大纲 基本涵盖了软件测试工程师需要掌握的全部技能 希望给准备学习测试的朋友提供一点指引和帮助 PS
  • 八大排序算法-堆排序

    在说堆排序之前 要先说明二叉堆的概念 因为堆排序就是通过二叉堆来实现的 注 以下说会用堆来作二叉堆的简称 至于堆的定义 大家可以自行查阅 在了解完堆之后 我们知道堆有大根堆和小根堆的不同 我们先了解堆排序的思想 之后用一个大根堆来实现代码

随机推荐

  • 搜索引擎-应用篇(地理位置查询)

    一 背景 查询附近的洗车店 二 原理探究 像Redis和ES都支持GEO来存储地理位置 GEO类型 地理点 geo point 即经纬度查询 地理形状查询 geo shape 即支持点 线 圈 多边形查询 GeoHash GeoHash 原
  • 转:图谱中的关系推理是什么

    知识图谱本质上是语义网络 是一种基于图的数据结构 由节点 Point 实体 和边 Edge 关系 组成 在知识图谱里 每个节点表示现实世界中存在的 实体 每条边为实体与实体之间的 关系 知识图谱是关系的最有效的表示方式 通俗地讲 知识图谱就
  • Win10企业版本激活方法

    右键管理员身份运行cmd 或者直接Win键 X 直接打开Windows Powershell 管理员 粘贴下面的命令即可 slmgr skms kms 03k org slmgr ato
  • scrollIntoView()的方法属性及使用其实现锚点定位

    scrollIntoView 方法属性 在一个移动项目中遇到个这样的需求 一个表单填写页面 每项都有表单验证 并且点击提交按钮 未通过校验的输入框下边显示校验信息 同时页面滑动定位到第一个未通过校验的输入框 我们在完成这项需求时 使用的sc
  • GROUP BY 与 HAVING

    sql语句中GROUP BY 和 HAVING的使用 count http blog 163 com hks blog blog static 214926090201382225845920 ql中的group by 和 having 用
  • swagger 接口测试,用 python 写自动化时该如何处理?

    在使用Python进行Swagger接口测试时 可以使用requests库来发送HTTP请求 并使用json库和yaml库来处理响应数据 以下是一个简单的示例代码 import requests import json import yam
  • 排序算法性能分析

    目录 实现插入排序 冒泡排序 选择排序 合并排序 快速排序算法 从小到大 插入排序 冒泡排序 选择排序 快速排序 五种排序 现在有10亿的数据 每个数据四个字节 请快速挑选出最大的十个数 并在小规模数据上验证算法的正确性 方法一 规模为10
  • javax.crypto.IllegalBlockSizeException: Input length must be multiple of 16 when decrypting with pad

    今天在做AES加密时 项目中出现javax crypto IllegalBlockSizeException Input length must be multiple of 16 when decrypting with padded c
  • 关于centos7虚拟机的问题:主机无法ping通虚拟机

    这个问题困扰了我好几天 我创建好了虚拟机就用MX ssh远程连接 发现连接超时 再三确认ip 和端口过后 还是无法连接 后来尝试在虚拟机里ping主机ip 和网关 都没有问题 问题在于主机无法ping通虚拟机ip 好在 我在网上浏览了一篇文
  • MobaXterm远程登录VirtualBox中的Linux常见问题

    2020 12 02 1 先检查linux是否开启shh服务 ssh localhost 1 如果提示 ssh connect to host localhost port 22 Connection refused 则需要下载安装ssh
  • MMDeploy详解

    MMDeploy详解 1 简介 1 1 流程简介 1 1 1 模型转换 Model Converter 1 1 2 MMDeploy 模型 MMDeploy Model 1 1 3 推理 SDK Inference SDK 1 2 支持多种
  • 5年 Python 功力,总结了 10个开发技巧!高效率开发真正的秘诀(二)

    话接上文 我又来了分享我学习到的10个开发技巧啦 学习的路上 只有多多交流才能更好更快的解决难题 在这里还是要推荐下我自己建的Python学习Q群 249029188 群里都是学Python的 如果你想学或者正在学习Python 欢迎你加入
  • camera调试:serdes camera调试

    serdes是串行器和解串器的简写 顾名思义是一种将并行数据转换成串行数据发送 将接收的串行数据转换成并行数据的 器件 camera常用的接口是MIPI高速接口 MIPI的传输距离受限 传输距离过大容易导致信号质量不佳 影响图像数据的传输
  • 多组输入方法【C语言基础】

    EOF为End Of File的缩写 通常在文本的最后存在此字符表示资料结束 在C语言中 或更精确地说成C标准函数库中表示文件结束符 end of file 在while循环中以EOF作为文件结束标志 这种以EOF作为文件结束标志的文件 必
  • 在校大学生用Python当爬虫一个月能赚3000吗?

    这个问题我挺有发言权的 我人之前和现在就是靠Python撸代码挣零花钱的 现在校学生时间多 自由度大 都知道淘宝没有什么不能卖的 合法的 基本上不论软硬件 不论是实物或服务 我研究生期间在淘宝做过python数据分析的活 每月撸代码撸出生活
  • PS全套插件一键安装包Pro中文版

    PS全套插件一键安装包Pro安装教程 1 下载解压 得到软件的安装原程序 2 双击 Project1 exe 开始安装 点击继续 3 软件能自动识别Ps软件版本和安装位置 若电脑上有多个Ps软件版本 请选择需要安装插件的版本 若只有一个Ps
  • 2020-05-07

    可不可以有大神救救孩子 Python作业不会做
  • mysql驱动版本支持

    Connector J 5 1 支持Mysql 4 1 Mysql 5 0 Mysql 5 1 Mysql 6 0 alpha这些版本 Connector J 5 0 支持MySQL 4 1 MySQL 5 0 servers distri
  • ecahrts给地图添加贴图纹理

    有个可视化需求给地图添加纹理 翻了好久没翻到成品 希望这篇文章对后面的人有所帮助吧 虽然echarts文档里面也有说明 但是echarts文档对一些配置属性确实不敢恭维 实现是以html实现的 vue其实一样的道理 不会差距太大 html代
  • 数据库计算引擎的优化技术:向量化执行与代码生成

    原文链接 https zhuanlan zhihu com p 100933389 阿尔德里竹 作者 徐飞 李德竹 随着数据库软硬件技术的发展 经典的 SQL 计算引擎逐渐成为数据库系统的性能瓶颈 尤其是对于涉及到大量计算的 OLAP 场景