分类目录归档：XML Database

SQL-XQuery相互转换设计与实现

发表于由
  • 主要介绍SQL与XQuery之间相互转换的设计与实现

#0. 背景.

  XML数据库管理系统（XMLDBMS）是近年快速发展的一种新型的数据库管理系统（DBMS），它存储和检索的数据是XML文档。 XML数据的检索和更新语言是有W3C制定的标准的XQuery和XQuery Update。XQuery系列语言基于序列数据模型（XDM），即XQuery中任意数据都是一个序列，序列由若干个有序的项目（item）的组成；一个item是一个原子值或者一个XDM节点，一个XDM节点是XML文档的7种节点之一。基于这样的数据模型，最自然和高效的XML数据存储方案就是把XML文档存储为节点。

在XMLDBMS中存储XML文档的实体称为容器(Container)，一个容器中存储任意多个XML文档，而这个容器则由若干个数据表构成，这些数据表分别存储XML文档各个方面的数据和结构信息：包括节点数据，节点间关系，节点路径数据，索引，统计信息等。数据表存储的单位是数据行，一个数据表中含有若干个数据行，并且可以通过索引快速查找到特定的数据行。

关系数据库作为当今使用范围最广而且应用最为普遍的数据库已经被大量的应用在各个行业中，结构化查询语言(SQL，structural query language)则在关系数据库中扮演着重要的角色，SQL定义了一套完整的用来操作关系数据的语法：数据定义语言(DDL, data define language)，数据操作语言(DML, data manipulation language)。其中的DML语言中包括了select语句，update语句，insert语句，delete语句等用来对关系数据库中的关系数据的数据进行查询,更新，插入或者删除操作。因而，这四类语句在关系数据库中被称作四大基本语句并被开发者广泛使用。

对于习惯使用SQL的用户来说，要学习并掌握使用一门新的查询语言-XQuery需要花费大量时间和精力。传统的方式是由数据库操作人员进行手工完成对SQL语句到XQuery语句的转换，在该种方式下无法做到进行大批次的转换，而且在转换过程中易出现相应的语法、语义转换错误。虽然现在有些关系数据库能以XML形式操作非关系数据，但其并非以Native方式存储XML数据，而是先进行数据拆分然后以关系数据的形式进行存储，而必然会导致系统处理非关系数据时系统性能低下。

本文提出了一种基于抽象语法树将SQL语句自动转为XQuery语句的方法，其可以使得用户无需进行数据的关系化处理的情况下使用非关系数据，只需将非关系数据以XML方式存储至XML数据库中，这样用户可以直接使用SQL语句以Native的方式对非关系数据—XML数据进行操作，从而解决了上述用户在使用关系数据库来处理非关系数据时所带来的问题。

#1. 实现介绍.

随着当前互联网及其业务的飞速发展，在互联网应用大环境下产生了各式各样的数据，包括：关系数据和非关系数据。对于这两种数据来说关系数据则可以使用关系数据库以及SQL来对关系数据进行操作；对于非关系数据在我们将其组织成XML格式后，可将其以Native存储至xml数据库中，此时用户便可以使用XQuery语句来操作这些非关系数据。

在实际环境中在SQL与XQuery间的切换会导致数据库的使用者在一定程度上的困惑且容易在转换后出现各种语法、语义错误。为了避免在SQL与XQuery间转换的常规做法是将非关系数据在业务层进行关系化处理并在处理后存储至关系数据库中使用SQL语句进行操作。该种做法在实际环境下存在有些数据无法做到关系化且进行数据关系化该种增加了系统的处理负担，致使系统效率低下。因此我们提出的基于抽象语法树将SQL与XQuery进行转换的方法可以很好的解决上述存在的问题。

现有如下的xml文档(以后称之为Person.xml)。

<Person>
   <id>1</id>
   <Name>Pitt</Name>
</Person>
<Person>
   <id>2</id>
   <Name>Leo</Name>
</Person>
我们考虑如下的应用场景，对于一个关系数据库用户如果想对文档Person.xml中的非关系数据进行操作，则需要该关系数据库用户进一步学习使用xquery语言的使用。如果将Person.xml中的非关系数据形式以关系数据库的形式存储后，我们需要如下形式一张关系表 表名： Name，字段名称： id类型 int ; 字段名称：name 类型 char来保存上述Person.xml中的非关系数据。
此时，关系数据库用户可以方便的使用其所熟悉的SQL语句来对表Name进行操作，例如：使用select语句来进行数据查询，使用update来进行数据更新，使用insert插入一条新纪录，使用delete语句来删除一条已有纪录。例如对于关系数据库用户可以使用SQL语句select name from Name where id =1来查询id为1的用户的名称；但是上述是在能够将非关系数据进行关系化的基础之上，实际环境下很多数据无法做到关系化。因此，上述的方法不具有通用性，但是我们却很容易将这些非关系数据组成XML形式并以Native方式存储至XML数据库中。在此情况下，关系数据库中的SQL语句显然无法方便的操纵XML数据库中的非关系数据。例如：我们无法使用SQL语句来操纵Person.xml文件中的数据，必须使用一种新的查询语言XQuery来操作Person.xml中的数据。对于select name from Name where person_id =1的SQL语句，我们可以使用其对应的XQuery 语句for $i in doc(“Person.xml”) where $i/person/id=1 return $i/person/name 来完成SQL语句相等价的操作，但这对于熟知SQL语句的用户来说显然会增加其使用负担。

#2. 实现方法.

对应一条SQL查询语句，其在真正被执行之前需要经历数个步骤，其中之一便是：根据其所定义的语法、语义规则由Lex/Bison来生成相应的抽象语法树。我们称该阶段为查询语句的解析(Parse)阶段。在查询解析阶段，系统会根据人们预先定义的语法，语义规则来对我们所要执行的查询语句进行解析并根据相应的语义规则生成相应的抽象语法树。

关系数据库中的SQL查询语句有一套语法语义规则，而XQuery也同样有自己的一套语法和语义规则。虽然SQL和XQuery具有截然不同的语法和语义规则，但是一条SQL语句和一条XQuery语句在经过Lex/Bison进行解析后会产生相类似的产出物：抽象语法树。抽象语法树（abstract syntax tree或者缩写为AST），或者语法树（syntax tree），是SQL查询语句或者Xquery查询语句源代码的抽象语法结构的树状表现形式。树上的每个节点都表示查询语句中的一种结构。比如，类似于select，where，for这样的语句均以分支的节点来表示。对于查询语句select name from Name where person_id =1和for $i in doc(“Name.xml”) where $i/person/id=1 return $i/person/name其在关系数据和XML数据库下其抽象语法树分别为：

expr
(图1：select name from Name where person_id=1 的抽象语法树)
expr_xqy
(图2：for $i in doc(“Name.xml”) where $i/person/id=1 return $i/person/name的抽象语法树)

为了能够更好以及动态配置SQL语句到XQuery语句的转换，我们在基于抽象语法树的基础上定义一组基于抽象语法树的转换规则，当一个SQL语句生成抽象语法树后，在该抽象语法树上面应用我们所定义的一组规则，将SQL语句所生成的抽象语法树的节点根据规则进行转换，将其转换为Xquery语句所需要的抽象语法树形式，在完成转换后，可以根据该抽象语法树生成该SQL语句所所对应的等价XQuery语句。

其中转换规则如下：

1）SQL语句中的where子句，将其转换为XQuery的where子句并将SQL语句中的where子句中的参数信息作为Xquery的Where子句中的参数信息。

2）SQL中的from子句，将其转换为XQuery中的for子句并将from子句中的表信息作为XQuery中for子句的doc或者container，collection函数的参数。

3）SQL中的select子句，将其转换为XQuery中的return子句并将select子句中的参数作为XQuery的return子句参数

4）SQL中的insert子句，将其转换为XQuery中的insert子句并将SQL的insert子句中的参数作为XQuery中的insert子句的参数。

5）SQL中的update子句，将其转换为XQuery中的replace子句并将SQL的update子句中的参数作为XQuery中replace子句的参数。

6）SQL中的delete子句，将其转换为XQuery中的delete子句并将SQL的delete子句中的参数作为XQuery中delete子句的参数。

对于上述的转换规则，我们可以将其保存至名为rules.y的文件中以便用户可以自定义转换规则，从而可以动态的满足不同用户的需求。

完成上述的转换规则的定义后，SQL语句转换XQuery语句的具体步骤可以分为如下的过程：

1）原始抽象语法树的生成阶段。

当一条SQL语句到达系统后，我们首先会将该SQL语句生成原始的抽象语法树，该过程由我们上述所说的Lex/Bison根据预先定义的SQL语义规则来生成。

2）规则读取阶段

在为SQL语句生成原始抽象语法树后，我们将预先定义的规则文件rules.y读入系统中以便后续步骤使用。

3）预定义规则rules.y应用阶段

将上述预先定义的转换规则应用于SQL语句所生成的原始抽象语法上，处理的规则为首先处理原始抽象语法树的叶子节点：根据叶子节点的类型分别应用上述的规则生成其所对应的XQuery抽象语法树上的相对应的节点，如果该节点的类型非系统所支持的类型，则系统抛出异常错误并终止规则应用。

当处理完叶子节点后，我们将已处理完成的叶子节点从抽象语法树中移除，此时该叶子节点的父亲节点由原先的非叶子节点变成叶子节点，然后对该新叶子节点应用转换规则，该节点所生成的XQuery抽象语法树的节点作为刚才所生成的已有XQuery抽象语法树节点的父节点。我们重复上述的处理过程直到SQL所生成的原始的抽象语法树都已完成规则转换。

4）XQuery语句生成阶段

在完成SQL抽象语法树的规则应用后，我们获得了一颗新的XQuery抽象语法树，在我们对其进行遍历后便可以获得其所对于的XQuery语句。

我们对SQL的抽象语法树的处理后，我们将得到一个其所对应的XQuery抽象语法树，我们可知XQuery抽象语法树在语义上与SQL抽象语法树是两棵等价的语法树，因此该种转换不会导致语义的丢失或者语义的转义。

#3. 结论.

本文提供了一种灵活的SQL语句与XQuery语句转换方法。对于较于传统的人工转换的方式下需要相关人员不但要熟知SQL语句同时也需要其熟知XQuery语句，这必然会增加数据库的维护成本。相对于传统方式新的方法采用系统根据相应的转换规则自动转换的方式进行，其具有快速准确的优点。同时，通过自定义转换规则可以做到SQL与其它相关语句之间的转换，为应用层的数据转换提供了一种全新的方式方法。

XML Database中索引方案

发表于由
  • XML Database中索引方案

#0. 前言背景.

  经过数年的开发XML数据已经在医院大数据分析平台中使用，但是在使用的过程中发现了诸多的bug；例如：有导致系统崩溃；有客户特殊需求；有系统性能效率过低等等。但是，经过大家的努力，现有系统至少已经在实际的项目中得到了一定程度的验证，系统的文档性，系统的健壮性得到了显著的提高，但仍然存在着显著的软肋，而该部分就是我们下面着重要讨论的部分—索引的高效使用。

FounderXML数据库对于索引的使用经历下面几个步骤的演化：（1）全路径索引；（2）部分路径索引；（3）属性索引。在数据库开发的早期为了使得谓词、where语句中的条件能快速的获得结果，我们建立了两种类型的索引：（1）字符类型索引；（2）数值类型索引。

上述的两种字符类型索引和数值索引，由加载文档的过程系统根据数据的类型自动创建字符索引或者是数值索引，通过XML文件在解析的过程中对于XML节点中的属性值和文本节中的文本进行相应判断，用以确定所建立的索引的类型。在索引建立完成后，对于查询语句中的谓词或者where子句中的条件数据库会根据条件的类型来判断使用何种索引？例如：当条件为a=’10’或者a=”10”此类，使用字符作为条件时，系统会默认选择使用字符索引来进行查询；但当查询条件为a=10或者a=10.01时，此时系统默认选择使用数值索引进行查询；

随着数据量的集聚增加，索引文件所占用的系统空间越来越多，当数据与索引之比例增加时，FounderXML数据库对于磁盘空间的需求越来越大，但在某些用户的实际应用场景下，广泛采用虚拟机环境作为实际运行环境，在该环境下磁盘资源，内存资源，cpu资源等受到严格限制。因此，对于磁盘空间大小的使用提出了需求，为了解决索引文件磁盘空间占用过大的问题，为此我们采用了部分路径索引方案：以XML路径为单位进行组织，将路径相同的数据组织在一颗索引树上，对于查询中暂时不需要使用的路径，将不再建立相应的字符索引和数值索引，从而达到减小磁盘空间的目的（此种解决方案是在系统中的XML结构存在大量相似结构的情况下，对于数据库中的XML文件为大量不同结构的XML文件，此种解决方案将失去其有效性）。

为了进一步的减少索引所占磁盘空间，我们在部分路径索引的基础上使用属性索引来进一步的优化索引的创建和使用；通过对路径索引的进一步细化，使得我们需要创建索引的数据进一步的减少，从而达到减少磁盘空间开销的目的。 虽然，属性索引可以进一步的减少磁盘空间的开销，同时提供索引查询时的效率，但是考虑到系统中索引使用策略，当前系统无法做到智能的对于比较条件中的逻辑表达式进行优化并选择合适的索引策略（当前索引的选择策略：选择条件表达式中的第一个逻辑变量作为索引列）。因此，我们需要系统中对于索引使用的策略进行进一步的优化。

#1. 当前系统索引选择策略及存在问题.

   当前系统对于一个比较复杂的逻辑比较条件未经过任何逻辑优化，即使是最简单的表达式去重优化，常量表达式计算等；再者，对于逻辑表达式中的索引选择是默认按照表达式中的第一个逻辑变量进行选择。例如：对于查询条件： where /a/b/c[@a=”name”] and /d/e/f[@b=10]，当前系统的默认选择/a/b/c[@a=”name”]作为索引使用，对于/a/b/c[@a=”name”]使用索引是否优于对/d/e/f[@b=10]的索引使用则为做考量。该种做法在用户熟知当前数据库中的XML文档结构以及数据分布的情况下，可以通过手工的调整索引使用：即通过查询语句写法来确定索引的使用策略。例如：where /a/b/c[@a=”name”] and /d/e/f[@b=10] 和where /d/e/f[@b=10] and /a/b/c[@a=”name”]，两种写法决定了不同索引列的使用。对于前者使用/a/b/c作为索引列；而对于后者查询条件则使用/d/e/f作为索引列。

当用户手工编写查询语句时，我们可以通过人为的操作来选择索引的使用，但是在实际的应用场景下，查询语句由应用系统自动产生，而应用系统所产生查询语句其查询效率（索引使用选择策略）无法与经验丰富的开发人员所写出的查询语句相提并论，两者的执行效率可能相差数倍甚至上百倍。

同时，当前系统中的另外一个很大的问题时，系统只是使用一个列作为索引列，无论当前系统中创建多少的索引。例如 where /a/b/c[@a=”name”] and /d/e/f[@b=10]，即使分别在/a/b/c和/d/e/f中创建两条索引，在实际的使用过程中只是使用了其中的一条索引，如何高效的尽可能使用所有的索引也是我们值得思考的地方。

最后，由于当前系统中对于数据的统计信息不完整，使得我们在对于是否使用索引，以及使用那个索引提出了一定的挑战；因为，并非所有的索引扫描均能达到最高的查询效率，对于选择率高的查询条件，使用索引查询反而会大大的降低查询效率；而对于选择率较低的数据反而使用索引查询则是一个较好的选择。同时，对于聚集函数和窗口函数也同样会影响到索引的使用，这点也需要我们给以足够的注意。

#2. 索引选择策略.

   关系数据库有一套完整的选择使用策略，该策略的标准是：尽可能的使用上所创建的索引。对于无法使用的场景下，关系数据库采用将该条件作为filter 操作的条件进行过滤。

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

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

Table: A

colA （colA_Index） colB (colB_Index) colXXX
/ / /

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函数输出为最终的查询结果。 其他情况就不在这里赘述，有兴趣的可以查看关系数据库查询计划进行验证。

#3. XML DBMS索引目标.

   为了使用XMLDB中所有建立的索引，我们首先需要知道当前系统中存在着何种索引，以及每一类索引的具体的信息。类似于关系数据库中的索引信息表，XMLDB中仍然以元数据表来描述当前系统中存在的所有索引。该元数据表中描述了系统中索引的类型，索引所建的路径，索引的类型，索引的优先级等信息。用户可以通过一系列的命令完成对系统中索引的操作。例如：创建索引，修改索引类型，修改索引的优先级等操作。

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

在阐述系统实现之前，我们要明确几个概念：（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语句在实际的应用中存在着一定的模式，使得我们能够将某些规则应用于该查询语句中成为可能；并且完成基于规则的查询优化后，系统可以利用代价信息进行进一步的基于代价的优化。

#4. 系统优化方案.

  • 概述

相较于传统的关系数据库中常用的两类优化策略：基于规则的优化和基于代价的优化策略，现有的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命令，在执行该命令后，系统将重新执行统计计算，将统计后的信息进行更新。

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

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

#5. 总述.

  当前系统中关于查询优化部分代码，在进行优化化时，存在着将某些过多的功能实现由一个优化器来完成，或者存在着将某些相关数据进行割裂后分别处理的现象。例如：对于 where a and b这种语句当前系统在优化过程中分别将a 和b进行割裂开，事实上我们应该将 a and b作为一个统一的条件来进行统一规划和优化处理，形成优化后的统一标准化的逻辑表达式，这样有利于后续优化器的优化工作。

How to Add a Document.

发表于由
  • About adding a document to an existed container in XML Database.

#0. prerequisite

#0: In this document, we will explain how the xquery adds an xml doucment into existed container. All the explanations are based on the query Statement:“addDoc test.xdb test.xml -f path;”
When you type a command into console, the server gets the command line and parses the command line, turns it into a specific request. Taking addDoctest.xdb test.xml -f d:\books.xml as an instance, the server receives the user typed command, then, server will perceive the user intention. After knowing the request type, the server will do actually works.

#1. In details

the BDBExecutor will invoke the member function execute() to do adding the document.

adddoc_step_1

In fact, what executor executes is xxxOperation. In this case, the BDBAddDocByLocalFileOperation does the real work. After checking the privilege of the container, container calls the function putDocument to add a document.

adddoc_step_2

It invokes the container::addDocumentInternal to put a document into a container. It shows by the picture below.

adddoc_step_3

#2. How to do XML processing with SAX?

SAX (Simple API for XML) is an event-based sequential access parser API developed by the XML-DEV mailing list for XML documents.[1] SAX provides a mechanism for reading data from an XML document that is an alternative to that provided by the Document Object Model (DOM). Where the DOM operates on the document as a whole, SAX parsers operate on each piece of the XML document sequentially.

    A parser that implements SAX (i.e., a SAX Parser) functions as a stream parser, with an event-driven API.[1] The user defines a number of callback methods that will be called when events occur during parsing. The SAX events include (among others):

XML Element Starts and Ends
XML Processing Instructions
XML Comments
XML Text nodes

Some events correspond to XML objects that are easily returned all at once, such as comments. However, XML elements can contain many other XML objects, and so SAX represents them as does XML itself: by one event at the beginning, and another at the end. Properly speaking, the SAX interface does not deal in elements, but in events that largely correspond to tags. SAX parsing is unidirectional; previously parsed data cannot be re-read without starting the parsing operation again.
There are many SAX-like implementations in existence. In practice, details vary, but the overall model is the same. For example, XML attributes are typically provided as name and value arguments passed to element events, but can also be provided as separate events, or via a hash or similar collection of all the attributes. For another, some implementations provide “Init” and “Fin” callbacks for the very start and end of parsing; others don’t. The exact names for given event types also vary slightly between implementations. Given the following XML document:

adddoc_step_4
This XML document, when passed through a SAX parser, will generate a sequence of events like the following:

XML Element start, named DocumentElement, with an attribute param equal to “value”
XML Element start, named FirstElement
XML Text node, with data equal to “Some Text”
XML Element end, named FirstElement

Processing Instruction event, with the target some_pi and data some_attr=”some_value” (the content after the target is just text; however, it is very common to imitate the syntax of XML attributes, as in this example)

XML Element start, named SecondElement, with an attribute param2 equal to “something”
XML Text node, with data equal to “Pre-Text”
XML Element start, named Inline
XML Text node, with data equal to “Inlined text”
XML Element end, named Inline
XML Text node, with data equal to “Post-text.”
XML Element end, named SecondElement
XML Element end, named DocumentElement

Note that the first line of the sample above is the XML Declaration and not a processing instruction; as such it will not be reported as a processing instruction event (although some SAX implementations provide a separate event just for the XML declaration).
The result above may vary: the SAX specification deliberately states that a given section of text may be reported as multiple sequential text events. Many parsers, for example, return separate text events for numeric character references. Thus in the example above, a SAX parser may generate a different series of events, part of which might include:

XML Element start, named FirstElement
XML Text node, with data equal to “¶” (the Unicode character U+00b6)
XML Text node, with data equal to ” Some Text”
XML Element end, named FirstElement.

It invokes the function, prepareAddDocument(). In this function, first of all, make sure the document is a valid document. And then goes into Document class to do putting operation. therefore, Doucment::getContentAsEventSource plays this role.

adddoc_step_5
The system reads the file as a file stream; all operations are based on this file stream. The class member function Document::stream2events function. After setting the parser and translator up, the system will go to indexAddDocument. Perform the actual parsing steps. As we have discussed above, all things are taken as events, Such as startAElement, startAText, etc. In function Container::indexAddDocument(), it start parsing.
adddoc_step_6
adddoc_step_7
 After starting, the parser will do parse. In NsSAX2Reader, this class will do internal parsing. The following code illustrated that.

void NsSAX2Reader::parse(XmlInputStream **is)
{
XmlInputStreamWrapper isw(is);
parse(isw);
}

In parsing phrase, at first, the scanner will scan the document. WFXMLScanner::scanDocument does that function. It will invoke the NsXercesTranscoder::startDocument. The call stack shows that.

adddoc_step_8
In function “WFXMLScanner::scanContent()”, the parser do parsing the xml content. According to the type of current token, it goes into different branches, such as scanCDSection(), scanComment(), scanEndTag(), etc. And, in function scanContent(), it starts the function scanStartTagNS of WFXMLSCanner to process the xml string. When it meets a start tag, the system will go into function NsSAX2Reader::startElement(), and the call stack above illustrate that.
From the function NsHandlerBase::startElem(), the code below show that how and when write the node down.

_doc->completeNode(tprev, nodesz, needUpdatePrevious_);
If the previous node is not null, it means before creating a new node, it should write the previous node down. Function completeNode used to store the specific node, then, sets the current node infor.

adddoc_step_9
In NsHandlerBase::startElem(), parser will generate the nodes according the type.
adddoc_step_10