Один із типових сценаріїв у всіх звичних нам додатках — пошук даних за певними критеріями та виведення їх у зручному для читання вигляді. Тут же можуть бути додаткові можливості сортування, угруповання, посторінкового висновку. Завдання, по ідеї, тривіальна, але при її вирішенні багато розробників роблять ряд помилок, через які потім страждає продуктивність. Спробуємо розглянути різні варіанти розв'язання цього завдання та сформулювати рекомендації щодо вибору найбільш ефективної реалізації.
Варіант пейджингу #1
Найпростіший варіант, який спадає на думку - це посторінковий висновок результатів пошуку в його самому класичному вигляді.
Припустимо, у додатку використовується реляційна база даних. У цьому випадку для виведення інформації в такому вигляді потрібно буде виконати два запити SQL:
- Отримати рядки для поточної сторінки.
- Порахувати загальну кількість рядків, що відповідає критеріям пошуку, - це потрібно для показу сторінок.
Розглянемо перший запит на прикладі тестової MS SQL бази для сервера 2016 року. Для цього будемо використовувати таблицю Sales.SalesOrderHeader:
SELECT * FROM Sales.SalesOrderHeader
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
Наведений вище запит виведе перші 50 замовлень зі списку, відсортованого за зменшенням дати додавання, тобто 50 останніх замовлень.
Виконується він швидко на тестовій базі, але давайте подивимося на план виконання та статистику введення-виведення:
Table 'SalesOrderHeader'. Scan count 1, logical reads 698, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.Отримати статистику введення/виводу для кожного запиту можна, виконавши в середовищі виконання запитів SET STATISTICS IO ON.
Як видно з плану виконання, найбільш ресурсомістким є сортування всіх рядків вихідної таблиці за датою додавання. І проблема в тому, що чим більше в таблиці з'являтиметься рядків, тим «важчим» буде сортування. На практиці таких ситуацій слід уникати, тому додамо індекс на дату додавання та подивимося, чи змінилося споживання ресурсів:
Table 'SalesOrderHeader'. Scan count 1, logical reads 165, physical reads 0, read-ahead reads 5, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Очевидно, стало набагато краще. Але чи всі проблеми вирішено? Змінимо запит на пошук замовлень, де сумарна вартість товарів перевищує 100 доларів:
SELECT * FROM Sales.SalesOrderHeader
WHERE SubTotal > 100
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
Table 'SalesOrderHeader'. Scan count 1, logical reads 1081, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.Маємо кумедну ситуацію: план запиту не набагато гірший за попередній, але фактична кількість логічних читань майже вдвічі більша, ніж при повному скані таблиці. Вихід є — якщо з індексу, що вже існує, зробити складовим і другим полем додати сумарну ціну товарів, то знову отримаємо 165 logical reads:
CREATE INDEX IX_SalesOrderHeader_OrderDate_SubTotal on Sales.SalesOrderHeader(OrderDate, SubTotal);
Цю серію прикладів можна продовжувати ще довго, але дві основні думки, які хочу тут висловити, такі:
- Додавання будь-якого нового критерію або порядку сортування пошукового запиту може суттєво вплинути на швидкість його виконання.
- Але якщо нам необхідно віднімати лише частину даних, а не всі результати, що підходять під умови пошуку, є багато способів оптимізувати такий запит.
Тепер перейдемо до другого запиту, згаданого на самому початку — до того, що вважає кількість записів, які відповідають пошуковому критерію. Візьмемо той самий приклад — пошук замовлень, які дорожчі за 100 доларів:
SELECT COUNT(1) FROM Sales.SalesOrderHeader
WHERE SubTotal > 100
За наявності складеного індексу, зазначеного вище, отримуємо:
Table 'SalesOrderHeader'. Scan count 1, logical reads 698, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.Те, що запит проходить весь індекс цілком - не дивно, тому що поле SubTotal стоїть не на першій позиції, тому запит не може скористатися ним. Проблема вирішується додаванням ще одного індексу на поле SubTotal і за підсумком дає вже всього 48 logical reads.
Можна навести ще кілька прикладів запитів на підрахунок кількості, але суть залишиться такою ж: отримання порції даних та підрахунок загальної кількості – це два принципово різні запитиі кожен вимагає своїх заходів для оптимізації. Загалом не вдасться знайти комбінацію індексів, яка однаково добре працює для обох запитів.
Відповідно одна з важливих вимог, яку слід уточнити при розробці такого пошукового рішення — чи справді бізнесу важливо бачити загальну кількість знайдених об'єктів. Найчастіше буває, що ні. А навігація за конкретними номерами сторінки, на мій погляд, рішення з дуже вузькою сферою застосування, оскільки більшість сценаріїв з пейджингом виглядають як «перейти на наступну сторінку».
Варіант пейджингу #2
Припустимо, користувачам не важливе знання загальної кількості знайдених об'єктів. Спробуємо спростити пошукову сторінку:
За фактом змінилося лише те, що немає можливості переходити за конкретними номерами сторінок, і тепер цій таблиці для відображення не потрібно знати, скільки їх може бути. Але постає питання — а як таблиця дізнається, чи є дані для наступної сторінки (щоб правильно відобразити посилання «Next»)?
Відповідь дуже проста: можна вичитувати з бази на один запис більше, ніж потрібно для відображення, і наявність цього «додаткового» запису буде показувати, чи є наступна порція. Таким чином, для отримання однієї сторінки даних потрібно буде виконати лише один запит, що суттєво покращує продуктивність та полегшує підтримку такої функціональності. У мене на практиці був випадок, коли відмова від підрахунку загальної кількості записів прискорила видачу результатів у 4-5 разів.
Для цього підходу існує кілька варіантів інтерфейсу користувача: команди «назад» і «вперед», як у прикладі вище, кнопка «завантажити ще», яка просто додає нову порцію в відображувані результати, «нескінченна прокрутка», яка працює за принципом «завантажити ще », але сигнал для отримання наступної порції є прокручування користувачем всіх виведених результатів до кінця. Яким би не було візуальне рішення, принцип вибірки даних залишається таким самим.
Нюанси реалізації пейджингу
У всіх прикладах наведених вище запитів використовується підхід «зміщення + кількість», коли в самому запиті вказується з якого по порядку рядка результату і яку кількість рядків потрібно повернути. Спочатку розглянемо, як краще організувати передачу параметрів у цьому випадку. На практиці я зустрічав кілька способів:
- Порядковий номер запитуваної сторінки (pageIndex), розмір сторінки (pageSize).
- Порядковий номер першого запису, який потрібно повернути (startIndex), максимальна кількість записів у результаті (count).
- Порядковий номер першого запису, який потрібно повернути (startIndex), порядковий номер останнього запису, який потрібно повернути (endIndex).
На перший погляд може здатися, що це настільки елементарно, що жодної різниці немає. Але це не так - найбільш зручним та універсальним варіантом є другий (startIndex, count). На це є кілька причин:
- Для підходу з відніманням +1 запису, наведеного вище, перший варіант з pageIndex і pageSize вкрай незручний. Наприклад, ми хочемо відобразити 50 записів на сторінці. Згідно з наведеним вище алгоритмом, потрібно читати на один запис більше, ніж треба. Якщо цей "+1" не закладено на сервері, виходить, що для першої сторінки ми повинні запитувати записи з 1 до 51, для другої - з 51 до 101 і т.д. Якщо вказати розмір сторінки 51 і збільшувати pageIndex, то друга сторінка поверне з 52 до 102 і т.д. Відповідно, у першому варіанті єдиний спосіб нормально реалізувати кнопку переходу на наступну сторінку — закладати на сервері вичитування «зайвого» рядка, що буде дуже неявним нюансом.
- Третій варіант взагалі не має сенсу, тому що для виконання запитів у більшості баз даних все одно потрібно буде передати кількість, а не індекс останнього запису. Нехай віднімання startIndex з endIndex та елементарна арифметична операція, але вона тут зайва.
Тепер слід описати недоліки реалізації пейджингу через «зміщення + кількість»:
- Отримання кожної наступної сторінки буде витратнішим і повільнішим, ніж попередній, тому що базі даних все одно потрібно буде пройти всі записи «з початку» згідно з критеріями пошуку та сортування, після чого зупинитися на потрібному фрагменті.
- Не всі СУБД можуть підтримувати цей підхід.
Альтернативи є, але вони також неідеальні. Перший з таких підходів називається "keyset paging" або "seek method" і полягає в наступному: після отримання порції можна запам'ятовувати значення полів в останній запис на сторінці, а потім використовувати їх для отримання наступної порції. Наприклад, ми виконували такий запит:
SELECT * FROM Sales.SalesOrderHeader
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
І в останньому записі набули значення дати замовлення '2014-06-29'. Тоді для отримання наступної сторінки можна буде спробувати виконати таке:
SELECT * FROM Sales.SalesOrderHeader
WHERE OrderDate < '2014-06-29'
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
Проблема в тому, що OrderDate - унікальне поле і умова, вказана вище, з великою ймовірністю пропустить багато потрібних рядків. Для внесення однозначності в цей запит необхідно додати до умови унікальне поле (припустимо, що 75074 — останнє значення первинного ключа з першої порції):
SELECT * FROM Sales.SalesOrderHeader
WHERE (OrderDate = '2014-06-29' AND SalesOrderID < 75074)
OR (OrderDate < '2014-06-29')
ORDER BY OrderDate DESC, SalesOrderID DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
Цей варіант працюватиме коректно, але у випадку його буде важко оптимізувати, оскільки умова містить оператор OR. Якщо зі зростанням OrderDate зростає значення первинного ключа, то умову можна спростити, залишивши лише фільтр SalesOrderID. Але якщо між значеннями первинного ключа та поля, за яким відсортовано результат, немає суворої кореляції — у більшості СУБД уникнути цього OR не вдасться. Відомим мені винятком є PostgreSQL, де повною мірою підтримується порівняння кортежів, і зазначену вище умову можна записати як "WHERE (OrderDate, SalesOrderID) <('2014-06-29', 75074)". За наявності складеного ключа з цими двома полями такий запит має бути досить легким.
Другий альтернативний підхід можна зустріти, наприклад, або — коли запит, окрім даних, повертає спеціальний ідентифікатор, за допомогою якого можна отримати наступну порцію даних. Якщо цей ідентифікатор має необмежений термін життя (як у Comsos DB), це відмінний спосіб реалізації пейджингу з послідовним переходом між сторінками (варіант #2 згаданий вище). Його можливі недоліки: підтримується далеко не у всіх СУБД; отриманий ідентифікатор наступної порції може мати обмежений термін життя, що не підходить для реалізації взаємодії з користувачем (як, наприклад, ElasticSearch scroll API).
Складна фільтрація
Ускладнюємо завдання далі. Припустимо, виникла вимога продати так званий faceted search, добре всім знайомий по Інтернет-магазинах. Наведені вище приклади на основі таблиці замовлень не дуже показові в цьому випадку, тому перейдемо на таблицю Product з бази AdventureWorks:
У чому ідея faceted search? У тому, що для кожного елемента фільтра відображається кількість записів, які відповідають цьому критерію з урахуванням фільтрів, вибраних у всіх інших категоріях.
Наприклад, якщо ми виберемо в цьому прикладі категорію Bikes та колір Black, таблиця виводитиме лише велосипеди чорного кольору, але при цьому:
- Для кожного критерію групи «Categories» буде показано кількість продуктів із цієї категорії чорного кольору.
- Для кожного критерію групи Colors буде показано число велосипедів цього кольору.
Ось приклад виведення результату для таких умов:
Якщо також відзначити категорію «Clothing», таблиця покаже ще й одяг чорного кольору, який є в наявності. Кількість продуктів чорного кольору в секції «Color» теж буде перерахована згідно з новими умовами, тільки в секції «Categories» нічого не зміниться… Сподіваюся, цих прикладів достатньо, щоб зрозуміти звичний алгоритм роботи faceted search.
Тепер уявімо, як це можна реалізувати на реляційній базі. Кожна група критеріїв, така як Category та Color, вимагатиме окремого запиту:
SELECT pc.ProductCategoryID, pc.Name, COUNT(1) FROM Production.Product p
INNER JOIN Production.ProductSubcategory ps ON p.ProductSubcategoryID = ps.ProductSubcategoryID
INNER JOIN Production.ProductCategory pc ON ps.ProductCategoryID = pc.ProductCategoryID
WHERE p.Color = 'Black'
GROUP BY pc.ProductCategoryID, pc.Name
ORDER BY COUNT(1) DESC
SELECT Color, COUNT(1) FROM Production.Product p
INNER JOIN Production.ProductSubcategory ps ON p.ProductSubcategoryID = ps.ProductSubcategoryID
WHERE ps.ProductCategoryID = 1 --Bikes
GROUP BY Color
ORDER BY COUNT(1) DESC
Що ж не так із цим рішенням? Дуже просто воно погано масштабується. Кожна секція фільтра вимагає окремого запиту для підрахунку кількостей і ці запити не найлегші. В інтернет-магазинах в деяких рубриках може бути кілька десятків секцій фільтра, що може виявитися серйозною проблемою для продуктивності.
Зазвичай після цих тверджень мені пропонують деякі рішення, а саме:
- Поєднати всі підрахунки кількості в один запит. Технічно це можливо за допомогою ключового слова UNION, тільки продуктивності це не дуже допоможе - базі даних все одно доведеться виконати "з нуля" кожен із фрагментів.
- Кешувати кількості. Це мені пропонують практично щоразу, коли я описую проблему. Нюанс у тому, що це взагалі неможливо. Припустимо, ми маємо 10 «фасетів», у кожному з яких 5 значень. Це дуже «скромна» ситуація на тлі того, що можна побачити у тих самих інтернет-магазинах. Вибір одного елемента фасета впливає на кількості в 9 інших, іншими словами, для кожної комбінації критеріїв кількості можуть бути різними. Усього в нашому прикладі 50 критеріїв, які користувач може вибрати, відповідно до можливих комбінацій буде 250. На заповнення такого масиву даних не вистачить ні пам'яті, ні часу. Тут можна заперечити і сказати, що не всі комбінації реальні і користувач рідко вибере більше 5-10 критеріїв. Так, можна зробити ліниве завантаження та кешування кількості тільки для того, що коли-небудь було обрано, але чим більше буде варіантів вибору, тим менш ефективним буде такий кеш і тим помітнішими будуть проблеми з часом відгуку (особливо якщо набір даних регулярно змінюється) .
На щастя, подібне завдання вже давно має досить ефективні рішення, які передбачають на великих обсягах даних. Для будь-якого з цих варіантів має сенс розділити перерахунок фасетів та отримання сторінки результатів на два паралельні звернення до сервера та організувати інтерфейс користувача таким чином, що завантаження даних по фасетах «не заважає» відображенню результатів пошуку.
- Викликати повний перерахунок «фасетів» якомога рідше. Наприклад, не перераховувати все на кожній зміні критеріїв пошуку, а натомість знаходити загальну кількість результатів, що відповідають поточним умовам, та пропонувати користувачеві їх показати — «1425 записів знайдено, показати?» Користувач може або продовжити змінювати умови пошуку або натиснути кнопку «показати». Тільки у другому випадку будуть виконані всі запити щодо отримання результатів та перерахунку кількостей на всіх «фасетах». При цьому, як неважко зауважити, доведеться мати справу із запитом на отримання загальної кількості результатів та його оптимізацією. Цей спосіб можна зустріти у багатьох невеликих інтернет-магазинах. Очевидно, що це не панацея для цієї проблеми, але у простих випадках може бути непоганим компромісом.
- Використовувати search engine для пошуку результатів та підрахунку фасетів, таких як Solr, ElasticSearch, Sphinx та інші. Всі вони розраховані на побудову "фасетів" і роблять це досить ефективно за рахунок інвертованого індексу. Як влаштовані пошукові системи, чому вони в таких випадках ефективніші за бази даних загального призначення, які є практики та підводні камені — це тема для окремої статті. Тут же я хочу звернути увагу, що search engine не може бути заміною основного сховища даних, використовується він як доповнення: будь-які зміни в основній базі, які мають значення для пошуку, синхронізуються в пошуковий індекс; Механізм пошуку взаємодіє зазвичай лише з search engine і не звертається до основної бази. Один із найважливіших моментів тут — як організувати цю синхронізацію надійно. Все залежить від вимог до «часу реакції». Якщо час між зміною в основній базі та його «проявом» у пошуку не критичний, можна зробити сервіс, який раз на кілька хвилин шукає недавно змінені записи та їх індексує. Якщо потрібний мінімально можливий час реакції, можна реалізувати щось типу для надсилання оновлень у пошуковий сервіс.
Висновки
- p align="justify"> Реалізація пейджингу на стороні сервера - серйозне ускладнення, і застосовувати його має сенс тільки для швидкозростаючих або просто великих наборів даних. Як оцінити «великий» чи «швидкозростаючий» — абсолютно точного рецепту немає, але я дотримувався б такого підходу:
- Якщо отримання повної колекції даних з урахуванням серверного часу та передачі по мережі нормально вкладається у вимоги щодо продуктивності – реалізовувати пейджинг на стороні сервера немає сенсу.
- Можливо така ситуація, що найближчим часом проблем із продуктивністю не передбачається, оскільки даних мало, але колекція даних постійно зростає. Якщо якийсь набір даних у перспективі може перестати задовольняти попередній пункт — краще закласти пейджинг відразу.
- Якщо з боку бізнесу немає жорсткої вимоги щодо показу загальної кількості результатів або відображення номерів сторінок, і при цьому у вашій системі немає пошукового движка — краще ці моменти не реалізовувати і розглядати варіант #2.
- Якщо є чітка вимога про faceted search, у вас є два варіанти не пожертвувати продуктивністю:
- Не перераховувати всі кількості на кожній зміні критеріїв пошуку.
- Використовувати search engine, такі як Solr, ElasticSearch, Sphinx та інші. Але слід розуміти, що він не може бути заміною основної бази даних і повинен використовуватися як доповнення до основного сховища для вирішення пошукових завдань.
- Також у разі faceted search має сенс розділити отримання сторінки результатів пошуку та підрахунок кількостей на два паралельні запити. Підрахунок кількостей може зайняти більший час, ніж отримання результатів, тоді як результати важливіші для користувача.
- Якщо ви використовуєте SQL базу для пошуку, будь-яка зміна коду, що стосується цієї частини, має добре тестуватися щодо продуктивності на відповідному об'ємі даних (перевищує обсяг у «живій» базі). Бажано також використовувати моніторинг часу виконання запитів на всіх екземплярах бази, і особливо на «живому». Навіть якщо на етапі розробки із планами запитів все було добре, зі зростанням обсягу даних ситуація може помітно змінитись.
Джерело: habr.com