8.2.1.6 Nested-Loop Join Algorithms — MySQL 5.7

8.2.1.6 Алгоритмы объединения с вложенными циклами

MySQL выполняет объединения таблиц с помощью алгоритма вложенных циклов или его вариаций.

Алгоритм объединения с вложенными циклами

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

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

Table   Join Type
t1      range
t2      ref
t3      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 имеет следующие характеристики:

Буферизация объединений может использоваться, когда объединение является типа ALL или index (другими словами, когда не могут быть использованы возможные ключи, и выполняется полный поиск, соответственно, данных или строк индекса), или range. Использование буферизации также применимо к внешним объединениям, как описано в Разделе 8.2.1.11, «Объединения с блоками вложенных циклов и объединения с поблочным доступом по ключам».
Буфер объединения никогда не выделяется для первой неконстантной таблицы, даже если бы он был типа ALL или index.
В буфер объединения хранятся только столбцы, которые важны для объединения, а не целые строки.
Система переменная join_buffer_size определяет размер каждого буфера объединения, используемого для обработки запроса.
Для каждого объединения, которое может быть буферизовано, выделяется один буфер, поэтому данный запрос может быть обработан с использованием нескольких буферов объединения.
Буфер объединения выделяется до выполнения объединения и освобождается после завершения запроса.

Для примера объединения, описанного ранее для алгоритма 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 join 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 достаточно велик, чтобы вместить все предыдущие комбинации строк. В этот момент увеличение его размера не дает ускорения.