Turbo-Charging Estimate Convergence in DBO

DBO is a database system that utilizes randomized algorithms to give statistically meaningful estimates for the final answer to a multi-table, disk-based query from start to finish during query execution. However, DBO's "Time Till Utility" (or "TTU"; that is, the time until DBO can give a useful estimate) can be overly large, particularly in the case that many database tables are joined in a query, or in the case that a join query includes a very selective predicate on one or more of the tables, or when the data are skewed. In this paper, the authors describe Turbo DBO, which is a prototype database system that can answer multi-table join queries in a scalable fashion, just like DBO.