浅谈分布式数据库系统查询优化

摘要:分布式数据库系统的查询优化,就是要寻找执行代价最小的查询执行策略,使系统执行效率达到最高。我们在应用中需要选择适当优化方法,在执行代价和便捷度之间得到最佳执行方案。

关键词:分布式数据库系统;查询优化;执行代价;半联接

中图分类号:TP311文献标识码: A 文章编号:1009-3044(2010)04-0790-03

Query Optimization in Distributed Database Systems

LI Ying

(Department of Computer Science, Shangqiu Normal College, Shangqiu 476000, China)

Abstract: The query optimization in distributed database systems is to look for execution plan for a query at minimum cost. Using this plan the system can work efficiently. We should choose the suitable method to get the best execution plan between costs and conveniences.

Key words: distributed database systems; query optimization; executed consideration; semi-join

1 概述

分布式数据库系统(Distributed Database Management System,DDBMS)是地理上分散而逻辑上集中的数据库系统。即通过计算机网络将地理上分散的各局域结点连接起来共同组成一个逻辑上统一的大数据库系统。因此可以说,分布式数据库系统是计算机网络技术和数据库技术的结合的产物。

分布式数据库系统的查询优化,就是要寻找执行代价(费用和时间)最小的查询执行策略,使系统执行效率达到最高。它包括局部执行代价的优化和网络传输代价的优化。其中局部执行代价:主要指输入/输出次数(I/O代价)及CPU处理代价。网络传输代价:主要指传输启动代价和数据传输代价。

2 查询优化的必要性

2.1 局部执行策略优化

我们通过一个例子来说明局部执行策略优化的必要性。

例2.1.1设有一供应关系数据库,有供应商和供应两关系,如下:

供应商:SUPPLIER{SNO,SNAME,AREA}

供应:SUPPLY{SNO,PNO,QTY}

查询要求:找出PNO 为100号零件的供应商的名称。

SQL表示为:SELECTSNAMEFROMSUPPLIER,SUPPLYWHEREPNO=100AND SUPPLIER.SNO=SUPPLY.SNO 。

关系代数表示为如下两种实现方法:

Q1= ∏SNAME (σSUPPLIER.SNO= SUPPLY .SNO and PNO=100 (SUPPLIER×SUPPLY))

Q2= ∏SNAME (SUPPLIER ∞ σPNO=100 (SUPPLY))

下面进行局部代价计算(不考虑CPU代价)。

首先我们假定: 在内存中,同时可存放5块SUPPLIER元组和1块SUPPLY元组,其中1个内存块可以装10个SUPPLIER元组或100个SUPPLY元组。另假定SUPPLIER有1000个元组,SUPPLY有10000个元组,其中PNO=100的有50个元组。假定计算机每秒可读写20块,而数据只有读到内存才能进行操作。

计算Q1的I/O代价(计算广义笛卡尔积代价):

读取总块数为:1000÷10+[1000÷(10×5)] ×(10000÷100)=2100;需时间t1=2100/20=105s;

按条件:笛卡尔积计算后的元组个数为:103×104=107,连接后的中间结果内存放不下, 需暂时写到外存,若每块可装10个完成笛卡尔积后的元组, 则写这些元组需:t2=(107÷10)/20=5×104s

进行选择操作:读回需t3=5×104s, 假设选择后剩50个元组,均可放在内存进行投影操作。

因此Q1查询共花费: t=t1+t2+t3=105+2×5 ×104≈105s≈28小时。

计算Q2的I/O代价:

计算对SUPPLY做选择运算的代价,需读SUPPLY到内存进行选择运算,读SUPPLY块数为:10000/100=100,花费为:t1=100/20=5s。

选择结果为50个SC元组, 均可放在内存。

计算和SUPPLIER自然连接的代价,需读SUPPLIER 到内存进行连接运算,读SUPPLIER块数为:1000/10=100,花费为:t2=100/20=5s。

连接结果为50个元组,均可放在内存进行投影运算。

因此Q2总花费为:t=t1+t2=5+5=10s。

从上述两种策略看,虽然都能实现所要完成的功能,但两种实现方法所须的代价却相差很大。

2.2网络传输优化

我们依然通过一个简单例子来说明网络传输优化的必要性。

例2.2.1有全局关系EMP{ENO,ENAME,BIRTH,SALARY,DNO} ,分别代表(主键)雇员编号、雇员姓名、出生日期、工资和部门号,及全局关系DEPT{DNO,DNAME},分别代表(主键)部门号和门名称。

查询要求:查询每个雇员的姓名及所在单位。

则:1)SQL语句:SELECTENAME,DNAME FROMEMP,DEPTWHEREEMP. DNO =DEPT. DNO;

2)关系表达式:∏ENAME,DNAME(EMP∞DEPT)。

选择策略(设结果为R,以传输代价为主)。

假设:

1)EMP:元组数:10000,元组大小:100B,关系大小:100×10000=1000KB。

2)DEPT:元组数:100,元组大小:35B,关系大小:35×100=3.5KB。

3)结果元组大小40B,S3为查询场地,结果关系大小:40×10000=400KB。

存在三个场地,S1、S2和S3。如图1所示。

策略1:S3为执行场地,则需传输EMP、DEPT ,传输量=1000K+3.5K=1003.5K。

策略2:S2为执行场地,则需传输EMP到S2,结果R传 输到S3。传输量=1000K+400K=1400K。

策略3:S1为执行场地,则需传输DEPT到S1,结果R传输到S3。 传输量=3.5K +400K=403.5K。

从上面三个策略看,选择不同的执行场地,传输代价差别很大。

分布式系统是多用户、多应用需求的复杂任务,那么采用不同的实现策略会相差更大,将直接影响整个系统整体性能。因此,进行分布式数据库系统的查询优化是分布式数据库系统必须重视的一个环节。

3 查询优化的方法

3.1 基于查询树的等价变换

基于查询树的等价变换,是将用户请求利用查询树来进行表示,然后再逐步对查询树进行等价变换,最终得到最优的查询策略。

查询树表示方法规则为,在查询树中,叶子表示关系,中间节点表示运算,前序遍历关系表示运算次序。

3.1.1 将用户请求构成的查询树进行等价变换,得到全局优化后的查询树

变换通用准则为:1) 尽可能将一元运算移到查询树的底部(树叶部分),使之优先执行一元运算。2) 利用一元运算的重复律,缩减每一关系,以减少关系尺寸,降低网络传输量和I/O大小。

在这里我们依然以例2.1.1进行说明。

查询要求:找出AREA在"北方"且PNO 为100号零件的供应商的信息。

SQL查询语句:SELECTSNO,SNAMEFROMSUPPLIER,SUPPLYWHEREAREA="北方"AND PNO=100ANDSUPPLIER.SNO=SUPPLY.SNO

等价的关系表达式:

Q1:∏SNO,SNAME σAREA="北方"σPNO=100(SUPPLIER∞SUPPLY)

查询树如图2。

利用变换规则进行等价变换后得到最终优化后的查询树Q2如图3所示。

3.1.2 利用全局关系与其片段关系的等价关系,将全局查询中的全局关系替换为对片段关系,得到对应于片段查询的查询树,经过等价变换,得到优化后的片段查询树

全局查询与片段查询对应的等价关系为:

1)对于全局关系R的水平分片R1、R2、…、Rn ,表示为:R=R1∪R2∪…∪Rn 。

2)对于全局关系R的垂直分片R1、R2、…、Rn ,表示为:R=R1∞R2∞…∞Rn 。

片段查询优化准则: 1)对于一元运算,根据一元运算的重复律,将叶子节点之前的选择运算作用于片段,如果不满足片段的限定条件,则置为空关系。2)对于联接运算的树,若联接条件不满足,则将其置为空关系。3)在查询树中,将联接运算(∞)下移到并运算(∪)之前执行。4)消去不影响查询运算的垂直片段。

3.2 基于半联接技术的分布式查询优化

半联接技术的优化就是通过减少联接操作的操作数,来降低传输费用的优化技术。

半联接优化算法原理如下:

输入信息:位于不同场地上的两个关系R和S;输出信息:实现R∞S(R.A=S.B);算法过程(设S的尺寸小于R):1) 在S所在场地上计算S'=∏B(S),2) 传送S'到R场地,3)在R场地上计算R'=R∞S'=R∝S,4) 将R'传到S所在场地,5) 在S所在场地上计算 R'∞S =(R∝S)∞S= R∞S 。

网络传输代价的比较:

假设:关系R和S分别在不同的场地上,C0为启动代价,C1为单位传输代价,设:在S所在的场地上执行。

则传输关系R实现R∞S的代价为C= C0+C1*Size(R) 。

采用半联接的传输代价C∝= CS'+ CR'。

= 2C0+C1*(Size(S')+ Size(R')) 。

因此如果有:C0/C1+ Size(S')+ Size(R')≤Size(R),则可用半联接技术来降低传输费用。

合理的采用半联接技术可以有效控制传输代价。

4 查询优化综合分析

那么现在的问题是,在设计查询执行策略时,是不是一定要寻找执行代价(费用和时间)最小的查询执行策略呢?我认为,软件系统的发展是以硬件系统的发展为基础的,不同阶段的硬件基础决定了相应的软件策略,我们之所以设计各种优化方法,就是因为我们的硬件条件没有达到我们需要的理想状态,所以我们需要软件的优化来弥补硬件的不足。我们知道优化的算法肯定不是最简单的算法,那么随着硬件条件的变化,我们在考虑执行代价的同时也要考虑算法的便捷度,在执行代价和便捷度之间取最佳执行方案,不能一味追求代价最小,做一些华而不实的优化策略。

这里有几个假设:1)假设我们的服务器的读取速度和处理速度可以达到无限快,那么我们就不用考虑局部处理优化。2)假设我们的网络带宽可以满足任何传输需求,那么我们就不需要进行网络传输优化。3)假设我们的存储器无限大,我们就可以存储任何信息,那么就不需要根据不同需求程度进行删减了。

如果满足上面3个假设,会得出什么结论呢?我们会发现不需要研究分布式数据库系统了,因为谁都知道分布式数据库的运行维护代价和出错频率要远远大于集中式数据库。即使达不到上面的理想状态,随着硬件的发展,软件简单化也必然是一种发展趋势。

或许大家觉得这是无稽之谈,我们回顾一下计算机软件的发展史我们会发现,早在计算机发展初期,机器处理速度非常低,内存用于数据交换的容量非常小,作为一个程序员,大部分精力都用在了研究算法上,写的程序尽可能简洁高效,在内存管理上更是倍加谨慎,不会轻易浪费一个字节的内存。现在又怎么样了呢?仅仅过了几十年时间,随便一台家用计算机可以有几GHZ的处理器以及几GB的内存,现在谁会去在乎一个程序是循环100次还是10000次,会注意一个程序是占用1KB内存还是1MB内存?我们现在关注的是程序的结构框架,关注的是实现的结果,对于具体算法实现过程往往很少在意。我们再回顾一个分布式数据库系统的典型实例――银行通存通兑系统,早在几年前,几乎每个大中城市都会有各自的数据库分片(副本节点),用户的一个存兑请求都作为一个事务在本地数据库分片上先操作,然后各个数据库分片(副本节点)之间会在一个约定的时间里,按照一定的更新算法进行传播更新,由于其间需要相互更新的数据量很大,而服务器性能不高,网络带宽也不够,因此我们的一个跨省市存款请求往往需要几天的时间才能完成。而现在由于服务器性能和网络带宽都显著提高了,很多数据库分片(副本节点)都已经取消了或者变成了全复制副本节点,通过提高硬件的性能来简化分布式数据库系统的组织结构,从而简化了软件系统的复杂程度,使得各种存兑操作都变得非常方便快捷。

因为硬件条件变化了,我们关注的点也变化了,当我们的硬件条件可以允许适当的浪费的时候,我们就会进一步考虑便捷性了。

5 结论

分布式数据库系统的查询优化,就是要寻找执行代价(费用和时间)最小的查询执行策略,使系统执行效率达到最高,优化的思想和方法在分布式数据库系统中必将得到广泛的应用和发展,优化的具体策略会随着硬件条件的发展而发展,从而实现既高效又便捷的分布式数据库系统。

参考文献:

[1] 邵佩英. 分布式数据库系统及其应用[M].2版.北京:科学出版社,2005.

[2] 郑振楣,于戈.分布式数据库[M].北京:科学出版社,1998.

[3] 贾焰,王志英,韩伟红,等.分布式数据库技术[M].北京:国防工业出版社,2001.

[4] 萨师煊,王珊. 数据库系统概论[M].3版.高等教育出版社,2000.

[5] 杨成忠,郑还远. 分布式数据库[M].哈尔滨:黑龙江科学技术出版社,1990.

注:本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文