Reducing multidatabase query response time by tree balancing

ABSTRACT

Execution of multidatabase queries differs from that of traditional queries in that sort merge and hash joins are more often favored, as nested loop join requires repeated accesses to external data sources. As a consequence, left deep join trees obtained by traditional (e.g., System-R style) optimizers for multidatabase queries are often suboptimal, with respect to response time, due to the long delay for a sort merge (or hash) join node to produce its last result after the subordinate join node did. In this paper, we present an optimization strategy that first produces an optimal left deep join tree and then reduces the response time using simple tree transformations. This strategy has the advantages of guaranteed minimum total resource usage, improved response time, and low optimization overhead. We describe a class of basic transformations that is the cornerstone of our approach. Then we present algorithms that effectively apply basic transformations to balance a left deep join tree, and discuss how the technique can be incorporated into existing query optimizers.

REFERENCES

• BTY84: David Brill , Marjorie Templeton , Clement T. Yu, Distributed Query Processing Strategies in Mermaid, A Frontend to Data Management Systems, Proceedings of the First International Conference on Data Engineering, p.211-218, April 24-27, 1984
• Chen90: Arbee L. P. Chen, Outerjoin optimization in multidatabase systems, Proceedings of the second international symposium on Databases in parallel and distributed systems, p.211-218, July 02-04, 1990, Dublin, Ireland [doi>10.1145/319057.319101]
• Daya83: Umeshwar Dayal, Processing Queries Over Generalization Hierarchies in a Multidatabase System, Proceedings of the 9th International Conference on Very Large Data Bases, p.342-353, October 31-November 02, 1983
• Daya85: U. Dayal. Query Processing in Multidatabase System, In Query Processing in Database Systems (Kim, Batory and Reiner (eds.), 1985), Springer Verlag.
• DH84: U. Dayal and H. Hwang. View Definition and Generalization for Database Integration in Multibase" A System for Heterogeneous Distributed Databases, In IEEE Tran. on Software Engineering, Vol. 10, No. 6, 1984.
• DKS92: Weimin Du , Ravi Krishnamurthy , Ming-Chien Shan, Query Optimization in a Heterogeneous DBMS, Proceedings of the 18th International Conference on Very Large Data Bases, p.277-291, August 23-27, 1992
• DSD94A: W. Du, M. Shah and J. Davis. Optimization and Execution Strategy for Multidatabase Queries, Technical Report HPL- 94-7~, Hewlett-Packard Labs., 1994.
• DSD94B: W. Du, M. Shan and U. Dayal. Reducing Multidatabase Query Response Time By Tree Balancing, DTD Technical Reporl, Hewlett-Packard Labs., 1994.
• Hong92: Wei Hong, Exploiting inter-operation parallelism in XPRS, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.19-28, June 02-05, 1992, San Diego, California, United States
• HS93: Wei Hong , Michael Stonebraker, Optimization of parallel query execution plans in XPRS, Distributed and Parallel Databases, v.1 n.1, p.9-32, Jan. 1993 [doi>10.1007/BF01277518]
• IK90: Y. E. Ioannidis , Younkyung Kang, Randomized algorithms for optimizing large join queries, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.312-321, May 23-26, 1990, Atlantic City, New Jersey, United States
• LMH+85: G. Lohman, C. Mohan, L. Haas, B. Lindsey and P. Selinger. Query Processing in R*, In Query Processing in Database Systems (Kim, Batory and Reiner (eds.), 1985), Springer Verlag.
• SAC+79: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• SAD+94: M. Shan, R. Ahmed, J. Davis, W. Du, and W. Kent. The Pegasus Project - A Heterogeneous information Management System, In Modern Information Computer (Kim ed.), Addison-Wesley, 1994.
• SL90: Amit P. Sheth , James A. Larson, Federated database systems for managing distributed, heterogeneous, and autonomous databases, ACM Computing Surveys (CSUR), v.22 n.3, p.183-236, Sept. 1990 [doi>10.1145/96602.96604]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Languages, Performance