分布式数据库查询优化技术

分布式数据库查询优化技术摘要在分布式数据库中，由于高可靠性和高速度性是其重要特点，所以对查询执行的要求也就更高。而查询执行中查询优化是执行的关键环节，查询优化在很大程度上决定查询的效率或快慢。本文讨论的重点是对分布式查询执行的全局处理策略进行优化，尽可能避免通信代价的开销，并着眼于查询执行的实际代价，从分布式系统中选出一个最优的执行节点。从查询执行的效果出发，通过统计的方式，不断从最近的查询执行代价学习纠正最近查询执行的统计代价，为查询的全局处理提供参考，以达到优化执行、提高执行效率和速度的目的。1分布式数据库概述1.1分布式数据库的定义所谓分布式数据库系统就是由分布于多个计算机结点上的若干个数据库组成,每个子数据库系统都是一个独立的数据库系统，它们都拥有各自的数据库、中央处理机、终端，以及各自的局部数据库管理系统，分布式数据库在使用上可视为一个完整的数据库,而实际上它是分布在地理分散的各个结点上。当然,分布在各个结点上的子数据库在逻辑上是相关的。简单的说，分布式数据库系统是一系列集中式数据库系统的联合。它们在逻辑上属于同一系统，但在物理结构上是分布式的[1]。1.2分布式数据库系统的组成如图1-1所示，分布式数据库系统由以下述成分组成:(1)多台计算机设备，并由计算机网络连接。(2)计算机网络设备，网络通讯的一组软件。(3)分布式数据库管理系统，它包括GDBMS、LDBMS、CM,除了具有全局用户接口由GDBMS连接外，还可以具有自治场地用户接口，由场地DBMS链接，并持有独立的场地目录。(4)分布式数据库管理者（DDB），包括全局数据库(GDB)和局部数据库(LDB)以及自制场地的自治场地数据库。(5)分布式数据库管理者(DDBA)，它可分为二级，一级为全局数据库管理者(GDBA),另一级问局部或自治场地数据库管理者，统称为局部数据库管理者(LDBA)。(6)分布式数据库系统软件文档，这是一组与软件相匹配的软件文档及系统各种使用说明和文件。图1-1分布式数据库系统的结构1.3分布式数据库系统的功能通常的集中式数据库管理系统应具备以下几个基本的功能[2]:(1)数据库定义功能;(2)数据存取功能;(3)数据库运行管理;(4)数据库的建立和维护功能。分布式数据库除了须具备以上集中式数据库的功能外，一般还须具有以下几个方面的功能:(1)分布在网络中的各节点的数据库，其物理位置对用户透明;在用户眼里见到的只是整个系统中有哪些数据库，无论是本地还是远程数据库，用户操纵某一数据库就像操纵本地数据库一样。(2)处于网络中的各数据库共享的数据应保证一致性:CommunicationNetworkS4S1S2S3当用户操纵(查询、更新、删除等)某一数据库时，整个网络中的各节点如果有该数据库的副本或备份数据库，应进行相应的更新操作，以保持数据一致性。(3)系统的可靠性应比集中式数据库系统的可靠性更高:如果因为某种原因，使系统中某一节点数据库崩溃，系统会自动选择另一具有该数据库的节点继续提供原来的服务。(4)支持多用户的并行访问，或者操作的并行性;(5)数据的安全性和完整性比集中式数据库要求更高;由于分布式数据库系统中各节点数据库处于网络环境中，数据受到破坏和窃取以及丢失的可能性大大增加。2数据库查询优化技术2.1查询优化技术数据库系统研究的主要目标是尽可能的对用户隐藏数据结构的细节，使数据库系统的应用更能面向各个领域。同样，分布式数据库研究的主要目标之一是隐藏分布式环境的细节，使系统用起来更加简单、有效[3]。关系数据模型可以为集中式数据库提供一个数据无关的接口关系数据库语言是关系演算，使用该语言进行数据查询时，只需对要查询的数据进行简单的描述，而无须说明如何获取这些数据，SQL语言就是其中之一。但是，使用这种语言，也要对搜索、存取操作以及数据传输过程进行说明，因此，相应的查询优化技术的研究和发展也在不断进行。所谓查询优化，就是要保证查询总开销和总时间为最小。查询优化器的主要任务是控制和加快查询的执行和数据的传输过程。查询优化器(如图2-1)首先以查询的某种表示作为输入，这种表示是查询处理器的语法分析子模块的输出，查询优化器为查询选择一种适当的数据存取策略。然而，查询优化一直是个复杂的问题，理想的全面的查询优化几乎是不可能的，许多专家和学者在这一领域曾做出过不少的研究和探讨，但总的说来，不尽人意，往往只能达到局部目标的查询优化效果，甚至有些理论并不适用。图2-1查询优化处理查询优化的基本类型通常包括两类:针对查询执行代价的优化和针对查询响应时间的优化。针对查询执行代价进行优化的目标是，使查询执行所使用的系统资源(总和)尽量地少，从而降低系统开销，整个系统的开销可以从单个系统资源的开销表达式中推出。针对查询响应时间优化的目标是尽量减少查询的响应时间，而不计较系统资源的耗费。2.2分布式数据库优化设计分析在分布式数据库系统中，一方面，许多相对独立的处理器可能参与数据库操作。分布式数据库可能提供若干机会[3]：1)由于在处理一个问题时可以使用多台机器，并行以及加快查询反应速度的可能性增大。2)由于数据可以在多个节点上存在副本，系统可能不会仅仅由于一个节点或部件发生故障而不得不停止处理。另一方面，分布式处理增加了分布式系统各个方面的复杂性，因此即使是DBMS中最基本的组成部分的设计，也得重新考虑。在许多分布式环境中，通信开销可能远大于处理开销，因此的问题是消息如何传送。比如分布式提交和分布式封锁。查找空间生成等价的QEP转化规则输入查询代价模型查找策略查询重写优化的逻辑查询计划(bestQEP)查询组合全局模式在分布关系上的代数查询数据本地化分片模式在分布关系上的查询计算控制节影响通信开销的因素主要是由于带宽开销迅速减小。某些类型的数据属于电子方式管理的大对象，因此即使在通信开销较小时，以太字节的数据传输开销也是不能忽视的。此外，通信开销常常不仅仅涉及数据传送，还有为数据传送做准备的各层协议、在接受方重建数据以及通信的管理。这些协议各自都需要大量的计算。尽管计算开销也在减小，与数据与关键数据库操作的传统单处理器操作相比，进行通信所需的计算可能仍不能忽视。分布式数据库查询处理如图2-5，分布特性的存在除带来通信开销外还影响到物理查询计划设计的复杂性和可选方案。在选择物理查询计划时必须考虑的问题包括：如果某个所需关系R有多个副本，那么应该从那个副本中获得R的值。当在两个关系R和S上实施某个操作例如连接时，有多个可选方案而且必须选择其中之一时，一些可能的选项如下：a)可以将S复制到R所在节点，并在该节点执行计算。b)可以将R复制到S所在节点，并在该节点执行计算。c)可以将R和S复制到二者各自所在节点之外的第三个节点，并在该节点执行计算。哪种选择最好，这依赖于多个因素，其中包括哪个节点上有可用的处理时间以及操作结果是否需要与第三个结点上的数据相结合等。如果关系R有分布在若干节点上的片断nRRR,...,,21,构成，那么在选择逻辑查询计划时，还应该考虑用n21...RRR替代查询中使用的R，替代后的查询或许能很大程度的简化表达式。3)对局域网来说，通讯代价有着跟数据库的磁盘I/O代价相比拟的重要性。网络通信代价会随着用户数或负载的变化而改变，所以网络情况变化的随机性对分布式查询处理来说，更应该考虑通信代价。但当某个数据库的查询负载过高时，需要牺牲一定的通讯代价来提高执行的并行度。此外局域网络的广播能力可以用于全局优化更新、收集信息。图2-5分布式查询处理的通用层级方案3分布式数据库查询优化技术研究3.1基于分布式数据库分布特点的优化分布式并行系统处于网络中，处于网络中的各个节点具有单个服务器系统所没有的特性，所要考虑的因素和重点也将有所不同。分布式系统中数据的分布性和操作的并行性。所以既要利用分布并行特点来加快查询执行速度，又要尽量减少分布并行所带来的网络通信延迟代价[3]。3.1.1系统环境和约束条件及设计目标(1)设计目标与系统环境本分布式数据库管理系统是针对局域网环境，分布式数据库是指分布于局域网络，而非广域网络，分布粒度为库一级，并且基于Mysql开源数据库来设计。目的是尽量避免数据库分布给查询执行带来的通信开销。(2)约束条件在此前提下，须考虑以下一些约束因素:1.通信代价分布式数据库不同于集中式数据库，所以通信代价不得不考虑；但同时它又没有广域网环境中的分布式数据库的通信开销那么大。所以既不能只考虑磁盘输入输出I/O和CPU计算代价的开销，也不能只考虑通信代价的开销，通过参考权威文献和对单机查询代价与数据通信代价的试验分析，二者都应考虑，且同时并重。由于是库级分布，不是表级分布，所以跨表操作始终只会在一个节点中进行处理。而跨库操作，目前Mysql数据库系统还不支持此种操作。因此，不存在查询时的服务器节点之间通信，因而省去对查询执行时通信代价的考虑。但是，当处理来自本节点没有的数据库时，就有可能了。在这种情况，传统的方式转发查询命令到其它节点上执行，这就要考虑通信代价的额外开销了2.查询分解由于是库级分布，某个数据库在某个节点存在，那么这个数据库的所有表都在这个节点上存在(主本或副本)，所以不考虑查询分解。3.透明访问。用户访问本分布式数据库系统感觉不到数据库物理位置位于何处，就像访问本地数据库(或集中式数据库)一样。4.Mysql不支持的特性Mysql不支持视图、子查询、存储过程和触发器、外键。(3)优化目标强调查询快捷，着眼于查询时间的开销;注重整体查询(整个分布式局域网系统和多路多线程的总体查询)效率和吞吐率，而非单机或具体某一条查询语句的执行效率。系统合理假设主要针对上层进行优化，而不针对下层，并假定已对查询语句进行了优化。因此，要考虑的关键问题便落在通信代价上，而其它磁盘输入输出I/O和CPU计算代价的开销，是由下层查询优化去处理。3.1.2优化策略研究与设计下面对启发式查询路径选择的优化策略进行详细探讨和设计。(1)基本思想根据最近一段时间的查询代价，推断局域网络中分布式数据库各节点当前的查询处理能力，实质上还是根据资源占用状况来选择一台较优的节点去执行查询处理。在实现策略上，属于不断学习优化的过程。基于一条基本思想:最近访问的表格，在最近一段时间内，仍处于同一状态(忙)，即很可能被再次访问。假如这种判断出现错误，也会仅仅因为一次的查询操作，而只误导一次，在下一次同样的查询，又会转入正确的优化判断。这样的“误判”，仅仅造成一次慢速的查询，不会有太大的损失。优化的另一策略是尽量避免通信代价的开销，使一个查询尽量不经过查询中转，避免查询结果数据的通信。(2)优化设计1.节点代价信息表为了记录上次访问表的查询代价，及其通信代价，需要设计以下一些表格如表3-1，以记录如下一些上次访问的历史信息：说明：(此处的通信代价不是指一次查询的所有数据的通信代价，是单位数据在当时的通信代价)节点IP：指示局域网中分布式数据库所在的节点的IP地址数据库：指该节点中存在有哪些数据库关系表：指该数据库中存在有哪些表用户数：指该表中当时有几个用户查询的计数为使各节点便于查询，该表存在于局域网中每一个节点中，而且为了提高查询速度，更快的执行优化选择，该表必须常驻内存。表中记录信息随时更新。全局查询代价由Mysql数据库系统本身的THD结构获得。某个表的用户计数是通过查询时锁表机制而获得。值得说明的是为什么不能采用共享数据结构方式?如果分布式网络中各节点共享一张表，表面上看起来，可以节省存储分配，维护单一;实际上，由于该表访问比较频繁，特别是查询用户量增大的时候更是如此，而为了保证数据的一致性，各节点必须互斥访问该表，无论采用锁机制，还是简单的互斥信号量，都会造成访问因竞争而等待，致使服务器处理性能大为降低。因此，它是不符合分布式系统设计思想的。2.代价的估算1)操纵单表的查询语句表3-1代价信息统计表节点IP数据库DB关系表table全局查询代价cost该表的负载数count...............一个分布式数据库查询的执行，包括全局处