02. История создания оптимизаторов запросов. History of Query Optimizers ft. IBM System R
В лекции рассказывают об истории развития оптимизаторов запросов, начиная с 1970‑х годов, и подробно разбирают подходы, заложенные в системе IBM System R. Плэйлист: https://rutube.ru/plst/1911137 16 янв. 2025 г. CARNEGIE MELLON UNIVERSITY Andy Pavlo (https://www.cs.cmu.edu/~pavlo/) Slides: https://15799.courses.cs.cmu.edu/spring2025/slides/02-systemr.pdf 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 Таймкоды: 00:00:03 — Введение и планы на занятие 00:01:03 — Логистика курса 00:01:49 — Предыстория развития баз данных 00:02:43 — Первые системы баз данных (1960‑е) 00:03:42 — Чарльз Бахман и движение COBOL 00:04:42 — Особенности работы с БД в прошлом 00:05:42 — Проблемы жёстко запрограммированных планов 00:06:37 — Преимущества реляционной модели 00:07:32 — История языков запросов 00:08:15 — Ранние реализации реляционной модели 00:10:05 — Подходы к оптимизации запросов Эвристики (Ingress, Oracle до 1990‑х). Поиск на основе затрат (System R) — основа современных систем. 00:11:55 — Принципы эвристического оптимизатора 00:13:50 — Правила эквивалентности в реляционной алгебре Логическая корректность преобразований. Гарантия одинакового результата после применения правил. 00:15:17 — Применение правил преобразования Перемещение предикатов в операторах выбора или сканирования отношений. Разбиение и перемещение предикатов по плану запроса. Упрощение выражений и предикатов. 00:16:14 — Оптимизация вычислений и функций 00:17:11 — Свойства коммутативности и ассоциативности 00:18:07 — Проблема выбора порядка соединений 00:22:07 — Определение порядка соединения без статистики 00:22:59 — Обработка запросов с ORDER BY Разбиение на подзапросы с одним отношением. Запись результатов первого запроса во временную таблицу. Рекурсивное использование временной таблицы в последующих запросах. 00:25:34 — Подход System R и других систем Рекурсивный подход для оптимизации вложенных запросов. Остановка процесса оптимизации, выполнение внутреннего запроса, ввод результата обратно. Ограничения подхода из‑за ограничений того времени. 00:26:49 — Работа операторов if‑then‑else в оптимизаторе Поиск шаблонов в плане запроса через операторы if‑then‑else. Вызов подпрограммы для логического или физического преобразования при распознавании шаблона. Быстрота работы для простых запросов. 00:27:47 — Проблемы сложных систем и «спагетти‑кода» Простота запуска систем с простыми методами оптимизации. Проблема «спагетти‑кода» из‑за множества условий if‑then‑else. Порядок преобразований не всегда приводит к наилучшему результату. 00:28:41 — Оптимизатор запросов Oracle и маркетинг Порядок объединения соответствует порядку в SQL‑запросе (изначально). Маркетинговая идея синтаксического оптимизатора (Ларри Эллисон). Переход к системному подходу к оптимизации в 1990‑х. 00:31:51 — Подход System R к оптимизации Алгоритм динамического программирования и поиск на основе затрат. Преобразование логического плана в физический. Начальный этап с if‑then‑else (как в Ingress). Участие около 15 человек в проекте System R. 00:34:48 — Преобразование логических операторов в физические 00:38:29 — Определение стоимости операций Функция затрат: стоимость = количество выборок страниц × взвешенный коэффициент RSI‑вызовов. Вес коэффициента зависит от аппаратного обеспечения. 00:42:02 — Коэффициент избирательности и статистика данных Формулы для расчёта ожидаемого количества кортежей на основе статистики. Обновление статистики при массовой загрузке или запуске VACUUM/ANALYZE в Postgres. 00:44:58 — Демонстрация работы Postgres Выбор между использованием индекса и последовательным сканированием. 00:47:09 — Особенности оптимизаторов запросов Проблемы Postgres с запросами, усложняющими идентификацию индексов. 00:49:41 — Сравнение Postgres и SQL Server Частичная оценка аргументов поиска в SQL Server. Просмотр плана запроса: EXPLAIN в Postgres vs специальный режим в SQL Server. 00:53:08 — Выбор метода доступа Индексное сканирование vs последовательное сканирование. 00:54:01 — Упорядочивание соединений Трёхэтапный подход: выбор метода доступа, рассмотрение комбинаций, итеративное создание плана. 00:56:58 — Динамический подход к исследованию 00:57:56 — Алгоритмы объединения 00:59:20 — Обработка предложения ORDER BY 01:00:17 — Подходы «снизу вверх» и «сверху вниз» 01:03:24 — Работа со вложенными запросами 01:05:19 — Преимущества эвристического поиска Нахождение хорошего плана за разумное время без тщательного поиска. Генерация плана для запроса с восемью таблицами за секунды. Риск «спагетти‑кода» при реализации в процедурном коде. 01:07:12 — Проблемы упрощающих допущений
Название:
02. История создания оптимизаторов запросов. History of Query Optimizers ft. IBM System R
Категория:
Технологии и интернет