文档介绍：******@ustc.
第2部分关系数据库系统实现
第7章查询处理与优化
高级数据库系统及其应用
第7章查询处理与优化
查询处理简介
查询优化综述
基于代价的枚举与优化
处理嵌入子查询
Oracle优化器简介
查询处理小结
关系代数等价规则
基于等价和启发式规则的查询优化
作为中间结果的操作符输出大小估计
查询处理简介
查询预编译简介
从语法树生成初步的逻辑查询计划
将查询基本块转化为关系代数表达式
查询处理简介
即使是一个简单的单操作符赋值,也有许多不同赋值方式。每种方法都可能在某些场合下优于其它方法。
一个实际查询通常不止涉及一个操作符。包含几个操作符的查询有更多的赋值方式选项,发现或找到一个好查询计划是一项重要的挑战。
DBMS必须考虑可替换的各种可选方式,并选择其中具有最少估算代价的一个。
查询处理简介
查询预编译简介
负责对提交查询语句进行语法分析和语义检查。
通过“语法分析器”,可将合法的SQL语句转换成语法分析树表示,其节点可以是以下两者之一:
原子类:属词法成份,相当于语言编译器产生的token。原子节点没有子节点。
语法类:在查询表达中起相似作用的查询子成份族名称。通常用角括号将描述名括起来表示语法类。
例如,用<SFW>表示SELECT-FROM-WHERE形式的查询语句,用<Condition>表示关键字WHERE之后的条件表达式。
语法类节点有子节点--通过语言的语法规则(产生式)之一进行描述。
SQL语法的一个简单子集
语义分析检查
检查关系名的合法性。
出现在语法树关系列表中的关系名,必须是语境DB中已定义的关系或视图名。
检查并解析属性的使用。
在SELECT或FROM子句中出现的每个属性名,必须是关系列表中某个关系的属性,如不然,预编译器必须报错。
检查类型的合法性。
当属性名不是单独出现,而是出现在某个表达式中时,属性类型必须能匹配表达式。
语法分析树举例
查询
SELECT
FROM Reserves, Sailors
WHERE = AND
=100
从语法树生成初步的逻辑查询计划(1)
解析语法树到一组查询处理基本块.
基本块是一个简单的<SFW>成份:
有且只有1个SELECT和FROM关键字;
最多一个WHERE子句;且条件表达式具有合取规范形式;
最多一个GROUP BY/HAVING 子句。
典型关系查询优化器的主要优化工作,一般都集中在针对基本块的优化处理方面。
查找具有最大职级且至少在红船上服务两次水手,给出该水手id号以及他最早在红船上服务的时间。
这个查询可表达为1基本块和1嵌入块的组合:
基本块
SELECT , MIN()
FROM Sailors S, Reserves R, Boats B
WHERE = AND = AND
=’red’ AND = <嵌入块结果集>
GROUP BY
HAVING COUNT(*)>2
嵌入块
SELECT MAX() FROM Sailors S2