Generating targeted queries for database testing

ABSTRACT

Tools for generating test queries for databases do not explicitly take into account the actual data in the database. As a consequence, such tools cannot guarantee suitable coverage of test cases commonly required for database testing. In this paper, we investigate the problem of generating queries that satisfy cardinality constraints on intermediate subexpressions when executed on a given test database. Such queries are required to test the performance of a database system under different operating conditions.

We formally analyze this problem, quantify its difficulty and follow up this analysis with a description of a practical algorithm which utilizes sampling and space pruning techniques to quickly generate test queries that have desired properties. We present the results of an experimental evaluation of our approach as implemented in an open source data manager, demonstrating the utility of our proposal.

REFERENCES

• 1: Transaction processing performance council. http://www.tpc.org.
• 2: Nabih N. Abdelmalek, L1 solution of overdetermined systems of linear equations, ACM Transactions on Mathematical Software (TOMS), v.6 n.2, p.220-227, June 1980 [doi>10.1145/355887.355894]
• 3: Hardik Bati , Leo Giakoumakis , Steve Herbert , Aleksandras Surna, A genetic approach for random testing of database systems, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 4: Carsten Binnig , Donald Kossmann , Eric Lo , M. Tamer Özsu, QAGen: generating query-aware test databases, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247520]
• 5: Nicolas Bruno , Surajit Chaudhuri, Exploiting statistics on query expressions for optimization, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564722]
• 6: Nicolas Bruno , Surajit Chaudhuri, Flexible database generators, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 7: Nicolas Bruno , Surajit Chaudhuri , Dilys Thomas, Generating Queries with Cardinality Constraints for DBMS Testing, IEEE Transactions on Knowledge and Data Engineering, v.18 n.12, p.1721-1725, December 2006 [doi>10.1109/TKDE.2006.190]
• 8: S. Chaudhuri and V. Narasayya. Program for TPC-D Data generation with skew. ftp://ftp.research.microsoft.com/users/viveknar/tpcdskew.
• 9: Jim Gray , Prakash Sundaresan , Susanne Englert , Ken Baclawski , Peter J. Weinberger, Quickly generating billion-record synthetic databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.243-252, May 24-27, 1994, Minneapolis, Minnesota, United States
• 10: Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Arun N. Swami, Fixed-precision estimation of join selectivity, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.190-201, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153875]
• 11: Peter J. Haas , Arun N. Swami, Sequential sampling procedures for query size estimation, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.341-350, June 02-05, 1992, San Diego, California, United States
• 12: Yannis Ioannidis, The history of histograms (abridged), Proceedings of the 29th international conference on Very large data bases, p.19-30, September 09-12, 2003, Berlin, Germany
• 13: Per-Ake Larson , Wolfgang Lehner , Jingren Zhou , Peter Zabback, Cardinality estimation using sample views with quality assurance, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247502]
• 14: Meikel Poess , John M. Stephens, Jr., Generating thousand benchmark queries in seconds, Proceedings of the Thirtieth international conference on Very large data bases, p.1045-1053, August 31-September 03, 2004, Toronto, Canada
• 15: Meikel Poess , Raghunath Othayoth Nambiar , David Walrath, Why you should run TPC-DS: a workload analysis, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 16: Donald R. Slutz, Massive Stochastic Testing of SQL, Proceedings of the 24rd International Conference on Very Large Data Bases, p.618-622, August 24-27, 1998
• 17: John M. Stephens , Meikel Poess, MUDD: a multi-dimensional data generator, Proceedings of the 4th international workshop on Software and performance, January 14-16, 2004, Redwood Shores, California

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

General Terms:
Performance, Reliability

Keywords:
database testing, query generation