Y. E. Ioannidis
Younkyung Kang
ABSTRACT
Query optimization for relational database systems is a combinatorial optimization problem, which makes exhaustive search unacceptable as the query size grows. Randomized algorithms, such as Simulated Annealing (SA) and Iterative Improvement (II), are viable alternatives to exhaustive search. We have adapted these algorithms to the optimization of project-select-join queries. We have tested them on large queries of various types with different databases, concluding that in most cases SA identifies a lower cost access plan than II. To explain this result, we have studied the shape of the cost function over the solution space associated with such queries and we have conjectured that it resembles a 'cup' with relatively small variations at the bottom. This has inspired a new Two Phase Optimization algorithm, which is a combination of Simulated Annealing and Iterative Improvement. Experimental results show that Two Phase Optimization outperforms the original algorithms in terms of both output quality and running time.
- Care86.M Carey and et al, The Architecture of the EXODUS Extenslble DBMS, m Proc of the 1986 Internatwnal Workshop on Object-Oriented Database Systems, e.dated by K Dlttnch and U Dayal, Pacific Grove, CA, September 1986, pp 52-65 Google Scholar
Digital Library
- Gran81.J Grant and J Mmker, Opttmlzataon m Deductive and Conventaonal Relational Database Systems, m Advances m Data Base Theory, Vol L edited by H Gallmre, J Mmker, and J M Nicolas, Plenum Press, New York, NY, 1981, pp 195-234Google Scholar
- Ioan87.Y E Ioanmdis and E Wong, Query Opttmlzataon by Stmulated Armealmg, m Proceedings of the 1987 ACM- SIGMOD Conference, San Francisco, CA, June 1987, pp 9-22 Google ScholarDigital Library
- Jark84.M Jarke and J Koch, Query Opttmizataon m Database Systems, ACM Computing Surveys 16 (June 1984), pp 111-152 Google ScholarDigital Library
- John87.D S Johnson, C R Aragon, L A McGeoch, and C Scheyon, Opttmtzatton by S~mulated Anneahng An Experunental Evaluatwn (Part I), unpubhshed manuscnpt, June 1987Google Scholar
- Kim86.W Klm, D Remer, and D Batory, Query Processing m Database Systems, Springer Verlag, New York, NY, 1986Google Scholar
- Kirk83.S Karkpatnck, C D Gdatt, Jr, and M P Veccba, Opumzatton by Smaulated Annealmg, Science 220, 4598 (May 1983), pp 671-680Google Scholar
- Kris86.R Knshnamurthy, H Boral, and C Zamolo, Oplamlzataon of Nonreeursive Queries, m Proceedings of the 12th Internarwhal VLDB Conference, Kyoto, Japan, August 1986, pp 128-137 Google ScholarDigital Library
- Litz88.M J Lltzkow, M Ltvny, and M W Mutka, Condor- A Htmter of Idle Workstataons, m The 8th lnternatwnal Conference on D~stnbuted Confuting Systems, 1988, pp 104-111Google Scholar
- Lohm88.G M Lohmart, Grammar-hke Functaonal Rules for Representing Query Optmuzation Alternatives, m Proceedrags of the 1988 ACM-SIGMOD Conference, Chicago, IL, June 1988, pp 18-27 Google ScholarDigital Library
- Naha86.S Nahar, S Sahm, and E Shragowitz, Stmulated Armealnag and Combinatorial Opumlzation, m Proceedings of the 23rd Design Automatwn Conference, 1986, pp 293-299 Google ScholarDigital Library
- Ono88.K OTto and G M Lohman, Extens~ble Enumeratwn of Feastble Joins for Relatwnal Query Optmuzatwn, IBM Research Report RJ6625, December 1988Google Scholar
- Rome85.F Romeo and A Sangiovanm-Vmcentelh, Probablhstac Hill Chmbmg Algorithms Properttes and Apphcanons, Proceedings of IEEE Conference on VLSI, 1985, pp 393- 417Google Scholar
- Seli79.P Selmger, M M Astrahan, D D Charnberlm, R A Lone, and T G Price, Access Path Selectaon m a Relational Database Management System, m Proceedings of the 1979 ACM.SIGMOD Conference, Boston, MA, June 1979, pp 23-34 Google ScholarDigital Library
- Sell88.T K Selhs, Multtple Query Opttrnlzataon, ACM Transactwns on Database Systems 13, 1 (March 1988), pp 23-52 Google ScholarDigital Library
- Swam88.A Swanu and A Gupta, Opttmizatmn of Large Join Queries, m Proceedings of the 1988 ACM-SIGMOD Conference, Chicago, IL, June 1988, pp 8-17 Google ScholarDigital Library
- Swam89.A Swarm, Opttmizalaon of Large Join Queries Combining Heunstaes and Combinatorial Techmques, m Proceedings of the 1989 ACM-SIGMOD Conference, Portland, OR, June 1989, pp 367-376 Google ScholarDigital Library
- Ullm82.J D Ullman, PrLnc~ples of Database Systems, Computer Science Press, Rockvdle, MD, 1982 Google ScholarDigital Library
- Whan85.K Y Whang, Query Optimization m Ofjice-by-Exan~le, IBM Research report, RC11571, 1985Google Scholar
Index Terms
- Randomized algorithms for optimizing large join queries
Recommendations
Optimization of large join queries
SIGMOD '88: Proceedings of the 1988 ACM SIGMOD international conference on Management of dataWe investigate the problem of optimizing Select—Project—Join queries with large numbers of joins. Taking advantage of commonly used heuristics, the problem is reduced to that of determining the optimal join order. This is a hard combinatorial ...
Randomized algorithms for optimizing large join queries
Query optimization for relational database systems is a combinatorial optimization problem, which makes exhaustive search unacceptable as the query size grows. Randomized algorithms, such as Simulated Annealing (SA) and Iterative Improvement (II), are ...
Comments