Turbo-Charging Estimate Convergence in DBO

Alin Dobra, Chris Jermaine, Florin Rusu, Fei XuPVLDB 2009 · DOI

TL;DR

This paper introduces Turbo-DBO, a novel database system that significantly speeds up the process of obtaining statistically meaningful query estimates. By intelligently remembering and building upon partial query results, Turbo-DBO dramatically reduces the "time to utility" (TTU) for complex queries, especially those involving multiple joins or highly selective predicates, compared to its predecessor, DBO.

What Problem Does This Paper Address?

Modern data warehousing systems often provide little to no feedback on query results until the entire query completes, which can take hours. This lack of intermediate feedback hinders query debugging and interactive data exploration. Online Aggregation (OLA) systems, like DBO, aim to solve this by providing continuously improving estimates with confidence bounds. However, DBO can still be slow to converge to a useful estimate, particularly for complex queries involving many table joins or highly selective filters, where finding matching tuples by chance becomes very unlikely. Turbo-DBO tackles this inefficiency by improving the speed at which these estimates become reliable.

Methods

Turbo-DBO builds upon the foundation of DBO but introduces a key innovation: the "in-memory join" (IMJ) component. Unlike DBO, which discards intermediate results when buffers are refilled, Turbo-DBO's IMJ actively stores and combines "partial match" tuples. These are tuples that satisfy some, but not all, of the query's join predicates. The IMJ maintains these partial results as "chains" and incrementally tries to extend them with new incoming tuples. When a chain successfully spans all relations and satisfies all predicates, it forms a "lucky" output tuple, contributing to the estimate.

Key techniques include:

  • Partial Match Tuples (Chains): Storing and building upon tuples that satisfy a subset of join conditions.
  • Timestamp-based Randomization: Assigning random timestamps to tuples to simulate random arrival order and ensure statistical properties.
  • Optimized Building Order: A greedy strategy to determine the order of relations for processing to minimize memory usage.
  • Subsampling: A mechanism to reduce memory footprint when exceeding hard limits, intelligently choosing which relation to subsample to minimize variance.

Datasets

The experiments were conducted using a 20GB instance of the TPC-H benchmark database. For data skew experiments, the TPC-H data generator was modified to produce data with varying degrees of skew using Zipf distributions.

Key Insights and Ideas

  • The Power of Partial Results: The core insight is that remembering and incrementally building upon partial join results, rather than discarding them, dramatically increases the chances of finding complete, valid tuples. This is analogous to not giving up on a puzzle piece just because you haven't found its immediate neighbors yet.
  • Timestamping as a Randomization Tool: Using random timestamps to order tuple processing is a clever way to achieve the statistical properties needed for unbiased estimation without relying on actual random sampling of the entire dataset upfront.
  • Intelligent Memory Management: The ability to intelligently choose which relation to subsample when memory is constrained is crucial for maintaining estimate accuracy in the face of data skew or limited resources. This is a significant improvement over a less adaptive approach.

Key Results

  • Dramatic TTU Reduction: For queries joining five large tables, Turbo-DBO reduced the "time to utility" (TTU) by almost 80% compared to the original DBO.
  • Significant Improvement on Standard Queries: Even for more typical TPC-H workloads, Turbo-DBO achieved an average TTU reduction of nearly 30% without data skew and over 60% with skew.
  • Robustness to Data Skew: Turbo-DBO showed remarkable resilience to data skew, with its performance degradation only becoming significant at extreme skew levels, unlike the original DBO.
  • Accurate Confidence Bounds: Experimental results confirmed that Turbo-DBO's confidence bounds were statistically accurate, closely matching the expected 95% coverage.

Limitations and Future Work

  • Performance Overhead: The current implementation of Turbo-DBO incurs a performance overhead compared to a traditional system without estimation capabilities. The authors attribute this to a naive IMJ implementation and suggest that a more optimized implementation could significantly reduce this cost.
  • Handling Complex Predicates: The paper notes that correlated sub-queries and DISTINCT clauses are not explicitly handled and represent interesting future research problems.
  • Further IMJ Optimization: The authors explicitly mention that the IMJ implementation was a prototype and could be significantly improved, particularly in terms of cache performance.

Summary updated

BibTeX
@article{dobra2009turbo,
  author = {Alin Dobra and Chris Jermaine and Florin Rusu and Fei Xu},
  title = {{Turbo-Charging Estimate Convergence in DBO}},
  journal = {Proc. VLDB Endow.},
  year = {2009},
  doi = {10.14778/1687627.1687675},
}
Figure