09.Алгоритмы хэш-соединений. Hash Join Algorithms

12+
12+

1 просмотр

8 часов назад

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

1 просмотр

8 часов назад

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

1 просмотр

8 часов назад

Lecture #09: Hash Join Algorithms Краткое содержание: Высокопроизводительные алгоритмы хеш-соединений (Hash Joins) в оперативной памяти на многоядерных архитектурах: - Базовые фазы хеш-соединения: - Build Phase: построение хеш-таблицы по меньшей (внутренней) таблице. - Probe Phase: последовательное чтение внешней таблицы, вычисление хеша и сопоставление ключей. - Дилемма секционирования: Partitioned vs. Non-Partitioned Joins: - Radix Hash Join: предварительное многопроходное разбиение данных по бакетам, помещающимся в кэш L1/L2, для предотвращения промахов TLB. - Non-Partitioned Hash Join: единая разделяемая хеш-таблица без фазы разбиения данных, полагающаяся на быстрый произвольный доступ к памяти. - Внутреннее устройство хеш-таблиц: - Chained Hashing (связные списки) против Open Addressing (Linear Probing, Robin Hood Hashing, Cuckoo Hashing). - Минимизация ветвлений и поддержка параллельной бесконфликтной записи (lock-free / atomic primitives). - Аппаратная адаптация и векторный зондаж: - Применение SIMD-инструкций для параллельного сравнения нескольких ключей в одном бакете и программная предвыборка данных (software prefetching) для скрытия задержек памяти. Дата лекции: 21 February 2024 Слайды: https://15721.courses.cs.cmu.edu/spring2024/slides/09-hashjoins.pdf Конспект: https://15721.courses.cs.cmu.edu/spring2024/notes/09-hashjoins.pdf Статьи: - https://15721.courses.cs.cmu.edu/spring2024/papers/09-hashjoins/schuh-sigmod2016.pdf - https://15721.courses.cs.cmu.edu/spring2024/papers/09-hashjoins/richter-vldb2015.pdf - https://15721.courses.cs.cmu.edu/spring2024/papers/09-hashjoins/p37-blanas.pdf - https://15721.courses.cs.cmu.edu/spring2024/papers/09-hashjoins/balkesen-icde2013.pdf - https://15721.courses.cs.cmu.edu/spring2024/papers/09-hashjoins/bandle-sigmod21.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=S40K8iGa8Ek

Название:

09.Алгоритмы хэш-соединений. Hash Join Algorithms