Database Internals Meetup #11 (офлайн + онлайн): Поздняя материализация в PosDB и неточная оптимизация порядка джойнов с помощью деревьев связанности

Трансляция:

• YouTube: 
• VK:

Приглашаем вас на одиннадцатый митап сообщества Database Internals. 

Мероприятие пройдет офлайн в офисе Яндекс по адресу г. Москва, ул. Льва Толстого д. 16, подъезд 4, 1-ый этаж, конференц-зал "Мулин Руж".

Участвующим онлайн будет доступна трансляция на VK Video, YouTube и чат.

Мероприятие бесплатное. Регистрация обязательна. При очном участии обязательно наличие паспорта. Количество мест ограничено.

Трансляция мероприятия организована нашими друзьями из компании Яндекс.

Программа

19:00 - 20:00 Поздняя материализация в PosDB. Георгий Чернышев, СПбГУ

20:00 - 20:10 Перерыв

20:10 - 21:10 Неточная оптимизация порядка джойнов с помощью связующих деревьев. Есдаулет Изенов, разработчик YDB

Доклады

Поздняя материализация в PosDB

Георгий Чернышев, СПбГУ

PosDB (Positional Database) — исследовательская распределенная колоночная аналитическая СУБД с поддержкой SQL.  В отличие от большинства существующих колоночных систем, она ориентирована на максимально широкое использование позиций при выполнении запросов. Способность исполнителя запросов оперировать позициями открывает широкие возможности для применения различных оптимизаций, а также приносит ряд других преимуществ.

Понятие «поздняя материализация» объединяет класс оптимизаций, при которых исполнитель как можно дольше работает с позициями и переходит к строковому представлению данных как можно позднее в плане выполнения запроса. В ряде случаев это позволяет не только экономить на промежуточном представлении данных, но и создавать высокоэффективные реализации операторов плана запроса. 

Проект PosDB развивается с 2016 года и был изначально нацелен на исследование и разработку подобных оптимизаций. В докладе я освещу основные идеи и архитектуру системы, ограничения подхода, а потом пройдусь по основным опубликованным результатам, в том числе представлю примеры таких оптимизаций. Наконец, я расскажу над чем работаем сейчас и обсудим дальнейшие планы.

Интерактивное демо PosDB и публикации по проекту доступны по адресу: https://pos-db.com/

Неточная оптимизация порядка джойнов с помощью связующих деревьев.

Есдаулет Изенов, разработчик YDB

В наше время все чаще на практике появляются запросы с очень большим количеством операций джойнов. Традиционный подход к оптимизации порядка и алгоритмов джойнов фокусируется на небольших запросах, где используется полный перебор возможных деревьев. Как ещё можно перебирать планы запросов с большим количеством джойнов? Когда полный перебор трудно масштабировать, жадный перебор зачастую не позволяет найти оптимальные или даже качественные субоптимальные планы. В этом выступлении мы обсудим, как классические, low-cost spanning tree (связующее дерево) алгоритмы могут стать практичной компромиссной стратегией между подходами полного и жадного перебора. Мы рассмотрим существующие решения, использующие формулировку задачи через spanning trees для упорядочивания джойнов, и покажем, как этот подход можно расширить для более эффективного масштабирования при работе с запросами содержащими большое количество джойнов. Сравним наш подход с жадными алгоритмами и более продвинутыми эвристическими алгоритмами, такими как IKKBZ и линеаризацией.

Полезные ссылки

• Telegram-чат сообщества: https://t.me/databaseinternalschat
• Анонсы предстоящий событий: https://databaseinternals.timepad.ru/events/