tl;dr В этой статье мы рассмотрим случай, когда лучше переместить самый селективный атрибут из префикса составного индекса в суффикс.

А также рассмотрим, что такое pipeline и как с его помощью select-ить данные уже отсортированными.

Описание предметной области

Есть логгер событий в системе X. Нужно сделать приложение для просмотра данных логов из этой системы.

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

Есть три типа сообщений:

• notice — нотификация,
• warning – предупреждение,
• error — кранты.

Таблица логов:

create table `log` (
    `message` text not null,
    `datetime` datetime not null,
    `type` enum('notice', 'warning', 'error') not null default 'notice'
);
create index `datetime_message` on `log`(`datetime`, `message`(150));

В таблице 10 миллионов записей. datetime уникален всегда, а вот поле message имеет всего 10к уникальных полей.

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

delimiter //
create procedure `generate_logs`(`amount` int, `amountOfUniqueMessages` int)
not deterministic
modifies sql data
sql security invoker
begin
    declare i int default 1;
    set @datetime = cast(current_date as datetime) - interval 9 year;

    -- проверка входных параметров
    input_params: begin    
        if (amount <= 0 or amountOfUniqueMessages <= 0) then 
            leave input_params; -- покидаем процедуру
        end if;
    end;

    start transaction;
    -- вставляем [amountOfUniqueMessages] уникальных сообщений с уникальным datetime 
    -- уникальность у сообщений достигается добавлением остатка от деления,
    -- а у datetime делается interval-ом
    while i < amount DO
        set @message = concat('message ', i % amountOfUniqueMessages);
        insert into `log`(`message`, `datetime`) values 
            (@message, @datetime + interval i second);
    end while;

    commit;
end;
//
delimiter ;

Реализация

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

select `message`, `datetime` from `log`
    where `datetime` >= '2017-04-01 00:00:00'
        and `datetime` < '2017-04-02 00:00:00'
    order by `datetime`;

upd: спасибо VolCh за совет с датами, исправил <= '2017-04-01 23:59:59' на < '2017-04-02 00:00:00'. Подробнее в комментариях к посту.

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

Explain этого запроса показывает хорошие результаты:

           id: 1
  select_type: SIMPLE
        table: log
   partitions: NULL
         type: range
possible_keys: datetime_message
          key: datetime_message
      key_len: 5
          ref: NULL
         rows: 172242
     filtered: 100.00
        Extra: Using index condition

Затронуто 172к полей. Это вполне ожидаемый результат при том условии, что данные генерировались так, будто логгер каждую секунду что-то пишет в БД.

Order by asc/desc

Отмечу, что даже если сортировка будет по убыванию (descending), то всё равно данные fetch-ятся уже отсортированными, и их не надо сортировать filesort–ом:

• Запрос с order by ... descending:
  

  select `message`, `datetime` from `log`
  where `datetime` >= '2009-03-24 00:00:00'
      and `datetime` < '2009-03-25 00:00:00'
  order by `datetime` desc;

• Его explain:
  

         id: 1
  select_type: SIMPLE
      table: log
  partitions: NULL
       type: range
  possible_keys: datetime_message
        key: datetime_message
    key_len: 5
        ref: NULL
       rows: 172242
   filtered: 100.00
      Extra: Using index condition

Без filesort–а и без temporary. Всё точно также, как и в первом случае.
Сиё явление называют pipeline, за то, что данные хранятся как бы связанными по цепочке, один за другим. И можно вытянуть все значения, начиная как с начального звена (order by asc), так и с конечного (desc).

Чтобы понять, как отсортирован message в составном индексе, можно представить себе школьные классы. Школьники в каждом классе отсортированы от а до я:

Если select-ить всех школьников из 1 "а", то они возвратятся уже отсортированными без использования filesort или temporary; неважно что использовалось, ascending или descending:

select `surname` from `schoolkids`
    where `class` = '1' and `liter` = 'а';

вернёт

Однако стоит только нам взять всех школьников из обоих классов и отсортировать их, как explain тут же выдаст зловещий Using filesort или Using temporary:

select `surname` from `schoolkids`
    where `class` = '1' and `liter` in ('а', 'б')
    order by `surname`

Произошло это очевидно потому, что значения уже не могут быть взяты по pipeline-у, поэтому СУБД нужно сортировать их самостоятельно.

Посмотрим на ещё один пример: нужно отсортировать предыдущий запрос по message. При этом атрибут уже отсортирован, но уже относительно префикса индекса, т.е. относительно datetime.

select `message`, `datetime` from `log`
    where `datetime` >= '2009-03-24 00:00:00'
        and `datetime` < '2009-03-25 00:00:00'
    order by `message` desc;

Explain:

           id: 1
  select_type: SIMPLE
        table: log
   partitions: NULL
         type: range
possible_keys: datetime_message
          key: datetime_message
      key_len: 5
          ref: NULL
         rows: 172242
     filtered: 100.00
        Extra: Using index condition; Using filesort

Почему произошёл filesort? Вспомним пример со школьниками: если тридцать школьников (суффикс индекса) учатся в одном классе (префикс индекса), то они отсортированы по pipeline–у; однако при выборе нескольких классов нужно сортировать вручную (брать в руки журнал и на новом листе бумаги создавать новый отсортированный список со всеми учениками 1го класса). Здесь такой же принцип, но с поправкой на то, что datetime – атрибут полностью уникальный (равносильно тому, что в каждом классе учится только один школьник). Значит, СУБД нужно проделать самостоятельную сортировку. Поэтому в данном запросе filesort – это норма, от которой никуда не денешься.

Всё работает, но внезапно...

Однако после анализа самых частых sql–запросов, совершаемых над таблицей log, выяснилось, что самая частая операция, совершаемая в приложении — это поиск логов с конкретным message–м и типом, без конкретных временных промежутков.
Например, поиск всех ошибок с сообщением "message 183".
Такой запрос будет уже неоптимальным и выполняться будет около 30 секунд:

select `datetime`, `message` from `log`
    where `message` = 'message 183'
        and `type` = 'error';

Explain этого запроса выдал такую картину:

           id: 1
  select_type: SIMPLE
        table: log
   partitions: NULL
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 10010745
     filtered: 3.33
        Extra: Using where

Теперь видно, что индекс вовсе не используется. Оно и понятно: слишком затратно искать информацию по суффиксу индекса.

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

drop index `datetime_message` on `log`;
create index `message_datetime` on `log`(`message`(150), `datetime`);

Теперь запрос, который при прошлом индексе ронял бы БД, выглядит вполне оптимально:

           id: 1
  select_type: SIMPLE
        table: log
   partitions: NULL
         type: ref
possible_keys: message_datetime
          key: message_datetime
      key_len: 452
          ref: const
         rows: 1000
     filtered: 100.00
        Extra: Using where

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

Подведём итоги

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

Есть люди, которые считают мифом ставить самый селективный столбец влево.
Сложно назвать это мифом, поскольку на практике самый селективный столбец даёт больше преимущества в поиске над остальными.

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

Полезные ссылки

• Почему ставить самый селективный столбец влево – это миф
• Use the index, Luke! Это, пожалуй, must have любого разраба баз данных. Очень хорошо объяснено оптимальное использование индексов, большое количество примеров с запросами и фишки по различным СУБД.
• Ещё раз на тему того, почему самый селективный столбец слева – это миф