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

《分布式大数据库查询优化技术》由会员分享，可在线阅读，更多相关《分布式大数据库查询优化技术（8页珍藏版）》请在装配图网上搜索。

1、分布式数据库查询优化技术摘 要在分布式数据库中，由于高可靠性和高速度性是其重要特点，所以对查询执行的要求也就更高。而查 询执行中查询优化是执行的关键环节，查询优化在很大程度上决定查询的效率或快慢。本文讨论的重点是 对分布式查询执行的全局处理策略进展优化，尽可能防止通信代价的开销，并着眼于查询执行的实际代价， 从分布式系统中选出一个最优的执行节点。从查询执行的效果出发，通过统计的方式，不断从最近的查询 执行代价学习纠正最近查询执行的统计代价，为查询的全局处理提供参考，以达到优化执行、提高执行效 率和速度的目的。1 分布式数据库概述 件。SSmunicationNetworkSS1.1 分布式数据

2、库的定义所谓分布式数据库系统就是由分布于多个计 算机结点上的假设干个数据库组成 , 每个子数据 库系统都是一个独立的数据库系统，它们都拥有各 自的数据库、中央处理机、终端，以与各自的局部 数据库管理系统，分布式数据库在使用上可视为一 个完整的数据库,而实际上它是分布在地理分散的 各个结点上。当然,分布在各个结点上的子数据库 在逻辑上是相关的。简单的说，分布式数据库系统 是一系列集中式数据库系统的联合。它们在逻辑上 属于同一系统，但在物理结构上是分布式的1。1.2 分布式数据库系统的组成如图 1-1 所示，分布式数据库系统由以下述成 分组成:(1) 多台计算机设备，并由计算机网络连接。(2) 计

3、算机网络设备，网络通讯的一组软件。(3) 分布式数据库管理系统，它包括 GDBMS、 LDBMS、CM，除了具有全局用户接口由GDBMS连接外， 还可以具有自治场地用户接口，由场地DBMS，并持 有独立的场地目录。(4) 分布式数据库管理者DDB，包括全局数 据库(GDB)和局部数据库(LDB)以与自制场地的自 治场地数据库。(5) 分布式数据库管理者(DDBA)，它可分为二 级，一级为全局数据库管理者(GDBA)，另一级问局 部或自治场地数据库管理者，统称为局部数据库管 理者(LDBA)。(6) 分布式数据库系统软件文档，这是一组与 软件相匹配的软件文档与系统各种使用说明和文图 1-1 分布

4、式数据库系统的结构1.3 分布式数据库系统的功能通常的集中式数据库管理系统应具备以下几 个根本的功能2:(1) 数据库定义功能;(2) 数据存取功能;(3) 数据库运行管理;(4) 数据库的建立和维护功能。分布式数据库除了须具备以上集中式数据库的功能外，一般还须具有以下几个方面的功能:(1) 分布在网络中的各节点的数据库，其物理 位置对用户透明;在用户眼里见到的只是整个系统中有哪些数 据库，无论是本地还是远程数据库，用户操纵某一 数据库就像操纵本地数据库一样。(2) 处于网络中的各数据库共享的数据应保证 一致性:当用户操纵（查询、更新、删除等）某一数据库 时，整个网络中的各节点如果有该数据库的

5、副本或 备份数据库，应进展相应的更新操作，以保持数据 一致性。（3）系统的可靠性应比集中式数据库系统的可 靠性更高:如果因为某种原因，使系统中某一节点数据 库崩溃，系统会自动选择另一具有该数据库的节点 继续提供原来的服务。（4）支持多用户的并行访问，或者操作的并行 性;（5）数据的安全性和完整性比集中式数据库要 求更高;由于分布式数据库系统中各节点数据库处于 网络环境中，数据受到破坏和窃取以与丢失的可能 性大大增加。2 数据库查询优化技术总的说来，不尽人意，往往只能达到局部目标的查 询优化效果，甚至有些理论并不适用。输入查询等价的QEP查找策略代价模型）ZZZ查询重写优化的逻辑查询计划（bes

6、t QEP）图2-1查询优化处理2.1 查询优化技术查询优化的根本类型通常包括两类 :针对查询执行在分布关数据库系统研究的主要目标是尽可能的对用户隐 藏数据结构的细节，使数据库系统的应用更能面向 各个领域。同样，分布式数据库研究的主要目标之 一是隐藏分布式环境的细节，使系统用起来更加简 单、有效3。关系数据模型可以为集中式数据库提供一个 数据无关的接口关系数据库语言是关系演算，使用 该语言进展数据查询时，只需对要查询的数据进展 简单的描述，而无须说明如何获取这些数据， SQL 语言就是其中之一。但是，使用这种语言，也要对 搜索、存取操作以与数据传输过程进展说明，因此， 相应的查询优化技术的研究

7、和开展也在不断进展。所谓查询优化，就是要保证查询总开销和总时 间为最小。查询优化器的主要任务是控制和加快查 询的执行和数据的传输过程。查询优化器（如图 2-1）首先以查询的某 种表 示作为输入，这种表示是查询处理器的语法分析子 模块的输出，查询优化器为查询选择一种适当的数 据存取策略。然而，查询优化一直是个复杂的问题， 理想的全面的查询优化几乎是不可能的，许多专家 和学者在这一领域曾做出过不少的研究和探讨，但代价的优化和针对查询响应时间的优化。针对查询 执行代价进展优化的目标是，使查询执行所使用的 系统资源（总和）尽量地少，从而降低系统开销，整 个系统的开销可以从单个系统资源的开销表达式 中推

8、出。针对查询响应时间优化的目标是尽量减少 查询的响应时间，而不计较系统资源的消耗。2.2 分布式数据库优化设计分析在分布式数据库系统中，一方面，许多相对独 立的处理器可能参与数据库操作。分布式数据库可 能提供假设干机会3：1）由于在处理一个问题时可以使用多台机器， 并行以与加快查询反响速度的可能性增大。2）由于数据可以在多个节点上存在副本，系统 可能不会仅仅由于一个节点或部件发生故障而不 得不停止处理。在分布另一方面，分布式处理增加了分布式系统各个 方面的复杂性，因此即使是 DBMS 中最根本的组成 局部的设计，也得重新考虑。在许多分布式环境中， 通信开销可能远大于处理开销，因此的问题是消息

9、如何传送。比如分布式提交和分布式封锁。图2-5分布式查询处理的通用层级方案3 分布式数据库查询优化技术研究3.1 基于分布式数据库分布特点的优化分布式并行系统处于网络中,处于网络中的各 个节点具有单个服务器系统所没有的特性,所要考 虑的因素和重点也将有所不同。分布式系统中数据 的分布性和操作的并行性。所以既要利用分布并行 特点来加快查询执行速度,又要尽量减少分布并行 所带来的网络通信延迟代价3。3.1.1 系统环境和约束条件与设计目标(1) 设计目标与系统环境本分布式数据库管理系统是针对局域网环境, 分布式数据库是指分布于局域网络,而非广域网 络，分布粒度为库一级，并且基于Mysql开源数据

10、库来设计。目的是尽量防止数据库分布给查询执行 带来的通信开销。(2) 约束条件 在此前提下，须考虑以下一些约束因素:影响通信开销的因素主要是由于带宽开销迅 速减小。某些类型的数据属于电子方式管理的大对 象，因此即使在通信开销较小时，以太字节的数据 传输开销也是不能无视的。此外，通信开销常常不 仅仅涉与数据传送，还有为数据传送做准备的各层 协议、在承受方重建数据以与通信的管理。这些协 议各自都需要大量的计算。尽管计算开销也在减 小，与数据与关键数据库操作的传统单处理器操作 相比，进展通信所需的计算可能仍不能无视。分布式数据库查询处理如图 2-5，分布特性的 存在除带来通信开销外还影响到物理查询计

11、划设 计的复杂性和可选方案。在选择物理查询计划时必 须考虑的问题包括：如果某个所需关系 R 有多个副本，那么应该从 那个副本中获得 R 的值。当在两个关系R和S上实施某个操作例如连接 时，有多个可选方案而且必须选择其中之一时，一 些可能的选项如下：a) 可以将S复制到R所在节点,并在该节点执 行计算。b) 可以将R复制到S所在节点,并在该节点执 行计算。c) 可以将R和S复制到二者各自所在节点之外 的第三个节点，并在该节点执行计算。哪种选择最好，这依赖于多个因素，其中包括 哪个节点上有可用的处理时间以与操作结果是否 需要与第三个结点上的数据相结合等。 如果关系 R 有分布在假设干节点上的片断

12、R , R ,., R12 n ,构成，那么在选择逻辑查询计划时，还应该考虑用R u R u.u R1 2 n替代查询中使用的R,替代后的查询或许能很大程 度的简化表达式。3) 对局域网来说,通讯代价有着跟数据库的磁 盘 I/O 代价相比拟的重要性。网络通信代价会随着 用户数或负载的变化而改变,所以网络情况变化的 随机性对分布式查询处理来说,更应该考虑通信代 价。但当某个数据库的查询负载过高时,需要牺牲 一定的通讯代价来提高执行的并行度。此外局域网 络的广播能力可以用于全局优化更新、收集信息。分布式数据库不同于集中式数据库，所以通信代价不得不考虑；但同时它又没有广域网环境中的 分布式数据库的通

13、信开销那么大。所以既不能只考 虑磁盘输入输出I/O和CPU计算代价的开销，也不 能只考虑通信代价的开销，通过参考权威文献和对 单机查询代价与数据通信代价的试验分析，二者都 应考虑，且同时并重。由于是库级分布，不是表级分布，所以跨表操 作始终只会在一个节点中进展处理。而跨库操作， 目前 Mysql 数据库系统还不支持此种操作。因此， 不存在查询时的服务器节点之间通信，因而省去对 查询执行时通信代价的考虑。但是，当处理来自本 节点没有的数据库时，就有可能了。在这种情况， 传统的方式转发查询命令到其它节点上执行，这就 要考虑通信代价的额外开销了由于是库级分布，某个数据库在某个节点存 在，那么这个数据

14、库的所有表都在这个节点上存在 中分布式数据库各节点当前的查询处理能力，实质 上还是根据资源占用状况来选择一台较优的节点 去执行查询处理。在实现策略上，属于不断学习优化的过程。基 于一条根本思想:最近访问的表格，在最近一段时 间内，仍处于同一状态（忙），即很可能被再次访问。 假设这种判断出现错误，也会仅仅因为一次的查询 操作，而只误导一次，在下一次同样的查询，又会 转入正确的优化判断。这样的“误判，仅仅造成 一次慢速的查询，不会有太大的损失。优化的另一策略是尽量防止通信代价的开销， 使一个查询尽量不经过查询中转，防止查询结果数 据的通信。（2）优化设计为了记录上次访问表的查询代价，与其通信代 价

15、，需要设计以下一些表格如表 3-1，以记录如下表 3-1 代价信息统计表节点IP数据库DB关系表t able全局查询代价cost该表的负载数count（主本或副本），所以不考虑查询分解。3.透明访问。用户访问本分布式数据库系统感觉不到数据 库物理位置位于何处，就像访问本地数据库 （或集 中式数据库）一样。Mysql 不支持视图、子查询、存储过程和触发 器、外键。（3）优化目标 强调查询快捷，着眼于查询时间的开销;注重 整体查询（整个分布式局域网系统和多路多线程的 总体查询）效率和吞吐率，而非单机或具体某一条 查询语句的执行效率。系统合理假设 主要针对上层进展优化，而不针对下层，并假 定已对查询

16、语句进展了优化。因此，要考虑的关键 问题便落在通信代价上，而其它磁盘输入输出 I/O 和CPU计算代价的开销,是由下层查询优化去处理。3.1.2 优化策略研究与设计 下面对启发式查询路径选择的优化策略进展 详细探讨和设计。（1）根本思想根据最近一段时间的查询代价，推断局域网络 一些上次访问的历史信息： 说明：（此处的通信代价不是指一次查询的所有数 据的通信代价，是单位数据在当时的通信代价）节点IP:指示局域网中分布式数据库所在的 节点的 IP 地址数据库:指该节点中存在有哪些数据库关系表:指该数据库中存在有哪些表 用户数:指该表中当时有几个用户查询的计数 为使各节点便于查询，该表存在于局域网中

17、每 一个节点中，而且为了提高查询速度，更快的执行 优化选择，该表必须常驻内存。表中记录信息随时 更新。全局查询代价由Mysq I数据库系统本身的THD 结构获得。某个表的用户计数是通过查询时锁表机 制而获得。值得说明的是为什么不能采用共享数据结构 方式?如果分布式网络中各节点共享一 X 表，外表 上看起来，可以节省存储分配，维护单一;实际上， 由于该表访问比拟频繁，特别是查询用户量增大的 时候更是如此，而为了保证数据的一致性，各节点 必须互斥访问该表，无论采用锁机制，还是简单的 互斥信号量，都会造成访问因竞争而等待，致使服 务器处理性能大为降低。因此，它是不符合分布式 系统设计思想的。1）操纵

18、单表的查询语句一个分布式数据库查询的执行，包括全局处理 和本地处理两个阶段，相应的查询代价也包括全局 处理代价和局部处理代价两局部，撇开CPU的开销， 可以一个公式近似简化为：全局查询代价二通信代价+本地执行代价 但基于前面的考虑，不计通信代价，所以只有本地 执行代价。本地执行代价=CPU计算时间+1/0等待时间 由于CPU计算时间相对很小，可以忽略，执行代价 近似等于I/O等待时间。实现中，统计的代价为：本地执行时间cost =I/O 数据量可以粗略的以一个表的所有元组数计。2）操纵多表的查询语句需要注意的是，如果一条查询语句需要操纵不 只一个数据库的一个表时，到底以哪个表的代价为 准，或者

19、都考虑但多个表之间考虑的偏重程度可能 不一样，并不平均对待。所以衡量多个表操纵的查 询代价，不能简单的将多个表代价相加之和作为该 查询语句的代价。统计操纵多表的查询语句的代价 时，很难将总体代价定位在各个表上，一些繁琐的 算法既费时，又不准确，所以，基于实际应用上的 考虑，略去本次查询的代价统计，而只统计单表操 作的代价。多表属于同一数据库（对库级分布，一定位于 同一结点上），理论上，任选其中一个表的代价来 衡量，但在实际操作中，为了减少单个表带来的偶 然误判，采用累加和。多表不属于同一数据库（不一定位于同一结点 上），此种情况，当然不能像上面一样，任选一个 表的代价去衡量，也不能将各表的代价

20、累加之和作 为痕量的代价。只能根据哪个表的操作代价高来决 定执行节点。但对库级分布的数据库不支持多表不 属于一个数据库的情况。这里讨论的负载主要指用户数量，以表作资源 对象，用在某个表上的等待的线程（用户数）来度量 负载。计数策略:由于多个查询可能操纵同一表，为 保证数据的一致性，本分布式数据库系统提供了互 斥锁（读锁和写锁）机制。当一个操纵某个表的查询 请求到来时，就将count计数作加1操作，当该表 的一个操作完毕;当解锁一次，就将count计数作 减I操作。然后定期更新此。ount计数。为此，需 要在THD的结构里定义一个变量以保存该计数值。对代价的统计，取一定时间内，每次查询的代 价的

21、平均值。这里的一定时间即为统计周期，也是 更新周期。同样，将每次查询的代价记入THD结构 里，也将代价的平均值保存到THD结构里。以便全 局优化器能方便获取所需信息。采用动态更新，即服务器一启动便开始统计， 在服务器运行过程中周期性更新。所以全局代价表 从无到有，逐渐增多，随着时间的推移，使查询优 化信息越来越完善，越来越准确。另外，如果本次 查询的表在全局代价表里尚未存在记录，如此该次 查询代价立即记入全局代价表中，以被后来的查询 参考。不必等到一定周期的统计。某一次的统计可能不是准确的，但屡次大量的 统计，正确率总是符合正态分布的，从统计学的角 度讲，是正确的、实用的。另外，为了使统计更为

22、真实和有效，本设计对 一些很少出现的一些语句抛弃掉，不予统计。比如 像 CREATE DATABASE, DROP DATABASE, CREATE TABLEDROP TABLE, ALTER TABLE, CREATE INDEX, DROP INDEX，等只有再创建数据库时，才会用到的 一些命令语句;还有一些显示数据库与其分布信息 的查询命令，以与全局视图查询命令，由于较少使 用或不涉与具体操纵哪个表，也不予统计其代价信 息，如 SHOW DATABASE, SHOW TABLES, SHOW GLOBALDBS，SHOW IPSBYDB 等。周期如何确定呢?周期过短可能造成统计的平 均

23、值不真实;但周期过长，有可能不能反响当时或 最近的服务器节点的处理情况。所以周期既不能过 长也不能过短，如何确定一个适宜的周期呢?首先， 这个周期不能是固定不变的，因为网络情况不是固 定不变的，它会随着服务器节点负载而变化，而服 务器节点的负载情况完全是随机的，随着用户数量 的变化而变化。因此，为了适应变化多端的网络环 境与节点资源负载情况，这里使用一种动态策略， 以更准确更与时地反响服务器的处理能力。从实际情况出发，如果前后几次波动很大，超过一定的值，说明负载变化很频繁，这时，需要缩 短统计周期;反之，可以加长统计周期。但为了防 止变化过于平凡，造成“抖动现象，一次不能偏 离初始值过大。怎样

24、确定偏离多大呢 ?可以以本次估计的代价，与上次代价估计的偏离程度来作调整。当I本次估价代价-上次估计代价I上次估计代价 P% 时,下次统计周期=本次统计周期（1+I本次估价代价-上次估价代价I.上次估价代价这里的P根据服务器运行情况，可以由系统管理员确定。同样，当I本次估价代价-上次估价代价I上次估计代价 P% 时,下次统计周期=本次统计周期（1-I本次估价代价-上次估价代价I.上次估价代价说明，如果本次统计代价与上次统计相比波动 较大，偏离程度超过P%，周期变长；反之，周期缩 短。初始值可以由系统管理员更改，默认为每 30 秒更新一次。为了保证优化信息的全局一致性，必须将各节 点本地的最新统

25、计的优化信息告知分布式系统中 其它节点，使得对任何一个节点来，从理论上说， 在当前的优化条件下，均会作出同样的选择（某个 优化节点）。由于本文讨论的分布式数据库系统是存在于 局域网络中，其可靠性和速度比拟高，所以本文采 用类似于选路信息协议（RIP）中路由信息在路由器 间更新的策略，即广播策略。它防止了设定一X全 局唯一的代价信息表，它属于共享资源，必须互斥 访问，需要使用互斥锁机制才能实现。广播周期:为了防止广播风暴，不能频繁的广 播消息，但是广播周期过于长，又会使全局优化信 息得不到与时更新。设定一个阀值，当改变超过某 一阀值时，才广播更新消息。1）关于数据库表的索引如果为数据库的表创建了

26、索引，如此在查询执 行时的磁盘输入输出操作会与没有创建索引的表 的代价低很多，因为查询时的扫描表分为两种:一 种是表一扫描;另一种为索引一扫描。由于索引扫 描时，能很快定位所需记录（元组数）所在磁盘块的 位置，所以比将整X表的记录都读入内存来查询比 拟效率要高得多。但创建了索引的表的列较少，大 多数表的大多数列没有创建索引。而且对同一个 表，每一次查询统计均是以一样的方式统计，所以 并不造成影响。对一些很少使用或者查询不涉与具体哪个表 的简单操作，不予统计其代价信息，以尽量减少或 防止统计数据的不真实性。2） CPU计算代价由于在查询执行中，CPU计算时间，比起磁盘输入输出和通信代价来说很小，

27、在通常的优化器设 计中，大都忽略不计，本优化也不予考虑。假设某一刻，同时有多个用户查询请求访问同 一表，并且是除插入、删除等更新操作以外的操作 （非更新操作），将查询命令分发出去并行处理。尽管单从代价来考虑，可能某一个服务器节点 当前是最优选择的节点，但如果同一时刻（或某一 段较小时间内）有多个客户请求到达，都要查询某 个数据库的某个表，即竞争到同一 X表上，必然形 成等待队列。如果这些查询不都是更新性表操作， 即非更新性操作是可并行化处理的，可以将非更新 性操作分发到其它客户数较少的节点上去处理。如果同一查询语句操纵多个表，遇到此种情 况，优化选择时就排除该表不计算其代价。本表常驻内存，所以

28、其存储组织不能有较大的 浪费。如果采用链表方式存储，表大小可以随时增 加或减少，内存可以随时申请和释放，得到充分利 用，但是，查找速度较慢。另一方面，由于提高查 询速度和查询效率是本优化设计的目的，所以如何 组织存储结构才能提高查找性能（速度），是首要考 虑的问题，所以使用数组存储方式就不太适宜。而 顺序存储方式比链表检索速度快，而且恰当的利用 索引可以更高的提高查找速度。但由于不能事先预 知该表信息的大小，而且可能动态改变，怎样解决 数组固定大小的问题呢?由于此种变化并不频繁， 可以使用 new 操作重新分配改变大小后的内存空 间，并将原数据拷贝过去。而且对于本表来说，采用索引顺序存储方式，

29、比起完全不采用索引的顺序存储方式或链表存储 方式来说，防止了较大的不必要的数据重复存储， 如表的前两项“数据库名和“表名无须重复存 储。PohllS TiUft-nhl.?Tabled Mei+I Tzbel+2CiM-tOCounlOTK.16B.D.167血卄Counit152.1(30.0:Ccxuntx192.16B.D.161g祐1&2.166167Qyjnll192.1SBD.16a:n iti：y132 16B0 ffiSC&uniOCtestll畑nil12.160.0.170-:CofjntE12.188fl181CwtFgnO*iK.ieeoiKi1&2.16B0J66伽a

30、w1921E9g耳jountIP存储结构采用索引顺序表组织，分两级索引， 如图3-1所示：分布式系统中其它节点的广播信息，根据需要，临 时申请存储分配。这样，表的大小可以不一次性分 配完，可以由小到大，随着表信息的不断增加而增 大。1）操作a）索引查找才能实现对上述索引顺序表的操纵，设计怎样 的数据结构才能达到索引的目的？要索引某一项， 需要知道被索引的表的地址，即索引表存放在哪个 内存地址段中，可以用一个全局变量来记录；然后 才能定位某级索引的相对位置（即地址偏移），以与 该级索引所覆盖的X围，即长度。数据库名标志状态地址位置长度对第一级索引（数据库索引）：表名标志状态地址位置长度表大小统计

31、代价统计次数图3-1代价信息的索引顺序表存储结构对第二级索引（表索引）:第一级索引为数据库名，按数据库名的字母顺 序有序排列；再按照数据库分成多个二级索引，即 表索引，按表名的字母顺序有序排列。然后根据表 来查找查询所要操纵的表相应的代价与客户计数 与所在节点的IP等优化信息。由于整个系统中不 同的数据库表和节点IP的数量并不太大，所以 按照两级索引来查找顺序代价表，很快便能找到优 化的表处理节点（IP ）。图中右半局部为顺序表， 按表的第一项（代价cost）有序排列。关于索引顺序表的大小确实定：由于本表常驻 内存，所以存储空间的分配不能又较大的浪费。所 以为了充分利用存储空间，有两种分配方案

32、：一种 分配方案是，采用静态数组，但需要预先确定数组 大小。在分配顺序表时，要预先确定表与索引的大 小。如果是系统中第一个节点初始启动，可以在系 统初启时，从Des Mysql底层预先获得数据库各 数据库的表与节点的数目，然后再分配存储空间并 初始化各项数据，其中，表中的所有代价初始化为 0（系统初启时，没有任何负载，所以这也是合理 的）。如果不是系统中的第一个节点初始启动，只 将本节点的所有数据库的所有表设为0,而将其它 节点的数据库的表的代价暂定为无穷大；在未来的 一段时间内，可以通过别的节点对全局优化信息表 的广播信息获取来得到更新。另一种分配方案是， 采用顺序表的动态存储分配，在系统启

33、动后，通过对顺序代价表:代价信息标志状态说明:对第一 二级索引中增加的“标志位， 指的是表（库）的当前状态：1表示该表（库）存在且 可用；0表示该表（库）当前不可用；其中二级索引 中新增加的“统计代价，是指在更新周期内的统 计代价，它只作临时记录用，不作优化信息用，等 到周期一到，才决定是否将其代价值加到代价Cost 列上。二级索引中新增加的“表大小，是指表的 每条记录的大小与记录数数的乘积；新增加“统计 次数记录该表的被统计的次数。同样，对顺序表 的“标志位，1表示该代价信息可用；0表示该代 价信息不可用。顺序代价表的“代价信息，指的 是上图中所列的代价Cost、客户计数Count和节点 I

34、P等信息。注释:为什么要将“统计代价和“统计次数 两项加到二级索引表中，而不加到顺序代价表中， 有两个方面的原因：一是因为这两项查询使用频 繁，每次查询都要查找某个数据库的某个表的这两 项，用以统计查询代价：第二级索引表的表项数量 比顺序代价表小，加之搜索级数低于到顺序代价表 的搜索，所以加快了搜索速度。二是因为，将此两 项放在顺序代价表里，浪费存储空间，因为只有本 节点的数据库中的表才会被统计到（能够查询到本 节点的自然是本结点上有的数据库与其表），如果 将此两项放在代价信息表里，那么必然造成大量的 代价表项（其它节点IP）也分配了一样的此两项空 白存储空间；而通过前两级索引，已经能够唯一区

35、 分本节点各个数据库的各个表的代价信息的记录。b）更改删除:如果某个表被删除，首先在标志位置0， 然后，将后面的表项依次往前移动;同时，须将顺 序代价表中的相应代价节点项全部置为0，但无需 将后面的表项往前移动。尽管这种操作，可能较慢， 但这样的操作毕竟极少发生，比起大量的查询查询 操作来说，可以忽略它。而且对绝大多数查询用户 没有删除表的权限。插入：如果某个表的优化信息是索引顺序表中 没有过的，这时，需要在索引表中增加一个表项， 记录其优化信息。首先在该数据库的第二级索引表 的尾部查找是否有标志位置为0的表项，如果有， 将该表项填入，并调整顺序使其有序。如果没有， 再在该数据库的第二级索引表

36、段中查找是否有标 志位置为0的表项，如果有，将该表项填入，调整 顺序使其有序。如果仍然没有，就须重新申请分配 更大存储空间，然后将原有的记录项移置过去，并 将新的表项按序插入，使其保持有序。此种情况出 现的机率虽然极少，但仍可以尽量防止，那就是采 用预留策略。即对各个数据库的表段预留一定的空 表项，以备插入新的表项用。预留表项的数目保持 一个阀值，如果因为出现删除表项，而使得预留的 空表项数目大于这个阀值一定数目，就将多余阀值 的空表项删除，这时，就须要对索引表作移置操作； 反之，如果，因为出现增加表项，而使得预留的空 表项数目小于这个阀值一定数目，就将少余阀值的 空表项增加一定数目，使其达到

37、阀值数目，这时， 仍然要对索引表作移置操作。做了这种防御措施 后，就出现移置的机率就更少了。以上讨论的策略对后面的数据库索引表和顺 序代价表同样适用。对数据库索引表来说，稍微复 杂一点，即多一个步骤。当某个库被删除之后，先 将该库表项的标志位置为 0 （不可用） ;再将该库所 辖的各表的标志位置为0（不可用）；接下来，将置 为0的各表所辖的顺序代价信息表段的所有代价信 息表项也置为0（不可用）。然后再将顺序代价表置 为0的表项“删除，这里的“删除是指将后面 的表项前移，覆盖废弃的表项，并非真正的删除。 接下来该“删除第二级索引中的废弃（表项标志 位置为o的表项。最后将第一级索引中的废弃表项 “

38、删除。注意，对顺序代价表，可以省去将表项 置为0的那一步，直接将它们“删除。对顺序代 价表，当获知某个节点不可用，这时需要搜索整X 顺序代价信息表的IP,将IP等于该节点IP的表项 全部作“废弃处理，在这种情况下，就不用先标 记为0，再“删除它们。如何获知数据库、表以与节点是否“废弃呢? 采用定期监测的策略，在优化器的后台统计进程里 周期性的查询分布式数据库系统的全局视图信息， 获得有那些数据库，某个数据库有哪些表，有哪些 节点目前可用。如 SHOWGLOBALDB，SHOW TABLES， SHOW IPSBY DB等2）访问锁 多个用户同时进展以上的访问操作，操作间须 遵循一定的规如此:查

39、找操作之间可以共享该表， 而更新操作之间或更新操作与查询操作之间如此 须互斥进展。为此，需要在操作间加锁机制:查找 操作加读锁，共享锁;更改操作间加写锁，互斥锁。 11.查询代价（查询时间）的获取利用mydql本身提供的粗略估计执行时间，省 去了额外的时间计量的开销。它是从服务器接收到 用户查询命令开始计时，经过语法分析和查询执 行，然后将结果集组装返回给客户端（Send OK）的 整个过程所经历的时间。说它“粗略，是指它是 使用时钟计数的相对值，而不是系统的真正时间， 即不是CPU或机器时间。但是，它服务器当前状态 的运行性能，所以这对设计的算法并不影响，因为 仅仅需要以某种计量单元为单位的相对时间，而无 须当前的绝对时间。1 庞惠，翟正利论分布式数据库J 电脑 知识与技术, 2011,Vol.7（ISSN 1009-3044）:271.2 赵光亮.基于半连接算法的分布式数据库系 统查询优化技术D.某某：某某工业大学,2013.3 X旭中.分布式数据库查询优化技术D.某 某：电子科技大学,2003.4 Hector Garicia-Molina.数据库系统实现M. 杨冬青，机械工业,2001.