资源描述：
《基于统计的查询优化.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、.第24卷第1期长春光学精密机械学院学报l24NO1vo.2001年3月Journ目ofClgehunIsntituteofticsandiPenMechaniesMar2001翻OP基于统计的查询优化叶青苑丽红(长春光学精密机械学院电子与信息分院)摘要本文介绍一种关系数据库查询优化方法,讨论如何利用与数据库文件存取,,,相关的参数评估查询策略的实现成本如何利用统计信忽寻找最优查询策略以及查询优化的必要性和基本步骤。;关键词关系数据岸查询处理中图分类号TP39文献标识码A1查询处理,查询处理是数据库管理系统一重要组成部分既根据用户要求从数据库文件中抽取满足
2、,:要求的数据结果通常由三部分组成压亚巫日一~一匣平画l)语法分析与转换;;2)查询优化3),:执行查询策略基本结构如图1在系统查询处理之前首先要将用户~输人的高级语言(SQ)L表示的查询转换为系统物理层能够识别和实现的形式一蓄,(关系代数表达式的语法树)通常这种,图1查询处理程序:转换结果并不唯一例如一个查询要气,求在SQL语言中有多种表达方式一条SQL语句又可以转换为多种等价的关系代数表达,,,式而每个代数运算操作有多种实现算法因此在一个查询要求被具体实现之前数据库管。:理系统必须提供关系代数表达式和每个代数操作的实现算法注释例如SELECT成绩FRO
3、M学生成绩表WHERE成绩<60:这条SQL语句可转换成下面两个等价的代数关系表达式一;成绩单<6。成绩Ql(n(学生成绩表))一成绩绩单<602Qn(鲡(学生成绩表)),,绩单0这两个关系代数表达式运算结果相同此外、6<有多种实现算法最简单的算法,,,,是线性查询如果关系中元组按成绩的值排序可以采用二分法如果建立索引文件查询。,。效率会更高一个关系代数表达式附上每步运算的算法说明即是一个查询策略查询优化,,,不同的查询策略虽然得到的结果相同但他们的实现成本不同应用中用户更重视的:2000一12一19收稿日期,:,,,。作者简介叶青女讲师硕士主要从事多媒体
4、技术工作长春光学精密机械学院学报2年,,是查询时间因此系统通过评估不同策略的时间代价选择一种效率最高的查询策略这一过。、、程被称为查询优化一个查询计划从开始执行到结束需要进行磁盘存取CPU计算传输等操作,其中最主要的延时是磁盘存取,为简化问题常常简单地使用读写磁盘块数来衡量一。,个查询策略的时间代价我们对查询策略的选择依赖于对查询策略成本的评估也就是需要。:计算每个查询策略大约访问多少次磁盘影响读写磁盘块数多少的因素有两个一个是每个,。关系代数运算的实现算法另一个是关系代数表达式的选择.21关系代数运算的实现算法,,=二:,关系代数有许多运算这里我们以选择
5、为例鼓(R)有多种实现算法算法:A采用,,,线性查询既从第一个元组扫描到最后一元组文件分布在磁盘上的每一个块都需读人一次。,r因此它的成本等于数据文件在磁盘上占用块数用B表示关系R在磁盘上占用块数用,。=BrC()ST(A)表示算法A的查询成本则有OOST(A),。:算法B若关系R在属性X上有序且与元组在磁盘上存放顺序相同可以采用二分法,,,,=:如果X是R的码即满足条件的元组只有一个则COST(B)「!goz(B)飞若X不是码有,,可能有多个满足条件的元组存在需计算这些元组占用磁盘块数用rF表示每块存放关系R,,:xlX=xlx/厂乍一1即的元组个数用(
6、)表示满足的元组个数则「r(l)]是满足条件的元组,,=12B:+rx丫一l占用块数所以。OST(B)「09()飞「(l)邝飞由此公式我们可以计算出采用二。,,x1X=xl分法实现选择运算的成本代价这里还有个问题r()即满足选择条件的元组个数,,由于系统还没有执行选择操作这个参数我们得不到确定值只能计算统计值假设属性X有,,不同的值M个且每个值出现的频率相同关系R中有N个元组则平均每个X值对应,,,,N/M个元组用Nr表示关系R中元组个数V(XR)表示R中属性X不同取值的个数,,,,,::xt=/VXRX是二VX尺x、=1则有公式()Nr()若码则Nr()
7、r()由此得出,。COST(B)=「lB门可见算法B的成本远远小于算法Aogz,要在不同的查询策略中选一种成本最低的策略优化器必须要评估每一种查询策略的成,,、、本这一过程需要一些统计信息如上面用到的关系的元组数每块存放元组数某一属性、,有多少不同取值以及整个关系在磁盘上占用块数等等这些参数必须在系统中详细记录并。且随数据库的更新而更新.22关系代数表达式的选择,,对某一代数运算选择一种算法是在关系代数表达式确立之后进行的同一查询可用多,:种等价的表达式表示例如...,’’sELEcrsNFROMSsc环下田RE55#=S#ANDC#=2CSCSC:系统可
8、将其转换成下面三种形式··二二5=1Q11sN(飞“趾,义#c。(
