Как Яндекс разработал алгоритм для стоимостного оптимизатора в YDB

Для поддержки эффективных аналитических запросов в СУБД Яндекса реализован механизм стоимостной оптимизации — алгоритм выбора оптимального плана выполнения запроса. При этом такая задача является NP-трудной — для её решения необходимо перебрать все варианты выполнения запроса, и время работы системы увеличивается экспоненциально. На вебинаре расскажем, как Яндекс решил эту задачу в своей универсальной СУБД — YDB. На вебинаре рассказали: как был имплементирован стоимостной оптимизатор и какие теоретические наработки использует Яндекс, чтобы добиться поддержки большого количества запросов в своей СУБД; как стоимостной оптимизатор помогает обеспечить производительность в СУБД; как динамическое программирование позволяет перебирать до 150 JOIN-операций за 1 секунду. Вебинар полезен тем, кто интересуется алгоритмами оптимизации, разработкой баз данных, динамическим программированием, — архитекторами и инженерам баз данных, разработчикам прикладного ПО и специалистам по системной интеграции. 00:00 Приветствие 01:40 О системе YDB 02:46 Компоненты аналитической системы 04:49 Зачем нужен стоимостный оптимизатор 07:21 Разработка оптимизатора 08:36 Компоненты оптимизатора 09:47 Подходы к построению оптимизаторов 12:34 Динамическое программирование 14:50 Граф соединения запросов 16:49 Пространство поиска 18:42 Что получилось на данный момент 19:43 Hash Join 20:23 Merge Join 20:52 Сравнение Join 22:08 Варианты исправления неоптимальности 23:49 Задача на оценку совместимости списков атрибутов 27:28 Решение задачи на примере 30:11 Оценка кардинальности 32:03 Развитие методов оценки кардинальности 34:50 Оценочная функция 36:06 Сбор статистики 36:55 Оценка качества оптимизатора 41:14 Сравнение с конкурентами 44:49 Распределение времени при разработке 45:25 Что пока не покрыто 46:10 Заключение и планы на будущее 47:57 Ответы на вопросы