[数据库技术]查询引擎-查询优化
发布时间：2022-11-21 11:02:42 所属栏目：MySql教程 来源：
导读： 数据库架构可以简要分为两个部分：计算/查询引擎和存储引擎。
计算/查询引擎可以分为两个部分：
给定一个SQL query, 查询引擎会进行：
Parser- 语法分析器进行SQL语法分析。生成语法分析
计算/查询引擎可以分为两个部分：
给定一个SQL query, 查询引擎会进行：
Parser- 语法分析器进行SQL语法分析。生成语法分析
|
数据库架构可以简要分为两个部分：计算/查询引擎和存储引擎。 计算/查询引擎可以分为两个部分： 给定一个SQL query, 查询引擎会进行： Parser- 语法分析器进行SQL语法分析。生成语法分析树AST。 逻辑查询优化-语法分析树转为逻辑执行计划。 物理查询优化-逻辑执行计划转为物理执行计划。 执行器-开始执行物理执行计划。 以上工作line比较清晰直白，本文主要介绍三个其中比较重要的组件，最后讨论当前的研究热点AI4DB： 查询优化 给定一个SQL query，数据库引擎需要找到一个执行计划execution plan去执行得到最终结果。比如说执行 A_{\theta} join B_{\theta} join C_{\theta} , A_{\theta} 表示在table/column A上的过滤的操作，那么三种方案，1）先执行A_{\theta} join B_{\theta}，得到的结果再join C_{\theta} 。2）先执行A_{\theta} join C_{\theta}，得到的结果再join B_{\theta}。3）先执行B_{\theta} join C_{\theta}，得到的结果再join A_{\theta}。执行优化就是要回答这三种方案中 哪一个更快，也就是执行结束更快。 逻辑查询优化 逻辑查询优化 可以理解为独立于运行机器物理实体的 逻辑上即可成立的优化规则。 比如包括： 谓词下推：在一个table上的过滤操作可以尽早完成，因为这样可以缩小中间数据规模。 join的交换律：A_{\theta} join B_{\theta} ，和 B_{\theta} join A_{\theta} 逻辑上相等，可得到同样的最终结果。 Jon的结合律： 多表join，join顺序无论怎么，都可得到最终相同结果。 基数估计(cardinality estimation) 其中一些逻辑查询优化可直接使用比如谓词下推。但有些规则需要收集一些信息才能做出判断。比如，对于多表join的场景，我们想达到的一个比较好的效果是：先完成一些表的join操作，可显著减少中间数据的大小。但如何判断那些表先做join操作能够产生小的中间结果呢，只能靠估计。这就是查询优化中的经典问题-基数估计cardinality estimation。 基数简单来说就是：tables之间进行join后的结果大小（tuples个数）。执行 A_{\theta} join B_{\theta} join C_{\theta}，如果基数大小 card(A_{\theta} join B_{\theta}) = 10, card(B_{\theta} join C_{\theta}) = 100, card(A_{\theta} join C_{\theta}) = 1000。那么我们就选择 (A_{\theta} join B_{\theta}) 先完成，而后在join C_{\theta}。 现在就是一个统计学的问题了，我们如何能够比较准确地预估table之间的基数大小呢。 目前工业界和学术界的方法，可归为两个大方向：传统方法 和基于learning的方法。 传统方法：主要依靠数学模型/概率统计。比如PostgreSQL, MySQL会对table的每个column建立直方图。PostgreSQL手册一个推荐的优化tips就是ANALYZE TABLE。这个命令其实就是在对这个table建立直方图。 然而这种方法对于单个table上的过滤操作后的基数预估 准确度尚可接受。但是对于多表join准确度就很差了，因为多表之间的数据相关性没有被描述出来，table A的一个key可能匹配table B的10w行数据。这是简单直方图信息无法表达的。当前postgreSQL对于table join的基数估计，就简单化为 |A| * |B| / (A *B)，这个简单粗暴的联合概率分布其实在假设tables之间是data independent。 对于传统方法的cardInality estimation，详细介绍和研究，强烈建议大家读一读： Leis, Viktor, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, and Thomas Neumann. "How good are query optimizers, really?."Proceedings of the VLDB Endowment9, no. 3 (2015): 204-215. 数据库领域总有些经典文章，没有将很高大上的东西，只是把一些经典的问题，掰开了揉碎了分析问题。会豁然发现一些你我之前的疑问得到了解答，你我之前说不清楚但又在质疑的问题得到了分析。上述这篇文章就是这样的存在。 基于Learning的方法：传统方法是依赖数学模型。learning的方法底层当然也是数学模型，因为learning的本质还是数学。但得益于AI/CV/NLP领域的快速发展，近几年涌现出来的各种各样的强大模型 也给数据库带来了新的思考机会。 Learning的基数估计基本可以分为三个方向：query-driven, data-driven and hybrid-driven (combine data and query)。 Query-driven就是从过去的查询query的样本总学习。思想就是有监督学习，当收集到了足够多的历史查询样本和其对应的cardinlity结果作为label。就可以借助当前各种强大模型去build up监督学习的模型。SIGMOD/VLDB在过去4年中涌现出来很多这个方向的paper。 Data-driven就是从dataset中建立数据分布模型。思想就是无监督学习，但可以对一个数据集build up一个足够复杂的数据模型，从一定程度上也就描述出了之前提到的多表之间的数据相关性，模型可以意识到table A的一个key可能匹配table B的10w行数据。这个方向我觉得SIGMOD/VLDB上 最亮眼的工作来自于UC Berkeley RISELab 的Yang zongheng, 和阿里达摩院的 Rong Zhu。感兴趣在其主页阅读最新工作。 Hybrid-driven 比较好懂了， 就是把query样本的信息 和 dataset的信息同时利用起来。这个方向的工作NUT的Gao cong的工作UAE，我觉得比较有代表性。 基于learning的基数估计，目前还是预研状态，距离像传统方法一样嵌入MySQL，PostgreSQL作为工业通用还有距离。Query-driven的难点主要在于1）如何在收集新的query samples后去动态update模型。2）如果预测很不准（可能查询的query和query samples差距很大），我怎么意识到。就是最好能给个guarantee bound，最差不能差过PostgreSQL的传统直方图方法。Data-driven的难点主要在于1）模型一般很high weight, 难以兼顾accuracy和估计时间。2）如何解决用户数据安全问题。清华Li guoliang老师的团队和华为高斯数据库合作已经在AI4DB上有一些技术实现在OpenGauss，感兴趣的可以去看一看。 执行计划的枚举 (plan space search/enumeration) 回忆上面我们用到的例子： 执行 A_{\theta} join B_{\theta} join C_{\theta} , A_{\theta} 表示在table/column A上的过滤的操作，那么三种方案，1）先执行A_{\theta} join B_{\theta}，得到的结果再join C_{\theta} 。2）先执行A_{\theta} join C_{\theta}，得到的结果再join B_{\theta}。3）先执行B_{\theta} join C_{\theta}，得到的结果再join A_{\theta}。 这里从Join ordering的角度，我们就有三个potential execution plan。如果考虑每个操作所用的物理运行实现，比如join是用hash join还是sort merge join运行，Plan的可能性就更多了。这里我们先关注逻辑execution plan, 那么plan的可能性主要是和join order的可能性相关。比如对于一个n-way join的多表join，考虑left-deep tree的plan，有 n! 中可能性。考虑bushy tree，有下图中可能性。left-deep tree简单理解为右节点总为叶子节点的二叉树，bushy tree则是右节点可以是一个小二叉树。 当table比较多时，是很个的大数了。在PostgreSQL中，对于join在16个以下默认采用DP去暴力搜索整个plan space数据库查询操作，当join更多是则采用遗传算法。当然这两种以外，还有很多算法，这里推荐一篇我觉得讨论比较仔细的paper: “Adaptive Optimization of Very Large Join Queries.” 一作是DB大牛 TUM的Thomas Neumann。这边文章讨论到了over 4000个关系的plan search。当然我不确定这么大的table对于现实操作环境是否有意义，一个query需要涉及到那么多table，只能说明底层数据关系该重新调整了。但是文章中对分别small query, mid query和very large query对作了讨论，读下来能对问题有系统的认识。 最后，plan search当然也在AI4DB中有工作，在下面会一起讨论。 计划的cost (which plan is better) 上节讨论对于一个query，它到底有多少可能plan。现在讨论这些plan中哪一个好。 “好”的定义一般是以执行时间execution time来作为衡量标准。一个plan能在当前的物理机子上执行地越快，就被认为越好。当前商业或成熟开源数据库中常用的是cost-based query optimizer, 也就是计算一个cost，把这个cost数值看成与执行时间正相关。比如在PostgreSQL中，query optimzer中cost的计算就主要基于CPU处理器的cost，和IO的cost。那么这两者的cost和谁有关呢，很明显就是1）数据量, 2)操作实现和3)机器特性。 数据量就是我们前面提到的cardinality。数据量越大，CPU cost就约大，IO的 cost也就越大。操作实现就是当前做一个操作所用的算法。比如hash join和nest loop join的算法计算方式肯定不一样，因为hash join需要build hash table，而nest loop join不需要build啥，而是一直用大表的tuple扫描小表。机器特性就比较好理解了，做同样一个操作，一台机子的CPU可能比较强但是IO非常慢，另一个机子可能CPU比较弱但是磁盘用的傲腾非常快。所以最后，对于算一个plan的cost，我们可以建立一个cost model = F(数据量，操作实现，和机器特性)。在用cost比较那个plan好的时候，我们不仅把plan的tree形状定下来了，也把tree的每个节点用什么算法实现也定下来了。 当然cost-based的query optimization只是比较plan的方法之一。这里主要讨论它是因为我目前接触的数据库中比较有限，这其中cost-based比较常见。比如单机PostgreSQL, 分布式Hive的calcite都是cost-based的。 另外上面提到以plan execution作为cost只是最简单直接的想法，但其实我们可以build up自己的cost model让其能反映出我们在乎的资源cost。比如当前公有云服务商就可以build up自己的cost，因为execution time可能不是首要服务衡量标准，用了多少内存，起了多少线程，多少query正在并行等，都是作为厂商可以考虑的资源消耗。比如，对于优先级比较低的用户，可以刻意拉高其内存使用的cost weight，从而让其最后选择到的plan使用的内存都更少一点。这个plan执行起来可能会慢一些，但是厂商就可以把更多资源节省给优先级高的用户使用。 AI4DB中的learning for query opitmization AI4DB自从18年Andy的AutoTune 和谷歌的Learned index, 就掀起了数据库领域的一阵小革命。大家都在使用learning去找数据库种不同的切入点优化。query optimizer当然是其中比较容易想到的。这里我总结learning for query optimizer的几个方向，以及值得读的代表paper。后面我会在选择几篇来详细介绍。 用learning学习整个query optimzier, 输出是一个plan 用learning学习query optimzier的部分组件 比如join ordering，或者输出的是一些优化/调优的hint tips 用learning学习cardinality estimation (这个方向最令我深刻的是NeuroCard, 和上面的Balsa是同一作者。这一篇推荐大家，同时结合VLDB那篇survey "Are We Ready" 基本可以了解这个方向的当前进展) 哈哈哈，最后一篇是夹带私货，这是作者我的个人工作，已accpted by SIGMOD 2023。之后和大家详细讨论。 （编辑：我爱资讯网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
站长推荐