Составные (комбинированные) индексы

Урок о составных индексах

Этот документ начинается с чего-то тривиального и, возможно, скучного, но в конечном итоге содержит более интересную информацию, возможно, вы не знали о том, как работают индексы в MariaDB и MySQL.

Также здесь объясняется (в определенной степени) оператор EXPLAIN.

(Большая часть этого также относится и к другим базам данных.)

Запрос для обсуждения

Вопрос: «Когда Эндрю Джонсон был президентом США?»

Доступная таблица `Presidents` выглядит следующим образом:

+-----+------------+----------------+-----------+
| seq | last_name  | first_name     | term      |
+-----+------------+----------------+-----------+
|   1 | Washington | George         | 1789-1797 |
|   2 | Adams      | John           | 1797-1801 |
...
|   7 | Jackson    | Andrew         | 1829-1837 |
...
|  17 | Johnson    | Andrew         | 1865-1869 |
...
|  36 | Johnson    | Lyndon B.      | 1963-1969 |
...

(«Эндрю Джонсон» был выбран для этого урока из-за дубликатов.)

Какие индексы (или индекс) были бы лучшими для этого вопроса? Более конкретно, что было бы лучше для

    SELECT  term
        FROM  Presidents
        WHERE  last_name = 'Johnson'
          AND  first_name = 'Andrew';

Некоторые индексы для тестирования:

• Без индексов
• INDEX(first_name), INDEX(last_name) (два отдельных индекса)
• «Объединение индексов по пересечению»
• INDEX(last_name, first_name) (составной индекс)
• INDEX(last_name, first_name, term) (покрывающий индекс)
• Варианты

Без индексов

Ну, я немного лукавлю. У меня есть PRIMARY KEY на `seq`, но это не приносит никакой пользы в изучаемом нами запросе.

SHOW CREATE TABLE Presidents \G
CREATE TABLE `presidents` (
  `seq` tinyint(3) unsigned NOT NULL AUTO_INCREMENT,
  `last_name` varchar(30) NOT NULL,
  `first_name` varchar(30) NOT NULL,
  `term` varchar(9) NOT NULL,
  PRIMARY KEY (`seq`)
) ENGINE=InnoDB AUTO_INCREMENT=45 DEFAULT CHARSET=utf8

EXPLAIN  SELECT  term
   FROM  Presidents
   WHERE  last_name = 'Johnson'
   AND  first_name = 'Andrew';
+----+-------------+------------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table      | type | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+------------+------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | Presidents | ALL  | NULL          | NULL | NULL    | NULL |   44 | Using where |
+----+-------------+------------+------+---------------+------+---------+------+------+-------------+

# Or, using the other form of display:  EXPLAIN ... \G
           id: 1
  select_type: SIMPLE
        table: Presidents
         type: ALL        <-- Implies table scan
possible_keys: NULL
          key: NULL       <-- Implies that no index is useful, hence table scan
      key_len: NULL
          ref: NULL
         rows: 44         <-- That's about how many rows in the table, so table scan
        Extra: Using where

Детали реализации

Сначала опишем, как InnoDB хранит и использует индексы.

• Данные и PRIMARY KEY «кластеризованы» вместе в одном B-дереве.
• Поиск по B-дереву довольно быстрый и эффективный. Для таблицы с миллионом строк может быть 3 уровня B-дерева, а два верхних уровня, вероятно, находятся в кэше.
• Каждый вторичный индекс находится в другом B-дереве, с PRIMARY KEY на листьях.
• Получение «последовательных» (согласно индексу) элементов из B-дерева очень эффективно, поскольку они хранятся последовательно.
• Для простоты, мы можем считать каждый поиск по B-дереву как 1 единицу работы и игнорировать сканирование последовательных элементов. Это приблизительно соответствует количеству обращений к диску для большой таблицы в загруженной системе.

Для MyISAM PRIMARY KEY не хранится вместе с данными, поэтому можно считать его вторичным ключом (упрощенно).

INDEX(first_name), INDEX(last_name)

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

MariaDB редко использует более одного индекса за раз в запросе. Поэтому она проанализирует возможные индексы.

• first_name — 2 возможные строки (один поиск по B-дереву, затем последовательное сканирование)
• last_name — 2 возможные строки Предположим, она выбирает last_name. Вот шаги для выполнения SELECT: 1. Используя INDEX(last_name), найдите 2 записи индекса с last_name = 'Johnson'. 2. Получите PRIMARY KEY (неявный добавление в каждый вторичный индекс в InnoDB); получите (17, 36). 3. Доступ к данным с seq = (17, 36), чтобы получить строки для Эндрю Джонсона и Линдона Б. Джонсона. 4. Используйте остальную часть условия WHERE, чтобы отфильтровать все, кроме необходимой строки. 5. Выведите результат (1865-1869).

EXPLAIN  SELECT  term
  FROM  Presidents
  WHERE  last_name = 'Johnson'
  AND  first_name = 'Andrew'  \G
  select_type: SIMPLE
        table: Presidents
         type: ref
possible_keys: last_name, first_name
          key: last_name
      key_len: 92                 <-- VARCHAR(30) utf8 may need 2+3*30 bytes
          ref: const
         rows: 2                  <-- Two 'Johnson's
        Extra: Using where

«Объединение индексов по пересечению»

Хорошо, вы становитесь очень умными и решаете, что MariaDB должна достаточно умно использовать оба индекса имен для получения ответа. Это называется «пересечение». 1. Используя INDEX(last_name), найдите 2 записи индекса с last_name = 'Johnson'; получите (7, 17) 2. Используя INDEX(first_name), найдите 2 записи индекса с first_name = 'Andrew'; получите (17, 36) 3. «Пересеките» два списка (7,17) & (17,36) = (17) 4. Доступ к данным с seq = (17), чтобы получить строку для Эндрю Джонсона. 5. Выведите результат (1865-1869).

           id: 1
  select_type: SIMPLE
        table: Presidents
         type: index_merge
possible_keys: first_name,last_name
          key: first_name,last_name
      key_len: 92,92
          ref: NULL
         rows: 1
        Extra: Using intersect(first_name,last_name); Using where

EXPLAIN не предоставляет подробных данных о количестве строк, полученных из каждого индекса, и т. д.

INDEX(last_name, first_name)

Это называется составным (или комбинированным) индексом, так как он содержит более одного столбца. 1. Пройдите по B-дереву для индекса, чтобы получить ровно строку индекса для Johnson+Andrew; получите seq = (17). 2. Доступ к данным с seq = (17), чтобы получить строку для Эндрю Джонсона. 3. Выведите результат (1865-1869). Это намного лучше. В действительности, это обычно «лучшее» решение.

    ALTER TABLE Presidents
        (drop old indexes and...)
        ADD INDEX compound(last_name, first_name);

           id: 1
  select_type: SIMPLE
        table: Presidents
         type: ref
possible_keys: compound
          key: compound
      key_len: 184             <-- The length of both fields
          ref: const,const     <-- The WHERE clause gave constants for both
         rows: 1               <-- Goodie!  It homed in on the one row.
        Extra: Using where

Покрывающий: INDEX(last_name, first_name, term)

Удивительно! Мы можем сделать еще немного лучше. Покрывающий индекс — это тот, в котором _все_ поля SELECT находятся в индексе. Он имеет дополнительный бонус — не нужно обращаться к «данным», чтобы завершить задачу. 1. Пройдите по B-дереву для индекса, чтобы получить ровно строку индекса для Johnson+Andrew; получите seq = (17). 2. Выведите результат (1865-1869). B-дерево «данных» не используется; это улучшение по сравнению с «составным» индексом.

    ... ADD INDEX covering(last_name, first_name, term);

           id: 1
  select_type: SIMPLE
        table: Presidents
         type: ref
possible_keys: covering
          key: covering
      key_len: 184
          ref: const,const
         rows: 1
        Extra: Using where; Using index   <-- Note

Все аналогично использованию «составного», за исключением добавления «Использование индекса».

Варианты

• Что произойдет, если вы переставите поля в условии WHERE? Ответ: Порядок элементов AND не имеет значения.
• Что произойдет, если вы переставите поля в индексе? Ответ: Это может сильно повлиять. Об этом чуть позже.
• Что, если есть дополнительные поля в конце? Ответ: Минимальный вред; возможно, большая польза (например, «покрытие»).
• Избыточность? То есть, что если у вас есть оба этих индекса: INDEX(a), INDEX(a,b)? Ответ: Избыточность требует затрат при вставках; для запросов SELECT она редко полезна.
• Префикс? То есть, INDEX(last_name(5), first_name(5)) Ответ: Не стоит этого делать; это редко помогает и часто вредит. (Подробности — это другая тема.)

Дополнительные примеры:

    INDEX(last, first)
    ... WHERE last = '...' -- good (even though `first` is unused)
    ... WHERE first = '...' -- index is useless

    INDEX(first, last), INDEX(last, first)
    ... WHERE first = '...' -- 1st index is used
    ... WHERE last = '...' -- 2nd index is used
    ... WHERE first = '...' AND last = '...' -- either could be used equally well

    INDEX(last, first)
    Both of these are handled by that one INDEX:
    ... WHERE last = '...'
    ... WHERE last = '...' AND first = '...'

    INDEX(last), INDEX(last, first)
    In light of the above example, don't bother including INDEX(last).

Postlog

Обновлено — окт. 2012; больше ссылок — ноя. 2016

См. также

• Кулинарная книга по проектированию лучшего индекса для SELECT
• Обсуждение индексов от Sheeri
• Слайды об EXPLAIN
• Страница руководства MySQL по оптимизации диапазонов в составных индексах
• Накладные расходы составных индексов
• Размер и другие ограничения индексов

Рик Джеймс любезно разрешил нам использовать эту статью в базе знаний.

Сайт Рика Джеймса содержит другие полезные советы, инструкции, оптимизации и рекомендации по отладке.

Исходный источник: http://mysql.rjweb.org/doc.php/index1