Enumerating projections in SQL queries containing outer and full

Details Enumerating projections in SQL queries containing outer and full Enumerating projections in SQL queries containing outer and full

1997-07-31

1998-12-29

Black, Thomas G.

Data processing: database and file management or data structures

Database design

Data structure types

G06F 1730

Patent

active

058550194

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., et al., "An Extended Relational Algebra With Control Over Duplicate Elimination", Proc. ACM PODDS, pp. 117-123, 1982.
Dayal, Umeshwar, "Proceedings Queries with Quantifiers: A Horticultural Approach", Proc. ACM PODS, pp. 125-136, 1983.
Dayal, Umeshwar, "Of Nests and Trees: A Unified Appraoch 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., et al., "Extensible/Rule Based Query Rewrite Optimization in Starbusrt", 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., et al., "Optimization Algorithms for Distributed Queries", IEEE Trans. Softw. Eng., SE-9, pp. 57-68, Jan. 1983.
Alon Levy, et al., "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. II No. 3, pp. 294-322, Sep. 1986.
Lohman, G.M., et al., "Query Processing in R*", Res. Rep. RJ 4272, IBM Research Laboratory, San Jose, California, Apr. 1984.
Selinger, P.G., et al., "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 Revisted", ACM, 1987, pp. 23-33.
Haas et al., "Extensible Query Processing in Starburst", IBM Almaden Research Center, San Jose, California (US), ACM 1989, pp. 377-388.
Date, C.J. and Darwen, Hugh, "Relationship 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.

Affiliated with

Also associated with

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1430851