Query Optimization in a Heterogeneous DBMS.

Weimin Du, Ravi Krishnamurthy, Ming-Chien Shan: Query Optimization in a Heterogeneous DBMS. VLDB 1992: 277-291
  author    = {Weimin Du and
               Ravi Krishnamurthy and
               Ming-Chien Shan},
  editor    = {Li-Yan Yuan},
  title     = {Query Optimization in a Heterogeneous DBMS},
  booktitle = {18th International Conference on Very Large Data Bases, August
               23-27, 1992, Vancouver, Canada, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1992},
  isbn      = {1-55860-151-1},
  pages     = {277-291},
  ee        = {db/conf/vldb/DuKS92.html},
  crossref  = {DBLP:conf/vldb/92},
  bibsource = {DBLP,}


We propose a query optimization strategy for heterogeneous DBMSs that extends the traditional optimizer strategy widely used in commercial DBMSs to allow execution of queries over both known (i.e., proprietary) DBMSs and foreign vendor DBMSs that conform to some standard such as providing the usual relational database statistics. We assume that participating DBMSs are autonomous and may not be able, even if willing, to provide the cost model parameters. The novelty of the strategy is to deduce the necessary information by calibrating a given DBMS. As the calibration has to be done as a user, not as a system administrator, it poses unpredictability problems such as inferring the access methods used by the DBMS, idiosyncrasies of the storage subsystem and coincidental clustering of data. In this paper we propose a calibrating database which is synthetically created so as to make the process of deducing the cost model coefficients reasonably devoid of the unpredictability problems. Using this procedure, we calibrate three commercial DBMSs, namely Allbase, DB2,and Informix, and observe that in 80% of the cases the estimate is quite accurate.

Copyright © 1992 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Li-Yan Yuan (Ed.): 18th International Conference on Very Large Data Bases, August 23-27, 1992, Vancouver, Canada, Proceedings. Morgan Kaufmann 1992, ISBN 1-55860-151-1
Contents BibTeX


Rafi Ahmed, Philippe De Smedt, Weimin Du, William Kent, Mohammad A. Ketabchi, Witold Litwin, Abbas Rafii, Ming-Chien Shan: The Pegasus Heterogeneous Multidatabase System. IEEE Computer 24(12): 19-27(1991) BibTeX
Dina Bitton, David J. DeWitt, Carolyn Turbyfill: Benchmarking Database Systems A Systematic Approach. VLDB 1983: 8-19 BibTeX
Danette Chimenti, Ruben Gamboa, Ravi Krishnamurthy: Abstract Machine for LDL. EDBT 1990: 153-168 BibTeX
Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
Sumit Ganguly, Waqar Hasan, Ravi Krishnamurthy: Query Optimization for Parallel Execution. SIGMOD Conference 1992: 9-18 BibTeX
Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo: Optimization of Nonrecursive Queries. VLDB 1986: 128-137 BibTeX
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX
Kyu-Young Whang, Ravi Krishnamurthy: Query Optimization in a Memory-Resident Domain Relational Calculus Database System. ACM Trans. Database Syst. 15(1): 67-95(1990) BibTeX

Referenced by

  1. Mary Tork Roth, Fatma Ozcan, Laura M. Haas: Cost Models DO Matter: Providing Cost Information for Diverse Data Sources in a Federated System. VLDB 1999: 599-610
  2. Joseph M. Hellerstein: Optimization Techniques for Queries with Expensive Methods. ACM Trans. Database Syst. 23(2): 113-157(1998)
  3. Anthony Tomasic, Louiqa Raschid, Patrick Valduriez: Scaling Access to Heterogeneous Data Sources with DISCO. IEEE Trans. Knowl. Data Eng. 10(5): 808-823(1998)
  4. Weiyi Meng, Clement T. Yu, Wei Wang, Naphtali Rishe: Performance Analysis of Three Text-Join Algorithms. IEEE Trans. Knowl. Data Eng. 10(3): 477-492(1998)
  5. Shivakumar Venkataraman, Tian Zhang: Heterogeneous Database Query Optimization in DB2 Universal DataJoiner. VLDB 1998: 685-689
  6. Frédéric Gingras, Laks V. S. Lakshmanan: nD-SQL: A Multi-Dimensional Language for Interoperability and OLAP. VLDB 1998: 134-145
  7. Hubert Naacke, Georges Gardarin, Anthony Tomasic: Leveraging Mediator Cost Models with Heterogeneous Data Sources. ICDE 1998: 351-360
  8. Ramana Yerneni, Yannis Papakonstantinou, Serge Abiteboul, Hector Garcia-Molina: Fusion Queries over Internet Databases. EDBT 1998: 57-71
  9. Silvio Salza, Giovanni Barone, Tadeusz Morzy: A Distributed Algorithm for Global Query Optimization in Multidatabase Systems. ADBIS 1998: 95-106
  10. Gustav Fahl, Tore Risch: Query Processing Over Object Views of Relational Data. VLDB J. 6(4): 261-281(1997)
  11. Chiang Lee, Chia-Jung Chen: Query Optimization in Multidatabase Systems Considering Schema Conflicts. IEEE Trans. Knowl. Data Eng. 9(6): 941-955(1997)
  12. Fatma Ozcan, Sena Nural, Pinar Koksal, Cem Evrendilek, Asuman Dogac: Dynamic Query Optimization in Multidatabases. IEEE Data Eng. Bull. 20(3): 38-45(1997)
  13. Laura M. Haas, Donald Kossmann, Edward L. Wimmers, Jun Yang: Optimizing Queries Across Diverse Data Sources. VLDB 1997: 276-285
  14. Georges Gardarin, Fei Sha, Zhao-Hui Tang: Calibrating the Query Optimizer Cost Model of IRO-DB, an Object-Oriented Federated Database System. VLDB 1996: 378-389
  15. Sibel Adali, K. Selçuk Candan, Yannis Papakonstantinou, V. S. Subrahmanian: Query Caching and Optimization in Distributed Mediator Systems. SIGMOD Conference 1996: 137-148
  16. Weiyi Meng, Clement T. Yu, Wei Wang, Naphtali Rishe: Performance Analysis of Several Algorithms for Processing Joins between Textual Attributes. ICDE 1996: 636-644
  17. Chengwen Liu, Hao Chen, Warren Krueger: A Distributed Query Processing Strategy Using Placement Dependency. ICDE 1996: 477-484
  18. Chengwen Liu, Hao Chen: A Hash Partition Strategy for Distributed Query Processing. EDBT 1996: 373-387
  19. Weimin Du, Ming-Chien Shan, Umeshwar Dayal: Reducing Multidatabase Query Response Time by Tree Balancing. SIGMOD Conference 1995: 293-303
  20. Silvio Salza, Giovanni Barone, Tadeusz Morzy: Distributed Query Optimization in Loosly Coupled Multidatabase Systems. ICDT 1995: 40-53
  21. Joseph M. Hellerstein: Practical Predicate Placement. SIGMOD Conference 1994: 325-335
  22. Qiang Zhu, Per-Åke Larson: A Query Sampling Method of Estimating Local Cost Parameters in a Multidatabase System. ICDE 1994: 144-153
  23. Peter Scheuermann, Eugene Inseok Chong: Role-based Query Processing in Multidatabase Systems. EDBT 1994: 95-108
  24. Anne H. H. Ngu, Ling-Ling Yan, Limsoon Wong: Heterogeneous Query Optimization Using Maximal Sub-Queries. DASFAA 1993: 413-420
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:52 2009