🥇Резултати от търсенето и проблеми с производителността

Един от типичните сценарии в приложенията, които използваме, е търсенето на данни по определени критерии и представянето им в лесно четим формат. Тук могат да се добавят и допълнителни функции за сортиране, групиране и странично извеждане. Задачата изглежда проста, но при нейното решаване много разработчици допускат редица грешки, които след това влияят на производителността. Нека разгледаме различни варианти за решаване на тази задача и формулираме препоръки за избор на най-ефективната реализация.

Вариант за странициране #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 последни поръчки.

Изпълнява се бързо на тестовата база, но нека погледнем плана за изпълнение и статистиката за вход/изход:

Таблица 'SalesOrderHeader'. Брой сканирания 1, логически четения 698, физически четения 0, четения за предварителна подготовка 0, логически четения на LOB 0, физически четения на LOB 0, четения за предварителна подготовка на LOB 0.

Статистиката за вход/изход за всяка заявка може да бъде получена, като изпълните командата SET STATISTICS IO ON в средата за изпълнение на заявки.

Както се вижда от плана за изпълнение, най-ресурсно-интензивната операция е сортирането на всички редове от началната таблица по дата на добавяне. Проблемът е, че колкото повече редове се добавят в таблицата, толкова „по-тежка“ става сортирането. На практика трябва да се избягват такива ситуации, затова ще добавим индекс по дата на добавяне и ще видим дали е променено потреблението на ресурси:

Таблица 'SalesOrderHeader'. Брой сканирания 1, логически четения 165, физически четения 0, четения за предварителна подготовка 5, логически четения на LOB 0, физически четения на LOB 0, четения за предварителна подготовка на LOB 0.

Очевидно, стана значително по-добре. Но решени ли са всички проблеми? Нека променим заявката за търсене на поръчки, където общата стойност на продуктите надвишава 100 долара:

SELECT * FROM Sales.SalesOrderHeader
WHERE SubTotal > 100
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY

Таблица 'SalesOrderHeader'. Брой на скановете 1, логически четения 1081, физически четения 0, четения за предварителен преглед 0, логически четения за LOB 0, физически четения за LOB 0, четения за предварителен преглед на LOB 0.

Имаме забавна ситуация: планът на заявката не е много по-лош от предишния, но фактическото количество логически четения е почти двойно по-голямо от при пълно сканиране на таблицата. Има изход — ако направим съществуващия индекс съставен и добавим сумарната цена на продуктите като второ поле, отново ще получим 165 логически четения:

CREATE INDEX IX_SalesOrderHeader_OrderDate_SubTotal on Sales.SalesOrderHeader(OrderDate, SubTotal);

Тази серия примери може да продължи дълго, но две основни мисли, които искам да изразя тук, са:

Добавянето на нов критерий или ред на сортиране в търсенето може да повлияе значително на скоростта на изпълнението му.
Но ако ни е необходимо да изтеглим само част от данните, а не всичките резултати, отговарящи на условията на търсенето — има много начини да оптимизираме такава заявка.

Сега да преминем към втората заявка, спомената в самото начало — тази, която преброява броя записи, отговарящи на критериите за търсене. Нека вземем същия пример — търсене на поръчки, които струват повече от 100 долара:

SELECT COUNT(1) FROM Sales.SalesOrderHeader
WHERE SubTotal > 100

При наличието на съставен индекс, посочен по-горе, получаваме:

Таблица 'SalesOrderHeader'. Брой сканирания 1, логически четения 698, физически четения 0, четения за предварителна подготовка 0, логически четения на LOB 0, физически четения на LOB 0, четения за предварителна подготовка на LOB 0.

Не е изненада, че заявката минава през целия индекс, тъй като полето SubTotal не е на първа позиция, затова заявката не може да се възползва от него. Проблемът се решава с добавянето на още един индекс на полето SubTotal, и в крайна сметка даваме само 48 логически четения.

Може да се приведат още няколко примера за заявки за преброяване, но същността остава същата: Получаването на част от данните и преброяването на общия брой — това са две коренно различни заявки, и всяка изисква свои мерки за оптимизация. В общия случай не може да се намери комбинация от индекси, която работи еднакво добре за двете заявки.

Следователно, едно от важните изисквания, които трябва да се уточнят при разработката на такова търсещо решение, е дали на бизнеса е важно да вижда общия брой намерени обекти. Често се оказва, че не е. А навигацията по конкретни номера на страници, според мен, е решение с много тясна област на приложение, тъй като повечето сценарии с странициране изглеждат като „премини на следващата страница“.

Опция за странициране #2

Предположим, че на потребителите не им е важно да знаят общия брой намерени обекти. Нека опитаме да опростим страницата за търсене:

По същество се е променило само това, че няма възможност за преминаване по конкретни номера на страници, и сега на тази таблица за показване не е нужно да знае колко общо могат да бъдат. Но възниква въпросът — как таблицата ще разбере дали има данни за следващата страница (за да покаже правилната връзка „Следваща“)?

Отговорът е много прост: можете да изтеглите от базата данни с една запис повече, отколкото е необходимо за показване, и наличието на този „допълнителен“ запис ще покаже дали има следваща порция. По този начин, за получаване на една страница данни, ще е необходимо да се извърши само едно запитване, което съществено подобрява производителността и улеснява поддръжката на такава функционалност. В практиката ми имах случай, когато отказът от преброяване на общия брой записи ускори получаването на резултати 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, споменат по-горе). Неговите възможни недостатъци: не се поддържа в много СУБД; полученото ID на следващата порция може да има ограничен срок на живот, което в общия случай не е подходящо за реализиране на взаимодействие с потребителя (както например, 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 записа, показване?». Потребителят може или да продължи да променя условията за търсене, или да натисне бутона «показване». Само в втория случай ще се извършат всички заявки за получаване на резултати и преразглеждане на количествата на всички «фасети». При това, както не е трудно да се види, ще трябва да се справите със заявка за получаване на общия брой резултати и неговата оптимизация. Този метод може да се срещне в много малки онлайн магазини. Очевидно е, че това не е панацея за проблема, но в простите случаи може да бъде разумен компромис.
Използвайте търсачка за намиране на резултати и броене на фасети, като Solr, ElasticSearch, Sphinx и други. Всички те са проектирани да изграждат «фасети» и го правят доста ефективно благодарение на обърнатия индекс. Как функционират търсачките, защо в такива случаи те са по-ефективни от общите бази данни, какви са практиките и подводните камъни — това е тема за отделна статия. Тук искам да подчертая, че търсачката не може да бъде заместител на основното хранилище на данни; тя се използва като допълнение: всяка промяна в основната база, която е от значение за търсенето, се синхронизира в търсачния индекс; механизмът за търсене обикновено взаимодействuje само с търсачката и не се обръща към основната база. Един от най-важните моменти тук е как надеждно да се организира тази синхронизация. Всичко зависи от изискванията за «време на реакция». Ако времето между промяната в основната база и нейното «проявление» в търсенето не е критично, може да се направи услуга, която на всеки няколко минути търси наскоро променени записи и ги индексира. Ако се изисква минимално възможно време на реакция, може да се реализира нещо като транзакционен изходящ канал за изпращане на актуализации в търсачката.

Изводи

Реализация на сървъра на пейджинг е сложно усложнение и има смисъл да се прилага само за бързо растящи или просто големи набори от данни. Как да оценим какво е "голямо" или "бързо растящо" — не съществува абсолютно точна рецепта, но аз бих следвал този подход:
- Ако получаването на целия набор от данни с оглед на времето на сървъра и предаването по мрежата отговаря на изискванията за производителност, реализирането на пейджинг на сървъра няма смисъл.
- Може да настъпи ситуация, в която в близко бъдеще не се предвиждат проблеми с производителността, тъй като данните са малко, но наборът от данни постоянно расте. Ако някой набор от данни в перспектива може да спре да отговаря на предишната точка — по-добре е да се предвиди пейджинг от самото начало.
Ако от страна на бизнеса няма строги изисквания за показване на общия брой резултати или за показване на номера на страниците, и в същото време вашата система няма търсачка — по-добре е да не реализирате тези моменти и да разгледате вариант #2.
Ако има ясно изискване за faceted search, имате две опции, за да не жертвате производителността:
- Да не се преразпределят всички количества при всяка промяна на критериите за търсене.
- Да се използват търсачки като Solr, ElasticSearch, Sphinx и други. Но трябва да се разбира, че тя не може да замести основната база данни и трябва да се използва като допълнение към основното хранилище за решаване на търсачески задачи.
Също така, в случай на faceted search, има смисъл да се раздели получаването на страницата с резултатите от търсенето и изчисляването на количествата на две паралелни заявки. Изчисляването на количествата може да отнеме повече време, отколкото получаването на резултатите, докато резултатите са по-важни за потребителя.
Ако използвате SQL база за търсене, всяка промяна в кода, свързана с тази част, трябва да бъде добре тествана по отношение на производителността на съответния обем от данни (надвишаващ обема в "живата" база). Също така е желателно да се използва мониторинг на времето за изпълнение на заявките на всички инстанции на базата, и особено — на "живата". Дори ако по време на разработката с плановете за заявки всичко е било наред, с увеличаването на обема на данните ситуацията може да се промени значително.

Източник: habr.com