Patent
1995-01-30
1997-11-11
Black, Thomas G.
G06F 1730
Patent
active
056873620
ABSTRACT:
The present invention discloses a method and apparatus for the enumeration of projections (i.e., "SELECT DISTINCT" operations) in SQL queries containing outer and full outer joins in the presence of inner joins without encountering any regression in performance. The present invention removes projections from a given user query by moving the projections to the top of an expression tree representation of the query, wherein the projection removal is performed using algebraic identities rather than rule-based transformations. The present invention also discloses several methods of enumerating different plans or schedules for projection operations and binary operations in the given user query. The present invention can significantly reduce the execution time of a query by selecting the optimal schedule for binary operations and projections between the binary operations. However, the present invention ensures that there is no regression in performance by comparing the cost of the query with the cost of enumerated plans or schedules, thereby ensuring that the optimizations or transformations do not introduce performance penalties.
REFERENCES:
patent: 4769772 (1988-09-01), Dwyer
patent: 4829427 (1989-05-01), Green
patent: 5091852 (1992-02-01), Tsunchida et al.
patent: 5335345 (1994-08-01), Frieder et al.
patent: 5367675 (1994-11-01), Cheng et al.
patent: 5412806 (1995-05-01), Du et al.
patent: 5495605 (1996-02-01), Calot
Date, C.J. "The Outer Join", Proceedings of the Second International Conference on Databases, Cambridge, England, Sep. 1983, pp. 76-106.
Dayal, U., Goodman, N. and Katz, R.H., "An Extended Relational Algebra With Control Over Duplicate Elimination", Proc. ACM PODS, pp. 117-123, 1982.
Dayal, Umeshwar, "Processing Queries with Quantifiers: A Horticultural Approach", Proc. ACM PODS, pp. 125-136, 1983.
Dayal, Umeshwar, "Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers", VLDB, pp. 197-208, 1987.
Galindo-Legaria, C., and Rosenthal, A., "How to Extend a Conventional Optimizer to Handle One-and Two-Sided Outerjoin", IEEE Proceedings of Data Engineering, pp. 402-409, 1992.
Galindo-Legaria, C.A., "Algebraic Optimization of Outerjoin Queries", Ph.D. dissertation, Center for Research in Computing Technology, Harvard University, Cambridge, MA, 1992.
Pirahesh, H., Hellerstein, J.M. and Hasan, W. "Extensible/Rule Based Query Rewrite Optimization in Starburst", ACM SIGMOD, pp. 39-48, San Diego, CA, Jun. 1992.
Rosenthal, A. and Galindo-Legaria, C., "Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins", ACM SIGMOD, pp. 291-299, 1990.
Apers, P.M.G., Hevner, A.R. and Yao, S.B., "Optimization Algorithms for Distributed Queries", IEEE Trans. Softw. Eng., SE-9, pp. 57-68, Jan. 1983.
Alon Levy, Inderpal Mumick, Yehoshua Sagiv, "Query Optimization by Predicate Move-Around," Proceedings of the 20th VLDB Conference, Santiago, Chile, Sep., 1994.
Paulley, G.N. and Per-Ake Larson, "Exploiting Uniqueness in Query Optimization", CASCON, pp. 804-822, vol. II, Oct. 1993.
Lafortune, S. and Wong, E., "A State Transition Model for Distributed Query Processing", ACM Transactions on Database Systems, vol. 11, No. 3, pp. 294-322, Sep. 1986.
Lohman, G.M., Mohan, C., Haas, L.M., Lindsay, B.G., Selinger, P.G., Wilms, P.F. and Daniels, D., "Query Processing In R*", Res. Rep. RJ 4272, IBM Research Laboratory, San Jose, Ca., Apr. 1984.
Selinger, P.G., Astrahan, M.M., Chamberlin, D.D., Lorie, R.A. and Price, T.G., "Access Path Selection in a Relational Database Management System", ACM SIGMOD, pp. 23-34, 1979.
Kim, Won, IBM Research "On Optimizing an SQL-Like Nested Query, ACM Transactions On Database Systems", vol. 7, No. 3, Sep. 1982, pp. 443-469.
Ganski et al., "Optimization of Nested SQL Queries Revisited", ACM, 1987, pp. 23-33.
Haas et al., "Extensible Query Processing in Starburst", IBM Almaden Research Center, San Jose, CA (US), ACM 1989, pp. 377-388.
Date, C.J. & Darwen, Hugh., "Relational Database Management" Relational Database Writings 1989-1991, Part II, pp. 133-154.
Ceri, Stephano, "Distributed Databases --Principles and Systems", McGraw Hill, 1984, pp. 93-172.
Bhargava Gautam
Goel Piyush
Iyer Balakrishna Ragmavendra
Black Thomas G.
Choules Jack M.
International Business Machines - Corporation
LandOfFree
Enumerating projections in SQL queries containing outer and full does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Enumerating projections in SQL queries containing outer and full, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enumerating projections in SQL queries containing outer and full will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1236816