Skip to content

Latest commit

 

History

History
114 lines (80 loc) · 9.59 KB

CalciteOverView.md

File metadata and controls

114 lines (80 loc) · 9.59 KB
Raw

快速入门

下载构建源码

  • 运行内置example
git clone https://github.com/apache/calcite.git
cd example/csv
./sqlline
!connect jdbc:calcite:model=src/test/resources/model.json admin admin

概念

与关系代数的联系

名称 英文 符号 说明
选择 select σ 类似于 SQL 中的 where
投影 project Π 类似于 SQL 中的 select
并 union ∪ 类似于 SQL 中的 union
集合差 set-difference - SQL中没有对应的操作符
笛卡儿积 Cartesian-product × 类似于 SQL 中不带 on 条件的 inner join
重命名 rename ρ 类似于 SQL 中的 as
集合交 intersection ∩ SQL中没有对应的操作符
自然连接 natural join ⋈ 类似于 SQL 中的 inner join
赋值 assignment ←

代数与物理优化基础

查询分析

  • 对查询语句进行扫描, 词法分析(识别出保留字, 变量, 运算符, 发现拼写错误)和语法分析(判断是否符合SQL的语法规则, 出现错误就报告SQL语法错误)

查询检查

  • 有效性检查: 对符合语法规则的查询语句进行语义检查, 也就是根据数据字典中有关的模式定义去检查语句中的数据库对象, 比如表名, 属性名是否都在存在和有效.
  • 视图转换: 把对视图的操作求解, 转换成对基本表的操作
  • 安全性: 还要检查用户权限
  • 完整性检查: 根据数据字典中存储的完整性约束进行检查(主键约束, 外键约束, 用户自定义约束非空, 取值范围等).

查询优化

  • 是数据库技术的关键. 划分为代数优化(逻辑优化), 物理优化(存取路径, 底层算法).
  • 优化的依据: 基于规则, 基于代价, 基于语义
  • 优化器得出一个执行策略, 并生成相应的查询计划.
project操作算法
  • naive table scan: 全表扫描, 按照物理次序读取Student表的M个block到内存, 检查是否满足条件, 满足则输出.
  • index scan: 如果选择条件中的属性上有索引(比如学号, 姓名, age可能有B+), 那么可以用索引扫描方法, 通过索引先找到满足条件的元组的指针, 然后通过指针在基本表中找到元组.
join操作算法
  • naive nested loop join: O(N^2), 嵌套循环
  • sort-merge join排序合并算法: 假设sno做连接, 那么两个表都按照sno排序, 排好序了以后按照Student, 对SC进行扫描, 注意由于排好序了, 因此两张表都只要扫描一遍即可, 总的时间复杂度是O(NlgN + 2N) = O(NlgN)
  • index join: 假设SC表上已经建立了属性sno的索引, 那么对于Student中的每一个元组, 在SC中找到对应的元组的时间就不是全表扫描O(N), 而是O(lgN).
  • hash join: 对记录行数较少的那张表, 假设是Student表, 建立一个hashtable, 然后对大表SC, 用同样的hash函数, 对每个元组上的sno进行hash, 如果在hashtable中有对应的Student元组, 就连接. 整个时间开销是O(N), 当然了, 相比其他算法, 额外的空间开销是O(N).
代价模型

DBMS会根据其特有的代价模型来计算各种查询执行策略的代价, 然后选取代价最小的方案.

  • 对集中式数据库: 主要开销是IO
  • 对分布式数据库: 主要开销是IO + 网络通信代价

查询执行

  • 根据code generator负责生成执行能够“查询计划”的实际代码，然后加以执行返回查询结果。

https://www.jb51.net/article/33535.htm

calcite概念

img

类型 描述 特点
RelOptRule transforms an expression into another。对 expression 做等价转换 根据传递给它的 RelOptRuleOperand 来对目标 RelNode 树进行规则匹配，匹配成功后，会再次调用 matches() 方法（默认返回真）进行进一步检查。如果 mathes() 结果为真，则调用 onMatch() 进行转换。
ConverterRule Abstract base class for a rule which converts from one calling convention to another without changing semantics. 它是 RelOptRule 的子类，专门用来做数据源之间的转换（Calling convention），ConverterRule 一般会调用对应的 Converter 来完成工作，比如说：JdbcToSparkConverterRule 调用 JdbcToSparkConverter 来完成对 JDBC Table 到 Spark RDD 的转换。
RelNode relational expression，RelNode 会标识其 input RelNode 信息，这样就构成了一棵 RelNode 树 代表了对数据的一个处理操作，常见的操作有 Sort、Join、Project、Filter、Scan 等。它蕴含的是对整个 Relation 的操作，而不是对具体数据的处理逻辑。
Converter A relational expression implements the interface Converter to indicate that it converts a physical attribute, or RelTrait of a relational expression from one value to another. 用来把一种 RelTrait 转换为另一种 RelTrait 的 RelNode。如 JdbcToSparkConverter 可以把 JDBC 里的 table 转换为 Spark RDD。如果需要在一个 RelNode 中处理来源于异构系统的逻辑表，Calcite 要求先用 Converter 把异构系统的逻辑表转换为同一种 Convention。
RexNode Row-level expression 行表达式（标量表达式），蕴含的是对一行数据的处理逻辑。每个行表达式都有数据的类型。这是因为在 Valdiation 的过程中，编译器会推导出表达式的结果类型。常见的行表达式包括字面量 RexLiteral， 变量 RexVariable， 函数或操作符调用 RexCall 等。 RexNode 通过 RexBuilder 进行构建。
RelTrait RelTrait represents the manifestation of a relational expression trait within a trait definition. 用来定义逻辑表的物理相关属性（physical property），三种主要的 trait 类型是：Convention、RelCollation、RelDistribution；
Convention Calling convention used to repressent a single data source, inputs must be in the same convention 继承自 RelTrait，类型很少，代表一个单一的数据源，一个 relational expression 必须在同一个 convention 中；
RelTraitDef 主要有三种：ConventionTraitDef：用来代表数据源 RelCollationTraitDef：用来定义参与排序的字段；RelDistributionTraitDef：用来定义数据在物理存储上的分布方式（比如：single、hash、range、random 等）；
RelOptCluster An environment for related relational expressions during the optimization of a query. palnner 运行时的环境，保存上下文信息；
RelOptPlanner A RelOptPlanner is a query optimizer: it transforms a relational expression into a semantically equivalent relational expression, according to a given set of rules and a cost model. 也就是优化器，Calcite 支持RBO（Rule-Based Optimizer） 和 CBO（Cost-Based Optimizer）。Calcite 的 RBO （HepPlanner）称为启发式优化器（heuristic implementation ），它简单地按 AST 树结构匹配所有已知规则，直到没有规则能够匹配为止；Calcite 的 CBO 称为火山式优化器（VolcanoPlanner）成本优化器也会匹配并应用规则，当整棵树的成本降低趋于稳定后，优化完成，成本优化器依赖于比较准确的成本估算。RelOptCost 和 Statistic 与成本估算相关；
RelOptCost defines an interface for optimizer cost in terms of number of rows processed, CPU cost, and I/O cost. 优化器成本模型会依赖；

calcite架构

  • 在 Calcite 架构中，最核心地方就是 Optimizer，也就是优化器，一个 Optimization Engine 包含三个组成部分：
    • rules：也就是匹配规则，Calcite 内置上百种 Rules 来优化 relational expression，当然也支持自定义 rules；
    • metadata providers：主要是向优化器提供信息，这些信息会有助于指导优化器向着目标（减少整体 cost）进行优化，信息可以包括行数、table 哪一列是唯一列等，也包括计算 RelNode 树中执行 subexpression cost 的函数；
    • planner engines：它的主要目标是进行触发 rules 来达到指定目标，比如像 cost-based optimizer（CBO）的目标是减少cost（Cost 包括处理的数据行数、CPU cost、IO cost 等）。

calcite处理流程

  • 解析 SQL， 把 SQL 转换成为 AST （抽象语法树），在 Calcite 中用 SqlNode 来表示；
  • 语法检查，根据数据库的元数据信息进行语法验证，验证之后还是用 SqlNode 表示 AST 语法树；
  • 语义分析，根据 SqlNode 及元信息构建 RelNode 树，也就是最初版本的逻辑计划（Logical Plan）；
  • 逻辑计划优化，优化器的核心，根据前面生成的逻辑计划按照相应的规则（Rule）进行优化；
  • 物理执行，生成物理计划，物理执行计划执行。