Semantic optimization of query order requirements using order de

Details Semantic optimization of query order requirements using order de Semantic optimization of query order requirements using order de

1995-02-17

1997-04-08

Black, Thomas G.

G06F 1730

Patent

active

056196920

ABSTRACT:
A procedure for detecting a reordering requirement in a directed record stream during query execution in a relational database processing system. The query compiler component of a relational database processing system includes procedures for building query execution plans (QEPs) for evaluation preparatory to selecting an optimal plan for execution. These plans are constructed from the bottom up using an internal graphical representation for the user query that has a number of relation nodes interconnected by directed record streams (data flows). A relational operation within each node imposes an "order requirement" on the outflow stream represented by an order requirement vector O.sub.R. The records within each directed record stream have an "order property" represented by an order property vector O.sub.P. Order detection occurs when these two vectors are compared to determine whether the order property satisfies the order requirement. Order detection by normalization (ODN) according to this invention first normalizes the two order specification vectors to remove all attributes made redundant by the effects of predicates and functional dependencies. Query execution plans constructed using ODN are found to execute an order of magnitude faster than those constructed using order detection without normalization.

REFERENCES:
patent: 5241648 (1993-08-01), Cheng et al.
patent: 5276870 (1994-01-01), Shan et al.
patent: 5301317 (1994-04-01), Lohman et al.
patent: 5345585 (1994-09-01), Iyer et al.
patent: 5367675 (1994-11-01), Cheng et al.
patent: 5369761 (1994-11-01), Conley et al.
patent: 5412804 (1995-05-01), Krishna
patent: 5546570 (1996-08-01), McPherson, Jr. et al.
patent: 5546576 (1996-08-01), Cochrane et al.
patent: 5548755 (1996-08-01), Leung et al.
C. J. Date, An Introduction to Database Systems, vol. 1, 6th Ed., Addison-Wesley Publishing Co., pp. 243-244, 361-392, No date.
G. N. Paulley et al., "Exploiting Uniqueness in Query Optimization", CASCON, vol. II, pp. 804-822, Oct. 1993.
G. M. Lohmn, "Grammar-like Functional Rules for Representing Query Optimization Alternatives", ACM SIGMOD International Conference on Management of Data, 1988, pp. 18-27.
ISO-ANSI, "ISO-ANSI Working Draft: Database Language SQL2 and SQL3", 1993, pp. 545-547.
J. R. Boykin et al., "Order Class Detection", IBM Technical Disclosure Bulletin, vol. 32, No. 5A, Oct. 1989, pp. 283-285.
L. W. Youngren, "Dynamic Ordering of Joined Rows using Fields from Multiple Tables", vol. 36, No. 11, Nov. 1993, pp. 363-366.
"A Similarity Graph-Based Approach To Declustering Problems And Its Application Towards Parallelizing Grid Files," Duen-Ren Liu, Shashi Shekhar, 6-10 Mar. 1995.
"HUH . . . VH Multi-Layer Channel Routing" Jeesoo Lee, Yokun Cho, Jan. 1991 .

Affiliated with

Also associated with

Rating

Semantic optimization of query order requirements using order de does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Semantic optimization of query order requirements using order de, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Semantic optimization of query order requirements using order de will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2403004