Оптимизация постраничной навигации

Требование

У вас есть веб-сайт с новостными статьями, блогом или другим списком элементов, который может быть слишком длинным для одной страницы. Поэтому вы решаете разбить его на фрагменты по, скажем, 10 элементов и предоставляете кнопку [Далее], чтобы перейти к следующей "странице".

Вы замечаете OFFSET и LIMIT в MariaDB и решаете, что это очевидный способ сделать это.

    SELECT  *
        FROM  items
        WHERE  messy_filtering
        ORDER BY  date DESC
        OFFSET  $M  LIMIT $N

Обратите внимание, что требования к задаче предполагают наличие ссылки [Далее] на каждой странице, чтобы пользователь мог переходить по данным. Ему не нужны ссылки "Перейти на страницу #". Возможно, полезны ссылки на первую или последнюю страницы.

Проблема

Все хорошо – до тех пор, пока в списке не будет 50 000 элементов. И кто-то попытается пройти все 5000 страниц. Такой "кто-то" может быть поисковым роботом.

В чем проблема? Производительность. Ваша веб-страница выполняет "SELECT ... OFFSET 49990 LIMIT 10" (или эквивалент "LIMIT 49990,10"). MariaDB должна найти все 50 000 строк, пропустить первые 49 990, а затем доставить 10 для этой удаленной страницы.

Если это робот ("паук"), который читает все страницы, то он фактически обработает около 125 000 000 элементов, чтобы прочитать все 5000 страниц.

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

Другие проблемы

Помимо проблемы с производительностью...

• Если элемент вставляется или удаляется между просмотрами одной страницы и следующей, вы можете пропустить элемент или увидеть дублированный.
• Страницы нелегко закрепить закладками или отправить кому-то другому, потому что содержимое со временем изменяется.
• Оператор WHERE и ORDER BY могут даже привести к тому, что все 50 000 элементов нужно будет прочитать, чтобы найти 10 элементов для первой страницы!

Что делать?

Аппаратное обеспечение? Нет, это просто пластырь. Данные будут продолжать расти, и даже новое оборудование не справится с этим.

Лучший ИНДЕКС? Нет. Вы должны отказаться от чтения всей таблицы для получения 5000-й страницы.

Создать другую таблицу, указывающую, где начинаются страницы? Давайте будем реалистичны! Это будет кошмар по обслуживанию и дорогостоящим.

Вывод: не используйте OFFSET; вместо этого запоминайте, где вы "остановились".

First page (latest 10 items):
    SELECT ... WHERE ... ORDER BY id DESC LIMIT 10
Next page (second 10):
    SELECT ... WHERE ... AND id < $left_off ORDER BY id DESC LIMIT 10

С INDEX(id) это внезапно становится очень эффективным.

Реализация – отказ от OFFSET

Вероятно, вы делаете это сейчас: ORDER BY datetime DESC LIMIT 49990,10. Вероятно, в таблице есть какой-то уникальный идентификатор. Его можно использовать для "остановки".

В настоящее время кнопка [Далее] вероятно имеет URL-адрес, похожий на ?topic=xyz&page=4999&limit=10. 'topic' (или 'метка', или 'источник', или 'пользователь' и т.д.) указывает, какой набор элементов отображается. Произведение page*limit даёт OFFSET. (Параметр "limit=10" может быть в URL-адресе или жёстко закодирован; этот выбор не имеет отношения к данному обсуждению.)

Новый вариант будет ?topic=xyz&id=12345&limit=10. (Примечание: 12345 нельзя вычислить из 4999.) С помощью INDEX(topic, id) вы можете эффективно сказать

    WHERE topic = 'xyz'
      AND id >= 1234
    ORDER BY id
    LIMIT 10

Это затронет только 10 строк. Это существенное улучшение для последующих страниц. Теперь для более подробной информации.

Реализация – "Остановка"

Что если на отображении текущей страницы осталось ровно 10 строк? Это сделает интерфейс удобнее, если вы выделите кнопку [Далее] серым цветом, не так ли? (Или вы можете полностью скрыть кнопку.)

Как это сделать? Вместо LIMIT 10 используйте LIMIT 11. Это даст вам 10 элементов, необходимых для текущей страницы, плюс указание наличия следующей страницы. И идентификатор этой страницы.

Итак, возьмите 11-й идентификатор для кнопки [Далее]: <a href=?topic=xyz&id=$id11&limit=10>Далее</a>

Реализация – ссылки, выходящие за пределы [Далее]

Давайте расширим трюк с 11 для поиска следующих 5 страниц и создания ссылок для них.

План А – указать LIMIT 51. Если вы находитесь на 12 странице, это даст ссылки на страницы 13 (используя 11-й идентификатор) до страницы 17 (51-й).

План Б – выполнить два запроса, один для получения 10 элементов для текущей страницы, а другой – для получения следующих 41 идентификатора (LIMIT 10, 41) для следующих 5 страниц.

Какой план выбрать? Это зависит от многих факторов, поэтому проведите бенчмаркинг.

Разумный набор ссылок

Достижение вперёд и назад на 5 страниц не слишком сложно. Для поиска идентификаторов в обоих направлениях потребуются два отдельных запроса. Также легко добавить ссылки на первую и последнюю страницы. Для них не нужен идентификатор; они могут быть, например,

    <a href=?topic=xyz&id=FIRST&limit=10>First</a>
    <a href=?topic=xyz&id=LAST&limit=10>Last</a>

Интерфейс распознает их, а затем сгенерирует SELECT с чем-то вроде

    WHERE topic = 'xyz'
    ORDER BY id ASC -- ASC for First; DESC for Last
    LIMIT 10

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

    ( SELECT ...
        WHERE topic = 'xyz'
        ORDER BY id DESC
        LIMIT 10
    ) ORDER BY id ASC

Предположим, вы находитесь на 12 странице из множества страниц. Он может отобразить такие ссылки:

    [First] ... [7] [8] [9] [10] [11] 12 [13] [14] [15] [16] [17] ... [Last]

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

Page one of three:
    First [2] [3]
Page one of many:
    First [2] [3] [4] [5] ... [Last]
Page two of many:
    [First] 2 [3] [4] [5] ... [Last]
If you jump to the Last page, you don't know what page number it is.
So, the best you can do is perhaps:
    [First] ... [Prev] Last

Как это работает

Цель – обработать только соответствующие строки, а не все строки, предшествующие желаемым строкам. Это хорошо достигается, за исключением создания ссылок на "следующие 5 страниц". Это может быть (или не быть) эффективно решено с помощью простого SELECT id, обсуждаемого выше. Причина, по которой это может быть неэффективным, связана с оператором WHERE.

Давайте обсудим оптимальные и неоптимальные индексы.

Для этого обсуждения я предполагаю

• Поле datetime может содержать дубликаты – это может вызвать проблемы
• Поле id уникальное
• Поле id достаточно близко к отсортированному по времени, чтобы его можно было использовать вместо datetime.

Очень эффективно – вся работа выполняется в индексе:

    INDEX(topic, id)
    WHERE topic = 'xyz'
      AND id >= 876
    ORDER BY id ASC
    LIMIT 10,41
<</code??
That will hit 51 consecutive index entries, 0 data rows.

Inefficient -- it must reach into the data:
<<code>>
    INDEX(topic, id)
    WHERE topic = 'xyz'
      AND id >= 876
      AND is_deleted = 0
    ORDER BY id ASC
    LIMIT 10,41

Это затронет по крайней мере 51 последовательную запись индекса, плюс по крайней мере 51 случайную строку данных.

Эффективно – возвращаемся к предыдущей эффективности:

    INDEX(topic, is_deleted, id)
    WHERE topic = 'xyz'
      AND id >= 876
      AND is_deleted = 0
    ORDER BY id ASC
    LIMIT 10,41

Обратите внимание, как все части WHERE с '=' идут первыми, затем идут как '>=' и 'ORDER BY', оба по полю id. Это означает, что ИНДЕКС можно использовать для всех WHERE, плюс ORDER BY.

"Элементы 11-20 из 12345"

Вы теряете "из", кроме случаев, когда количество невелико. Вместо этого скажите что-то вроде

    Items 11-20 out of Many

В качестве альтернативы... Только несколько поисковых запросов будут иметь слишком много элементов для подсчёта. Создайте другую таблицу с критериями поиска и количеством. Это количество можно вычислять ежедневно (или ежечасно) с помощью фонового скрипта. Когда вы обнаружите, что тема популярна, обратитесь к таблице, чтобы получить

    Items 11-20 out of about 49,000

Фоновый скрипт округлил бы количество.

Быстрый способ получить _приблизительное_ количество строк для таблицы InnoDB – это

    SELECT  table_rows
        FROM  information_schema.TABLES
        WHERE  TABLE_SCHEMA = 'database_name'
          AND  TABLE_NAME = 'table_name'

Однако он не поддерживает оператор WHERE, который, вероятно, у вас есть.

Сложные WHERE или JOIN

Если критерии поиска не могут быть ограничены ИНДЕКСОМ в одной таблице, этот метод обречён на провал. У меня есть другая статья, обсуждающая "списки", которая решает эту проблему (требуется дополнительная работа), а также улучшает то, что обсуждается здесь.

Насколько быстрее?

Это зависит от

• Количество строк (в общей сложности)
• Тот ли оператор WHERE предотвратил эффективное использование ORDER BY
• Данные больше, чем кеш. Этот последний пункт срабатывает, когда построение одной страницы требует чтения большего объёма данных с диска, который может быть кэширован. На этом этапе проблема переходит от ограниченной процессором к ограниченной вводом-выводом. Это может внезапно замедлить загрузку страниц в 10 раз.

Что потеряно

• Нельзя "перейти к странице N" для произвольного N. Зачем вам это нужно?
• Переход назад от конца не знает номеров страниц.
• Код более сложный.

Дата публикации

Разработан примерно в 2007 году; опубликован в 2012 году.

См. также

• Обсуждение на форуме
• Льюк называет это "методом поиска" или "постраничной навигацией по набору ключей"
• Ещё статьи Льюка

Рик Джеймс любезно разрешил нам использовать эту статью в базе знаний.

Сайт Рика Джеймса содержит другие полезные советы, инструкции, оптимизации и рекомендации по отладке.

Исходный источник: http://mysql.rjweb.org/doc.php/pagination