Рано или поздно многие крупные проекты сталкиваются с проблемами производительности при постраничной навигации по записям. Некоторые из них решают эту проблему ограничением количества доступных для просмотра записей (скажем, не больше 1000). Вполне приемлемое решение. Но в этом случаем могут возникнуть проблемы с индексированием сайта сторонними поисковиками, которые и представляют наибольшую угрозу. В этой статье я хотел бы отказаться от привычной для всех панели навигации вида «1..2..3..4..» в пользу простой «вперед… назад» (будет проще объяснить), но это не проблема реализовать подобное и с первым вариантом.
Более точно определить тему, назвав, какое количество записей считать достаточно большим для появления тормозов, не получится, так как эта цифра для всех разная и сильно зависит от того, насколько быстрые у Вас жесткие диски, сколько памяти, и какая часть Ваших данных уже закеширована в ней и тд. Но если Вы и Ваши сервера ощущают, что n-ная страница при выводе даётся тяжелее первой, и при этом не знаете, что с этим делать – статья для Вас. Но для начала, я хотел бы на пальцах объяснить, почему ОНО работает медленно.
Кстати, тест происходит на виртуальной машинке, работаю я с СУБД под рутом, версия MySQL – 5.0.32.
Для тестирования создадим небольшую табличку и наполним ее чем-нибудь.
Небольшим скриптом на PHP был сгенерирован INSERT 100000 записей. Данные такого вида:
— порядок полей в INSERT:
height, width, price, title
— шаблон для полей:
$val_tmpl = "\t(%d, %d, %f, 'Item %d')";
— тестовые значения ($i = 1..100000):
sprintf($val_tmpl, rand(0, 120), rand(0, 220), 10 * rand(0, $i) / $i, $i);
Заносим это все в нашу БД. И можно начинать…
Все, кто уже знает, чем плохи COUNT(*) и LIMIT… OFFSET, могут пропустить эту часть.
Прежде, чем рисовать навигатор, мы делаем SELECT COUNT(*) … WHERE (условия_выборки). Многие, почему-то уверены, что даже если у нас миллионы записей, но условия_выборки позволяют использовать индекс, то такой запрос отработает очень быстро. Проведем эксперимент. Выберем количество записей, у которых height больше 100. Для начала посмотрим, что будет, если индекса по полю height нет.
FLUSH STATUS;
SELECT SQL_NO_CACHE COUNT(*) FROM items WHERE height>100;
+----------+
| count(*) |
+----------+
| 16405 |
+----------+
1 row in set (0.09 sec)
SHOW STATUS LIKE ‘handler%’;
Последняя команда покажет, сколько же, и каких действий пришлось сделать СУБД, чтобы выполнить наш запрос. Так как индекса у нас нет, MySQL пришлось читать данные прямо из таблицы, поэтому нас интересует строка:
…
| Handler_read_rnd_next | 100001 |
…
То есть, MySQL пришлось сделать 100001 операцию перехода к следующей записи, чтобы найти все, соответствующие запросу.
Везде ниже перед каждым SELECT подразумевается выполнение FLUSH STATUS, а после: SHOW STATUS LIKE ‘handler%’.
Чем нам может помочь индекс.
ALTER TABLE items ADD INDEX height_idx (height);
SELECT SQL_NO_CACHE COUNT(*) FROM items FORCE INDEX(height_idx) WHERE height>100;
+----------+
| count(*) |
+----------+
| 16405 |
+----------+
1 row in set (0.04 sec)
В данном случае использовался индекс, поэтому Handler_read_rnd_next будет равен 0, а вот
…
| Handler_read_next | 16405 |
…
То есть индекс позволяет изначально посчитать только те записи, которые нужны, НО ему все равно требуется пробежаться по ним всем. Нет никакой магии, MySQL нигде не хранит количество записей, соответствующих запросу. Поэтому, если у вас миллионы записей, соответствующих условиям запроса, COUNT будет работать очень медленно.
Второй момент. LIMIT … OFFSET. Тот же эксперимент. Попросим нам 5 записей.
SELECT SQL_NO_CACHE * FROM items FORCE INDEX(height_idx) WHERE height>100 LIMIT 5;
…
5 rows in set (0.00 sec)
…
| Handler_read_next | 4 |
…
Вроде все логично. А теперь попросим вернуть другие 5 записей, начиная с 16401.
SELECT SQL_NO_CACHE * FROM items FORCE INDEX(height_idx) WHERE height>100 LIMIT 16400, 5;
…
5 rows in set (0.13 sec)
Видим, что время выборки значительно возросло. Смотрим статус:
…
| Handler_read_next | 16404 |
…
То есть, MySQL, прочитал все 16405, а только потом просто откинул все ненужные.
Как быть?
Итак. От нас требуется вывести 10 записей, а так же нарисовать меню навигации. Мы поняли, что, чтобы дойти до записи, с которой необходимо начать отдавать нам результаты, MySQL тратит много лишних действий. Единственное, как это избежать – сразу перейти к нужной, изменив условия выборки.
Рассмотрим все на простом примере: пусть записи выдаются отсортированные по id. В этом случае нам нужно вместе со ссылкой передать id записи, на которой мы остановились. А остановимся мы на записи с id=10. То есть, в параметрах ссылки на следующую страницу нам нужно передать 10. Соответственно, для второй страницы запрос будет выглядеть так:
SELECT SQL_NO_CACHE id FROM items WHERE id>10 ORDER BY id LIMIT 10;
Кстати, в обоих случаях Handler_read_next будет равен 9. То есть, прыгнули на первую соответствующую запросу запись (благодаря индексу) и сделали 9 переходов на следующую. Самое главное, что какое бы число вместо 10 в условие мы не подставили – мы всегда в результате SHOW STATUS увидим одно и то же, и время выполнения такого запроса уже не будет зависеть от того, где мы находимся, а будет зависеть только от того, сколько и чего мы выбираем.
Надеюсь, смысл Вам понятен. Давайте тогда решим, что делать с меню навигации, а потом перейдем к более сложной ситуации. Пусть в url мы используем ключевые слова next, previous и last. В каких случаях показывать ссылки «вперед», «назад» и «последняя»?
Каждый раз, когда нам приходит next (запрос следующей страницы), мы выбираем не 10 записей, а 11, начиная с id, переданного в параметрах запроса. Если нам вернулось 11 записей, то следует показать ссылку вперед с id 10-й записи, а 11-ю откинуть. Если вернулось меньше 11 записей, то ссылку вперед показывать не надо. При этом мы всегда (всегда, когда пришло next) показываем ссылку назад (previous) с id первой записи из выборки. Ссылки «в начало» и «последняя» всегда показываются вместе с «назад» и «вперед» соответственно. То есть, если мы решили показывать «назад», то должны показать и «в начало».
Каждый раз, когда нам приходит previous (запрос на предыдущую страницу), мы выбираем 11 записей, у которых id меньше указанного в запросе, отсортированные в обратном порядке. То же самое: если вернулось 11 записей, то ссылку «назад» показываем. Ссылку вперед показываем всегда.
Надеюсь, понятно написал…
Что если нам пришел запрос «last»? Просто показать 10 записей, начиная с самой последней. То есть:
SELECT id FROM items ORDER BY id DESC LIMIT 10;
Думаете, у кого-нибудь из пользователей хватит сил промотать несколько сотен, а то и тысяч страниц, для того, чтобы обвинить Вас во лжи, обнаружив в итоге на первой странице не 10 записей? Даже если и хватит, то Вы можете ответить, что он слишком долго мотал…
Предыдущий пример был прост тем, что id – уникален. А что если требуется сортировка по полю, значения которого могут повторяться? Например, height в нашем случае. Простым запросом было выяснено, что в таблице каждое значения height встречается примерно 800 раз. Просто передать последний выведенный height в параметрах запроса уже мало. Поможет нам всё тот же id. От нас просят отсортировать записи по высоте, но это ведь не мешает нам отсортировать их потом еще и по id?
Для этого нам понадобится новый индекс:
ALTER TABLE items ADD KEY height_id_idx (height, id);
Запрос для первой страницы будет такой:
SELECT SQL_NO_CACHE id, height FROM items ORDER BY height, id LIMIT 10;
В моих результатах у последней записи height=0, id=1174. Так и надо передать следующей странице. Например, next_0_1174 или next/0/1074 – как Вам удобнее.
Теперь нам нужно выбрать записи, у которых либо height больше 0, либо height=0, а id>1174 (именно для этого мы и сделали дополнительную сортировку).
То есть:
SELECT SQL_NO_CACHE * FROM items WHERE (height>0) OR (height=0 AND id>1174) ORDER BY height, id LIMIT 10;
Надеюсь, пояснять, почему так, не нужно. Статус по-прежнему показывает всего 9 шагов вперед.
Таким образом, мы можем добавлять и другие сортировки. Например, если мы хотим вывести все записи, отсортированные по цене и высоте, запрос будет таким:
SELECT SQL_NO_CACHE * FROM items WHERE (price>5) OR (price=5 AND height>0) AND (price=5 AND height=0 AND id>1174) ORDER BY price, height, id LIMIT 10;
Остается только передавать все необходимые данные, правильно их обрабатывать и подставлять в запрос. И про индекс не забудьте.
Как быть, если мы хотим показать пользователям, сколько же результатов найдено? Так как речь идет о больших числах, то вряд ли нас кто-то будет проверять. Тот же гугл может выдать, что нашел 1000000 страниц, соответствующих запросу, но больше 1000 вы не увидите. Мы тоже можем выдать количество результатов лишь примерно. Где его взять и как оценить? Помните, мы выполняли запрос:
SELECT SQL_NO_CACHE COUNT(*) FROM items FORCE INDEX(height_idx) WHERE height>100;
А давайте сделаем так:
EXPLAIN SELECT SQL_NO_CACHE * FROM items FORCE INDEX(height_idx) WHERE height>100;
В результате получим что-то такое:
+----+-------------+-------+-------+---------------+------------+---------+------+-------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+-------+---------------+------------+---------+------+-------+-------------+
| 1 | SIMPLE | items | range | height_idx | height_idx | 4 | NULL | 22616 | Using where |
+----+-------------+-------+-------+---------------+------------+---------+------+-------+-------------+
Столбец rows как раз показывает оценочное число записей, которые нужно просмотреть. 22616 и 16405 – разница совсем не велика. Можно округлить до ~20000, да и ладно. Сойдёт. Только помните, что если используете, например, подзапросы и/или объединения, то EXPLAIN вернет несколько строк. Их все надо прочитать и перемножить значения rows.
Данная проблема уже освещалась вскользь на хабре, но не так подробно.
Статья получилась больше, чем ожидал, хотя текст и разбавлен вставками запросов и результатов. В данный момент некуда выложить использованный для генерации данных скрипт + sql файлы. В общем… На заключение сил не осталось:)
Более точно определить тему, назвав, какое количество записей считать достаточно большим для появления тормозов, не получится, так как эта цифра для всех разная и сильно зависит от того, насколько быстрые у Вас жесткие диски, сколько памяти, и какая часть Ваших данных уже закеширована в ней и тд. Но если Вы и Ваши сервера ощущают, что n-ная страница при выводе даётся тяжелее первой, и при этом не знаете, что с этим делать – статья для Вас. Но для начала, я хотел бы на пальцах объяснить, почему ОНО работает медленно.
Кстати, тест происходит на виртуальной машинке, работаю я с СУБД под рутом, версия MySQL – 5.0.32.
1 Начнем с данных
Для тестирования создадим небольшую табличку и наполним ее чем-нибудь.
CREATE TABLE items (
id INT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
height INT UNSIGNED NOT NULL DEFAULT 0,
width INT UNSIGNED NOT NULL DEFAULT 0,
price DECIMAL(10,2) NOT NULL DEFAULT 0.0,
title VARCHAR(255) NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=UTF8;
Небольшим скриптом на PHP был сгенерирован INSERT 100000 записей. Данные такого вида:
— порядок полей в INSERT:
height, width, price, title
— шаблон для полей:
$val_tmpl = "\t(%d, %d, %f, 'Item %d')";
— тестовые значения ($i = 1..100000):
sprintf($val_tmpl, rand(0, 120), rand(0, 220), 10 * rand(0, $i) / $i, $i);
Заносим это все в нашу БД. И можно начинать…
2 Обычный метод постраничного вывода
Все, кто уже знает, чем плохи COUNT(*) и LIMIT… OFFSET, могут пропустить эту часть.
Прежде, чем рисовать навигатор, мы делаем SELECT COUNT(*) … WHERE (условия_выборки). Многие, почему-то уверены, что даже если у нас миллионы записей, но условия_выборки позволяют использовать индекс, то такой запрос отработает очень быстро. Проведем эксперимент. Выберем количество записей, у которых height больше 100. Для начала посмотрим, что будет, если индекса по полю height нет.
FLUSH STATUS;
SELECT SQL_NO_CACHE COUNT(*) FROM items WHERE height>100;
+----------+
| count(*) |
+----------+
| 16405 |
+----------+
1 row in set (0.09 sec)
SHOW STATUS LIKE ‘handler%’;
Последняя команда покажет, сколько же, и каких действий пришлось сделать СУБД, чтобы выполнить наш запрос. Так как индекса у нас нет, MySQL пришлось читать данные прямо из таблицы, поэтому нас интересует строка:
…
| Handler_read_rnd_next | 100001 |
…
То есть, MySQL пришлось сделать 100001 операцию перехода к следующей записи, чтобы найти все, соответствующие запросу.
Везде ниже перед каждым SELECT подразумевается выполнение FLUSH STATUS, а после: SHOW STATUS LIKE ‘handler%’.
Чем нам может помочь индекс.
ALTER TABLE items ADD INDEX height_idx (height);
SELECT SQL_NO_CACHE COUNT(*) FROM items FORCE INDEX(height_idx) WHERE height>100;
+----------+
| count(*) |
+----------+
| 16405 |
+----------+
1 row in set (0.04 sec)
В данном случае использовался индекс, поэтому Handler_read_rnd_next будет равен 0, а вот
…
| Handler_read_next | 16405 |
…
То есть индекс позволяет изначально посчитать только те записи, которые нужны, НО ему все равно требуется пробежаться по ним всем. Нет никакой магии, MySQL нигде не хранит количество записей, соответствующих запросу. Поэтому, если у вас миллионы записей, соответствующих условиям запроса, COUNT будет работать очень медленно.
Второй момент. LIMIT … OFFSET. Тот же эксперимент. Попросим нам 5 записей.
SELECT SQL_NO_CACHE * FROM items FORCE INDEX(height_idx) WHERE height>100 LIMIT 5;
…
5 rows in set (0.00 sec)
…
| Handler_read_next | 4 |
…
Вроде все логично. А теперь попросим вернуть другие 5 записей, начиная с 16401.
SELECT SQL_NO_CACHE * FROM items FORCE INDEX(height_idx) WHERE height>100 LIMIT 16400, 5;
…
5 rows in set (0.13 sec)
Видим, что время выборки значительно возросло. Смотрим статус:
…
| Handler_read_next | 16404 |
…
То есть, MySQL, прочитал все 16405, а только потом просто откинул все ненужные.
Как быть?
3 Как быть
Итак. От нас требуется вывести 10 записей, а так же нарисовать меню навигации. Мы поняли, что, чтобы дойти до записи, с которой необходимо начать отдавать нам результаты, MySQL тратит много лишних действий. Единственное, как это избежать – сразу перейти к нужной, изменив условия выборки.
Рассмотрим все на простом примере: пусть записи выдаются отсортированные по id. В этом случае нам нужно вместе со ссылкой передать id записи, на которой мы остановились. А остановимся мы на записи с id=10. То есть, в параметрах ссылки на следующую страницу нам нужно передать 10. Соответственно, для второй страницы запрос будет выглядеть так:
SELECT SQL_NO_CACHE id FROM items WHERE id>10 ORDER BY id LIMIT 10;
Кстати, в обоих случаях Handler_read_next будет равен 9. То есть, прыгнули на первую соответствующую запросу запись (благодаря индексу) и сделали 9 переходов на следующую. Самое главное, что какое бы число вместо 10 в условие мы не подставили – мы всегда в результате SHOW STATUS увидим одно и то же, и время выполнения такого запроса уже не будет зависеть от того, где мы находимся, а будет зависеть только от того, сколько и чего мы выбираем.
Надеюсь, смысл Вам понятен. Давайте тогда решим, что делать с меню навигации, а потом перейдем к более сложной ситуации. Пусть в url мы используем ключевые слова next, previous и last. В каких случаях показывать ссылки «вперед», «назад» и «последняя»?
Каждый раз, когда нам приходит next (запрос следующей страницы), мы выбираем не 10 записей, а 11, начиная с id, переданного в параметрах запроса. Если нам вернулось 11 записей, то следует показать ссылку вперед с id 10-й записи, а 11-ю откинуть. Если вернулось меньше 11 записей, то ссылку вперед показывать не надо. При этом мы всегда (всегда, когда пришло next) показываем ссылку назад (previous) с id первой записи из выборки. Ссылки «в начало» и «последняя» всегда показываются вместе с «назад» и «вперед» соответственно. То есть, если мы решили показывать «назад», то должны показать и «в начало».
Каждый раз, когда нам приходит previous (запрос на предыдущую страницу), мы выбираем 11 записей, у которых id меньше указанного в запросе, отсортированные в обратном порядке. То же самое: если вернулось 11 записей, то ссылку «назад» показываем. Ссылку вперед показываем всегда.
Надеюсь, понятно написал…
Что если нам пришел запрос «last»? Просто показать 10 записей, начиная с самой последней. То есть:
SELECT id FROM items ORDER BY id DESC LIMIT 10;
Думаете, у кого-нибудь из пользователей хватит сил промотать несколько сотен, а то и тысяч страниц, для того, чтобы обвинить Вас во лжи, обнаружив в итоге на первой странице не 10 записей? Даже если и хватит, то Вы можете ответить, что он слишком долго мотал…
Предыдущий пример был прост тем, что id – уникален. А что если требуется сортировка по полю, значения которого могут повторяться? Например, height в нашем случае. Простым запросом было выяснено, что в таблице каждое значения height встречается примерно 800 раз. Просто передать последний выведенный height в параметрах запроса уже мало. Поможет нам всё тот же id. От нас просят отсортировать записи по высоте, но это ведь не мешает нам отсортировать их потом еще и по id?
Для этого нам понадобится новый индекс:
ALTER TABLE items ADD KEY height_id_idx (height, id);
Запрос для первой страницы будет такой:
SELECT SQL_NO_CACHE id, height FROM items ORDER BY height, id LIMIT 10;
В моих результатах у последней записи height=0, id=1174. Так и надо передать следующей странице. Например, next_0_1174 или next/0/1074 – как Вам удобнее.
Теперь нам нужно выбрать записи, у которых либо height больше 0, либо height=0, а id>1174 (именно для этого мы и сделали дополнительную сортировку).
То есть:
SELECT SQL_NO_CACHE * FROM items WHERE (height>0) OR (height=0 AND id>1174) ORDER BY height, id LIMIT 10;
Надеюсь, пояснять, почему так, не нужно. Статус по-прежнему показывает всего 9 шагов вперед.
Таким образом, мы можем добавлять и другие сортировки. Например, если мы хотим вывести все записи, отсортированные по цене и высоте, запрос будет таким:
SELECT SQL_NO_CACHE * FROM items WHERE (price>5) OR (price=5 AND height>0) AND (price=5 AND height=0 AND id>1174) ORDER BY price, height, id LIMIT 10;
Остается только передавать все необходимые данные, правильно их обрабатывать и подставлять в запрос. И про индекс не забудьте.
4 Что делать с количеством результатов
Как быть, если мы хотим показать пользователям, сколько же результатов найдено? Так как речь идет о больших числах, то вряд ли нас кто-то будет проверять. Тот же гугл может выдать, что нашел 1000000 страниц, соответствующих запросу, но больше 1000 вы не увидите. Мы тоже можем выдать количество результатов лишь примерно. Где его взять и как оценить? Помните, мы выполняли запрос:
SELECT SQL_NO_CACHE COUNT(*) FROM items FORCE INDEX(height_idx) WHERE height>100;
А давайте сделаем так:
EXPLAIN SELECT SQL_NO_CACHE * FROM items FORCE INDEX(height_idx) WHERE height>100;
В результате получим что-то такое:
+----+-------------+-------+-------+---------------+------------+---------+------+-------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+-------+---------------+------------+---------+------+-------+-------------+
| 1 | SIMPLE | items | range | height_idx | height_idx | 4 | NULL | 22616 | Using where |
+----+-------------+-------+-------+---------------+------------+---------+------+-------+-------------+
Столбец rows как раз показывает оценочное число записей, которые нужно просмотреть. 22616 и 16405 – разница совсем не велика. Можно округлить до ~20000, да и ладно. Сойдёт. Только помните, что если используете, например, подзапросы и/или объединения, то EXPLAIN вернет несколько строк. Их все надо прочитать и перемножить значения rows.
Заключение
Данная проблема уже освещалась вскользь на хабре, но не так подробно.
Статья получилась больше, чем ожидал, хотя текст и разбавлен вставками запросов и результатов. В данный момент некуда выложить использованный для генерации данных скрипт + sql файлы. В общем… На заключение сил не осталось:)
