Multiple join size estimation by virtual domains (extended abstract)

ABSTRACT

A model is described to estimate the size of intermediate relations produced by large relational algebra expressions, in particular, those containing several equi-joins. The intended application is within query optimization searches, where fast estimates are needed as many alternative plans are examined. It is shown that previous methods, which use an independence assumption when several attributes are joined, can lead to unrealistically low size estimates. This method attempts to overcome that problem by the introduction of “virtual domains”, which avoid the independence assumption. The method does not require extensive statistics about the database. After describing an “exact” version, an approximation that is simpler and faster is presented.

REFERENCES

• AKS80: M.M. Astrahan, W. Kim, and M. Schkolnick. Evaluation of the System R Access Path Selection Mechanism. Technical Report RJ2797, IBM Research Laboratory, San Jose, CA, 1980.
• 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]
• IK90: Y. E. Ioannidis , Younkyung Kang, Randomized algorithms for optimizing large join queries, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.312-321, May 23-26, 1990, Atlantic City, New Jersey, United States
• IK91: Yannis E. Ioannidis , Younkyung Cha Kang, Left-deep vs. bushy trees: an analysis of strategy spaces and its implications for query optimization, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.168-177, May 29-31, 1991, Denver, Colorado, United States
• IW87: Yannis E. Ioannidis , Eugene Wong, Query optimization by simulated annealing, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.9-22, May 27-29, 1987, San Francisco, California, United States
• KBZ86: Ravi Krishnamurthy , Haran Boral , Carlo Zaniolo, Optimization of Nonrecursive Queries, Proceedings of the 12th International Conference on Very Large Data Bases, p.128-137, August 25-28, 1986
• LN90: 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
• LVZ92: Rosana S. G. Lanzelotte , Patrick Valduriez , Mohamed Zaït, Optimization of object-oriented recursive queries using cost-controlled strategies, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.256-265, June 02-05, 1992, San Diego, California, United States
• Lyn88: 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
• PSC84: 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
• SAC+79: 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]
• SG88: Arun Swami , Anoop Gupta, Optimization of large join queries, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.8-17, June 01-03, 1988, Chicago, Illinois, United States
• Swa89: A. Swami, Optimization of large join queries: combining heuristics and combinatorial techniques, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.367-376, June 1989, Portland, Oregon, United States
• Ull82: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Theory