1、An Introduction to Database System信息科学与技术学院计算机系数据库系统概论数据库系统概论An Introduction to Database System第九章第九章 关系查询处理和查询优化关系查询处理和查询优化An Introduction to Database System第九章 关系系统及其查询优化9.1 关系数据库系统的查询处理9.2 关系数据库系统的查询优化9.3 代数优化9.4 物理优化9.3 小结An Introduction to Database System9.1关系数据库系统的查询处理9.1.1 查询处理步骤9.1.2 实现查询操作的
2、算法示例An Introduction to Database System9.1.1 查询处理步骤p查询分析n词法/语法/语义分析n符号名转换p查询检查n语义检查n安全性检查n完整性检查p查询优化n代数优化n物理优化p查询执行n查询计划生成n代码生成 An Introduction to Database System9.1关系数据库系统的查询处理9.1.1 查询处理步骤9.1.2 实现查询操作的算法示例An Introduction to Database System9.1.2 实现查询操作的算法示例p一一 选择操作的实现选择操作的实现p二二 连接操作的实现连接操作的实现An Intro
3、duction to Database System9.1.2 实现查询操作的算法示例一一 选择操作的实现选择操作的实现n1、简单的全表扫描方法、简单的全表扫描方法n2、索引、索引(或散列或散列)扫描方法扫描方法例例1 Select*from student where p表达式情况表达式情况:nC1:无条件无条件;nC2:Sno=200215121;nC3:Sage 20;nC4:Sdept=CS AND Sage 20;An Introduction to Database System9.1.2 实现查询操作的算法示例p1、简单的全表扫描方法、简单的全表扫描方法An Introducti
4、on to Database System9.1.2 实现查询操作的算法示例p2、索引、索引(或散列或散列)扫描方法扫描方法p例例1-C2 nSno上有索引上有索引p例例1-C3 nSage上有上有B+树索引树索引p例例1-C4 nSdept和和Sage上都有索引上都有索引An Introduction to Database System9.1.2 实现查询操作的算法示例二二 连接操作的实现连接操作的实现n1、嵌套循环方法、嵌套循环方法(nested loop)n2、排序、排序-合并方法合并方法(sort-merge join)n3、索引连接、索引连接(Index Join)方法方法n4、H
5、ash Join方法方法例例2 Select*from student,scwhere student.sno=sc.sno;An Introduction to Database System9.1.2 实现查询操作的算法示例p1、嵌套循环方法、嵌套循环方法An Introduction to Database System9.1.2 实现查询操作的算法示例p2、排序合并方法、排序合并方法2002151212002151222002151232002151242002151212200215121320021512112002151222200215122320021512352002151
6、2332002151231SNOSNOCNOAn Introduction to Database System9.1.2 实现查询操作的算法示例p3、索引连接方法、索引连接方法20021512320021512220021512120021512420021512122002151233200215123120021512122002151223200215121520021512232002151231SNOSNOCNO索引表An Introduction to Database System9.1.2 实现查询操作的算法示例p3、Hash Join方法方法2002151232002151
7、2220021512120021512412002151233200215122520021512132002151222200215121120021512332002151232200215121SNOSNOCNOAn Introduction to Database System第四章 关系系统及其查询优化9.1 关系数据库系统的查询处理9.2 关系数据库系统的查询优化9.3 代数优化9.4 物理优化9.3 小结An Introduction to Database System9.2关系数据库系统的查询优化p查询优化的必要性n查询优化极大地影响RDBMS的性能。p查询优化的可能性n关系
8、数据语言的级别很高，使DBMS可以从关系表达式中分析查询语义。An Introduction to Database System9.2.1 查询优化概述p关系系统的查询优化既是RDBMS的关键技术又是关系系统的优点所在;p大大减轻了用户的负担。An Introduction to Database System9.2.1 查询优化概述p由DBMS进行查询优化的好处n用户不必考虑如何最好地表达查询以获得较好的效率n系统可以比用户程序的优化做得更好(1)优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息 An Introduction to Database System由DB
9、MS进行查询优化的好处p(2)如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。p(3)优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。p(4)优化器中包括了很多复杂的优化技术An Introduction to Database System9.2.1 查询优化概述p集中式数据库查询开销：nI/O+CPU+内存p分布式数据库查询开销：nI/O+CPU+内存+通信代价p查询优化的总目标n选择有效策略，求得给定关系表达式的值，使得查询代价较小An Introduction
10、 to Database System9.2.2 一个实例例3：求选修了课程2的学生姓名 SELECT Student.SnameFROM Student,SCWHERE Student.Sno=SC.SnoAND SC.Cno=2;An Introduction to Database System9.2.2 一个实例（续）假设1：外存：Student:1000条,SC:10000条,选修2号课程:50条假设2：一个内存块装元组:10个Student,或100个SC,内存中一次可以存放:5块Student元组,1块SC元组和若干块连接结果元组假设3：读写速度：20块/秒假设4：连接方法：基于
11、数据块的嵌套循环法 An Introduction to Database System9.2.2 一个实例（续）p三种策略：p1 name(Student.Sno=SC.Sno SC.Cno=2(StudentSC)p2 name(SC.Cno=2(Student SC)p2 Sname(Student SC.Cno=2(SC)An Introduction to Database System执行策略11 name(Student.Sno=SC.Sno SC.Cno=2(StudentSC)StudentSC 读取总块数=读Student表块数+读SC表遍数 *每遍块数=1000/10+(
12、1000/(105)(10000/100)=100+20100=2100 读数据时间=2100/20=105秒An Introduction to Database System不同的执行策略,考虑I/O时间中间结果大小=1000*10000=107 (1千万条元组)写中间结果时间=10000000/10/20=50000秒 读数据时间=50000秒 总时间=1055000050000秒=100105秒 =27.8小时An Introduction to Database System9.2.2 一个实例（续）策略2.2 name(SC.Cno=2(Student SC)读取总块数=2100块
13、读数据时间=2100/20=105秒中间结果大小=10000 （减少1000倍）写中间结果时间=10000/10/20=50秒 读数据时间=50秒 总时间1055050秒205秒=3.4分 An Introduction to Database System9.2.2 一个实例（续）策略3.3 Sname(Student SC.Cno=2(SC)读SC表总块数=10000/100=100块读数据时间=100/20=5秒 中间结果大小=50条 不必写入外存 读Student表总块数=1000/10=100块读数据时间=100/20=5秒 总时间55秒10秒 An Introduction to
14、Database System9.2.2 一个实例（续）策略4.2 name(Student SC.Cno=2(SC)假设SC表在Cno上有索引，Student表在Sno上有索引 读SC表索引=读SC表总块数=50/1001块读数据时间 中间结果大小=50条 不必写入外存An Introduction to Database System9.2.2 一个实例（续）读Student表索引=读Student表总块数=50/10=5块读数据时间 总时间 连接运算 例：S t u d e n t.S n o=S C.S n o (StudentSC)Student SCp提取公共子表达式An Intr
15、oduction to Database System9.3.2 查询树的启发式优化算法算法：关系表达式的优化输入：一个关系表达式的语法树。输出：计算该表达式的程序。方法：（1）分解选择运算 利用规则4把形如F1 F2 Fn(E)变换为 F1(F2(Fn(E)An Introduction to Database System关系代数表达式的优化算法(续)（2）通过交换选择运算，将其尽可能移到叶端 对每一个选择，利用规则49尽可能把它移到树的叶端。（3）通过交换投影运算，将其尽可能移到叶端对每一个投影利用规则3，10，11，5中的一般形式尽可能把它移向树的叶端。An Introduction
16、to Database System关系代数表达式的优化算法(续)（4）合并串接的选择和投影，以便能同时执行或在一次扫描中完成n利用规则35把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。n使多个选择或投影能同时执行，或在一次扫描中全部完成n尽管这种变换似乎违背“投影尽可能早做”的原则，但这样做效率更高。An Introduction to Database System关系代数表达式的优化算法(续)（5）对内结点分组n把上述得到的语法树的内节点分组。n每一双目运算(，-)和它所有的直接祖先为一组(这些直接祖先是，运算)。n如果其后代直到叶子全是单目运算，则也将它们并入该组，
17、但当双目运算是笛卡尔积()，而且其后的选择不能与它结合为等值连接时除外。把这些单目运算单独分为一组。An Introduction to Database System关系代数表达式的优化算法(续)（6）生成程序n生成一个程序，每组结点的计算是程序中的一步。n各步的顺序是任意的，只要保证任何一组的计算不会在它的后代组之前计算。An Introduction to Database System优化的一般步骤 1把查询转换成某种内部表示2代数优化：把语法树转换成标准（优化）形式3物理优化：选择低层的存取路径4生成查询计划，选择代价最小的 An Introduction to Database S
18、ystem优化的一般步骤(续)（1）把查询转换成某种内部表示例：求选修了课程2的学生姓名SELECT Student.SnameFROM Student,SCWHERE Student.Sno=SC.SnoAND SC.Cno=2;An Introduction to Database System（1）把查询转换成某种内部表示语法树 结果结果project(Sname)select(SC.Cno=2)join(Student.Sno=SC.Sno)StudentSCAn Introduction to Database System关系代数语法树Sname SC.Cno=2 Student.
19、Sno=SC.S StudentSCAn Introduction to Database System（2）代数优化利用优化算法把语法树转换成标准（优化）形式 Sname Student.Sno=SC.Sno SC.Cno=2 StudentSCAn Introduction to Database System第九章 关系系统及其查询优化9.1 关系数据库系统的查询处理9.2 关系数据库系统的查询优化9.3 代数优化9.4 物理优化9.3 小结An Introduction to Database System9.4 物理优化1、基于规则的启发式优化2、基于代价估算的优化3、两者结合的优化
20、方法An Introduction to Database System9.4 物理优化9.4.1 基于启发式规则的存取路径选择优化9.4.2 基于代价的优化An Introduction to Database System9.4.1基于启发式规则的存取路径选择优化一、选择操作的启发式规则二、连接操作的启发式规则P273An Introduction to Database System9.4 物理优化9.4.1 基于启发式规则的存取路径选择优化9.4.2 基于代价的优化An Introduction to Database System9.4.2 基于代价的优化p统计信息n表的元组数、元组
21、长度、占用的块数等等n属性列不同值的个数、选择率，最大最小值n索引的层数、不同索引值的个数、索引叶结点数等p代价估算示例n全表扫描算法的代价估算公式n索引扫描算法的代价估算公式n嵌套循环连接算法的代价估算公式n排序-合并连接算法的代价估算公式An Introduction to Database System第九章 关系系统及其查询优化9.1 关系数据库系统的查询处理9.2 关系数据库系统的查询优化9.3 代数优化9.4 物理优化9.3 小结An Introduction to Database System9.3 小结p查询处理是核心、优化是关键p查询优化的必要性p代数优化及其启发式规则（查询树）p物理优化（存取路径启发式规则、代价优化）An Introduction to Database System 下课了。休息一会儿。休息一会儿。
