圈子推荐
查看所有吧>>
活跃用户
    Vastdata 核心技术-SQL引擎(1)

     SQL引擎是数据库系统重要组成部分,它的主要职责是负责将应用程序输入的SQL在当前负载场景下生成高效的执行计划,在SQL的高效执行上扮演重要角色。SQL在SQL引擎里执行过程,如图1所示。

    1 SQL执行流程:

      从图1中可以看出,应用程序的SQL需要经过SQL解析生成逻辑执行计划、经过查询优化生成物理执行计划,然后将物理执行计划转交给查询执行引擎做物理算子的执行操作。

     SQL解析通常包含词法分析、语法分析、语义分析几个子模块。SQL语言是介于关系演算和关系代数之间一种描述性语言,它吸取了关系代数中一部分逻辑算子的描述,而放弃了关系代数中“过程化”的部分,SQL解析主要的作用就是将一个SQL语句编译成为一个由关系算子组成的逻辑执行计划。

      描述语言的特点是规定了需要获取的“WHAT”,而不关心“HOW”,也就是只关注结果而不关注过程,因此SQL语言描述性的特点导致查询优化在数据库管理系统中具有非常重要的作用。

      查询重写则是在逻辑执行计划的基础上进行等价的关系代数变换,这种优化也可以称为代数优化,虽然两个关系代数式获得的结果完全相同,但是它们的执行代价却可能有很大的差异,这就构成了查询重写优化的基础。

      在早期的数据库管理系统中,通常采用基于启发式规则的方法来生成最优的物理执行计划,但是这种基于规则的优化的灵活度不够,常常导致产生一些次优的执行计划,而代价估算的引入,则从根本上解决了基于规则优化的不足。

    基于代价的优化器一方面生成“候选”的物理执行路径,另一方面对这些执行路径计算它们的执行代价,这样就建立了执行路径的筛选标准,从而能够通过比较代价而获得最优的物理执行计划。

    2 SQL解析

    SQL语句在数据库管理系统中的编译过程符合编译器实现的常规过程,需要进行词法分析、语法分析和语义分析。

        · 词法分析:从查询语句中识别出系统支持的关键字、标识符、操作符、终结符等,每个词确定自己固有的词性。

       · 语法分析:根据SQL语言的标准定义语法规则,使用词法分析中产生的词去匹配语法规则,如果一个SQL语句能够匹配一个语法规则,则生成对应的抽象语法树(Abstract Syntax Tree,AST)。

      · 语义分析:对语法树(AST)进行有效性检查,检查语法树中对应的表、列、函数、表达式是否有对应的元数据,将抽象语法树转换为逻辑执行计划(关系代数表达式)。

    SQL语言标准中,确定了SQL语言的关键字以及语法规则信息,SQL解析器在做词法分析的过程中会将一个SQL语句根据关键字信息以及间隔信息划分为独立的原子单位,每个单位以一个词的方式展现,例如如下SQL语句:

      

    SELECT w_name FROM warehouse WHERE w_no = 1;


    可以划分的关键字、标识符、操作符、常量等原子单位,如下所示:

    语法分析会根据词法分析获得的词来匹配语法规则,最终生成一个抽象语法树(AST),每个词作为语法树的叶子结点出现,如下图所示。

     抽象语法树表达的语义还仅仅限制在能够保证应用的SQL语句符合SQL标准的规范,但是对于SQL语句的内在含义还需要做有效性的检查。

      · 检查关系的使用:FROM子句中出现的关系必须是该查询对应模式中的关系或视图。

      · 检查与解析属性的使用:在SELECT句中或者WHERE子句中出现的各个属性必须是FROM子句中某个关系或视图的属性。

      · 检查数据类型:所有属性的数据类型必须是匹配的。

     在有效性检查的同时,语义分析的过程还是有效性语义绑定(Bind)的过程,通过语义分析的检查,抽象语法树就转换成一个逻辑执行计划,逻辑执行计划可以通过关系代数表达式的形式来表现。

    3 查询优化

      SQL语句在编写的过程中,数据库应用开发人员通常会考虑以不同的形式来编写SQL,来达到提升执行性能的目的,那么为什么还需要查询优化器来对SQL进行优化呢?这是因为一个应用程序可能会涉及到大量的SQL语句,而且有些SQL语句的逻辑极为复杂,数据库开发人员很难面面俱到的写出高性能语句,而查询优化器则具有一些独特的优势:

      · 查询优化器和数据库应用程序开发人员之间的信息不对称,查询优化器在优化的过程中会参考数据库统计模块自动产生的统计信息,这些统计信息从各个角度来描述数据的分布情况,查询优化器会综合考虑统计信息中的各种数据,从而能够得到一个比较好的执行方案,而数据库用户一方面无法全面的了解数据的分布情况,另一方面也很难通过统计信息构建一个精确的代价模型来对执行计划进行筛选。

      · 查询优化器和数据库应用程序开发人员之间的时效性不同,数据库中的数据瞬息万变,一个在A时间点执行性能很高的执行计划,在B时间点由于数据内容发生了变化,它的性能可能就很低,查询优化器则随时都能根据数据的变化调整执行计划,而数据库应用程序开发人员则只能手动的调整SQL语句,和查询优化器相比,它的时效性比较低。

      · 查询优化器和数据库应用程序开发人员的计算能力不同,目前计算机的计算能力已经大幅提高,在执行数值计算方面和人脑相比具有巨大的优势,查询优化器对一个SQL语句进行优化时,可以从成百上千个执行方案中选择一个最优方案,而人脑要计算这几百种方案需要的时间要远远长于计算机。

      因此,查询优化器是提升查询效率的非常重要的一个手段,虽然一些数据库也提供了人工干预执行计划生成的方法,但是通常而言,查询优化器的优化过程对数据库开发人员是透明的,它自动进行逻辑上的等价变换、自动进行物理执行计划的筛选,极大的提高了数据库应用程序开发人员的“生产力”。

      依据优化方法的不同,优化器的优化技术可以分为:

      · 基于规则的查询优化(Rule Based Optimization,RBO):根据预定义的启发式规则对SQL语句进行优化。

      · 基于代价的查询优化(Cost Based Optimization,CBO):对SQL语句对应的待选执行路径进行代价估算,从待选路径中选择代价最低的执行路径作为最终的执行计划。

      · 基于机器学习的查询优化(AI Based Optimization,ABO):收集执行计划的特征信息,借助机器学习模型获得经验信息,进而对执行计划进行调优,获得最优的执行计划。

      在早期的数据库中,查询优化器通常采用启发式规则进行优化,这种优化方式不不够灵活,往往难以获得最优的执行代价,而基于代价的优化则能够针对大多数场景都高效筛选出性能较好的执行计划,但面对用户千人千面,日趋复杂的实际查询场景,普适性的查询优化由于难以捕捉到用户特定的查询需求、数据分布、硬件性能等特征,难以全方位满足实际的优化需求。

      近年来AI技术,特别是在深度学习领域,发展迅速,基于机器学习的优化器在建模效率、估算准确率和自适应性等方面都有很大优势,有望打破RBO和CBO基于静态模型的限制,通过对历史经验的不断学习,将目标场景的模式进行抽象化,形成动态的模型,自适应地针对用户的实际场景进行优化。openGauss采用基于CBO的优化技术,另外在ABO方面也在进行积极探索。

     查询重写利用已有语句特征和关系代数运算来生成更高效的等价语句,在数据库优化器中扮演关键角色,尤其在复杂查询中,能够在性能上带来数量级的提升,可谓是“立竿见影”的“黑科技”。本节介绍查询重写的基本概念、常见的查询重写技术、查询重写面临的挑战。

    查询重写的概念

      SQL语言是丰富多样的,非常的灵活,不同的开发人员依据经验的不同,手写的SQL语句也是各式各样,另外还可以通过工具自动生成。SQL语言是一种描述性语言,数据库的使用者只是描述了想要的结果,而不关心数据的具体获取方式,输入数据库的SQL语言很难做到是以最优形式表示的,往往隐含了一些冗余信息,这些信息可以被挖掘用来生成更加高效的SQL语句。查询重写就是把用户输入的SQL语句转换为更高效的等价SQL,查询重写遵循两个基本原则:

      · 等价性:原语句和重写后的语句,输出结果相同。

      · 高效性:重写后的语句,比原语句在执行时间和资源使用上更高效。

    关系代数等价变换

      查询重写主要是基于关系代数式的等价变换,关系代数的变换通常满足交换律、结合律、分配率、串接率等,如下图所示:

      因此,在熟悉了关系代数的操作之后,就可以灵活的利用关系代数的等价关系进行推导,获得更多的等价式。这些等价的变换一方面可以用来根据启发式的规则做优化,这样能保证等价转换之后的关系代数表达式的执行效率能够获得提高而非降低,例如借助分配率可以将一个选择操作下推,这样能降低上层结点的计算量,另一方面还可以用来生成候选的执行计划,候选的执行计划再由优化器根据估算的代价进行筛选。


    参考文献:

    https://opengauss.org/zh/blogs/blogs.html?post/kangyang/opengauss-sql-1-update/

    • 分享到:
    排序方式:回复时间 共有2条评论

    fdkjsghjkf 发表于 02月28日 18:05 1 楼

    本文还不全好像

    | 回复

    数据库死忠粉 发表于 03月15日 09:16 2 楼

    回复@fdkjsghjkf :参考连接里啥都有

    | 回复