Query Optimization by Simulated Annealing.

@inproceedings{DBLP:conf/sigmod/Ioannidis87,
  author    = {Yannis E. Ioannidis and
               Eugene Wong},
  editor    = {Umeshwar Dayal and
               Irving L. Traiger},
  title     = {Query Optimization by Simulated Annealing},
  booktitle = {Proceedings of the Association for Computing Machinery Special
               Interest Group on Management of Data 1987 Annual Conference,
               San Francisco, California, May 27-29, 1987},
  publisher = {ACM Press},
  year      = {1987},
  pages     = {9-22},
  ee        = {http://doi.acm.org/10.1145/38713.38722, db/conf/sigmod/Ioannidis87.html},
  crossref  = {DBLP:conf/sigmod/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1987 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/smod7592 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[Ackl85]

...

[Aho79]

Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX

[Aho84]

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX

[Arag84]

...

[Astr76]

Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX

[Banc85]

...

[Banc86a]

François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15 BibTeX

[Banc86b]

François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX

[Banc86c]

...

[Bern81]

Philip A. Bernstein, Nathan Goodman, Eugene Wong, Christopher L. Reeve, James B. Rothnie Jr.: Query Processing in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 6(4): 602-625(1981) BibTeX

[Blas76]

...

[Codd70]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX

[Epst78]

Robert S. Epstein, Michael Stonebraker, Eugene Wong: Distributed Query Processing in a Relational Data Base System. SIGMOD Conference 1978: 169-180 BibTeX

[Gall78]

...

[Gall84]

Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984) BibTeX

[Gran81]

John Grant, Jack Minker: Optimization in Deductive and Conventional Relational Database Systems. Advances in Data Base Theory 1979: 195-234 BibTeX

[Haje85]

...

[Ioan86a]

Yannis E. Ioannidis: On the Computation of the Transitive Closure of Relational Operators. VLDB 1986: 403-411 BibTeX

[Ioan86b]

Yannis E. Ioannidis, Eugene Wong: An Algebraic Approach to Recursive Inference. Expert Database Conf. 1986: 295-309 BibTeX

[Ioan86c]

Yannis E. Ioannidis: A Time Bound on the Materialization of Some Recursively Defined Views. Algorithmica 1(3): 361-385(1986) BibTeX

[Jark84]

Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984) BibTeX

[Kers86a]

...

[Kers86b]

...

[Kim86]

...

[Kirk83]

...

[Kooi80]

Robert Kooi: The Optimization of Queries in Relational Databases. Ph.D. thesis, Case Western Reserve University 1980
BibTeX

[Kris86]

Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo: Optimization of Nonrecursive Queries. VLDB 1986: 128-137 BibTeX

[Mack86a]

Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Distributed Queries. VLDB 1986: 149-159 BibTeX

[Mack86b]

Lothar F. Mackert, Guy M. Lohman: R* Optimizer Validation and Performance Evaluation for Local Queries. SIGMOD Conference 1986: 84-95 BibTeX

[Mitr85]

...

[Naug86]

...

[Rich83]

...

[Rome84]

...

[Rome85]

...

[Rose80]

Daniel J. Rosenkrantz, Harry B. Hunt III: Processing Conjunctive Predicates and Queries. VLDB 1980: 64-72 BibTeX

[Sacc86]

Domenico Saccà, Carlo Zaniolo: The Generalized Counting Method for Recursive Logic Queries. ICDT 1986: 31-53 BibTeX

[Sagi86]

...

[Sech86a]

...

[Sech86b]

...

[Seli79]

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

[Sell86]

Timos K. Sellis: Global Query Optimization. SIGMOD Conference 1986: 191-205 BibTeX

[Ston76]

Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) BibTeX

[Vald86]

Patrick Valduriez, Haran Boral: Evaluation of Recursive Queries Using Join Indices. Expert Database Conf. 1986: 271-293 BibTeX

[Wile83]

...

[Wong76]

Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX

Referenced by

1. Timos K. Sellis: Review - Query Optimization by Simulated Annealing. ACM SIGMOD Digital Review 2: (2000)
2. Navin Kabra, David J. DeWitt: OPT++: An Object-Oriented Implementation for Extensible Database Query Optimization. VLDB J. 8(1): 55-78(1999)
3. Alin Deutsch, Lucian Popa, Val Tannen: Physical Data Independence, Constraints, and Optimization with Universal Plans. VLDB 1999: 459-470
4. Ramana Yerneni, Chen Li, Jeffrey D. Ullman, Hector Garcia-Molina: Optimizing Large Join Queries in Mediation Systems. ICDT 1999: 348-364
5. Joachim Kröger, Regina Illner, Steffen Rost, Andreas Heuer: Query Rewriting and Search in CROQUE. ADBIS 1999: 288-302
6. Tolga Urhan, Michael J. Franklin, Laurent Amsaleg: Cost Based Query Scrambling for Initial Delays. SIGMOD Conference 1998: 130-141
7. Michael Steinbrunn, Guido Moerkotte, Alfons Kemper: Heuristic and Randomized Optimization for the Join Ordering Problem. VLDB J. 6(3): 191-208(1997)
8. Yannis E. Ioannidis, Raymond T. Ng, Kyuseok Shim, Timos K. Sellis: Parametric Query Optimization. VLDB J. 6(2): 132-151(1997)
9. Arjan Pellenkoft, César A. Galindo-Legaria, Martin L. Kersten: The Complexity of Transformation-Based Join Enumeration. VLDB 1997: 306-315
10. Chiang Lee, Chi-Sheng Shih, Yaw-Huei Chen: A Graph-Theoretic Model for Optimizing Large Join Queries. DASFAA 1997: 87-96
11. Myra Spiliopoulou, Michael Hatzopoulos, Yannis Cotronis: Parallel Optimization of Large Join Queries with Set Operators and Aggregates in a Parallel Environment Supporting Pipeline. IEEE Trans. Knowl. Data Eng. 8(3): 429-445(1996)
12. Bojan Groselj, Qutaibah M. Malluhi: Combinatorial Optimization of Distributed Queries. IEEE Trans. Knowl. Data Eng. 7(6): 915-927(1995)
13. Bernd-Uwe Pagel, Hans-Werner Six, Mario Winter: Window Query-Optimal Clustering of Spatial Objects. PODS 1995: 86-94
14. Raymond T. Ng, Jiawei Han: Efficient and Effective Clustering Methods for Spatial Data Mining. VLDB 1994: 144-155
15. César A. Galindo-Legaria, Arjan Pellenkoft, Martin L. Kersten: Fast, Randomized Join-Order Selection - Why Use Transformations? VLDB 1994: 85-95
16. Tadeusz Morzy, Maciej Matysiak, Silvio Salza: Tabu Search Optimization of Large Join Queries. EDBT 1994: 309-322
17. Philip S. Yu, Douglas W. Cornell: Buffer Management Based on Return on Consumption in a Multi-Query Environment. VLDB J. 2(1): 1-37(1993)
18. Alfons Kemper, Guido Moerkotte, Klaus Peithner: A Blackboard Architecture for Query Optimization in Object Bases. VLDB 1993: 543-554
19. Allen Van Gelder: Multiple Join Size Estimation by Virtual Domains. PODS 1993: 180-189
20. Arun N. Swami, Balakrishna R. Iyer: A Polynomial Time Algorithm for Optimizing Join Queries. ICDE 1993: 345-354
21. Jorng-Tzong Horng, Gwo-Dong Chen, Baw-Jhiune Liu: Query Processing Techniques in the Team-Oriented Database Query Language. DASFAA 1993: 245-252
22. Yannis E. Ioannidis, Raymond T. Ng, Kyuseok Shim, Timos K. Sellis: Parametric Query Optimization. VLDB 1992: 103-114
23. Jean-Pierre Cheiney, Rosana S. G. Lanzelotte: A Model for Optimizing Deductive and Object-Oriented DB Requests. ICDE 1992: 385-392
24. Georges Gardarin, Rosana S. G. Lanzelotte: Optimizing Object-Oriented Datbase Queries using Cost-Controlled Rewriting. EDBT 1992: 534-549
25. Rosana S. G. Lanzelotte, Patrick Valduriez: Extending the Search Strategy in a Query Optimizer. VLDB 1991: 363-373
26. Yannis E. Ioannidis, Younkyung Cha Kang: Left-Deep vs. Bushy Trees: An Analysis of Strategy Spaces and its Implications for Query Optimization. SIGMOD Conference 1991: 168-177
27. Rosana S. G. Lanzelotte, Jean-Pierre Cheiney: Adapting Relational Optimization Technology to Deductive and Object-Oriented Declarative Database Languages. DBPL 1991: 322-336
28. Kenichi Yajima, Hiroyuki Kitagawa, Kazunori Yamaguchi, Nobuo Ohbo, Yuzuru Fujiwara: Optimization of Queries Including ADT Functions. DASFAA 1991: 366-373
29. Danette Chimenti, Ruben Gamboa, Ravi Krishnamurthy, Shamim A. Naqvi, Shalom Tsur, Carlo Zaniolo: The LDL System Prototype. IEEE Trans. Knowl. Data Eng. 2(1): 76-90(1990)
30. Yannis E. Ioannidis, Younkyung Cha Kang: Randomized Algorithms for Optimizing Large Join Queries. SIGMOD Conference 1990: 312-321
31. Edward Sciore, John Sieg Jr.: A Modular Query Optimizer Generator. ICDE 1990: 146-153
32. Michael Stonebraker: Future Trends in Database Systems. IEEE Trans. Knowl. Data Eng. 1(1): 33-44(1989)
33. Richard J. Lipton, Jeffrey F. Naughton: Estimating the Size of Generalized Transitive Closures. VLDB 1989: 165-171
34. Yannis E. Ioannidis: Commutativity and its Role in the Processing of Linear Recursion. VLDB 1989: 155-163
35. Arun N. Swami: Optimization of Large Join Queries: Combining Heuristic and Combinatorial Techniques. SIGMOD Conference 1989: 367-376
36. Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
    Contents
37. Shashi Shekhar, Jaideep Srivastava, Soumitra Dutta: A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization. VLDB 1988: 457-467
38. Arun N. Swami, Anoop Gupta: Optimization of Large Join Queries. SIGMOD Conference 1988: 8-17
39. Michael Stonebraker: Future Trends in Data Base Systems. ICDE 1988: 222-231
40. Ming-Chien Shan: Optimal Plan Search in a Rule-Based Query Optimizer. EDBT 1988: 92-112
41. Ravi Krishnamurthy, Carlo Zaniolo: Optimization in a Logic Based Language for Knowledge and Data Intensive Applications. EDBT 1988: 16-33
42. Ravi Krishnamurthy, Carlo Zaniolo: Control and Optimization Strategies in the Implementation of LDL. DBPL 1987: 329-345