Counting and Data Sampling in Physical Design Exploration - Physical Database Design - page 195

nontrivial and even the best mathematical models for this have double-digit RMS error.
However, there are simple estimators that can be used to give a reasonable result and
these are appropriate for rapid exploration of database design possibilities. The best
database designs are almost always developed with the aid of counting.

10.5

Literature Summary

Acharya, S., Gibbons, P., Poosala, V., and Ramaswamy, S. Join Synopses for Approxi-
mate Query Answering. In Proceedings of 1999 SIGMOD . New York: ACM Press,
1999, pp. 275-286.

Chan, T. F., Golub, G. H., and LeVeque, R. J. Algorithms for Computing the Sample
Variance: Analysis and Recommendation. Amer. Statist ., 37, 1983: 242-247.

Chaudhuri, S., Motwani, R., and Narasayya, V. R. On Random Sampling over Joins. In
Proceedings of 1999 SIGMOD . New York: ACM Press, 1999, pp. 263-274.

Chaudhuri, S., Motwani, R., and Narasayya, V. R. Random Sampling for Histogram
Construction: How Much Is Enough? SIGMOD Conference, 1998, pp. 436-447.

Devroye, L. Non-Uniform Random Variate Generation . New York: Springer-Verlag,
1986.

Flajolet, P., and Martin, G. N. Probabilistic Counting Algorithms for Database Applica-
tions. Journal of Computer and System Sciences, 31, 1985: 182-209.

Ganguly, S. Gibbons, P. B., Matias, Y., and Silberschatz, A. Bifocal Sampling for Skew-
resistant Join Size Estimation. In Proceedings of 1996 SIGMOD . New York: ACM
Press, 1996, pp. 271-281.

Haas, P. J., and Kˆnig, C. A Bi-level Bernoulli Scheme for Database Sampling. In Pro-
ceedings of 2004 SIGMOD . New York: ACM Press, 2004, pp. 275-286.

Haas, P. J. The Need for Speed: Speeding Up DB2 Using Sampling. IDUG Solutions
Journal , 10, 2003: 32-34.

Haas, P. J., and Hellerstein, J. M.. Ripple Joins for Online Aggregation. In Proceedings of
1999 SIGMOD . New York: ACM Press, 1999, pp. 287-298.

Haas, P. J., and Stokes, L. Estimating the Number of Classes in a Finite Population. J.
American Statistical Association 93, Dec. 1998: 1475-1487.

Haas, P. J., Naughton, J. F., Seshadri, S., and Swami, A. N. Selectivity and Cost Estima-
tion for Joins Based on Random Sampling. J. Comput. Sys. Sci ., 52, 1996: 550-569.