Scalable approximate query processing with the DBO engine

ABSTRACT

This article describes query processing in the DBO database system. Like other database systems designed for ad hoc analytic processing, DBO is able to compute the exact answers to queries over a large relational database in a scalable fashion. Unlike any other system designed for analytic processing, DBO can constantly maintain a guess as to the final answer to an aggregate query throughout execution, along with statistically meaningful bounds for the guess's accuracy. As DBO gathers more and more information, the guess gets more and more accurate, until it is 100% accurate as the query is completed. This allows users to stop the execution as soon as they are happy with the query accuracy, and thus encourages exploratory data analysis.

REFERENCES

• 1: Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala , Sridhar Ramaswamy, Join synopses for approximate query answering, ACM SIGMOD Record, v.28 n.2, p.275-286, June 1999
• 2: Gennady Antoshenkov, Random Sampling from Pseudo-Ranked B+ Trees, Proceedings of the 18th International Conference on Very Large Data Bases, p.375-382, August 23-27, 1992
• 3: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, On random sampling over joins, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.263-274, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 4: Cochran, W. G. 1977. Sampling Techniques, 3rd Edition. John Wiley.
• 5: Jens-Peter Dittrich , Bernhard Seeger , David Scot Taylor , Peter Widmayer, Progressive merge join: a generic and non-blocking sort-based join algorithm, Proceedings of the 28th international conference on Very Large Data Bases, p.299-310, August 20-23, 2002, Hong Kong, China
• 6: Jens-Peter Dittrich , Bernhard Seeger , David Scot Taylor , Peter Widmayer, On producing join results early, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.134-142, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773167]
• 7: Alin Dobra, Histograms revisited: when are histograms the best approximation method for aggregates over joins?, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065196]
• 8: Peter J. Haas, Large-Sample and Deterministic Confidence Intervals for Online Aggregation, Proceedings of the Ninth International Conference on Scientific and Statistical Database Management, p.51-63, August 11-13, 1997 [doi>10.1109/SSDM.1997.621151]
• 9: Peter J. Haas , Joseph M. Hellerstein, Ripple joins for online aggregation, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.287-298, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 10: Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Arun N. Swami, Selectivity and cost estimation for joins based on random sampling, Journal of Computer and System Sciences, v.52 n.3, p.550-569, June 1996 [doi>10.1006/jcss.1996.0041]
• 11: Hardy, G., Littlewood, J., and Polya, G. 1988. Inequalities. Cambridge University Press.
• 12: Joseph M. Hellerstein , Ron Avnur , Andy Chou , Christian Hidber , Chris Olston , Vijayshankar Raman , Tali Roth , Peter J. Haas, Interactive Data Analysis: The Control Project, Computer, v.32 n.8, p.51-59, August 1999 [doi>10.1109/2.781635]
• 13: Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, ACM SIGMOD Record, v.26 n.2, p.171-182, June 1997
• 14: Christopher Jermaine , Subramanian Arumugam , Abhijit Pol , Alin Dobra, Scalable approximate query processing with the DBO engine, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247560]
• 15: Christopher Jermaine , Alin Dobra , Subramanian Arumugam , Shantanu Joshi , Abhijit Pol, A disk-based join with probabilistic guarantees, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066222]
• 16: Christopher Jermaine , Alin Dobra , Abhijit Pol , Shantanu Joshi, Online estimation for subset-based SQL queries, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 17: Gang Luo , Curt J. Ellmann , Peter J. Haas , Jeffrey F. Naughton, A scalable hash ripple join algorithm, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564721]
• 18: Olken, F. 1993. Random sampling from databases. Ph.D. thesis, U. of California, Berkeley.
• 19: F. Olken , D. Rotem, Random sampling from B+ trees, Proceedings of the 15th international conference on Very large data bases, p.269-277, July 1989, Amsterdam, The Netherlands
• 20: Gultekin Özsoyoglu , Kaizheng Du , Sujatha Guru Swamy , Wen-Chi Hou, Processing Real-Time, Non-Aggregate Queries with Time-Constraints in CASE-DB, Proceedings of the Eighth International Conference on Data Engineering, p.410-417, February 03-07, 1992
• 21: Shao, J. 1999. Mathematical Statistics. Springer-Verlag.
• 22: Leonard D. Shapiro, Join processing in database systems with large main memories, ACM Transactions on Database Systems (TODS), v.11 n.3, p.239-264, Sept. 1986 [doi>10.1145/6314.6315]
• 23: Stefanov, S. 2001. Separable Programming. Applied Optimization, vol. 53. Kluwer Academic Publishers.
• 24: Jeffrey Scott Vitter , Min Wang, Approximate computation of multidimensional aggregates of sparse data using wavelets, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.193-204, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Performance

Keywords:
Online aggregation, randomized algorithms, sampling