Выбор и использование индексов MySQL

Первичный индекс

При построении первичного индекса необходимо учитывать несколько факторов:

  • INT + AUTO_INCREMENT — лучший выбор
  • использовать строки — плохо, много места и долгая обработка
  • MyISAM пакует индексы — еще медленнее для строк (до 6 раз)
  • InnoDB включает первичный индекс во вторичные — дополнительное место
  • в InnoDB первичный ключ — кластерный индекс по умолчанию
  • Случайные строки (MD5, SHA1) — медленные выборки и вставка (соседние записи не являются соседними в индексе)
  • Хранение UUID — удалить тире, еще лучше преобразовать в BINARY(16) с помощью UNHEX()

Виды индексов

  • Поиск элемента в хорошей хэш-таблице занимает О(1).
  • В хорошо сбалансированном дереве — O(log(n)).
  • В массиве — O(n).
  • Наилучшие алгоритмы сортировки имеют сложность O(n*log(n)).
  • Плохие алгоритмы сортировки — O(n2).

https://habrahabr.ru/company/mailru/blog/266811/

B-TREE

Возможности

B-TREE — основной используемый типа индекса. Поиск может выполняться:

  • по полному значению
  • по левостороннему префиксу, по первой колонке индекса
  • по интервалу значений (range), только для первой колонки
  • по фиксированному значению первой колонки (или нескольких) и интервалу на последующую

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

Ограничения

Для B-TREE индексов существуют и ограничения:

  • нельзя искать по суффиксу (имена, оканчивающиеся на определенную букву)
  • нельзя пропустить колонку в индексе
  • не учитываются колонки справа от сравнения с интервалом (date_of_birth):
WHERE last_name="Smith" AND
      first_name LIKE 'J%' AND
      date_of_birth = '1976-12-23'
  • IN (v1,v2,v3) тоже считается интервалом (range), но после него учитываются.

HASH

Особенности

Основное преимущество — очень быстрый поиск по полному значению индекса, но масса ограничений:

  • нельзя использовать для покрывающих индексов
  • нельзя использовать для поиска по префиксу
  • нельзя использовать для сортировки
  • не может использовать в выражениях <, >, только в =, IN, <>
  • не эффективен при частых коллизиях

Эмуляция через B-TREE

Предположим, у нас есть большой и медленный индекс по url:

SELECT id FROM url WHERE url="http://www.mysql.com";

Можно построить быстрый индекс по url_crc, индекса по url нет:

SELECT id FROM url WHERE url='http://www.mysql.com'
AND url_crc=CRC32('http://www.mysql.com');

Выборка ведется по url для разрешения коллизий.

Заполнение url_crc — триггер или слой модели. Внимательно выбираем хэш-функцию, SHA1, MD5 — слишком сложные и длинные.

crc32-trigger.sql
DELIMITER $$
CREATE TRIGGER `url_crc_fill` BEFORE INSERT ON `url`
  FOR EACH ROW BEGIN
    SET NEW.url_crc = CRC32(NEW.url);
  END $$
DELIMITER ;

Еще один пример для точного поиска по адресу:

DROP TRIGGET IF EXISTS `address_crc_fill_insert`;
DROP TRIGGET IF EXISTS `address_crc_fill_update`;
 
DELIMITER $$
CREATE TRIGGER `address_crc_fill_insert` BEFORE INSERT ON `MarketNavigator`
  FOR EACH ROW BEGIN
    SET NEW.FullAddressCRC = CRC32(NEW.FullAddress);
  END $$
 
CREATE TRIGGER `address_crc_fill_update` BEFORE UPDATE ON `MarketNavigator`
  FOR EACH ROW BEGIN
    IF NEW.FullAddress <> OLD.FullAddress THEN
      SET NEW.FullAddressCRC = CRC32(NEW.FullAddress);
    END IF;
  END $$
 
DELIMITER ;

Использование индексов

Принцип изолирования колонок

Индекс не используется, если колонка внутри выражения или вызова функции:

SELECT actor_id FROM actor WHERE actor_id + 1 = 5;
SELECT ... WHERE TO_DAYS(CURRENT_DATE) * TO_DAYS(date_col) <= 10;

Часто можно переписать запрос с учетом принципа изолирования колонок, тогда индексы используются:

SELECT actor_id FROM actor WHERE actor_id = 4;
SELECT ... WHERE date_col >= DATE_SUB(CURRENT_DATE, INTERVAL 10 DAY);

Префиксные индексы и селективность

Для длинных строк часто имеет смысл строить индекс по префиксу строки (а не по полному значению), уменьшая место и ускоряя обработку.

При этом важно не забывать о селективности:

selectivity = cardinality / общее количество значений
cardinality - количество различных значений

Длина префикса — компромисс между хорошей селективностью и занимаемым местом.

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

Кластеризованный индекс

Определяет физический порядок записей. В случае InnoDB это единая структура для хранения и индекса, и данных. В качестве кластеризованного индекса выбираются:

1. первичный ключ 2. первый уникальный ключ, если нет первичного 3. суррогатный первичный ключ в порядке добавления записей, если нет уникальных ключей

Все прочие созданные индексы ссылаются не на записи, а на значения кластеризованного индекса, это важная особенность InnoDB.

Преимущества

  • очень быстрая выборка по первичному ключу
  • эффективный поиск по интервалу первичного ключа
  • быстрая сортировка по первичному ключу
  • покрывающие индексы автоматически используют первичный ключ
  • быстрая вставка в порядке сортировки первичного ключа

Недостатки

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

Как правило, достоинства перевешивают недостатки.

Покрывающие (covering) индексы

MySQL может брать данные из индекса, не обращаясь к записи, в результате получаем значительное увеличение производительности:

  • меньше обрабатываемых данных
  • быстрее навигация по записям
  • лучшее кеширование
  • для InnoDB — нет дополнительного поиска по первичному ключу
CREATE INDEX store_film ON inventory(store_id, film_id, name);
 
SELECT store_id, film_id FROM inventory WHERE store_id = 1;
 
SELECT store_id, film_id
  FROM inventory
  WHERE store_id = 1 AND name LIKE 'Secret%';

Существуют ограничения:

  • работает только для B-TREE индексов
  • все запрашиваемые колонки должны быть в индексе
  • условие LIKE — только по префиксу (pattern%)

Например, в приведенном ниже запросе покрывающий индекс не используется: поле price не в индексе, LIKE не по префиксу:

SELECT store_id, film_id, price
  FROM store_film
  WHERE store_id = 1 AND
        name LIKE '%mission%';

Дублирующиеся и избыточные индексы

Дублирующиеся (dublicate) индексы — индексы по одним и тем же колонкам в том же порядке, всегда нужно оставлять только один.

Избыточные (redundant) индексы — если один индекс содержит другой: (A,B) и (A,B,C).

Прежде чем добавить новый индекс — смотрим, нельзя ли расширить старый, но возможны варианты:

(A INT, B INT) и (A INT, B INT, C VARCHAR)

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

Многокритериальные индексы

Если необходим поиск по форме, содержащей много полей:

CREATE INDEX search ON people(gender,eye_color,hair_color,city,age);

Работает с запросами gender, gender+country, gender+country+region. Но что делать с поиском по region+age?

Можно построить еще один индекс, однако большое количество индексов (по одному на каждую комбинацию) ­- плохо.

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

... WHERE eye_color IN('brown','blue','hazel')
    AND hair_color IN('black','red','blonde','brown')
    AND gender IN('M','F');

Сортировка по индексам

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

  • порядок колонок в индексе должен точно совпадать с ORDER BY
  • не работает для разнонаправленной сортировки (ASC/DESC) при нескольких колонках в ORDER BY
  • для JOIN — если ORDER BY содержит только колонки первой таблицы
  • левосторонняя префиксность, кроме случаев ограничения в WHERE по константе

Пример:

CREATE INDEX rental_date (rental_date,inventory_id,customer_id);
 
SELECT rental_id, staff_id FROM rental
  WHERE rental_date = '2005-05-25'
  ORDER BY inventory_id, customer_id;

Сортировка по индексу не работает в следующих случаях:

  • если колонка не в индексе:
... WHERE rental_date = '2005-05-25' ORDER BY inventory_id, staff_id;
  • различные направления сортировки:
... WHERE rental_date = '2005-05-25' ORDER BY inventory_id DESC, customer_id ASC;
  • если нарушение префиксности:
... WHERE rental_date = '2005-05-25' ORDER BY customer_id;
  • если интервал по первой колонке индекса, то остальные не используются:
... WHERE rental_date > '2005-05-25' ORDER BY inventory_id, customer_id;
          AND hair_color IN('black','red','blonde','brown')
          AND gender IN('M','F');

Порядок следования полей в индексе

При построении индекса в большинстве случаев можно придерживаться следующего принципа:

  • сначала колонки, по которым делается выборка по значению, в порядке убывания селективности
  • потом колонка, по которой делается выборка по интервалу
CREATE INDEX ON employees(department_id, education_type, gender, age);
                          ^              ^               ^       ^
SELECTIVITY:              10             3               2       20

В тексте WHERE порядок следования условий как правило не играет роли, оптимизатор запросов достаточно умный.

В SORT — еще как влияет, поэтому нужно еще и учитывать наиболее частые сортировки.