Анализ одного алгоритма операции Join
Аннотация
Реляционный подход к организации баз данных за время своего существования пе-режил достаточно коллизий и неоднократно подвергался серьезной, и часто, необоснованной критике. Одним из положений критики было возражение против операции Join, которая считалась крайне неэффективной. Однако эта операция существовала в самых ранних системах обработки данных. В ранних публикациях она относится к классу слияния нестрого упорядоченных информационных массивов. В дальнейшем она была названа операцией слияния нестрого упорядоченных файлов. В последних работах в области машинного обучения стало активно развиваться направление, связанное с реляционными базами данных. Современные аналитические системы в производственной, финансовой, банковской, медицинской и многих других сферах базируются на больших объемах, структурированных данных, которые хранятся в, как правило, реляционных базах данных. Важное направление ускорения реализации запросов в таких базах данных заключается в использовании методов параллельной обработки данных. А так как операция Join – самая сложная из всех остальных операций, составляющих запросы, вопросам выбора для ее реализации наиболее эффективных алгоритмов, которые, в свою очередь, могут быть просто и эффективно. В статье предложен алгебраический метод формализации операции Join. На основе этого метода предложен алгоритм ее реализации с использованием специфической структуры очереди, которая называется "черпак". Приведены результаты экспериментального анализа алгоритма, подтвердившие его преимущество перед алгоритмом, который реализован в использованной системе управления базами данных Microsoft SQL Server. Приведены методы параллельной реализации предложенного алгоритма. Для этой цели использован традиционный поточный подход и подход, основанный на на архитектуре вычислительной системы с ассоциативным распределением ресурсов.
Литература
2. Chaudhuri S., Motwani R., Narasayya V. On random sampling over joins. In: Proceedings of the 1999 ACM SIGMOD international conference on Management of data (SIGMOD '99). New York, NY, USA: Association for Computing Machinery; 1999. p. 263-274. https://doi.org/10.1145/304182.304206
3. Zhao Z., Christensen R., Li F., Hu X., Yi K. Random Sampling over Joins Revisited. In: Proceedings of the 2018 International Conference on Management of Data (SIGMOD '18). New York, NY, USA: Association for Computing Machinery; 2018. p. 1525-1539. https://doi.org/10.1145/3183713.3183739
4. Deng S., Lu S., Tao Y. On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms. In: Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS '23). New York, NY, USA: Association for Computing Machinery; 2023. p. 99-111. https://doi.org/10.1145/3584372.3588666
5. Huang D., Yoon D.Y., Pettie S., Mozafari B. Joins on samples: a theoretical guide for practitioners. Proceedings of the VLDB Endowment. 2019;13(4):547-560. https://doi.org/10.14778/3372716.3372726
6. Chen Y., Yi K. Random Sampling and Size Estimation Over Cyclic Joins. In: 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs). 2020;155:7:1-7:18. https://doi.org/10.4230/LIPIcs.ICDT.2020.7
7. Vengerov D., Menck A.C., Zait M., Chakkappen S.P. Join size estimation subject to filter conditions. Proceedings of the VLDB Endowment. 2015;8(12):1530-1541. https://doi.org/10.14778/2824032.2824051
8. Timofeeva N.E., Dmitrieva K.A. Universal algorithm of processing of requests with use of parallel technology. Nauchno-tekhnicheskiy vestnik Bryanskogo gosudarstvennogo universiteta = Scientific and Technical Journal of Bryansk State University. 2018;(2):211-217. (In Russ., abstract in Eng.) https://doi.org/10.22281/2413-9920-2018-04-02-211-217
9. Nugroho D.P.A., et al. Benchmarking Stream Join Algorithms on GPUs: A Framework and its Application to the State-of-the-art. In: Proceedings of the 27th International Conference on Extending Database Technology (EDBT). 2024. p. 188-200. https://doi.org/10.48786/edbt.2024.17
10. Ji H., et al. BS-Join: A novel and efficient mixed batch-stream join method for spatiotemporal data manage-ment in Flink. Future Generation Computer Systems. 2023;141:67-80. https://doi.org/10.1016/j.future.2022.11.016
11. Wang J., Trummer I., Kara A., Olteanu D. ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning. Proceedings of the VLDB Endowment. 2012;16(11):2805-2817. https://doi.org/10.14778/3611479.3611489
12. Munerman V.I., Munerman D.V. The parallel implementation of the files processing operations. Modern Information Technologies and IT-Education. 2016;12(2):84-90. (In Russ., abstract in Eng.) EDN: XSATGX
13. Munerman V.I. Implementation of big data processing on symmetric multiprocessing systems. Highly Available Systems.2013;9(2):036-039. (In Russ., abstract in Eng.) EDN: QOVNNR
14. Levin N.A., Munerman V.I. Logically sequential data access method. Highly Available Systems. 2011;7(4):65-67. (In Russ., abstract in Eng.) EDN: PEZEGP
15. Li M., Huang L., Xu G., Biao K. A parallel particle swarm optimization framework based on a fork-join thread pool using a work-stealing mechanism. Applied Soft Computing. 2023;145(C):110537. https://doi.org/10.1016/j.asoc.2023.110537
16. Hu X., Yi K. Massively Parallel Join Algorithms. ACM SIGMOD Record. 2020;49(3):6-17. https://doi.org/10.1145/3444831.3444833
17. Mancini R., Karthik S., Chandra B., Mageirakos V., Ailamaki A. Efficient Massively Parallel Join Optimization for Large Queries. In: Proceedings of the 2022 International Conference on Management of Data (SIGMOD '22). New York, NY, USA: Association for Computing Machinery; 2022. p. 122-135. https://doi.org/10.1145/3514221.3517871
18. Lang H., Leis V., Albutiu M.C., Neumann T., Kemper A. Massively Parallel NUMA-Aware Hash Joins. In: Jagatheesan A., Levandoski J., Neumann T., Pavlo A. (eds.) In: Memory Data Management and Analysis. IMDM IMDM 2013 2014. Lecture Notes in Computer Science. Vol. 8921. Cham: Springer; 2015. p. 3-14. https://doi.org/10.1007/978-3-319-13960-9_1
19. Barthels C., Müller I., Schneider T., Alonso G., Hoefler T. Distributed join algorithms on thousands of cores. Proceedings of the VLDB Endowment. 2017;10(5):517-528. https://doi.org/10.14778/3055540.3055545
20. Munerman V.I. Construction of hardware-software complexes architecture to improve massively data processing. Highly Available Systems.2014;10(4):3-16. (In Russ., abstract in Eng.) EDN: TFQJWX
21. Munerman V.I., Munerman D.V. Odin metod realizacii simmetrichnogo gorizontal'nogo raspredelenija dannyh [One method for implementing symmetric horizontal data distribution]. Sistemy komp'yuternoj matem-atiki i ih prilozheniya = Computer Mathematics Systems and Their Applications. 2017;(18):97-100. (In Russ., abstract in Eng.) EDN: ZQTUZT
22. Munerman V.I., Munerman D.V. Parallel implementation of symmetric horizontal distributionof data on the network technologies basis. Modern Information Technologies and IT-Education. 2017;13(3):38-43. (In Russ., abstract in Eng.) https://doi.org/10.25559/SITITO.2017.3.521
23. Munerman V.I. The implementation of parallel data processing in cloud systems. Modern Information Technologies and IT-Education. 2017;13(2):57-63. (In Russ., abstract in Eng.) https://doi.org/10.25559/SITITO.2017.2.223
24. Munerman V., Munerman D., Samoilova T. The Heuristic Algorithm For Symmetric Horizontal Data Distribution. In: 2021 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus). St. Petersburg, Moscow, Russia: IEEE Press; 2021. p. 2161-2165. https://doi.org/10.1109/ElConRus51938.2021.9396510
25. Provotorova A. Parallel data base system simulating on the VSARR computing system. Systems and Means of Informatics. 2006;16(1):418-430. (In Russ., abstract in Eng.) EDN: KZUWMZ
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
