Поводом для написания данной статьи послужили некоторые дебаты в одной из групп linkedin, связанной с MySQL, а также общение с коллегами и хабролюдьми :-)
В данной статье хотел написать что такое вообще JOINы в MySQL и как можно оптимизировать запросы с ними.
В MySQL термин JOIN используется гораздо шире, чем можно было бы предположить. Здесь JOINом может называться не только запрос объединяющий результаты из нескольких таблиц, но и запрос к одной таблице, например, SELECT по одной таблице — это тоже джоин.
Все потому, что алгоритм выполнения джоинов в MySQL реализован с использованием вложенных циклов. Т.е. каждый последующий JOIN это дополнительный вложенный цикл. Чтобы выполнить запрос и вернуть все записи удовлетворяющие условию MySQL выполняет цикл и пробегает по записям первой таблицы параллельно проверяя соответствия условиям описанных в теле запроса, когда находятся записи, удовлетворяющие условиям — во вложенном цикле по второй таблице ищутся записи соответствующие первым и удовлетворяющие условиям проверки и т.д.
Прмер обычного запроса с INNER JOIN
где Р — условия склейки таблиц и фильтры в WHERE условии.
Можно представить такой псевдокод выполнения такого запроса.
где конструкция t1||t2||t3 означает конкатенацию столбцов из разных таблиц.
Если в запросе встречаются OUTER JOINs, например, LEFT OUTER JOIN
то алгоритм выполнения этого запроса MySQL будет выглядеть как-то так
Более подробно почитать об этом можно здесь — dev.mysql.com/doc/refman/5.1/en/nested-joins.html
Итак, как мы видим, JOINы это просто группа вложенных циклов. Так почему же в MySQL и UNION и SELECT и запросы с SUBQUERY тоже джоины?
MySQL оптимизатор старается приводить запросы к тому виду к которому ему удобней обрабатывать и выполнять запросы по стандартной схеме.
С SELECT все понятно — просто цикл без вложенных циклов. Все UNION выполняются как отдельные запросы и результаты складываются во временную таблицу, и потом MySQL работает уже с этой таблицей, т.е. проходясь циклом по записям в ней. С Subquery та же история.
Приводя все к одному шаблону, например, МySQL переписывает все RIGHT JOIN запросы на LEFT JOIN эквиваленты.
Но стратегия выполнения запросов через вложенные циклы накладывает некоторые ограничения, например, в связи с такой схемой MySQL не поддерживает выполнение FULL OUTER JOIN запросов.
Но результат такого запроса можно получить с помощью UNION двух запросов на LEFT JOIN и на RIGHT JOIN
Пример самого запроса можно посмотреть по ссылке на вики.
В отличии от других СУРБД MySQL не генерирует байткод для выполнения запроса, вместо этого MySQL генерирует список инструкций в древовидной форме, которых придерживается engine выполнения запроса выполняя запрос.
Это дерево имеет следующий вид и имеет название «left-deep tree»
В отличии от сбалансированных деревьев (Bushy plan), которые применяются в других СУБД (например Oracle)
Теперь перейдем к самому интересному — к оптимизации джоинов.
MySQL оптимизатор, а именно та его часть, которая отвечает за оптимизацию JOIN-ов выбирает порядок в котором будет производиться склейка имеющихся таблиц, т.к. можно получить один и тот же результат (датасет) при различном порядке таблиц в склейке. MySQL оптимизатор оценивает стоимость различных планов и выбирает с наименьшей стоимостью. Единицей оценки является операция единичного чтения страницы данных размером в 4 килобайта из произвольного места на диске.
Для выбранного плана можно узнать стоимость путем выполнения команды
SHOW SESSION STATUS LIKE 'Last_query_cost';
после выполнения интересующего нас запроса. Переменная Last_query_cost является сессионной переменной. Описание переменной Last_query_cost в MySQL документации можно найти здесь — dev.mysql.com/doc/refman/5.1/en/server-status-variables.html#option_mysqld_Last_query_cost
Оценка основана на статистике: количество страниц памяти, занимаемое таблицей и/или индексами для этой таблицы, cardinality (число уникальных значений) индексов, длинна записей и индексов, их распределение и т.д. Во время своей оценки оптимизатор не рассчитывает на то, что какие-то части попадут в кеш, оптимизатор предполагает, что каждая операция чтения это обращение к диску.
Иногда анализатор-оптимизатор не может проанализировать все возможные планы выполнения и выбирает неправильный. Например, если у нас INNER JOIN по 3м таблицам, то возможных вариантов у анализатора — 3! = 6, а если у нас склейка по 10 таблицам, то тут возможных вариантов уже 10! = 3628800… MySQL не может проанализировать столько вариантов, поэтому в таком случае он использует алгоритм "жадного" поиска.
И вот как раз для решения данной проблемы, нам может пригодиться конструкция STRAIGHT_JOIN. На самом деле я противник подобных хаков как FORCE INDEX и STRAIGH_JOIN, точней против их бездумного использования везде где только можно и нельзя. В данном случае — можно :-) Выяснив (либо экспериментальным путем делая запросы с STRAIGH_JOIN и оценивая Last_query_cost, либо эмпирическим путем) нужный порядок джоинов можно переписать запрос с таблицами в соответствующем порядке и добавить STRAIGH_JOIN к данному запросу, таким образом мы сразу убьем двух зайцев — определим правильный план выполнения запроса (это главный заяц) и сэкономим время на стадии «Statistic» (Все стадии выполнения запроса можно посмотреть установив профайлинг запросов командой SET PROFILING =1, я описывал это в своей предыдущей статье по теме профайлинга запросов в MySQL )
Но не стоит применять этот хак ко всем запросам, расчитывая произвести оптимизацию на спичках и сэкономить время на составление плана выполнения запроса оптимизатором и добавлять STRAIGH_JOIN ко всем запросам с джоинами, т.к. данные меняются и склейка, которая оптимальна сейчас может перестать быть оптимальной со временем, и тогда запросы начнуть очень сильно лагать.
Также, как уже говорилось выше, результаты джоинов помещаются во временные таблицы, поэтому зачастую уместно применять «derived table» в котором мы накладываем все необходимые нам условия на выборку, а также указываем LIMIT и порядок сортировки. В данном случае мы избавимся от избыточности данных во временной таблице, а также проведем сортировку на раннем этапе (по результату одной выборки, а не финальной склейки, что уменьшит размеры записей которые будут сортироваться).
Стандартный пример подхода описанного выше. Простая выборка для отношения много к многим: новости и теги к ним.
Ну и на последок небольшая задачка, которую я иногда задаю на собеседованиях :-)
Есть новостной блоггерный сайт. Есть такие сущности как новости и комментарии к ним.
Задача — нужно написать запрос, который выводит список из 10 новостей определенного типа (задается пользователем) отсортированные по времени издания в хронологическом порядке, а также к каждой из этих новостей показать не более 10 последних коментариев, т.е. если коментариев больше — показываем только последние 10.
Все нужно сделать одним запросом. Да, это, может, и не самый лучший способ, и вы вольны предложить другое решение :-)
В данной статье хотел написать что такое вообще JOINы в MySQL и как можно оптимизировать запросы с ними.
Что такое JOINы в MySQL
В MySQL термин JOIN используется гораздо шире, чем можно было бы предположить. Здесь JOINом может называться не только запрос объединяющий результаты из нескольких таблиц, но и запрос к одной таблице, например, SELECT по одной таблице — это тоже джоин.
Все потому, что алгоритм выполнения джоинов в MySQL реализован с использованием вложенных циклов. Т.е. каждый последующий JOIN это дополнительный вложенный цикл. Чтобы выполнить запрос и вернуть все записи удовлетворяющие условию MySQL выполняет цикл и пробегает по записям первой таблицы параллельно проверяя соответствия условиям описанных в теле запроса, когда находятся записи, удовлетворяющие условиям — во вложенном цикле по второй таблице ищутся записи соответствующие первым и удовлетворяющие условиям проверки и т.д.
Прмер обычного запроса с INNER JOIN
SELECT
*
FROM
Table1
INNER JOIN
Table2 ON P1(Table1,Table2)
INNER JOIN
Table3 ON P2(Table2,Table3)
WHERE
P(Table1,Table2,Table3).
* This source code was highlighted with Source Code Highlighter.где Р — условия склейки таблиц и фильтры в WHERE условии.
Можно представить такой псевдокод выполнения такого запроса.
FOR each row t1 in Table1 {
IF(P(t1)) {
FOR each row t2 in Table2 {
IF(P(t2)) {
FOR each row t3 in Table3 {
IF P(t3) {
t:=t1||t2||t3; OUTPUT t;
}
}
}
}
}
}
* This source code was highlighted with Source Code Highlighter.где конструкция t1||t2||t3 означает конкатенацию столбцов из разных таблиц.
Если в запросе встречаются OUTER JOINs, например, LEFT OUTER JOIN
SELECT
*
FROM
Table1
LEFT JOIN
(
Table2 LEFT JOIN Table3 ON P2(Table2,Table3)
)
ON P1(Table1,Table2)
WHERE
P(Table1,Table2,Tabke3)
* This source code was highlighted with Source Code Highlighter.то алгоритм выполнения этого запроса MySQL будет выглядеть как-то так
FOR each row t1 in T1 {
BOOL f1:=FALSE;
FOR each row t2 in T2 such that P1(t1,t2) {
BOOL f2:=FALSE;
FOR each row t3 in T3 such that P2(t2,t3) {
IF P(t1,t2,t3) {
t:=t1||t2||t3; OUTPUT t;
}
f2=TRUE;
f1=TRUE;
}
IF (!f2) {
IF P(t1,t2,NULL) {
t:=t1||t2||NULL; OUTPUT t;
}
f1=TRUE;
}
}
IF (!f1) {
IF P(t1,NULL,NULL) {
t:=t1||NULL||NULL; OUTPUT t;
}
}
}
* This source code was highlighted with Source Code Highlighter.Более подробно почитать об этом можно здесь — dev.mysql.com/doc/refman/5.1/en/nested-joins.html
Итак, как мы видим, JOINы это просто группа вложенных циклов. Так почему же в MySQL и UNION и SELECT и запросы с SUBQUERY тоже джоины?
MySQL оптимизатор старается приводить запросы к тому виду к которому ему удобней обрабатывать и выполнять запросы по стандартной схеме.
С SELECT все понятно — просто цикл без вложенных циклов. Все UNION выполняются как отдельные запросы и результаты складываются во временную таблицу, и потом MySQL работает уже с этой таблицей, т.е. проходясь циклом по записям в ней. С Subquery та же история.
Приводя все к одному шаблону, например, МySQL переписывает все RIGHT JOIN запросы на LEFT JOIN эквиваленты.
Но стратегия выполнения запросов через вложенные циклы накладывает некоторые ограничения, например, в связи с такой схемой MySQL не поддерживает выполнение FULL OUTER JOIN запросов.
Но результат такого запроса можно получить с помощью UNION двух запросов на LEFT JOIN и на RIGHT JOIN
Пример самого запроса можно посмотреть по ссылке на вики.
План выполнения JOIN запросов
В отличии от других СУРБД MySQL не генерирует байткод для выполнения запроса, вместо этого MySQL генерирует список инструкций в древовидной форме, которых придерживается engine выполнения запроса выполняя запрос.
Это дерево имеет следующий вид и имеет название «left-deep tree»
В отличии от сбалансированных деревьев (Bushy plan), которые применяются в других СУБД (например Oracle)
JOIN оптимизация
Теперь перейдем к самому интересному — к оптимизации джоинов.
MySQL оптимизатор, а именно та его часть, которая отвечает за оптимизацию JOIN-ов выбирает порядок в котором будет производиться склейка имеющихся таблиц, т.к. можно получить один и тот же результат (датасет) при различном порядке таблиц в склейке. MySQL оптимизатор оценивает стоимость различных планов и выбирает с наименьшей стоимостью. Единицей оценки является операция единичного чтения страницы данных размером в 4 килобайта из произвольного места на диске.
Для выбранного плана можно узнать стоимость путем выполнения команды
SHOW SESSION STATUS LIKE 'Last_query_cost';
после выполнения интересующего нас запроса. Переменная Last_query_cost является сессионной переменной. Описание переменной Last_query_cost в MySQL документации можно найти здесь — dev.mysql.com/doc/refman/5.1/en/server-status-variables.html#option_mysqld_Last_query_cost
Оценка основана на статистике: количество страниц памяти, занимаемое таблицей и/или индексами для этой таблицы, cardinality (число уникальных значений) индексов, длинна записей и индексов, их распределение и т.д. Во время своей оценки оптимизатор не рассчитывает на то, что какие-то части попадут в кеш, оптимизатор предполагает, что каждая операция чтения это обращение к диску.
Иногда анализатор-оптимизатор не может проанализировать все возможные планы выполнения и выбирает неправильный. Например, если у нас INNER JOIN по 3м таблицам, то возможных вариантов у анализатора — 3! = 6, а если у нас склейка по 10 таблицам, то тут возможных вариантов уже 10! = 3628800… MySQL не может проанализировать столько вариантов, поэтому в таком случае он использует алгоритм "жадного" поиска.
И вот как раз для решения данной проблемы, нам может пригодиться конструкция STRAIGHT_JOIN. На самом деле я противник подобных хаков как FORCE INDEX и STRAIGH_JOIN, точней против их бездумного использования везде где только можно и нельзя. В данном случае — можно :-) Выяснив (либо экспериментальным путем делая запросы с STRAIGH_JOIN и оценивая Last_query_cost, либо эмпирическим путем) нужный порядок джоинов можно переписать запрос с таблицами в соответствующем порядке и добавить STRAIGH_JOIN к данному запросу, таким образом мы сразу убьем двух зайцев — определим правильный план выполнения запроса (это главный заяц) и сэкономим время на стадии «Statistic» (Все стадии выполнения запроса можно посмотреть установив профайлинг запросов командой SET PROFILING =1, я описывал это в своей предыдущей статье по теме профайлинга запросов в MySQL )
Но не стоит применять этот хак ко всем запросам, расчитывая произвести оптимизацию на спичках и сэкономить время на составление плана выполнения запроса оптимизатором и добавлять STRAIGH_JOIN ко всем запросам с джоинами, т.к. данные меняются и склейка, которая оптимальна сейчас может перестать быть оптимальной со временем, и тогда запросы начнуть очень сильно лагать.
Также, как уже говорилось выше, результаты джоинов помещаются во временные таблицы, поэтому зачастую уместно применять «derived table» в котором мы накладываем все необходимые нам условия на выборку, а также указываем LIMIT и порядок сортировки. В данном случае мы избавимся от избыточности данных во временной таблице, а также проведем сортировку на раннем этапе (по результату одной выборки, а не финальной склейки, что уменьшит размеры записей которые будут сортироваться).
Стандартный пример подхода описанного выше. Простая выборка для отношения много к многим: новости и теги к ним.
SELECT
t.tid, t.description, n.nid, n.title, n.extract, n.modtime
FROM
(
SELECT
n.nid
FROM
news n
WHERE
n.type = 1321
AND n.published = 1
AND status = 1
ORDER BY
n.modtime DESC
LIMIT
200
) as news
INNER JOIN
news n ON n.nid = news.nid
INNER JOIN
news_tag nt ON n.nid = nt.nid
INNER JOIN
tags t ON nt.tid = t.tid
* This source code was highlighted with Source Code Highlighter.Ну и на последок небольшая задачка, которую я иногда задаю на собеседованиях :-)
Есть новостной блоггерный сайт. Есть такие сущности как новости и комментарии к ним.
Задача — нужно написать запрос, который выводит список из 10 новостей определенного типа (задается пользователем) отсортированные по времени издания в хронологическом порядке, а также к каждой из этих новостей показать не более 10 последних коментариев, т.е. если коментариев больше — показываем только последние 10.
Все нужно сделать одним запросом. Да, это, может, и не самый лучший способ, и вы вольны предложить другое решение :-)
