Yannis E. Ioannidis
Eugene Wong
ABSTRACT
Query optimizers of future database management systems are likely to face large access plan spaces in their task. Exhaustively searching such access plan spaces is unacceptable. We propose a query optimization algorithm based on simulated annealing, which is a probabilistic hill climbing algorithm. We show the specific formulation of the algorithm for the case of optimizing complex non-recursive queries that arise in the study of linear recursion. The query answer is explicitly represented and manipulated within the closed semiring of linear relational operators. The optimization algorithm is applied to a state space that is constructed from the equivalent algebraic forms of the query answer. A prototype of the simulated annealing algorithm has been built and few experiments have been performed for a limited class of relational operators. Our initial experience is that, in general, the algorithm converges to processing strategies that are very close to the optimal. Moreover, the traditional processing strategies (e.g., the semi-naive evaluation) have been found to be, in general, suboptimal.
- Ackl85.Acldey, D. H., G. E. Hmton, and T J. Sejnowska, "A Learning Algorithm for Bolmnann Machines", Cogmtive Science 9 (1985), pp. 147- 169Google Scholar
Cross Ref
- Aho79.Aho, A., Y. Sagtv, and J Unman, "Equivakzw, es Among Relatmnal Expresstons", S/AM Computzng Journal 8, 2 (May 1979), pp 218-246.Google Scholar
- Aho84.Aho, A., J. Hoperoft, and J. Ullman, The Destgn and Analysts of Computer Al&ortt#, Wesley, Reading, MA, 1974. Google ScholarDigital Library
- Arag84.Aragon, C. R., D. S. Johnson, L. A. Megeoch, and C. Schevon, "#tratton by Snnulated Annealrag: An Expemnental Evaluauon', unpubhslmd manuscript, October 1984Google Scholar
- Astr76.Astrahan M. el al., "System R" Relauonal Approach to Database Management", ACM Transacttons on Database Systems 1, 2 (June 1976), pp 97-137 Google ScholarDigital Library
- Banc85.Bancflhon F., "Natve Evaluatton of Recurmvely Defined Relauons', m Procee&ngs of the Islamorada Workshop on Large Scale Knowledge Base and Reasomng Systems, Islam# FL, February 1985Google Scholar
- Banc86a.Banctlhon, F., D Mater, Y Saglv, and J. D. Ullman, "Magic Sets and Other Strange Ways to Implement Logic Progntms', m Proceedings of the 5th ACM SIGMOD.SIGACT Syml#s#um on Principles of Database Systems, Boston, MA, March 1986,pp 1-15 Google ScholarDigital Library
- Banc86b.Bancdhon, F. and R. Rmnaimshnl# "An Amate#'s Introducuon to Recurssve Query Pmceding Strategies", m Proceedings of the 1986 A CM-SIGMOD Conference on the Management of Data, Washington, DC, May 1986, pp. 16-52 Google ScholarDigital Library
- Banc86c.Banetlhon F and R Ramaknshnan, "Performance Evaluauon of Data intenstve Logic Programs", m Preprmts of the Workshop on Foundatwns of Deductzve Databases and Logzc Programnung, Washington, DC, August 1986, pp 284-314. Google ScholarDigital Library
- Bern81.Bernstem, P. A., H. Goodman, E Wong, C L Reeve, and J. B. Rothme, "Query Proc#smg m a System for Distn'buted Databases (SDD-I)", ACM TODS 6, 4 (December 1981), pp. 602-625 Google ScholarDigital Library
- Blas76.Blasgen, M W. and K. P Eswaran, "On the Evaiuauon of Queries m a Relauonal Data Base System", Research Report RJ-1745, IBM San Jose, Aprd 1976.Google Scholar
- Codd70.Codd E. F., "A Relauonal Model of Data for Large ShareA Data Banks", CACM 13, 6 (1970), pp. 377-387. Google ScholarDigital Library
- Epst78.Epstein, R., M. Stonebraket, and E. Wong, "D#stnbuted Query Processing m a Relauonal Data Base System", m Proceedings of the 1978 ACM- SIGMOD Conference on the Management of Data, Austm, TX, May 1978, pp 169-180 Google ScholarDigital Library
- Gall78.Gallane H. and J. Mmker, Logic and Data Bases, Plenum Press, New York, N.Y, 1978. Google ScholarDigital Library
- Gall84.Gallane H., J Mmker, and I. M. Ntcolas, "Logic and Databases: A Deducuve Approach", A CM Computm& Sw'veys 16, 2 (June 1984), IV 153- 185. Google ScholarDigital Library
- Gran81.J. Grant and J Mmker, "Opttmmauon m Dexlucuve and Convenuonal Relattonal Databases", m Advances m Data Base Theory, Vol 1, Plenum Press, New York, N Y, 1981, pp 195-234Google Scholar
- Haje85.Hajek, B., "Coohng Schedules for Opttmal AnneXing", unpubhshe# manuscript, January 1985Google Scholar
- Ioan86a.Ioanm&s, Y E, "On the Computauon of the Transmve Closure of Relaaonal Operators", m Proc 12th lnternatwnal VLDB Conference, Kyoto, Japan, August 1986, pp. 403-411. Google ScholarDigital Library
- Ioan86b.Ioanmchs, Y. E. and E Wong, "An Algelntc Approach to Recursive Inference", m Proceedm&s of the 1st lnternanonal Conference on E:g#en Database Systems, Charleston, South Carohna, Aprd 1986, pp 209-223.Google Scholar
- Ioan86c.Ioanmchs, Y. E., "A Tune Bound on the MatenaltzaUon of Some Recurslvely Defined V#ews", Al&onthnuca 1, 4 October 1986, pp 361-385.Google Scholar
- Jark84.Jarke, M. and J. Koch, "Query Op# in Database Systems', ACM Computing Surveys 16, 2 (June 1984), pp. 111-152. Google ScholarDigital Library
- Kers86a.Kerschberg, L., Expert Database Systems, Proceechn&s from the F#rst Internatwnal Workshop, Benjamm-Cummmgs, Inc, Menlo Park, CA, 1986. Google ScholarDigital Library
- Kers86b.Kerschberg, L, Procee&ngs from the Fwst Internaaonal Conference on Expert Database Systems, Charleston, SC, Aprd 1986 Google Scholar
- Kim86.Knn, W., D Remet, and D Batory, Query Processmg m Database Systems, Spnnger Verlag, 1986Google Scholar
- Kirk83.#ck, S., C D. Gelatt, Jr. and M. P. Vocclu, "OpU#tlon by Simulated Annealing", Sctence 220, 4598 (May 1983), pp. 671-680.Google Scholar
- Kooi80.Kool, R. P., "The OpUm#n of Queries an Relational Databases", Ph D. Thesis, Case Western Reserve Umvers#ty, September 1980. Google ScholarDigital Library
- Kris86.Knshnamurthy, R., H. Boral, and C. Zamolo, "OptumzaRton of Nonrecurslve Queries', m Proc 12th lnternatwnal VLDB Conference, Kyoto, Japan, August 1986, pp 128-137 Google ScholarDigital Library
- Mack86a.Mackert, L F and G. M. Lohman, "R* Vahda- Uon and Performance Evaluauon for Distributed Queries', m Proc 12th Internattonal VLDB Conference, Kyoto, Japm, August 1986, pp 149-159. Google ScholarDigital Library
- Mack86b.M_ackert, L. F. and G M Lohman, "R* Vahdalion and Performance EvaluaUon for Local Quenes', m Proceechn&s of the 1986 A CM- SIGMOD Conference on the Management of Data, Washington, DC, May 1986, pp. 84-95 Google ScholarDigital Library
- Mitr85.Mltra, D., F Romeo, and A. Sanglovanm- V#telh, "Convergence and Finite-Time Belmvmr of Stmulat# Anneahng", m Proc 24th Conference on Decuwn and Control, FL Lauderdale, FL, December 1985.Google Scholar
- Naug86.Naughton, J., "Opmnmng Funcum-Free Recurrove Inference Rules", Computer Sctew# Techmcal Relx# Stanford Umvefslty, Stanford, CA, May 1986 Google ScholarDigital Library
- Rich83.Rich, E., ArtOctal lntelhgence, McGraw-Han, New York, N.Y., 1983.Google Scholar
- Rome84.Romeo, F., A. Sanglovanm-Vmcentelh, and C Sechen, "Research on Stmulated Anneathng at Berkeley", m Proc 1984 IEEE lnternatwnal Conference on Conjurer Design, Port Chester, N.Y., October 1984, pp. 652-657Google Scholar
- Rome85.Romeo, F and A. Sangtovanm-Vmcentelh, "Probabdlstl~ Hdl Clnnbmg Algcmthms: Propemes and Apph#', m Proc 1985 Chapel Hdl Conference on VLSI, e(hted by H. Fuchs, Computer Science Press, Chapel Hall, N C, 1985, pp 393-417Google Scholar
- Rose80.Rosenknmtz, D J and H B Hunt M, "Processmg Ccmjuncuve Predwattes and Quertes', m Proc 6th Internattonal VLDB Conference, Montreal, Canada, October 1980, pp. 64-72.Google Scholar
- Sacc86.Sacca, D and C. Zamolo, "The Geaerahzed Countmg Method for Recurslve Logtc Queries', m Proceedings of the lnternatwnal Conference on Database Theory, Rome, Italy, October 1986 Google ScholarDigital Library
- Sagi86.Sager, Y., "Opummng Datalog Prooan#", m Prepnnts of the Workshop on Foundanons of Deducave Databases and Logtc Progranmung, Waslungton, DC, August 1986, pp 136-162.Google Scholar
- Sech86a.Seclw#, C. and A. Sangtovanm-Vmcentelh, "TnnbexWolf 3.2: A New Standard Cell Placemeat and Global Routing Package', m Proc Design Automatwn Conference, Las Vegas, NV, June 1986. Google ScholarDigital Library
- Sech86b.Sechen, C., private commumcauon, June 1986.Google Scholar
- Seli79.Selinger, P. et aL, "Access Path Selecuon m a Relational Data Base System', in Proceedings of the 1979 ACM-#GMOD Conference on the Management of Data, Beelon, MA, June 1979, pp. 23-34. Google ScholarDigital Library
- sell86.Sellis, T. K., "Global Query Opumization", m Proceechngs of the 1986 ACM-SIGMOD Conference on the Management of Data, Washington, DC, May 1986, 191-205. Google ScholarDigital Library
- Ston76.S tonebraker, M., E. Wong, P. Kreps, and G. Held, "The Deign and Implementatton of INGRES", ACM Transacnons on Database Systems 1, 3 (September 1976), pp. 189-222. Google ScholarDigital Library
- Vald86.Valdunez, P. and H. Boral, "Evaluauon of Recurstve Queries Using Jom Indw.es", m Proceedings of the 1st lnternatwnal Conference on Expert Database Systems, Charleston, SC, Aprd 1986, pp. 197-208.Google Scholar
- Wile83.Wflemky, R.,LlSPcraft, 1983Google Scholar
- Wong76.Wong, E and K. Youssefi, "#pos#tton - A Strategy for Query processmg", ACM Transactwns on Database Systems 1, 3 (Seplember 1976), pp. 223-241. Google ScholarDigital Library
Index Terms
- Query optimization by simulated annealing
Recommendations
Query optimization by simulated annealing
Query optimizers of future database management systems are likely to face large access plan spaces in their task. Exhaustively searching such access plan spaces is unacceptable. We propose a query optimization algorithm based on simulated annealing, ...
Query Optimization for Ontology-Mediated Query Answering
WWW '24: Proceedings of the ACM on Web Conference 2024Ontology-mediated query answering (OMQA) consists in asking database queries on knowledge bases (KBs); a KB is a set of facts called the KB's database, which is described by domain knowledge called the KB's ontology. A widely-investigated OMQA technique ...
Synopses for query optimization: A space-complexity perspective
Special Issue: SIGMOD/PODS 2004Database systems use precomputed synopses of data to estimate the cost of alternative plans during query optimization. A number of alternative synopsis structures have been proposed, but histograms are by far the most commonly used. While histograms ...
Comments