Statistical profile estimation in database systems

ABSTRACT

A statistical profile summarizes the instances of a database. It describes aspects such as the number of tuples, the number of values, the distribution of values, the correlation between value sets, and the distribution of tuples among secondary storage units. Estimation of database profiles is critical in the problems of query optimization, physical database design, and database performance prediction. This paper describes a model of a database of profile, relates this model to estimating the cost of database operations, and surveys methods of estimating profiles. The operators and objects in the model include build profile, estimate profile, and update profile. The estimate operator is classified by the relational algebra operator (select, project, join), the property to be estimated (cardinality, distribution of values, and other parameters), and the underlying method (parametric, nonparametric, and ad-hoc). The accuracy, overhead, and assumptions of methods are discussed in detail. Relevant research in both the database and the statistics disciplines is incorporated in the detailed discussion.

REFERENCES

• 1: APERS, P. M. G., HEV~ER, A. R., ^NO Y^O, S. B. 1983. Optimization algorithms for distributed queries. IEEE Trans. Softw. Eng. SE-9, 1, 57-68.
• 2: ASTRAHAN, M., SCHKOLNICK, M., AND WHANG, K. 1985. Counting unique values of an attribute without sorting. Tech. Rep. RJ 4960, IBM Research Division.
• 3: D. S. Batory , M. Mannino, Panel: Extensible database systems, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.187-190, May 28-30, 1986, Washington, D.C., United States
• 4: Philip A. Bernstein , Nathan Goodman , Eugene Wong , Christopher L. Reeve , James B. Rothnie, Jr., Query processing in a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.6 n.4, p.602-625, Dec. 1981 [doi>10.1145/319628.319650]
• 5: BREIMAN, L., MEISEL, W., AND PURCELL, E. 1977. Variable kernel estimates of multivariate densities. Technometrics 19, 135-144.
• 6: CACOULLOS, V., 1966. Estimation of a multivariate density. Ann. Inst. Stat. Math. 18, 178-189.
• 7: Alfonso F. Cárdenas, Analysis and performance of inverted data base structures, Communications of the ACM, v.18 n.5, p.253-263, May 1975 [doi>10.1145/360762.360766]
• 8: Stefano Ceri , Giuseppe Pelagatti, Distributed databases principles and systems, McGraw-Hill, Inc., New York, NY, 1984
• 9: D. D. Chamberlin , M. M. Astrahan , W. F. King , R. A. Lorie , J. W. Mehl , T. G. Price , M. Schkolnick , P. Griffiths Selinger , D. R. Slutz , B. W. Wade , R. A. Yost, Support for repetitive transactions and ad hoc queries in System R, ACM Transactions on Database Systems (TODS), v.6 n.1, p.70-94, March 1981 [doi>10.1145/319540.319550]
• 10: To-Yat Cheung, Estimating block accesses and number of records in file management, Communications of the ACM, v.25 n.7, p.484-487, July 1982 [doi>10.1145/358557.358581]
• 11: Stavros Christodoulakis, Estimating selectivities in data bases, 1982
• 12: CHRISTODOULAKIS, S. 1983a. Estimating record selectivities. Inf. Syst. 8, 2 105-115.
• 13: 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
• 14: CHRISTODOULAKIS, $. 1984a. Estimating block selectivities. Inf. Syst. 9, 1, 69-79.
• 15: S. Christodoulakis, Implications of certain assumptions in database performance evauation, ACM Transactions on Database Systems (TODS), v.9 n.2, p.163-186, June 1984 [doi>10.1145/329.318578]
• 16: CLARK, C., AND SCHKADE, L. 1983. StatisticalAnatysis for Administrative Decisions. South-Western, Cincinnati.
• 17: George P. Copeland , Setrag Khoshafian , Marc G. Smith , Patrick Valduriez, Buffering Schemes for Permanent Data, Proceedings of the Second International Conference on Data Engineering, p.214-221, February 05-07, 1986
• 18: DEVROYE, L. 1985. A note on the L~ consistency of variable kernel estimates. Ann. Star. 13, 1041-1049.
• 19: David J DeWitt , Randy H Katz , Frank Olken , Leonard D Shapiro , Michael R Stonebraker , David Wood, Implementation techniques for main memory database systems, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 20: Jane Fedorowicz, Database evaluation using multiple regression techniques, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 21: Jane Fedorowicz, Database performance evaluation in an indexed file environment, ACM Transactions on Database Systems (TODS), v.12 n.1, p.85-110, March 1987 [doi>10.1145/12047.13675]
• 22: S. Finkelstein , M. Schkolnick , P. Tiberio, Physical database design for relational databases, ACM Transactions on Database Systems (TODS), v.13 n.1, p.91-128, March 1988 [doi>10.1145/42201.42205]
• 23: FRASER, D. 1957. Nonparametric Methods in Statistics. Wiley, New York.
• 24: 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
• 25: HEVNER, A., AND YAO, S. B. 1979. Query processing in distributed database systems. IEEE Trans. Softw. Eng. SE-3, 3.
• 26: Alle IJbema , Henk M. Blanken, Estimating Bucket Accesses: A Practical Approach, Proceedings of the Second International Conference on Data Engineering, p.30-37, February 05-07, 1986
• 27: Matthias Jarke , Jurgen Koch, Query Optimization in Database Systems, ACM Computing Surveys (CSUR), v.16 n.2, p.111-152, June 1984 [doi>10.1145/356924.356928]
• 28: JOHNSON, N., AND KOTZ, S. 1970. Distributions in Statistics: Continuous Univariate Distributions, vols. I and 2. Houghton Mifflin, Boston.
• 29: Nabil Kamel , Roger King, A model of data distribution based on texture analysis, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.319-325, May 1985, Austin, Texas, United States
• 30: Larry Kerschberg , Peter D. Ting , S. Bing Yao, Query optimization in star computer networks, ACM Transactions on Database Systems (TODS), v.7 n.4, p.678-711, Dec. 1982 [doi>10.1145/319758.319778]
• 31: Robert Philip Kooi, The optimization of queries in relational databases, 1980
• 32: KOTZ, S., AND JOHNSON, N. 1977. Urn Models and Their Application. Wiley, New York.
• 33: Akhil Kumar , Michael Stonebraker, The effect of join selectives on optimal nesting order, ACM SIGMOD Record, v.16 n.1, p.28-41, March 1987 [doi>10.1145/24820.24822]
• 34: LOHMAN, G., MOHAN, C., HAAS, L., LINDSAY, B., SELINGER, P., WILMS, P., AND DANIELS, D. 1985. Query processing in R*. In Query Processing in Database Systems, W. Kim, D. Batory, and D. Reiner, Eds. Springer-Verlag, New York, pp. 31-47.
• 35: W. S. Luk, On estimating block accesses in database organizations, Communications of the ACM, v.26 n.11, p.945-947, Nov. 1983 [doi>10.1145/182.358456]
• 36: MACKERT, L., AND LOHMAN, G. 1985. Index scans using a finite LRU buffer: A validated I/O model. IBM Research Rep. RJ4836, Almaden Research Center, San Jose, Calif.
• 37: Lothar F. Mackert , Guy M. Lohman, R* optimizer validation and performance evaluation for local queries, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.84-95, May 28-30, 1986, Washington, D.C., United States
• 38: Lothar F. Mackert , Guy M. Lohman, R* Optimizer Validation and Performance Evaluation for Distributed Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.149-159, August 25-28, 1986
• 39: MAHALANOBIS, P. 1936. On the generalized distance in statistics. In Proceedings of the National Institute of Sciences of India 12, pp. 35-49.
• 40: MANNINO, M. 1986. Selectivity estimation in unify SQL. Tech. Rep. Dept. of Management Science and Information Systems, Univ. of Texas, Austin.
• 41: M. V. Mannino , A. Rivera, An extensible model of selectivity estimation, Information Sciences: an International Journal, v.49 n.1-3, p.225-247, Oct.-Dec. 1989 [doi>10.1016/0020-0255(89)90029-7]
• 42: MERRETT, T. H., AND OTOO, E. 1979. Distribution models of relations. In Proceedings of the 5th International Conference on Very Large Data Bases (Rio de Janeiro, Brazil, Oct.). ACM, New York, pp. 418-425.
• 43: MONTGOMERY, A., D'SOuzA, D., AND LEE, S. 1983. The cost of relational algebraic operations on skewed data: Estimates and experiments. In Information Processing Letters 83. Elsevier North-Holland, New York, pp. 235-241.
• 44: MOORE, D., AND YACKEL, J. 1977. Consistency properties of nearest neighbor density function estimates. Ann. Stat. 5, 143-154.
• 45: M. Muralikrishna , David J. DeWitt, Equi-depth multidimensional histograms, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.28-36, June 01-03, 1988, Chicago, Illinois, United States
• 46: MUTHUSWAMY, B., AND KERSCHBERG, G. 1985. A DDSM for relational query optimization. Tech. Rep., Univ. of South Carolina, Columbia. Also in Proceedings of the ACM Annual Conference (Denver, Colo., Oct.). ACM, New York.
• 47: 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
• 48: PIATETSKY-SHAPIRO, G. 1985. Estimating the number of distinct attribute values by using sampling. Submitted for publication.
• 49: 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]
• 50: SAMSON, W., AND BENDELL, A. 1983. Rank order distributions and secondary key indexing (extended abstract). In Proceedings of the 2nd International Conference on Databases, (Cambridge, England).
• 51: 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]
• 52: SCHKOLNICK, M., AND TIBERIO, P. 1979. Considerations in developing a design tool for a relational DBMS. In Proceedings of the IEEE COMPSAC Conference (Chicago, Ill., Nov.). IEEE Press, New York, pp. 228-235.
• 53: STONEBRAKER, M., RUBENSTEIN, B., AND GUTMANN, A. 1983. Application of abstract data types and abstract indices to CAD databases. In Proceedings of Database Week: Engineering Design Applications (San Jose, Calif., May). pp. 107-113.
• 54: STUROES, H. 1926. The choice of class interval. J. Am. Stat. Assoc. 65-66.
• 55: TAPIA, R., AND THOMPSON, J. 1978. Nonparametric Probability Density Estimation. John Hopkins University Press, Baltimore, Md.
• 56: Toby J. Teorey , James P. Fry, Design of Database Structures, Prentice Hall Professional Technical Reference, 1982
• 57: UNIFY CORPORATION. 1985. Unix Relational Database Management System--Reference Manual. Release 3.2. Portland, Oreg.
• 58: 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
• 59: WEOMAN, E. 1983. Density estimation. In Encyclopedia of Statistical Sciences, Vol. 2, S. Kotz and N. Johnson, Eds. Wiley, New York.
• 60: WERTZ, W. 1978. Statistical Density Estimation: A Survey. Vandenhoeck and Ruprecht, Gottingen.
• 61: 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]
• 62: S. B. Yao, Approximating block accesses in database organizations, Communications of the ACM, v.20 n.4, p.260-261, April 1977 [doi>10.1145/359461.359475]
• 63: ZAHORJAN, J., BELL. B., AND SEVCIK, K. 1983. Estimating block transfers when record access probabilities are non-uniform. Inf. Process. Lett. 16, 5 (June), 249-252.
• 64: ZIPF, G. 1949. Human Behavior and the Principle of Least Effort. Addison-Wesley, Cambridge, Mass.

INDEX TERMS

Primary Classification:
  H. Information Systems

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods
      H.2.3 Languages
          Subjects: Query languages
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

General Terms:
Algorithms, Languages, Performance