8.2.1.2 Range Optimization — MySQL 5.7

8.2.1.2 Оптимизация диапазонов

Метод доступа range использует один индекс для извлечения подмножества строк таблицы, которые находятся внутри одного или нескольких интервалов значений индекса. Он может использоваться для индекса из одной части или нескольких частей. В следующих разделах описываются условия, при которых оптимизатор использует доступ по диапазону.

Метод доступа по диапазону для индексов из одной части

Для индекса из одной части интервалы значений индекса удобно представлять соответствующими условиями в предложении WHERE, обозначаемыми как условия диапазона, а не “интервалами.”

Определение условия диапазона для индекса из одной части таково:

Для индексов как BTREE, так и HASH, сравнение части ключа со значением константы является условием диапазона при использовании операторов =, <=>, IN(), IS NULL или IS NOT NULL.
Кроме того, для индексов BTREE, сравнение части ключа со значением константы является условием диапазона при использовании операторов >, <, >=, <=, BETWEEN, != или <>, или сравнений LIKE, если аргументом для LIKE является строка-константа, которая не начинается с символа подстановки.
Для всех типов индексов несколько условий диапазона, объединённых операторами OR или AND, образуют условие диапазона.

“Значение константы” в предыдущих описаниях означает одно из следующего:

Константа из строки запроса
Столбец таблицы const или system из того же соединения
Результат некоррелированного подзапроса
Любое выражение, полностью составленное из подвыражений предыдущих типов

Вот некоторые примеры запросов с условиями диапазона в предложении WHERE:

SELECT * FROM t1
  WHERE key_col > 1
  AND key_col < 10;

SELECT * FROM t1
  WHERE key_col = 1
  OR key_col IN (15,18,20);

SELECT * FROM t1
  WHERE key_col LIKE 'ab%'
  OR key_col BETWEEN 'bar' AND 'foo';

Некоторые значения, не являющиеся константами, могут быть преобразованы в константы на стадии распространения констант оптимизатора.

MySQL пытается извлечь условия диапазона из предложения WHERE для каждого из возможных индексов. Во время извлечения условия, которые не могут быть использованы для построения условия диапазона, удаляются, условия, которые создают перекрывающиеся диапазоны, объединяются, а условия, которые создают пустые диапазоны, удаляются.

Рассмотрим следующее утверждение, где key1 — индексированный столбец, а nonkey — нет:

SELECT * FROM t1 WHERE
  (key1 < 'abc' AND (key1 LIKE 'abcde%' OR key1 LIKE '%b')) OR
  (key1 < 'bar' AND nonkey = 4) OR
  (key1 < 'uux' AND key1 > 'z');

Процесс извлечения для ключа key1 следующий:

Начать с исходного предложения WHERE:

(key1 < 'abc' AND (key1 LIKE 'abcde%' OR key1 LIKE '%b')) OR
(key1 < 'bar' AND nonkey = 4) OR
(key1 < 'uux' AND key1 > 'z')

Удалить nonkey = 4 и key1 LIKE '%b', потому что они не могут быть использованы для сканирования по диапазону. Правильный способ их удаления — заменить их на TRUE, чтобы не пропустить совпадающие строки при сканировании по диапазону. Замена их на TRUE даёт:
```
(key1 < 'abc' AND (key1 LIKE 'abcde%' OR TRUE)) OR
(key1 < 'bar' AND TRUE) OR
(key1 < 'uux' AND key1 > 'z')
```
Объединить условия, которые всегда истинны или ложны:
- (key1 LIKE 'abcde%' OR TRUE) всегда истинно
- (key1 < 'uux' AND key1 > 'z') всегда ложно
Замена этих условий константами даёт:
```
(key1 < 'abc' AND TRUE) OR (key1 < 'bar' AND TRUE) OR (FALSE)
```
Удаление ненужных TRUE и FALSE констант даёт:
```
(key1 < 'abc') OR (key1 < 'bar')
```
Объединение перекрывающихся интервалов в один даёт конечное условие для использования при сканировании по диапазону:
```
(key1 < 'bar')
```

В общем случае (как показано на предыдущем примере), условие, используемое для сканирования по диапазону, менее строгое, чем предложение WHERE. MySQL выполняет дополнительную проверку, чтобы отфильтровать строки, которые удовлетворяют условию диапазона, но не всему предложению WHERE.

Алгоритм извлечения условия диапазона может обрабатывать вложенные конструкции AND/OR произвольной глубины, а его результат не зависит от порядка, в котором условия появляются в предложении WHERE.

MySQL не поддерживает объединение нескольких диапазонов для метода доступа range для пространственных индексов. Чтобы обойти это ограничение, можно использовать UNION с идентичными утверждениями SELECT, за исключением того, что каждое пространственное предикат помещено в разное утверждение SELECT.

Метод доступа по диапазону для индексов из нескольких частей

Условие диапазона для индекса из нескольких частей является расширением условия диапазона для однокомпонентного индекса. Условие диапазона для индекса из нескольких частей ограничивает строки индекса значениями, попадающими в один или несколько интервалов кортежей ключей. Интервалы кортежей ключей определяются на множестве кортежей ключей с использованием порядка из индекса.

Например, рассмотрим многокомпонентный индекс, определенный как key1(key_part1, key_part2, key_part3), и следующий набор кортежей ключей, упорядоченных по ключам:

key_part1  key_part2  key_part3
  NULL       1          'abc'
  NULL       1          'xyz'
  NULL       2          'foo'
   1         1          'abc'
   1         1          'xyz'
   1         2          'abc'
   2         1          'aaa'

Условие key_part1 = 1 определяет этот интервал:

(1,-inf,-inf) <= (key_part1,key_part2,key_part3) < (1,+inf,+inf)

Интервал охватывает 4-й, 5-й и 6-й кортежи в предыдущем наборе данных и может быть использован методом доступа по диапазону.

В противоположность этому, условие key_part3 = 'abc' не определяет единый интервал и не может быть использовано методом доступа по диапазону.

Следующие описания более подробно показывают, как работают условия диапазона для многокомпонентных индексов.

Для индексов HASH каждый интервал, содержащий одинаковые значения, может быть использован. Это означает, что интервал может быть сгенерирован только для условий в следующем формате:
```
    key_part1 cmp const1
AND key_part2 cmp const2
AND ...
AND key_partN cmp constN;
```
Здесь const1, const2, … являются константами, cmp — один из =, <=> или IS NULL операторов сравнения, а условия охватывают все части индекса. (То есть, есть N условия, по одному для каждой части индекса из N частей.) Например, следующее является условием диапазона для трехкомпонентного индекса HASH:
```
key_part1 = 1 AND key_part2 IS NULL AND key_part3 = 'foo'
```
Для определения того, что считается константой, см. Метод доступа по диапазону для однокомпонентных индексов.
Для индекса BTREE интервал может быть использован для условий, объединённых с AND, где каждое условие сравнивает часть ключа со значением константы, используя =, <=>, IS NULL, >, <, >=, <=, !=, <>, BETWEEN или LIKE 'pattern' (где 'pattern' не начинается с подстановки). Интервал может быть использован, если возможно определить один кортеж ключа, содержащий все строки, соответствующие условию (или два интервала, если используется <> или !=).

Оптимизатор пытается использовать дополнительные части ключа для определения интервала, если оператор сравнения — =, <=> или IS NULL. Если оператор — >, <, >=, <=, !=, <>, BETWEEN или LIKE, оптимизатор использует его, но не учитывает больше частей ключа. Для следующего выражения оптимизатор использует = из первого сравнения. Он также использует >= из второго сравнения, но не учитывает дальнейшие части ключа и не использует третье сравнение для построения интервала:
```
key_part1 = 'foo' AND key_part2 >= 10 AND key_part3 > 10
```
Единый интервал:
```
('foo',10,-inf) < (key_part1,key_part2,key_part3) < ('foo',+inf,+inf)
```
Возможно, созданный интервал содержит больше строк, чем исходное условие. Например, предыдущий интервал включает значение ('foo', 11, 0), которое не удовлетворяет исходному условию.
Если условия, охватывающие наборы строк, содержащиеся внутри интервалов, объединяются с OR, они образуют условие, охватывающее набор строк, содержащихся в объединении их интервалов. Если условия объединяются с AND, они образуют условие, охватывающее набор строк, содержащихся в пересечении их интервалов. Например, для этого условия в индексе из двух частей:
```
(key_part1 = 1 AND key_part2 < 2) OR (key_part1 > 5)
```
Интервалы:
```
(1,-inf) < (key_part1,key_part2) < (1,2)
(5,-inf) < (key_part1,key_part2)
```
В этом примере интервал на первой строке использует одну часть ключа для левой границы и две части ключа для правой границы. Интервал на второй строке использует только одну часть ключа. Столбец key_len в выводе EXPLAIN указывает максимальную длину префикса ключа, используемого.

В некоторых случаях key_len может указывать, что использовалась часть ключа, но это может не соответствовать ожиданиям. Предположим, что key_part1 и key_part2 могут быть NULL. Тогда столбец key_len отображает две длины частей ключа для следующего условия:
```
key_part1 >= 1 AND key_part2 < 2
```
Но, на самом деле, условие преобразуется в это:
```
key_part1 >= 1 AND key_part2 IS NOT NULL
```

Для описания того, как выполняются оптимизации для объединения или исключения интервалов для условий диапазона в однокомпонентном индексе, см. Метод доступа по диапазону для однокомпонентных индексов. Аналогичные шаги выполняются для условий диапазона в многокомпонентных индексах.

Оптимизация диапазонов равенства для многозначных сравнений

Рассмотрим эти выражения, где col_name — индексированный столбец:

col_name IN(val1, ..., valN)
col_name = val1 OR ... OR col_name = valN

Каждое выражение истинно, если col_name равно одному из нескольких значений. Эти сравнения являются сравнениями диапазонов равенства (где «диапазон» — это одно значение). Оптимизатор оценивает стоимость чтения квалифицирующих строк для сравнений диапазонов равенства следующим образом:

Если есть уникальный индекс по col_name, оценка строк для каждого диапазона равна 1, так как не более одной строки может иметь данное значение.
В противном случае любой индекс по col_name является неуникальным, и оптимизатор может оценить количество строк для каждого диапазона, используя погружения в индекс или статистику индекса.

При погружениях в индекс оптимизатор выполняет погружение в каждом конце диапазона и использует количество строк в диапазоне в качестве оценки. Например, выражение col_name IN (10, 20, 30) имеет три диапазона равенства, и оптимизатор выполняет два погружения на каждый диапазон для генерации оценки строк. Каждая пара погружений дает оценку количества строк, имеющих данное значение.

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

Системная переменная eq_range_index_dive_limit позволяет настроить количество значений, при котором оптимизатор переключается с одной стратегии оценки строк на другую. Чтобы разрешить использование погружений в индекс для сравнений до N диапазонов равенства, установите eq_range_index_dive_limit на N + 1. Чтобы отключить использование статистики и всегда использовать погружения в индекс независимо от N, установите eq_range_index_dive_limit на 0.

Для обновления статистики индексов таблицы для получения лучших оценок используйте ANALYZE TABLE.

Даже в условиях, когда погружения в индекс в противном случае использовались, они пропускаются для запросов, удовлетворяющих всем этим условиям:

Наличие подсказки индекса single-index FORCE INDEX. Идея в том, что если использование индекса принудительно, то дополнительная накладная стоимость выполнения погружений в индекс не принесет никакой выгоды.
Индекс неуникальный и не является индексом FULLTEXT.
Отсутствует подзапрос.
Отсутствуют клаузы DISTINCT, GROUP BY или ORDER BY.

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

Оптимизация диапазонов для выражений с конструкторами строк

Оптимизатор может применить метод доступа по диапазону к запросам следующего вида:

SELECT ... FROM t1 WHERE ( col_1, col_2 ) IN (( 'a', 'b' ), ( 'c', 'd' ));

Ранее для использования сканирования по диапазону требовалось записать запрос следующим образом:

SELECT ... FROM t1 WHERE ( col_1 = 'a' AND col_2 = 'b' )
OR ( col_1 = 'c' AND col_2 = 'd' );

Для использования сканирования по диапазону запросы должны удовлетворять следующим условиям:

Используются только предикаты IN(), а не NOT IN().
В левой части предиката IN() конструктор строки содержит только ссылки на столбцы.
В правой части предиката IN() конструкторы строк содержат только константы времени выполнения, которые являются либо литералами, либо ссылками на локальные столбцы, привязанные к константам во время выполнения.
В правой части предиката IN() присутствует более одного конструктора строки.

Дополнительную информацию об оптимизаторе и конструкторах строк см. в Разделе 8.2.1.19, «Оптимизация выражений с конструкторами строк».

Ограничение использования памяти для оптимизации диапазонов

Для управления памятью, доступной оптимизатору диапазонов, используйте системную переменную range_optimizer_max_mem_size:

Значение 0 означает «без ограничения».
При значении больше 0 оптимизатор отслеживает потребление памяти при рассмотрении метода доступа по диапазону. Если указанное ограничение вот-вот будет превышено, метод доступа по диапазону отменяется, и вместо него рассматриваются другие методы, включая полное сканирование таблицы. Это может быть менее оптимальным. Если это произойдет, появляется следующее предупреждение (где N — текущее значение range_optimizer_max_mem_size):
```
Warning    3170    Memory capacity of N bytes for
                   'range_optimizer_max_mem_size' exceeded. Range
                   optimization was not done for this query.
```
Для операторов UPDATE и DELETE, если оптимизатор возвращается к полному сканированию таблицы, и системная переменная sql_safe_updates включена, возникает ошибка, а не предупреждение, потому что фактически не используется ключ для определения строк, которые необходимо изменить. Дополнительную информацию см. в Разделе «Использование режима безопасных обновлений (--safe-updates)».

Для отдельных запросов, превышающих доступную память для оптимизации диапазонов, и для которых оптимизатор возвращается к менее оптимальным планам, увеличение значения range_optimizer_max_mem_size может улучшить производительность.

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

Для простого запроса, такого как следующий, где есть один кандидатский ключ для метода доступа по диапазону, каждое предикат, объединённое с OR, использует приблизительно 230 байтов:
```
SELECT COUNT(*) FROM t
WHERE a=1 OR a=2 OR a=3 OR .. . a=N;
```
Аналогично для запроса, такого как следующий, каждое предикат, объединённое с AND, использует приблизительно 125 байтов:
```
SELECT COUNT(*) FROM t
WHERE a=1 AND b=1 AND c=1 ... N;
```
Для запроса с предикатами IN():
```
SELECT COUNT(*) FROM t
WHERE a IN (1,2, ..., M) AND b IN (1,2, ..., N);
```
Каждое значение литерала в списке IN() считается предикатом, объединённым с OR. Если есть два списка IN(), количество предикатов, объединенных с OR, равно произведению количества значений литералов в каждом списке. Таким образом, количество предикатов, объединённых с OR в предыдущем случае, равно M × N.

До версии 5.7.11 количество байтов на предикат, объединённый с OR, было выше, приблизительно 700 байтов.