maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2016-2-153-163mais-325Research ArticleОригинальные статьиArticlesОб эффективности минимизирующего подхода к оптимизации запросовOn the Effectiveness of the Minimization Approach to the Query OptimizationМендковичН. А.MendkovichN.

инженер

engineer

mend@f-group.ruООО «Фринет Групп», Ленинский проспект, 47, Москва, 119991 РоссияРоссияFREENet Group Ltd., Leninsky Ave. 47, Moscow, 119991 Russia,Russian Federation201620042016232153163Copyright © Мендкович Н.А., 20162016Мендкович Н.А.Mendkovich N.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/325

Стандартной проблемой использования СУБД является недостаток эффективности и высокая стоимость доступа к хранимым данным. Допустимый уровень работы системы может достигаться с помощью технологий оптимизации запросов, определяющих наиболее эффективный способ выполнения конкретного запроса с помощью его модификации и определения возможных планов выполнения. 

Целью данной работы является доказательство эффективности алгоритмов минимизации запроса, основанных на минимизации ограничения запроса и удаления избыточных условий. 

Статья представляет алгоритмы минимизации, основанные на математических преобразованиях, определяющих и удаляющих избыточные условия из ограничения запроса, чтобы упростить его. Она включает алгоритмы, основанные на технологиях «поглощения условий», первичных импликант и минимизации множеств линейных неравенств. 

Работа также включает теоретическое доказательство эффективности минимизирующего подхода, основанного на упрощении ограничения. Мы также рассматриваем экспериментальные результаты применения этих технологий оптимизации и их влияния на скорость обработки запроса. В конце мы представляем обзор влияния минимизации запроса на весь процесс оптимизации запроса. 

A standard problem of DBMSs usage is a lack of efficiency and high cost of the access to the stored data. The acceptable level of system performance may be achieved by query optimization technics that determine the most efficient way to execute a given query by its modification and considering possible query execution plans. The goal of this paper is to prove the efficiency of the query minimization algorithms based on minimization of the query restriction by elimination of the redundant conditions. The paper represents minimization algorithms based on the mathematical transformations, which detect and remove redundant conditions from query restriction to simplify it. It includes minimization algorithms based on “condition absorption”, prime implicants, and a set of linear inequalities minimization technics. The paper also includes theoretical justification of the efficiency of minimization approach to the query optimization based on restriction simplification. We also observe experimental results of the implementation of these optimization techniques and their influence on the query processing speed. In the end, we represent an observation of the query minimization impact on the whole optimization process 

оптимизация запросовлексическая оптимизация запросовquery optimizationlexical optimizationReferencesHall P. A. V., “Optimization of single expressions in a relational data base system”, IBM Journal of Research and Development, 20:3 (1976), 244–257.Hall P. A. V., “Optimization of single expressions in a relational data base system”, IBM Journal of Research and Development, 20:3 (1976), 244–257.Bellamkonda S. at al., “Enhanced Subquery Optimizations in Oracle”, Proceedings of the 35th international conference on Very large data base, August, 2009, 2, 2009, 1368.Bellamkonda S. at al., “Enhanced Subquery Optimizations in Oracle”, Proceedings of the 35th international conference on Very large data base, August, 2009, 2, 2009, 1368.“Chapter 7. Optimization”, MySQL 5.5 Reference Manual. http://dev.mysql.com/doc/refman/5.5/en/optimization.html.“Chapter 7. Optimization”, MySQL 5.5 Reference Manual. http://dev.mysql.com/doc/refman/5.5/en/optimization.html.“PostgreSQL 8.3.3”, postgresql-8.3.3/src/backend/optimizer/util/predtest.c.“PostgreSQL 8.3.3”, postgresql-8.3.3/src/backend/optimizer/util/predtest.c.“Query Optimization in Oracle Database 10g Release 2. P. 9”.“Query Optimization in Oracle Database 10g Release 2. P. 9”.Seshadri P. at al., “Cost-Based Optimization for Magic: Algebra and Implementation”, ACM SIGMOD Record, 25:2 (1996).Seshadri P. at al., “Cost-Based Optimization for Magic: Algebra and Implementation”, ACM SIGMOD Record, 25:2 (1996).Faber W., Greco G., Leone N., “Sets and their application to data integration”, Journal of Computer and System Sciences, 73:4 (2007).Faber W., Greco G., Leone N., “Sets and their application to data integration”, Journal of Computer and System Sciences, 73:4 (2007).Mendkovich N., Kuznetcov S., “New Algorithms for Lexical Query Optimization”, Proceedings of the 31st International Conference on Information Technology Interfaces, Cavtat/Dubrovnik, June 22–25, 2009 (Zagreb, University of Zagreb), 2009, 187–192.Mendkovich N., Kuznetcov S., “New Algorithms for Lexical Query Optimization”, Proceedings of the 31st International Conference on Information Technology Interfaces, Cavtat/Dubrovnik, June 22–25, 2009 (Zagreb, University of Zagreb), 2009, 187–192.Кузнецов С.Д., Мендкович Н.А., “Новые алгоритмы лексической оптимизации запросов”, Моделирование и анализ информационных систем, 16:4 (2009), 22–33; [Kuznetsov S.D., Mendkovich N.A., “New algorithms for query modifications”, Modeling and Analysis of Information Systems, 16:4 (2009), 22–33, (in Russian).]Кузнецов С.Д., Мендкович Н.А., “Новые алгоритмы лексической оптимизации запросов”, Моделирование и анализ информационных систем, 16:4 (2009), 22–33; [Kuznetsov S.D., Mendkovich N.A., “New algorithms for query modifications”, Modeling and Analysis of Information Systems, 16:4 (2009), 22–33, (in Russian).]Кузнецов С.Д., Мендкович Н.А., “Оптимизация конъюнктов условий в составе запросов”, Модел. и анал. информ. систем, 18:3 (2011), 144–154; [Kuznetsov S.D., Mendkovich N.A., “Optimization of queries containing conjunctions of conditions”, Modeling and Analysis of Information Systems, 18:3 (2011), 144–154, (in Russian).]Кузнецов С.Д., Мендкович Н.А., “Оптимизация конъюнктов условий в составе запросов”, Модел. и анал. информ. систем, 18:3 (2011), 144–154; [Kuznetsov S.D., Mendkovich N.A., “Optimization of queries containing conjunctions of conditions”, Modeling and Analysis of Information Systems, 18:3 (2011), 144–154, (in Russian).]“BNF Grammar for ISO/IEC 9075-2:2003”, http://savage.net.au/SQL/sql-20032.bnf.html.“BNF Grammar for ISO/IEC 9075-2:2003”, http://savage.net.au/SQL/sql-20032.bnf.html.Khaitan P. at al., “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, 147–152.Khaitan P. at al., “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, 147–152.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, 91–102.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, 91–102.Satoh K. at al., “Local and Global Query Optimization Mechanisms”, Proceedings of 11th International Conference on Very Large Data Bases, August 21-23, 1985, Stockholm, Sweden (Berlin: Morgan Kaufmann), 1985, 408–409.Satoh K. at al., “Local and Global Query Optimization Mechanisms”, Proceedings of 11th International Conference on Very Large Data Bases, August 21-23, 1985, Stockholm, Sweden (Berlin: Morgan Kaufmann), 1985, 408–409.Hellerstein J. M., Stonebraker M., “Predicate Migration: Optimizing Queries with Expensive Predicates”, ACM SIGMOD Record, 22:2 (1993), 267–276.Hellerstein J. M., Stonebraker M., “Predicate Migration: Optimizing Queries with Expensive Predicates”, ACM SIGMOD Record, 22:2 (1993), 267–276.Chaudhuri S., “Optimization of queries with user-defined predicates”, Journal ACM Transactions on Database Systems (TODS), 24:2 (1999), 177–228.Chaudhuri S., “Optimization of queries with user-defined predicates”, Journal ACM Transactions on Database Systems (TODS), 24:2 (1999), 177–228.Fontoura M. at al., “Efficiently Evaluating Complex Boolean Expressions”, Proceedings of the 2010 ACM SIGMOD International Conference on Management of data (New York: ACM), 2010, 3–4.Fontoura M. at al., “Efficiently Evaluating Complex Boolean Expressions”, Proceedings of the 2010 ACM SIGMOD International Conference on Management of data (New York: ACM), 2010, 3–4.Vorwerk K., Paulley G. N., “On Implicate Discovery and Query Optimization”, Proceedings of the International Database Engineering and Applications Symposium, IDEAS 2002. July 17-19, 2002, Edmonton, Canada (Los Alamitos: Computer Society), 2002, 2–12.Vorwerk K., Paulley G. N., “On Implicate Discovery and Query Optimization”, Proceedings of the International Database Engineering and Applications Symposium, IDEAS 2002. July 17-19, 2002, Edmonton, Canada (Los Alamitos: Computer Society), 2002, 2–12.Roy P. at al., “Efficient and extensible algorithms for multi-query optimization”, Proceedings of the 2000 ACM SIGMOD International Conference on Management of data (ACM New York, NY, USA), 2000, 249–260.Roy P. at al., “Efficient and extensible algorithms for multi-query optimization”, Proceedings of the 2000 ACM SIGMOD International Conference on Management of data (ACM New York, NY, USA), 2000, 249–260.Dalvia N. N. at al., “Pipelining in multi-query optimization”, Journal of Computer and System Science, 66:4 (2003).Dalvia N. N. at al., “Pipelining in multi-query optimization”, Journal of Computer and System Science, 66:4 (2003).Ioannidis Y. E., “Query Optimization”, ACM Computing Surveys (CSUR), 28:1 (1996), 121–123.Ioannidis Y. E., “Query Optimization”, ACM Computing Surveys (CSUR), 28:1 (1996), 121–123.Neumann T., “Query Simplification: Graceful Degradation for Join-Order Optimization”, SIGMOD’09, June 29–July 2, 2009, Providence, Rhode Island, USA, 2009, 405–406.Neumann T., “Query Simplification: Graceful Degradation for Join-Order Optimization”, SIGMOD’09, June 29–July 2, 2009, Providence, Rhode Island, USA, 2009, 405–406.Moerkotte G., Neumann T., “Dynamic programming strikes back”, Proceedings of SIGMOD Conference 2008, June 9–12, 2008, Vancouver, BC, Canada, 2009.Moerkotte G., Neumann T., “Dynamic programming strikes back”, Proceedings of SIGMOD Conference 2008, June 9–12, 2008, Vancouver, BC, Canada, 2009.

The authors declare that there are no conflicts of interest present.