10.Алгоритмы многосторонних соединений таблиц. Multi-Way Join Algorithms
Lecture #10: Multi-Way Join Algorithms Краткое содержание: Алгоритмы многосторонних соединений таблиц и теория оптимальных по худшему случаю соединений (Worst-Case Optimal Joins, WCOJ): - Ограничения классических бинарных соединений (Pairwise Joins): - Традиционные деревья планов (левосторонние, кустообразные) соединяют таблицы парами, что при циклических графах запросов (напр. поиск треугольников в графах) порождает колоссальные промежуточные результаты, многократно превышающие размер финального ответа. - Граница АГМ (Atserias-Grohe-Marx Bound): - Математическое определение максимального размера результата соединения произвольного реляционного запроса на основе покрытий дробной ширины графа. - Алгоритм Leapfrog Triejoin: - Итерация по атрибутам с использованием префиксных деревьев (Tries) и алгоритма прыгающей лягушки (Leapfrog) над отсортированными списками значений. - Гарантия оптимальности по худшему случаю без создания огромных промежуточных таблиц. - Практические гибридные реализации: - Интеграция WCOJ в реляционные движки (EmptyHeaded, LogicBlox, Umbra): динамический выбор между традиционными хеш-соединениями и WCOJ в зависимости от селективности и структуры графа запроса. Дата лекции: 26 February 2024 Слайды: https://15721.courses.cs.cmu.edu/spring2024/slides/10-multiwayjoins.pdf Конспект: https://15721.courses.cs.cmu.edu/spring2024/notes/10-multiwayjoins.pdf Статьи: - https://15721.courses.cs.cmu.edu/spring2024/papers/10-multiwayjoins/p1891-freitag.pdf - https://15721.courses.cs.cmu.edu/spring2024/papers/10-multiwayjoins/ngo-sigmodrec13.pdf - https://15721.courses.cs.cmu.edu/spring2024/papers/10-multiwayjoins/aberger-icde2018.pdf Rutube плейлист: https://rutube.ru/plst/1923067 Автор: Andy Pavlo (https://www.cs.cmu.edu/~pavlo/) Курс: CMU Advanced Database Systems (15-721 / Spring 2024) https://15721.courses.cs.cmu.edu/spring2024/ YouTube_Playlist: https://youtube.com/playlist?list=PLSE8ODhjZXjYa_zX-KeMJui7pcN1rIaIJ&si=_JzW6pE0nsACv-Zo YouTube: https://www.youtube.com/watch?v=1aHT3KitTYo
Название:
10.Алгоритмы многосторонних соединений таблиц. Multi-Way Join Algorithms
Категория:
Технологии и интернет