ОЦЕНКА ПЛАНОВ ВЫПОЛНЕНИЯ SQL ЗАПРОСОВ ДЛЯ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ
EDN: NYDIOB
Аннотация
Существующие подходы к проблеме поиска оптимального плана выполнения SQL запроса далеки от идеала. Учитывая многопараметрический характер транспортных задач, минимизация времени выполнения запроса может иметь решающее значение. Функция стоимости, которая каждому плану ставит в соответствие время его выполнения должна удовлетворять следующим требованиям: 1) отношение порядка стоимостей должно как можно больше совпадать с отношением порядка времени, 2) стоимость любого плана не может быть больше стоимости другого плана, полученного путём добавления операций соединений. В работе рассматривается задача оптимизации планов выполнения SQL запросов с помощью методов машинного обучения. В работе подробно описан традиционный подход к решению данной задачи, рассмотрены его недостатки. Также приведён анализ существующих методов машинного обучения, которые призваны устранить ряд недостатков традиционного оптимизатора. Рассмотрены их преимущества и недостатки.
Об авторах
С. К. Дулин
АО «НИИАС»; ИПИ ФИЦ ИУ РАН
Россия
Россия
д.т.н., профессор, главный научный сотрудник
А. Б. Рябцев
Московский физико-технический институт (МФТИ)
Россия
Россия
аспирант
Список литературы
1. 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.
2. 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.
3. 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.
4. 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.
5. Abraham Silberschatz, Henry F Korth and Shashank Sudarshan. Database system concepts. Vol. 5. McGraw-Hill New York, 2002.
6. 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.
7. 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.
8. Gavin Powell. Beginning database design. John Wiley & Sons, 2006.
9. Hector Garcia-Molina. Database systems: the complete book. Pearson Education India, 2008.
10. 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.
11. 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.
12. Hazar Harmouch and Felix Naumann. Cardinality estimation: An experimental survey. Proceedings of the VLDB Endowment 11.4 (2017), pp. 499–512.
13. Oleg Ivanov and S Bartunov. Adaptive query optimization in PostgreSQL. PGCon 2017 Conference, Ottawa, Canada. 2017.
14. 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.
15. Viktor Leis, Bernhard Radke, Andrey Gubichev, Alfons Kemper and Thomas Neumann. Cardinality Estimation Done Right: Index-Based Join Sampling. Cidr. 2017.
16. 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).
17. 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.
18. 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.
19. 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.
20. Pedro Lopes, Craig Guyer and Milener Gene. Sql docs: cardinality estimation (SQL Server). 2019.
21. 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.
22. 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).
23. MariaDB Server Documentation. Statistics for optimizing queries: InnoDB persistent statistics. 2020.
24. Postgresql Documentation. 12. 2020. Chapter 70.1. Row Estimation Examples. 2020.
25. 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.
26. 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).
27. 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).
28. 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.
29. 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.
Рецензия
Для цитирования:
Дулин С.К., Рябцев А.Б. ОЦЕНКА ПЛАНОВ ВЫПОЛНЕНИЯ SQL ЗАПРОСОВ ДЛЯ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ. Интеллектуальный транспорт. 2023;(1(25)):38-43. EDN: NYDIOB
For citation:
Dulin S.K., Ryabtsev A.V. EVALUATION OF EXECUTION PLANS OF SQL QUERY FOR SOLVING TRANSPORT PROBLEMS. Intelligent transport. 2023;(1(25)):38-43. (In Russ.) EDN: NYDIOB
Просмотров:
24
JATS XML
Послать статью по эл. почте 