由于关系数据库的数据执行关系固定，因此关系数据库在使用索引上有较多的优化空间，而相对于关系数据库中较为固定的数据组织结构，XML数据库的数据之间的组织关系较为松散，甚至是无结构的组织方式，而这种无结构的组织方式则在很大程度上导致索引使用的困难，具体原因我们将在后续的文章中进行讨论。在讨论XML数据库的索引之前，我们将首先看看关系数据库的索引使用策略。

首先，我们讨论关系数据库中的索引使用策略。例如：对于表A ，分别在两列上建立索引：colA(colA_Index)， colB(colB_Index)。当使用条件conA，conB在colA和colB上进行查询时候，系统会根据具体情况来决定是使用索引查询(索引+Filter)和是使用全表扫描查询(全表+Filter)。

Table: A

Select * from A where colA = conA and colB = conB 对于此类情况将使用colA和colB上的索引，然后进行And操作得出结果。当其中一个无法使用索引时，系统首先选择能够使用索引的列进行索引扫描，然后将非索引列使用Filter进行操作。 例如: select * from A where (colA +1) = conA and colB = conB，此时对于colA将无法使用索引进行索引扫描，系统将会首先选择colB进行索引扫描，对于colA将使用Filter进行条件扫描，由Filter函数输出为最终的查询结果。 其他情况就不在这里赘述，有兴趣的可以查看关系数据库查询计划进行验证。

在完成系统中索引信息的记录后，我们得到系统中关于索引的全部信息，基于这些信息，我们可以在对查询语句优化，按照系统中的索引信息来选择相应的索引进行优化。

在阐述系统实现之前，我们要明确几个概念：（1）系统中存在着哪些查询需要使用索引；（2）系统中存在着哪些类型的索引。对于第二点，我们可以由索引元数据表中获得详细对索引的描述。对于第一点，从FLWOR语句中可以看出存在着条件判断的类型分为两类：（1）谓词判断；（2）where条件判断。例如：对于语句/a/b/c[@attr1=”value1”]或者/d/e/f[@attr2=”value2”]/g[@attr3=”value3”]，其中的[@attr1=”value1”]、[@attr2=”value2”]或者[@attr3=”value3”]这种情况我们称之为谓词过滤；对于语句 where $i/a/b/c/@attr1=”value1” and $i/d/e/f/@attr2=”valu2” and $i/g/@attr3=”value3”，我们称$i/a/b/c/@attr1=”value1”、 $i/d/e/f/@attr2=”valu2”以及$i/g/@attr3=”value3”为where条件判断。

在完成FLWOR语句中两类常见可以使用索引的场景分析后，以及我们上述对于系统当前索引选择策略的阐述后，可以得出明确的结论：现有系统的所有选择在策略限于当时各种条件，只是完成了最简单的索引使用策略，并且在索引使用的顺序也未做详细考虑。例如对于在一个FLWOR语句中存在where子句的情况下，是首先使用where条件中的条件进行条件过滤，而后进行后续的操作；还是按照语句的顺序进行执行，然后进行where条件过滤等，在现有系统中均为做仔细的考虑和验证。例如：对于 query for $i in doc(“xxx”)/a/b/c where $i/@attr=”value”，当前的先进行/a/b/c路径过滤，然后进行索引过滤，由于/a/b/c在系统中可能存在较多的数据，使得在进行where条件索引过滤时需要经过较多次数的所有扫描；若我们首先执行where条件的索引扫描，则首先将满足where条件的记录取得，在此基础上在进行/a/b/c路径条件的判定，从而有可能使得执行索引扫描的开销，进而提高系统的查询效率。

在上述理想的情况下，无论是关系数据库还是非关系数据库(XMLDB)都可以按照上述的处理步骤进行优化，但是实际的情况是理想的情况属于少数，而多数场景下，我们无法以理想场景进行优化。但是，同时考虑到FLWOR语句在实际的应用中存在着一定的模式，使得我们能够将某些规则应用于该查询语句中成为可能；并且完成基于规则的查询优化后，系统可以利用代价信息进行进一步的基于代价的优化。

• 概述

相较于传统的关系数据库中常用的两类优化策略：基于规则的优化和基于代价的优化策略，现有的XMLDB中仅仅存在着一些简单的基于规则的查询优化，主要是基于查询语句的模版类型进行优化，例如：对于where子句中的条件如果两个条件中的左值相同且两个查询条件相邻，则系统会进行查询条件的合并操作，如:$i/a/b/c/@attr1=”value1” and $i/a/b/c/@attr1=”value2” 则系统会识别出该类型的查询语句模式并对这两个条件进行条件合并，合并后的查询条件变为： $i/a/b/c/@attr1=”value1 &value2”，系统将在执行的时使用合并后的条件进行索引扫描，从而将两次的索引扫描合并成一次的索引扫描。

理想情况下我们可以将逻辑条件首先进行逻辑优化，然后合并相同的项目。但是，当所处理的多个条件在逻辑优化后无法进行合并后，而这两个条件又分别建立索引，如：存在一个条件：$i/a/b/c/@attr1=”value1” and $i/a/b/c/@attr2=”value2”，系统无法将该条件进行合并，而该条件表达式的两个条件又分别建立了各种的索引；又如上文中所提到的关系数据为例，对于条件 where colA =”valueA” and colB =”valueB”，在colA和colB上分别建立了索引colA_Index 和colB_Index ，关系数据库则会分别使用colA_Index和colB_Index，最后将两次索引查询的结果进行and/or操作（或者使用BitmapAnd/BitmapOr）形成最后的返回结果。但当查询语句为 where colA=”valueA” and (1 + colB) =“valueB”形式后，对于条件colA =”valueA”可以使用索引进行索引查询，但是对于条件(1+colB) =”valueB”则无法使用索引进行索引查询，因此关系数据库采用的Index + Filter的方式进行。先使用colA_Index进行索引查询，然后将该查询结果送入Filter{con: (1+colB)=”valueB”}，最后得到最终的查询结果。

• 逻辑表达式优化（Logical Expression Optimization）

逻辑表达式描述了一系列的逻辑运算，通常这些逻辑运算又作为一系列的判定条件存在于查询语句中。一个逻辑表达式可以很简单，例如：a=”a” and a=”b” 也可以非常复杂，包含运算嵌套等，例如：(a =”a” and a=”b”) or (b=”b” or (c=”c” and d=”d”))；同时，也存在着类似于(1 +a) = 10 and (1+b) = 20 此类的左值中存在着复杂运行的情况，此类情况下，若不对该逻辑表达式进行相应的优化，无论如何是无法进行索引优化；对于此类未经优化的逻辑表达式也不利于我们后续的优化工作：例如：多索引条件的合并等等。 相当于其它部分，逻辑表达式的优化，相对独立于系统：无论是关系数据库还是非关系数据库，其处理逻辑表达式的方式方法较为独立具有一套完整的算法。

在完成对于逻辑表达式的优化后，我们将获得一个精简的逻辑表达式，基于此精简后的逻辑表达式，我们即可进行后续的基于规则的优化和基于代价的查询优化。

• 基于规则的查询优化(Rules-based Optimization)

规则：描述了当系统遇到条件后，所执行的动作。如.y文件中描述一套语法规则，该规则规定了当遇到何种的语法形式时执行的相应动作，类似于语法规则文件的做法。

为了使得系统能够使用基于规则的优化策略，我们需要元数据表来记录当前系统中所存在的规则定义。该表中记录了目标语句与源语句之间的对比关系。系统在执行查询操作时，首先会进入规则系统中进行规则查询，以检查该查询语句与规则系统中的模版相匹配，当查询语句中存在着与规则系统想匹配的部分时候，此时系统将源查询语句使用规则系统中的规则进行规则替换，使得我们的查询语句能够按照事先所定义的转换规则进行替换。 规则系统定义为：

Rules —–> Actions.

其中，Rules是我们所定义的一系列规则系统，而Actions则是满足该规则后，系统所需要执行的操作。 例如：对于查询语句中存在规则datetime < “range1” and datetime > “range2”  “setIndexLevel /path/@datetime NEW_LEVEL_VALUE”。

当系统检测到datetime的时间范围在 range1至range2之间，系统将执行该规则的行为 当系统中存在着如上的规则，用户执行某类查询时，存在这个datetime项的查询条件，此时需要决定是否对该条件使用索引扫描，以及使用何种索引进行索引扫描。如果该条件的索引选择率较高则我们可以使用该索引，但由于系统的统计信息的丢失，使得我们的索引选择异常困难。为了弥补由于统计信息的缺少，同时又可以完成对于索引的选择。我们引入规则系统，通过对规则系统的定义来完成对于索引使用的选择控制。例如：存在着查询 where datetime<”” and datetime >”” and conA= value1，此时系统中datetime索引的选择率为0.6 ，conA的索引选择率为0.55，导致的结果是系统会首先选择使用datetime进行索引扫描，然后对conA=value1进行处理。若datetime的比较条件范围较大，导致的结果是使用datetime进行索引查询时，其返回的结果集过大，其索引扫描的代价过大，显然使用datetime进行索引扫描不合理，而应当首先使用conA作为索引列，进行索引扫描。

规则引擎模块处于逻辑优化模块之下，而处于基于代价优化模块之上。在完成了逻辑优化之后，进入基于规则的优化，在完成基于规则的优化后，最后完成基于代价的优化。

• 基于代价的查询优化(Cost-base Optimization)

代价：描述了执行某类操作时，所需要的资源消耗。其中代价信息可以包括：计算代价+ io代价 + others代价。代价的高低衡量了一个操作的执行所需要系统资源消耗。下面我们从代价技术的表达式中的每一项进行分别讨论。

计算代价：包括了cpu计算时间，除去从编译层的高级语言的语句到机器指令，从系统结构层面来看，一条机器指令从取得到执行包括了：取指令(IF)，译码(DE)，执行(EX)，内存存取(MA)，结果回写(WB)五个阶段。考虑到现在指令系统通常采用流行线方式进行，并提供多核以及多处理器架构，这些技术的引入使得我们的计算代价在数据库应用中所占的比例越来越低。

相对高速CPU的计算能力，内存IO能力则落后于CPU技术的发展，为了减少由于内存IO能力所带来的瓶颈，Cache技术发展则进一步的弥补两种直接的差距。处理器中的多级cache架构的引入则是一个有力的证明。 内存的双通道技术也进一步解决内存带宽的瓶颈(内存墙)。

低速的磁盘IO决定了整个数据库系统整体性能，由于当前的磁盘多数均为机械硬盘，而其中的磁盘的寻道算法觉得了磁盘机械臂的运转，数据读取速率等诸多因素影响了磁盘IO的性能。因此，相比较而言，磁盘的顺序读写性能高于磁盘的随机读写效率。而作为数据库系统，一个重要的任务就是减少由于频繁的随机磁盘读写所造成的系统性能下降。 磁盘的寻道算法以及数据读写速度均有磁盘硬件所决定，我们能做到是减少磁盘的随机读写，提高磁盘的顺序读写。随着今年磁盘技术的发展，固态硬盘的单位字节价格比越来越低，固态硬盘已有取代机械硬盘或者与机械硬盘搭配使用的趋势：将固态硬盘作为外部存储的一级存储，将机械硬盘作为外部存储的二级存储系统。固态硬盘的引入带给我们在进行数据库设计的变革，而相应的系统架构也应该随着新技术的应用而进行适当的调整。

基于代价的查询优化就是在我们的查询计划/执行计划在产生的过程中要重复考虑上述因素所带来的影响，使得最后的我们所产生的查询计划/执行计划最优：所消耗的资源最少（计算资源+io资源）。相对应关系数据库经过数十年的发展，其在查询优化算法上已经相当成熟，相反在非结构化数据库中则未有较大发展，无论是XMLDB，还是当前的MongoDB在查询优化部分作为较少。考虑到MongoDB所出的应用场景已经其所提供的查询语法，我们不难发现其对于所针对的应用为逻辑简单的大数据量操作。XMLDB则是另外一个使用场景：其不但要解决大数据量的操作外，还需要满足w3c所提供的标准，而FLWOR语句则是w3c描述了使用高级查询语句对xml文件的操作。由于其使用的是类似于SQL的高级描述语言。

在完成上述的基于规则的优化后的查询计划已有很大的提高，但是由于基于规则的优化并未考虑到优化后的查询计划是否是执行效率最优；这有可能会导致：索引的滥用，错用等现象（FounderXMLDB系统中）。例如：对于查询条件 /a/b/c/@attr1=”value1” and /a/b/c/@attr2=”value2”，当系统中数据对于attr1和attr2的值的选择不高情况下，我们仍然使用索引扫描，在该种情况下必然会导致过多的IO操作(索引IO+数据存取IO)。相反，顺序扫描则是一个较优的选择；同时对于嵌套循环查询下的(NestLoop)多文档的连接顺序的选择，寻找一条最优的连接顺序也需要代价信息的支持。

例如：
for $i in doc(“doc1”)/a/b/c
For $j in doc(“doc2”)/d/e/f
Where $i/@attr1=$j/@attr2
Where $i/@attr3=”value3”
与
for for $j in doc(“doc2”)/a/b/c
for   for For $j in doc(“doc1”)/d/e/f
for   for Where $j/@attr3=”value3”
for Where $i/@attr1=$j/@attr2

上述的两种写法所产生的执行效率可能相差数倍甚至数十倍，不同的连接策略所产生的中间结果，存在巨大的差距，而这也是我们进行基于代价的优化的初衷。考虑到，现有分布式系统中文档处于不同的数据节点上，因此上述的代价优化中网络传输率，以及文档数量大小等相关参数也需要考虑，数据是否进行数据迁移，然后进行连接操作，还是进行在线连接操作也需要在后续的详细设计中进行仔细考虑和衡量。为了能够使用基于代价的查询优化，需要相关数据：统计信息。例如：满足索引条件的记录数量，每个Tuple大小，数据表中记录数等等；

考虑到，当前系统中的无论是存储层亦或是查询层的统计模块功能均被破坏，现有两个步骤方案：（1）首先，手工提供统计数据；（2）在完成基于手工统计数据的基础上完成优化实现，而后将统计数据的采集部分逐渐替换为自动采集。而自动统计数据则由存储底层接口提供，例如：当需要获得满足索引条件的Tuple条数，通过一个存储底层接口来获得。

对于（1）中所论述的首先采用手工数据提供统计数据的方式，我们可以提供的统计数据有：（1）所建每个索引的选择率；（2）每条路径上的数据数量；（3）文档的总数等信息。

为了使得在优化过程中能够访问到这些数据，系统将创建数张元数据表用以保存统计元数据。 当系统运行一段时候后，会造成统计元数据表中的统计信息不完全正确，为了能够及时更新统计信息，系统提供类似于关系数据库中的Analysis命令，在执行该命令后，系统将重新执行统计计算，将统计后的信息进行更新。

在进行查询计划/执行计划生成过程中，可以通过查询统计信息元数据表来获得当前数据的统计信息，而后根据这些统计信息执行上述的关系基于代价的查询优化。

无论是基于规则的查询优化还是基于代价的查询优化，我们朴素的想法是在现有的代码基础上将所建立的索引尽量使用起来，否则所建立的索引将毫无价值。