Hash Join, Nested Loop и Merge Join

Лена вошла в кабинет Макса с видом детектива, который почти раскрыл дело, но наткнулся на последнюю загадку.

— Макс, я снова с EXPLAIN’ом. Смотри, какая странность! — она развернула свой ноутбук. — Вот запрос с JOIN, он летает. Я написала почти такой же, но поменяла одно условие в ON — и он стал в 10 раз медленнее! План совершенно другой.

Макс отхлебнул утренний кофе и взглянул на экран. На одном плане красовался знакомый Hash Join, на другом — какой-то Nested Loop Join.

— Поздравляю, — усмехнулся он. — Ты только что столкнулась с большой тройкой стратегий соединения таблиц. Postgres не просто выполняет JOIN, он сначала выбирает, как именно его выполнить. А твое условие и статистика — ключ к его выбору.

Макс взял маркер, подошел к доске и начал рисовать.

1. Nested Loop Join

— PostgreSQL берёт строку из внешнего плана и для неё запускает внутренний план. Внутри может быть полный scan, но может быть и очень дешёвый индексный поиск.

— Когда хорош: Когда внутренняя таблица очень маленькая (например, 5 строк). Тогда «пробежаться» по ней недолго. Или когда для поиска во внутренней таблице есть очень селективный индекс.

— Когда плох: если внешний план возвращает много строк, а внутренний каждый раз читает большой объём. Две таблицы по 100 тысяч строк действительно могут породить миллиарды проверок, но только при неудачном внутреннем плане.

2. Hash Join

— Это твой старый знакомый. PostgreSQL полностью читает выбранный build-вход и строит по нему хеш-таблицу, а затем проверяет строки второго входа. Планировщик обычно старается хешировать более удобный по оценке набор, но нет правила «всегда меньшая таблица»: важны выбранный план, ширина строк и ограничения соединения.

— Когда хорош: Когда таблицы большие и соединяются по условию равенства (=). Это самый частый и эффективный способ.

— Ограничение: нужен hashjoinable-оператор, обычно равенство. Для условий вроде > или LIKE Hash Join не подходит.

3. Merge Join

— А это самый хитрый способ. Если обе таблицы отсортированы по ключу соединения, Postgres может соединить их за один проход, просто идя по обоим спискам одновременно, как застёжка-молния.

— Когда хорош: Когда соединяются большие, уже отсортированные таблицы (например, по выходу из Index Scan).

— Ограничение: Требует сортировки. Если данные не отсортированы, то узел Sort может съесть всю выгоду.

Лена хлопнула себя по лбу:

— Точно! В быстром запросе у меня было t1.user_id = t2.user_id, и он выбрал Hash Join. А в медленном — t1.value > t2.limit, и для этого неравенства Hash Join не подошел. Ему пришлось использовать медленный Nested Loop!

Макс кивнул:

— Это закономерно: для неравенства Hash Join не работает. Но вот где главное — Nested Loop не всегда беда. Проблема часто не в самом JOIN, а в том, что планировщик не угадал, сколько реально вернёт строк и выбрал неподходящий алгоритм.

— Да? — удивилась Лена.

— Вот смотри: если в плане у Nested Loop написано rows=2, а на деле actual rows=1500 — это тревожный признак. Планировщик думает, что с каждой внешней строки получит всего пару совпадений, а реально их гораздо больше. Потому и делает медленный вложенный цикл. Чаще всего причина такого - устаревшая или неточная статистика.

— А как понять, что дело именно в статистике?

— Сначала сравни rows и actual rows с учётом loops. Большое расхождение подтверждает ошибку оценки, но не объясняет её автоматически. Причиной бывает устаревшая статистика, зависимость столбцов, параметр плана или условие, которое трудно оценить. ANALYZE — один из первых тестов, а не универсальное лечение.

— Получается, не всегда условие виновато? Иногда плохой план — это просто сбившаяся статистика?

— Да. статистика очень важна для выбора правильного алгоритма соединения. Это как информация о длине улиц и пробках для навигатора.

— Поняла. Теперь буду внимательнее к статистике. На всякий случай пробегусь по таблицам с ANALYZE!

Макс улыбнулся:

— Обычно база сама заботится о статистике через autovacuum. Руками ANALYZE нужен только при массовых изменениях или явных проблемах с производительностью.