Patent
1995-05-02
1997-12-02
Amsbury, Wayne
395610, 395604, G06F 1730
Patent
active
056945914
ABSTRACT:
A method for optimizing data retrieval from a multidatabase system by restructuring a database query tree to optimize query response time in a two step optimization process. First, the query tree is transformed into a left deep join tree having a root query, a plurality of subordinate (descendant) query nodes and a plurality of table nodes, each subordinate query node having a left child subtree and a right child subtree. This transformation is usually the result of a first optimization scheme such as System-R. A response time for the root query and for each of the plurality of subordinate query nodes is estimated and access response times to each table node and subtree are estimated. Then, this data is utilized in the balancing of the left deep join query tree so that the cost for access to each left child subtree is substantially equal to the cost for the right child subtree. This balancing step encompasses the second phase of the query tree optimization process and includes using transformation processes such top-down, bottom-up, and a hybrid of the first two. Finally, the query is executed in a relational database to retrieve data responsive to the query in accordance with an execution plan operating according to the balanced query tree.
REFERENCES:
patent: 5412804 (1995-05-01), Krishna
patent: 5412806 (1995-05-01), Du et al.
patent: 5446886 (1995-08-01), Li
patent: 5495605 (1996-02-01), Cadot
Chen et al, "using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins", Proc of the 18th Intl Conf on Very Large Databases, pp. 15-26, Jun. 1, 1992.
Swami et al, "A Polynominal Time Algorithm for Optimizing join Queries", PROC Ninth Intl Conf on Data Engineering, pp. 345-354, 19-23 Apr. 1993.
Harada et al, "Evaluation of Linear Join Processing Trees in Shared-Nothing Database Environment", Proc ICCI '93, pp. 413-417, May 29, 1993.
Zhu et al, "A Query Sampling Method for Estimating Local Cost Parameters in a Multidatabase System", Proc of the 10th Intl Conf Data Engineering, 14-18 Feb. 1994, pp. 145-153.
Dayal, Umesh, "Processing Queries Over Generalization Hierachies in a Multidatabase System", In Proc. VLDB 1983, pp. 342-353.
Brill, David et al., "Distributed Query Processing Strategies in Mermaid, a Frontend to Data Management Systems", In Proc. IEEE Data Engineering, Los Angeles, CA, 1984, pp. 211-218.
Hong, Wei and Stonebraker, Michael, "Optimization of Parallel Query Execution Plans in XPRS", Distributed and Parallel Databases, vol. 1, No. 1, 1993, pp. 9-32.
Du, Weimin et al., "Query Optimization in Heterogeneous DBMS", Proceedings of the 18th VLDB Conference, Vancouver, British Columbia, Canada, 1992, pp. 277-291.
Hong, Wei, "Exploiting Inter-Operation Parallelism in XPRS", Association of Computing Machinery, SIGMOD, Jun. 1992, pp. 19-28.
Selinger, P. Griffiths et al., "Access Pathe Selection in a Relational Database Management System", ACM SIGMOD, 1979, pp. 82-93.
Arbee L. P. Chen, "Outerjoin Optimization in Multidatabase Systems", IEEE, 1990, pp. 211-218.
Dayal Umeshwar
Du Weimin
Shan Ming-Chien
Amsbury Wayne
Hewlett -Packard Company
LandOfFree
Reducing query response time using tree balancing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Reducing query response time using tree balancing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reducing query response time using tree balancing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-809873