SQL查询引擎概述-关系模型与查询优化

一、SQL语句分类

关系模型->关系代数(过程式)->SQL(声明式)

SQL语句分类 SQL语句分类

SQL->AST->Logical Plan Tree->Physical Plan Tree

二、查询流程概述

查询流程 查询流程

三、基于规则的查询优化

基于关系代数等价性进行逻辑变换，减少无用开销

  • 关系代数等价：关系代数表达式生成相同的结果集
  • 依据关系代数的等价交换原则做一些逻辑变换
  • 谓词下推：1) 尽可能早地进行过滤；2) 分解复杂的谓词条件，下推；3) 分解连接条件，笛卡尔积转Join计算
  • 投影下推：提前做投影，去除不需要的列信息
  • 排序、Limit、聚合下推
  • 投影消除：如果子集投影和投影操作相同，则消除投影操作
  • 排序消除：如果子集结果排序和排序操作相同，则消除排序操作

四、基于代价的查询优化

基于统计信息进行代价搜索，选择最优的物理执行计划

SQL查询引擎概述-执行引擎

一、查询流程和表达式

1. 查询流程

查询的过程：SQL语句->查询计划->查询结果

2. 查询计划

查询计划描述了执行的动作，通过以下方式进行描述

  1. 运算符（Operator）：Projection\TopK\Sort\Filter(Select)\HashJoin\Aggregation\TableScan…
  2. 表达式（Expression）：R.id, S.id, S.age \ age >= 20 \ COUNT(S.id) + 1, AVG(S.age) <= 50 \ R.id = S.id \ …
  3. 运算符中包含表达式 查询计划示例图

3.表达式（Expression）

3.1 表达式类型：常量，元组属性引用，标量函数，聚合函数

  • 常量（Constant）：表达式中的常量值
  • 元组属性引用（Tuple Atribute Ref）：引用表中某个属性的值
  • 标量函数（Scalar Function）：比较（,!=,>=,<=,in..）；逻辑 （AND,OR, XOR, NOT..）；算术 (AND, SUB, MUL, DIV, MOD ..)；内置函数（Buildin Function）；自定义函数（UDF）
  • 聚合函数（Agg Function）：COUNT，MAX, MIN, SUM, AVG

3.2 表达式求值

整体是自底向上求值，分为 元组属性求值、标量函数求值、聚合函数求值 三种：

  • 元组属性求值：输入一个元组，输出元组中对应属性的值； 标量函数求值：Row Style 输入一个元组，输出一个标量；Block Style 输入一个 Block，输出一个 vector； 聚合函数求值：Initialize 初始化聚合状态；Update 根据当前的 Tuple 更新聚合状态；Finalize 计算聚合最终状态

二、常见运算符

  1. 排序(Sorting) 排序是查询执行中的基本算法，在多个场景中使用，Order by, group by, sortmerge join 排序类型：1) 内存排序(In-memory sorting) 快排、堆排、归并排序等；2) 外部归并排序( External Merge sorting) IO代价评估、两路外部归并、K路外部归并。

作者：ChaunhewieTian 链接：https://www.jianshu.com/p/fed99000e664 来源：简书 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。