《2022年并行数据库的查询处理技术概 .pdf》由会员分享，可在线阅读，更多相关《2022年并行数据库的查询处理技术概 .pdf（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、作者简介!潘志安#$%&()男)湖北孝感人)高级工程师)武汉大学计算机学院在读工程硕士)主要研究软件工程*数据库技术+并行数据库的查询处理技术武汉大学潘志安,摘要-随着并行计算机系统的迅速发展)并行数据库系统已经成为数据库研究和应用的一个重要领域)本文介绍了各种并行数据库系统的并行计算机结构和关系数据库查询的固有并行性)然后探讨了并行数据库查询处理的并行化技术+,关键词-并行数据库查询划分技术并行数据流方法随着全球信息化浪潮和计算机应用领域的不断拓展)数据库的规模越来越大)传统的集中式和客户.服务器数据库系统的能力不足以支持海量数据库的查询和海量事务的处理)难以适应迅速增长的应用要求)因此并行
2、计算机越来越普及)并行数据库系统的研究与应用也变得更加重要+一*并行数据库系统的并行结构并行数据库系统所依赖的并行计算机结构主要包括四种!共享主存结构/0*共享磁盘结构/1*完全共享结构/2*无共享资源结构1 2,#-+在共享主存结构/0中)多处理机共享主存储器)每个处理机具有独立的磁盘存储器)多处理机和共享主存由高速通讯网络连接)处理机之间的通讯可以通过主存间接实现)也可以通过高速通讯网络直接实现+在共享磁盘结构/1中)处理机共享所有磁盘存储器)每个处理机具有独立的主存储器)处理机之间的通讯可以通过磁盘存储器间接实现)也可以通过高速通讯网络直接实现+在 完 全 共 享 结 构/2中)处 理
3、机 共 享 主 存 储 器 和 磁 盘 存 储器)处理机*共享主存储器和磁盘存储器由高速通讯网络连接+处理机之间的通讯可以通过主存间接实现)也可以通过高速通讯网络直接实现+/2结构兼有/0结构和/1结构的特点+在无共享资源结构1 2中)没有任何共享硬件资源)每个处理机都具有独立的主存储器和磁盘存储器)处理机之间的通讯由高速通讯网络实现+/3结构的优点主要有三个!第一)通过最小化共享资源使得由资源竞争带来的系统干扰最小化4第二)具有高可扩充性)处理机个数可扩展到数百甚至上千个而不增加处理机间的干扰4第三)在复杂数据库查询处理和联机事务处理过程中可以获得接近线性的加速+/3结构的主要缺点是通讯的代
4、价和非本地磁盘访问的代价)因为数据的传送涉及到两端 软件的交换+5 2 67 1 7 5 7系统*57 3 12 0系统*3 89:系统和;7?A BC系统 都 具 有/3结 构)DC E=B和DEF F E研 究原型也是建立在/3体系结构之上的,#-,G-,H-+本文主要基于/3结构+下文中将/3结构中的每个由单处理机*主存储器和磁盘构成的单处理机系统称为处理结点+二*关系数据库查询的固有并行性关系模型和关系数据库系统的非过程性查询语言为其并行实现提供了有利的条件+关系查询特别适于并行处理)关系查询一般由多个基本数据操作组成)这些数据操作与关系集合形成了一个代数系统)称为关系代数+由于关系代
5、数的封闭性和数据操作的相对独立性)关系查询具有三种固有并行性)即数据操作间的流水线并行性*数据操作间的独立并行性和单数据操作内的并行性,#-+设 I)J(是关系代数系统)其中I是数据操作集合)J是关系集合+关系查询是一个 I)J(上的代数表达式+以下K表示关系查 询)L MN I表示K中的关系操作)O PQ?AL M(N J表示L M的输入关系)L?A Q?A L M(N J表示L M的输出关系+#R设L M#*L MSN I)如 果L M#和L MS无 依 赖 关 系)则 称L M#和L MS是相互独立的)可独立并行执行+在一个关系查询中常常存在多个可独立并行执行的数据操作)可以使用多个处理
6、机同时执行这些可独立并行执行的操作)实现查询处理的并行化+SR设L M#T L MSN I)如果LMS或L M#(在缓冲区:上以流水 线 方 式 依 赖 于L M#或L MS()则 称L M#和L MS可 以 按 流 水线 方 式 并 行 执 行)即 一 个 操 作 QC UV?=BC(是 另 一 个 操 作=UPW?F BC(的输入+我们可以为 每 一个 操 作 分 配 一 个 处 理 机)使 得QC UV?=BC产生第一个输出后=UP?F BC即可执行)从而实现这两个操作的并行执行+可按流水线方式并行执行的数据操作的个数不局限于两个)可以有任意多个+XR设L MN I)若LM可以分为多个可
7、独立或按流水线方式并行执行的子任务)则称L M是可并行执行的操作+上述三种并行性为成功地建立并行关系数据库系统提供了充分的条件,S-,X-+三*查询处理的并行化技术并行性的关键在算法)把一个查询分解成能由对应的足够多的处理机进行处理的并行过程是复杂的,G-+并行数据流方法能够实现查询处理的并行化)它使用现有的数据操作算法并行地执行关系数据库查询)实现关系数据库查询的三种固有并行性)既不需要设计新的并行数据操作算法)也不需要修改现有的顺序数据操作算法)是一种在现有数据库理论*技术和方法的基础上实现并行数据库系统的简单方法+并行数据流方法分为简单并行数据流方法和以数据划分为基础的并行数据流方法+这
8、些方法已被D7 007*;L Y8 7 3 L*5 7 3 W1 2 0等系统使用,S-+#R简单并行数据流方法+关系查询可以作为并行数据流图执行+图#给出了一个/K Y查询语句及其并行数据流图+图中=EP表示数据操作选择和投影的组合 B B=A QC UZ B=A(+如果为图中每个操作分配一个处理机)并按数据流图执行给定的查询)则 可 以 使P BC A和Z UP按 流 水 线 方 式 并 行 执 行)ZUP和 两 个=EP按流水线方式并行 执 行)两 个=EP独 立 并 行 执 行)实 现 了该查询的并行执行+使用简单并行数据流图方法实现关系查询的并行化)需要一个关系查询执行器)完成以下几
9、个功能!#(由查询语句产生数据流图4 S(为数据流图中的数据操作分配处理机4 X(协调各个处理机调用顺序数据操作算法完成查询处理+简单并行数据流图方法可以有效地发挥关系数据库查询的G#科技信息博士专家论坛名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 4 页 -流水线并行性和独立并行性!但是难以实现单关系操作的并行性下述#$%方法可以很好地解决这个问题&以数据划分为基础的并行数据流图方法(#$%方法)假设系统中的关系都已根据需要划分为多个子集并存储在不同的磁盘上当系统接收一个查询后!#$%的查询运行器将其转化为并行数据流图!然后按照这个并行数据流图进行查询处理#$%处理查询中每个
10、数据操作*#的方法与简单并行数据流图方 法 不 同!它 首 先 把 操 作 关 系 划 分为+个 子 集 合!并 建 立+个执行相同操作*#的进程!每个进程在一个子集合上运行,然后使用多个处理机并行地执行这些进程,最后将执行结果合成为*#操作的最终结果在#$%中!由 于 数 据 的 划 分 和 数 据 操 作 的 多 进 程 化!每个数据操作进程可能具有多个输入数据流!而且每个操作进程的输出数据流可能需要分解为多个数据流来为其它操作进程提供输入数据流因此!除了查询运行器以外!#$%方法还需要两个新的数据操作-合并(./01/)和分解(2345 6)操作前者将多个输入数据流合并为一个输出数据流,
11、后者将一个输入数据流分解为多个输出数据流合并和分解操作的算法不是唯一的!与数据划分策略有关把合并和分解操作与数据操作进程相结合!就 可 以 使 用#$%方 法 利 用 现 有 的 顺 序 数 据 操 作 算 法 实 现 查询的并行处理78 97&9下面以图8中:;%8和%&!存放在三个不同的磁盘上,关系?已分解为两个子集合?=和?8!存放在两个不同的磁盘上,关系已分解为三个子集合=8和&!存放在三个不同的磁盘上查询运行器为%上的:%+操 作 建 立 三 个:%+进 程!记 作:%+8:%+&和:%+A,为?上 的:%+操 作 建 立 两 个:%+进 程!记 作:%+B和:%+C,为D*E+操
12、作 建 立 三 个D*E+进 程!记 作D*E+8D*E+&和D*E+A,为E+:F GH操作建立三个E+:FGH进程!记作E+:F GH8E+:F GH&和E+:FGHA给定查询的基于数据划分的并行数据流图如图&所示为了保证数据流正确地在各个进程之间流动!需要在每个:%+进 程 的 输 出 端 连 接 一 个 分 解 操 作!在 每 个D*E+进 程 的输 入 端 连 接 一 个 合 并 操 作!在 每 个D*E+进 程 的 输 出 端 连 接 一个分解操作!在每个E+FGH进程的输入端连接一个合并操作关 系%的:%+进 程 输 出 端 所 连 的 分 解 操 作 的 功 能 是 将:%+的
13、 输 出 按D*E+操 作 的 数 据 划 分 要 求 分 解 为 三 个 数 据流!分别送到三个D*E+进程的第一输入端所连的合并操作关系?的:%+进 程 输 出 端 所 连 的 分 解 操 作 的 功 能 是 将:%+的 输 出 按D*E+操 作 的 数 据 划 分 要 求 分 解 为 三 个 数 据 流!分 别送到三个D*E+进行的第二输入端所连的合并操作 D*E+进程输出端所连的分解操作的功能是将D*E+的输出按关系的划分策略分解为三个数据流!分别送到三个E+:F GH进程输入端所连的合并操作若查询运行器为每个数据操作进程和相应的分解与合并操作分配一个处理结点!按照图&所示的并行数据流
14、图执行给定的数据库查询!则可实现操作E+:F GH和D*E+D*E+和两个:%+之间的流水线并行运行以及两个:%+间的独立并行运行!也可实现E+:F GHD*E+和:%+本身的并行运行参考文献789(美)%I 0JKJ.:5 4 I/02LKJ6M等著!扬冬青等译!数据库系统概念7N 9!北京-机械工业出版社!&=&7&9黄铠等著!陆鑫达等译!可扩展并行计算技术结构与编程7N 9!北京-机械工业出版社!&=C7A9(美)#J605 LO*P+/5 4等 著!周 傲 英 等 译!数 据 库 原 理编程与性能7N 9!北京-机械工业出版社!&=&87B9李学才等著!计算机系统结构7N 9!西安-西
15、安电子科技大学出版社!8QQ8 R7C9白中英等著!计算机组成原理7N 9!北 京-科 学 出 版 社!8QSS TUC8U科技信息博士V专家论坛名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 4 页 -并行数据库的查询处理技术作者：潘志安作者单位：武汉大学刊名：科技信息（学术版）英文刊名：SCIENCE&TECHNOLOGY INFORMATION年，卷(期)：2006，(6)被引用次数：0次参考文献(5条)1.Abraham Silberschatz.扬冬青 数据库系统概念 20022.黄铠.徐志伟 可扩展并行计算技术、结构与编程 20003.Patrick ONeil.周傲
16、英 数据库原理、编程与性能 20024.李学干 计算机系统结构 19915.白中英 计算机组成原理 1988相似文献(10条)1.期刊论文许新华.谌颃.李春.XU Xin-hua.CHEN Hang.LI Chun 并行数据库的语义查询优化研究:基于Agent-西南师范大学学报（自然科学版）2007,32(4)并行数据库技术中的查询处理及优化方法,都各有优劣;作者提出了一种基于 Multi-Agent技术的语义查询模型(SQMAS),并以此模型为基础建立了一种基于Agent 的并行数据库语义查询方法;同时为了保证系统组内、组间 Agent 之间的高效通信,采用了树型拓扑结构(TTMAS)的通信
17、模型,系统内各 Agent 使用通信原语高效通信、协作,且满足 Agent 间的通信路由最优,从而保证了 SQMAS的查询效率.2.学位论文许新华 基于Agent的并行数据库查询优化2006 本文针对并行数据库的查询优化处理领域，提出了一种基于Multi-Agent技术的语义查询模型(SQMAS)，并以此模型为基础建立了一种基于 Agent 的并行数据库语义查询方法，同时为了保证系统组内、组间Agent 之间的高效通信，建立了树型拓扑结构(TTMAS)的通信模型，系统内各 Agent 使用通信原语高效通信、协作，从而在并行数据库技术的查询优化领域做出了有益的探索和贡献。语义查询优化方法不是简单
18、摒弃传统的查询优化方法，而是采用Multi-Agent技术自动查找与给定查询有关的完整性约束条件，然后，修改给定的查询为更有效的等价查询，使得多个关系间连接操作的效率得到很大的提高，从而达到查询所期望达到的减少连接操作、缩短查询时间的优化效果，实现了基于Agent 的语义查询优化。SQMAS 查询模型基于多 Agent 技术，结构组成中包括查询监测组(QueryDetectGroup)、内核组(KernelGroup)、知识库组和规则集组(KDB&RuleSetGroup)、输出组(ExportGroup)、系统级命名服务 Agent(NameServer-Agent)、辅助通信 Agent(
19、AssCommu-Agent，含组内通信门户 GGA，系统通信门户 MASGA)等功能组和系统Agent；另外，为了保证查找效率，设计了一个基于“黑板”模型的树型拓扑通信模型TTMAS，使用通信原语实现了 SQMAS系统组内 Agent 以及不同组间Agent 的单播、多播、选播、广播通信，且满足Agent 间的通信路由最优，从而保证了 SQMAS的查询效率。3.会议论文玄萍.李建中.李金宝.张兆功 并行数据库多连接查询的新优化算法2004 在基于机群系统的并行数据库中，多连接查询优化是一个重要的研究内容。本文提出了基于遗传算法的并行优化算法BGA，在估算查询执行计划的代价时，考虑了资源的分配
20、信息和网络的通信代价。在资源的分配过程中，充分利用了数据的物理存储分布信息，减小了额外的通信开销。实验结果表明，算法较大地提高了机群系统中多连接查询优化的效率，对提高并行数据库性能起到重要作用。4.学位论文玄萍 并行数据库查询优化的遗传算法2004 查询优化是并行数据库系统的核心技术.目前,查询优化的研究主要围绕着具有多个连接操作的复杂关系数据库查询的优化问题进行.近十几年来,人们对于并行数据库中的多连接查询优化问题,已经进行了广泛的研究.然而,目前在基于机群并行计算环境的多连接查询的优化算法的研究工作还很少.该文重点研究了基于机群并行数据库中关系的存储分布、多连接查询优化和查询处理等关键技术
21、.机群并行计算机系统是并行处理技术的一个重要分支,是进行高性能计算的一个有效途径,必将主宰并行计算技术的发展.该文在借鉴了机群并行数据库系统特点的基础上,提出了关系分布算法、多连接查询优化算法和查询处理方法.在实验部分,通过对基于最小中间结果的贪心算法、基于右深树的启发式算法和该文提出的算法的模拟实验,对比了三种算法的性能.实验结果表明,算法较大的提高了机群系统中多连接查询优化的效率,是解决多连接查询优化的有效途径,对提高并行数据库的性能起到重要作用.5.会议论文周胜.文继荣.王珊 嵌套查询在并行数据库中的实现1998 在并行数据库系统中处理嵌套查询的途径包括TIS 和嵌套化两种方法.本文在分
22、析嵌套查询的基本特点后,着重讨论并行环境下 TIS 算法以及常规连接的实现,并提出并行环境下嵌套查询的关键.6.学位论文吕成 基于遗传算法的并行数据库和数据仓库的查询优化技术研究2005 随着数据库规模的日益增大，使用并行处理能力提高数据库的性能已成为数据库发展的必然趋势，这其中并行数据查询优化是一个重要的研究课题。同时数据仓库技术的出现和分析查询应用的剧增，使得数据库中多连接查询优化(MJQO)的重要性越来越突出。多连接查询优化是一个NP 问题，是提高数据库系统有效性的关键，同时也是数据库领域的一个没有很好解决的问题，面对日渐复杂的查询应用，传统的system-R 优化技术显得更加无能为力。
23、本文的主要内容是采用遗传算法解决并行数据库环境下多连接查询的优化问题。通过对并行多连接查询优化问题的抽象建模，以左深树作为搜索空间，采用有序串编码，设计了适用于 MJQO遗传算法的遗传算子和算法结构，并通过实验讨论了算法的有效性以及各种参数设置的合理性，并针对数据仓库典型查询应用提出了启发式改进方法。最后采用多种群的并行遗传算法思想，基于并行数据库的特有并行结构，对通用MJQO遗传算法进行并行设计，并通过模拟实现伪并行遗传算法实验证明了其对解决 MJQO问题的诸多改进作用。7.期刊论文李建中.LI Jian-Zhong基于多重加权树的并行数据库查询优化方法-计算机学报 1998,21(5)本文
24、提出了一种基于多重加权树的查询优化方法,包括多重加权树并行查询计划模型、并行查询计划的复杂性模型和查询优化算法.该方法能够处理最常用的选择-投影-连接查询,支持多种并行连接算法,包括流水线缓冲区的存储器优化分配算法、数据操作的处理机与存储器优化分配算法和连接操作实现算法的优选算法.该方法已经用于作者设计与实现的并行关系数据库管理系统原型,效果良好.8.学位论文张艳 并行XML 数据库查询处理算法的设计、实现及性能评价2005 本文介绍的是基于分布式对象数据库的并行XML 查询系统，XML 是一种标准化的、可以在 Web 上表示结构化信息的文本格式，它不仅可以表述信息内容，更重要的是可以定义信息
25、结构，揭示了文本内在的语义信息。该系统在单机XML 查询和并行数据库两方面研究基础之上，实现了并行XML 数据库查询功能。在该系统中，提出了一种在并行多处理机环境下，利用分布式对象数据库对XML 进行并行查询的新方法：基于父子关系的并行流水线连接查询方法(PCPPJ)。XML 查询的基础是正则路径表达式(RegularPathExpression)查询，对正则路径表达式的查询可以分解成为各个子路径的查询或子路径上每个结点的查询，然后按照名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 4 页 -相应的规则对查询结果进行合并，得到最终的查询结果。同时，还简单介绍了一下有关的并行数据库
26、XML 文档分片策略和为了提高查询性能而设计的若干种查询索引。最后本文对这种并行 XML 查询方法的测试结果进行分析和说明。实验证明，本文提出的并行数据库环境下XML 查询处理方法有较好的加速比、缩放比和较优的查询响应时间。尤其在长路径和大文档情况下有更好的查询效果。这进一步证明了并行 XML 数据库查询在实际应用中有更好的发展前景。9.学位论文王碧 并行数据库中数据分布和查询处理技术的研究2003 该文分析并比较了各种基于树结构的多维数据分布方法,给出了基于 k-d树结构的分布方法的详细设计方案,指出设计基于传统索引结构的数据分布方法是解决并行数据库系统数据分布问题的一种较好方式.该方法在构
27、造树的过程中,完成了对数据空间的划分和数据超方体的放置,不仅可以使各个处理机能够合理得分配工作负载,而且可以方便地利用索引执行查询处理操作,提高了系统的效率.如何将并行数据库系统应用于局域网络环境,并实现查询处理及优化也是该文研究的工作之一.该文采用了基于工作站网络的数据库的并行查询处理设计思想,在传统的串行数据库基础之上加入了并行化的设计方案,通过开发关系数据库的三个固有并行性来提高系统执行查询处理的能力.在此基础上,该文提出了一种并行查询处理的结构,并根据该结构在局域网络环境下设计和实现了并行查询处理的模拟系统.通过对实验结果的分析与比较,证明了合理的并行化设计可以减少通信带来的开销,获得较好的性能.10.期刊论文厉阳春.LI Yang-chun基于线性浓密树的并行数据库查询优化算法-湖南理工学院学报（自然科学版）2006,19(1)查询优化是并行数据库的核心技术.基于线性浓密树的查询优化方法是对基于浓密树(Bushy-Tree)查询优化方法的一种改进.这种优化方法大大地缩减了查询执行计划空间,确保了并行查询执行计划的优化性.本文链接：http:/ 年12月12日名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 4 页 -