MySQL-индексы для чайников

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

Начну с того, что часто вижу ошибки, связанные с созданием индексов в MySQL. Многие разработчики (и не только новички в MySQL) создают много индексов на тех колонках, которые будут использовать в выборках, и считают это оптимальной стратегией. Например, если мне нужно выполнить запрос типа AGE=18 AND STATE=’CA’, то многие люди просто создадут 2 отдельных индекса на колонках AGE и STATE.

Намного лучшей (здесь и далее прим. переводчика: а обычно и единственной верной) стратегией является создание комбинированного индекса вида (AGE,STATE). Давайте рассмотрим почему это так.

Обычно (но не всегда) индексы в MySQL являются BTREE-индексами — такой тип индекса способна быстро просматривать информацию, содержащуюся в своих префиксах, и перебирать диапазоны отсортированных значений. Например, когда Вы запрашиваете AGE = 18 с BTREE-индексом по колонке AGE MySQL найдёт в таблице первую отвечающую запросу строку и продолжит поиск до тех пор, пока не найдёт первую неподходящую строку — тогда он останавливает поиск, т.к. считает, что дальше ничего подходящего не будет. Диапазоны, например запросы вида BETWEEN 18 AND 20, работают сходным образом — MySQL останавливается на других значениях.

Несколько сложнее ситуация с запросами типа AGE IN (18,20,30), т.к. на самом деле MySQL приходится несколько раз проходить по индексу.

Итак, мы обсудили как MySQL ищет по индексу, но не определили что же он возвращает после поиска — обычно (если речь не идёт о покрывающих (covering) индексах) получает «указатель строки», который может быть значением первичного ключа (если используется движок InnoDB), физическое смещение в файле (для MyISAM) или что-нибудь в этом роде. Важно, что внутренний движок MySQL может по этому указателю найти полную строку со всеми необходимыми данными, отвечающими заданному значению индекса.

А какие есть варианты у MySQL, если Вы создали два отдельных индекса? Он может либо использовать только один из них, чтобы отобрать подходящие строки (а потом отфильтровать извлечённые данные, руководствуясь WHERE — но уже без использования индексов), либо может получить указатели на строки от всех подходящих индексов и вычислить их пересечение, а затем уже вернуть данные.

Какой из способов будет более подходящим зависит от избирательности и корреляции индексов. Если после отработки WHERE по первой колонке будет отобрано 5% строк, а применение далее WHERE по второй колонке отфильтровывает строки до 1% от общего количества, то применение пересечений, конечно, имеет смысл. Но если второй WHERE отфильтрует только до 4.5%, то обычно значительно выгоднее использовать только первый индекс и отфильтровать ненужные нас строки после извлечения данных.

Давайте рассмотрим несколько примеров:

CREATE TABLE ‘idxtest’ (
‘i1’ int(10) UNSIGNED NOT NULL,
‘i2’ int(10) UNSIGNED NOT NULL,
‘val’ varchar(40) DEFAULT NULL,
KEY ‘i1’ (‘i1’),
KEY ‘i2’ (‘i2’),
KEY ‘combined’ (‘i1′,’i2’)
) ENGINE=MyISAM DEFAULT CHARSET=latin1

Я создал колонки i1 и i2 независимыми друг от друга, причём каждая из них отбирает около 1% строк в таблице, которая содержит в общей сложности 10 млн. записей.

mysql> EXPLAIN SELECT avg(length(val)) FROM idxtest WHERE i1=50 AND i2=50;

+—-+————-+———+——+—————-+———-+———+————-+——+——-+
| id | select_type | TABLE | type | possible_keys | KEY | key_len | ref | rows | Extra
+—-+————-+———+——+—————-+———-+———+————-+——+——-+
| 1 | SIMPLE | idxtest | ref | i1,i2,combined | combined | 8 | const,const | 665 |
+—-+————-+———+——+—————-+———-+———+————-+——+——-+
1 row IN SET (0.00 sec)

Как Вы можете видеть MySQL предпочёл использовать комбинированный индекс, и запрос выполнился меньше, чем за 10 мс!

А теперь предположим, что у нас есть индекс только по отдельным колонкам (сказать оптимизатору игнорировать комбинированный индекс):

mysql> EXPLAIN SELECT avg(length(val)) FROM idxtest IGNORE INDEX (combined) WHERE i1=50 AND i2=50;

+—-+————-+———+————-+—————+——-+———+——+——+————————————-+
| id | select_type | TABLE | type | possible_keys | KEY | key_len | ref | rows | Extra
+—-+————-+———+————-+—————+——-+———+——+——+————————————-+
| 1 | SIMPLE | idxtest | index_merge | i1,i2 | i1,i2 | 4,4 | NULL | 1032 | USING intersect(i1,i2); USING WHERE
+—-+————-+———+————-+—————+——-+———+——+——+————————————-+
1 row IN SET (0.00 sec)

Как Вы можете видеть в данном случае MySQL выполнил поиск пересечений индексов, а на выполнение запроса понадобилось 70 мс — в 7 раз дольше!

Теперь давайте посмотрим, что будет, если использовать только один индекс и отфильтровывать полученные данные:

mysql> EXPLAIN SELECT avg(length(val)) FROM idxtest IGNORE INDEX (combined,i2) WHERE i1=50 AND i2=50;

+—-+————-+———+——+—————+——+———+——-+———+————-+
| id | select_type | TABLE | type | possible_keys | KEY | key_len | ref | rows | Extra
+—-+————-+———+——+—————+——+———+——-+———+————-+
| 1 | SIMPLE | idxtest | ref | i1 | i1 | 4 | const | 106222 | USING WHERE
+—-+————-+———+——+—————+——+———+——-+———+————-+
1 row IN SET (0.00 sec)

На этот раз MySQL пришлось обойти значительно больше строк, а выполнение запроса заняло 290 мс. Таким образом мы видим, что использование пересечения индексов намного лучше, чем использование одного индекса, но значительно лучше использовать комбинированные индексы.

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

mysql> EXPLAIN SELECT avg(length(val)) FROM idxtest IGNORE INDEX (combined) WHERE i1=50 AND i2 IN (49,50);

+—-+————-+———+——+—————+——+———+——-+———+————-+
| id | select_type | TABLE | type | possible_keys | KEY | key_len | ref | rows | Extra
+—-+————-+———+——+—————+——+———+——-+———+————-+
| 1 | SIMPLE | idxtest | ref | i1,i2 | i1 | 4 | const | 106222 | USING WHERE
+—-+————-+———+——+—————+——+———+——-+———+————-+
1 row IN SET (0.00 sec)

Как только запрос по одной из колонок становится не сравнением, а перечислением, MySQL больше не сможет использовать пересечение индексов, несмотря на то, что в данном случае при запросе i2 IN (49,50) это было бы более, чем разумно, т.к. запрос остаётся достаточно селективным.

Теперь давайте проведём ещё один тест. Я очистил таблицу и вновь наполнил её данными таким образом, чтобы значения в i1 и i2 сильно коррелировали. На самом деле они теперь вообще равны:

mysql> UPDATE idxtest SET i2=i1;

Query OK, 10900996 rows affected (6 min 47.87 sec)
Rows matched: 11010048 Changed: 10900996 Warnings: 0

Давайте посмотрим, что произойдёт в этом случае:

mysql> EXPLAIN SELECT avg(length(val)) FROM idxtest WHERE i1=50 AND i2=50;

+—-+————-+———+————-+—————-+——-+———+——+——+————————————-+
| id | select_type | TABLE | type | possible_keys | KEY | key_len | ref | rows | Extra
+—-+————-+———+————-+—————-+——-+———+——+——+————————————-+
| 1 | SIMPLE | idxtest | index_merge | i1,i2,combined | i2,i1 | 4,4 | NULL | 959 | USING intersect(i2,i1); USING WHERE
+—-+————-+———+————-+—————-+——-+———+——+——+————————————-+
1 row IN SET (0.00 sec)

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

Это произошло из-за того, что MySQL считает значения в колонках i1 и i2 независимыми, и потому выбирает пересечение индексов. На самом деле он не может предположить другого, т.к. никакой статистики о корреляции значений в колонках у него нет.

mysql> EXPLAIN SELECT avg(length(val)) FROM idxtest IGNORE INDEX(i2) WHERE i1=50 AND i2=50;

+—-+————-+———+——+—————+——+———+——-+———+————-+
| id | select_type | TABLE | type | possible_keys | KEY | key_len | ref | rows | Extra
+—-+————-+———+——+—————+——+———+——-+———+————-+
| 1 | SIMPLE | idxtest | ref | i1,combined | i1 | 4 | const | 106222 | USING WHERE
+—-+————-+———+——+—————+——+———+——-+———+————-+
1 row IN SET (0.00 sec)

А теперь, когда мы запретили MySQL использовать индекс по колонке i2 (а значит он не может и найти пересечение индексов), он использует индекс по одной колонке, а не комбинированный. Произошло так потому, что у MySQL есть статистика о примерном количестве подходящих строк, и так как оно равно для обоих индексов, то MySQL выбрал меньший по размеру. Выполнение запроса опять заняло 290 мс — в точности столько же, сколько и в прошлый раз.

Заставим MySQL использовать только combined индекс:

mysql> EXPLAIN SELECT avg(length(val)) FROM idxtest IGNORE INDEX(i1,i2) WHERE i1=50 AND i2=50;

+—-+————-+———+——+—————+———-+———+————-+———+——-+
| id | select_type | TABLE | type | possible_keys | KEY | key_len | ref | rows | Extra
+—-+————-+———+——+—————+———-+———+————-+———+——-+
| 1 | SIMPLE | idxtest | ref | combined | combined | 8 | const,const | 121137 |
+—-+————-+———+——+—————+———-+———+————-+———+——-+
1 row IN SET (0.00 sec)

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

Из-за того, что используемый комбинированный индекс больше, чем индекс по одной колонке, выполнение запроса заняло 300 мс.

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

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

Наконец, давайте рассмотрим ситуацию, когда процедура нахождения пересечения индексов работает значительно лучше, чем комбинированные индексы по нескольким колонкам. Речь идёт о случае, когда мы используете OR при выборке между колонками. В этом случае комбинированный индекс становится совершенно бесполезным, и у MySQL есть выбор между полным сканированием таблицы (FULL SCAN) и выполнением объединения (UNION) значений вместо поиска пересечения на данных, которые он получил из одной таблице.

Я вновь изменил взначения в столбцах i1 и i2 таким образом, чтобы в них содержались независимые данные (типичная ситуация для таблиц).

mysql> EXPLAIN SELECT avg(length(val)) FROM idxtest WHERE i1=50 OR i2=50;

+—-+————-+———+————-+—————-+——-+———+——+———+———————————+
| id | select_type | TABLE | type | possible_keys | KEY | key_len | ref | rows | Extra
+—-+————-+———+————-+—————-+——-+———+——+———+———————————+
| 1 | SIMPLE | idxtest | index_merge | i1,i2,combined | i1,i2 | 4,4 | NULL | 203803 | USING union(i1,i2); USING WHERE
+—-+————-+———+————-+—————-+——-+———+——+———+———————————+
1 row IN SET (0.00 sec)

Такой запросы выполняется 660 мс. Отключив индекс по второй колонке мы получим FULL SCAN:

mysql> EXPLAIN SELECT avg(length(val)) FROM idxtest IGNORE INDEX(i2) WHERE i1=50 OR i2=50;

+—-+————-+———+——+—————+——+———+——+———-+————-+
| id | select_type | TABLE | type | possible_keys | KEY | key_len | ref | rows | Extra
+—-+————-+———+——+—————+——+———+——+———-+————-+
| 1 | SIMPLE | idxtest | ALL | i1,combined | NULL | NULL | NULL | 11010048 | USING WHERE
+—-+————-+———+——+—————+——+———+——+———-+————-+
1 row IN SET (0.00 sec)

Обратите внимание, что MySQL указал ключи i1,combined как возможные к использованию, однако на самом деле такой возможности у него нет. Выполнение такого запросы занимает 3370 мс!

Также обратите внимание на то, что выполнение запроса заняло в 5 раз больше времени несмотря на то, что FULL SCAN прошёл примерно в 50 раз больше строк. Это показывает очень большую разницу в производительности между полным проходом по таблице и доступе по ключу, который занимает в 10 раз больше времени (в смысле «стоимости» доступа на строку), несмотря на то, что выполняется в памяти.

В случае UNION оптизатор действует более продвинуто и вполне способен справится с диапазонами:

mysql> EXPLAIN SELECT avg(length(val)) FROM idxtest WHERE i1=50 OR i2 IN (49,50);

+—-+————-+———+————-+—————-+——-+———+——+———+—————————————+
| id | select_type | TABLE | type | possible_keys | KEY | key_len | ref | rows | Extra
+—-+————-+———+————-+—————-+——-+———+——+———+—————————————+
| 1 | SIMPLE | idxtest | index_merge | i1,i2,combined | i1,i2 | 4,4 | NULL | 299364 | USING sort_union(i1,i2); USING WHERE
+—-+————-+———+————-+—————-+——-+———+——+———+—————————————+
1 row IN SET (0.00 sec)

Подводя итоги

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

Все индексы MySQL (PRIMARY, UNIQUE, и INDEX) хранятся в виде B-деревьев. Строки автоматически сжимаются с удалением пробелов в префиксах и оконечных пробелов (see Раздел 6.5.7, «Синтаксис оператора CREATE INDEX»).
Индексы используются для того, чтобы:

  • Быстро найти строки, соответствующие выражению WHERE.
  • Извлечь строки из других таблиц при выполнении объединений.
  • Найти величины MAX() или MIN() для заданного индексированного столбца. Эта операция оптимизируется препроцессором, который проверяет, не используете ли вы WHERE key_part_4 = константа, по всем частям составного ключа < N. В этом случае MySQL сделает один просмотр ключа и заменит выражение константой MIN(). Если все выражения заменяются константой, запрос моментально вернет результат:

SELECT MIN(key_part2),MAX(key_part2) FROM table_name where key_part1=10

  • Производить сортировку или группирование в таблице, если эти операции делаются на крайнем слева префиксе используемого ключа (например ORDER BY key_part_1,key_part_2). Если за всеми частями ключа следует DESC, то данный ключ читается в обратном порядке (see Раздел 5.2.7, «Как MySQL оптимизирует ORDER BY»).
  • В некоторых случаях запрос можно оптимизировать для извлечения величин без обращения к файлу данных. Если все используемые столбцы в некоторой таблице являются числовыми и образуют крайний слева префикс для некоторого ключа, то чтобы обеспечить большую скорость, искомые величины могут быть извлечены непосредственно из индексного дерева:

SELECT key_part3 FROM table_name WHERE key_part1=1

Предположим, что вызывается следующий оператор SELECT:

mysql> SELECT * FROM tbl_name WHERE col1=val1 AND col2=val2;

Если по столбцам col1 и col2 существует многостолбцовый индекс, то соответствующие строки могут выбираться напрямую. В случае, когда по столбцам col1 и col2 существуют раздельные индексы, оптимизатор пытается найти наиболее ограничивающий индекс путем определения, какой индекс найдет меньше строк, и использует данный индекс для выборки этих строк.
Если данная таблица имеет многостолбцовый индекс, то любой крайний слева префикс этого индекса может использоваться оптимизатором для нахождения строк. Например, если имеется индекс по трем столбцам (col1,col2,col3), то существует потенциальная возможность индексированного поиска по (col1), (col1,col2) и (col1,col2,col3).
В MySQL нельзя использовать частичный индекс, если столбцы не образуют крайний слева префикс этого индекса. Предположим, что имеются команды SELECT, показанные ниже:

mysql> SELECT * FROM tbl_name WHERE col1=val1;
mysql> SELECT * FROM tbl_name WHERE col2=val2;
mysql> SELECT * FROM tbl_name WHERE col2=val2 AND col3=val3;
mysql> SELECT * FROM tbl_name WHERE col1=val1 AND col2=val2;

Если индекс существует по (col1,col2,col3), то только первый и четвертый показанные выше запросы использует данный индекс. Второй и третий запросы действительно включают индексированные столбцы, но (col2) и (col2,col3) не являются крайней слева частью префиксов (col1,col2,col3).

*при этом, индексы будут работать не зависимо от типа индекса, т.е. и тип индекса: INDEX и тип индекса UNIQUE отработают очень быстро.

MySQL применяет индексы также для сравнений LIKE, если аргумент в выражении LIKE представляет собой постоянную строку, не начинающуюся с символа-шаблона. Например, следующие команды SELECT используют индексы:

mysql> SELECT * FROM tbl_name WHERE key_col LIKE «Patrick%»;
mysql> SELECT * FROM tbl_name WHERE key_col LIKE «Pat%_ck%»;

В первой команде рассматриваются только строки с «Patrick» <= key_col < «Patricl», а во второй — только строки с «Pat» <= key_col < «Pau».

Следующие команды SELECT не будут использовать индексы:

mysql> SELECT * FROM tbl_name WHERE key_col LIKE «%Patrick%»;
mysql> SELECT * FROM tbl_name WHERE key_col LIKE other_col;

В первой команде величина LIKE начинается с шаблонного символа. Во второй команде величина LIKE не является константой.

В версии MySQL 4.0 производится другая оптимизация на выражении LIKE. Если используется выражение … LIKE «%string%» и длина строки (string) больше, чем 3 символа, то MySQL будет применять алгоритм Турбо Бойера-Мура для инициализации шаблона для строки и затем использовать этот шаблон, чтобы выполнить поиск быстрее.

При поиске с использованием column_name IS NULL будут использоваться индексы, если column_name является индексом.

MySQL обычно использует тот индекс, который находит наименьшее количество строк. Индекс применяется для столбцов, которые сравниваются с помощью следующих операторов: =, >, >=, <, <=, BETWEEN и LIKE с префиксом, не содержащим шаблонного символа, такого как something%.

Если индекс не охватывает все уровни AND в выражении WHERE, то он не применяется для оптимизации данного запроса. Другими словами: чтобы индекс можно было использовать, префикс этого индекса должен входить в каждую группу AND.

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

… WHERE index_part1=1 AND index_part2=2 AND other_column=3
… WHERE index=1 OR A=10 AND index=2 /* индекс = 1 ИЛИ индекс = 2 */
… WHERE index_part1=’hello’ AND index_part_3=5
/* оптимизировано как «index_part1=’hello’» */
… WHERE index1=1 and index2=2 or index1=3 and index3=3;
/* Можно использовать индекс по index1, но не по index2 или index 3 */
Следующие выражения WHERE не используют индексы:
… WHERE index_part2=1 AND index_part3=2
/* index_part_1 не используется */
… WHERE index=1 OR A=10
/* Индекс не используется в обеих частях AND */
… WHERE index_part1=1 OR index_part2=10
/* Нет индекса, покрывающего все строки*/

В некоторых случаях MySQL не использует индекс, даже если это возможно. Несколько примеров таких ситуаций приведено ниже:

Если использование индекса требует от MySQL прохода более чем по 30% строк в данной таблице (в таких случаях просмотр таблицы, по всей видимости, окажется намного быстрее, так как потребуется выполнить меньше операций поиска). Следует учитывать, что если подобный запрос использует LIMIT по отношению только к извлекаемой части строк, то MySQL будет применять индекс в любом случае, так как небольшое количество строк можно найти намного быстрее, чтобы вернуть результат.