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: 10052
Venue: VLDB
Year: 2009
Pagerank: 7.6911286e-05
Overall Rank: 3,157 | 78.35%
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
593	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00016027871
802	Random Sampling over Joins Revisited	2018	SIGMOD	0.00013907725
1,401	Knowing When You’re Wrong: Building Fast and Reliable Approximate Query Processing Systems	2014	SIGMOD	0.00010889902
1,995	Database Learning: Toward a Database that Becomes Smarter Every Time	2017	SIGMOD	9.3403665e-05
2,413	A Sampling Algebra for Aggregate Estimation	2013	VLDB	8.6116764e-05
4,927	Neighbor-Sensitive Hashing	2016	VLDB	6.4426453e-05
5,743	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB	6.1025457e-05
5,785	BlinkML: Efficient Maximum Likelihood Estimation with Probabilistic Guarantees	2019	SIGMOD	6.0892672e-05
5,906	Approximate Query Engines: Commercial Challenges and Research Opportunities	2017	SIGMOD	6.0457047e-05
7,847	Biathlon: Harnessing Model Resilience for Accelerating ML Inference Pipelines	2024	VLDB	5.5330423e-05
8,051	Wander Join: Online Aggregation for Joins	2016	SIGMOD	5.4997517e-05
8,204	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	5.4667903e-05
8,698	SkinnerMT: Parallelizing for Efficiency and Robustness in Adaptive Query Processing on Multicore Platforms	2023	VLDB	5.3830073e-05
9,017	PR-Join: A Non-Blocking Join Achieving Higher Early Result Rate with Statistical Guarantees	2010	SIGMOD	5.3311284e-05
11,749	BitGourmet: Deterministic Approximation via Optimized Bit Selection	2020	CIDR	5.093636e-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.00077458002
29	Database Architecture Optimized for the New Bottleneck: Memory Access	1999	VLDB	0.00052093615
75	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00037277061
131	Ripple Joins for Online Aggregation	1999	SIGMOD	0.00030424509
484	Error-Constrained COUNT Query Evaluation in Relational Databases	1991	SIGMOD	0.00017746696
553	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00016590619
1,064	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012336248
1,093	Maximizing the Output Rate of Multi-Way Join Queries over Streaming Information Sources	2003	VLDB	0.00012218435
1,785	A Scalable Hash Ripple Join Algorithm	2002	SIGMOD	9.7702627e-05
5,460	Derby/S: A DBMS for Sample-Based Query Answering	2006	SIGMOD	6.2106757e-05
8,398	The DBO Database System	2008	SIGMOD	5.4342404e-05
9,026	A Bayesian Method for Guessing the Extreme Values in a Data Set	2007	VLDB	5.3295983e-05
12,760	Online Estimation For Subset-Based SQL Queries	2005	VLDB	5.093636e-05

Semantically Similar Papers

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