ROX: run-time optimization of XQueries
ROX: run-time optimization of XQueries
复制标题
ROX：XQuery 的运行时优化
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
R. A. Kader
中科院分区：
文献类型：
--
作者：
R. A. Kader
目前，由于缺乏良好的 XQuery 基数估计和成本模型，结合许多 XPath 步骤和连接的复杂 XQuery 的优化受到阻碍。此外，即使是最先进的关系查询优化仍然难以应对随着计划大小以及相关连接和选择的影响而增加的成本模型估计错误。在这项研究中，我们建议从根本上摆脱分离查询编译和查询执行阶段的传统路径，通过让优化器执行、具体化部分结果并使用基于采样的估计技术来观察中间体的特征。所提出的技术将连接图作为输入，其中边是等连接或 XPath 步骤，并且执行环境提供值和结构连接算法，以及基于结构和基于值的索引。虽然使用采样的运行时优化消除了经典优化器的许多漏洞，但它在控制资源使用方面带来了自己的挑战，无论是中间体的具体化，还是使用采样的计划探索的成本。我们的方法通过将运行时搜索空间限制为所谓的“零投资算法”来解决这些问题，该算法可以保证采样在样本大小上严格线性。ROX 用于采样的所有运算符和 XML 值索引都具有零投资属性。我们对大型 XML 数据集进行了广泛的实验评估，结果表明我们的运行时查询优化器以稳健的方式找到良好的查询计划，并且运行时开销有限。
Optimization of complex XQueries combining many XPath steps and joins is currently hindered by the absence of good cardinality estimation and cost models for XQuery. Additionally, the state-of-the-art of even relational query optimization still struggles to cope with cost model estimation errors that increase with plan size, as well as with the effect of correlated joins and selections. In this research, we propose to radically depart from the traditional path of separating the query compilation and query execution phases, by having the optimizer execute, materialize partial results, and use sampling based estimation techniques to observe the characteristics of intermediates. The proposed technique takes as input a Join Graph where the edges are either equi-joins or XPath steps, and the execution environment provides value- and structural-join algorithms, as well as structural and value-based indices. While run-time optimization with sampling removes many of the vulnerabilities of classical optimizers, it brings its own challenges with respect to keeping resource usage under control, both with respect to the materialization of intermediates, as well as the cost of plan exploration using sampling. Our approach deals with these issues by limiting the run-time search space to so-called "zero-investment algorithms for which sampling can be guaranteed to be strictly linear in sample size. All operators and XML value indices used by ROX for sampling have the zero-investment property. We perform extensive experimental evaluation on large XML datasets that shows that our run-time query optimizer finds good query plans in a robust fashion and has limited run-time overhead.