Multi-objective parametric query optimization
Multi-objective parametric query optimization
复制标题
多目标参数查询优化
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Christoph E. Koch
中科院分区：
文献类型：
--
作者：
Immanuel Trummer;Christoph E. Koch
经典查询优化根据一个成本度量比较查询计划，并将每个计划与恒定成本值相关联。本文介绍了多目标参数查询优化(MPQO)问题，其中查询计划根据多个代价指标进行比较，并且根据给定的指标将给定计划的代价建模为依赖于多个参数的函数。例如，成本度量可以包括执行时间或货币费用；参数可以表示在优化时间未指定的查询谓词的选择性。MPQO概括了参数查询优化(允许多个参数，但只允许一个代价度量)和多目标查询优化(允许多个代价度量，但不允许参数)。我们形式化地分析了新的MPQO问题，并说明了现有算法不适用的原因。我们提出了一种求解MPQO的通用算法和一种特殊形式的分段线性规划代价函数的MPQO算法。我们证明了这两种算法都能找到所有相关的查询计划，并通过实验评估了第二种算法在多个场景下的性能。
Classical query optimization compares query plans according to one cost metric and associates each plan with a constant cost value. In this paper, we introduce the multi-objective parametric query optimization (MPQO) problem where query plans are compared according to multiple cost metrics and the cost of a given plan according to a given metric is modeled as a function that depends on multiple parameters. The cost metrics may, for instance, include execution time or monetary fees; a parameter may represent the selectivity of a query predicate that is unspecified at optimization time. MPQO generalizes parametric query optimization (which allows multiple parameters but only one cost metric) and multi-objective query optimization (which allows multiple cost metrics but no parameters). We formally analyze the novel MPQO problem and show why existing algorithms are inapplicable. We present a generic algorithm for MPQO and a specialized version for MPQO with piecewise-linear plan cost functions. We prove that both algorithms find all relevant query plans and experimentally evaluate the performance of our second algorithm in multiple scenarios.