Есть вопросы, которые, казалось бы, не могут быть не решены. Слишком часто мы с ними встречаемся в повседневной жизни. Но посмотришь внимательно — и оказывается, нет, не решены. Все делают по-разному. И не всегда хорошо. Одним из таких вопросов является взаимодействие пользовательского интерфейса работы с таблицей и системы управления базами данных (СУБД).
Требования понятны. Данные должны отображаться быстро, создавать минимальную нагрузку на СУБД и работа с ними должна быть удобна пользователю. Решения вроде тоже все есть. Но все равно даже в очень успешных проектах применены технологии, которые заставляют предположить, что разработчики решили еще раз придумать “самое лучшее” решение.
Хотелось бы рассмотреть современные подходы к решению этой задачи и подумать, есть ли наилучший вариант. И, если нет, когда что лучше использовать.
Самая быстрая операция в базе данных — получение записи по значениям индексированных полей, например, следующий запрос мгновенно возвращает следующую запись в упорядоченной совокупности.
где sortField — поле (набор полей), по которому упорядочена совокупность данных. Обычно такой набор полей включает первичный ключ, благодаря чему порядок записей всегда неизменен.
Здесь и далее я намеренно упрощаю вид запросов, чтобы повысить удобочитаемость. Понятно, что в реальной жизни для набора полей запрос будет выглядеть более громоздко.
Таким образом, самый быстрый вариант отображения данных — это их последовательная загрузка по мере прокручивания. Естественно, в этом случае мы заранее не знаем, когда прокрутка дойдет до конца и отображаем бегунок, исходя из текущих загруженных записей.
При этом может использоваться либо постраничное отображение, как, например, в поисковиках, на Яндекс.Маркет или почте Google, либо «бесконечная прокрутка», как, например во ВКонтакте. Есть комбинации этих подходов, но принцип работы с базой данных один.
В случае с постраничным просмотром пользователю сразу отображается первая страница и определяется, есть ли следующая (проверяется наличие следующего элемента отсортированной совокупности данных). Иногда идет проверка на наличие нескольких следующих страниц. В случае бесконечной прокрутки предполагается, что в таблице есть только загруженные записи. По мере прокрутки загружаются дополнительные записи (если есть) и корректируется положение бегунка в полосе прокрутки. В любом случае идет последовательное считывание записей.
Для пользователя работа вполне логична. Он задает какие-то условия отбора и сортировки записей. Далее ему обычно требуются только верхние записи. Если же пользователь решил посмотреть, что дальше, он вполне может это сделать, пролистав несколько страниц. Так мы, например, работаем с результатами поиска в поисковиках.
Однако есть недостатки.
1. При работе таблицами (особенно не очень большими) использование полосы прокрутки для навигации по всем записям исключительно удобно. В данном случае такая возможность теряется. Опыт же показывает, что большинство таблиц, с которыми работает пользователь, не содержат много записей.
2. Отсутствует возможность перехода к записи. Предположим при работе со своей фонотекой, я хочу найти какую-то песню, которую (я знаю) кто-то загрузил сразу после «Queen. The Show Must Go On ». Если я введу в условиях отбора «Queen. The Show Must Go On», нужная мне песня просто не отобразится. Я, конечно, увижу «Queen. The Show Must Go On», но что было загружено до или после нее никак не узнаю. Единственный вариант в данном случае — прокрутить все записи до необходимой и посмотреть, что там рядом. Аналогичная проблема бывает при использовании почтового сервера, когда необходимо найти письмо в окрестностях заданного. Сначала приходится найти это самое заданное письмо, посмотреть дату, и далее задать еще один фильтр по датам.
3. Все загруженные данные необходимо держать в памяти.
4. Если пользователь выделил запись и ушел с нее на другие операции, то при возвращении в интерфейс таблицы для восстановления старого вида придется заново подгружать все записи с самой первой.
Насколько эти неудобства серьезны — судить системным аналитикам и, в конечном счете, пользователям. В разных случаях эти неудобства проявляются по-разному.
Однако преодоление этих неудобств в любом случае предполагает, что необходимо как-то оценить общее количество записей, которые попадают в диапазон выборки, и обеспечить переход по ним. Т.е. необходимо сразу показывать правильное положение бегунка на полной полосе прокрутки.
Опять же есть два варианта: постраничный просмотр и, так называемый «живой» (live) просмотр. В последнем случае записи подгружаются в момент прокрутки. При этом записи, выходящие за пределы видимого диапазона, забываются.
Для возврата требуемых записей в большинстве СУБД в настоящий момент предусмотрено ключевое слово offset, возвращающая записи со смещением по отсортированной совокупности. У всех, кто мучился с производительностью СУБД, сразу возникает следующий вопрос.
Ответ — нет.
Для многих этот ответ покажется очевидным, например для тех, кто читал руководство к PostgreSQL (http://www.postgresql.org/docs/9.4/static/queries-limit.html): «Строки, пропускаемые при помощи OFFSET, должны все равно просчитываться на стороне сервера; поэтому работа при больших значениях параметра OFFSET может быть неэффективной».
Но в реальности это неочевидный ответ.
Вопреки устоявшимся убеждениям offset работает достаточно быстро, если таблица правильно проиндексирована и статистика обновлена.
Да, многие безуспешно пытались использовать offset на больших таблицах. Еще хуже пришлось тем, кто пытался использовать функцию row_number в MS SQL Server. Есть две хорошие статьи на эту тему. Они посвящены MS SQL Server (http://sqlperformance.com/2015/01/t-sql-queries/pagination-with-offset-fetch) и My SQL (https://explainextended.com/2009/10/23/mysql-order-by-limit-performance-late-row-lookups). Смысл заключается в том, что offset надо применять не сразу к выборке:
а опосредованно через поле, по которому построен кластерный индекс
Здесь предполагается, что по полю clusteredField построен кластерный индекс и применяются все стандартные рекомендации, например, не делать поле clusteredField типа «уникальный идентификатор».
Анализ этого запроса показывает, что использование процессора, количество чтений и общее время примерно соответствует операции подсчета количества записей до искомой. Это не удивительно, алгоритм работы при использовании как offset, так и count примерно одинаковый. Разница только в том, что запросы с count более простые и у оптимизатора запросов меньше шансов создать неадекватный план выполнения.
Хуже другое: запросы, использующие как count, так и offset, будучи быстрыми, не являются мгновенными. Подсчет есть подсчет. Пусть даже используется статистика. Т.е. на больших таблицах пользователь будет в любом случае ожидать некоторое, возможно очень некомфортное, время, прежде чем получит нужные записи.
Можно ли от этого избавиться? Да. Алгоритм дан в статье https://habrahabr.ru/post/278773.
Если говорить упрощенно, поиск записей происходит не по номеру, а по значениям полей, указанным для сортировки (далее сортировочные поля).
Например, если первая фамилия в отсортированном телефонном справочнике Андреев (А — первая буква), а последняя — Яковлев (Я — 33-я буква), то если пользователь сдвинул бегунок на середину, то скорее всего надо показать что-то на букву П (17-я буква).
После мгновенного отображения пользователю записей на букву П (мгновенно, так как поиск происходит по индексу) можно запустить операцию подсчета записей (count) и через некоторое время сдвинуть бегунок, куда положено. Для пользователя это не будет неудобством. Он уже работает с требуемыми записиями.
При этом можно накапливать так называемую «интерполяционную» таблицу, которая содержит пары: фамилия — реальное положение бегунка. В следующий раз при сдвижке бегунка можно учитывать реально положение буквы П.
Если заранее рассчитать несколько точек интерполяционной таблицы, то отскок если и будет, то минимальным и незаметным для пользователя.
Вы скажете, что несколько операций с подсчетом количества записей — это много. Это не так. Сразу несколько точек можно рассчитать одним запросом примерно следующего вида:
Стоимость этого запроса будет незначительно выше, чем просто:
Действительно, все расчеты в данном случае делаются в рамках одного сканирования индекса.
Конечно, если в нашем справочнике один Андреев, один Яковлев, а все остальные лица — так уж случилось — имеют фамилию, начинающуюся на «П» (но заранее мы этого не знаем), то запрос по всем буквам алфавита не поможет, все равно нужны будут следующие итерации, чтобы «расшить» множество записей на «П». Но это уже редкий случай, который не скажется на производительности в среднем.
Описанный метод позволяет мгновенно отобразить пользователю требуемые записи. Таким образом, удобство работы становится значительно выше, чем при использовании offset. Нагрузка на СУБД при этом ничем не отличается. Единственное неудобство заключается отскоке движка, который в реальности минимален.
Более серьезный недостаток — сложная реализация. Но такие проблемы конечного пользователя волновать не должны. Высокоуровневых разработчиков, честно говоря, тоже. Для того и нужны каркасы разработки (framework), чтобы такие проблемы решать за разработчиков.
Естественно, использование подхода, при котором пользователь видит сразу всю полосу прокрутки, в любой реализации предполагает использование медленных операций (не важно с использованием ключевых слов count или offset), которые нагружают СУБД. Но за удобство все равно приходится платить. В данном случае, платить не так много. Если в таблице отображается много полей, то часто затраты ресурсов на подсчет записей даже в больших наборах бывают меньше, чем на выборку.
Более того, оценивать надо не весь набор данных, а только ту часть, которая попадает в выборку пользователя. Скажем, если в таблице 10 млн. записей, но в условия выборки не может попадать более 1 млн. записей, то для оценки нужно брать именно 1 млн. записей.
Мы экспериментировали на данных Федеральной адресной системы (ФИАС). Это более миллиона записей.
Эксперимент был очень простым. Мы реализовали два варианта работы с базой данных: (1) быстрый — с последовательной загрузкой данных) и (2) удобный — при котором пользователю показывается полная полоса прокрутки и корректное положение бегунка. При первичном отображении 1-й способ срабатывает действительно в несколько раз быстрее. Однако после того, как мы прокрутили несколько страниц записей оказалось, что нагрузка на СУБД в обоих случаях вполне сопоставима. Я намеренно не привожу точные цифры, чтобы не усложнять статью. Кроме того, понятно, что даже при аналогичных операция СУБД может срабатывать по-разному. Поэтому тут важны именно оценочные величины: «незначительно больше ресурсов», «значительно больше ресурсов», «примерно одинаково» и т.п. В данном случае речь идет именно о «незначительно больше ресурсов».
В заключение хотелось бы признаться, что в начале статьи при указании недостатков метода последовательной загрузки не была указана важная деталь. Если дополнить этот метод кусками алгоритма отображения записей на основе значений сортировочных полей, можно часть недостатков убрать.
При этом необходимо учитывать следующее.
Таким образом, мы имеем два полюса (назовем их менее радикально, чем в названии статьи): (1) очень быстро/удовлетворительно удобно, (2) очень удобно/достаточно быстро. Есть варианты между этими полюсами, но в данном случае их искать, как мне кажется, не имеет смысла.
P.S. В Microsoft Dynamics NAV в версиях до 2013 при работе с таблицами отображалась полная полоса прокрутки, поиск записей для отображения осуществлялся по значениям сортировочных полей. Начиная с версии 2013 используется алгоритм, при котором данные подгружаются последовательно. Складывается ощущение, что Microsoft пожертвовала удобством 99% пользователей ради того, чтобы на 1% расширить применение NAV.
Остается надеяться, что от 3d в пользу 2d в Xbox Microsoft не откажется. Более притязательные пользователи.
Требования понятны. Данные должны отображаться быстро, создавать минимальную нагрузку на СУБД и работа с ними должна быть удобна пользователю. Решения вроде тоже все есть. Но все равно даже в очень успешных проектах применены технологии, которые заставляют предположить, что разработчики решили еще раз придумать “самое лучшее” решение.
Хотелось бы рассмотреть современные подходы к решению этой задачи и подумать, есть ли наилучший вариант. И, если нет, когда что лучше использовать.
Вопрос 1. Какой самый быстрый способ работы с таблицей?
Самая быстрая операция в базе данных — получение записи по значениям индексированных полей, например, следующий запрос мгновенно возвращает следующую запись в упорядоченной совокупности.
select sortField from table where sortField > [текущая позиция] limit 1;где sortField — поле (набор полей), по которому упорядочена совокупность данных. Обычно такой набор полей включает первичный ключ, благодаря чему порядок записей всегда неизменен.
Здесь и далее я намеренно упрощаю вид запросов, чтобы повысить удобочитаемость. Понятно, что в реальной жизни для набора полей запрос будет выглядеть более громоздко.
Таким образом, самый быстрый вариант отображения данных — это их последовательная загрузка по мере прокручивания. Естественно, в этом случае мы заранее не знаем, когда прокрутка дойдет до конца и отображаем бегунок, исходя из текущих загруженных записей.
При этом может использоваться либо постраничное отображение, как, например, в поисковиках, на Яндекс.Маркет или почте Google, либо «бесконечная прокрутка», как, например во ВКонтакте. Есть комбинации этих подходов, но принцип работы с базой данных один.
В случае с постраничным просмотром пользователю сразу отображается первая страница и определяется, есть ли следующая (проверяется наличие следующего элемента отсортированной совокупности данных). Иногда идет проверка на наличие нескольких следующих страниц. В случае бесконечной прокрутки предполагается, что в таблице есть только загруженные записи. По мере прокрутки загружаются дополнительные записи (если есть) и корректируется положение бегунка в полосе прокрутки. В любом случае идет последовательное считывание записей.
Для пользователя работа вполне логична. Он задает какие-то условия отбора и сортировки записей. Далее ему обычно требуются только верхние записи. Если же пользователь решил посмотреть, что дальше, он вполне может это сделать, пролистав несколько страниц. Так мы, например, работаем с результатами поиска в поисковиках.
Однако есть недостатки.
1. При работе таблицами (особенно не очень большими) использование полосы прокрутки для навигации по всем записям исключительно удобно. В данном случае такая возможность теряется. Опыт же показывает, что большинство таблиц, с которыми работает пользователь, не содержат много записей.
2. Отсутствует возможность перехода к записи. Предположим при работе со своей фонотекой, я хочу найти какую-то песню, которую (я знаю) кто-то загрузил сразу после «Queen. The Show Must Go On ». Если я введу в условиях отбора «Queen. The Show Must Go On», нужная мне песня просто не отобразится. Я, конечно, увижу «Queen. The Show Must Go On», но что было загружено до или после нее никак не узнаю. Единственный вариант в данном случае — прокрутить все записи до необходимой и посмотреть, что там рядом. Аналогичная проблема бывает при использовании почтового сервера, когда необходимо найти письмо в окрестностях заданного. Сначала приходится найти это самое заданное письмо, посмотреть дату, и далее задать еще один фильтр по датам.
3. Все загруженные данные необходимо держать в памяти.
4. Если пользователь выделил запись и ушел с нее на другие операции, то при возвращении в интерфейс таблицы для восстановления старого вида придется заново подгружать все записи с самой первой.
Насколько эти неудобства серьезны — судить системным аналитикам и, в конечном счете, пользователям. В разных случаях эти неудобства проявляются по-разному.
Однако преодоление этих неудобств в любом случае предполагает, что необходимо как-то оценить общее количество записей, которые попадают в диапазон выборки, и обеспечить переход по ним. Т.е. необходимо сразу показывать правильное положение бегунка на полной полосе прокрутки.
Опять же есть два варианта: постраничный просмотр и, так называемый «живой» (live) просмотр. В последнем случае записи подгружаются в момент прокрутки. При этом записи, выходящие за пределы видимого диапазона, забываются.
Для возврата требуемых записей в большинстве СУБД в настоящий момент предусмотрено ключевое слово offset, возвращающая записи со смещением по отсортированной совокупности. У всех, кто мучился с производительностью СУБД, сразу возникает следующий вопрос.
Вопрос 2. Можно ли использовать ключевое слово offset
Ответ — нет.
Для многих этот ответ покажется очевидным, например для тех, кто читал руководство к PostgreSQL (http://www.postgresql.org/docs/9.4/static/queries-limit.html): «Строки, пропускаемые при помощи OFFSET, должны все равно просчитываться на стороне сервера; поэтому работа при больших значениях параметра OFFSET может быть неэффективной».
Но в реальности это неочевидный ответ.
Вопреки устоявшимся убеждениям offset работает достаточно быстро, если таблица правильно проиндексирована и статистика обновлена.
Да, многие безуспешно пытались использовать offset на больших таблицах. Еще хуже пришлось тем, кто пытался использовать функцию row_number в MS SQL Server. Есть две хорошие статьи на эту тему. Они посвящены MS SQL Server (http://sqlperformance.com/2015/01/t-sql-queries/pagination-with-offset-fetch) и My SQL (https://explainextended.com/2009/10/23/mysql-order-by-limit-performance-late-row-lookups). Смысл заключается в том, что offset надо применять не сразу к выборке:
select * from table order by attr1, clusteredField offset 1000;а опосредованно через поле, по которому построен кластерный индекс
select * from table where clusteredField in (select clusteredField from table order by attr1, clusteredField offset 1000);Здесь предполагается, что по полю clusteredField построен кластерный индекс и применяются все стандартные рекомендации, например, не делать поле clusteredField типа «уникальный идентификатор».
Анализ этого запроса показывает, что использование процессора, количество чтений и общее время примерно соответствует операции подсчета количества записей до искомой. Это не удивительно, алгоритм работы при использовании как offset, так и count примерно одинаковый. Разница только в том, что запросы с count более простые и у оптимизатора запросов меньше шансов создать неадекватный план выполнения.
Хуже другое: запросы, использующие как count, так и offset, будучи быстрыми, не являются мгновенными. Подсчет есть подсчет. Пусть даже используется статистика. Т.е. на больших таблицах пользователь будет в любом случае ожидать некоторое, возможно очень некомфортное, время, прежде чем получит нужные записи.
Можно ли от этого избавиться? Да. Алгоритм дан в статье https://habrahabr.ru/post/278773.
Если говорить упрощенно, поиск записей происходит не по номеру, а по значениям полей, указанным для сортировки (далее сортировочные поля).
Например, если первая фамилия в отсортированном телефонном справочнике Андреев (А — первая буква), а последняя — Яковлев (Я — 33-я буква), то если пользователь сдвинул бегунок на середину, то скорее всего надо показать что-то на букву П (17-я буква).
После мгновенного отображения пользователю записей на букву П (мгновенно, так как поиск происходит по индексу) можно запустить операцию подсчета записей (count) и через некоторое время сдвинуть бегунок, куда положено. Для пользователя это не будет неудобством. Он уже работает с требуемыми записиями.
При этом можно накапливать так называемую «интерполяционную» таблицу, которая содержит пары: фамилия — реальное положение бегунка. В следующий раз при сдвижке бегунка можно учитывать реально положение буквы П.
Если заранее рассчитать несколько точек интерполяционной таблицы, то отскок если и будет, то минимальным и незаметным для пользователя.
Вы скажете, что несколько операций с подсчетом количества записей — это много. Это не так. Сразу несколько точек можно рассчитать одним запросом примерно следующего вида:
select
count(*)
,sum(case attr1 < ‘и’ then 1 else 0 end)
,sum(case attr1 < ‘ф’ then 1 else 0 end)
from table;
Стоимость этого запроса будет незначительно выше, чем просто:
select count(*) from table;Действительно, все расчеты в данном случае делаются в рамках одного сканирования индекса.
Конечно, если в нашем справочнике один Андреев, один Яковлев, а все остальные лица — так уж случилось — имеют фамилию, начинающуюся на «П» (но заранее мы этого не знаем), то запрос по всем буквам алфавита не поможет, все равно нужны будут следующие итерации, чтобы «расшить» множество записей на «П». Но это уже редкий случай, который не скажется на производительности в среднем.
Описанный метод позволяет мгновенно отобразить пользователю требуемые записи. Таким образом, удобство работы становится значительно выше, чем при использовании offset. Нагрузка на СУБД при этом ничем не отличается. Единственное неудобство заключается отскоке движка, который в реальности минимален.
Более серьезный недостаток — сложная реализация. Но такие проблемы конечного пользователя волновать не должны. Высокоуровневых разработчиков, честно говоря, тоже. Для того и нужны каркасы разработки (framework), чтобы такие проблемы решать за разработчиков.
Естественно, использование подхода, при котором пользователь видит сразу всю полосу прокрутки, в любой реализации предполагает использование медленных операций (не важно с использованием ключевых слов count или offset), которые нагружают СУБД. Но за удобство все равно приходится платить. В данном случае, платить не так много. Если в таблице отображается много полей, то часто затраты ресурсов на подсчет записей даже в больших наборах бывают меньше, чем на выборку.
Более того, оценивать надо не весь набор данных, а только ту часть, которая попадает в выборку пользователя. Скажем, если в таблице 10 млн. записей, но в условия выборки не может попадать более 1 млн. записей, то для оценки нужно брать именно 1 млн. записей.
Мы экспериментировали на данных Федеральной адресной системы (ФИАС). Это более миллиона записей.
Эксперимент был очень простым. Мы реализовали два варианта работы с базой данных: (1) быстрый — с последовательной загрузкой данных) и (2) удобный — при котором пользователю показывается полная полоса прокрутки и корректное положение бегунка. При первичном отображении 1-й способ срабатывает действительно в несколько раз быстрее. Однако после того, как мы прокрутили несколько страниц записей оказалось, что нагрузка на СУБД в обоих случаях вполне сопоставима. Я намеренно не привожу точные цифры, чтобы не усложнять статью. Кроме того, понятно, что даже при аналогичных операция СУБД может срабатывать по-разному. Поэтому тут важны именно оценочные величины: «незначительно больше ресурсов», «значительно больше ресурсов», «примерно одинаково» и т.п. В данном случае речь идет именно о «незначительно больше ресурсов».
В заключение хотелось бы признаться, что в начале статьи при указании недостатков метода последовательной загрузки не была указана важная деталь. Если дополнить этот метод кусками алгоритма отображения записей на основе значений сортировочных полей, можно часть недостатков убрать.
При этом необходимо учитывать следующее.
- У пользователя все равно не будет полосы прокрутки, на основе которой можно оценить и количество записей, и место текущих отображаемых записей. Т.е. все равно будет неудобно.
- Если мы даем возможность перехода к дальним записям, то в любом случае нагружаем СУБД, т.е. в той или иной мере теряем основное преимущество метода последовательной загрузки данных.
Таким образом, мы имеем два полюса (назовем их менее радикально, чем в названии статьи): (1) очень быстро/удовлетворительно удобно, (2) очень удобно/достаточно быстро. Есть варианты между этими полюсами, но в данном случае их искать, как мне кажется, не имеет смысла.
Выводы
- Использование прокрутки, при которой пользователь сразу видит позицию бегунка, даже на больших объемах данных (миллионы записей в выборке) при позиционировании по значениям сортировочных полей обеспечивает быструю и удобную работу с таблицей при приемлемом штрафе на производительность сервера управления базами данных.
- Использование решений, обеспечивающих последовательную загрузку данных, обосновано только в том случае, если поиск осуществляется в огромных объемах данных: архивы писем, фонотека и т.п.
- Использование ключевого слова offset нецелесообразно в виду того, что данный метод по скорости отображения записей хуже поиска записей по значениям сортировочных полей, дает то же удобство в части навигации и не дает никаких преимуществ в производительности.
P.S. В Microsoft Dynamics NAV в версиях до 2013 при работе с таблицами отображалась полная полоса прокрутки, поиск записей для отображения осуществлялся по значениям сортировочных полей. Начиная с версии 2013 используется алгоритм, при котором данные подгружаются последовательно. Складывается ощущение, что Microsoft пожертвовала удобством 99% пользователей ради того, чтобы на 1% расширить применение NAV.
Остается надеяться, что от 3d в пользу 2d в Xbox Microsoft не откажется. Более притязательные пользователи.