Swarup Acharya
Phillip B. Gibbons
ABSTRACT
In large data warehousing environments, it is often advantageous to provide fast, approximate answers to complex decision support queries using precomputed summary statistics, such as samples. Decision support queries routinely segment the data into groups and then aggregate the information in each group (group-by queries). Depending on the data, there can be a wide disparity between the number of data items in each group. As a result, approximate answers based on uniform random samples of the data can result in poor accuracy for groups with very few data items, since such groups will be represented in the sample by very few (often zero) tuples.
In this paper, we propose a general class of techniques for obtaining fast, highly-accurate answers for group-by queries. These techniques rely on precomputed non-uniform (biased) samples of the data. In particular, we propose congressional samples, a hybrid union of uniform and biased samples. Given a fixed amount of space, congressional samples seek to maximize the accuracy for all possible group-by queries on a set of columns. We present a one pass algorithm for constructing a congressional sample and use this technique to also incrementally maintain the sample up-to-date without accessing the base relation. We also evaluate query rewriting strategies for providing approximate answers from congressional samples. Finally, we conduct an extensive set of experiments on the TPC-D database, which demonstrates the efficacy of the techniques proposed.
- AGP99a.S. Acharya, P. B. Gibbons, and V. Poosala. Aqua: A fast decision support system using approximate query answers. In Proc. 25th International Conf. on Very Large Databases, pages 754-757, September 1999. Demo paper. Google Scholar
Digital Library
- AGP99b.S. Acharya, P. B. Gibbons, and V. Poosala. Congressional samples for approximate answering of group-by queries. Technical report, Bell Laboratories, Murray Hill, New Jersey, November 1999.Google Scholar
- AGPR99.S. Acharya, P. B. Gibbons, V. Poosala, and S. Ramaswamy. Join synopses for approximate query answering. In Proc. ACM SIGMOD International Conf. on Management of Data, pages 275-286, June 1999. Google ScholarDigital Library
- CD97.S. Chaudhuri and U. Dayal. An overview of data warehousing and OLAP technology. SIGMOD Record, 26(1):65-74, 1997. Google ScholarDigital Library
- CMN99.S. Chaudhuri, R. Motwani, and V. Narasayya. On random sampling over joins. In Proc. ACM SIGMOD International Conf. on Management of Data, pages 263-274, June 1999. Google ScholarDigital Library
- Coc77.W. G. Cochran. Sampling Techniques. John Wiley & Sons, New York, third edition, 1977.Google Scholar
- CS94.S. Chaudhuri and K. Shim. Including group-by in query optimization. In Proc. 20th International Conf. on Very Large Data Bases, pages 354-366, September 1994. Google ScholarDigital Library
- CS95.S. Chaudhuri and K. Shim. An overview of cost-based optimization of queries with aggregates. IEEE Data Englneerlng Bulletin, 18(3):3-9, 1995.Google Scholar
- GM98.P. B. Gibbons and Y. Matins. New sampling-based summary statistics for improving approximate query answers. In Proe. ACM SIGMOD International Conf. on Management of Data, pages 331-342, June 1998. Google ScholarDigital Library
- HH99.P. Haas and J. Hellerstein. Ripple joins foe online aggregation. In Proc. ACM SIGMOD International Conf. on Management of Data, pages 287-298, June 1999. Google ScholarDigital Library
- HHW97.J. M. Hellerstein, P. J. Haas, and H. J. Wang. Online aggregation. In Proe. ACM SIGMOD International Conf. on Management of Data, pages 171-182, May 1997. Google ScholarDigital Library
- IP99.Y. Ioannidis and V. Poosala. Histogram-based techniques for approximating set-vMued query-answers. In Proe. 25th International Conf. on Very Large Databases, pages 174-185, September 1999. Google ScholarDigital Library
- Kim96.R. Kimball. The Data Warehouse Tookit. John Wiley and Sons Inc., 1996.Google Scholar
- Olk93.F. Olken. Random Sampling from Databases. PhD thesis, Computer Science, U.C. Berkeley, April 1993.Google Scholar
- PIHS96.V. Poosala, Y. E. Ioannidis, P. J. Haas, and E. J. Shekita. Improved histograms for selectivity estimation of range predicates. In Proc. A CM SIGMOD International Conf. on Management of Data, pages 294-305, June 1996. Google ScholarDigital Library
- SAC+79.P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. T. Price. Access path selection in a relational database management system. In Proc. ACM SIGMOD International Conf. on Management of Data, pages 23-34, June 1979. Google ScholarDigital Library
- Sch97.D. Schneider. The ins & outs (and everything in between) of data warehousing. Tutorial in the 23rd International Conf. on Very Large Data Bases, August 1997.Google Scholar
- TPC99.Transaction processing performance council (TPC). TPC-D Benchmark Version 2.0, February 1999. URL: www. tpc. org.Google Scholar
- VW99.J. S. Vitter and M. Wang. Approximate computation of multidimensional aggregates of sparse data using wavelets. In Proc. ACM SIGMOD International Conf. on Management of Data, pages 193-204, June 1999. Google ScholarDigital Library
Index Terms
- Congressional samples for approximate answering of group-by queries
Recommendations
Congressional samples for approximate answering of group-by queries
In large data warehousing environments, it is often advantageous to provide fast, approximate answers to complex decision support queries using precomputed summary statistics, such as samples. Decision support queries routinely segment the data into ...
Sample synopses for approximate answering of group-by queries
EDBT '09: Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database TechnologyWith the amount of data in current data warehouse databases growing steadily, random sampling is continuously gaining in importance. In particular, interactive analyses of large datasets can greatly benefit from the significantly shorter response times ...
Comments