Optimization of SQL queries using early-out join transformations

Details Optimization of SQL queries using early-out join transformations Optimization of SQL queries using early-out join transformations

1995-02-07

1996-08-20

Kulik, Paul V.

Boots, shoes, and leggings

395700, 364974, 3649746, 3642821, 364DIG2, G06F 1730

Patent

active

055487548

ABSTRACT:
A method and apparatus for optimizing SQL queries in a relational database management system uses early-out join transformations. An early-out join comprises a many-to-one existential join, wherein the join scans an inner table for a match for each row of the outer table and terminates the scan for each row of the outer table when a single match is found in the inner table. To transform a many-to-many join to an early-out join, the query must include a requirement for distinctiveness, either explicitly or implicitly, in one or more result columns for the join operation. Distinctiveness can be specified using the DISTINCT keyword in the SELECT clause or can be implied from the predicates present in the query. The early-out join transformation also requires that no columns of the inner table be referenced after the join, or if an inner table column is referenced after the join, that each referenced column be "bound". A referenced column can be bound in one of three ways: (1) an inner table column can be bound to a constant through an equality predicate, (2) an inner table column can be bound to an outer table column, or (3) an inner table column can be bound to a correlated value, wherein the correlated value originates outside the query block. In all three cases, an inner table column can be bound through the transitivity of equality predicates.

REFERENCES:
patent: 4506326 (1985-03-01), Shaw et al.
patent: 4769772 (1988-09-01), Dwyer
patent: 4829427 (1989-05-01), Green
patent: 5091852 (1992-02-01), Tsunchida et al.
patent: 5317742 (1994-05-01), Bapat
patent: 5367675 (1994-11-01), Cheng et al.
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.
Pirahesh et al., "Extensible/Rule Based Query Rewrite Optimization in Starburst", IBM Almaden Research Center, San Jose, CA (US), ACM Sigmond, Jun. 1992, pp. 39-48.
Paulley et al., "Exploiting Uniqueness in Query Optimization", Department of computer Science, University of Waterloo, Ontario, Canada, IEEE 1994, pp. 68-79.
Lohman et al., Research Report--"Query Processing in R*", IBM Research Laboratory, San Jose, CA (US) IBM Research Division, Apr. 1984, pp. 1-33.
Agrawal et al., "Composition of Database Relations", Proceedings Fifth International Conference on Data Engineering, 6-10 Feb. 1989, Los Angles California, pp. 102-108.
Wei et al., "Hot-Spot Based Composition Algorithm", Eighth International Conference on Data Engineering, 2-3 Feb. 1992, Tempe, Arizona, pp. 48-55.

Affiliated with

Also associated with

Rating

Optimization of SQL queries using early-out join transformations does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Optimization of SQL queries using early-out join transformations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization of SQL queries using early-out join transformations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2337825