Query size estimation by adaptive sampling (extended abstract)

ABSTRACT

We present an adaptive, random sampling algorithm for estimating the size of general queries. The algorithm can be used for any query Q over a database D such that 1) for some n, the answer to Q can be partitioned into n disjoint subsets Q1, Q2, …, Qn, and 2) for 1 ≤ i ≤ n, the size of Qi is bounded by some function b(D, Q), and 3) there is some algorithm by which we can compute the size of Qi, where i is chosen randomly. We consider the performance of the algorithm on three special cases of the algorithm: join queries, transitive closure queries, and general recursive Datalog queries.

REFERENCES

• BKBR87: C. Beeri , P. Kanellakis , F. Bancilhon , R. Ramakrishnan, Bounds on the propagation of selection into logic programs, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.214-226, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28683]
• Chr83: Stavros Christodoulakis, Estimating block transfers and join sizes, Proceedings of the 1983 ACM SIGMOD international conference on Management of data, May 23-26, 1983, San Jose, California
• Dem80: Robert Demolombe. Estimation of the number of tuples satisfying a query expressed in predicate calculus language. In Proceedings of the Sixth International Conference on Very Large Databases, pages 55-63, Montreal, Canada, 1980.
• HOT88: Wen-Chi Hou , Gultekin Ozsoyoglu , Baldeo K. Taneja, Statistical estimators for relational algebra expressions, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.276-287, March 1988, Austin, Texas, United States [doi>10.1145/308386.308455]
• LN89: R. J. Lipton , J. F. Naughton, Estimating the size of generalized transitive closures, Proceedings of the 15th international conference on Very large data bases, p.165-171, July 1989, Amsterdam, The Netherlands
• Lyn88: Clifford A. Lynch, Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distribution of Column Values, Proceedings of the 14th International Conference on Very Large Data Bases, p.240-251, August 29-September 01, 1988
• MNS+87: Katherine Morris, Jeffrey F. Naughton, Yatin Saraiya, Jeffrey D. Ullman, and Allen Van Gelder. YAWN! (Yet Another Window on NAIL!). Database Engineering, December 1987.
• MUVG86: Katherine Morris , Jeffrey D Ullman , Allen Van Gelder, Design overview of the NAIL] system, Proceedings on Third international conference on logic programming, p.554-568, September 1986, London, United Kingdom
• NRSU89: J. F. Naughton , R. Ramakrishnan , J. D. Ullman, Argument reduction by factoring, Proceedings of the 15th international conference on Very large data bases, p.173-182, July 1989, Amsterdam, The Netherlands
• OR86: Frank Olken , Doron Rotem, Simple Random Sampling from Relational Databases, Proceedings of the 12th International Conference on Very Large Data Bases, p.160-169, August 25-28, 1986
• PSC84: Gregory Piatetsky-Shapiro , Charles Connell, Accurate estimation of the number of tuples satisfying a condition, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• Row83: Neil C. Rowe, Top-down statistical estimation on a database, Proceedings of the 1983 ACM SIGMOD international conference on Management of data, May 23-26, 1983, San Jose, California
• SAC+79: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• TZ86: Shalom Tsur , Carlo Zaniolo, LDL: A Logic-Based Data Language, Proceedings of the 12th International Conference on Very Large Data Bases, p.33-41, August 25-28, 1986

INDEX TERMS

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

General Terms:
Algorithms, Design, Management, Performance, Theory, Verification