Spec-Zone .ru
спецификации, руководства, описания, API

8.13.8. Алгоритмы Соединения вложенного цикла

MySQL выполняет соединения между таблицами, используя алгоритм вложенного цикла или изменения на нем.

Алгоритм Соединения вложенного цикла

Простое соединение вложенного цикла (NLJ), алгоритм читает строки из первой таблицы в цикле по одному, передавая каждую строку к вложенному циклу, который обрабатывает следующую таблицу в соединении. Этот процесс повторяется так много раз, как там остаются таблицами, к которым присоединятся.

Предположите что соединение между тремя таблицами t1, t2, и t3 должен быть выполнен, используя следующие типы соединения:

Table   Join Typet1      ranget2      reft3      ALL

Если простой алгоритм NLJ используется, соединение обрабатывается как это:

for each row in t1 matching range {  for each row in t2 matching reference key {    for each row in t3 {      if row satisfies join conditions,      send to client    }  }}

Поскольку алгоритм NLJ передает строки по одному от внешних циклов до внутренних циклов, он обычно читает таблицы, обработанные во внутренних циклах много раз.

Блокируйте Алгоритм Соединения Вложенного цикла

Блочный Вложенный цикл (BNL) присоединяется к буферизации использования алгоритма чтения строк во внешних циклах, чтобы уменьшить число раз, что таблицы во внутренних циклах должны быть считаны. Например, если 10 строк читаются в буфер, и буфер передают к следующему внутреннему циклу, каждое чтение строки во внутреннем цикле может быть сравнено со всеми 10 строками в буфере. Уменьшение числа раз внутренняя таблица должно быть считано порядком величины.

MySQL использует буферизацию соединения при этих условиях:

Для соединения в качестве примера, описанного ранее для алгоритма NLJ (не буферизуя), делается соединение, как следуют за буферизацией соединения использования:

for each row in t1 matching range {  for each row in t2 matching reference key {    store used columns from t1, t2 in join buffer    if buffer is full {      for each row in t3 {        for each t1, t2 combination in join buffer {          if row satisfies join conditions,          send to client        }      }      empty buffer    }  }}if buffer is not empty {  for each row in t3 {    for each t1, t2 combination in join buffer {      if row satisfies join conditions,      send to client    }  }}

Если S размер каждого сохраненного t1, t2 комбинация является буфером соединения и C число комбинаций в буфере, таблице числа раз t3 сканируется:

(S * C)/join_buffer_size + 1

Число t3 сканирования уменьшаются как значение join_buffer_size увеличения, до точки, когда join_buffer_size является достаточно большим, чтобы содержать все предыдущие комбинации строки. В той точке нет никакой скорости, которая будет получена, делая это больше.