数据库原理与程序设计（孙杰）第11章 查询优化技术.ppt

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