07.Восходящие алгоритмы ранжирования соединений Join Ordering: Bottom-Up

12+
12+

1 просмотр

9 часов назад

ПожаловатьсяНарушение авторских прав
12+
12+

1 просмотр

9 часов назад

ПожаловатьсяНарушение авторских прав
12+
12+

1 просмотр

9 часов назад

Lecture #07: Join Ordering: Bottom-Up Краткое содержание: Восходящие алгоритмы перебора соединений (Bottom-Up Join Ordering) и современные подходы немецкой школы: - Комбинаторная сложность задачи: - Количество форм бинарных деревьев определяется числами Каталана, перестановки листьев растут факториально; задача NP-полная в общем виде. - Алгоритмы динамического программирования (DP): - DPsize: перебор по количеству отношений в подплане. - DPsub: перебор по битовым маскам подмножеств таблиц. - DPhyp (Moerkotte & Neumann): динамическое программирование на гиперграфах, генерирующее строго связные непересекающиеся пары подграфов (csg-cmp) без рассмотрения декартовых произведений. - Адаптивная оптимизация гигантских запросов (Томас Нойман, 2018): - Точный перебор DPhyp для небольшого числа таблиц. - Переключение на быстрые жадные эвристики (IKKBZ, Greedy Operator Ordering / GOO) и генетические алгоритмы при росте числа таблиц до десятков и сотен. - Современный прогресс (DPconv, 2025): - Сверхполиномиальное ускорение перебора на базе сверток подмножеств. Дата лекции: 05 February 2025 Слайды: https://15799.courses.cs.cmu.edu/spring2025/slides/07-joins1.pdf Конспект: https://15799.courses.cs.cmu.edu/spring2025/notes/07-joins1.pdf Статьи: - https://15799.courses.cs.cmu.edu/spring2025/papers/07-joins1/neumann-sigmod2018.pdf - https://15799.courses.cs.cmu.edu/spring2025/papers/07-joins1/p539-moerkotte.pdf - https://15799.courses.cs.cmu.edu/spring2025/papers/07-joins1/stoian-sigmod2025.pdf YouTube: https://www.youtube.com/watch?v=CcUVvnYv7Hg ------------------------------------------------------------------- Плэйлист: https://rutube.ru/plst/1911137 15-799 Special Topics in Database: Query Optimization (Spring 2025) Carnegie Mellon University https://15799.courses.cs.cmu.edu/spring2025/ YouTube: https://www.youtube.com/@CMUDatabaseGroup YouTube Playlist: https://youtube.com/playlist?list=PLSE8ODhjZXjYCZfIbmEWH7f6MnYqyPwCE&si=2YncIrR6SGsjwwGm

Название:

07.Восходящие алгоритмы ранжирования соединений Join Ordering: Bottom-Up