并行数据库的查询处理技术概况
科技信息
博士]专家论坛
并行数据库的查询处理技术
武汉大学
潘志安
摘要-随着并行计算机系统的迅速发展)并行数据库系统已经成为数据库研究和应用的一个重要领域)本文介绍了,
各种并行数据库系统的并行计算机结构和关系数据库查询的固有并行性)然后探讨了并行数据库查询处理的并行化技术+
关键词-并行数据库,
查询
划分技术
并行数据流方法
关系查询是一个"上的代数表达式+以下K表示关系集合+)(IJ
查询)表示K中的关系操作)ONI"(NJ表示LM的LMPQ?ALM表示LM的输出关系+输入关系)"(NJL?AQ?ALM
如果LM则称#*SNI)#和LMS无依赖关系)#R设LMLM可独立并行执行+在一个关系查询#和LMS是相互独立的)LM
中常常存在多个可独立并行执行的数据操作)可以使用多个处理机同时执行这些可独立并行执行的操作)实现查询处理的并行化+
如果LM或LM在缓冲区:上以流SR设LM#TLMSNI)S"#(水线方式依赖于LM或LM则称LM#"S()#和LMS可以按流水的输入+我们可以为每一个操作分配一个处理机)使得(@?FBC
产生第一个输出后=即可执行)从而实现这两QCUV?=BCUP@?FBC个操作的并行执行+可按流水线方式并行执行的数据操作的个数不局限于两个)可以有任意多个+
若LM可以分为多个可独立或按流水线方式XR设LMNI)
并行执行的子任务)则称LM是可并行执行的操作+
上述三种并行性为成功地建立并行关系数据库系统提供了
S-,X-充分的条件,+
数据随着全球信息化浪潮和计算机应用领域的不断拓展)库的规模越来越大)传统的集中式和客户.服务器数据库系统的难以适能力不足以支持海量数据库的查询和海量事务的处理)应迅速增长的应用要求)因此并行计算机越来越普及)并行数据库系统的研究与应用也变得更加重要+
一*并行数据库系统的并行结构
并行数据库系统所依赖的并行计算机结构主要包括四种!共享主存结构/共享磁盘结构/完全共享结构/无共享**0*12资源结构12+
在共享主存结构/多处理机共享主存储器)每个处理0中)
多处理机和共享主存由高速通讯网机具有独立的磁盘存储器)
,#-
络连接)处理机之间的通讯可以通过主存间接实现)也可以通过高速通讯网络直接实现+
在共享磁盘结构/处理机共享所有磁盘存储器)每个1中)
处理机之间的通讯可以通过磁盘处理机具有独立的主存储器)
存储器间接实现)也可以通过高速通讯网络直接实现+
在完全共享结构/处理机共享主存储器和磁盘存储2中)
处理机*共享主存储器和磁盘存储器由高速通讯网络连接+器)
处理机之间的通讯可以通过主存间接实现)也可以通过高速通讯网络直接实现+/2结构兼有/0结构和/1结构的特点+在无共享资源结构1没有任何共享硬件资源)每个处2中)处理机之间的通讯理机都具有独立的主存储器和磁盘存储器)
由高速通讯网络实现+/第一)通过3结构的优点主要有三个!第二)最小化共享资源使得由资源竞争带来的系统干扰最小化4具有高可扩充性)处理机个数可扩展到数百甚至上千个而不增第三)在复杂数据库查询处理和联机事务处加处理机间的干扰4
理过程中可以获得接近线性的加速+/3结构的主要缺点是通讯的代价和非本地磁盘访问的代价)因为数据的传送涉及到两端软件的交换+52671757系统*573120系统*389:系统和;7<=系统都具有/>?@ABC3结构)DCE=B和DEFFE研究
,#-,G-,H-原型也是建立在/+3体系结构之上的
本文主要基于/下文中将/3结构+3结构中的每个由单处
线方式并行执行)即一个操作"是另一个操作"(QCUV?=BC=UPW
三*查询处理的并行化技术
并行性的关键在算法)把一个查询分解成能由对应的足够
G-多的处理机进行处理的并行过程是复杂的,+
并行数据流方法能够实现查询处理的并行化)它使用现有的数据操作算法并行地执行关系数据库查询)实现关系数据库也不需要修改现有的顺序数据操作算法)是一种在现有数据库理论*技术和方法的基础上实现并行数据库系统的简单方法+并行数据流方法分为简单并行数据流方法和以数据划分为基础的
查询的三种固有并行性)既不需要设计新的并行数据操作算法)
并行数据流方法+这些方法已被D7007*;LY873L*573W
,S-120等系统使用+#R简单并行数据流方法+关系查询可以作为并行数据流图
执行+图#给出了一个/KY查询语句及其并行数据流图+图中
理机*主存储器和磁盘构成的单处理机系统称为处理结点+
二*关系数据库查询的固有并行性
关系模型和关系数据库系统的非过程性查询语言为其并行关系查询特别适于并行处理)关系查询实现提供了有利的条件+
一般由多个基本数据操作组成)这些数据操作与关系集合形成了一个代数系统)称为关系代数+由于关系代数的封闭性和数据操作的相对独立性)关系查询具有三种固有并行性)即数据操作数据操作间的独立并行性和单数据操作内间的流水线并行性*
#-的并行性,+
设"是关系代数系统)其中I是数据操作集合)是关系)(IJJ
如果为’Q(+@=EP表示数据操作选择和投影的组合"@B>B=ACUZB=A
图中每个操作分配一个处理机)并按数据流图执行给定的查询)则可以使[和ZP@BCAU[P按流水线方式并行执行)ZU[P和两个
两个@实现了@=EP按流水线方式并行执行)=EP独立并行执行)该查询的并行执行+使用简单并行数据流图方法实现关系查询的并行化)需要一个关系查询执行器)完成以下几个功能!由"#(查询语句产生数据流图4为数据流图中的数据操作分配处理"S(机4协调各个处理机调用顺序数据操作算法完成查询处理+"X(
简单并行数据流图方法可以有效地发挥关系数据库查询的
作者简介!潘志安"男)湖北孝感人)高级工程师)武汉大学计算机学院在读工程硕士)主要研究软件工程*数据库技术+#$%&’()
方数据万
\#G\
并行数据库的查询处理技术概况
科技信息
博士V
专家论坛
性"下述##$%方法可以很好地解决这个问题"
流水线并行性和独立并行性!但是难以实现单关系操作的并行
&’以数据划分为基础的并行数据流图方法(##$%方法)
"假设系统中的关系都已根据需要划分为多个子集并存储在不同的磁盘上"当系统接收一个查询后!##$%的查询运行器将其转化为并行数据流图!然后按照这个并行数据流图进行查询处理"##$%处理查询中每个数据操作*#的方法与简单并行数据流图方法不同!它首先把操作关系划分为+个子集合!并建立+个执行相同操作*#的进程!每个进程在一个子集合上运行,然后使用多个处理机并行地执行这些进程,最后将执行结果合成为*#操作的最终结果"