Алгоритмы соединения данных

Posted: Октябрь 9, 2010 in TSQL

Хотелось бы поговорить про алгоритмы соединения данных. Когда вы смотрите план запроса в SQL Server, то видите, что при соединении таблиц могут использоваться несколько разных типов соединений. Дело в том, что в зависимости от соединяемых таблиц и наличия индексов оптимизатор может использовать разные алгоритмы. Это может быть Nested Loop, Merge, Hash. Давайте посмотрим на них поближе.

Nested loop join

Это соединение использует внешнюю таблицу (на графической схеме показывается сверху) и внутреннюю (нижнюю). Внешний цикл использует внешнюю входную таблицу построчно. Во внутреннем цикле для каждой внешней строки производится сканирование внутренней входной таблицы и вывод совпадающих строк.
В простейшем случае во время поиска целиком просматривается таблица. Это называется упрощенным соединением. Если при поиске используется индекс, то такой поиск называется индексным. Если индекс создается в качестве части плана запроса (и уничтожается после завершения запроса), то он называется временным индексным.
Такое соединение является особенно эффективным, когда таблицы невелики, либо внешняя таблица сравнительно невелика, а внутренняя велика и заранее индексирована по join полю.

Merge join

Для такого соединения нужно, чтобы была выполнена сортировка по join-полям. Хорошо, если на каждом поле будет индекс, но если его нет, то оптимизатор установит оператор сортировки. Из названия понятно как действует этот метод: получается строка из каждого набора данных, сравнивается, а затем либо соединяется, либо берется следующая строка из набора с меньшим значением.
Merge join является самым эффективным соединением, если необходимые данные могут быть получены из существующих индексов с выполненной предварительной сортировкой. Однако оно может быть очень ресурсоемким, если сортировку все же придется делать.

Hash join

Hash join является самым интересным из трех представленных. Это соединение будет использовано, если обе таблицы велики и нет индексов по join-полям. Это самая наихудшая ситуация.Hash join выполняется в два этапа: построение и проба. При построении берется первая таблица, вычисляются хэш значения join-полей, строится хэш таблица. Во второй фазе берется вторая таблица, и вычисляются хэш значения ее join-полей. Далее на основе хэша вычисляется соответствующий список хэш таблицы. И для каждой записи первой таблицы в соответствующем списке из хэш таблицы происходит сравнивание с записью второй таблицы. При совпадении выдается соединение соответствующих строк.

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

Реклама
- комментарии
  1. Danila:

    все четко, понятно

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s