第六章 ApproximateQueryProcessingTamingtheTeraBytes!ATutorial.pptVIP

Garofalakis Gibbons, VLDB 2001 Approximate Query Processing:Taming the TeraBytes!A Tutorial Minos Garofalakis and Phillip B. Gibbons Information Sciences Research Center Bell Laboratories /user/{minos, pbgibbons}/ Outline Intro Approximate Query Answering Overview Synopses, System architecture, Commercial offerings One-Dimensional Synopses Histograms, Samples, Wavelets Multi-Dimensional Synopses and Joins Multi-D Histograms, Join synopses, Wavelets Set-Valued Queries Using Histograms, Samples, Wavelets Discussion Comparisons Advanced Techniques Future Directions Dependency-based, Workload-tuned, Streaming data Conclusions Introduction Motivation Exact answers NOT always required DSS applications usually exploratory: early feedback to help identify “interesting” regions Aggregate queries: precision to “last decimal” not needed e.g., “What percentage of the US sales are in NJ?” (display as bar graph) Preview answers while waiting. Trial queries Base data can be remote or unavailable: approximate processing using locally-cached data synopses is the only option Fast Approximate Answers Primarily for Aggregate queries Goal is to quickly report the leading digits of answers In seconds instead of minutes or hours Most useful if can provide error guarantees E.g., Average salary $59,000 +/- $500 (with 95% confidence) in 10 seconds vs. $59,152.25 in 10 minutes Achieved by answering the query based on samples or other synopses of the data Speed-up obtained because synopses are orders of magnitude smaller than the original data Approximate Query Answering Basic Approach 1: Online Query Processing e.g., Control Project [HHW97, HH99, HAR00] Sampling at query time Answers continually improve, under user control Approximate Query Answering Basic Approach 2: Precomputed Synopses Construct store synopses prior to query time At query time, use synopses to answer the query Like estima