Вивід результатів пошуку та проблеми з продуктивністю

Івон Юрій

Senior Solution Architect, EPAM

22/03/2021

Лайфхаки

Solution Architecture

Одним з типових сценаріїв у всіх звичних нам додатках є пошук даних за певними критеріями і виведення їх в зручному для читання вигляді. Тут також можуть бути додаткові можливості з сортування, групування, посторінкового виводу. Задача, здавалося б, тривіальна, але під час її вирішення багато розробників роблять низку помилок, через які згодом знижується продуктивність. Спробуємо розглянути різні варіанти рішень цього завдання і сформулювати рекомендації щодо вибору найефективнішої реалізації.

Варіант пейджингу #1

Найпростіше рішення, яке лежить на поверхні - це посторінковий вивід результатів пошуку в його класичному вигляді.

Припустимо, в додатку використовується реляційна база даних. Отже, для виведення інформації в такому вигляді потрібно буде виконати два SQL запити:
Отримати рядки для поточної сторінки.
Порахувати загальну кількість рядків, які відповідають критеріям пошуку - це потрібно для показу сторінок.
Розглянемо перший запит на прикладі тестової MS SQL бази AdventureWorks для 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)». За наявності складеного ключа з цими двома полями подібний запит повинен бути доволі легким.

Другий альтернативний підхід можна побачити, наприклад, в ElasticSearch scroll API або Cosmos DB - коли запит крім даних повертає спеціальний ідентифікатор, за допомогою якого можна отримати наступну порцію даних. Якщо цей ідентифікатор має необмежений термін життя (як в 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 та не звертається до основної бази. Один з найважливіших моментів – це надійна організація синхронізації. Все залежить від вимог до «часу реакції». Якщо час між зміною в основній базі та його «проявом» в пошуку не критичний, можна зробити сервіс, який з періодичністю в кілька хвилин шукає нещодавно змінені записи та індексує їх. Якщо потрібен мінімально можливий час реакції, можна реалізувати щось на кшталт transactional outbox для відправки оновлень в пошуковий сервіс.

Висновки

1. Реалізація пейджінгу на боці сервера - значне ускладнення, і застосовувати його варто лише для швидкозростаючих або великих наборів даних. Як визначити «великий» або «швидко зростаючий» - точного рецепта немає, але я раджу дотримуватися наступного підходу.

Якщо отримання повної колекції даних з урахуванням серверного часу і передачі по мережі вкладається в вимоги до продуктивності – немає сенсу реалізовувати пейджинг на боці сервера.
Може мати місце ситуація, що на найближчий час проблем з продуктивністю не передбачається, оскільки даних мало, але колекція даних постійно зростає. Якщо якийсь набір даних в перспективі може перестати задовольняти умови попереднього пункту, тоді пейджинг варто закласти відразу.

2. Якщо з боку бізнесу немає жорсткої вимоги щодо показу загальної кількості результатів або відображення номерів сторінок, і при цьому у вашій системі немає пошукового движка - краще ці моменти не реалізовувати і розглядати варіант # 2.

3. Якщо є чітка вимога щодо faceted search, у вас є два варіанти як не втратити продуктивність:

Не рахувати повторно всі кількості під час кожної зміні критеріїв пошуку.
Використовувати search engine такі як Solr, ElasticSearch, Sphinx тощо. Але слід розуміти, що вони не може бути заміною основній базі даних, і повинні використовуватися як доповнення до основного сховища для вирішення пошукових задач.

4. Також у випадку faceted search має сенс розділити отримання сторінки результатів пошуку і підрахунок кількостей на два паралельних запити. Підрахунок кількостей може тривати довше, ніж отримання результатів, в той час як результати важливіші для користувача.

5. Якщо ви використовуєте SQL базу для пошуку, будь-яка зміна коду, що стосується цієї частини, має добре тестуватися на продуктивність на певному обсязі даних (більшому за обсяг в «живій» базі). Бажано також використовувати моніторинг часу виконання запитів на всіх примірниках бази, а особливо - на «живому». Навіть якщо на етапі розробки з планами запитів все було добре, зі збільшенням обсягу даних ситуація може помітно змінюватися.

Вивід результатів пошуку та проблеми з продуктивністю

Івон Юрій

Варіант пейджингу #1

Варіант пейджингу #2

Нюанси реалізації пейджингу

Складна фільтрація

Висновки

Огляд та Виклики ITIL: оптимізація підтримки застосунків та пріоритизація інцидентів

Як зробити документи Word доступними для всіх

Як не потонути під час планування дата-інжинірингового продукту

Ефективна підготовка до сертифікацій PSM I та PSK I: лайфхаки та особистий досвід

Олександра Серебрянська, Senior Business Analyst в EPAM: про світчинг, ВА-спільноту, кар’єрні плани та дозвілля