<4D F736F F F696E74202D20B5DACEE5D5C220B9D8CFB5CFB5CDB3BCB0C6E4D3C5BBAF2D6E6577>

Size: px

Start display at page:

Download "<4D F736F F F696E74202D20B5DACEE5D5C220B9D8CFB5CFB5CDB3BCB0C6E4D3C5BBAF2D6E6577>"

员却弘
4 years ago
Views:

第五章 : 关系系统及其查询优化关系系统的定义和分类查询处理关系系统中的查询优化关系系统的定义关系系统 : 支持关系数据模型的数据库管理系统 ( 粗略 ) 关系系统 ( 确切定义 ): 一个系统可以定义为一个关系系统, 当且仅当它 : 支持关系数据库支持选择投影和连接运算 ( 自然连接 ), 对这些运算不要求定义任何物理存取路径关系系统的分类许多关系系统的产品按 E.F.

1 第五章 : 关系系统及其查询优化关系系统的定义和分类查询处理关系系统中的查询优化关系系统的定义关系系统 : 支持关系数据模型的数据库管理系统 ( 粗略 ) 关系系统 ( 确切定义 ): 一个系统可以定义为一个关系系统, 当且仅当它 : 支持关系数据库支持选择投影和连接运算 ( 自然连接 ), 对这些运算不要求定义任何物理存取路径关系系统的分类许多关系系统的产品按 E.F.Codd 的思想将关系系统分为 : 集合级 M I M M M I I I a b c d 表式系统 (a) 最小关系系统 (b) 关系完备的系统 (c) 全关系系统 (d) 关系数据模型 : tructure I: Integrity M: Manipulation 关系系统的查询处理查询处理的步骤 : 查询查询结果输出分析器 & 翻译器评价引擎数据关系代数表达式优化器执行计划 DBM 基于数据的统计分析为什么需要查询优化? 一个查询实例 : 求选修 2 号课程的学生姓名 QL 表示 : select name from tudents, C where tudents.no=c.no and Cno= 2 ; 关系代数表示 : Q1= π sname (σ tudents.no=c.no and Cno= 2 (tudentsc)) Q2= π sname (σ Cno= 2 (tudents C)) Q3= π sname ( tudents σ Cno= 2 (C)) Q1 = π sname (σ tudents.no=c.no and Cno= 2 (tudentsc)) tudents 代价计算 5 块 Q1 代价计算 ( 仅考虑 I/O 代价 ) 计算广义笛卡尔积代价假定 : 在内存中, 存放 5 块 tudents 元组和一块 C 元组, 一块可以装 10 个 tudents 元组或 100 个 C 元组. 假定 : tudents 有 1000 个元组,C 有个元组, 其中选 2 号课程的有 50 个元组数据只有读到内存才能进行连接 10 C 100

2 C 读入内存的次数 tudent 块数 Q1 = π sname (σ tudents.no=c.no and Cno= 2 (tudentsc)) 通过读取块数计算 I/O 代价读取块数计算方法 : tudents 1000 个元组 C 个元组读取总块数 : C 块数 5 块 tudents = = 若每秒读写 20 块, 则花费 : 2100 = 105s 20 C 100 Q1 = π sname (σ tudents.no=c.no and Cno= 2 (tudentsc)) 条件 :tudents 1000 个元组, C 个元组迪卡尔集后后的元组个数为 : =10 7 连接后的中间结果内存放不下, 需暂时写到外存若每块可装 10 个完成迪卡尔集后的元组, 则写这些元组需 : (10 7 /10)/20= s 选择操作 : 读回需 s, 假设选择后剩 50 个元组, 均可放在内存每秒读 20 块 tudents 10 C 投影操作 : 只需 CU 时间 100 查询共花费 : s 28 小时 5 块 Q2= π sname (σ Cno= 2 (tudents C)) Q2 代价计算 ( 仅考虑 I/O 代价 ) 计算自然连接代价也要把数据读到内存进行连接, 但连接结果比笛卡尔积要小得多读取块数依然为 : = = 花费为 2100/20 105s 假设连接结果大小为 10 4 个元组, 写到外存需 : (10 4 /10)/20=50s 每秒读 20 块 Q2= π sname (σ Cno= 2 (tudents C)) Q3= π sname ( tudents σ Cno= 2 (C)) 读取自然连接结果, 执行选择运算, 需 50s, 选择结果均可放在内存投影运算 : 只需 CU 时间总花费为 : =205s 3.4 分钟 Q3 代价计算 ( 仅考虑 I/O 代价 ) 计算对 C 做选择运算的代价需读 C 到内存进行选择运算读 C 块数为 : 10000/100=100 花费为 : 100/20=5s 选择结果为 50 个 C 元组, 均可放在内存 Q3= π sname ( tudents σ Cno= 2 (C)) 计算和 tudents 自然连接的代价 tudents 需读 tudents 到内存进行连 10 接运算 5 块读 tudents 块数为 : 1000/10=100 花费为 : 100/20=5s 连接结果为 50 个元组, 均可放在内存投影运算 : 只需 CU 时间总花费 : 5+5=10s C 50 关系系统的查询优化关系系统的查询优化由系统完成, 而不是由用户完成优化器可以从数据字典获取许多统计信息如果数据库的物理统计信息改变了, 优化器可以对查询进行重新优化以选择适应的执行计划优化器可以考虑数百种不同的执行计划优化器包括了许多复杂的技术优化目标 : 寻求最优的执行计划, 使查询执行开销尽量小

3 关系系统的查询优化查询执行开销主要包括 : 总代价 = I/O 代价 + CU 代价多用户数据库执行开销 : 总代价 = I/O 代价 + CU 代价 + 内存代价查询优化的途径物理优化查询优化的一般步骤将查询转化成内部表示 -- 语法树根据等价变化规则, 将语法树转化成优化形式选择底层操作算法生成查询计划查询优化的一般准则 ( 启发式规则 ): 下面的优化策略一般能提高查询效率, 但不一定是最优的选择和投影运算尽可能先做, 降低中间结果大小把投影运算和选择运算同时进行 π sno (no= 2 (C)) 把投影和其前或后的双目运算结合起来 π Cname (Course C) 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算 σ tudents.no=c.no and Cno= 2 (tudentsc) 找出公共子表达式关系代数等价变换规则 : 给定 π sname (σ tudents.no=c.no and Cno= 2 (tudentsc)) 如何将上述提到的运算先做, 即得到 : π sname ( tudents σ Cno= 2 (C)) 规则 1: 连接笛卡尔积的交换律 F F E 1 E 2 E 2 E 1 E 1 E 2 = E 2 E 1 E 1 E 2 = E 2 E 1 E: 关系代数表达式 F: 连接条件规则 2: 连接笛卡尔积的结合律 (E 1 E 2 ) E 3 = E 1 (E 2 E 3 ) (E 1 E 2 ) E 3 E 1 (E 2 E 3 ) (E 1 E 2 ) E 3 E 1 (E 2 E 3 ) F 1 F 2 F 1 F 2 规则 3: 投影的串接定律 π A1,A2,,An ( π B1,B2,,Bn (E)) π A1,A2,,An (E) 规则 4: 选择的串接定律 σ F1 (σ F2 (E)) σ F1 F2 (E) 规则 5: 选择和投影的交换律 σ F (π A1,A2,,An (E)) = π A1,A2,,An (σ F (E)) 特殊情况 π A1,A2,,An (σ F (E)) π A1,A2,,An (σ F (π A1,A2,,An, B1,B2,,Bm (E)))

4 规则 6: 选择与笛卡尔积的交换律 σ F (E 1 E 2 ) σ F (E 1 ) E 2 F 仅和 E 1 有关 σ F (E 1 E 2 ) σ F1 (E 1 )σ F2 ( E 2 ) F= F1 F2 σ F (E 1 E 2 ) σ F2 (σ F1 (E 1 )E 2 ) F1--E1 F2--E1E2 规则 7: 选择与并的分配律 σ F (E 1 E 2 ) σ F (E 1 ) σ F (E 2 ) 规则 8: 选择与差的分配律 σ F (E 1 -E 2 ) σ F (E 1 )- σ F (E 2 ) 规则 9: 选择对自然连接的分配律 σ F (E 1 E 2 ) σ F (E 1 ) σ F (E 2 ) 规则 10: 投影与笛卡尔积的分配律 π A1,A2,,An, B1,B2,,Bm (E 1 E 2 ) π A1,A2,,An (E 1 ) π B1,B2,,Bm (E 2 ) 规则 11: 投影与并的分配律 π A1,A2,,An (E 1 E 2 ) π A1,A2,,An (E 1 ) π A1,A2,,An (E 2 ) 关系代数表达式的优化算法 : 应用关系代数等价变换规则来优化关系代数表达式, 使优化后的表达式能遵循查询优化的一般准则, 在语法树上进行优化关系代数表达式的优化算法输入 : 语法树输出 : 计算关系代数表达式的程序 1 利用规则 4 把形如 σ F1 F2 Fn (E) 变换成 σ F1 (σ F2 ( (σ Fn (E)))) 2 对每一个选择, 利用规则 4~9 尽可能移到树的叶端 3 对于每个投影, 利用规则 3, 5, 10, 11 尽可能移到树的叶端 4 利用规则 3~5 把选择和投影的串接合并成单个选择, 单个投影, 或一个选择后跟一个投影 5 把处理后的语法树内节点分组 : 每一双目运算 (,,, ) 和它的所有直接祖先 (σ,π) 为一组, 后代直到叶子全是单目运算也并入该组 ; 若双目运算为, 且其后的选择不能与它结合为等值连接时, 这些单目运算单独为一组. 6 生成一个程序, 每组节点的计算是程序中的一步

5 σ π σ σ σ σ 不能结合成等值连接 σ.no=c.no C 能结合成等值连接优化的一般步骤 : 因 DBM 而不同把查询转换成某种内部表示 ( 例如关系代数语法树 ) 把语法树转化成标准 ( 优化 ) 形式选择底层的存取路径生成查询计划, 选择代价最小的例子 : 设有供应商, 零件和供应关系三个关系, 其关系模式 : (num, name, City) (num, name, Weight, ize) (num, num, Dept, Quan) select name from,, where.num=.num and.num=.num and.city= NANJING and.name= Bolt and.quan>1000; 原始语法树 : select-- 投影 from-- 笛卡尔积 where-- 选择 π name c:.num=.num and.num=.num and.city= NANJING and.name= Bolt and.quan>1000 π name π name π name π name π name p c:.num=.num and.num=.num and.city= NANJING and.name= Bolt and.quan>1000 c :.num=.num and.num=.num s:.city= NANJING p:.name= Bolt sp:.quan>1000

6 π name π name π name π name π name π name π name π name π name p p p p p c :.num=.num s:.city= NANJING p:.name= Bolt sp:.quan>1000 s:.city= NANJING p:.name= Bolt sp:.quan>1000 练习 1 查询要求 : 查询信息系学生选修的所有的课程的课程名称写出关系代数及其原始语法树, 并进行优化处理, 画出优化后的语法树. ELECT Cname FROM tudents,courses,c WHERE tudents.sno=c.sno and Courses.cno=C.cno and dept= I ; 练习 1: Π Cname (σ tudents.sno=c.sno C.cno=Courses.cno dept= I (tudents(ccourse))) 原始语法树 : tudents Π Cname 1 Π Cname C Courses 1 C Courses tudents tudents c: tudents.sno=c.sno C.cno=Courses.cno dept= I c : C.cno=Courses.cno c1: dept= I Π Cname C Courses 练习 2 查询要求 : 一图书管理数据库, 其关系如下 : 图书编号 BOOK(Title, Author, name, LC_No) UBLIHER(name, addr, city) 图书证号 BORROWER(Name, Addr, City, Card_No) LOAN(Card_No, LC_No, Date) 要求 : 1. 列出 2003 年 1 月 1 日之后借出的所有书名和借书人姓名 2. 写出关系代数及其原始语法树, 并进行优化处理, 画出优化后的语法树. ELECT Title,Name FROM BOOK,BORROWER,LOAN WHERE BOOK. LC_No = LOAN. LC_No AND BORROWER. Card_No= LOAN. Card_No AND Date> 01/01/2003 Π Title,Name (σ BOOK.LC_No=LOAN.LC_No BORROWER.Card_No=LOAN.Card_No Date> 01/01/2003 (BOOK BORROWERLOAN)) 语法树 : Π Title,Name Π Title,Author,name,LC_No,Name,Addr,City,Card_No,Date σ BOOK.LC_No=LOAN.LC_No BORROWER.Card_No=LOAN.Card_No BOOK LOAN BORROWER

7 Π Title,Name (σ F Date> 01/01/2003 (BOOK BORROWERLOAN)) σ F Date> 01/01/2003 (BOOK BORROWERLOAN) = σ F (BOOK) (BORROWERLOAN) = σ F (BOOK BORROWER) (LOAN) Π Title,Name σ BOOK. LC_No = LOAN. LC_No σ BORROWER. Card_No= LOAN. Card_No BOOK BORROWER LOAN Π Title,Name (σ F Date> 01/01/2003 (BOOK BORROWERLOAN)) 增加两个投影 : Π Title, BOOK.LC_No Π Name, LOAN.LC_No Π Title,Name σ BOOK.LC_No = LOAN. LC_No Π Π Name, LOAN.LC_No Title, BOOK.LC_No σ BORROWER.Card_No= LOAN.Card_No BOOK BORROWER LOAN Π Title,Name (σ F Date> 01/01/2003 (BOOK BORROWERLOAN)) Π Title,Name (σ F Date> 01/01/2003 (BOOK BORROWERLOAN)) Π Title,Name σ BOOK. LC_No = LOAN. LC_No Π Π Name, LOAN. LC_No Title,BOOK. LC_No σ BORROWER. Card_No= LOAN. Card_No BOOK 最后语法树 : Π Title,Name Π Π Name, LOAN. LC_No Title,BOOK. LC_No BOOK Π Π Name, BORROWER.CARD_No LOAN.LC_No,LOAN. Card_No Π LOAN.LC_No,LOAN. Card_No Π Name,BORROWER. CARD_No BORROWER LOAN BORROWER LOAN 物理优化涉及底层的存取路径, 不同的存取方案导致不同的执行效率物理选择高效合理的操作算法或存取路径优化方法基于启发式规则的存取路径选择优化基于代价的优化两者结合的优化方法选择操作的启发式规则小关系 : 全表顺序扫描 ( 优点 : 简单有效 ) C 95001, 1, , 1, , 2, , 1, , 3, 62

8 选择操作的启发式规则大关系选择条件是主码 = 值的查询, 查询结果最多一个选择主码索引 (RDBM 会自动建立主码索引 ) C 95001, , , , , 3 no, Cno 是主码选择操作的启发式规则大关系选择条件是范围查询或非等值查询, 或选择条件是非主属性 = 值的查询查询结果数目不明确估算查询结果的元组数量如果查询结果的元组数量 <10%, 且选择列上有索引使用索引扫描否则, 使用全表顺序扫描索引扫描 B+ 树索引或 Hash 索引如果选择条件的属性上有索引, 则可以利用索引进行扫描等值查询 : 使用索引得到符合等值条件的指针范围查询 : 仅适用于 B+ 树索引例如 age>20, 以 age=20 为索引项, 以此为入口点找到 age>20 的所有元组指针合取选择查询 : 例如 dept= C AND age>20 分别找到符合各个条件的元组指针, 取指针的交集 ; 或者找到符合第一个条件的元组指针, 在此范围内检查另一条件是否满足析取选择查询 : 使用全表顺序扫描物理优化预备知识 B+ 树索引连接操作的启发式规则如果两个表都已经按照连接属性排序排序合并连接例如 : tudents C 排序合并连接 ( 连接的关系分别排序 ): tudents 两个表只要扫描一次就可以完成连接操作 C 95001, , , , , 3 连接操作的启发式规则如果一个表的连接属性上有索引排序索引连接例如 : tudents 索引连接 ( 在 C 的连接列 no 上建立索引 ): tudents C C 上建立 no 的索引 C 95003, , , , , 1

9 连接操作的启发式规则如果前两个规则不适用, 且一个表较小 Hash 连接例如 : tudents C tudents (1) (2) C , 1 1. 划分阶段为小表建立 hash 桶 (3) Hash 连接 ( 选用 Hash 函数散列连接属性值 ): 例如 :Hash 函数 = 将 no 后三位模除 , , , , 1 2. 连接阶段 * 对大表顺序扫描 * 在匹配的 hash 桶内做顺序扫描连接操作的启发式规则最后可选用嵌套循环方法例如 : tudents C 循环嵌套连接 ( 不做任何预处理 ) 对外层循环表 ( 外表 ) 的每个元组, 扫描一遍内层循环表外循环表 tudents 选择占用内存块较少的表作为外表内循环表 C 物理优化基于代价的优化启发式规则适用于解释执行的系统优化开销包含在查询总开销中基于代价的优化适用于编译执行的系统一次编译优化, 多次执行优化开销不包含在查询执行中对代价进行估算, 选择代价最小的查询计划新教材 274 页

第二章关系数据库

第二章关系数据库本章内容针对关系数据模型的三要素进行论述 1. 数据结构 2. 数据操作 3. 数据的完整性约束条件 2.1 关系数据模型概述关系数据库, 是建立在关系数据模型基础上的数据库系统关系系统基于关系模型, 关系模型又是基于数学方面的数据抽象理论关系数据库, 用数学的方法来处理数据库中的数据关系数据模型 E.F.Codd,1970 年提出关系模型理论大型共享数据库数据的关系模型