分布式数据库查询优化核心技术.docx
《分布式数据库查询优化核心技术.docx》由会员分享，可在线阅读，更多相关《分布式数据库查询优化核心技术.docx（18页珍藏版）》请在冰点文库上搜索。
分布式数据库查询优化核心技术
分布式数据库查询优化技术
摘要在分布式数据库中，由于高可靠性和高速度性是其重要特点，因此对查询执行规定也就更高。
而查询执行中查询优化是执行核心环节，查询优化在很大限度上决定查询效率或快慢。
本文讨论重点是对分布式查询执行全局解决方略进行优化，尽量避免通信代价开销，并着眼于查询执行实际代价，从分布式系统中选出一种最优执行节点。
从查询执行效果出发，通过记录方式，不断从近来查询执行代价学习纠正近来查询执行记录代价，为查询全局解决提供参照，以达到优化执行、提高执行效率和速度目。
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）处在网络中各数据库共享数据应保证一致性:
当顾客操纵（查询、更新、删除等）某一数据库时，整个网络中各节点如果有该数据库副本或备份数据库，应进行相应更新操作，以保持数据一致性。
（3）系统可靠性应比集中式数据库系统可靠性更高:
如果由于某种因素，使系统中某一节点数据库崩溃，系统会自动选取另一具备该数据库节点继续提供本来服务。
（4）支持多顾客并行访问，或者操作并行性;
（5）数据安全性和完整性比集中式数据库规定更高;
由于分布式数据库系统中各节点数据库处在网络环境中，数据受到破坏和窃取以及丢失也许性大大增长。
2数据库查询优化技术
2.1查询优化技术
数据库系统研究重要目的是尽量对顾客隐藏数据构造细节，使数据库系统应用更能面向各个领域。
同样，分布式数据库研究重要目的之一是隐藏分布式环境细节，使系统用起来更加简朴、有效[3]。
关系数据模型可觉得集中式数据库提供一种数据无关接口关系数据库语言是关系演算，使用该语言进行数据查询时，只需对要查询数据进行简朴描述，而不必阐明如何获取这些数据，SQL语言就是其中之一。
但是，使用这种语言，也要对搜索、存取操作以及数据传播过程进行阐明，因而，相应查询优化技术研究和发展也在不断进行。
所谓查询优化，就是要保证查询总开销和总时间为最小。
查询优化器重要任务是控制和加快查询执行和数据传播过程。
查询优化器（如图2-1）一方面以查询某种表达作为输入，这种表达是查询解决器语法分析子模块输出，查询优化器为查询选取一种恰当数据存取方略。
然而，查询优化始终是个复杂问题，抱负全面查询优化几乎是不也许，许多专家和学者在这一领域曾做出过不少研究和探讨，但总说来，不尽人意，往往只能达到局部目的查询优化效果，甚至有些理论并不合用。
图2-1查询优化解决
查询优化基本类型普通涉及两类:
针对查询执行代价优化和针对查询响应时间优化。
针对查询执行代价进行优化目的是，使查询执行所使用系统资源（总和）尽量地少，从而减少系统开销，整个系统开销可以从单个系统资源开销表达式中推出。
针对查询响应时间优化目的是尽量减少查询响应时间，而不计较系统资源耗费。
2.2分布式数据库优化设计分析
在分布式数据库系统中，一方面，许多相对独立解决器也许参加数据库操作。
分布式数据库也许提供若干机会[3]：
1）由于在解决一种问题时可以使用多台机器，并行以及加快查询反映速度也许性增大。
2）由于数据可以在各种节点上存在副本，系统也许不会仅仅由于一种节点或部件发生故障而不得不断止解决。
另一方面，分布式解决增长了分布式系统各个方面复杂性，因而虽然是DBMS中最基本构成某些设计，也得重新考虑。
在许多分布式环境中，通信开销也许远不不大于解决开销，因而问题是消息如何传送。
例如分布式提交和分布式封锁。
影响通信开销因素重要是由于带宽开销迅速减小。
某些类型数据属于电子方式管理大对象，因而虽然在通信开销较小时，以太字节数据传播开销也是不能忽视。
此外，通信开销经常不但仅涉及数据传送，尚有为数据传送做准备各层合同、在接受方重建数据以及通信管理。
这些合同各自都需要大量计算。
尽管计算开销也在减小，与数据与核心数据库操作老式单解决器操作相比，进行通信所需计算也许仍不能忽视。
分布式数据库查询解决如图2-5，分布特性存在除带来通信开销外还影响到物理查询筹划设计复杂性和可选方案。
在选取物理查询筹划时必要考虑问题涉及：
如果某个所需关系R有各种副本，那么应当从那个副本中获得R值。
当在两个关系R和S上实行某个操作例如连接时，有各种可选方案并且必要选取其中之一时，某些也许选项如下：
a）可以将S复制到R所在节点，并在该节点执行计算。
b）可以将R复制到S所在节点，并在该节点执行计算。
c）可以将R和S复制到两者各自所在节点之外第三个节点，并在该节点执行计算。
哪种选取最佳，这依赖于各种因素，其中涉及哪个节点上有可用解决时间以及操作成果与否需要与第三个结点上数据相结合等。
如果关系R有分布在若干节点上片断
构成，那么在选取逻辑查询筹划时，还应当考虑用
代替查询中使用R，代替后查询或许能很大限度简化表达式。
3）对局域网来说，通讯代价有着跟数据库磁盘I/O代价相比拟重要性。
网络通信代价会随着顾客数或负载变化而变化，因此网络状况变化随机性对分布式查询解决来说，更应当考虑通信代价。
但当某个数据库查询负载过高时，需要牺牲一定通讯代价来提高执行并行度。
此外局域网络广播能力可以用于全局优化更新、收集信息。
图2-5分布式查询解决通用层级方案
3分布式数据库查询优化技术研究
3.1基于分布式数据库分布特点优化
分布式并行系统处在网络中，处在网络中各个节点具备单个服务器系统所没有特性，所要考虑因素和重点也将有所不同。
分布式系统中数据分布性和操作并行性。
因此既要运用分布并行特点来加快查询执行速度，又要尽量减少分布并行所带来网络通信延迟代价[3]。
3.1.1系统环境和约束条件及设计目的
（1）设计目的与系统环境
本分布式数据库管理系统是针对局域网环境，分布式数据库是指分布于局域网络，而非广域网络，分布粒度为库一级，并且基于Mysql开源数据库来设计。
目是尽量避免数据库分布给查询执行带来通信开销。
（2）约束条件
在此前提下，须考虑如下某些约束因素:
1.通信代价
分布式数据库不同于集中式数据库，因此通信代价不得不考虑；但同步它又没有广域网环境中分布式数据库通信开销那么大。
因此既不能只考虑磁盘输入输出I/O和CPU计算代价开销，也不能只考虑通信代价开销，通过参照权威文献和对单机查询代价与数据通信代价实验分析，两者都应考虑，且同步并重。
由于是库级分布，不是表级分布，因此跨表操作始终只会在一种节点中进行解决。
而跨库操作，当前Mysql数据库系统还不支持此种操作。
因而，不存在查询时服务器节点之间通信，因而省去对查询执行时通信代价考虑。
但是，当解决来自本节点没有数据库时，就有也许了。
在这种状况，老式方式转发查询命令到其他节点上执行，这就要考虑通信代价额外开销了
2.查询分解
表3-1代价信息登记表
节点IP
数据库DB
关系表table
全局查询代价cost
该表负载数count
...
...
...
...
...
由于是库级分布，某个数据库在某个节点存在，那么这个数据库所有表都在这个节点上存在（主本或副本），因此不考虑查询分解。
3.透明访问。
顾客访问本分布式数据库系统感觉不到数据库物理位置位于何处，就像访问本地数据库（或集中式数据库）同样。
4.Mysql不支持特性
Mysql不支持视图、子查询、存储过程和触发器、外键。
（3）优化目的
强调查询快捷，着眼于查询时间开销;注重整体查询（整个分布式局域网系统和多路多线程总体查询）效率和吞吐率，而非单机或详细某一条查询语句执行效率。
系统合理假设
重要针对上层进行优化，而不针对下层，并假定已对查询语句进行了优化。
因而，要考虑核心问题便落在通信代价上，而其他磁盘输入输出I/O和CPU计算代价开销，是由下层查询优化去解决。
3.1.2优化方略研究与设计
下面对启发式查询途径选取优化方略进行详细探讨和设计。
（1）基本思想
依照近来一段时间查询代价，推断局域网络中分布式数据库各节点当前查询解决能力，实质上还是依照资源占用状况来选取一台较优节点去执行查询解决。
在实现方略上，属于不断学习优化过程。
基于一条基本思想:
近来访问表格，在近来一段时间内，仍处在同一状态（忙），即很也许被再次访问。
如果这种判断浮现错误，也会仅仅由于一次查询操作，而只误导一次，在下一次同样查询，又会转入对的优化判断。
这样“误判”，仅仅导致一次慢速查询，不会有太大损失。
优化另一方略是尽量避免通信代价开销，使一种查询尽量不通过查询中转，避免查询成果数据通信。
（2）优化设计
1.节点代价信息表
为了记录上次访问表查询代价，及其通信代价，需要设计如下某些表格如表3-1，以记录如下某些上次访问历史信息：
阐明：
（此处通信代价不是指一次查询所有数据通信代价，是单位数据在当时通信代价）
节点IP：
批示局域网中分布式数据库所在节点IP地址
数据库：
指该节点中存在有哪些数据库
关系表：
指该数据库中存在有哪些表
顾客数：
指该表中当时有几种顾客查询计数
为使各节点便于查询，该表存在于局域网中每一种节点中，并且为了提高查询速度，更快执行优化选取，该表必要常驻内存。
表中记录信息随时更新。
全局查询代价由Mysql数据库系统自身THD构造获得。
某个表顾客计数是通过查询时锁表机制而获得。
值得阐明是为什么不能采用共享数据构造方式?
如果分布式网络中各节点共享一张表，表面上看起来，可以节约存储分派，维护单一;事实上，由于该表访问比较频繁，特别是查询顾客量增大时候更是如此，而为了保证数据一致性，各节点必要互斥访问该表，无论采用锁机制，还是简朴互斥信号量，都会导致访问因竞争而等待，致使服务器解决性能大为减少。
因而，它是不符合分布式系统设计思想。
2.代价估算
1）操纵单表查询语句
一种分布式数据库查询执行，涉及全局解决和本地解决两个阶段，相应查询代价也涉及全局解决代价和局部解决代价两某些，撇开CPU开销，可以一种公式近似简化为：
全局查询代价二通信代价+本地执行代价
但基于前面考虑，不计通信代价，因此只有本地执行代价。
本地执行代价=CPU计算时间+I/O等待时间
由于CPU计算时间相对很小，可以忽视，执行代价近似等于I/O等待时间。
实现中，记录代价为：
I/O数据量可以粗略以一种表所有元组数计。
2）操纵多表查询语句
需要注意是，如果一条查询语句需要操纵不只一种数据库一种表时，究竟以哪个表代价为准，或者都考虑但各种表之间考虑偏重限度也许不同样，并不平均对待。
因此衡量各种表操纵查询代价，不能简朴将各种表代价相加之和作为该查询语句代价。
记录操纵多表查询语句代价时，很难将总体代价定位在各个表上，某些繁琐算法既费时，又不精确，因此，基于实际应用上考虑，略去本次查询代价记录，而只记录单表操作代价。
多表属于同一数据库（对库级分布，一定位于同一结点上），理论上，任选其中一种表代价来衡量，但在实际操作中，为了减少单个表带来偶尔误判，采用累加和。
多表不属于同一数据库（不一定位于同一结点上），此种状况，固然不能像上面同样，任选一种表代价去衡量，也不能将各表代价累加之和作为痕量代价。
只能依照哪个表操作代价高来决定执行节点。
但对库级分布数据库不支持多表不属于一种数据库状况。
3.负载
这里讨论负载重要指顾客数量，以表作资源对象，用在某个表上等待线程（顾客数）来度量负载。
计数方略:
由于各种查询也许操纵同一表，为保证数据一致性，本分布式数据库系统提供了互斥锁（读锁和写锁）机制。
当一种操纵某个表查询祈求到来时，就将count计数作加1操作，当该表一种操作结束;当解锁一次，就将count计数作减I操作。
然后定期更新此。
ount计数。
为此，需要在THD构造里定义一种变量以保存该计数值。
4.记录方略
对代价记录，取一定期间内，每次查询代价平均值。
这里一定期间即为记录周期，也是更新周期。
同样，将每次查询代价记入THD构造里，也将代价平均值保存到THD构造里。
以便全局优化器能以便获取所需信息。
采用动态更新，即服务器一启动便开始记录，在服务器运营过程中周期性更新。
因此全局代价表从无到有，逐渐增多，随着时间推移，使查询优化信息越来越完善，越来越精确。
此外，如果本次查询表在全局代价表里尚未存在记录，则该次查询代价及时记入全局代价表中，以被日后查询参照。
不必等到一定周期记录。
某一次记录也许不是精确，但多次大量记录，对的率总是符合正态分布，从记录学角度讲，是对的、实用。
此外，为了使记录更为真实和有效，本设计对某些很少浮现某些语句抛弃掉，不予记录。
例如像CREATEDATABASE，DROPDATABASE，CREATETABLEDROPTABLE，ALTERTABLE，CREATEINDEX，DROPINDEX，等只有再创立数据库时，才会用到某些命令语句;尚有某些显示数据库及其分布信息查询命令，以及全局视图查询命令，由于较少使用或不涉及详细操纵哪个表，也不予记录其代价信息，如SHOWDATABASE，SHOWTABLES，SHOWGLOBALDBS，SHOWIPSBYDB等。
5.更新周期
周期如何拟定呢?
周期过短也许导致记录平均值不真实;但周期过长，有也许不能反映当时或近来服务器节点解决状况。
因此周期既不能过长也不能过短，如何拟定一种适当周期呢?
一方面，这个周期不能是固定不变，由于网络状况不是固定不变，它会随着服务器节点负载而变化，而服务器节点负载状况完全是随机，随着顾客数量变化而变化。
因而，为了适应变化多端网络环境及节点资源负载状况，这里使用一种动态方略，以更精确更及时地反映服务器解决能力。
从实际状况出发，如果先后几次波动很大，超过一定值，阐明负载变化很频繁，这时，需要缩短记录周期;反之，可以加长记录周期。
但为了防止变化过于平凡，导致“抖动”现象，一次不能偏离初始值过大。
如何拟定偏离多大呢?
可以以本次预计代价，与上次代价预计偏离限度来作调节。
当
这里P依照服务器运营状况，可以由系统管理员拟定。
同样，当
阐明，如果本次记录代价与上次记录相比波动较大，偏离限度超过P%，周期变长；反之，周期缩短。
初始值可以由系统管理员更改，默以为每30秒更新一次。
6.更新方略
为了保证优化信息全局一致性，必要将各节点本地最新记录优化信息告知分布式系统中其他节点，使得对任何一种节点来，从理论上说，在当前优化条件下，均会作出同样选取（某个优化节点）。
由于本文讨论分布式数据库系统是存在于局域网络中，其可靠性和速度比较高，因此本文采用类似于选路信息合同（RIP）中路由信息在路由器间更新方略，即广播方略。
它避免了设定一张全局唯一代价信息表，它属于共享资源，必要互斥访问，需要使用互斥锁机制才干实现。
广播周期:
为了防止广播风暴，不能频繁广播消息，但是广播周期过于长，又会使全局优化信息得不到及时更新。
设定一种阀值，当变化超过某一阀值时，才广播更新消息。
7.问题简化
1）关于数据库表索引
如果为数据库表创立了索引，则在查询执行时磁盘输入输出操作会与没有创立索引表代价低诸多，由于查询时扫描表分为两种:
一种是表一扫描;另一种为索引一扫描。
由于索引扫描时，能不久定位所需记录（元组数）所在磁盘块位置，因此比将整张表记录都读入内存来查询比较效率要高得多。
但创立了索引表列较少，大多数表大多数列没有创立索引。
并且对同一种表，每一次查询记录均是以相似方式记录，因此并不导致影响。
对某些很少使用或者查询不涉及详细哪个表简朴操作，不予记录其代价信息，以尽量减少或避免记录数据不真实性。
2）CPU计算代价
由于在查询执行中，CPU计算时间，比起磁盘输入输出和通信代价来说很小，在普通优化器设计中，大都忽视不计，本优化也不予考虑。
8.非更新数据库操作并行化解决
若某一刻，同步有各种顾客查询祈求访问同一表，并且是除插入、删除等更新操作以外操作（非更新操作），将查询命令分发出去并行解决。
尽管单从代价来考虑，也许某一种服务器节点当前是最优选取节点，但如果同一时刻（或某一段较小时间内）有各种客户祈求到达，都要查询某个数据库某个表，即竞争到同一张表上，必然形成等待队列。
如果这些查询不都是更新性表操作，即非更新性操作是可并行化解决，可以将非更新性操作分发到其他客户数较少节点上去解决。
如果同一查询语句操纵各种表，遇到此种状况，优化选取时就排除该表不计算其代价。
9.全局优化信息表存储组织
本表常驻内存，因此其存储组织不能有较大挥霍。
如果采用链表方式存储，表大小可以随时增长或减少，内存可以随时申请和释放，得到充分运用，但是，查找速度较慢。
另一方面，由于提高查询速度和查询效率是本优化设计目，因此如何组织存储构造才干提高查找性能（速度），是首要考虑问题，因此使用数组存储方式就不太适当。
而顺序存储方式比链表检索速度快，并且恰当运用索引可以更高提高查找速度。
但由于不能事先预知该表信息大小，并且也许动态变化，如何解决数组固定大小问题呢?
由于此种变化并不频繁，可以使用new操作重新分派变化大小后内存空间，并将原数据拷贝过去。
并且对于本表来说，采用索引顺序存储方式，比起完全不采用索引顺序存储方式或链表存储方式来说，避免了较大不必要数据重复存储，如表前两项“数据库名”和“表名”不必重复存储。
存储构造采用索引顺序表组织，分两级索引，如图3-1所示：
表名
标志（状态）
地址（位置）
长度
表大小
记录代价
记录次数
图3-1代价信息索引顺序表存储构造
第一级索引为数据库名，按数据库名字母顺序有序排列；再按照数据库提成各种二级索引，即表索引，按表名字母顺序有序排列。
然后依照表来查找查询所要操纵表相应代价及客户计数及所在节点IP等优化信息。
由于整个系统中不同数据库、表和节点IP数量并不太大，因此按照两级索引来查找顺序代价表，不久便能找到优化表解决节点（IP）。
图中右半某些为顺序表，按表第一项（代价cost）有序排列。
关于索引顺序表大小拟定：
由于本表常驻内存，因此存储空间分派不能又较大挥霍。
所觉得了充分运用存储空间，有两种分派方案:
一种分派方案是，采用静态数组，但需要预先拟定数组大小。
在分派顺序表时，要预先拟定表及索引大小。
如果是系统中第一种节点初始启动，可以在系统初启时，从DesMysql底层预先获得数据库、各数据库表及节点数目，然后再分派存储空间并初始化各项数据，其中，表中所有代价初始化为0}（系统初启时，没有任何负载，因此这也是合理）。
如果不是系统中第一种节点初始启动，只将本节点所有数据库所有表设为0，而将其他节点数据库表代价暂定为无穷大;在将来一段时间内，可以通过别节点对全局优化信息表广播信息获取来得到更新。
另一种分派方案是，采用顺序表动态存储分派，在系统启动后，通过度布式系统中其他节点广播信息，依照需要，暂时申请存储分派。
这样，表大小可以不一次性分派完，可以由小到大，随着表信息不断增长而增大。
10.索引顺序表操作与互斥锁
1）操作
a）索引查找
才干实现对上述索引顺序表操纵，设计如何数据构造才干达到索引目?
要索引某一项，需要懂得被索引表地址，即索引表存储在哪个内存地址段中，可以用一种全局变量来记录;然后才干定位某级索引相对位置（即地址偏移），以及该级索引所覆盖范畴，即长度。
对第一级索引（数据库索引）：
数据库名
标志（状态）
地址（位置）
长度
对第二级索引（表索引）:
对顺序代价表：
代价信息
标志（状态）
阐明:
对第一、二级索引中增长“标志位”，指是表（库）当前状态：
1表达该表（库）存在且可用；0表达该表（库）当前不可用；其中二级索引中新增长“记录代价”，是指在更新周期内记录代价，它只作暂时记录取，不作优化信息用，等到周期一到，才决定与否将其代价值加到代价Cost列上。
二级索引中新增长“表大小”，是指表每条记录大小与记录数数乘积；新增长“记录次数”记录该表被记录次数。
同样，对顺序表“标志位”，1表达该代价信息可用;0表达该代价信息不可用。
顺序代价表“代价信息”，指是上图中所列代价Cost、客户计数Count和节点IP等信息。
注释：
为什么要将“记录代价”和“记录次数”两项加到二级索引表中，而不加到顺序代价表中，有两个方面因素：
一是由于这两项查询使用频繁，每次查询都要查找某个数据库某个表这两项，用以记录查询代价：
第二级索引表表项数量比顺序代价表小，加之搜索级数低于到顺序代价表搜索，因此加快了搜索速度。
二是由于，将此两项放在顺序代价表里，挥霍存储空间，由于只有本节点数据库中表才会被记录到（可以查询到本节点自然是本结点上有数据库及其表），如果将此两项放在代价信息表里，那么必然导致大量代价表项（其他节点IP）也分派了相似此两项空白存储空间；而通过前两级索引，已经可以唯一区别本节点各个数据库各个表代价信息记录。
b）更改
删除:
如果某个表被删除，一方面在标志位置0，然后，将背面表项依次往前移动;同步，须将顺序代价表中相应代价节点项所有置为0，但无需将背面表项往前移动。
尽管这种操作，也许较慢，但这样操作毕竟很少发生，比起大量查询查询操作来说，可以忽视它。
并且对绝大多数查询顾客没有删除表权限。
插入：
如果某个表优化信息是索引顺序表中没有过，这时，需要在索引表中增长一种表项，记录其优化信息。
一方面在该数据库第二级索引表尾部查找与否有标志位置为0表项，如果有，将该表项填入，并调节顺序使其有序。
如果没有，再在该数据库第二级索引表段中查找与否有标志位置为0表项，如果有，将该表项填入，调节顺序使其有序。
如果依然没有，就须重新申请分派更大存储空间，然后将原有记录项移置过去，并将新表项按序插入，使其保持有序。
此种状况浮现机率虽然很少，但仍可以尽量避免，那就是采用预留方略。
即对各个数据库表段预留一定空表项，以备插入新表项用。
预留表项数目保持一种阀值，如果由于浮现删除表项，而使得预留空表项数目不不大于这个阀值一定
升级会员 