QUEST: An Exploratory Approach to Robust Query Processing

摘要

In modern database systems, accurate estimations of predicate selectivities are a basic requirement for the effective optimization of declarative SQL queries. For example, consider EQ, the simple SPJ query shown in Figure 1 - here, the optimizer needs to estimate the selectivities of a selection predicate (p_retailprice ＜ 1000) and two join predicates (part (Δ) lineitem, lineitem (Δ) orders). select ~* from lineitem, orders, part where p_partkey = l_partkey and Lorderkey = o_orderkey and p_retailprice ＜ 1000 Figure 1: Example Query (EQ) In practice, however, compile-time selectivity estimates are often significantly in error with respect to the actual values subsequently encountered during query execution. These errors mislead the optimizer into making poor execution plan choices, resulting in substantially inflated query response times. Over the past few decades, the database research community has spent considerable efforts to address the above problem, which is of immediate relevance to currently operational systems. The proposed techniques (see for a comprehensive survey) include sophisticated meta-data structures, feedback-based statistical adjustments, and on-the-fly re-optimization strategies. While this rich body of literature features several innovative formulations, a common limitation is their inability to provide robust query processing, as per the following definition.