知微在路上
近期研究了《数据库系统实现》这本书,了解了一条SQL是如何进行编译的,以下为自己从书中的总结。
首先先介绍概念,对于查询处理,一般分为三个步骤:
对SQL语句进行语法分析,即将查询语句转换成按照某种有用方式表示查询语句结构的语法树
把语法分析树转换成关系代数表达式树(或某种类似标记),一般称之为逻辑查询计划
逻辑查询计划必须转换成物理查询计划,物理查询计划不仅指明了要执行的操作,而且也找出了这些操作执行的顺序、执行每步所用的算法,获得所存储数据的方式以及数据从一个操作传递给另一个操作的方式,除此之外,还必须估计每个可能选项的预计代价。
以下是详细的步骤。
查询的编译
1:语法分析与预处理
语法分析与语法分析树
原子
语法类
SQL简单子集的语法(语法分析)
查询
<query> ::= SELECT <SelList> FROM <FromList> WHERE <Condition>
选择列表
from列表
条件
举例说明:
query: select title from startsin WHERE name = "tao"
语法树
语法树
预处理器
主要用来检查关系的使用,检查与解析属性的使用以及检查类型
2:用于改进查询计划的代数定律
交换律与结合律
涉及选择的定律
下推选择(必须下推到包含涉及属性的关系中,下推选择较为复杂)
涉及投影的定律
有关连接和积的定律
有关消除重复的定律
涉及分组与聚集的定律
说明:
代数定律类似于数学里的各种定律,如(x+y)+z=x+(y+z)等。
了解下推选择,必须了解前置知识,即数据库的关系代数:投影、选择、并、差、积、交、自然连接等,在此不赘述了,有兴趣的可以了解一下。
3:从语法分析树到逻辑查询计划
概念:将语法树转换成所希望的逻辑查询计划
终目标:将查询语句转化为关系代数
《数据库系统实现》这本书上,有详细的例子说明,辅以图说明,可以详细研究一下。
4:查询的优化
后可以了解一下查询是以什么指标来衡量查询的优化的。
中间关系大小的估计
投影运算大小的估计
选择运算大小的估计
连接运算大小的估计
多连接属性的自然连接
多个关系的连接
其他运算大小的估计(并、交、差、消除重复、分组与聚集)
本次总结较为干货,如果没有数据库方面的知识储备可能很难看懂。建议做数据开发或者数据分析的同学有兴趣可以研究一下《数据库系统实现》这本书,从深层次帮我们理解一条SQL语句是如何从编译到执行的。我们平时使用例如hive等,进行SQL操作时,内部执行计划就是以上这样的。如果我们要进行SQL的血缘分析,那么代码就是按照以上步骤实现的,有兴趣可以研究类似HiveParser之类的SQL解析方式。