Databend SQL Planner 全新设计

前言

为了支持复杂的 SQL 查询,并且提供更好的使用体验,我们在最近的几个月里对 Databend 的 SQL planner 进行了大规模的重构。目前重构已经接近尾声,感兴趣的朋友可以通过修改 Databend 的 Session settings

SET enable_planner_v2 = 1

来启用新 planner 进行抢先体验。

功能亮点

更加友好的查询体验

无论是数据分析师还是开发人员,在编写 SQL 查询的时候总会遇到各种各样的报错。尤其是在 SQL 查询较为复杂的情况下,排查报错成了许多人的噩梦(笔者本人曾经修改过有数十个 JOIN 子句的 MySQL 查询,从此对 MySQL 的错误提示深恶痛绝)。

为了改善这方面的用户体验,我们在新的 Planner 中引入了严格的语义检查环节,使得大部分的错误可以在查询编译阶段就被拦截。同时为了方便用户定位错误的位置,我们也引入了全新的错误提示算法。

当你的 SQL 查询使用了错误的语法时(比如写错了关键字,或者遗漏了某些子句),Databend 会为你提供提示信息:

Databend SQL Planner 全新设计

当你的 SQL 查询出现语义上的错误时(比如使用了不存在的 Column,或者 Column 具有歧义),Databend 也会为你指出错误出现的位置:

Databend SQL Planner 全新设计

在编写复杂查询时,依然可以获得较好的体验:

Databend SQL Planner 全新设计

支持 JOIN 查询与关联子查询

在新的 SQL planner 中,我们支持了 JOIN 查询(INNER JOIN,OUTER JOIN,CROSS JOIN)与关联子查询,并且提供了 Hash Join 算法用以执行 JOIN 查询。

JOIN 查询的相关文档已经发布在 https://databend.rs/doc/refer...,你可以查阅文档以了解 Databend 中 JOIN 查询的使用方式。

在 OLAP 查询中,JOIN 是非常重要的一部分。在传统的星型模型雪花模型中,我们都需要通过 JOIN 查询将维度表事实表连接起来以生成结果报表。

TPCH Benchmark 是由 TPC 委员会制定的一套 OLAP 查询基准测试标准,用于评测数据库系统的 OLAP 能力。其中包含了 8 张表,分别是:

  • Lineitem:产品项目
  • Orders:订单信息
  • Customer:顾客信息
  • Part:零部件信息
  • Supplier:供应商信息
  • Partsupp:零件与供应商的关系表
  • Nation:国家信息
  • Region:地区信息

TPCH 中有 22 条复杂的查询,对应不同的商业需求。这里以 Q9 查询为例,它的用途是计算指定年度地区利润额,其中包含了大量的 JOIN 计算。在新的 Planner 中,我们已经可以支持该查询:

Databend SQL Planner 全新设计

关联子查询同样也是 SQL 中的重要组成部分,通过关联子查询可以轻松表示复杂的查询逻辑。TPCH 的 Q4 就是一个例子,它的用途是计算一段时间内各优先级的订单的交付情况。其中使用了 EXISTS 关联子查询来筛选逾期收货的订单:

Databend SQL Planner 全新设计

目前 Databend 仅支持了关联子查询的简单执行,相关的查询优化工作仍在进行中,敬请期待。

全新架构

新的 SQL planner 中我们对 SQL 解析的流程进行了重新设计,以支撑更加复杂的语义分析和 SQL 优化。在新的 SQL planner 中,一条 SQL 语句通过客户端发送到 databend-query server 后,会按照下图所示的顺序由不同的组件进行处理,最终将查询的结果返回给客户端:

Databend SQL Planner 全新设计

收到 SQL 查询后,Parser 组件会对其进行解析。在此步骤中如果遇到了语法错误则会直接将错误信息返回给客户端,解析成功则会生成查询对应的 AST(抽象语法树)。

Parser

为了提供更丰富的语法分析功能和更好的开发体验,我们开发了一套基于 nom Parser combinator 的 DSL (领域特定语言) nom-rule,并基于该框架重新编写了 SQL Parser。

在这套框架下我们可以非常轻松地定义一条 Statement 的语法,以 CREATE TABLE 语句为例,我们可以使用 DSL 将其简单描述为:

CREATE ~ TABLE ~ #identifier ~ "(" ~ (#column_def)+ ~ ")" ~ ";"

优雅的语法大大提高了编写 Parser 的乐趣,欢迎有兴趣的朋友们进行尝试。

Binder

由 Parser 成功解析出 AST 后,我们会通过 Binder 对其进行语义分析,并且生成一个初始的 Logical Plan(逻辑计划)。在此过程中,我们会进行不同类型的语义分析:

  • Name resolution:通过查询 Databend Catalog 中相关的 Table, Column 对象信息,来检查 SQL 查询中引用的变量的合法性。并将合法的变量与对应的对象进行绑定,以进行后续的分析。
  • Type check:根据 name resolution 中拿到的信息,对表达式的合法性进行检查,并且为表达式寻找合适的返回类型。
  • Subquery unnesting:将表达式中的子查询提取出来,翻译成关系代数的形式
  • Grouping check: 对于含有聚合计算的查询,分析是否在聚合函数以外引用了非聚合列

通过语义分析,我们可以排除掉绝大多数的语义错误,并在编译阶段将其返回给用户,以提供最佳的错误排查体验。

Optimizer

得到初始的 Logical Plan 后,优化器会对其进行改写和优化,最终生成一个可执行的 Physical Plan 。

在新的 Planner 中,我们引入了一套基于 Transformation Rule 的优化器框架(Volcano/Cascades)。通过定义一个关系代数子树结构的 Pattern 以及相关的 Transform 逻辑,即可实现一个独立的 Rule。

以简单的 Predicate Push Down 为例:

Databend SQL Planner 全新设计

我们只需要定义输入的 Plan 的 Pattern:

impl RulePushDownFilterProject {     pub fn new() -> Self {         Self {             id: RuleID::PushDownFilterProject,             // Filter             //               //   Project             //                 //     *             pattern: SExpr::create_unary(                 Pattern {                     plan_type: RelOp::Filter,                 },                 SExpr::create_unary(                     Pattern {                         plan_type: RelOp::Project,                     },                     SExpr::create_leaf(                         Pattern {                             plan_type: RelOp::Pattern,                         },                     ),                 ),             ),         }     } }

并且实现一个进行转换的函数:

impl RulePushDownFilterProject {     pub fn apply(&self, s_expr: SExpr) -> Result<SExpr> {         let filter = s_expr.plan().into();         let project = s_expr.child(0).plan().into();         let result = SExpr::create_unary(             project,              SExpr::create_unary(                 filter,                 s_expr.child(0).child(0)             )         );                  Ok(result)     } }

Interpreter

通过 Optimizer 生成 Physical Plan 后,我们会将其翻译成可执行的 Pipeline,并交由 Databend 的 Processor 执行框架进行计算。至此 Planner 的工作就告一段落,相信读者也对新 Planner 的架构有了一个初步的了解。更多的技术细节请关注我们的后续文章。

未来规划

从头构建一个 SQL Planner 是一件十分具有挑战性的事情,但是通过重新的设计和开发,我们可以找到最适合系统本身的架构与功能。在未来的一段时间里,我们将持续完善和巩固新的 SQL Planner,功能方面则会注重于:

  • Cost-based Optimization(CBO, 基于代价的优化)
  • 分布式查询优化
  • 更多的优化规则

目前,新的 SQL planner 的迁移工作已经接近尾声,你可以通过该 issue 追踪进度。预计在七月份内所有的迁移工作将会完成, 届时我们将会发布版本更新的公告,敬请期待。

关于 Databend

Databend 是一款开源、弹性、低成本,基于对象存储也可以做实时分析的新式数仓。期待您的关注,一起探索云原生数仓解决方案,打造新一代开源 Data Cloud。

Databend SQL Planner 全新设计
文章首发于公众号:Databend

发表评论

相关文章