优化XQuery路径表达式中的排序和去重及高效索引方法

### 优化XQuery路径表达式中的排序和去重及高效索引方法 #### 一、XQuery路径表达式优化 在XQuery路径表达式处理中，排序和去重操作的优化至关重要。 1. **状态表示与转换** - 仅含单个无括号名称的状态，其转换信息在其他片段给出。 - 对于所有常规状态，每个轴都有对应的转换，通过不同箭头表示： - 实心箭头：表示此步骤后无需σ或δ操作。 - 虚线箭头：表示需要δ操作。 - 点线箭头：表示需要σ; δ操作。 - 标有A−{↑, ↓}的边表示除↑和↓之外所有轴的转换。按此自动机规定构建评估计划，可得到最小去重整洁评估计划。 2. **算法实现** - 在Galax XQuery引擎中实现了相关算法，以及整洁和宽松方法。Galax是XQuery 1.0规范的完整实现，架构简单且文档完善。 - **规范化操作**：在每个路径步骤后引入按文档顺序排序和去重操作，使表达式符合整洁定义。 - **ddo优化**：在查询重写阶段应用。ddo自动机的起始状态需要max1属性，可通过以下两种方式推断： - 若启用静态类型，可从每个子表达式计算类型的基数精确推导max1属性。但静态类型是XQuery的可选特性，支持的实现较少。 - 对于不支持静态类型的实现，可使用简单静态分析推导。如fn:doc和fn:root函数、fs:dot变量以及所有由for表达式绑定的变量始终具有max1属性。 - **算法流程**： - 当推导出max1属性时算法启动。 - 若中间结果可能包含重复项，注入distinct运算符；若最终结果可能无序，注入docorder运算符。 - 最终重写的表达式传递给编译器，编译器构建编译评估计划并传递到评估阶段。 3. **实验结果** - **XMark基准测试**：使用XMark基准测试套件对不同大小文档进行实验。XMark包含20个查询，涵盖XQuery多数特性，且所有查询至少包含一个路径表达式。 - 优化效果：在所有规范化XMark查询的239个不同文档顺序操作中，ddo优化后仅剩余3个docorder操作。 - 对复杂路径表达式查询的影响：如查询6、7、14和19，随着输入文档从10MB增加到50MB，ddo优化对评估时间的影响增大。例如，在20MB文档上，查询6优化后运行速度快5.75倍，查询7、14和19加速2 - 6倍。这些查询频繁使用后代或自身轴，产生的大中间结果排序成本高，且输入文档越大加速越明显。 - **不同方法对比**： - 对于多数XMark基准测试，宽松方法和去重整洁方法效果相当，因这些基准测试的路径表达式在中间步骤不产生重复项。 - 但对于某些查询，宽松技术在路径表达式长度增加时扩展性差。这是由于中间结果存在重复节点，若不立即去重，路径表达式后续步骤会对相同节点多次冗余应用。若后续步骤也产生重复项，中间结果大小会呈指数级增长。如对(∗//)n∗形式的路径表达式，n = 1, 2, 3, 4应用于52MB和169MB文档时，宽松方法评估时间随//步骤数量呈指数级增加。去重整洁方法结合了宽松方法在文档大小上的可扩展性和整洁方法在路径表达式大小上的可扩展性。 以下是一个简单的mermaid流程图，展示算法实现流程： ```mermaid graph TD; A[开始] --> B[推导max1属性]; B -- 有max1属性 --> C[启动算法]; C --> D{中间结果有重复项?}; D -- 是 --> E[注入distinct运算符]; D -- ```