Merge Join исправил, спасибо.
Про Index Join мне уже напомнили в комментах выше, но добавлять его в статью уже не хочется. Тем более, его код будет выглядеть почти как у HashJoin, только без построения хеша.
Так же я не написал про джойн по не-равенству, алгоритм sort join, anti join и еще много всяких редких штук.
Эта статья не про собеседования, а про операцию JOIN.
Про собеседования мысль вот:
Что касается того, кого я ищу, то на самом деле, мне плевать на внутренности РСУБД. Я просто пытаюсь понять, насколько глубоко человек изучил те технологии, с которыми он работал. Т.е. если у вас в проекте было много low-level NIO, а с базой вы почти не работали — я не буду ожидать от вас знания Merge Join, но захочу услышать про селекторы и грин-треды.
В статье нет ничего про подход к собеседованиям. Эта статья — про операцию JOIN и веру в магию.
Как я писал в комментах выше:
Что касается того, кого я ищу, то на самом деле, мне плевать на внутренности РСУБД. Я просто пытаюсь понять, насколько глубоко человек изучил те технологии, с которыми он работал. Т.е. если у вас в проекте было много low-level NIO, а с базой вы почти не работали — я не буду ожидать от вас знания Merge Join, но захочу услышать про селекторы и грин-треды.
Меня Join'ы интересуют больше в разрезе офлайн аналитики, различных SQL поверх Hadoop. Там криво написанное условие превращается в лишние каскады map-reduce'ов и множественные OOM'ы.
Я могу на собеседовании вести достаточно детальный разговор про устройство трех баз из вашего списка.
Базы данных — достаточно узкая область, чтобы ее можно было изучить за вменяемое время.
А, так вот, что всех испугало! Дописал пояснение, спасибо.
Я не надеюсь, что кто-нибудь мне с ходу напишет код сложнее, чем nested loops. Во-первых, на собеседовании программисты-интроверты находятся в состоянии сильного стресса и "тупят". А во-вторых, на реализацию более сложного алгоритма банально не хватит времени — я писал реализацию merge join для статьи почти полчаса, хотя точно знал, что делать.
На собеседовании такой роскоши не будет, поэтому мы просто поговорим.
Что касается того, кого я ищу, то на самом деле, мне плевать на внутренности РСУБД. Я просто пытаюсь понять, насколько глубоко человек изучил те технологии, с которыми он работал. Т.е. если у вас в проекте было много low-level NIO, а с базой вы почти не работали — я не буду ожидать от вас знания Merge Join, но захочу услышать про селекторы и грин-треды.
Подобный подход прокатывает на ранних стадиях. На проектах посложнее однажды появляется архитектор или ведущий разработчик, который компенсирует нехватку компетенции основателя.
Я не требую досконального знания каких-либо деталей. Но если кандидат заявляет, что он три года оптимизировал запросы в Oracle, он должен понимать вывод EXPLAIN'а, а значит, должен различать типы JOIN'ов. Если это не так, он либо дилетант, либо лжец.
При этом я готов простить человеку даже непонимание разницы между float и double, если в остальном он молодец.
Дилетанты нам не нужны, а недостающие знания мы всегда подкачаем.
Для начала, меня устроит устное описание любого из вышеприведенных алгоритмов. Например, нормальный ответ:
"Берет все записи из левой таблицы и для каждой из них находит соответствующую запись в правой таблице."
Уже понятно, что человек не мыслит категориями волшебных коробок.
Далее я попрошу оценить асимптотику этого решения и предложить улучшения.
Настолько, чтобы использовать его эффективно и без очевидных ошибок.
Например, избегать nested loops join в запросах.
Не создавать каждый раз новый ObjectMapper в Jackson и не гонять по кругу сериализацию.
Буферизовать IO и не злоупотреблять seek'ами в RandomAccessFile.
Мы пока используем MapReduce, и у нас слишком много легаси, чтобы «резко перейти».
Здесь пригодится то, что Scalding уже неофициально умеет работать поверх Spark, а Cascading клянется вскоре доделать официальную поддержку Spark и Storm(!).
Мы надеемся, что сможем обеспечить себе плавный переход между бекендами.
Про Index Join мне уже напомнили в комментах выше, но добавлять его в статью уже не хочется. Тем более, его код будет выглядеть почти как у HashJoin, только без построения хеша.
Так же я не написал про джойн по не-равенству, алгоритм sort join, anti join и еще много всяких редких штук.
Про собеседования мысль вот:
Как я писал в комментах выше:
Про дилетантов и лжецов был вполне конкретный контекст. Про согласен/не согласен я ничего не говорил.
Меня Join'ы интересуют больше в разрезе офлайн аналитики, различных SQL поверх Hadoop. Там криво написанное условие превращается в лишние каскады map-reduce'ов и множественные OOM'ы.
Базы данных — достаточно узкая область, чтобы ее можно было изучить за вменяемое время.
Я не надеюсь, что кто-нибудь мне с ходу напишет код сложнее, чем nested loops. Во-первых, на собеседовании программисты-интроверты находятся в состоянии сильного стресса и "тупят". А во-вторых, на реализацию более сложного алгоритма банально не хватит времени — я писал реализацию merge join для статьи почти полчаса, хотя точно знал, что делать.
На собеседовании такой роскоши не будет, поэтому мы просто поговорим.
Что касается того, кого я ищу, то на самом деле, мне плевать на внутренности РСУБД. Я просто пытаюсь понять, насколько глубоко человек изучил те технологии, с которыми он работал. Т.е. если у вас в проекте было много low-level NIO, а с базой вы почти не работали — я не буду ожидать от вас знания Merge Join, но захочу услышать про селекторы и грин-треды.
При этом я готов простить человеку даже непонимание разницы между float и double, если в остальном он молодец.
Дилетанты нам не нужны, а недостающие знания мы всегда подкачаем.
"Берет все записи из левой таблицы и для каждой из них находит соответствующую запись в правой таблице."
Уже понятно, что человек не мыслит категориями волшебных коробок.
Далее я попрошу оценить асимптотику этого решения и предложить улучшения.
Например, избегать nested loops join в запросах.
Не создавать каждый раз новый ObjectMapper в Jackson и не гонять по кругу сериализацию.
Буферизовать IO и не злоупотреблять seek'ами в RandomAccessFile.
Здесь пригодится то, что Scalding уже неофициально умеет работать поверх Spark, а Cascading клянется вскоре доделать официальную поддержку Spark и Storm(!).
Мы надеемся, что сможем обеспечить себе плавный переход между бекендами.