A linear-time probabilistic counting algorithm for database applications

ABSTRACT

We present a probabilistic algorithm for counting the number of unique values in the presence of duplicates. This algorithm has O(q) time complexity, where q is the number of values including duplicates, and produces an estimation with an arbitrary accuracy prespecified by the user using only a small amount of space. Traditionally, accurate counts of unique values were obtained by sorting, which has O(q log q) time complexity. Our technique, called linear counting, is based on hashing. We present a comprehensive theoretical and experimental analysis of linear counting. The analysis reveals an interesting result: A load factor (number of unique values/hash table size) much larger than 1.0 (e.g., 12) can be used for accurate estimation (e.g., 1% of error). We present this technique with two important applications to database problems: namely, (1) obtaining the column cardinality (the number of unique values in a column of a relation) and (2) obtaining the join selectivity (the number of unique values in the join column resulting from an unconditional join divided by the number of unique join column values in the relation to he joined). These two parameters are important statistics that are used in relational query optimization and physical database design.

REFERENCES

• 1: Morton M. Astrahan , Mario Schkolnick , Kyu-Young Whang, Approximating the number of unique values of an attribute without sorting, Information Systems, v.12 n.1, p.11-15, Jan. 1987 [doi>10.1016/0306-4379(87)90014-7]
• 2: Dina Bitton , David J. DeWitt, Duplicate record elimination in large data files, ACM Transactions on Database Systems (TODS), v.8 n.2, p.255-265, June 1983 [doi>10.1145/319983.319987]
• 3: Samuel Daniel Conte , Carl W. De Boor, Elementary Numerical Analysis: An Algorithmic Approach, McGraw-Hill Higher Education, 1980
• 4: DEMOLOMBE, R. Estimation of the number of tuples satisfying a query expressed in predicate calculus language. In Proceedings of the 6th International Conference on Very Large Data Bases, 1980, pp. 55-63.
• 5: FELLER, W. An Introduction to Probability Theory and Its Applications. Vol. 1, 3rd ed., Wiley, New York, 1968.
• 6: Erol Gelenbe , Danièle Gardy, The Size of Projections of Relations Satisfying a Functional Dependency, Proceedings of the 8th International Conference on Very Large Data Bases, p.325-333, September 08-10, 1982
• 7: JOHNSON, N. L., AND KOTZ, S. Urn Models and Their Application. Wiley, New York, 1977.
• 8: MOOD, A. M., GRAYBILL, F. A., AND BOES, D.C. Introduction to the Theory of Statistics. 3rd ed., McGraw-Hill, New York, 1974.
• 9: 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
• 10: Neil C. Rowe, Antisampling for estimation: an overview, IEEE Transactions on Software Engineering, v.11 n.10, p.1081-1091, Oct. 1985 [doi>10.1109/TSE.1985.231855]
• 11: 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]
• 12: SHERMAN, B. A random variable related to the spacing of sample values. Ann. Math. Statistics 21 (1950), 339-361.
• 13: Brad T. Vander Zanden , Howard M. Taylor , Dina Bitton, Estimating Block Accessses when Attributes are Correlated, Proceedings of the 12th International Conference on Very Large Data Bases, p.119-127, August 25-28, 1986
• 14: Kyu-Young Whang , Gio Wiederhold , Daniel Sagalowicz, Estimating block accesses in database organizations: a closed noniterative formula, Communications of the ACM, v.26 n.11, p.940-944, Nov. 1983 [doi>10.1145/182.358452]
• 15: WHANG, K., WIEDERHOLD, G., AND SAGALOWICZ, D. Separability--An approach to physical database design. IEEE Trans. Comput. C-33, 3 (Mar. 1984), 209-222.
• 16: Gio Wiederhold , Ramez Elmasri, The Structural Model for Database Design, Proceedings of the 1st International Conference on the Entity-Relationship Approach to Systems Analysis and Design, p.237-258, January 1980
• 17: Gio C. Wiederhold, Database Design, McGraw-Hill, Inc., New York, NY, 1983
• 18: YOUSSEFI, K., AND WONG, E. Query processing in a relational database management system. In Proceedings of the 5th International Conference on Very Large Data Bases, 1979, pp. 409-417.
• 19: C. T. Yu , M. K. Siu , K. Lam , M. Ozsoyoglu, Performance analysis of three related assignment problems, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582109]

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.2 Physical Design
          Subjects: Access methods
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Design, Experimentation, Performance, Theory