REDUCING QUERY RESPONSE TIME USING TREE BALANCING

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.