Turbo-Charging Estimate Convergence in DBO

Summary: Turbo DBO speeds estimate convergence for multi-table, disk-based queries by caching partial-match tuples in a randomized search. Novel partial-match discovery seeds growth toward final results, lowering TTU under skew and selective predicates. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h573ca171b55f92c4
Venue: VLDB
Year: 2009
Pagerank: 7.5328015e-05
Overall Rank: 3,213 | 78.40%
DOI: 10.14778/1687627.1687675

Incoming Non-self Citations Over Time

Authors

1. Alin Dobra (University of Florida)
2. Chris Jermaine (Rice University; University of Florida)
3. Florin Rusu (University of Florida)
4. Fei Xu (University of Florida)

BibTeX Citation

@article{dobra_vldb09,
        title = {{Turbo-Charging Estimate Convergence in DBO}},
        author = {Dobra, Alin and Jermaine, Chris and Rusu, Florin and Xu, Fei},
        journal = {PVLDB},
        series = {{VLDB} '09},
        doi = {10.14778/1687627.1687675},
        url = {https://doi.org/10.14778/1687627.1687675},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
596	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015785583
795	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013938779
1,428	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010693831
2,027	Database Learning: Toward a Database that Becomes Smarter Every Time	2017	SIGMOD	9.1618139e-05
2,456	A Sampling Algebra for Aggregate Estimation	2013	VLDB	8.4377192e-05
4,856	Neighbor-Sensitive Hashing	2016	VLDB	6.3798143e-05
5,831	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB	5.9782109e-05
5,877	BlinkML: Efficient Maximum Likelihood Estimation with Probabilistic Guarantees	2019	SIGMOD	5.9627218e-05
6,004	Approximate Query Engines: Commercial Challenges and Research Opportunities	2017	SIGMOD	5.9166815e-05
7,978	Biathlon: Harnessing Model Resilience for Accelerating ML Inference Pipelines	2024	VLDB	5.4136835e-05
8,216	Wander Join: Online Aggregation for Joins	2016	SIGMOD	5.3764262e-05
8,223	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	5.3751366e-05
8,850	SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms	2023	VLDB	5.2645282e-05
9,184	PR-Join: A Non-Blocking Join Achieving Higher Early Result Rate with Statistical Guarantees	2010	SIGMOD	5.211541e-05
12,052	BitGourmet: Deterministic Approximation via Optimized Bit Selection	2020	CIDR	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
9	Online Aggregation	1997	SIGMOD	0.00076195956
27	Database Architecture Optimized for the New Bottleneck: Memory Access	1999	VLDB	0.0005158963
77	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00036828234
135	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00029866033
492	Error-Constrained COUNT Query Evaluation in Relational Databases	1991	SIGMOD	0.00017408001
564	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00016296665
1,090	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012077577
1,108	Maximizing the Output Rate of Multi-Way Join Queries over Streaming Information Sources	2003	VLDB	0.00011991195
1,820	A Scalable Hash Ripple Join Algorithm	2002	SIGMOD	9.5690887e-05
5,589	Derby/S: A DBMS for Sample-Based Query Answering	2006	SIGMOD	6.0740498e-05
8,543	The DBO Database System	2008	SIGMOD	5.3187151e-05
9,195	A Bayesian Method for Guessing the Extreme Values in a Data Set	2007	VLDB	5.2100166e-05
13,050	Online Estimation For Subset-Based SQL Queries	2005	VLDB	4.9793485e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,217	A Disk-Based Join With Probabilistic Guarantees*	2005	SIGMOD
2	487	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD
3	1,596	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
4	4,415	Estimating Compilation Time of a Query Optimizer	2003	SIGMOD
5	470	Optimization of Large Join Queries	1988	SIGMOD
6	3,041	Configuration-Parametric Query Optimization for Physical Design Tuning	2008	SIGMOD
7	569	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD
8	8,543	The DBO Database System	2008	SIGMOD
9	8,971	A Fast Randomized Algorithm for Multi-Objective Query Optimization	2016	SIGMOD
10	1,090	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD