时间：2022-12-12 14:30:02 | 来源：信息时代
时间：2022-12-12 14:30:02 来源：信息时代
并行数据库 : 以并行计算机为硬件环境并能充分体现多处理和I/O并行性的数据库。并行数据库是并行计算技术与数据库技术相结合而产生的新一代数据库,并行数据库着眼于采用各种并行算法提高数据库系统的计算速度和解决复杂性计算问题的能力。
从20世纪70年代开始,并行计算机系统发展十分迅速,很多大规模并行计算机系统(简记作MPP)已经投入市场,如nCUBE、iPSC、Paragon、KSR-1、CM2、CM5等。最近,随着高速通信网络技术的出现(如ATM和光纤通信技术)和操作系统的进展,基于网络的多计算机机群并行计算环境(简称机群并行计算环境)也开始出现,如NECTAR、PVM等系统。MPP和机群并行计算环境为高性能数据库系统的实现带来了希望。在MPP和机群并行计算系统的基础上建立的数据库系统称为并行数据库系统。并行数据库系统引起了学术界和工业界密切关注,已经成为一个重要的数据库研究领域。
并行数据库系统的历史可以追溯到数据库机(database machine,DBM)的研究。数据库机或称数据库机器旨在设计支持各种数据库管理系统功能的专用硬件,用专用计算机系统结构代替通用的Von Neumann计算机系统结构,为高性能数据库系统提供一个高效支撑环境。数据库机试图通过减少软件的复杂性来提高系统的效率和可靠性; 通过增加专用硬件、并行处理能力来改善数据库系统的性能。人们设计了很多数据库机。数据库机一般都作为通用计算机(称为宿主机)的后端机使用。在这种宿主机-后端机结构中,宿主机是用户与数据库机的界面,后端机(即数据库机)实现数据库的存取与控制。鉴于处理机与辅助存储器速度的极不匹配,加上数据库机硬件设计与实现的开销太大,数据库机没有取得成功。但是,数据库机的研究对并行数据库系统的建立起到了很大的作用,很多研究成果已经直接用于并行数据库系统。
20世纪80年代末期,人们开始研究如何在通用并行计算机系统上实现并行数据库系统。关系数据模型的面向集合和非过程性为关系数据库系统的并行化提供了有利的条件。并行数据库系统的研究主要围绕着关系数据库进行,包括三个研究领域:并行数据库的物理组织、并行数据操作算法的设计及并行数据库查询的优化处理。
并行数据库物理存储方法的目的是在多处理机之间分布各种数据库对象(关系、索引等),使得在查询处理过程中系统的并行性能够得到充分的发挥,最小化查询处理的响应时间。数据分布对并行数据库系统的性能具有极大的影响。到目前为止,人们已经提出了一维数据分布、多维数据分布等多种并行数据库物理存储方法。一维数据分布方法是最简单的数据分布方法,已被Bubba、Gamma、Teradata等并行数据库原型系统采用。一维数据分布技术的特点是: 通过划分关系的一个属性的域值来划分整个关系,得到一组子关系,然后在多处理机之间分布这些子关系。目前已经出现的一维数据分布方法主要包括 round-robin、hash、rangepartition、hybrid-range-partition等方法。一维数据分布方法具有一个共同的问题: 不能够有效地支持在非划分属性上具有选择谓词的查询。为了解决这个问题,后来又提出一些多维分布方法,其中包括CMD数据分布方法、基于错误校正码的数据分布方法、随机数据分布方法、基于hilbert曲线的数据分布方法、BERD数据分布方法等。除了数据分布方法以外,人们还对传统的数据库物理存储方法进行了拓展,进行并行化,使其适合于并行数据库系统,如并行B-树和并行GRID文件等。
并行数据操作算法研究的目的是设计实现各种关系操作的并行算法,如并行排序算法、并行连接操作算法、并行集合操作算法、并行选择操作算法、并行投影操作算法等,重点是并行连接操作算法的研究。目前已经出现了很多并行连接算法。这些算法可以归结为四类: 并行嵌套循环连接算法、并行排序合并连接算法、并行Hash连接算法及基于特定存储结构的并行连接算法。前三类并行连接算法不考虑被连接关系的物理存储结构。第四类并行连接算法是充分利用被连接关系的物理存储结构特点的并行连接算法。
并行数据库查询的优化处理是并行数据库系统的关键组成部分。在并行数据库系统中,查询优化的目标是寻找查询的具有最小响应时间的执行计划、需要新的查询处理算法和新的查询优化技术。目前已经出现了两类并行数据库查询处理和优化方法。一类是并行数据流方法; 另一类是并行查询计划空间搜索方法。并行数据流方法的基本思想是使用数据操作的顺序算法开发关系数据库系统的固有并行性,实现关系查询的并行执行。这种方法既不需要设计新的并行数据操作算法,也不需要修改现有的顺序数据操作算法,是一种在现有数据库技术的基础上实现并行数据库系统的简单方法。Gamma、Volcano、Tandem等并行数据库系统原型使用了这种方法。但是,并行数据流既没有考虑数据操作本身的并行处理也没有考虑在并行计算环境下的查询优化问题,不能充分地发挥多处理机的并行性,系统的查询处理的效率和能力受到很大的限制。于是,人们研究了基于查询计划空间搜索的并行数据库查询优化方法,提出了很多新的并行查询优化方法。这些方法可以分为两类: 两阶段方法和一阶段方法。两阶段方法分两阶段产生高效率的并行查询执行计划。第一阶段使用传统的查询优化方法产生高效率的顺序查询执行计划。第二阶段并行化第一阶段产生的顺序查询执行计划,产生一个高效率的并行查询执行计划。两阶段算法具有一个很大的问题: 第一阶段产生的顺序查询执行计划可能具有很高的固有顺序性,从而第二阶段产生的并行查询执行计划的并行性可能很低。一阶段方法直接产生高效率的并行查询执行计划,不需要首先得到优化的顺序查询执行计划,避免了两阶段方法的问题。但是,一阶段方法的复杂性远高于两阶段方法。目前提出的一阶段方法都是近似或启发式方法,主要有基于左线性树的方法、基于右线性树的方法、基于浓密树的方法、基于右片段树的方法、基于操作森林的方法和基于多重加权树的方法等。
目前,人们已经开始把并行数据库的基础研究成果转化为数据库产品,出现了很多商品化的并行数据库系统,并得到了广泛的应用。
在线咨询
