An instant and accurate size estimation method for joins and selections in a retrieval-intensive environment

ABSTRACT

This paper proposes a novel strategy for estimating the size of the resulting relation after an equi-join and selection using a regression model. An approximating series representing the underlying data distribution and dependency is derived from the actual data. The proposed method provides an instant and accurate size estimation by performing an evaluation of the series, with no run-time overheads in page faults and space, and with negligible CPU overhead. In contrast, the popular sampling methods incur run-time overheads in page faults (for sampling), CPU time and space. These overheads of sampling methods increase the response time of processing a query. The results of a comprehensive experimental study are also reported, which demonstrate that the estimation accuracy by the proposed method is comparable with that of the sampling methods which are believed to provide the most accurate estimation. The proposed method seems ideal for retrieval-intensive database and information systems. Since the overheads involved in deriving the approximating series are fairly moderate, we believe that this method is also an extremely competent method when moderate or periodical updates are present.

REFERENCES

• 1: Ahrens, J.H. and Dieter, U., "Extensions of Forsythe's Method for Random Sampling from the Normal Distribution". Math. Compu., 27, 124 (Oct. 1973), pp. 92%937.
• 2: Christodoulakis, S. "Estimating Record Selectivities", Inf. Syst. 8, 2 1983, pp. 105-115.
• 3: 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
• 4: 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]
• 5: Gerard P. Weeg, Georgia B. Reed, "Introduction to Numerical Analysis", Blaisdell Publishing Company, 1966, pp. 63-72.
• 6: 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
• 7: 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
• 8: 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]
• 9: 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
• 10: Wen-Chi Hou , Gultekin Ozsoyoglu, Statistical estimators for aggregate relational algebra queries, ACM Transactions on Database Systems (TODS), v.16 n.4, p.600-654, Dec. 1991 [doi>10.1145/115302.115300]
• 11: 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]
• 12: Marvin J. Karson, "Multivariate Statistical Methods", The Iowa State University Press, 1982.
• 13: Robert Philip Kooi, The optimization of queries in relational databases, 1980
• 14: Ezio Lefons , Alberto Silvestri , Filippo Tangorra, An Analytic Approach to Statistical Databases, Proceedings of the 9th International Conference on Very Large Data Bases, p.260-274, October 31-November 02, 1983
• 15: Pierre L'Ecuyer , Serge Côté, Implementing a random number package with splitting facilities, ACM Transactions on Mathematical Software (TOMS), v.17 n.1, p.98-111, March 1991 [doi>10.1145/103147.103158]
• 16: Yibei Ling , Wei Sun, A supplement to sampling-based methods for query size estimation in a database system, ACM SIGMOD Record, v.21 n.4, p.12-15, Dec. 1992 [doi>10.1145/141818.141820]
• 17: 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
• 18: Luk, W. S. and Black, P. A., "On Cost Estimation in Processing a Query in a Distributed Database System'# Proc. of the IEEE 5th COMSAC, Chicago, IL, Nov. 1981, pp. 24-32.
• 19: 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
• 20: M. :I. Maron, "Numerical Analysis# A practical approach", Macmillan Publishing Company, 1987.
• 21: Michael V. Mannino , Paicheng Chu , Thomas Sager, Statistical profile estimation in database systems, ACM Computing Surveys (CSUR), v.20 n.3, p.191-221, Sept. 1988 [doi>10.1145/62061.62063]
• 22: Michael V. Mannino , Paicheng Chu , Thomas Sager, Statistical profile estimation in database systems, ACM Computing Surveys (CSUR), v.20 n.3, p.191-221, Sept. 1988 [doi>10.1145/62061.62063]
• 23: Tommaso Mostardi, Estimating the size of relational SP J operation results: an analytical approach, Information Systems, v.15 n.5, p.591-601, 1990 [doi>10.1016/0306-4379(90)90031-J]
• 24: 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]
• 25: Christopher B. Walton, Four Types of Data Skew and Their Effect on Parallel Join Performance, University of Texas at Austin, Austin, TX, 1990
• 26: Wolf, 3., Dias, D., Yu, P., and Turek, J., "A Parallel Hash-:loin Algorithm for Managing Data Skew", Tech Report RC 16489, IBM Watson Center, 1991.
• 27: 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]
• 28: C. T. Yu , C. C. Chang, Distributed query processing, ACM Computing Surveys (CSUR), v.16 n.4, p.399-433, Dec. 1984 [doi>10.1145/3872.3874]

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.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

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

General Terms:
Algorithms, Design, Experimentation, Performance