海山数据库(He3DB)原理剖析:浅析OLAP数据库计算引擎中的统计信息

本文主要是介绍海山数据库(He3DB)原理剖析:浅析OLAP数据库计算引擎中的统计信息,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

背景:

统计信息在计算引擎的优化器模块中经常被提及,尤其是在基于成本成本优化(CBO)框架中统计信息发挥着至关重要的作用。CBO旨在通过评估执行查询的可能方法,并选择最有效的执行计划来提高查询性能。而统计信息则提供了关于数据分布、数据倾斜等方面的关键信息,帮助CBO做出最优的决策。无论是传统数据库MySQL、PostgreSQL,还是Hive、Spark计算引擎、Doris、StarRocks 等OLAP引擎,都针对CBO模块做了大量开发工作。而统计信息作为影响CBO决策的最重要因素,计算引擎需要对统计信息的搜集、加工、利用多个阶段进行打磨优化,最终帮助用户业务提供成本最低的执行计划。

本文将会从统计信息的常见来源以及计算引擎如何利用统计信息多个方面着手,综合多个计算引擎的CBO统计信息框架优化案例,浅析计算引擎的CBO统计信息。

图1 计算引擎的优化器模块

一、统计信息的种类与来源

综合多个计算引擎的统计信息集成情况,可以发现大家获取统计信息手段不尽相同,一种是精准搜集统计信息,一种是采用多种手段对数据进行评估获取统计信息。

常见的基本统计信息类型有min/max/ndv/totalSize/fileNum,各家计算引擎会根据引擎特点继续扩展不同的统计信息,如涉及到数据整体评估的统计信息,MVC(高频非NULL值)、HiSTOGRAM(直方图)等。

1、基本类型统计信息

基本统计类型是相对精准的信息,一般用户analyze语句获取的统计信息多数是这种min/max等基本信息。一般表级别、分区级别、字段级别都会有相应的统计信息。在不同的SQL业务中,计算引擎会根据SQL中的谓词语句、table scan的具体表来分别利用哪种统计信息。

如select count(*) from testtbl; 显然这条语句会用到表级别统计信息,select count(distinct id) from testtbl where date=2024; 这条语句一般就会用到分区date以及字段id的统计信息。

基本类型统计信息一般都是实时获取+定时任务获取。如大数据中Hive每次执行写入任务之后会有线程启动搜集写入数据的基本统计信息,一定程度上保证统计信息实时准确,StarRocks会有定时任务自动执行内表的统计信息搜集。

2、估算类型统计信息

估算类型统计信息一般泛指对数据集的一个整体评估,能够在牺牲一定的准确性的情况下给出数据集的一个分布情况,常见的如MVC。这种统计信息适合对于在大规模数据集下,基本统计信息搜集相对代价较高且基本统计信息缺乏对整体数据集的极端分布(如数据倾斜)的体现,而估算类型的统计信息能够告诉计算引擎数据的分布状况,能够使任务避免数据倾斜等情况。

一般评估数据分布的统计信息都会采用histogram直方图,多数计算引擎根据自身的业务特性实现了不同的直方图。直方图的基本原理是将数据排序后分成若干个bucket桶,并记录每个桶中数据的最大值、最小值、频次出现等信息。常见的直方图有Equal-width Histogram、Equi-height Histogram等。像Doris和StarRocks,均实现了Equi-height Histogram。Equi-width Histogram(等宽直方图)是将数据最大、小值之间的区间等分为N份,每个桶中最大、小值之差都为整体数据最大、小值之差/N,既所谓“等宽”。

Equi-height Histogram(等高直方图),它的桶宽度并不相等,取而代之的是,等高直方图会保证每个桶中数值的频次之和接近总行数的 1/N,就是落入每个桶里的值数量尽量相等。数据数据分布范围比较大时也可以很好的保证误差。各种计算引擎会根据其擅长的业务特性去改进直方图,以尽可能避免直方图落入局部最优的境地,这里不过多详细解释直方图实现原理,大家可以参考直方图的基本原理以及具体计算引擎实现去做细致研究。

一般情况下,估算类型统计信息能够相对准确、相对高效的应用在一些大数据量的表上,尤其是一些数据湖的大表(PB级别),但是一般的估算统计信息实现还是需要对数据做一遍整体扫描,所以多数情况下的实现会判断大小表来决定是否整体数据评估信息搜集还是采样搜集。判断是否整体还是采样搜集各家计算引擎都会有不同的规则,如StarRocks、Doris([Enchancement](statistics) Support sampling collection of statistics by weizhengte · Pull Request #18880 · apache/doris · GitHub)搜集histogram直方图统计信息支持设置最大行数采样、根据比例进行采样;也有的利用统计学方式如伯努利采样PrestoDB(Add reservoir_sample aggregation function by ZacBlanco · Pull Request #21296 · prestodb/presto · GitHub)。

apache datasketches是另一种可用的非常高效的数据分布计算工具, 目前基于apache datasketches算法库实现的直方图统计信息如Hive4.0,草图中实现了各种近似估算方法,很多方法都来源于数据库领域的论文算法。Sketch 结构即「数据草图」结构,主要是为了计算海量的流式数据的概率指标而设计的一种数据结构。

一般占用固定大小的内存,不随着数据量的增加而增大。这种结构通过巧妙地保存或丢弃一些数据的策略,将数据流的信息抽象存储起来,汇总成 Sketch 结构,最终能根据 Sketch 结构还原始数据的分布,实现基数统计、分位数计算等操作。

Spark3.5之后也使用apache datasketches实现了一些估算函数如ndvApache Spark ❤️ Apache DataSketches: New Sketch-Based Approximate Distinct Counting | Databricks Blog ,基于sketch的估算函数能有效加速Spark对大数据集的一些数据分布估算,比如在此之前,统计数据集中的ndv,一般spark用户都会count(distinct),这种计算十分耗时,而且计算结果不会有临时存储,每次都需要重新计算,而datasketch能够利用经过验证的统计学算法,快速的返回计算结果,结果还可以持久化到sketch的存储中,能够大大加速一些统计类型查询。

二、统计信息带来的常见收益

我们常常说统计信息能够加速查询,能够优化执行计划,那么从计算引擎角度来说,统计信息利用最多的地方有哪些呢?这里列举几个关键的点,我们可以从不同的计算引擎中了解统计信息是怎样给用户的业务带来加速。

1、join选择

join能力是考量OLAP引擎的关键指标。如何在复杂的SQL语句中找到优化的join方式是CBO优化要做的事情。分析中常见的hash join,涉及到大小表join,一个关键的因素是怎么判断表的大小,最直接的指标就是表的统计信息,优化器根据表大小,把小表作为build side来构造哈希表放入内存,大表作为probe side,这样可以有效避免数据的shuffle过程,主流的计算引擎都会支持这种高效的join方式。

还有join reorder优化,经常会根据计算过程中生成的临时统计信息对执行计划动态调整,修改join算法,简而言之,join优化的基本要素就是需要有相对准确的统计信息,最直接的统计信息如rowCount判断表大小。计算引擎一般利用这些基础的统计信息再结合一些reorder算法或者自定义的规则,完成join查询的最优执行路径选择。

2、自适应任务执行

Adaptive Query Execution即AQE也是计算引擎高阶优化经常谈到的一个点。AQE执行可以理解为动态CBO,可以根据运行期的一些临时数据的统计信息,动态调整CBO选择的执行路径。典型的一个是Spark AQE,其根据在运行时统计信息(runtime statistics)在查询执行的过程中进行动态(Dynamic)Spark的查询优化,AQE可以Spark运行query stage阶段准确获取统计信息,然后进行CBO优化剩余的stage,可以有效的动态合并Spark shuffle分区,避免join阶段的一些数据倾斜问题。

无独有偶,除了Spark AQE,其他计算引擎也都有很多类似AQE优化。(个人理解AQE优化一般针对中间数据有落盘的计算过程,如上面提到的Spark(shuffle阶段),所以可以推测其他有中间数据可以物化/落盘行为的计算引擎也可以去做这种优化。)。

TrinoDB近年来增强了自身的容错计算能力,即设计了中间shuffle数据落盘的一种计算模式(fte),可以在部分task运行失败时从磁盘中恢复中间执行数据然后重新执行,TrinoDB的这种fte模式很适合使用AQE优化,用于减少运行期启动不必要的task,如Adaptive planning framework in FTE by gaurav8297 · Pull Request #20276 · trinodb/trino · GitHub 就是利用运行期统计信息做一些自适应优化;

PrestoDB虽然没有fte执行模式,但是其曾经也做过一些中间数据物化以提高task容错的开发如[Design] Exchange Materialization · Issue #12387 · prestodb/presto · GitHub ,其思想会把中间数据物化成一个临时表供下游task消费,那么很显然的优化就是获取这个中间表的统计信息来对下游的CBO执行计划做动态自适应调整Initial Support of Adaptive Optimization with Presto Unlimited by pguofb · Pull Request #14675 · prestodb/presto · GitHub。

类似的,Hive3其实就有AQE优化,核心思想缓存中间运行期的统计信息,动态修正CBO执行计划、动态调整分区裁剪优化等[HIVE-17626] Query reoptimization using cached runtime statistics - ASF JIRA 。所以,一旦清楚了AQE思想,每一种计算引擎都可以根据自己运行期的统计信息特点做进一步动态优化,给与业务最好的加速体验。

3、聚合下推优化

计算引擎中的聚合算子如sum、count是相对比较消耗计算资源的操作,常规执行逻辑就是扫描数据的每一行来进行各种加减操作。但是如果已经搜集了存储表的统计信息如rowCount,那么像这种count算子就是一个O(1)的简单元数据操作,计算引擎不需要计算直接返回已经搜集的统计信息即可。

这种聚合下推的优化在各个计算引擎中基本都有实现,尤其是针对底层存储采用Parquet/ORC这种开发式列存的文件格式(如Iceberg的metadata文件就记录了详细的Parquet/ORC统计信息),如Spark利用Iceberg的统计信息,做一些下推的优化操作,如TrinoDB也做了类似的基于统计信息的聚合下推操作优化Add aggregation pushdown support for count using Iceberg Metrics by osscm · Pull Request #15832 · trinodb/trino · GitHub 。

当然,Hadoop之上经典的Hive计算引擎也早就有这种聚合下推优化,比如有些Hive优化参数会控制是否启动MR分布式任务,如参数hive.compute.query.using.stats,该参数开启的情况下,Hive计算引擎会去判断当前表的统计信息rowCount是否最新,如果统计信息最新,则在SQL语句中涉及到count的操作算子直接通过统计信息返回,避免了启动分布式任务去计算。

三、小结

无论是数据库领域还是大数据领域,CBO优化都是非常重要,而统计信息则是作为CBO优化的最关键一环,每一种计算引擎都会根据自身擅长的业务特点进行统计信息的搜集/利用,从而获得最佳的执行计划。如何准确且轻量地获取统计信息,并合理地应用在CBO框架以及其他优化中,是一个非常值得探索的方向。

四、作者介绍

张步涛,中国移动云能力中心数据库产品部-OLAP数据库开发工程师。主要参与OLAP内核研发/湖仓一体研发相关工作。

这篇关于海山数据库(He3DB)原理剖析:浅析OLAP数据库计算引擎中的统计信息的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/893809

相关文章

使用Python从PPT文档中提取图片和图片信息(如坐标、宽度和高度等)

《使用Python从PPT文档中提取图片和图片信息(如坐标、宽度和高度等)》PPT是一种高效的信息展示工具,广泛应用于教育、商务和设计等多个领域,PPT文档中常常包含丰富的图片内容,这些图片不仅提升了... 目录一、引言二、环境与工具三、python 提取PPT背景图片3.1 提取幻灯片背景图片3.2 提取

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息:读取"/proc/cpuinfo"文件获取磁盘信息:读取"/proc/diskstats"文

数据库面试必备之MySQL中的乐观锁与悲观锁

《数据库面试必备之MySQL中的乐观锁与悲观锁》:本文主要介绍数据库面试必备之MySQL中乐观锁与悲观锁的相关资料,乐观锁适用于读多写少的场景,通过版本号检查避免冲突,而悲观锁适用于写多读少且对数... 目录一、引言二、乐观锁(一)原理(二)应用场景(三)示例代码三、悲观锁(一)原理(二)应用场景(三)示例

Spring Boot循环依赖原理、解决方案与最佳实践(全解析)

《SpringBoot循环依赖原理、解决方案与最佳实践(全解析)》循环依赖指两个或多个Bean相互直接或间接引用,形成闭环依赖关系,:本文主要介绍SpringBoot循环依赖原理、解决方案与最... 目录一、循环依赖的本质与危害1.1 什么是循环依赖?1.2 核心危害二、Spring的三级缓存机制2.1 三

C#中async await异步关键字用法和异步的底层原理全解析

《C#中asyncawait异步关键字用法和异步的底层原理全解析》:本文主要介绍C#中asyncawait异步关键字用法和异步的底层原理全解析,本文给大家介绍的非常详细,对大家的学习或工作具有一... 目录C#异步编程一、异步编程基础二、异步方法的工作原理三、代码示例四、编译后的底层实现五、总结C#异步编程

浅析Java中如何优雅地处理null值

《浅析Java中如何优雅地处理null值》这篇文章主要为大家详细介绍了如何结合Lambda表达式和Optional,让Java更优雅地处理null值,感兴趣的小伙伴可以跟随小编一起学习一下... 目录场景 1:不为 null 则执行场景 2:不为 null 则返回,为 null 则返回特定值或抛出异常场景

Node.js 数据库 CRUD 项目示例详解(完美解决方案)

《Node.js数据库CRUD项目示例详解(完美解决方案)》:本文主要介绍Node.js数据库CRUD项目示例详解(完美解决方案),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考... 目录项目结构1. 初始化项目2. 配置数据库连接 (config/db.js)3. 创建模型 (models/

Mysql如何将数据按照年月分组的统计

《Mysql如何将数据按照年月分组的统计》:本文主要介绍Mysql如何将数据按照年月分组的统计方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql将数据按照年月分组的统计要的效果方案总结Mysql将数据按照年月分组的统计要的效果方案① 使用 DA

Go 语言中的select语句详解及工作原理

《Go语言中的select语句详解及工作原理》在Go语言中,select语句是用于处理多个通道(channel)操作的一种控制结构,它类似于switch语句,本文给大家介绍Go语言中的select语... 目录Go 语言中的 select 是做什么的基本功能语法工作原理示例示例 1:监听多个通道示例 2:带

鸿蒙中@State的原理使用详解(HarmonyOS 5)

《鸿蒙中@State的原理使用详解(HarmonyOS5)》@State是HarmonyOSArkTS框架中用于管理组件状态的核心装饰器,其核心作用是实现数据驱动UI的响应式编程模式,本文给大家介绍... 目录一、@State在鸿蒙中是做什么的?二、@Spythontate的基本原理1. 依赖关系的收集2.