数据库原理与程序设计孙杰第11章查询优化技术.ppt
第第11章章 查询优化技术查询优化技术生物医学软件工程教研室生物医学软件工程教研室查询优化的必要性查询优化的必要性v例：查询选修了课程例：查询选修了课程C031的学生的姓名的学生的姓名sc)(student(osc.snoostudent.snsname)scstudent(031cno.sc csname)(031.scstudentccnoscsnamev为了对查询的效率进行比较，我们进行如为了对查询的效率进行比较，我们进行如下的假设：下的假设：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千万千万条元组条元组)sc)(student(osc.snoostudent.snsname读数据时间读数据时间=2100/20=105秒秒写中间结果时间写中间结果时间=10000000/10/20=50000秒秒v 运算需读取中间结果运算需读取中间结果 读数据时间读数据时间=50000秒秒 vv总时间总时间=1055000050000秒秒 v =100105秒秒v =27.8小时小时v 读取总块数读取总块数=2100块块 读数据时间读数据时间=2100/20=105秒秒 中间结果大小中间结果大小=10000 （减少（减少1000倍）倍）写中间结果时间写中间结果时间=10000/10/20=50秒秒 v 读数据时间读数据时间=50秒秒vv总时间总时间1055050秒秒205秒秒=3.4分分)scstudent(031cno.sc csnamev 读读SC表总块数表总块数=10000/100=100块块 读数据时间读数据时间=100/20=5秒秒 中间结果大小中间结果大小=50条条 不必写入外存不必写入外存 读读Student表总块数表总块数=1000/10=100块块 读数据时间读数据时间=100/20=5秒秒v总时间总时间55秒秒10秒秒)(031.scstudentccnoscsnamev 读读SC表索引表索引=读读SC表总块数表总块数=50/1001块块 读数据时间读数据时间 中间结果大小中间结果大小=50条条 不必写入外存不必写入外存v 读读Student表索引表索引=读读Student表总块数表总块数=50/10=5块块 读数据时间读数据时间v总时间总时间10秒秒假设假设 SC 表在表在 Cno上有索引上有索引Student 表在表在 Sno上有索引上有索引)(031.scstudentccnoscsname查询优化的一般规则查询优化的一般规则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选择条件可以合并，一次可以检查多个条件选择条件可以合并，一次可以检查多个条件)()(211EEnnccccANDANDcv等价规律等价规律2：选择交换律：选择交换律v其中其中E是关系代数表达式，是关系代数表达式，ci是选择条件是选择条件.)()(1221EEccccv等价规律等价规律3：投影串接律：投影串接律v其中，其中，E是关系代数表达式，是关系代数表达式，Li是投影属性集是投影属性集合，且合，且L1 L2 Ln)()(121EELLLLnv等价规律等价规律4：选择投影交换律：选择投影交换律v其中，其中，E是关系代数表达式，是关系代数表达式，L是投影属性集是投影属性集合，合，C是选择条件，是选择条件，C值设计值设计L中属性中属性)()(EELCCLv等价规律等价规律5：连接和笛卡尔积交换律：连接和笛卡尔积交换律v其中，其中，E1 和和E2 是关系代数表达式，是关系代数表达式，C是连是连接条件。接条件。12211221EEEEEEEECCv等价规律等价规律6：集合操作的交换律：集合操作的交换律v其中，其中，E1和和E2是关系代数表达式是关系代数表达式12211221EEEEEEEEv等价规律等价规律7：连接、笛卡尔积和集合操作的：连接、笛卡尔积和集合操作的结合律结合律)()()()()()()()(3213213213213213213213212121EEEEEEEEEEEEEEEEEEEEEEEECCCCv等价规律等价规律8：选择、连接和笛卡尔积的分配：选择、连接和笛卡尔积的分配律律v部分的选择可以在笛卡尔积部分的选择可以在笛卡尔积(或连接或连接)前先做；前先做；)()()()()()()()()()(2121212121212121121111112211212121EEEEEEEEEEEEEEEECCCCCCCCCCCCCCv等价规律等价规律9：投影、连接和笛卡尔积的分配：投影、连接和笛卡尔积的分配律律)()()()()()()()()()()()(212121212121212121212121EEEEEEEEEEEEEEEELLLLLLLLCLLCLLCLCLv等价规律等价规律10：选择与集合操作的分配律：选择与集合操作的分配律)()()()()()()()()(212121212121EEEEEEEEEEEECCCCCCCCCv等价规律等价规律11：投影与集合操作的分配律：投影与集合操作的分配律)()()()()()()()()(212121212121EEEEEEEEEEEELLLLLLLLL关系代数优化算法关系代数优化算法查询树查询树v查询树查询树是一种表示关系代数表达式的树形是一种表示关系代数表达式的树形结构。结构。叶子节点表示关系叶子节点表示关系 内节点表示关系代数操作内节点表示关系代数操作 自底向上执行自底向上执行v处理一个查询需要构造该查询的内部表示处理一个查询需要构造该查询的内部表示查询树查询树v高级查询语言定义的查询语句高级查询语言定义的查询语句v关系代数表达式关系代数表达式(查询树查询树)v优化算法优化算法最终的结果查询树最终的结果查询树例例vSelect A from R1,R2,R3 vwhere P=15 and N=user;v关系代数表达式关系代数表达式vA(p=15and N=user(R1R2R3)R1R2R3p=15 and N=userA查询优化算法的描述查询优化算法的描述v算法输入算法输入：关系代数表达式：关系代数表达式v算法输出算法输出：计算输入关系代数表达式的程序：计算输入关系代数表达式的程序(1)使用规律使用规律1，把每个选择操作，把每个选择操作 变换为变换为)(1EncANDANDc)(21Enccc使得选使得选择操作择操作可以灵可以灵活方便活方便地言查地言查询树下询树下移移(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.Cn=Loa.Cn;v了解了解1994年年2月月1日前借出的所有书籍的名字。日前借出的所有书籍的名字。vselect Ti from LBI where Da2/1/1994;)(1994/1/2LBIDaTi)(,.,.,.,DaCnBorCiAdNaNcBooPnBooAuTi)(.BooBorLoaCnLoaCnBorANDNcLoaNcBooTiLoaBorBooDaCnBorCiAdNaNcBooPnBooAuTi,.,.,.,CnLoaCnBorANDNcLoaNcBoo.1994/1/2Da1994/1/2DaCnLoaCnBor.NcLoaNcBoo.LoaBorDaCnBorCiAdNaNcBooPnBooAuTi,.,.,.,TiBoo1994/1/2DaCnLoaCnBor.NcLoaNcBoo.LoaBorTiBoo1994/1/2DaCnLoaCnBor.NcLoaNcBoo.LoaBorTiBooNcLoa.TiNcBoo,.CnLoaNcLoa.，CnBor.1994/1/2DaCnLoaCnBor.NcLoaNcBoo.BorBooNcLoa.TiNcBoo,.CnLoaNcLoa.，CnBor.LoaTi
