В этом году, волею судеб, я был научным руководителем двух студентов из ИТМО. Это было мегаинтересное приключение длиной почти в год, которое закончилось две недели назад - ребята получили два заслуженных отла и степень магистра!

Принёс небольшой отчёт о проделанной работе и каплю рефлексии

Что делали

Формальные названия научных работ запарные, но по сути задача была разработать прототип вычислительного узла join с учётом SOTA-решений и граблей, на которые мы в YDB успели понаступать.

Что сделали

Скрафили два алгоритма: HashJoin - побыстрее и GraceHashJoin - помедленнее, но зато с партиционированием и заделом на спиллинг. А также бонусом 3 (три!) хэштаблицы под разные сценарии использования и алгоритм, гибко адаптирующий джоин под входные данные.

Синтетические бенчи показали, что новый join работает в несколько раз быстрее, чем текущие реализации. См. BlockGraceJoin::* на графике.

Да, на реальных данных результаты могут отличаться - встроить код в пайплайн достаточно сложно, а без этого даже TPC-H/DS прогнать не получится, не говоря уже о настоящих запросах.

Но тем не менее! Офигенные результаты для прототипа. Испытываю какую-то невероятную гордость за ребят.

For nerds

Нанотехнологии имплементации
- поддержано блочное (Apache Arrow) представление данных
- фокус сделан на типовые аналитические джоины - в основном фильтрующие, с явным разделением на build/probe стороны
- разработано компактное внутреннее представление (сериализация) и конвертеры, использующие SIMD-инструкции
- гистограммы, которые по первым N мб данных оценивают кардинальность и выбирают стратегию хранения
- используются prefetch-инструкции (если честно, я всегда считал, что их придумали маркетологи, чтобы продавать книжки по проге, но тут разница видна - буду разбираться ещё)
- ну и блум-фильтры офк

Про защиту

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

Ещё, кстати, удивительно хорошо со стороны было видно, как важно уметь показать себя в выгодном свете.
Задает комиссия вопрос:
"Ну вот эти все числа и алгоритмы - это хорошо. А что вы конкретно сделали?"
И студент теряется, начинает что-то говорить про какие-то оптимизации, какие-то копирования. Вместо того чтобы подойти и уверенно сказать: "запрограммировал несколько хеш-таблиц и на их основе построили join, который работает в несколько раз быстрее текущих имплементаций".

При этом вмешиваться мне не разрешили, пришлось выкручиваться во время финального слова и дополнительно акцентировать внимание на том, что было сделано.

Если бы ребята за такую огромную проделанную работу получили бы не отлы - это был бы мегапровал (в первую очередь меня как научника)

Про студентов вообще

Вообще, в этом году я как-то много работал со студентами: в вышке на АКОСе, был стажёр, и вот теперь - магистры.

Удивляюсь, какие студенты нынче жёсткие. Схватывают на лету, замотивированные, да еще и знают кучу всего. Как будто с детства под подушкой прячут TLPI (да я буду везде его упоминать). Пообщаешься немного и сразу хочется тоже что-то крутое замутить!

Что дальше

В планах на полгода у нас разработка полноценного нового production-ready джоина. Мне предстоит полноценно продумать его дизайн, защитить его на внутреннем design review и как-то запрограммировать.

Пока трудно сказать, будут ли использоваться какие-то наработки студентов - всё-таки это прототип, и в нём учитываются не все требования, которые у нас есть. Но если что-то понадобится, то буду пинать ребят, чтобы приносили PRы, и код не пропал.

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