inttransИнтеллектуальный транспортIntelligent transport3033-6007АО «НИИАС»NYDIOBinttrans-107Research ArticleЦИФРОВЫЕ МЕТОДЫ НА ЖЕЛЕЗНОДОРОЖНОМ ТРАНСПОРТЕОЦЕНКА ПЛАНОВ ВЫПОЛНЕНИЯ SQL ЗАПРОСОВ ДЛЯ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧEVALUATION OF EXECUTION PLANS OF SQL QUERY FOR SOLVING TRANSPORT PROBLEMSДулинС. К.DulinS. K.

д.т.н., профессор, главный научный сотрудник

D.ofSci., Professor, Chief Researcher

skdulin@mail.ruРябцевА. Б.RyabtsevA. V.

аспирант

Postgraduate student

antr5@mail.ruАО «НИИАС»; ИПИ ФИЦ ИУ РАНРоссияJSC «NIIAS»; Federal Research Center "Informatics and Management" of the RASRussian FederationМосковский физико-технический институт (МФТИ)РоссияMoscow Institute of Physics and Technology (MIPT)Russian Federation20231509202601(25)3843Copyright © Дулин С.К., Рябцев А.Б., 20262026Дулин С.К., Рябцев А.Б.Dulin S.K., Ryabtsev A.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.intelligent-transport.ru/jour/article/view/107

Существующие подходы к проблеме поиска оптимального плана выполнения SQL запроса далеки от идеала. Учитывая многопараметрический характер транспортных задач, минимизация времени выполнения запроса может иметь решающее значение. Функция стоимости, которая каждому плану ставит в соответствие время его выполнения должна удовлетворять следующим требованиям: 1) отношение порядка стоимостей должно как можно больше совпадать с отношением порядка времени, 2) стоимость любого плана не может быть больше стоимости другого плана, полученного путём добавления операций соединений. В работе рассматривается задача оптимизации планов выполнения SQL запросов с помощью методов машинного обучения. В работе подробно описан традиционный подход к решению данной задачи, рассмотрены его недостатки. Также приведён анализ существующих методов машинного обучения, которые призваны устранить ряд недостатков традиционного оптимизатора. Рассмотрены их преимущества и недостатки.

Existing approaches to the problem of finding a good SQL query execution plan are far from ideal. Given the multi-parameter nature of transport problems, the optimal plan that minimizes query execution time can be critical. The cost function that associates each plan with its execution time must satisfy the following requirements: 1) the order of cost ratio should match the order of time as much as possible, 2) the cost of any plan cannot be greater than the cost of another plan obtained by adding join operations. The paper considers the problem of optimizing SQL query execution plans using machine learning methods. The paper describes in detail the traditional approach to solving this problem, and considers its shortcomings. An analysis of existing machine learning methods is also given, which are designed to eliminate a number of shortcomings of the traditional optimizer. Their advantages and disadvantages are considered

ТРАНСПОРТОПТИМАЛЬНЫЙ ПЛАН ВЫПОЛНЕНИЯ ЗАПРОСАФУНКЦИЯ СТОИМОСТИМЕТОДЫ МАШИННОГО ОБУЧЕНИЯКАРДИНАЛЬНОСТЬ ТАБЛИЦЫTRANSPORTOPTIMAL QUERY EXECUTION PLANCOST FUNCTIONMACHINE LEARNING METHODSTABLE CARDINALITYReferencesM Muralikrishna and David J DeWitt. Equi-depth multidimensional histograms. Proceedings of the 1988 ACM SIGMOD international conference on Management of data. 1988, pp.28–36.M Muralikrishna and David J DeWitt. Equi-depth multidimensional histograms. Proceedings of the 1988 ACM SIGMOD international conference on Management of data. 1988, pp.28–36.P Griffiths Selinger, Morton M Astrahan, Donald D Chamberlin, Raymond A Lorie and Thomas G Price. Access path selection in a relational database management system. Readings in Artificial Intelligence and Databases. Elsevier, 1989, pp. 511–522.P Griffiths Selinger, Morton M Astrahan, Donald D Chamberlin, Raymond A Lorie and Thomas G Price. Access path selection in a relational database management system. Readings in Artificial Intelligence and Databases. Elsevier, 1989, pp. 511–522.Nicolas Bruno, Surajit Chaudhuri and Luis Gravano. STHoles: A multidimensional workloadaware histogram. Proceedings of the 2001 ACM SIGMOD international conference on Management of data. 2001, pp. 211–222.Nicolas Bruno, Surajit Chaudhuri and Luis Gravano. STHoles: A multidimensional workloadaware histogram. Proceedings of the 2001 ACM SIGMOD international conference on Management of data. 2001, pp. 211–222.Amol Deshpande, Minos Garofalakis and Rajeev Rastogi. Independence is good: Dependencybased histogram synopses for high-dimensional data. ACM SIGMOD Record 30.2 (2001), pp.199–210.Amol Deshpande, Minos Garofalakis and Rajeev Rastogi. Independence is good: Dependencybased histogram synopses for high-dimensional data. ACM SIGMOD Record 30.2 (2001), pp.199–210.Abraham Silberschatz, Henry F Korth and Shashank Sudarshan. Database system concepts. Vol. 5. McGraw-Hill New York, 2002.Abraham Silberschatz, Henry F Korth and Shashank Sudarshan. Database system concepts. Vol. 5. McGraw-Hill New York, 2002.Hai Wang and Kenneth C Sevcik. A multi-dimensional histogram for selectivity estimation and fast approximate query answering. Proceedings of the 2003 conference of the Centre for Advanced Studies on Collaborative research. 2003, pp.328–342.Hai Wang and Kenneth C Sevcik. A multi-dimensional histogram for selectivity estimation and fast approximate query answering. Proceedings of the 2003 conference of the Centre for Advanced Studies on Collaborative research. 2003, pp.328–342.Dimitrios Gunopulos, George Kollios, Vassilis J Tsotras and Carlotta Domeniconi. Selectivity estimators for multidimensional range queries over real attributes. VLDB Journal 14.2 (2005), pp. 137–154.Dimitrios Gunopulos, George Kollios, Vassilis J Tsotras and Carlotta Domeniconi. Selectivity estimators for multidimensional range queries over real attributes. VLDB Journal 14.2 (2005), pp. 137–154.Gavin Powell. Beginning database design. John Wiley & Sons, 2006.Gavin Powell. Beginning database design. John Wiley & Sons, 2006.Hector Garcia-Molina. Database systems: the complete book. Pearson Education India, 2008.Hector Garcia-Molina. Database systems: the complete book. Pearson Education India, 2008.Max Heimel, Martin Kiefer and Volker Markl. Self-tuning, GPU-accelerated kernel density models for multidimensional selectivity estimation. Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. 2015, pp. 1477–1492.Max Heimel, Martin Kiefer and Volker Markl. Self-tuning, GPU-accelerated kernel density models for multidimensional selectivity estimation. Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. 2015, pp. 1477–1492.Feifei Li, Bin Wu, Ke Yi and Zhuoyue Zhao. Wander join: Online aggregation via random walks. Proceedings of the 2016 International Conference on Management of Data. 2016, pp. 615–629.Feifei Li, Bin Wu, Ke Yi and Zhuoyue Zhao. Wander join: Online aggregation via random walks. Proceedings of the 2016 International Conference on Management of Data. 2016, pp. 615–629.Hazar Harmouch and Felix Naumann. Cardinality estimation: An experimental survey. Proceedings of the VLDB Endowment 11.4 (2017), pp. 499–512.Hazar Harmouch and Felix Naumann. Cardinality estimation: An experimental survey. Proceedings of the VLDB Endowment 11.4 (2017), pp. 499–512.Oleg Ivanov and S Bartunov. Adaptive query optimization in PostgreSQL. PGCon 2017 Conference, Ottawa, Canada. 2017.Oleg Ivanov and S Bartunov. Adaptive query optimization in PostgreSQL. PGCon 2017 Conference, Ottawa, Canada. 2017.Martin Kiefer, Max Heimel, Sebastian Breß and Volker Markl. Estimating join selectivities using bandwidth-optimized kernel density models. Proceedings of the VLDB Endowment 10.13 (2017), pp. 2085–2096.Martin Kiefer, Max Heimel, Sebastian Breß and Volker Markl. Estimating join selectivities using bandwidth-optimized kernel density models. Proceedings of the VLDB Endowment 10.13 (2017), pp. 2085–2096.Viktor Leis, Bernhard Radke, Andrey Gubichev, Alfons Kemper and Thomas Neumann. Cardinality Estimation Done Right: Index-Based Join Sampling. Cidr. 2017.Viktor Leis, Bernhard Radke, Andrey Gubichev, Alfons Kemper and Thomas Neumann. Cardinality Estimation Done Right: Index-Based Join Sampling. Cidr. 2017.Sanjay Krishnan, Zongheng Yang, Ken Goldberg, Joseph Hellerstein and Ion Stoica. Learning to optimize join queries with deep reinforcement learning. arXiv preprint arXiv:1808.03196 (2018).Sanjay Krishnan, Zongheng Yang, Ken Goldberg, Joseph Hellerstein and Ion Stoica. Learning to optimize join queries with deep reinforcement learning. arXiv preprint arXiv:1808.03196 (2018).Ryan Marcus and Olga Papaemmanouil. Deep reinforcement learning for join order enumeration. Proceedings of the First International Workshop on Exploiting Artificial Intelligence Techniques for Data Management. 2018, pp. 1–4.Ryan Marcus and Olga Papaemmanouil. Deep reinforcement learning for join order enumeration. Proceedings of the First International Workshop on Exploiting Artificial Intelligence Techniques for Data Management. 2018, pp. 1–4.Zhuoyue Zhao, Robert Christensen, Feifei Li, Xiao Hu and Ke Yi. Random sampling over joins revisited. Proceedings of the 2018 International Conference on Management of Data. 2018, pp. 1525–1539.Zhuoyue Zhao, Robert Christensen, Feifei Li, Xiao Hu and Ke Yi. Random sampling over joins revisited. Proceedings of the 2018 International Conference on Management of Data. 2018, pp. 1525–1539.Walter Cai, Magdalena Balazinska and Dan Suciu. Pessimistic cardinality estimation: Tighter upper bounds for intermediate join cardinalities. Proceedings of the 2019 International Conference on Management of Data. 2019, pp. 18–35.Walter Cai, Magdalena Balazinska and Dan Suciu. Pessimistic cardinality estimation: Tighter upper bounds for intermediate join cardinalities. Proceedings of the 2019 International Conference on Management of Data. 2019, pp. 18–35.Pedro Lopes, Craig Guyer and Milener Gene. Sql docs: cardinality estimation (SQL Server). 2019.Pedro Lopes, Craig Guyer and Milener Gene. Sql docs: cardinality estimation (SQL Server). 2019.Lucas Woltmann, Claudio Hartmann, Maik Thiele, Dirk Habich and Wolfgang Lehner. Cardinality estimation with local deep learning models. Proceedings of the second international workshop on exploiting artificial intelligence techniques for data management. 2019, pp. 1–8.Lucas Woltmann, Claudio Hartmann, Maik Thiele, Dirk Habich and Wolfgang Lehner. Cardinality estimation with local deep learning models. Proceedings of the second international workshop on exploiting artificial intelligence techniques for data management. 2019, pp. 1–8.Zongheng Yang, Eric Liang, Amog Kamsetty, Chenggang Wu, Yan Duan, Xi Chen, Pieter Abbeel, Joseph M Hellerstein, Sanjay Krishnan and Ion Stoica. Deep Unsupervised Cardinality Estimation. Proceedings of the VLDB Endowment 13.3 (2019).Zongheng Yang, Eric Liang, Amog Kamsetty, Chenggang Wu, Yan Duan, Xi Chen, Pieter Abbeel, Joseph M Hellerstein, Sanjay Krishnan and Ion Stoica. Deep Unsupervised Cardinality Estimation. Proceedings of the VLDB Endowment 13.3 (2019).MariaDB Server Documentation. Statistics for optimizing queries: InnoDB persistent statistics. 2020.MariaDB Server Documentation. Statistics for optimizing queries: InnoDB persistent statistics. 2020.Postgresql Documentation. 12. 2020. Chapter 70.1. Row Estimation Examples. 2020.Postgresql Documentation. 12. 2020. Chapter 70.1. Row Estimation Examples. 2020.Zongheng Yang, Amog Kamsetty, Sifei Luan, Eric Liang, Yan Duan, Xi Chen and Ion Stoica. NeuroCard: one cardinality estimator for all tables. Proceedings of the VLDB Endowment 14.1 (2020), pp. 61–73.Zongheng Yang, Amog Kamsetty, Sifei Luan, Eric Liang, Yan Duan, Xi Chen and Ion Stoica. NeuroCard: one cardinality estimator for all tables. Proceedings of the VLDB Endowment 14.1 (2020), pp. 61–73.Yuxing Han, Ziniu Wu, Peizhi Wu, Rong Zhu, Jingyi Yang, Liang Wei Tan, Kai Zeng, Gao Cong, Yanzhao Qin, Andreas Pfadler et al. Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation. arXiv preprint arXiv:2109.05877 (2021).Yuxing Han, Ziniu Wu, Peizhi Wu, Rong Zhu, Jingyi Yang, Liang Wei Tan, Kai Zeng, Gao Cong, Yanzhao Qin, Andreas Pfadler et al. Cardinality Estimation in DBMS: A Comprehensive Benchmark Evaluation. arXiv preprint arXiv:2109.05877 (2021).Ryan Marcus, Parimarjan Negi, Hongzi Mao, Chi Zhang, Mohammad Alizadeh, Tim Kraska, Olga Papaemmanouil and Nesime Tatbul23. Neo: A Learned Query Optimizer. Proceedings of the VLDB Endowment 12.11 (2021).Ryan Marcus, Parimarjan Negi, Hongzi Mao, Chi Zhang, Mohammad Alizadeh, Tim Kraska, Olga Papaemmanouil and Nesime Tatbul23. Neo: A Learned Query Optimizer. Proceedings of the VLDB Endowment 12.11 (2021).Immanuel Trummer, Junxiong Wang, Ziyun Wei, Deepak Maram, Samuel Moseley, Saehan Jo, Joseph Antonakakis and Ankush Rayabhari. Skinnerdb: Regret-bounded query evaluation via reinforcement learning. ACM Transactions on Database Systems (TODS) 46.3 (2021), pp. 1– 45.Immanuel Trummer, Junxiong Wang, Ziyun Wei, Deepak Maram, Samuel Moseley, Saehan Jo, Joseph Antonakakis and Ankush Rayabhari. Skinnerdb: Regret-bounded query evaluation via reinforcement learning. ACM Transactions on Database Systems (TODS) 46.3 (2021), pp. 1– 45.Rong Zhu, Ziniu Wu, Yuxing Han, Kai Zeng, Andreas Pfadler, Zhengping Qian, Jingren Zhou and Bin Cui. FLAT: fast, lightweight and accurate method for cardinality estimation. Proceedings of the VLDB Endowment 14.9 (2021), pp. 1489–1502.Rong Zhu, Ziniu Wu, Yuxing Han, Kai Zeng, Andreas Pfadler, Zhengping Qian, Jingren Zhou and Bin Cui. FLAT: fast, lightweight and accurate method for cardinality estimation. Proceedings of the VLDB Endowment 14.9 (2021), pp. 1489–1502.

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