#32: Merge sort и hash join: соединяют и сортируют

[00:20] Здарова! Меня зовут Саша Пахомов, и я инженер, который любит своё дело. Вы слушаете подкаст, в котором разработчик современной базы данных изучает, как они работают, и делится знаниями со слушателями. В сегодняшнем выпуске мы поговорим про алгоритмы сортировки и соединения таблиц. Тема довольно интересная, к тому же меня не раз спрашивали про это на собеседованиях. Прослушав выпуск, вы получите представление о трёх способах соединения таблиц и узнаете, какой из них самый эффективный, а заодно освежите свои знания по алгоритмам сортировок. Поехали!

[01:05] Чтобы обсуждать сортировки и алгоритмы соединения таблиц, нам для начала нужно представить себе одну простую картинку — план исполнения, он же query-план. По сути, это такое абстрактное синтаксическое дерево, только вместо синтаксических конструкций у нас конкретные операторы конкретных операций: например, join, filter, fetch и так далее. Звучит классно, но выглядит не очень. В этом выпуске мы будем использовать query-план максимально просто. Это дерево, у которого есть root — представьте такую ноду. Это результат нашего запроса, и наверху всегда будет оператор SELECT: если мы селектим id, возраст и пол, то там будет оператор «взять id, возраст и пол». Ниже от него идёт оператор — например, join. Если мы соединяем несколько таблиц, там будет оператор join, и у него будет два children — первая таблица и вторая. А ещё у нас, например, есть WHERE, то есть помимо соединения мы делаем фильтрацию, и эти фильтры тоже будут располагаться где-то в дереве.

[02:01] Нужно представить себе это дерево так: снизу находятся операторы доступа к данным, то есть чтение — sequential scan, index scan и так далее. Дальше идут операторы соединения, фильтрации, агрегаций. А наверху — SELECT, то есть выделение именно тех полей, которые у нас запросили. Такое вот дерево, идущее снизу вверх, и наверху одна нода. То, как этот план строится и оптимизируется, мы обсудим в следующем выпуске, а пока нам достаточно просто представить, что какой-то план есть.

[02:26] И вот, имея этот план выполнения, мы начинаем выполнять операторы, начинаем выполнять запрос. Проблема в том, что результат запроса — тот result set, который мы хотим вернуть пользователю, — не всегда помещается в нашей оперативной памяти. Нам приходится использовать buffer pool, например страничный, чтобы подгружать страницы с диска. И тут появляется новое ограничение: мы не можем для отдельного оператора — например, того же join — использовать только in-memory-вариант, то есть тот, что целиком живёт в оперативной памяти. Нужно учитывать и вариант, когда данные в оперативную память не помещаются и приходится задействовать дисковые алгоритмы.

[03:06] Когда мы говорим про диск, всегда нужно помнить, что random I/O — это всегда более медленный доступ, чем sequential I/O. Random I/O — это когда мы доступаемся к данным по случайным страницам, без последовательного чтения. А sequential I/O — это как раз последовательное чтение, и при работе с диском оно всегда лучше.

[03:26] Говоря про реляционные данные, про реляционную алгебру — которая, по сути, и задаёт формат данных и то, как мы их селектируем, читаем и обрабатываем в современных SQL-базах, — важно помнить: реляционная алгебра вообще не подразумевает сортировки. Там нет такого понятия, что данные отсортированы или не отсортированы. Казалось бы, зачем нам тогда сортировки вообще нужны? А вот зачем. Во-первых, они нужны, когда мы делаем ORDER BY: если мы выполняем такой запрос, подразумевается, что ответ будет отсортирован. Во-вторых, когда мы делаем DISTINCT — вывести только уникальные тюплы, уникальные записи, — нам нужно либо отсортировать данные, либо использовать другие алгоритмы, но сортировка здесь тоже может быть полезна.

[04:06] Ещё пример — когда мы загружаем данные в B+-дерево. Если мы делаем SELECT с COPY INTO или CREATE TABLE AS SELECT, то отсортированные данные из подзапроса намного проще вставить в новую таблицу: в B+-дерево отсортированные данные ложатся гораздо эффективнее, чем неотсортированные. К тому же отсортированные данные можно использовать при реализации GROUP BY: когда мы делаем агрегацию с группировкой, нам нужно как-то сконцентрировать в одном месте значения с одним и тем же ключом, а отсортированные данные по определению кладут одинаковые значения друг за другом. Так что сортировки в базах данных используются широко.

[04:52] Есть два типа сортировок, если делить глобально. Первый — сортировки в оперативной памяти, второй — сортировки на диске. Если таблица целиком умещается в оперативную память — у нас просто огромное счастье, и мы можем использовать quicksort, быструю сортировку. Почему её — понятно, потому что она быстрая. Как она работает, я сейчас в подкасте объяснять не буду — если интересно, посмотрите отдельно; но это самый распространённый, быстрый и эффективный алгоритм сортировки данных именно в оперативной памяти.

[05:20] Если пользователь задал нам запрос с LIMIT 10 — то есть хочет видеть в результате только 10 отсортированных записей, — то мы можем применить ещё один алгоритм, который называется top-N heap sort. По сути, мы строим отсортированную кучу размера того лимита, который нам задали: LIMIT 10 — значит, куча будет размера 10. Мы делаем full scan по таблице и вставляем данные в эту кучу. По завершении full scan в куче останутся только 10 топовых записей, отсортированных по какому-то предикату, — их мы и вернём. Так что если у нас ограниченное и небольшое количество записей, мы, скорее всего, используем кучу. А если нужно просто всё отсортировать — это quicksort.

[06:06] Но не всё так просто. В некоторых случаях данные просто не помещаются в оперативную память на одной машине, и тогда приходится задействовать диск. Сортировка с использованием диска называется external merge sort. Работает она несложно и состоит из двух фаз. Первая фаза — когда мы считываем данные чанками, кусочками, в память, сортируем эти кусочки и записываем обратно на диск. Вторая фаза — когда мы берём уже отсортированные кусочки (один и второй в простейшем случае, но вообще можно брать N кусочков одновременно) и записываем на выход отсортированный результат этих кусочков, а потом берём этот результат и рекурсивно мержим с другими кусочками.

[06:52] Таким образом, в оперативную память одномоментно загружается 2–3 страницы, если это примитивный минимальный случай, или столько страниц, сколько мы задали. Это такая итеративная сортировка с сохранением промежуточного результата на диск. Так мы можем в целом отсортировать таблицу огромных размеров — сколько на диск умещается, такую таблицу и отсортируем. Это лишь вопрос времени.

[07:20] Говоря о сортировках и вообще о запросах и оптимизациях, нужно упомянуть такой факт: мы можем материализовать данные и делать так называемый early materialization. Это когда мы сортируем наши тюплы — данные, где есть ключи, по которым мы сортируем, и значения, — и они у нас копируются в памяти, всегда ездят с нами по всем сортировкам, неизбежно увеличивая размер занимаемой памяти. Зато данные всегда при нас, и когда мы будем выдавать их наружу, нам не придётся заново считывать их с диска. Это early materialization.

[07:52] И есть второй вариант — late materialization, когда мы таскаем за собой только id тех записей в реальных данных, которые потом, уже при сборке результата запроса и возвращении его клиенту, будем подчитывать. То есть сначала мы сортируем такие легковесные записи — где есть только ключи и условные ссылки на данные, — а после того как всё отсортировали и выбрали и уже готовы возвращать результат, считываем с диска именно то, что нам нужно. Так мы экономим место в памяти, и, например, в случае columnar storage, который не хочет много читать с диска, или вообще в аналитических системах, late materialization — очень эффективный способ.

[08:33] Но это не единственная оптимизация, которую можно применить при сортировке данных. Есть ещё одна, но, прежде чем её понять, давайте ещё раз разберём пошагово external merge sort, который одновременно может брать всего лишь две страницы. Представим, что у нас есть набор страниц на диске — это наша таблица. И нам нужно получить таблицу, то есть такой же набор страниц, но уже с отсортированными данными. Во время первой фазы мы берём в память просто одну страницу, считываем её — она занимает 4 килобайта, как мы знаем, — и на её основе создаём новую, отсортированную страницу. Отсортированную страницу записываем на диск. Затем берём следующую неотсортированную страницу, сортируем, записываем на диск. Берём следующую, сортируем, записываем. Это первая фаза, и, пока мы не отсортируем все страницы, ко второй фазе перейти не можем.

[09:20] Допустим, все страницы отсортированы. Начинается вторая фаза. Делается она так. Мы берём две уже отсортированные страницы, например первую и вторую, и ставим курсоры на начало этих страниц — мы же знаем, что данные отсортированы. Например, в первой лежат 0, 1, 2, 3, 10, во второй — 0, 1, 2, 3, 13. Ставим курсоры на начало обеих страниц — у нас два курсора — и начинаем итеративно проходиться. Сравниваем значения под курсорами: меньшее из них кладём в результирующую страницу, а тот курсор, из которого мы только что взяли значение, передвигаем на следующую позицию. Теперь сравниваем два новых значения, меньшее снова кладём в результирующую страницу и двигаем соответствующий курсор. Так два курсора по очереди двигаются по отсортированным данным, и на выходе мы получаем две слитые между собой отсортированные страницы.

[10:09] Таким образом мы берём по две странички, и в итоге получается в два раза меньше страниц, уже отсортированных по две. Потом мы читаем их по две — получается по четыре. И так до тех пор, пока не отсортируем все данные. Да, это немножко сложновато звучит, и приседаний мы делаем много, но зато экономим оперативную память — и это реализация сортировки на диске.

[10:31] Узких мест у этого алгоритма на самом деле довольно много. В основном это, конечно, I/O — мы упираемся в работу с диском. Мы знаем, что диск медленный, а мы каждый раз на него записываем и с него считываем, и это всё медленно. Одна из оптимизаций, которая чуть-чуть облегчает страдания, — это prefetch. Что такое prefetch? Когда мы знаем, какие у нас есть страницы и что мы с ними делаем — сейчас проходим по всей таблице, по всем страницам, сортируем их и записываем в новые, — мы понимаем, что раз мы считали первую страницу, то нам стопроцентно нужно будет считать вторую, потом третью, потом четвёртую. Мы ведь не ищем какие-то записи, чтобы, найдя, выйти из алгоритма, — нам нужно прочитать всё, потому что нас интересует конечный отсортированный результат.

[11:19] Как работает prefetch? В одном потоке мы считываем страницу и начинаем её сортировать, и, пока CPU занят сортировкой, другой поток уже подгружает вторую и третью страницу в буфер. То есть в буфере уже лежит следующая страница, которую CPU просто подхватит и начнёт сортировать. Получается разделение: I/O мы делаем в отдельном потоке, а сортировку — в другом. Это называется prefetch, довольно стандартная оптимизация, и она немного облегчает страдания при работе с I/O.

[11:54] Помимо prefetch, есть ещё всякие интересные оптимизации сортировок. Например, само сравнение — вот этот код, который сравнивает два ключа: какой больше, какой меньше или равны ли они. Откуда его взять, как его интерпретировать? Нам на вход приходит просто SQL-запрос, по сути строка; мы её как-то распарсили, взяли этот оператор, но всё равно это ещё знак «больше» между двумя int-ами, или «меньше», и так далее. Как это имплементировать? Можно просто написать на C набор функций и передавать алгоритму сортировки указатель на нужную функцию сравнения. Но это прыжки по указателям, и, если мы очень много и жёстко сортируем, это может оказаться узким местом.

[12:29] Чтобы этого избежать, базы данных генерируют алгоритмы сортировок под каждый тип — ну, некоторые базы данных, не все, конечно. То есть если мы сортируем ключи типа int, у нас будет специальная функция — например, int sort. Если сортируем double или string — будет double sort, string sort. Или, например, int, double sort. То есть мы не передаём функцию сравнения в дженерализованный алгоритм сортировки, а используем узкоспециализированные под конкретные типы, — так мы избегаем прыжков по указателям. В целом количество поддерживаемых базой данных типов ключей ограничено, и ничто не мешает сгенерировать под каждый тип свою функцию. Такая вот интересная оптимизация.

[13:12] Ещё одна оптимизация — когда мы сравниваем конкретно строки. Чтобы не сравнивать их посимвольно — что довольно медленно (первая буква с первой, вторая со второй, обычное сравнение строк), — мы можем сравнивать бинарные префиксы массивов этих varchar’ов. Varchar — это же массив байтов. Мы можем сравнить префиксы байтов, и, если один префикс больше другого, значит, и строка больше другой строки. Мы свитчаемся в это низкоуровневое бинарное сравнение, которое сильно быстрее сравнения строк, и понимаем, кто больше, кто меньше, даже не интерпретируя их как строки. А если бинарные префиксы равны и мы понимаем, что нужно смотреть уже на строчное представление, — мы фоллбэчимся в строчное представление и делаем медленное сравнение. Тоже довольно интересная оптимизация.

[14:05] Нам как разработчикам баз данных иногда может повезти. Например, ключ сортировки… Вообще, это хорошая практика — сортировать по ключам, на которые есть индексы, чтобы базе данных было легче. До этого мы рассматривали алгоритмы, где сортируем неиндексированные ключи. А вот если на ключик есть индекс, причём B+-дерево, то мы можем взять нижние листья этого B+-дерева и просто прочитать их от начала до конца — мы же знаем, что там всё отсортировано, B+-дерево-индекс отсортирован по определению. И если он кластеризованный — а кластеризованный значит, что внутри индекса, прямо среди значений, лежат сами данные, — то это вообще супер. Мы просто берём и читаем индексные листья один за другим, они и на диске лежат один за другим, и просто возвращаем. Это супербыстро.

[14:48] А если индекс некластеризованный и у нас есть только ссылки на данные, то представьте: мы делаем sequential scan по отсортированным ключам на диске — это правда будет быстро, — но для каждого ключа нам придётся прыгать в случайное место в файлах данных и забирать оттуда данные. Поэтому использовать B+-дерево-индекс для сортировки, если он unclustered, — плохая идея. Если есть возможность и вы часто сортируете по какому-то ключу — сделайте на него индекс, и, если база данных поддержит кластеризованный индекс, он здесь будет очень кстати.

[15:46] Перейдём к агрегации. Тут, как правило, всё проще и быстрее делается через хеш, и здесь у нас опять два стула. Если хеш-таблица полностью умещается в память — нам повезло, и мы просто строим её в памяти и считаем агрегаты. Как это выглядит? Берём таблицу из нашего запроса, где есть GROUP BY по какому-то ключу, — это и будет ключ, по которому мы считаем хеши. Проходимся по таблице простым sequential scan один раз, вычисляем хеш и кладём в хеш-таблицу. В хеш-таблице у нас получается «ключ → значение», причём значение — это не конкретные тюплы, а уже посчитанный предагрегат: мы делаем агрегацию на ходу.

[16:22] Что я имею в виду? Если агрегат — это, например, SUM или COUNT, два простых случая, то мы считаем хеш, кладём в таблицу, а значение увеличиваем: для COUNT — на единицу. Потом в тот же ключ попали второе, третье, четвёртое значение — и агрегат так и растёт. В итоге, когда мы сделаем full scan, у нас в памяти будет хеш-таблица с посчитанными агрегатами, которые просто нужно вернуть клиенту. И это довольно просто.

[16:53] Но проблемы, опять же, начинаются там, где хеш-таблица в память не умещается, — а это довольно логичный кейс в контексте баз данных. Для этого мы используем другой алгоритм, который называется external hash aggregate, по сути external hashing. Что мы здесь делаем? Мы, как и в merge sort, разделяем алгоритм на две части. В первой части мы проходимся по таблице и раскладываем данные на бакеты, записывая их на диск. Бакет может принадлежать одному хешу или нескольким, но, скорее всего, одному. Допустим, у нас много данных: мы проходимся по таблице, вычисляем хеш и кладём в бакет само значение — не предагрегат, а именно значение: значение 1, значение 2, значение 3. Так у нас собирается бакет, лежащий на диске, и в одном бакете лежат ключи с одним и тем же хеш-кодом.

[17:44] Таким образом, пройдя full scan по таблице, мы получаем на диске набор бакетов — по сути, логично разбили данные на кусочки, сделали группировку. Первым шагом мы сделали группировку для GROUP BY прямо на диске. Потом мы читаем каждый бакет по одному и уже из этих сгруппированных данных строим новую хеш-таблицу по новому хеш-ключу — этот процесс называется rehash. И там уже делаем то же, что и в начале, в случае in-memory: кладём ключ и считаем для него running-агрегат. Если это сумма — просто прибавляем значение; если максимум — сравниваем, и если текущее значение больше того, что в хеш-таблице, заменяем, и так далее. То есть это считающийся в runtime агрегат. Так мы в один момент работаем с одним бакетом: берём бакет, строим по нему новую хеш-таблицу, считаем running-агрегат, берём следующий бакет — и так итеративно. Это в случае, если хеш-таблица не помещается в память целиком.

[18:45] Ну что, про агрегаты поговорили, про сортировки поговорили — и теперь можем перейти к самому интересному, к join, с чего я и начал выпуск. Я специально сначала рассказал про сортировки и хеши, потому что эти алгоритмы используются во время join точно так же, а не только при агрегации. Давайте для начала разберёмся, что такое join. Это когда мы берём две таблицы и соединяем по какому-то предикату, по какому-то условию. Чаще всего это условие соединения по ключу: есть id в одной таблице и id в другой, мы соединяем строки так, чтобы эти id были равны, и получаем как бы смердженные по этому id две таблицы.

[19:27] Углубляться в семантику join-ов — left outer join, right outer join, inner join, cross join — я сейчас не буду; это тоже важная тема, но, надеюсь, вы прочитаете сами, информации по ней много. Мы рассматриваем inner join и считаем, что все ключи у нас есть, никаких проблем нет, и соединяем две таблицы. Это наш кейс, потому что нас интересует конкретный алгоритм, а не его усложнение. Поэтому для простоты у нас две таблицы соединяются по id.

[19:53] Во время join точно так же действуют правила early materialization и late materialization, и базы данных сами решают, когда что использовать, — тут всё зависит от реализации. Выбрать алгоритм join-а и понять, делать early или late materialization, нам помогает так называемый cost analysis — анализ, который проводит оптимизатор запросов, решая, какой алгоритм здесь использовать. На самом деле это тема для следующего выпуска, но сделаю небольшую ремарку: сейчас нас интересует единственная метрика — количество I/O, то есть количество обращений к диску во время join. Чем меньше мы обращаемся к диску, тем эффективнее считаем алгоритм. Вот такая простая метрика на текущий момент.

[20:38] Говоря об алгоритмах соединения, отметим: у нас есть три основных алгоритма — nested loop join, sort-merge join и hash join. У nested loop join есть несколько реализаций. Самая наивная, простая — некоторые называют её даже stupid — это, по сути, аналог сортировки пузырьком. Что я имею в виду? Мы считываем одну таблицу в память и для каждого ключа из неё вычитываем всю вторую таблицу целиком, находя ключ, который соединяется. Потом для второго ключа первой таблицы опять вычитываем вторую, для третьего — опять вторую. По сути, это соединение пузырьком. Вложенный цикл — очень тяжёлая операция, потому что мы работаем с диском и по тысяче раз вычитываем одно и то же. Это не сильно оптимально, и такой simple loop join никто особо не делает.

[21:35] А как реализуется nested loop join на практике? В большинстве случаев это block nested loop join: мы вычитываем данные блоками, потому что у нас есть страницы, и нам выгоднее вычитывать страницы целиком и соединять их, чем каждое значение, каждый тюпл по отдельности, — так мы меньше взаимодействуем с диском. Но если по таблице есть индекс, смотрите, что получается: мы вычитываем одну таблицу в память (если она туда помещается) и для каждого её ключа ищем соответствующий не через full scan второй таблицы, а через индекс, если он есть. Тогда соединение будет гораздо быстрее, потому что мы делаем не full scan для каждого значения, а index search — и это уже получше. Но nested loop join, как правило, всегда плохой вариант.

[22:27] Следующий способ соединить две таблицы — sort-merge join, что уже больше похоже на то, что реально исполняется, когда вы выполняете адекватный запрос. Он основан, как вы можете догадаться, на алгоритме сортировки, который мы обсуждали до этого, — merge-сортировке на диске. Что происходит? На первом этапе обе соединяемые таблицы сортируются по ключу, и на выходе получаются две отсортированные таблицы, причём они могут располагаться на диске. После этого вторым этапом мы берём два курсора: один ставим на одну таблицу, другой — на другую, и вычитываем отсортированные данные в память. Так как у нас join и мы, скорее всего, хотим соединить, отсортированность подсказывает: если с левой таблицы пришёл нолик, а с правой — единица, значит, во второй нолика уже не будет.

[23:16] Мы просто скипаем наше первое значение, видим единицу — вот у нас две единицы, соединили, отдали. Потом перешагнули к следующим значениям, скажем 10 и 5: с одной стороны десятка, с другой пятёрка. Мы понимаем, что там, где у нас была десятка, пятёрки уже не будет, — пятёрку скипаем, и так далее. То есть два указателя идут, соединяют и возвращают результат наверх, другим операторам, что довольно эффективно. И самое главное — всё это может находиться на диске, и в каждый момент времени нам тоже нужно держать в памяти всего лишь две страницы.

[23:50] Есть, конечно, плохой сценарий для такой сортировки — когда ключ, по которому мы соединяемся, одинаков у большинства записей: например, id неуникальный, и у всех он равен трём. Тогда толку от сортировки, по сути, никакого. Но это довольно редкий сценарий, и мы его оставляем за скобками. Sort-merge join реально полезен, когда наши данные уже отсортированы на диске — например, мы используем clustered B+-дерево-индекс и по этому ключу начинается соединение. Тогда мы знаем, что данные на диске уже отсортированы, первая фаза сортировки пропускается, и мы сразу переходим ко второй, что довольно эффективно. И второй вариант — когда результат этого join потом нужно будет сортировать по тому же ключу; тогда логично сразу использовать sort-merge join, раз мы знаем, что данные должны быть отсортированы.

[24:46] Но если ни того, ни другого нет — данные на диске не отсортированы и результат запроса сортировать не нужно, — то наш выбор hash join, который в большинстве случаев базы данных и выбирают как основную реализацию join-ов, потому что он самый эффективный. Работает он так. У нас есть две таблицы, которые мы хотим соединить. Мы сканируем первую таблицу и на её основе билдим, так сказать, хеш-таблицу. Скорее всего, это будет linear probing — хеширование, про которое я говорил в 27-м эпизоде, так что, если хотите узнать чуть глубже про алгоритмы хеширования в базах данных, послушайте 27-й выпуск, если ещё не слушали. С помощью linear probing, который лучше всего себя показывает, мы сканируем первую таблицу и строим хеш-таблицу.

[25:31] Опять же, допустим, что эта хеш-таблица пока умещается в памяти. Потом мы сканируем вторую таблицу, точно так же вычисляем хеш той же хеш-функцией от ключа, смотрим в хеш-таблицу в памяти, и, если значение там есть, — вот мы сделали join, возвращаем наверх. И так, пока не вычитаем всю вторую таблицу. Тут, кстати, может быть интересная оптимизация. Обращение к хеш-таблице, если её части лежат на диске, может стоить нам I/O, а I/O — это дорого, и делать его мы не хотим. Во время построения хеш-таблицы мы можем рядом с ней — внутри или сбоку — строить структуру данных, которая называется Bloom-фильтр.

[26:13] Это структура из класса вероятностных: она отвечает с некоторой вероятностью. Конкретно Bloom-фильтр со стопроцентной вероятностью отвечает, что ключа в хеш-таблице нет: если его нет, фильтр говорит «нет», и на это можно положиться на все 100%. А вот если Bloom-фильтр говорит «есть», доверять ему на 100% нельзя — нужно ещё проверить самим. Фишка Bloom-фильтра в том, что вся структура умещается в кэш процессора и работает очень быстро. Таким образом, мы можем сначала спросить у Bloom-фильтра: «Эй, а есть у нас такой ключ в хеш-таблице?» Если он почти моментально сказал «нет» — мы счастливо не идём в хеш-таблицу и не читаем. А если сказал «есть» — что ж, придётся сходить, почитать и проверить, действительно ли он там. Как работает Bloom-фильтр, я, возможно, расскажу в специальном выпуске про такие вероятностные структуры данных. В общем, работает он быстро и хорошо, и многие базы данных его используют.

[27:10] Проблема у хеш-таблицы, собственно, та же, что и у любой другой структуры данных в базах: иногда оперативной памяти может не хватать, и приходится задействовать диск. Так вот, когда мы делаем hash join и понимаем, что хеш-таблица в память не умещается, базы данных используют алгоритм под названием Grace hash join, он же партиционированный hash join. Как он работает? В обычном hash join мы билдим хеш-таблицу в памяти для одной таблицы, а потом читаем вторую и делаем join. А в partitioned hash join мы строим хеш-таблицы для обеих таблиц, но, конечно, не в памяти, потому что они туда не помещаются, — они будут партиционированные и лежать на диске.

[27:49] То есть мы берём одну таблицу, вычитываем её и строим хеш-таблицу прямо на диске: записи с одним и тем же хеш-кодом для ключа пойдут в одну и ту же партицию. Партицию можно представить как страницу — мы в одну страницу на диске складываем значения с одним и тем же хешом для одной таблицы. То же самое делаем для второй. Вот у нас на диске две партиционированные хеш-таблицы для двух таблиц — первый этап сделан. Второй этап: мы берём партиции с одним и тем же хешом — партицию из одной таблицы и партицию из другой, обе с одним и тем же хешом, — загружаем их обе в оперативную память и уже там делаем join. Так, итеративно, партиция за партицией, пара за парой, мы перебираем всё на диске и возвращаем результат наверх.

[28:41] Проблема тут может быть в том, что и отдельная партиция не уместится в памяти. То есть не только вся хеш-таблица не умещается — так ещё и отдельная партиция может не влезть. Например, если ключ партиционирования — какая-нибудь дата, скажем день, и в какой-то день случилось событие, которое занимает 90% всей таблицы, — естественно, эта партиция займёт очень много места в памяти. Для этого мы можем делать так называемый recursive partitioning, рекурсивное партиционирование: сделать первую фазу, положить эту большую партицию на диск, потом взять её и сделать rehash по другой хеш-функции — то есть разбить партицию на партиции уже по другому хешу. И если и те не вмещаются, будем разбивать и их; но, как правило, двух шагов хватает, и мы за счёт двух хеш-функций разбиваем данные так, как нам удобно.

[29:35] Давайте подведём итоги. Самый эффективный способ соединить две таблицы — это hash join. Однако если результат нам нужно сортировать, то наш выбор — merge join. Большинство баз данных сами знают, какой алгоритм лучше использовать в какой ситуации, и нам как пользователям об этом задумываться не стоит. Это лишь одна из десятков оптимизаций, которые делает оптимизатор запросов, — о нём мы поговорим в следующем выпуске. Не забывайте делиться подкастом с друзьями и коллегами: давайте прокачивать себя и людей вокруг. Ну а на этом всё. Услышимся!