《数据库原理与程序设计（孙杰）查询优化技术课件》由会员分享，可在线阅读，更多相关《数据库原理与程序设计（孙杰）查询优化技术课件（41页珍藏版）》请在金锄头文库上搜索。
1、数据库原理与程序设计（孙杰）第11章 查询优化技术,第11章 查询优化技术,生物医学软件工程教研室,数据库原理与程序设计（孙杰）第11章 查询优化技术,查询优化的必要性,例：查询选修了课程C031的学生的姓名,数据库原理与程序设计（孙杰）第11章 查询优化技术,为了对查询的效率进行比较，我们进行如下的假设： 外存：Student：1000条；SC：10000条；选修2号课程：50条； 一个内存块装元组：10个Student或100个SC，内存中一次可以存放：5块Student元组，1块SC元组和若干块连接结果元组； 读写速度：20块/秒,数据库原理与程序设计（孙杰）第11章 查询优化技术,st
2、udentsc 读取时间=读取总块数读取速度 读取总块数= 读Student表块数+读SC表遍数*每遍块数=1000/10+(1000/(105) (10000/100) =100+20100=2100 写中间结果的时间=中间结果的大小磁盘块容量读写速度 中间结果大小 = 1000*10000 = 107(1千万条元组,读数据时间=2100/20=105秒,写中间结果时间 = 10000000/10/20 = 50000秒,数据库原理与程序设计（孙杰）第11章 查询优化技术,运算需读取中间结果 读数据时间 = 50000秒 总时间 =1055000050000秒 = 100105秒 = 27.
3、8小时,数据库原理与程序设计（孙杰）第11章 查询优化技术,读取总块数= 2100块 读数据时间=2100/20=105秒 中间结果大小=10000 （减少1000倍） 写中间结果时间=10000/10/20=50秒 读数据时间=50秒 总时间1055050秒205秒=3.4分,数据库原理与程序设计（孙杰）第11章 查询优化技术,读SC表总块数= 10000/100=100块 读数据时间=100/20=5秒 中间结果大小=50条 不必写入外存 读Student表总块数= 1000/10=100块 读数据时间=100/20=5秒 总时间55秒10秒,数据库原理与程序设计（孙杰）第11章 查询优化
4、技术,读SC表索引= 读SC表总块数= 50/1001块 读数据时间 中间结果大小=50条 不必写入外存 读Student表索引= 读Student表总块数= 50/10=5块 读数据时间 总时间10秒,假设 SC 表在 Cno上有索引 Student 表在 Sno上有索引,数据库原理与程序设计（孙杰）第11章 查询优化技术,查询优化的一般规则,规则1：选择和投影操作尽早执行 减少中间结果,数据库原理与程序设计（孙杰）第11章 查询优化技术,查询优化的一般规则,规则2：把某些选择操作与邻接笛卡尔积相结合，形成一个连接操作 连接操作比笛卡尔积节省时间，特别是等值连接。 student.son=s
5、c.sno(studentsc) studentsc,数据库原理与程序设计（孙杰）第11章 查询优化技术,查询优化的一般规则,规则3：同时执行相同关系上的多个选择和投影操作 避免重复扫描关系,数据库原理与程序设计（孙杰）第11章 查询优化技术,查询优化的一般规则,规则4：把投影操作与邻接操作结合起来执行 减少扫描关系的遍数,数据库原理与程序设计（孙杰）第11章 查询优化技术,查询优化的一般规则,规则5：在执行连接操作前对关系适当进行预处理 按连接属性排序 在连接属性上建立索引,数据库原理与程序设计（孙杰）第11章 查询优化技术,查询优化的一般规则,规则6：提取公共表达式,数据库原理与程序设计（
6、孙杰）第11章 查询优化技术,关系代数等价变换规律,等价的概念：设E1和E2是两个关系代谢表达式。如果E1和E2中表示相同的关系，则称E1和E2等价,数据库原理与程序设计（孙杰）第11章 查询优化技术,等价规律1：选择串接律 其中E是关系代数表达式，ci是选择条件. 选择条件可以合并，一次可以检查多个条件,数据库原理与程序设计（孙杰）第11章 查询优化技术,等价规律2：选择交换律 其中E是关系代数表达式，ci是选择条件,数据库原理与程序设计（孙杰）第11章 查询优化技术,等价规律3：投影串接律 其中，E是关系代数表达式，Li是投影属性集合，且L1L2 Ln,数据库原理与程序设计（孙杰）第11章
7、 查询优化技术,等价规律4：选择投影交换律 其中，E是关系代数表达式，L是投影属性集合，C是选择条件，C值设计L中属性,数据库原理与程序设计（孙杰）第11章 查询优化技术,等价规律5：连接和笛卡尔积交换律 其中，E1 和E2 是关系代数表达式，C是连接条件,数据库原理与程序设计（孙杰）第11章 查询优化技术,等价规律6：集合操作的交换律 其中，E1和E2是关系代数表达式,数据库原理与程序设计（孙杰）第11章 查询优化技术,等价规律7：连接、笛卡尔积和集合操作的结合律,数据库原理与程序设计（孙杰）第11章 查询优化技术,等价规律8：选择、连接和笛卡尔积的分配律 部分的选择可以在笛卡尔积(或连接)
8、前先做,数据库原理与程序设计（孙杰）第11章 查询优化技术,等价规律9：投影、连接和笛卡尔积的分配律,数据库原理与程序设计（孙杰）第11章 查询优化技术,等价规律10：选择与集合操作的分配律,数据库原理与程序设计（孙杰）第11章 查询优化技术,等价规律11：投影与集合操作的分配律,数据库原理与程序设计（孙杰）第11章 查询优化技术,关系代数优化算法查询树,查询树是一种表示关系代数表达式的树形结构。 叶子节点表示关系 内节点表示关系代数操作 自底向上执行,数据库原理与程序设计（孙杰）第11章 查询优化技术,处理一个查询需要构造该查询的内部表示查询树 高级查询语言定义的查询语句 关系代数表达式(查
9、询树) 优化算法最终的结果查询树,数据库原理与程序设计（孙杰）第11章 查询优化技术,例,Select A from R1, R2, R3 where P=15 and N=user; 关系代数表达式 A(p=15and N=user (R1R2R3,R1,R2,R3,p=15 and N=user,A,数据库原理与程序设计（孙杰）第11章 查询优化技术,查询优化算法的描述,算法输入：关系代数表达式 算法输出：计算输入关系代数表达式的程序 (1)使用规律1，把每个选择操作 变换为,使得选择操作可以灵活方便地言查询树下移,数据库原理与程序设计（孙杰）第11章 查询优化技术,2)使用规律2,4,8
10、和10，把查询树上的每个选择操作移动到尽可能靠近叶子节点 (3)使用规律3,4,9和11，把查询树上的每个投影操作移动到尽可能靠近叶子节点,数据库原理与程序设计（孙杰）第11章 查询优化技术,4)使用规律1,3和4，把串接的多个选择或多个投影操作组合为但个选择或投影操作 (5)使用规律7重新安排叶节点，使具有最小选择操作的叶子节点最先执行,数据库原理与程序设计（孙杰）第11章 查询优化技术,6)组合笛卡尔积和相继的选择操作形成连接操作 (7)把最后的查询树划分为多个子树，使每个子树上的操作可以由单个存取程序一次完成,数据库原理与程序设计（孙杰）第11章 查询优化技术,8)产生一个计算最后查询树
11、的程序，每一步计算一个子树,数据库原理与程序设计（孙杰）第11章 查询优化技术,例,考虑一个具有如下关系的图书馆数据库 书目：Boo(Ti, Au, Pn, Nc) 借阅者：Bor(Na, Ad, Ci, Cn) 出版社：Pub(Pn, Pa, Pc) 借阅登记：Loa(Cn, Nc, Da) 设有一个由已借出图书信息构成的视图LBI, create view LBI as select Ti, Au, Boo.Pn, Boo.Nc, Na, Ad, Ci, Bor.Cn, Da from Boo, Bor, Loa where Boo.Nc=Loa.Nc and Bor.Cn=Loa.Cn,数据库原理与程序设计（孙杰）第11章 查询优化技术,了解1994年2月1日前借出的所有书籍的名字。 select Ti from LBI where Da2/1/1994,数据库原理与程序设计（孙杰）第11章 查询优化技术,Loa,Bor,Boo,数据库原理与程序设计（孙杰）第11章 查询优化技术,Loa,Bor,Boo,数据库原理与程序设计（孙杰）第11章 查询优化技术,Loa,Bor,Boo,数据库原理与程序设计（孙杰）第11章 查询优化技术,Loa,Bor,Boo,数据库原理与程序设计（孙杰）第11章 查询优化技术,Bor,Boo,Loa
