9 октября 2012 в 13:50

Оптимизация сложных запросов MySQL из песочницы tutorial

Введение


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

Прежде всего хотелось бы ограничить круг рассматриваемых проблем оптимизации «широкими» и большими таблицами. Скажем до 10m записей и размером до 20Gb, с большим количеством изменяемых запросов к ним. Если в вашей в таблице много миллионов записей, каждая размером по 100 байт, и пять несложных возможных запросов к ней — это статья не для Вас. NB: Рассматривается движок MySQL innodb/percona — в дальнейшем просто MySQL.

Большинство запросов не являются очень сложными. Поэтому очень важно знать как построить индекс для использования нужным запросом и/или модифицировать запрос таким образом, чтобы он использовал уже имеющиеся индексы. Мы рассмотрим работу оптимизатора для выбора индекса обычных запросов (select_type=simple), без джойнов, подзапросов и объединений.

Отбросим простейшие случаи для очень небольших таблиц, для которых оптимизатор зачастую использует type=all (полный просмотр) вне зависимости от наличия индексов — к примеру, классификатор с 40-ка записями. MySQL имеет алгоритм использования нескольких индексов (index merge), но работает этот алгоритм не очень часто, и только без order by. Единственный разумный способ пытаться использовать index merge — случаи выборки по разным столбцам с OR.

Еще одно отступление: подразумевается что читатель уже знаком с explain. Часто сам запрос немного модифицируется оптимизатором, поэтому для того, чтобы понять, почему использовался или нет тот или иной индекс, следует вызвать
explain extended select xxx;
а затем
show warnings;
который и покажет измененный оптимизатором запрос.

Покрывающий индекс — от толстых таблиц к индексам


Итак задача: пусть у нас есть довольно простой запрос, который выполняется довольно часто, но для такого частого вызова относительно медленно. Рассмотрим стратегию приведения нашего запроса к using index, как к наиболее быстрому выбору.

Почему using index? Да, MySQL используют только B-tree индексы, но тем не менее MySQL старается по возможности держать индексы целиком в памяти (и при этом может даже добавить поверх них адаптивные хеш-индексы) — собственно все это и дает сказочный прирост производительности MySQL по отношению к другим базам данных. К тому же оптимизатор зачастую предпочтет использовать хоть и не лучший, но уже загруженный в память индекс, нежели более лучший, но на диске (для type=index/range). Отсюда несколько выводов:
  • слишком тяжелые индексы — зло. Либо они не будут использоваться потому что они еще не в памяти, либо их не будут грузить в память потому что при этом вытеснятся другие индексы.
  • если размер индекса сопоставим с размером таблицы, либо совокупность используемых индексов для разных частых запросов существенно превышает размер памяти сервера — существенной оптимизации не добиться.
  • Нюанс — индексировать/сортировать по TEXT — обрекать себя на постоянный using filesort.

Один тонкий момент, про который иногда забываешь — MySQL создает только кластерные индексы. Кластерный — по сути указывающий не на абсолютное положение записи в таблице, а (условно) на запись первичного ключа, который в свою очередь позволяет извлечь саму искомую запись. Но MySQL, не мудрствуя лукаво, для того чтобы обойтись без второго лукапа, поступает просто — расширяя любой ключ на ширину первичного ключа. Таким образом если у вас в таблице primary key (ID), key (A,B,C), то в реальности у вас второй ключ не (A,B,C), а (A,B,C,ID). Отсюда мораль — толстый первичный ключ суть зло.

Следует указать на разницу в кешировании запросов в разных базах. Если PostgreSQL/Oracle кешируют планы запросов (как бы prepare for some timeout), то MySQL просто кеширует СТРОКУ запроса (включая значение параметров) и сохраняет результат запроса. То есть если последовательно селектировать
select AAA from BBB where CCC=DDD
несколько раз — то, если DDD не содержит изменяющихся функций, и таблица AAA не изменилась (в смысле используемой изоляции), результат будет взят прямо из кеша. Довольно спорное улучшение.

Таким образом, считаем, что мы не просто вызываем один и тот же запрос несколько раз. Параметры запроса меняются, данные таблицы меняются. Наилучший вариант — использование покрывающего индекса. Какой же индекс будет покрывающим?
  1. Во-первых, смотрим на клоз order by. Используемый индекс должен начинаться с тех же столбцов что упомянуты в order by, в той же или в полностью обратной сортировке. Если сортировка не прямая и не обратная — индекс не может быть использован. Здесь есть одно но… MySQL до сих пор не поддерживает индексов со смешанными сортировками. Индекс всегда asc. Так что если у вас есть order by A asc, B desc — распрощайтесь с using index.
  2. Столбцы, которые извлекаются, должны присутствовать в покрывающем индексе. Очень часто это невыполнимое условие в связи с бесконечным ростом индекса, что, как известно, зло. Поэтому существует способ обойти этот момент — использование self join'а. То есть разделение запроса на выбор строк и извлечение данных. Во-первых, выбираем по заданному условию только столбцы первичного ключа (который всегда присутствует в кластером индексе), и во-вторых, полученный результат джойним к селекту всех требуемых столбцов, используя этот самый первичный ключ. Таким образом у нас будет чистый using index в первом селекте, и eq_ref (суть множественный const) для второго селекта. Итак, мы получаем что-то похожее на:
    select AAA,BBB,CCC,DDD from tableName as a join tableName as b using (PK) «where over table b»
    
  3. Далее клоз where. Здесь в худшем случае мы можем перебрать весь индекс (type=index), но по возможности стоит стремиться использовать функции, не выводящие за рамки type=range (>, >=, <, <=, like «xxx%» и так далее). Используемый индекс должен включать все поля из where, для того чтобы сохранить using index. Как уже было отмечено выше — можно пытаться использовать index_merge — но зачастую это просто не возможно со сложными условиями.

Собственно, это все, что можно сделать для случая, когда мы имеем только один вид запроса. К сожалению, оптимизатор MySQL не всегда при наличии покрывающего индекса может выбрать именно его для выполнения запроса. Что ж, в таком случае приходится помогать оптимизатору с помощью стандартных хинтов use/force index.

Вычленение толстых полей из покрывающего индекса — от толстых индексов к тонким


Но что делать, если у нас запросы бывают нескольких видов, или требуются разные сортировки и при этом используются толстые поля (varchar)? Просто посчитайте размер индекса поля varchar(100) в миллионе записей. А если это поле используется в разных видах запросов — для которых у нас разные покрывающие индексы? Возможно ли иметь в памяти только ОДИН индекс по этому толстому полю, сохранив при этом ту же (или почти ту же) производительность в разных запросах? Итак — последний пункт.
  1. Толстые и тонкие поля. Очевидно, что иметь несколько РАЗНЫХ вариантов ключей с использованием толстых полей — непозволительная роскошь. Поэтому по возможности мы должны пытаться иметь только один ключ начинающийся на толстое поле. И здесь уместно использовать некоторый искусственный алгоритм замены условий. То есть заменить условие по толстому полю на джойн по результатам этого условия. К примеру:
    select A from tableName where A=1 or fatB='test'
    
    вместо создания ключа key(fatB, A) мы создадим тонкий ключ key(A) и толстый key(fatB). И перепишем условие след образом.
    create temporary table tmp as select PK from tableName where fatB='test';
    select A from tableName left join tmp using (PK) where A=1 or tmp.PK is not null;
    

Следовательно, мы можем иметь много тонких ключей, для разных запросов и только один толстый по полю fatB. Реальная экономия памяти, при почти полном сохранении производительности.

Задание для самостоятельного разбора


Требуется создать минимальное количество ключей (с точки зрения памяти) и оптимизировать запросы вида:
select A,B,C,D from tableName where A=1 and B=2 or C=3 and D like 'test%';  
select A,C,D from tableName where B=3 or C=3 and D ='test' order by B;
Допустим запросы не сводимы к type=range.

Список используемой литературы

  1. High Performance MySQL, 2nd Edition
    Optimization, Backups, Replication, and More
    By Baron Schwartz, Peter Zaitsev, Vadim Tkachenko, Jeremy D. Zawodny, Arjen Lentz, Derek J. Balling
    Publisher: O'Reilly Media
    Released: June 2008
    Pages: 712
  2. www.mysqlperformanceblog.com
+42
28956
462

Комментарии (20)

0
AlexeyVD, #
> Таким образом если у вас в таблице primary key (ID), key (A,B,C), то в реальности у вас второй ключ не (A,B,C), а (A,B,C,ID).

Тогда уж (ID, A, B, C).

И на мой взгляд как-то многовато воды в статье. Хотелось бы больше примеров на реальных данных и с DDL таблиц.
+4
Milovantsev, #
Не знаю, уместно ли спорить — но вот тут же на хабре есть подробная статья об этом
Фактически, вторичный ключ вида KEY `key` (a,b,c) будет иметь структуру KEY `key` (a,b,c,clustered_index).
С уважением,
PAV.
0
AlexeyVD, #
Да, вы правы, я перепутал.
0
shagguboy, #
>Да, MySQL используют только B-tree индексы,
dev.mysql.com/doc/refman/5.5/en/create-index.html
index_type:
USING {BTREE | HASH}

index_option:
KEY_BLOCK_SIZE [=] value
| index_type
| WITH PARSER parser_name
| COMMENT 'string'
0
Milovantsev, #
Я крайне извиняюсь что не выделил специальным шрифтом фразу
> Рассматривается движок MySQL innodb/percona — в дальнейшем просто MySQL.
Сейчас выделю.

По той же ссылке видим:

Storage Engine Permissible Index Types
MyISAM — BTREE
InnoDB — BTREE
MEMORY/HEAP — HASH, BTREE
NDB — HASH, BTREE (see note in text)
0
shagguboy, #
14.2.10.4. Adaptive Hash Indexes

If a table fits almost entirely in main memory, the fastest way to perform queries on it is to use hash indexes. InnoDB has a mechanism that monitors index searches made to the indexes defined for a table. If InnoDB notices that queries could benefit from building a hash index, it does so automatically.
0
Melkij, #
Адаптивный — это не то. Хотя бы потому, что мы никак на него влиять не можем.

Впрочем, никто не мешает прозрачно эмулировать хэш-индекс дополнительным полем и парой триггеров.
+2
Milovantsev, #
Похоже у нас завязалась настоящая дискуссия.
Я хотел бы попросить вас, уважаемый shagguboy, дочитывать приводимые ссылки до конца.
А далее там же написано что адаптивный хеш индекс строится только в памяти, только поверх существующего B-tree индекса, и только в тех случаях когда оптимайзер найдет это целесообразным. То есть в случае множества запросов с type=const/ew_ref
К сожалению такие случаи не попадают под изначальные условия статьи.

Но чтобы закончить спор я переформулирую фразу.

С уважением,
PAV.
+3
shagguboy, #
> MySQL создает только кластерные индексы.
вы перманентно путаете MYSQL и storage engine
+3
Milovantsev, #
> Рассматривается движок MySQL innodb/percona — в дальнейшем просто MySQL.

С уважением,
PAV.
0
rbtaxi, #
Кстати, что касается задания. В задаче не хватает условий. Например, какой тип у нас имеет поле D, текст это, чар или варчар? Какие значения принимает.
В своё время был удивлён, когда узнал, что like работает достаточно быстро при выборках типа like 'any%'.
В своё время был удивлён, когда узнал, что чар на порядок быстрее варчара при поиске, т.к. выделяется определённое количество места в памяти под значение.
В настоящее время был удивлён, когда узнал, что уже не надо оптимизировать OR, что mysql это делает сама )
+1
Milovantsev, #
> какой тип у нас имеет поле D, текст это, чар или варчар?
Так как сортировки по D в примере нет, то все три толстых строковых типа ведут себя одинаково.

> Какие значения принимает.
Безусловно ограничений на количество значений нет. На мой взгляд самоочевидно то, что что при наличии ограничений на количество значений в строковом типе в таблицах с миллионами записей, использование char/varchar/text не эффективно. Для таких случаев следует использовать статический (ENUM) или динамический (отдельная таблица) классификатор. И то и другое сводят толстое поле к тонкому и в таблице и в индексе.

> В своё время был удивлён, когда узнал, что like работает достаточно быстро при выборках типа like 'any%'.
Только при наличии b-tree индекса.

> В своё время был удивлён, когда узнал, что чар на порядок быстрее варчара при поиске, т.к. выделяется определённое количество места в памяти под значение.
Только при отсутствии индекса, и при условии что в таблице нет полей с непостоянной длиной (varchar/text/etc).

> В настоящее время был удивлён, когда узнал, что уже не надо оптимизировать OR, что mysql это делает сама )
Не все так радужно. Для простых условий — делает. А если OR внутри сложной комбинации скобок — то может ошибаться.

Похоже уже пора рисовать десять заповедей оптимизатора (My)SQL.
Вот и мои пять копеек. В статью не включил, потому что объяснить такую черную магию не могу.
Если у вас гарантированный полный скан покрывающего индекса для запроса без order by, и у таблицы первичный ключ — автоинкрементное поле, то добавление этого поля в начало покрывающего индекса даст 15-20% улучшения скорости. (Да, в реальности это означает что автоинкрементное поле дважды присутствует в индексе — в начале и в конце).
+1
LightAsterix, #
Поясните, что из описанного специфично именно для перконы и не работает для обычных innodb/myisam?
+2
Milovantsev, #
Думается, оборот «обычных innodb/myisam» не совсем корректен. Эти два движка имеют столько различий, что с равным успехом можно было бы говорить об «обычных Oracle / MS SQL Server».

Percona XtraDB (Innodb-plugin) просто оптимизированный форк от InnoDB. Чего-то специфичного в оптимизации на уровне SQL запросов, отличающего его от InnoDB, мне не известно. С удовольствием узнаю что-то новое.

Относительно оптимизации запросов для MyISAM видимо нужна отдельная статья. Но я не большой специалист по MyISAM.

С уважением,
PAV.
+1
ztxn, #
Мне показался несколько странным и удивительным приведенный Вами порядок
>> Во-первых, смотрим на клоз order by
>>Далее клоз where.

Сразу оговорюсь я не знаком с МySQL (но стремлюсь быть в курсе), я эскалирую свои знания из других систем.
Если бы речь шла об оракле, я бы настаивал на следующем порядке:

В первую очередь смотрим на where. Причем только на строгие равентсва (=,in).
Во вторую очередь смотрим на ордер бай и отбор по диапазонам. Здесь все очень не однозначно, зависит от состава данных. Для поиска по диапазону мне удавалось использовать только один предикат, по этой причине тут надо выбрать наиболее селективный и оценить, что нам будет дешевле — отсортировать набор, полученный с отбором по всем предикатам, или же сканирование индекса по предикатам выбранным в первую очередь, но без сортировки.
В третью очередь, соответственно, ставим то, что не во поставили во вторую
В четвертую очередь, в самый хвост ставим селект лист и отбор по неравенству.

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

В MySQL как-то все совсем иначе?
+1
ztxn, #
Домашка:
1)
select A,B,C,D from tableName where A=1 and B=2 or C=3 and D like 'test%';  


create index indexAB on table tableName (A,B,C,D);
create index indexCD on table tableName (C,D,A,B);
select A,B,C,D from tableName where A=1 and B=2 
union all
select A,B,C,D from tableName where C=3 and D like 'test%'  and (not (A=1 and B=2) or A is null or B is null)
)

Но тут, право же, оба индекса сделаны покрываеющими только лишь от того, что тема про покрывающие индексы. Нужны ли тут покрывающие — всамделе большой вопрос. Мне так думается, в большинстве случаев достаточно было бы индексов по А,B и C,D
2)
select A,C,D from tableName where B=3 or C=3 and D ='test' order by B;

тут собсна то же саоме
create index (B,A,C,D);
create index (C,D,B,A);
select A,C,D  from tableName where (B<3 /*or B is null*/)and C=3 and D ='test' order by B
union all
select A,C,D  from tableName where B=3
union all
select A,C,D  from tableName where (B>3 /*or B is null*/)and C=3 and D ='test' order by B

В какой — верхний или нижний запрос поставить предикат b is null — не зна, зависит от того, где нулы в индексе mysql хранит — в верху или внизу

c покрытием то же самое, мне думается можно было бы обойтись индексами по B и C,D,B
0
Milovantsev, #
Браво, ztxn. Замечательное приведение к type=range. Добавил вам плюсик.

Но все же суть статьи была не в этом. Попробую пояснить.
Для большого числа видов запросов, определяемых пользователями, и в большинстве своем сложных и несводимых к type=range, для больших и широких таблиц, в свое время было выяснено, что одни и те же запросы (с точностью до автоматического перевода) вполне нормально работают на PostgreSQL/MS SQL Server (порт на Oracle сейчас готовится, и пока что показывает себя вполне пристойно), но начинают крайне медленно выполняться и сильно нагружать систему на MySQL, при наличии одних и тех же индексов.

Стоит отметить, что изначально система писалась именно под MySQL, и порты на другие базы данных зачастую не так оптимальны в силу необходимости перевода «нестандартных возможностей» MySQL.

С другой стороны, в защиту MySQL стоит сказать что остальная работа системы (читай обычные запросы) на MySQL выполняются либо так же быстро, либо гораздо быстрее чем на PostgreSQL/MS SQL Server.

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

Почему только покрывающий индекс, а не перевод условия в ДНФ, накопление статистики по данным столбцов, разбиение порядка и так далее, по списку того что было продемонстрировано выше, и многое другое? Другими словами почему не написать оптимизатор оптимизатора MySQL? Ответ, я думаю, очевиден.

Таким образом, видимо стоит добавить в задание, условие «допустим запросы не сводимы к type=range»

Относительно сортировки. Если покрывающий индекс не начинается со столбцов используемых в клозе order by, то нам грозит using filesort, который приводит к самым серьезным нагрузкам системы. Поэтому это условие первое.
+1
petropavel, #
Не иначе. Это в статье все иначе, плюс куча ошибок, не говоря уж про «лукапы» и «клозы».
0
svetasmirnova, #
> Один тонкий момент, про который иногда забываешь — MySQL создает только кластерные индексы.

Что-то у Вас с терминологией. Почитайте какие индексы кластерные, а какие дополнительные (или вторичные) здесь: dev.mysql.com/doc/refman/5.5/en/innodb-index-types.html

> Следует указать на разницу в кешировании запросов в разных базах. Если PostgreSQL/Oracle кешируют планы запросов (как бы prepare for some timeout), то MySQL просто кеширует СТРОКУ запроса (включая значение параметров) и сохраняет результат запроса.

Это Вы зачем-то поведение query cache объясняете. Каким оно тут боком — непонятно.
0
Milovantsev, #
Согласен, неудачная фраза. Думаю всех устроит оборот "… создает только таблицы с кластерным индексом"

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