On the relative cost of sampling for join selectivity estimation

ABSTRACT

We compare the cost of estimating the selectivity of a “star join” using sampling procedure t-cross to the cost of simply computing the join and obtaining the exact answer. Our bounds and approximations for the relative cost of sampling show how this cost depends on the size of the input relations, the number of input relations, and the precision criterion used by the estimation procedure. We also demonstrate the deleterious effect of dangling tuples and the mixed effect of data skew on the relative cost of sampling. These results provide insight into when sampling should or should not be used for join selectivity estimation.

REFERENCES

• DNS92: David J. DeWitt , Jeffrey F. Naughton , Donovan A. Schneider , S. Seshadri, Practical Skew Handling in Parallel Joins, Proceedings of the 18th International Conference on Very Large Data Bases, p.27-40, August 23-27, 1992
• HN+93a: 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]
• HN+93b: Haas, P. J., Naughton, J. F., Seshadri, S., and Swami, A. N. (1993). Selectivity and cost estimation for joins based on random sampling. Technical Report RJ 9577. IBM Almaden Research Center. San Jose, CA.
• HS92a: 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
• HS92b: 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
• 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]
• HOT89: Wen-Chi Hou , Gultekin Ozsoyoglu , Baldeo K. Taneja, Processing aggregate relational queries with hard time constraints, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.68-77, June 1989, Portland, Oregon, United States
• HOD91: Wen-Chi Hou , Gultekin Ozsoyoglu , Erdogan Dogdu, Error-constrained COUNT query evaluation in relational databases, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.278-287, May 29-31, 1991, Denver, Colorado, United States
• 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
• LN90: Richard J. Lipton , Jeffrey F. Naughton, Query size estimation by adaptive sampling (extended abstract), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.40-46, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298540]
• LNS90: Richard J. Lipton , Jeffrey F. Naughton , Donovan A. Schneider, Practical selectivity estimation through adaptive sampling, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.1-11, May 23-26, 1990, Atlantic City, New Jersey, United States
• 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
• OR89: 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
• ORX90: Frank Olken , Doron Rotem , Ping Xu, Random sampling from hash files, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.375-386, May 23-26, 1990, Atlantic City, New Jersey, United States
• Olk93: Olken, F. (1993). Random Sampling from Databases. Ph.D. Dissertation. Department of Computer Science. University of California at Berkeley. Berkeley, California.
• Ses92: S. Seshadri, Probabilistic methods in query processing, University of Wisconsin at Madison, Madison, WI, 1992

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

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

General Terms:
Algorithms, Theory