×

Reducing query response time using tree balancing

  • US 5,694,591 A
  • Filed: 05/02/1995
  • Issued: 12/02/1997
  • Est. Priority Date: 05/02/1995
  • Status: Expired due to Term
First Claim
Patent Images

1. In a multidatabase system (MDBS) for accessing data in a plurality of relational computer databases on a distributed network of database machines, a method of structuring a database query to reduce query response time using a two phase optimization, comprising the steps of:

  • inputting the database query;

    as a first phase, optimization,transforming the database query into a left deep join query 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;

    as a second phase optimization.estimating a response time for the root query and for each of the plurality of subordinate query nodes;

    measuring a response time to access each of the plurality of table nodes and a cost to access each subtree;

    balancing the left deep join query tree into a bushy query tree, wherein the cost for each left child subtree is substantially equal to the cost for the right child subtree; and

    executing the database query in one or more of said relational databases in accordance with an execution plan operating according to the balanced bushy query tree.

View all claims
  • 3 Assignments
Timeline View
Assignment View
    ×
    ×