Scalable approximate query processing with the DBO engine

ABSTRACT

This paper 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 answer 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 at any time that they are happy with the query accuracy, and encourages exploratory data analysis.

REFERENCES

• 1: S. Acharya, P. Gibons, V. Poosala, S. Ramaswamy: Join Synopses for Approximate Query Processing. SIGMOD 1999:275--286.
• 2: S. Chaudhuri, R. Motwani, V. R. Narasayya: On Random Sampling over Joins. SIGMOD 1999: 263--274.
• 3: W. Cochran: Sampling Techniques. Wiley and Sons, 1977.
• 4: 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]
• 5: J. P. Dittrich, B. Seeger, D. S. Taylor, P. Widmayer: Progressive Merge Join: A Generic and Non-blocking Sort-based Join Algorithm. VLDB 2002: 299--310.
• 6: P. J. Haas, J. M. Hellerstein: Ripple Joins for Online Aggregation. SIGMOD 1999: 287--298.
• 7: 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]
• 8: 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]
• 9: G. H. Hardy, J. E. Littlewood, and G. Polya. Inequalities. Cambridge University Press, 1988.
• 10: 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]
• 11: J. M. Hellerstein, P. J. Haas, H. J. Wang: Online Aggregation. SIGMOD 1997: 171--182.
• 12: 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
• 13: C. Jermaine, A. Dobra, S. Arumugam, S. Joshi, A. Pol: A Disk-Based Join with Probabilistic Guarantees. SIGMOD 2005: 456--467.
• 14: 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
• 15: 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]
• 16: F. Olken: Random Sampling from Databases. PhD Thesis, U. of California, Berkeley, 1993
• 17: F. Olken, D. Rotem, P. Xu: Random Sampling from Hash Files. SIGMOD 1990: 375--386.
• 18: 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
• 19: 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]
• 20: J. Shao: Mathematical Statistics. Springer-Verlag, 1999.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

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

General Terms:
Algorithms, Performance

Keywords:
DBO, online aggregation, randomized algorithms, sampling