Когда Hash Join быстрее Nested Loops

Внутри SQL-движка соединение таблиц — это не магия, а конкретный алгоритм. Сравним два подхода к соединению таблиц.

Nested Loops работает буквально так, как звучит: берём строку из первой таблицы и ищем совпадения во второй. Если вторая таблица имеет подходящий индекс, поиск по нему будет очень быстрым, и такой алгоритм блестяще справляется с задачей маленькое соединяется с большим.

Hash Join подходит там, где Nested Loops захлёбывается. Он сначала строит хэш-таблицу по одной из входных таблиц, а затем пробегается по второй и ищет совпадения через хэш-функцию. Это даёт огромный выигрыш, когда нужно соединить два больших набора данных, и когда индексов для ускорения поиска нет. Цена такого подхода — расход памяти.

В итоге — если речь идёт о маленьком наборе строк против большого и есть индекс, Nested Loops окажется быстрее. Но если обе таблицы крупные и индексы не спасают, Hash Join чаще всего становится оптимальным выбором.

#dotnet_challenge