Алгоритмы соединения: вложенный цикл, хеширование и слияние

Вы уже знаете синтаксис INNER JOIN. На собеседовании на позицию старшего разработчика интервьюеры спрашивают, как база данных физически выполняет соединение. Существуют три алгоритма:

• Соединение вложенным циклом
• Хеш-соединение
• Соединение слиянием (сортировка и слияние)

Логический тип соединения (INNER, LEFT) не зависит от алгоритма. Планировщик выбирает алгоритм на основе размеров таблиц, индексов и порядка сортировки. Понимание того, когда каждый алгоритм эффективнее остальных, — основа этого урока.

Вложенный цикл — самый простой алгоритм: для каждой строки внешней таблицы выполняется поиск совпадений во внутренней таблице. В псевдокоде это два цикла, один внутри другого.

В простейшем случае сложность составляет O(внешняя × внутренняя), что очень плохо для больших таблиц. Но алгоритм становится отличным вариантом, если во внутренней таблице есть индекс по ключу соединения: для каждой строки внешней таблицы выполняется дешёвый поиск по индексу вместо полного сканирования внутренней таблицы.

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

Признак вложенного цикла — значение loops у внутреннего узла. В примере указано loops=3, потому что внешняя сторона вернула 3 строки, поэтому сканирование внутреннего индекса выполнилось 3 раза.

Проблема возникает, когда внешняя сторона велика. Если внешняя сторона возвращает 2 миллиона строк, внутренняя часть выполняется 2 миллиона раз. Даже быстрый поиск за 0,01 мс превращается в 20 секунд.

На собеседовании отмечайте любой вложенный цикл, у которого значение loops велико, а во внутренней таблице нет хорошего индекса: именно такой запрос будет медленным.

Хеш-соединение хорошо работает с большими неотсортированными таблицами. Оно выполняется в две фазы:

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

Каждая таблица читается только один раз, поэтому сложность составляет примерно O(внешняя + внутренняя). Индексы и предварительно отсортированные данные не требуются, поэтому этот алгоритм преобладает при больших аналитических соединениях по условиям равенства.

О хеш-соединениях необходимо упомянуть две вещи:

• Они работают только с условиями соединения на равенство (a.id = b.id). Условие диапазона, например a.x < b.y, не может использовать хеш-соединение.
• Сторона построения должна помещаться в work_mem. Если это не так, PostgreSQL выгружает части данных на диск (вы увидите Batches: > 1 и использование диска), что сильно замедляет соединение.

Поэтому хеш-соединение с огромной стороной построения и маленьким значением work_mem — это реальная ошибка производительности, на которую стоит указать.

Соединение слиянием (сортировка и слияние) требует, чтобы оба входных набора были отсортированы по ключу соединения. Затем алгоритм проходит по ним синхронно, как при слиянии двух отсортированных списков, продвигая тот указатель, который отстаёт.

Алгоритм эффективен, когда входные данные уже отсортированы, например получены непосредственно из индекса в порядке ключа, поскольку тогда этап сортировки не нужен. В отличие от хеш-соединения, он также поддерживает соединения по диапазону и неравенству.

Если входные данные предварительно не отсортированы, планировщик добавляет явные узлы Sort, и стоимость сортировки может сделать хеш-соединение более дешёвым вариантом.

Запомните, когда каждый алгоритм эффективнее всего:

• Соединение вложенным циклом — небольшая внешняя таблица и индексированный ключ соединения во внутренней таблице; также это единственный вариант для соединений не по равенству, если входные данные не отсортированы.
• Хеш-соединение — большие неотсортированные таблицы, соединяемые по равенству; индексы не нужны.
• Соединение слиянием — оба входных набора уже отсортированы по ключу (часто благодаря индексам) или требуется соединение по диапазону; отлично подходит для очень больших предварительно отсортированных наборов.

Планировщик оценивает стоимость каждого варианта и выбирает самый дешёвый с учётом оценочного количества строк.

Использование ресурсов у этих алгоритмов сильно различается, и интервьюеры проверяют, понимаете ли вы это:

• Соединение вложенным циклом — минимальное использование памяти; стоимость определяется повторяющимися поисками во внутренней таблице.
• Хеш-соединение — требует памяти для хеш-таблицы; при слишком большом размере выгружает данные на диск.
• Соединение слиянием — само слияние дёшево, но предварительная сортировка может быть дорогой; сортировки также используют work_mem и могут выгружать данные на диск.

Поэтому увеличение work_mem может превратить медленное хеш-соединение или сортировку с выгрузкой на диск в операцию, выполняемую в памяти. Это конкретный вариант оптимизации.

Классический сценарий: в среде разработки запрос выполнялся быстро, а в боевой среде — медленно. План показывает вложенный цикл со значением loops=3000000.

Планировщик недооценил количество строк на внешней стороне (устаревшая статистика показывала 3 строки, тогда как на самом деле их было 3 миллиона), поэтому он выбрал вложенный цикл. При точной статистике он выбрал бы хеш-соединение.

Ваш ответ на собеседовании: выполнить ANALYZE, чтобы оценка стала корректной; после этого планировщик переключится на хеш-соединение, и запрос значительно ускорится.

Обычно не следует принудительно выбирать алгоритмы, но при тестировании можно сравнить их. PostgreSQL предоставляет переключатели для отдельных алгоритмов:

SET enable_nestloop = off; и аналогичные переключатели для enable_hashjoin и enable_mergejoin. Отключите один алгоритм, повторно выполните EXPLAIN ANALYZE и проверьте, действительно ли альтернативный вариант работает быстрее.

Правильные способы исправления остаются прежними: свежая статистика, подходящие индексы, достаточный объём work_mem и селективные предикаты. Принудительный выбор предназначен только для диагностики.

Рассмотрим аналитическую нагрузку, при которой две большие таблицы фактов и измерений соединяются по идентификатору:

• Если таблица измерений помещается в память, ожидайте хеш-соединение, часто это лучший вариант.
• Если обе таблицы поступают отсортированными благодаря индексам, соединение слиянием может обойтись без построения хеш-таблицы.
• Соединение вложенным циклом в такой ситуации было бы тревожным признаком, обычно вызванным неправильной оценкой.

Умение понять, какой алгоритм выбрал планировщик, и оценить, стоило ли выбирать именно его, — это как раз признак уровня старшего разработчика, который проверяют такие вопросы.

Вы соединяете две большие неотсортированные таблицы по условию равенства a.id = b.id, ни в одной из них нет полезного индекса, а статистика точна. Какой алгоритм соединения, скорее всего, выберет планировщик?

Три алгоритма соединения:

• Соединение вложенным циклом — для каждой строки внешней таблицы выполняется поиск во внутренней; отлично работает с небольшой внешней таблицей и индексированным ключом во внутренней, но опасно, когда значение loops огромно.
• Хеш-соединение — построение и проверка; лучше всего подходит для больших неотсортированных соединений по равенству, ограничено условиями равенства и доступным объёмом work_mem.
• Соединение слиянием — синхронный проход по отсортированным входным данным; идеально, когда данные уже отсортированы, а также для соединений по диапазону.

Планировщик выбирает алгоритм на основе стоимости и статистики. Неожиданный вложенный цикл с огромным количеством повторений почти всегда означает неправильную оценку количества строк — исправьте статистику.