Обзор развития методов лексической оптимизации запросов
https://doi.org/10.15514/ISPRAS-2012-23-12
Аннотация
Статья посвящена лексической оптимизации запросов и описывает работы, опубликованные в течение последних четырех десятилетий. Особое внимание уделяется таким подходам к оптимизации как модификация, украшение и сокращение запросов. Обсуждаются алгоритмы оптимизации для реляционных и нереляционных СУБД.
Список литературы
1. Palermo F. A data base search problem // Proceedings of the 4th Symposium on Computer and Information Sciences, Virginia, USA, 1972. Restion: AFIPS Press, 1972. Pp. 67-101.
2. Jarke M., Koch J. Query Optimization in Database Systems // ACM Computing Surveys (CSUR), 1984. March, Volume 16, Issue 2. Pp. 111-152.
3. Mannino M. V., Chu P., Sager T. Statistical profile estimation in database systems // ACM Computing Surveys, 1988. September, Volume 20, Issue 3. Pp. 191-221.
4. Ionnidis Y. E. Query Optimization // The Computer Science and Engineering Handbook. Boca Raton: CRC Press, 1996. Pp. 1038-1054.
5. Chaudhari S. An Overview of Query Optimization in Relational Systems // Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems. New York: SIGMOD, 1998. Pp. 34-43.
6. Кузнецов С. Д. Методы оптимизации выполнения запросов в реляционных СУБД // http://www.citforum.ru/database/articles/art_26.shtml [Обращение 20 сентября 2012].
7. Graefe G. Query Evaluation Techniques for Large Databases // ACM Computing Surveys, 1993. Volume 25, Issue 2. P. 73-169.
8. Дейт К. Дж. Введение в системы баз данных. Москва – Санкт-Петербург – Киев: Издательский дом «Вильямс», 2001. 1072 с.
9. Ozsu M. N., Valduriez P. Principles of Distributed Database Systems. Second Edition. New Jersey: Prentice Hall International, 1999. 666 pp.
10. Ramakrishnan R., Gehrcke J. Database System Management. 2nd Edition. Singapore: The McGraw-Hill Book Co, 2000. 906 pp.
11. Karayannidis N. Query Optimization Bibliography, http://www.dbnet.ece.ntua.gr/~nikos/edith/qopt_bibl/, [Обращение 20 сентября 2012].
12. MySQL 5.5 Reference Manual. Chapter 7. Optimization. http://dev.mysql.com/doc/refman/5.5/en/optimization.html, [Опубликовано в 2010 году, обращение 20 сентября 2012].
13. Веллин Л., Томсон Дж. MySQL. Учебное пособие. Перевод с английского. М.: Издательский дом «Вильямс», 2005. 292 c.
14. Upgrading from Oracle Database 10 g to 11 g: What to expect from the Optimizer. An Oracle White Paper, November 2009. Redwood Shores: Oracle Corporation, 2009. 36 pp.
15. Comparison of Materialized Views & Analytic Workspaces in Oracle Database 11 g. An Oracle White Paper, March 2008. Redwood Shores: Oracle Corporation, 2008. 27 pp.
16. Markl V., Lohman G. M., Raman V. LEO: An autonomic query optimizer for DB2 // IBM System Journal, 2003. V. 42, № 1. Pp. 98-106.
17. PostgreSQL 8.1.19 Documentation. Chapter VII: Internals, http://www.postgresql.org/docs/8.1/interactive/internals.html, [Обращение 20 сентября 2012].
18. Ioannidis Y. The History of Histograms // Proceedings of 29th International Conference on Very Large Data Bases, September 9-12, 2003, Berlin, Germany. Berlin: Morgan Kaufmann, 2003. Pp. 19-30.
19. Halevy Y. Answering queries using views: A survey // The International Journal on Very Large Data Bases, December 2001. Volume 10 Issue 4. Pp. 270-294.
20. Braga D., Ceri S., Grossniklaus M. Join Methods and Query Optimization // Lecture Notes on Computer Science, 2010. Issue 5950. Pp. 188-210.
21. Query Optimization in Oracle Database 10g Release 2. An Oracle White Paper, June 2005. Redwood Shores: Oracle Corporation, 2005. 31 pp.
22. Смирнов С. Н., Задворьев И. С. Работаем с Oracle: Учебное пособие. М: Гелиос АРВ, 2002. 496 сс.
23. Shenoy S. T., Ozsoyoglu Z. M. A System for Semantic Query Optimization // SIGMOD Record, 1987. Volume 16, Number 3. Pp. 181-195
24. Geng K., Dobbie G., Meng Y. Survey of XML Semantic Query Optimization // Proceedings 4th International Conference on Internet Computing for Science and Engineering (ICICSE), Harbin, 2009. Washington D. C.: IEEE Computer Society, 2009. Pp. 297-300
25. Зверев Д. Л. Оптимизация потоков простых SQL-запросов: Диссертация кандидата технических наук: 05.13.11. Санкт-Петербург: Санкт-Петербургский Государственный Университет Аэрокосмического Приборостроения, 2005. 169 сс.
26. XQuery 1.0 and XPath 2.0 Formal Semantics. World Wide Web Consortium (W3C), W3C Recommendation, 2007. http://www.w3.org/TR/xquery-semantics/, [Обращение 20 сентября 2012].
27. Deutsch A., V. Tannen XML queries and constraints, containment and reformulation // Theoretical Computer Science, 2005. № 336. Pp. 57-87.
28. Fan W., Xu J. Y., Ding B., Qin L., Rastogi R. Query Translation from XPath to SQL in the Presence of Recursive DTDs // Very Large Data Bases Journal, 2009. Issue 18. Pp. 857-883.
29. Барашев Д. В., Горшкова Е. А., Новиков Б. А. Оптимизация представления XML документов в реляционной базе данных // Вторая Всероссийская научная конференция. Электронные библиотеки. Перспективные методы и технологии, электронные коллекции. 26-28 сентября, Протвино, 2000. C. 224-229.
30. Manolescu I., Florescu D., Kossmann D. Answering xml queries on heterogeneous data sources // Proceedings of the 27th International Conference on Very Large Data Bases, San Francisco, 2001. San Francisco: Morgan Kaufmann Publishers Inc., 2001. Pp.241-250.
31. Krishnamurthy R., Kaushik R., Naughton J. XML-SQL query translation literature: The state of the art and open problems // XML Database Symposium (XSym 2003) at VLDB 2003. Berlin, September 2003. Lecture Notes in Computer Science, Volume 2824, 2003. Pp. 1-18.
32. Cluet S., Moerkotte G. Nested queries in object bases // Proceedings of the 4th International Workshop on Database Programming Languages: Object Models and Language. Manhattan, New York City, USA, 30 August-1 September, 1993. London: Springer-Verlag, 2004. Pp. 226-242.
33. Steenhagen H. J., Apers P. M. G., Blanken H.M., de By R. A. From nested-loop to join queries in OODB // Proceedings of the 20th International Conference on Very Large Data Bases, 1994. Santiago: Morgan Kaufman, 1994 P. 618-629.
34. Frasincar F., Houben G.-J., Pau C. XAL: An algebra for XML query optimization // Proceedings of the 13th Australasian Database Conference, Australian Computer Society, Inc. Darlinghurst, Australia, 2002. Volume 5. Melbourne: Australian Computer Society, 2002. Pp. 49-56.
35. May N., Helmer S., Moerkotte G. Strategies for Query Unnesting in XML Databases // ACM Transactions on Database Systems (TODS) 2006. Volume 31, Issue 3. Pp. 968-1013.
36. Re C., Simeon J., Fernandez M. F. A Complete and Efficient Algebraic Compiler for XQuery // Proceedings of the 22nd International Conference on Data Engineering, ICDE 2006, 3-8 April, 2006, Atlanta, GA, USA: IEEE Computer Society, 2006. Lecture Notes on Computer Society, 2007. Volume 4797. Pp. 81-96.
37. Ghelli G., Onose N., Rose K., Siméon J. XML Query Optimization in the Presence of Side Effects // Proceedings of the 2008 ACM SIGMOD international conference on Management of data. New York, USA, 2008. New York: ACM, 2008. Pp. 339-352.
38. Lukichev M., Barashev D. XML Query Algebra for Cost-based Optimization // SYRCODIS*07 The Fourth Spring Young Researchers Colloquium on Databases and Information Systems, Moscow, May 31 - June 1, 2007. http://ceur-ws.org/Vol-256/, [Обращение 20 сентября 2012].
39. Лукичев М. С. Оптимизация запросов в слабоструктурированной модели данных. Диссертация кандидата физико-математических наук: 05.13.11. Санкт-Петербург: Санкт-Петербургский Государственный Университет, 2009. 120 с.
40. Smith M., Chang P. Y. W. Optimizing the performance of a relational algebra database interface // Communications for the ACM, October, 1975. Volume 18, Issue 10. Pp. 568-579.
41. Hall P. A. V. Optimization of single expressions in a relational data base system // IBM Journal of Research and Development. Volume 20, Number 3, 1976. Pp. 244-257.
42. Chaudhuri S., Shim K. Including Group-By in Query Optimization // Proceedings of the 20th International Conference on Very Large Data Bases, Morgan Kaufmann, San Mateo, USA, 1994. San Francisco: Morgan Kaufmann Publishers Inc., 1994. Pp. 354-366.
43. Levy Y., Mumick I. S., Sagiv Y. Query Optimization by Predicate Move Around // Proceedings of the 20th International Conference on Very Large Data Bases, Morgan Kaufmann, San Mateo, USA, 1994. Morgan Kaufmann Publishers Inc., 1994. Pp. 96-107.
44. Wong E., Youssefi K. Decomposition - a strategy for query processing // ACM Transactions On Database Systems, September 1976. Volume 1, Number 3. Pp. 223–241.
45. Yannakakis M. Algorithms for acyclic database schemes // Proceedings of Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings. IEEE Computer Society 1981. New York: IEEE Press, 1981. Pp. 82-94.
46. McMahan B., Porter P., Pan G., M. Y. Vardi Projection Pushing Revisited // Proceedings of the 9th International Conference on Extending Database Technology, Heraklion, Crete, Greece, March 14-18, 2004. Berlin: Springer, 2004. Pp. 441-458.
47. McMahan B. J. Structural Heuristics for Query Optimization. Master of Science Degree Thesis. Houston: Rice University, 2004. 64 pp.
48. Kim W. On optimizing an SQL-Like Nested Query // ACM Transactions on Database Systems (TODS), September, 1982. Volume 7 Issue 3. Pp. 443-469.
49. Kisessling W. On Semantic Reefs and Efficient Processing of Correlation Queries Revisited // Proceedings of 11th International Conference for Very Large Data Bases. August 21-23, Stockholm, Sweden, 1985. New York: Morgan Kaufmann, 1985. Pp. 241-250.
50. Ganski R. A., Wong H. K. T. Optimization of Nested SQL Queries Revisited // Proceedings of the ACM SIGMOD international conference on Management of data. San Francisco, May 1987. New York: ACM, 1987. Pp. 23-33.
51. Muralikrishna M. Improved unnesting algorithms for join aggregate SQL queries // Proceedings of the 18th International Conference on Very Large Data Bases, August 23-27, Vancouver, Canada, 1992. San Francisco: Morgan Kaufmann Publishers Inc., 1992. Pp. 91-102.
52. Khaitan P., Satish K. M., S. B. Korra, S. K. Jena Improved query plans for unnesting nested SQL queries // Proceedings of 2nd International Conference on Computer Science and its Applications, December 10-12, South Korea, 2009. Jeju Island : IEEE, 2009. Pp. 147-152.
53. Fegaras L., D. Levine, S. Bose, V. Chaluvadi Query processing of streamed XML data // Proceedings of the eleventh international conference on Information and knowledge management. ACM Press, New York, USA, 2002. Berlin: Springer, 2004. Pp. 195-215.
54. May N., Moerkotte G. Normalization and Translation of XQuery // Advanced Applications and Structures in XML Processing: Label Streams, Semantics Utilization and Data Query Technologies. Hershey: Igi Global Publishing, 2010. Pp. 283-307.
55. Pirahesh H., Hellerestein J., Hasan W. Extensible/rule based query rewrite optimization in Starburst // ACM SIGMOD Record, June 1, 1992. Volume 21, Issue 2. Pp. 39-48.
56. MySQL Nested-Loop Join Algorithms, http://dev.mysql.com/doc/refman/5.5/en/nested-loop-joins.html, [Обращение 20 сентября 2012].
57. Bancilhon F., Maierl D., Sagiv Y., Ullman J. D. Magic Sets and Other Strange Ways to Implement Logic Programs // Proceedings of the Fifth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, Cambridge, Massachusetts, March 24-26, 1986. New York: ACM, 1986. Pp. 1-15.
58. Mumick S., Finkelsteint S. J., Pirahesh H., Ramakrishnan R. Magic Conditions // ACM Transactions on Database Systems (TODS), March 1996. Volume 21 Issue 1. Pp. 107-155.
59. Mumick I. S., Finkelstein S. J., Pirahesh H., Ramakrishnan R. Magic is Relevant // Proceedings of the 1990 ACM SIGMOD international conference on Management of data. New York: ACM, 1990. Pp. 247-258.
60. Jezek K., Zima M. Query optimization in deductive programs with aggregates // Proceeding of the 4th International Conference Information Systems Modelling, Ostrava: MARQ, 2001. Pp. 85-92.
61. Seshadri P., Hellerstein J. M., Pirahesh H., Cliff Leung T. Y., Ramakrishnan R., Srivastava D., Stuckey P. J., Sudarshan S. Cost-Based Optimization for Magic: Algebra and Implementation // ACM SIGMOD Record, June 1996. Volume 25, Issue 2, Pp. 28-33.
62. Sagiv Y. Is there anything better than magic? // Logic Programming, Proceedings of the 1990 North American Conference, Austin, Texas, October 29 - November 1, 1990. Austin: MIT Press 1990. Pp. 235-254.
63. Sippu S., Soisalon-Soininen E. An Analysis of Magic Sets and Related Optimization Strategies for Logic Queries // Journal of the ACM, November 1996. Volume 43, № 6. Pp. 1046-1088.
64. Azevedo P. J. Magic sets with full sharing // The Journal of Logic Programming, 1997. Volume 30, № 3. Pp. 223-237.
65. Faber W., Greco G., Leone N. Magic Sets and their application to data integration // Journal of Computer and System Sciences, June 2007. Volume 73, Issue 4. Pp. 584-609.
66. Ruckhaus E., Ruiz E., Vidal M. E. OnEQL: An Ontology Efficient Query Language Engine for the Semantic Web // Proceedings of the Workshop on Applications of Logic Programming to the Web, Semantic Web and Semantic Web Services (ALPSWS), Porto, Portugal, September 13th, 2007. Porto: CEUR Workshop Proceedings, 2007. Pp. 65-88.
67. Alviano M., Faber W., Greco G., Leone N. Magic Sets for Disjunctive Datalog Programs // Artificial Intelligence, 2012. Volume 187. Pp. 156-192.
68. Almendros-Jiménez M., Becerra-Terón A., Enciso-Banos F. J. Magic Sets for the XPath Language // Journal of Universal Computer Science, 2006. Volume 12, № 11. Pp. 1651-1678.
69. Ozcan F., Seemann N., Wang L. XQuery Rewrite Optimization in IBM DB2 pureXML // IEEE, Data Engineering Bulletin, December 2008. Volume 34, Number 4. Pp. 25-32.
70. Kolaitis P. G., Martin D.L., Thakur M.N. On the complexity of the containment problem for conjunctive queries with built-in predicates // Proceeding of the 17th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), Seattle, Washington, USA, June 1-3, 1998. New York: ACM, 1998. Pp. 197-204.
71. Benedikt M., Gottlob G. The Impact of Virtual Views on Containment // Proceedings of the The Very Large Data Bases, September 2010. Volume 3 Issue 1-2. Pp. 297-308.
72. Kolaitis P. G., Vardi M. Conjunctive-query containment and constraint satisfaction // Proceeding of the 17th ACM SIGACT-SIGMOD-SIGART SIGART Symposium on Principles of Database Systems (PODS), Seattle, Washington, USA, June 1-3, 1998. New York: ACM, 1998. Pp. 205-213.
73. Kolaitis P. G., Vardi M. Conjunctive-Query Containment and Constraint Satisfaction // Journal of Computer and System Sciences, 2000. № 61. Pp. 302-332.
74. Goldstein J., Larson P.-A. Optimization Queries Using Materialized Views: A Practical Scalable Solution // ACM SIGMOD Record, June 2001. Volume 30 Issue 2. Pp.331-342.
75. Пашинин О. В. Оптимизация запросов к базам данных // Математические структуры и моделирование. Выпуск 17, 2007. С. 100-107ю
76. Chandra K., Merlin P. M. Optimal Implementation of Conjunctive Queries in Relational Databases // Proceedings of the 9th annual ACM symposium on Theory of computing, May, 1977. New York: ACM, 1977. Pp. 77-90.
77. Stroet J. W. M., Engmann R. Manipulation of expressions in a relational algebra // Information Systems, 1979. Volume 4, Issue 4. Pp. 195-203.
78. Aho V., Sagiv Y., Ullman J. D. Equivalences among relational expressions // Society for Industrial and Applied Mathematics Journal on Computing, 1979. Volume 8, Issue 2. Pp. 218-246.
79. Aho V., Sagiv Y., Ullman J. D. Efficient optimization of a class of relational expressions // Journal ACM Transactions on Database Systems (TODS), December 1979. Volume 4, Issue 4. Pp.435-454.
80. Sagiv Y., Yannakakis M. Equivalences among relational expressions with the union and difference operators // Journal of the ACM, October 1980. Volume 27, Issue 4. Pp. 633-655.
81. 2.1.2 How MySQL Optimizes WHERE Clauses http://dev.mysql.com/doc/refman/5.5/en/where-optimizations.html, [Обращение 20 сентября 2012].
82. Приложение PostgreSQL 8.3.3., http://www.postgresql.org/download/, [Обращение 20 сентября 2012]. Адрес файла, содержащего обсуждаемый код, в архиве postgresql-8.3.3srcbackendoptimizerutilpredtest.c.
83. Veitch E. W. A Chart Method for Simplifying Truth Functions // ACM Annual Conference/Annual Meeting: Proceedings of the 1952 ACM Annual Meeting. Pittsburg: ACM, NY, 1952. Pp. 127-133.
84. Karnaugh M. The Map Method for Synthesis of Combinational Logic Circuits // Transactions of the American Institute of Electrical Engineers, November 1953. Part I, № 72 (9). Pp. 593-599.
85. Quin W. V. On Cores and Prime Implicants of Truth Functions // American Mathematics Monthly, 1959. V. 66, № 9. P. 755-760.
86. McCluskey E. J. Minimization of Boolean Functions // The Bell System Technical Journal, November 1956. V. 35, Issue 5. Pp. 1236-1249.
87. Wu M.-C. Query Optimizatiom for Selecting Using Bitmaps // ACM SIGMOD Record, June 1999. Volume 28 Issue 2. Pp. 227-238.
88. Das Sarma A., Theobald M., Widom J. Exploiting Lineage for Confidence Computation in Uncertain and Probabilistic Databases. Technical Report. Stanford, 2007. http://ilpubs.stanford.edu:8090/800/, [Обращение 20 сентября 2012].
89. Тарасенко П. Ф., Бухарова М. Ф. Технология «The Reporter» для построения отчетов по базам данных // Вестник Томского Государственного Университета, № 275, апрель 2002. С. 167-176.
90. Mendkovich N., Kuznetcov S. New Algorithms for Lexical Query Optimization // Proceedings of the 31st International Conference on Information Technology Interfaces. Cavtat/Dubrovnik, Croatia, June 22-25, 2009. Zagreb: University of Zagreb, 2009. Pp. 187-192.
91. Кузнецов С. Д., Мендкович Н. А. Новые алгоритмы лексической оптимизации запросов // Модели и анализ информационных систем, 2009. Т. 16, № 4. С. 22-33.
92. Мендкович Н. А., Кузнецов С. Д. Оптимизация конъюнктов условий в составе запросов // Модели и анализ информационных систем, 2011. Т. 18, № 3. С. 144-154.
93. Bellamkonda S., Ahmed R., Witkowski A., Amor A., Zait M., Lin Ch.-Ch. Enhanced Subquery Optimizations in Oracle / // Proceedings of the 35th international conference on Very large data base, August 2009. Volume 2 Issue 2. Pp. 1366-1377.
94. Chaudhuri S. Query Optimizers: Time to Rethink the Contract? // Proceedings of the ACM SIGMOD International Conference on Management of Data, Providence, Rhode Island, USA, June 29 - July 2, 2009. New York: ACM, 2009. Pp. 961-968.
Рецензия
Для цитирования:
Мендкович Н.А., Кузнецов С.Д. Обзор развития методов лексической оптимизации запросов. Труды Института системного программирования РАН. 2012;23. https://doi.org/10.15514/ISPRAS-2012-23-12
For citation:
Mendkovich N.A., Kuznetsov S.D. An Overwiew of Evolution of Lexical Query Optimization Techniques. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2012;23. (In Russ.) https://doi.org/10.15514/ISPRAS-2012-23-12
Послать статью по эл. почте 