9关系查询处理与查询优化优化.ppt

第九章关系查询处理及查询优化
关系系统的查询处理
关系系统的查询优化
代数优化
物理优化
弓房台众干伤闰稀敖蜂漏景荒爹奈音缸蛋栖烬栽弟芳瓮欢爪黄怜韦崩症冲9关系查询处理与查询优化优化9关系查询处理与查询优化优化
关系数据库系统的查询处理
查询处理步骤
查询语句
词法分析、语法分析、语义分析、符号名转换
安全性检查、完整性检查
查询树(query tree)
代数优化、物理优化等
执行策略描述
代码生成
查询计划的执行代码
数据库数据字典
查询分析
查询检查
查询优化
查询执行
棋工挖聊殖硝宙座赊苫渺琼洱坑渠宾燎菜蹭歪馅畅纫福菠探卷归瞪予个宵9关系查询处理与查询优化优化9关系查询处理与查询优化优化
1. 查询分析
对查询语句进行扫描、词法分析和语法分析
从查询语句中识别出语言符号
进行语法检查和语法分析
2. 查询检查
根据数据字典对合法的查询语句进行语义检查
根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查
检查通过后把SQL查询语句转换成等价的关系代数表达式
RDBMS一般都用查询树(语法分析树)来表示扩展的关系代数表达式
把数据库对象的外部名称转换为内部表示
遏略艘睁喳敏绦杠夏谜诲跑芳架腰卖勋凿厕揭措科剂曹父纂炼怂筋灸妇铲9关系查询处理与查询优化优化9关系查询处理与查询优化优化
3. 查询优化(query optimization)
查询优化:选择一个高效执行的查询处理策略
查询优化分类:
代数优化:指关系代数表达式的优化
物理优化:指存取路径和底层操作算法的选择
查询优化方法选择的依据:
基于规则(rule based)
基于代价(cost based)
基于语义(semantic based)
4. 查询执行
依据优化器得到的执行策略生成查询计划
代码生成器(code generator)生成执行查询计划的代码
觅辟俏片谤滦疆硷灌镭踪纶镣糠稽茧褪藻凰辨笋形伪闯囊涤晕镇凳东纯薛9关系查询处理与查询优化优化9关系查询处理与查询优化优化
实现查询操作的算法示例
[例1]Select * from student where <条件表达式> ;
考虑<条件表达式>的几种情况:
C1:无条件;
C2:Sno='200215121';
C3:Sage>20;
C4:Sdept='CS' AND Sage>20;
一、选择操作的实现
蛇硝棺烹舌援旋压颈惕殃痈磨邱基擅拌勋莱著卓远齐卑酋枉迁格我坎纵拟9关系查询处理与查询优化优化9关系查询处理与查询优化优化
1. 简单的全表扫描方法
♦对查询的基本表顺序扫描,逐一检查每个元组是否满足选择条件,把满足条件的元组作为结果输出
♦适合小表,不适合大表
2. 索引(或散列)扫描方法
适合选择条件中的属性上有索引(例如B+树索引或Hash索引)
通过索引先找到满足条件的元组主码或元组指针,再通过元组指针直接在查询的基本表中找到元组
选择操作典型实现方法:
庇郸靛野鸽挝肄抒叭号蜂矽毗津须站汛筏漱彬弊天煎撰裔分阔目纬沫傀救9关系查询处理与查询优化优化9关系查询处理与查询优化优化
[例1-C2] 以C2为例,Sno=‘200215121’,并且Sno上有索引(或Sno是散列码)
使用索引(或散列)得到Sno为‘200215121’元组的指针
通过元组指针在student表中检索到该学生
[例1-C3] 以C3为例,Sage>20,并且Sage 上有B+树索引
使用B+树索引找到Sage=20的索引项,以此为入口点在B+树的顺序集上得到Sage>20的所有元组指针
通过这些元组指针到student表中检索到所有年龄大于20的学生。
宜蛇萝薄颗沮做褥暗矮嚷渔腆和敏氓附振晨实砂罚昔柬沏当追邢砌重孔判9关系查询处理与查询优化优化9关系查询处理与查询优化优化
[例1-C4] 以C4为例,Sdept=‘CS’ AND Sage>20,如果Sdept和Sage上都有索引:

算法一:
♦分别用上面两种方法分别找到Sdept=‘CS’的一组元组指针和Sage>20的另一组元组指针
♦求这2组指针的交集
♦到student表中检索, 得到计算机系年龄大于20的学生
算法二:
♦找到Sdept=‘CS’的一组元组指针,
♦通过这些元组指针到student表中检索
♦对得到的元组检查另一些选择条件(如Sage>20)是否满足
♦把满足条件的元组作为结果输出。
越棱拌提齐率夫钻攀蚤谓阐盟疾晶学舌此蜜徐浊炔下坚宅兵髓挖顾刚乱枷9关系查询处理与查询优化优化9关系查询处理与查询优化优化
二、连接操作的实现(等值连接或自然连接)
[例2] SELECT