您的位置: 首页 > 技术杂谈 > 正文

SQL优化-RBO（Rule-Based Optimization）

2022-08-29 16:00 https://my.oschina.net/u/5148943/blog/5570869 开务数据库次阅读条评论

SQL 优化的过程可以分为逻辑优化和物理优化两个部分。逻辑优化主要是基于规则的优化，简称 RBO（Rule-Based Optimization）。物理优化会为逻辑查询计划中的算子选择某个具体的实现，需要用到一些统计信息，决定哪一种方式代价最低，所以是基于代价的优化 CBO（Cost-Based Optimization）。

优化器是开务数据库中的一个核心的模块，开务数据库使用优化器来完成对 SQL 语句优化并得到最优的逻辑计划，开务数据库里的优化器分为 RBO 和 CBO 两个阶段。

RBO 是基于规则的优化，这些规则背后的原理是关系代数的等价变换，其中典型的规则包括：列剪裁，谓词下推等。RBO 将内置的规则作为优化的基础，同时这些规则是硬编码在开务数据库的代码中的，RBO 会根据这些规则从目标 SQL 诸多可能的代数转换中选择一条来作为逻辑计划。

开务数据库的 RBO 优化器采用了 Optgen 语言编写，它提供了一种直观的语法来定义、匹配和替换目标表达式树中的节点。优化器规则的编写便是基于这种语言，使用 Optgen 语言可以很容易实现 RBO 规则。

开务数据库的 RBO 规则实现如下图所示，①被称为匹配模式，②被称为替换模式，优化器规则是某表达式满足①模式，然后转化为②模式的表达式。

①的匹配模式又分为三部分，第一部分中括号内是规则的名称，在 Opt 文件编译时会作为规则的标识，第二部分是第二行左小括号后位规则作用域，在开务数据库内有明确的类型划分。编写规则时要清楚这条规则是针对哪种类型表达式发生作用，第三部分是剩下的规则部分，是规则的匹配条件。

模式①匹配条件是等值表达式，左孩子不是变量，右孩子是变量。这里的 NormalizeEq 是名称，Eq 是规则类型，针对等值表达式。模式②表示新构建一个等值表达式，只是与原表达式相比，左右孩子互换。示例：1=a => a=1

开务数据库内置了上百种 RBO 规则，支持大量的 SQL 语句的代数优化，包括传统的列裁剪、最大最小消除、投影消除、谓词下推等等，也包括一些复杂的 Join 等下推操作。TryDecorrelateGroupBy，这个规则的 OptGen 规则描述如下：

[TryDecorrelateGroupBy, Normalize]
(InnerJoin | InnerJoinApply
    $left:*
    $right:* &
        (HasOuterCols $right) &
        (GroupBy | DistinctOn
            $input:*
            $aggregations:*
            $groupingPrivate:*
        ) &
        (IsUnorderedGrouping $groupingPrivate)
    $on:*
    $private:*
)
=>
(Select
    ((OpName $right)
        (InnerJoinApply
            $newLeft:(EnsureKey $left)
            $input
            []
            $private
        )
        (AppendAggCols
            $aggregations
            ConstAgg (NonKeyCols $newLeft)
        )
        (AddColsToGrouping $groupingPrivate (KeyCols $newLeft))
    )
    $on
)

TryDecorrelateGroupBy 主要作用在 InnerJoin | InnerJoinApply 操作中，它将 Join“下推”到 GroupBy 运算符中，以尝试继续“挖掘”以找到并消除不必要的相关性。最终的希望是触发 DecorrelateJoin 规则，将 JoinApply 操作符转换为非 Apply Join 操作符。

SELECT left.x, left.y, input.*
FROM left
INNER JOIN LATERAL
 (
  SELECT COUNT(*) FROM input WHERE input.x = left.x GROUP BY c
) AS input
ON left.y = 10
=>
SELECT CONST_AGG(left.x), CONST_AGG(left.y), COUNT(*)
FROM left WITH ORDINALITY
INNER JOIN LATERAL
 (
  SELECT * FROM input WHERE input.x = left.x
) AS input
ON True
GROUP BY input.c, left.ordinality
HAVING left.y = 10

开务数据库采用了 Optgen 语言作为 RBO 规则的编写语言，通过上面的例子可以看出，按照既定模式添加完善 RBO 规则十分便捷，通过编译可以将规则嵌入到系统 RBO 规则框架中；后续会有更深入的关于 RBO 使用框架与大家分享，敬请期待！

开务数据库是一款浪潮集团核心研发的先进、安全的云原生分布式数据库；具备云原生、多中心、高可用、事务强一致等特性，满足HTAP场景需求。业务范围覆盖能源、工业互联网、政务、教育、金融等多行业。我们是一支平均年龄30岁的年轻团队，在短短不到三年的时间里，我们已取得近300项发明专利受理，10项自有产品软著授权。热烈欢迎广大伙伴加入我们的团队，热门岗位火热招聘中，简历投递邮箱：zhoubeili@inspur.com / bixueting@inspur.com

数据库存储内核研发工程师

工作职责：

1、负责存储子系统的研发路线规划、架构设计和关键技术问题攻关；

2、负责编写功能测试用例，测试工具进行系统验证；

3、负责数据库的系统性能诊断与调优；

4、负责数据库相关关键技术的预研和在团队中的引导；

5、深入理解业务场景的数据库存储需求，针对性的为不同业务场景提供最合适的存储方案。

任职要求：

1、学历：本科或者本科以上学历；

2、专业：计算机或相关专业；

3、专业知识：

— 3 年及以上 GO/C++ 开发经验；