Multi objective parametric query optimization
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.
SGMD