Digital Symposium Collection 2000  

 
 
 
 
 
 

 



















Join Synopses for Approximate Query Answering

Swarup Acharya, Phillip B. Gibbons, Viswanath Poosala, and Sridhar Ramaswamy

  View Paper (PDF)  

Return to Sampling - Approximate Answers

Abstract
In large data warehousing environments, it is often advantageous to provide fast, approximate answers to complex aggregate queries based on statistical summaries of the full data. In this paper, we demonstrate the difficulty of providing good approximate answers for join-queries using only statistics (in particular, samples) from the base relations. We propose join synopses as an effective solution for this problem and show how precomputing just one join synopsis for each relation suffices to significantly improve the quality of approximate answers for arbitrary queries with foreign key joins. We present optimal strategies for allocating the available space among the various join synopses when the query work load is known and identify heuristics for the common case when the work load is not known. We also present efficient algorithms for incrementally maintaining join synopses in the presence of updates to the base relations. Our extensive set of experiments on the TPC-D benchmark database show the effectiveness of join synopses and various other techniques proposed in this paper.


References

Note: References link to DBLP on the Web.

[AGPR99a]
Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala , Sridhar Ramaswamy : The Aqua Approximate Query Answering System. SIGMOD Conference 1999 : 574-576
[AGPR99b]
...
[AMS96]
Noga Alon , Yossi Matias , Mario Szegedy : The Space Complexity of Approximating the Frequency Moments. STOC 1996 : 20-29
[APR99]
Swarup Acharya , Viswanath Poosala , Sridhar Ramaswamy : Selectivity Estimation in Spatial Databases. SIGMOD Conference 1999 : 13-24
[BDF+97]
Daniel Barbará , William DuMouchel , Christos Faloutsos , Peter J. Haas , Joseph M. Hellerstein , Yannis E. Ioannidis , H. V. Jagadish , Theodore Johnson , Raymond T. Ng , Viswanath Poosala , Kenneth A. Ross , Kenneth C. Sevcik : The New Jersey Data Reduction Report. Data Engineering Bulletin 20(4) : 3-45(1997)
[CR94]
Chungmin Melvin Chen , Nick Roussopoulos : Adaptive Selectivity Estimation Using Query Feedback. SIGMOD Conference 1994 : 161-172
[GGMS96]
Sumit Ganguly , Phillip B. Gibbons , Yossi Matias , Abraham Silberschatz : Bifocal Sampling for Skew-Resistant Join Size Estimation. SIGMOD Conf. 1996 : 271-281
[GM98]
Phillip B. Gibbons , Yossi Matias : New Sampling-Based Summary Statistics for Improving Approximate Query Answers. SIGMOD Conference 1998 : 331-342
[GM99a]
...
[GM99b]
...
[GMP97a]
...
[GMP97b]
Phillip B. Gibbons , Yossi Matias , Viswanath Poosala : Fast Incremental Maintenance of Approximate Histograms. VLDB 1997 : 466-475
[Haa96]
...
[Haa97]
Peter J. Haas : Large-Sample and Deterministic Confidence Intervals for Online Aggregation. SSDBM 1997 : 51-63
[HHW97]
Joseph M. Hellerstein , Peter J. Haas , Helen Wang : Online Aggregation. SIGMOD Conference 1997 : 171-182
[HNS94]
Peter J. Haas , Jeffrey F. Naughton , Arun N. Swami : On the Relative Cost of Sampling for Join Selectivity Estimation. PODS 1994 : 14-24
[HNSS95]
Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Lynne Stokes : Sampling-Based Estimation of the Number of Distinct Values of an Attribute. VLDB 1995 : 311-322
[HÖT88]
Wen-Chi Hou , Gultekin Özsoyoglu , Baldeo K. Taneja : Statistical Estimators for Relational Algebra Expressions. PODS 1988 : 276-287
[Koo80]
Robert Kooi : The Optimization of Queries in Relational Databases. Ph.D. thesis, Case Western Reserve University 1980
[LN95]
Richard J. Lipton , Jeffrey F. Naughton : Query Size Estimation by Adaptive Sampling. JCSS 51(1) : 18-25(1995)
[LNS09]
Richard J. Lipton , Jeffrey F. Naughton , Donovan A. Schneider : Practical Selectivity Estimation through Adaptive Sampling. SIGMOD Conference 1990 : 1-11
[OR92]
Frank Olken , Doron Rotem : Maintenance of Materialized Views of Sampling Queries. ICDE 1992 : 632-641
[PIHS96]
Viswanath Poosala , Yannis E. Ioannidis , Peter J. Haas , Eugene J. Shekita : Improved Histograms for Selectivity Estimation of Range Predicates. SIGMOD Conf. 1996 : 294-305
[Poo97]
Viswanath Poosala : Histogram-Based Estimation Techniques in Database Systems. Ph.D. thesis, Univ. of Wisconsin-Madison 1997
[SAC+79]
Patricia G. Selinger , Morton M. Astrahan , Donald D. Chamberlin , Raymond A. Lorie , Thomas G. Price : Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979 : 23-34
[Sch97]
...
[VL93]
Susan V. Vrbsky , Jane W.-S. Liu : APPROXIMATE - A Query Processor that Produces Monotonically Improving Approximate Answers. TKDE 5(6) : 1056-1068(1993)

Referenced by

  1. Yannis E. Ioannidis , Viswanath Poosala : Histogram-Based Approximation of Set-Valued Query-Answers. VLDB 1999 : 174-185
  2. Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala : Aqua: A Fast Decision Support Systems Using Approximate Query Answers. VLDB 1999 : 754-757
  3. Viswanath Poosala , Venkatesh Ganti : Fast Approximate Answers to Aggregate Queries on a Data Cube. SSDBM 1999 : 24-33
  4. Peter J. Haas : Techniques for Online Exploration of Large Object-Relational Datasets. SSDBM 1999 : 4-12
  5. Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala , Sridhar Ramaswamy : The Aqua Approximate Query Answering System. SIGMOD Conference 1999 : 574-576
  6. Noga Alon , Phillip B. Gibbons , Yossi Matias , Mario Szegedy : Tracking Join and Self-Join Sizes in Limited Storage. PODS 1999 : 10-20

BIBTEX

@inproceedings{DBLP:conf/sigmod/AcharyaGPR99a,
  author    = {Swarup Acharya and
                Phillip B. Gibbons and
                Viswanath Poosala and
                Sridhar Ramaswamy},
   editor    = {Alex Delis and
                Christos Faloutsos and
                Shahram Ghandeharizadeh},
   title     = {Join Synopses for Approximate Query Answering},
   booktitle = {SIGMOD 1999, Proceedings ACM SIGMOD International Conference
                on Management of Data, June 1-3, 1999, Philadephia, Pennsylvania,
                USA},
   publisher = {ACM Press},
   year      = {1999},
   isbn      = {1-58113-084-8},
   pages     = {275-286},
   crossref  = {DBLP:conf/sigmod/99},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


























Copyright(C) 2000 ACM