Як працює hash join у MySQL 8 і коли він замінює вкладені цикли?

Довгий час MySQL виконував з'єднання лише вкладеними циклами (nested loop): для кожного рядка першої таблиці шукаємо відповідні рядки в другій. З індексом на колонці з'єднання це дуже ефективно. Без індексу - катастрофа: повне сканування другої таблиці на кожен рядок першої (частково пом'якшене буфером block nested loop).

Hash join (MySQL 8.0.18+) працює інакше:

1. побудова: менша таблиця (після фільтрів) читається в пам'ять, будується хеш-таблиця за ключем з'єднання;
2. перевірка: більша таблиця читається один раз, для кожного рядка ключ шукається в хеш-таблиці.

Кожна таблиця читається один раз - замість N × M порівнянь виходить N + M.

EXPLAIN FORMAT=TREE
SELECT * FROM orders o JOIN import_rows r ON r.external_id = o.external_id;

-> Inner hash join (r.external_id = o.external_id)
    -> Table scan on r
    -> Hash
        -> Table scan on o

Коли MySQL обирає hash join:

• з'єднання, для якого немає придатного індексу (з 8.0.20 hash join повністю замінив block nested loop);
• зазвичай за рівністю, але з 8.0.20 і для нерівностей, зовнішніх з'єднань, напівз'єднань (EXISTS, IN) і антиз'єднань (NOT EXISTS);
• коли є індекс, оптимізатор найчастіше лишається на вкладених циклах з пошуком в індексі.

Пам'ять: хеш-таблиця будується в межах join_buffer_size. Якщо не вміщується - дані розбиваються на частини у тимчасових файлах на диску, і з'єднання сповільнюється (але все одно зазвичай краще за повний перебір). Для великих аналітичних з'єднань має сенс збільшити join_buffer_size для запиту через /*+ SET_VAR(join_buffer_size = ...) */.

Керування: окремі підказки HASH_JOIN / NO_HASH_JOIN у сучасних версіях не діють. Використовуються BNL / NO_BNL (історично про block nested loop, тепер про hash join), або optimizer_switch: block_nested_loop=off.

Що це означає на практиці:

• hash join не заміна індексам для OLTP. Запит «замовлення користувача з товарами» має йти індексами: читати всю таблицю товарів заради 5 рядків - погано навіть одним проходом;
• для разових і аналітичних запитів (звірка імпорту з існуючими даними, звіти на репліці) hash join робить прийнятними запити без спеціальних індексів;
• побачивши hash join у плані частого запиту, варто перевірити, чи не бракує індексу на колонці з'єднання. Часта причина - різні типи чи кодування колонок, через які індекс непридатний.

Докладніше в документації: Оптимізація hash join