Выбор алгоритма JOIN имеет огромное влияние на производительность SQL-запроса. Оптимизатор СУБД автоматически выбирает лучший вариант, но важна
актуальная статистика по данным таблиц.
| Критерий |
Nested Loop Join |
Hash Join |
Merge Join |
|
Базовый механизм
|
Вложенные циклы
|
Хэш-таблица в памяти
|
Сортировка и слияние
|
|
Принцип работы
|
Для каждой строки из внешней таблицы (Outer table) сканируется (или ищется по индексу) весь внутренний набор данных (Inner table)
|
Строится хеш-таблица в памяти для меньшей из двух таблиц по ключу JOIN. Затем сканируется большая таблицу и для каждой строки ищется совпадение в хэш-таблице
|
Сначала обе таблицы сортируются по ключу JOIN (если они ещё не отсортированы). Затем отсортированные таблицы сканируются параллельно, сравнивая текущие строки и продвигаясь по той таблице, чей ключ меньше
|
|
Оператор соединения
|
Любой (=, BETWEEN, >, <)
|
Только равенство (=)
|
Только равенство (=)
|
|
Использование памяти
|
Минимальное
|
Высокое (для хэш-таблицы)
|
Умеренное (для сортировки)
|
|
Сброс на диск (Spilling)
|
Редко (только если большие промежуточные результаты)
|
Часто, если недостаточно памяти
|
Может быть при сортировке больших объёмов
|
|
Таблицы отсортированы уже?
|
Не важно
|
Не важно
|
Идеально, если да (критично)
|
|
Индексы
|
Идеален для внутренней таблицы
|
Не так важны для самого JOIN, но полезны для фильтрации до JOIN
|
Полезны для сортировки, если нет других средств
|
|
Производительность
|
Очень медленно для больших таблиц без индекса
|
Очень быстро если помещается в память
|
Очень быстро если отсортированы таблицы
|
|
Производительность
|
Очень быстро, если малая внешняя и индексированная внутренняя таблицы
|
Очень медленно при интенсивном spilling
|
Очень медленно при сортировке больших таблиц
|
|
Когда лучше?
|
• Маленькая внешняя таблица и индексированная внутренняя таблица: самый эффективный сценарий. Если внешний набор данных очень мал, а внутренний имеет подходящий индекс по ключу JOIN, то поиск по индексу будет очень быстрым для каждой строки
• Очень маленькие обе таблицы: если обе таблицы содержат всего несколько строк, накладные расходы на построение хэш-таблиц или сортировку (которые нужны для других JOIN-ов) могут превысить выгоду
• Небольшое количество строк во внешней таблице: если условие WHERE сильно отфильтровывает одну из таблиц до нескольких строк, NLJ может быть быстрым
• JOIN по условиям неравенства: NLJ — часто единственный способ выполнения JOIN по условиям вроде =, BETWEEN, >, <, так как Hash и Merge JOINs требуют условий равенства
|
• Идеальный сценарий: одна таблица значительно меньше другой. Меньшая таблица легко помещается в память, хэш-таблица строится быстро, а поиск по хэшу очень быстр
• Таблицы среднего размера, обе помещаются в память: если обе таблицы достаточно малы, чтобы их хэш-таблицы (или хотя бы одна) поместились в доступную память
• Отсутствие полезных индексов: если для полей JOIN нет эффективных индексов, Hash Join часто превосходит Nested Loop Join
• Соединение по условию равенства (=): Hash Join специально разработан для этого
|
• Самый быстрый сценарий: обе таблицы уже отсортированы по полям JOIN. Например, если таблицы хранятся в кластеризованном индексе или первичный ключ ORDER BY совпадает с полем JOIN - в этих случаях нет фазы сортировки, и JOIN выполняется очень быстро
• Очень большие таблицы, которые не помещаются в память: Merge Join не требует больших объёмов памяти для хэш-таблиц. Сортировка может быть выполнена на диске, если данных слишком много
• Последующие операции требуют сортировки: если результат JOIN всё равно нужно будет сортировать (например, для ORDER BY или оконных функций), то сортировка для Merge Join может быть переиспользована, уменьшая общую стоимость запроса
• Основное условие: JOIN по условию равенства (=)
|
|
Когда хуже?
|
• Обе таблицы большие и без индексов: катастрофически медленно. Количество операций равно rows_outer * rows_inner
• Большая внешняя таблица и большая внутренняя таблица (даже с индексом): поиск по индексу для каждой строки большой внешней таблицы всё равно может быть очень накладным
• Нет подходящего индекса для внутренней таблицы: тогда для каждой строки внешней таблицы придется сканировать всю внутреннюю таблицу
|
• Не хватает памяти: если хэш-таблица для меньшей таблицы не помещается в память, ей приходится сбрасывать данные на диск (spilling). Это резко снижает производительность, т. к. операции I/O диска намного медленнее операций RAM
• Низкая кардинальность полей JOIN: если поля JOIN имеют очень мало уникальных значений, то хэш-таблица может быть неэффективной из-за большого количества коллизий
• Очень маленькие таблицы: накладные расходы на построение хэш-таблицы могут быть больше, чем выгода
|
• Обе таблицы не отсортированы и очень большие: стоимость сортировки обеих таблиц может быть огромной. Это может быть медленнее, чем Hash Join, если последний может избежать сброса на диск
• Нет достаточной памяти для сортировки: если сортировка сама по себе требует сброса данных на диск, производительность сильно падает
• Низкая кардинальность полей JOIN (много дубликатов): алгоритм становится сложнее, когда есть много повторяющихся ключей, т. к. приходится сканировать вперёд и назад, чтобы найти все совпадения для каждого дубликата
|