QUEST: An Exploratory Approach to Robust Query Processing

Database Systems Lab
Indian Institute of Science

[Abstract] [Related Publications] [Video] [Team]

Selectivity estimates for optimizing OLAP queries often differ significantly from those actually encountered during query execution, leading to poor plan choices and inflated response times. Prior approaches to address this long-standing problem have attempted to either reduce the errors themselves, or reduce their adverse impact on the run-time performance.

We have recently proposed a conceptually new approach (Plan Bouquet) to address this problem, wherein the compile-time estimation process is completely eschewed for error-prone selectivities. Instead, a small "bouquet" of plans is identified from the set of optimal plans in the query's selectivity error space, such that at least one among this subset is near-optimal at each location in the space. Then, at run time, the actual selectivities of the query are incrementally "discovered" through a sequence of partial executions of bouquet plans, eventually identifying the appropriate bouquet plan to execute. The duration and switching of the partial executions is controlled by a graded progression of isocost surfaces projected onto the optimal performance profile. This construction lends itself to guaranteed worst-case performance bounds and repeatable execution strategies across multiple invocations of a query.

We have evaluated the proposed technique with PostgreSQL engine on TPC-H and TPC-DS benchmark environments. This prototype implementation of the "plan bouquet" technique is known as QUEST (QUery Execution without Selectivity esTimation) .

Our experimental results indicate that, even with conservative assumptions, it delivers substantial improvements in the worst-case behavior of plan choices, without impairing the average-case performance, as compared to the native optimizers of these systems. Overall, the bouquet approach provides novel guarantees that open up new possibilities for robust query processing.

Related Publications
Plan Bouquets: Query Processing without Selectivity Estimation
Anshuman Dutt and Jayant Haritsa
Proc. of ACM SIGMOD 33rd Intl. Conf. on Management of Data, Snowbird, USA, June 2014.
QUEST: An Exploratory Approach to Robust Query Processing (demo)
Anshuman Dutt, Sumit Neelam and Jayant Haritsa
Proc. of 40th Intl. Conf. on Very Large Data Bases (VLDB), Hangzhou, China, September 2014
(Received Excellent Demo Award).

Platform-independent Robust Query Processing
Srinivas Karthik, Jayant Haritsa, Sreyash Kenkre and Vinayaka Pandit
Proc. of 32nd Intl. Conf. on Data Engineering (ICDE), Helsinki, Finland, May 2016
(Received the Best Student Paper Award).
Plan Bouquets: A Fragrant Approach to Robust Query Processing
Anshuman Dutt and Jayant Haritsa
ACM Trans. on Database Systems (TODS), vol. 41, issue 2, article no. 11, June 2016.

QUEST demonstration video (mp4 format)[15MB]

Primary QUEST Contributors (in chronological order of participation)

  • Jayant Haritsa (Project Lead)
  • Anshuman Dutt (PhD, CSA, IISc)
  • Sumit Neelam (ME, CSA, IISc)
  • C Rajmohan (ME, CSA, IISc)
  • Lohit Krishnan (ME, CSA, IISc)
  • Srinivas Karthik (PhD, CSA, IISc)