4关系系统及其查询优化.ppt

1、9 关系系统及其查询优化,4.1 思考题,关系系统的定义？如何理解关系系统？ 关系系统分类？常用的关系系统示例 什么是表式系统？最小关系系统？关系完备系统？全关系系统？ 准则的含义？ 信息准则的含义？ 保证访问准则？空值的含义？ 统一的数据子语言准则？ 视图更新准则？ 数据物理独立性数据逻辑独立性 数据完整性独立性？,关系系统及其查询优化,关系系统: 关系模型的基本要素:关系数据结构 、关系的完整性、关系操作 支持关系数据结构（表） 支持选择、投影、连接运算，对这些运算不必要定义任何物理存储路径 关系系统的分类 表式系统：仅支持表数据结构,不支持集合操作 最小关系系统:仅支持关系数据结构和3种

2、关系操作 关系完备的系统:支持关系数据结构和所有的关系代数操作 全关系系统:支持关系模型的所有特征,关系系统及其查询优化,全关系系统的12条准则 0. 一个关系的DBMS必须能完全通过它的关系能力来管理数据库. 关系的DBMS必须在关系级别上支持数据的插入修改删除 关系的DBMS必须保证信息准则和访问准则. 1.信息准则:关系的DBMS的所有信息都应该在逻辑一级上用一种方法即表中的值显式地表示. 2.保证访问准则. 3.空值的系统化处理. 4.基于关系模型的动态的联机数据字典. 5.统一的数据子语言的准则. 6.视图更新准则.,关系系统及其查询优化,全关系系统的12条准则 7. 高级的删除插入

3、修改操作 8.数据的物理独立性 9.数据逻辑独立性 10.数据完整性独立性. 11.分布独立性. 在第一次引入分布式数据时 当数据重新分布时 12.无破坏准则.,关系系统及其查询优化,关系数据库系统的查询优化 查询处理:从查询语句出发到获得查询结果的处理过程 查询优化是查询处理中的重要环节.寻求最优的执行策略 包括:代数优化物理优化规则优化等 包括4个步骤: 将查询转换成某种内部表示,通常是语法树 根据等价变化规则将语法树转化为标准(优化)形式 选择低层的算法 生成查询计划:,关系系统及其查询优化,一个示例: 求选修了2号课程的学生的姓名. SELECT S.Sname FROM S,SC W

4、HERE S.sno=SC.Sno AND SC.Cno=2 等价的关系代数:,关系系统及其查询优化,假设有1000个学生记录,10000个选课记录,选2号课程的选课记录有50个 第一种情况: 计算笛卡儿积：设一个块可以装入10个S元组和100个SC元组，在内存里存放5块S元组和1块SC元组。 则读取总块数为： 1000/10+1000/（10*5）*10000/100 设每秒读20块，则读数据时间为105秒 连接后的元组为10000000个，设可以装10个元组每块。写进中间文件的时间为：10000000/10/20=50000秒 做选择操作：忽略处理时间。读入数据时间为50000秒 做投影：

5、 总时间为：105+50000*2=100105秒。,关系系统及其查询优化,第二种情况: 计算自然连接：设一个块可以装入10个S元组和100个SC元组，在内存里存放5块S元组和1块SC元组。 则读取总块数为： 1000/10+1000/（10*5）*10000/100 设每秒读20块，则读数据时间为105秒 连接后的元组为10000个，设可以装10个元组每块。写进中间文件的时间为：10000/10/20=50秒 读取中间 文件块：忽略处理时间。执行选择运算，时间也是50秒 做投影： 总时间为：105+50+50=205秒。,关系系统及其查询优化,第三种情况: 先对SC表做选择运算：读SC表5秒

6、。 读取S表：时间也是5秒 连接结果做投影： 总时间为：5+5=10秒,查询优化的一般准则 选择运算应该尽可能先做：使计算的中间结果由大变小 在执行连接之前对关系进行适当的预处理 在连接属性上建立索引或对关系排序。P161 把投影运算和选择运算同时进行。避免重复扫描关系 把投影同其前或后的双目运算结合起来。 把某些选择同它在前面要执行的笛卡儿积结合起来成为一个连接运算 找出公共子表达式,关系系统及其查询优化,关系代数等价变换规则 1 连接、笛卡儿积交换律 2 连接、笛卡儿积结合律 3 投影的串接定律 4 选择的串接定律 5 选择与投影的交换律 6 选择与笛卡儿积的交换律 7 选择与并的交换 8

7、 选择与差的交换 9 投影与笛卡儿积的交换 10 投影与并的交换,关系系统及其查询优化,关系代数表达式的优化算法 算法:关系表达式的优化 输入:一个关系表达式的语法树 输出:计算表达式的程序 方法: 1 规则4:选择的串接定律进行变换 2 对每个选择尽量安排在叶端(规则4-8) 3 对每个投影尽可能移到叶端(规则3 9 10 5) 4 把选择和投影串接合并成单个选择单个投影或一个选择后跟一个投影 P164,关系系统及其查询优化,优化的一般步骤 将查询转换成某种内部表示,通常是语法树 根据等价变化规则将语法树转化为标准(优化)形式,关系系统及其查询优化,选择低层的算法 生成查询计划:,关系系统及

8、其查询优化,代数优化:对查询进行等价交换. 设有: S(SNUM,SNAME,CITY) 供应商 P(PNUM,PNAME,WEIGHT,SIZE) 零件 SP(SNUM,PNUM,DEPT,QUAN) 供应关系 查询: 查询供应一个部门10000个以上螺栓并且位于南京的供应商的名字. SELECT SNAME FROM S,P,SP WHERE S.SNUM=SP.SNUM AND SP.PNUM=P.PNUM AND S.CITY=NAJING AND P.PNAME=BOLT AND SP.QUAN10000;,关系系统及其查询优化,语法树: C=S.SNUM=SP.SNUM AND S

9、P.PNUM=P.PNUM AND S.CITY=NAJING AND P.PNAME=BOLT AND SP.QIAN10000;,关系系统及其查询优化,尽可能将选择操作 沿语法树下压 则有:,关系系统及其查询优化,将连接条件与笛卡儿积 组合成连接操作,关系系统及其查询优化,用投影操作取消对查询 无用的属性,关系系统及其查询优化,代数优化总结： 以SELECT子句对应投影操作，以FROM子句对应笛卡儿积，以WHERE子句对应选择操作，生成原始查询树 尽可能将选择条件移向树叶 应用连接、笛卡儿积的结合律，按照小关系先做的原则，重新安排连接（笛卡儿积）的次序。 如果笛卡儿积后还需要按连接条件进行

10、选择操作，可以将2者组合成连接操作 对每个叶节点加必要的投影操作，以消除对查询无用的属性。,关系系统及其查询优化,规则优化:结合存储路径的分析,讨论各种基本操作执行的策略及选择原则. 选择操作的实现与优化:与选择条件存取路径选取元组占整个关系的比例有关系 最原始的实现方法是-顺序扫描(不需要特殊的存取路径),适用于小的关系 DBMS支持建立各种存取路径 B+树 索引:无序索引/排序索引,关系系统及其查询优化,优化策略: 小的关系直接扫描 对于主键上的等值条件查询,最多只有一个元组可以满足条件应优先用主键上的索引 对于非主键上的等值条件查询,需要估计中选的元组的在关系中站的比例,比例小(15%)

11、可以用无序索引,否则可以用有序索引或顺序扫描 对于有and连接的复合选择,应有复合索引 对于用or 连接的选择条件,只能按其中各个条件分别选出一个元组集,在求并运算. 无好的优化方法,应该尽量少用. 有些选择操作只要访问索引就可以得到结果.如,查询索引属性的最大值等.,关系系统及其查询优化,连接操作的实现与优化: 嵌套循环法:设有关系R和S进行连接操作 原始的办法就是选取R的一个元组,与S的所有的元组比较,满足连接条件的就输出,再选取R下一个元组重复上述过程. 具体算法如下:,关系系统及其查询优化,/*r有n个元组,s有m个元组*/ I1,j1 While (I=n) Do while (J=

12、m) do if r(I)a=s(j)b then 输出 R(I),s(j)到T; j=j+1 J=1,I=I+1 利用索引寻找匹配元组的方法:在内关系上建立索引,具有合适的存取路径,以取代顺序扫描,关系系统及其查询优化,排序归并法:原理P161. /*r有n个元组,按属性A排序,s有m个元组,按属性B排序*/ I1,j1 While (Is(j)b then j=j+1; else if r(I)as(j)b then I=I+1; else /* r(I)a=s(j)b,输出连接元组*/ 输出 R(I),s(j)到T; /*输出r(I)与S中除S(j)外的其他元组所组成的连接元组*/ p-

13、j+1 while (p=m) and (r(i)a=s(p)b),关系系统及其查询优化,do 输出R(i),s(p)到T p=p+1; /*输出S(J)与r中除r(I)外的其他元组所组成的连接元组*/ K-I+1 while (K=N) and (r(K)a=s(J)b) do 输出R(K),s(J)到T KK+1; II+1, J1+1; ,关系系统及其查询优化,投影操作的实现:与选择连接同时进行.不需要增加I/O开销. 注意投影后消除重复元组 可以用排序等方法消除重复元组. 集合操作的实现:笛卡儿积并交差 笛卡儿积用嵌套循环实现. 并/交/差的算法如下:,并操作算法 将RS按主键升序排序

14、 I1,j1 While (Is(j) /*指的R(i)主键大于S(j)的主键,下同*/ then 输出 s(j)到T; jj+1; else if r(I) s(j) then 输出 R(i)到T; II+1 else jj+1;/*跳过一个重复的元组*/ if (I=n) then 把R(i)到 R(n)的元组输出到 T; if (j=m) then 把S(j)到 S(m)的元组输出到 T;,交操作算法 将RS按主键升序排序 I1,j1 While (Is(j) /*指的R(i)主键大于S(j)的主键,下同*/ then jj+1; else if r(I) s(j) then II+1

15、else 输出R(i)到T;/*R(i)=S(j),输出一元组*/ II+1,jj+1; ,差操作算法 将RS按主键升序排序 I1,j1 While (Is(j) /*指的R(i)主键大于S(j)的主键,下同*/ then jj+1; else if r(I) s(j) then 输出R(i)到T; II+1; else II+1,jj+1; If (I=n) then 把R(i)到 R(n)的元组输出到 T;,关系系统及其查询优化,代价估算优化 查询执行代价的组成 访问辅助存储器代价(I/O代价) 计算代价(CPU代价) 通信代价(分布式时要考虑) 代价模型: Ci/o=D0+D1x X 存

16、取数据的大小 D0 与x无关的I/O代价,包括寻道时间和等待时间 D1 每个字节所需要的传输时间 一般: Ci/o=D0 I/O代价=I/O次数* D0,关系系统及其查询优化,nR关系R中的元组数目 pR-关系R的块因子,既每个物理块中所包含的元组数 Na 表示属性a在关系中取多少种不同的值 Fa 属性a的选择因子.即属性a为某属性值的概率Fa=1/Na,在目录里只保留Fa,Na中的一个. Ma属性 a的域的大小|DOM(a)| L索引的级别 选择操作的代价估算 顺序扫描: 最多选取一个元组: C=.5n/p=.5b 关系的物理块数 选取多个元组:C=b,关系系统及其查询优化,利用聚集索引进行

17、等值查询: C=L+S/P S 满足条件的元组数目. L :访问索引所需要的I/O代价 利用聚集索引进行范围查询(估算): C=L+b/2 应用示例:设有关系S统计数据及存取路径如下: n=10000,b=2000,则 P=5 在属性dept上建有聚集索引,L=2,Ndept=25 在属性sno上建有主索引,L=4,Nsno=10000 在属性dno上建有2次索引,L=2,Ndno=20 宿舍号码 在属性age上建有聚集索引,L=2,Nage=15,Q1: C=L+1=5 利用主索引 Q2: 利用聚集索引 S=10000/25=400(平均值) C=L+S/P=2+400/5=82 Q3: 范围查询.虽然有2次索引,但非聚集索引如果取一半以上元组还不