Jedním z typických scénářů ve všech aplikacích, které známe, je vyhledávání dat podle určitých kritérií a jejich zobrazení ve snadno čitelné podobě. Mohou existovat také další možnosti pro řazení, seskupování a stránkování. Úkol je to teoreticky triviální, ale při jeho řešení se mnoho vývojářů dopouští řady chyb, které později způsobují utrpení produktivity. Pokusme se zvážit různé možnosti řešení tohoto problému a formulovat doporučení pro výběr nejúčinnější implementace.
Možnost stránkování #1
Nejjednodušší možností, která vás napadne, je zobrazení výsledků vyhledávání po jednotlivých stránkách v té nejklasičtější podobě.
Řekněme, že vaše aplikace používá relační databázi. V tomto případě pro zobrazení informací v tomto formuláři budete muset spustit dva SQL dotazy:
- Získat řádky pro aktuální stránku.
- Vypočítejte celkový počet řádků odpovídajících vyhledávacím kritériím - to je nutné pro zobrazení stránek.
Podívejme se jako příklad na první dotaz pomocí testovací databáze MS SQL pro server 2016. Pro tento účel použijeme tabulku Sales.SalesOrderHeader:
SELECT * FROM Sales.SalesOrderHeader
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
Výše uvedený dotaz vrátí prvních 50 objednávek ze seznamu seřazených podle sestupného data přidání, jinými slovy 50 nejnovějších objednávek.
Na testovací základně běží rychle, ale podívejme se na plán provádění a statistiky I/O:
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.Statistiku I/O pro každý dotaz můžete získat spuštěním příkazu SET STATISTICS IO ON v modulu runtime dotazu.
Jak můžete vidět z plánu provádění, nejnáročnější možností je seřadit všechny řádky zdrojové tabulky podle data přidání. A problém je v tom, že čím více řádků se v tabulce objeví, tím „těžší“ bude řazení. V praxi je třeba se takovým situacím vyhnout, proto přidejte index k datu přidání a zjistěte, zda se spotřeba zdrojů změnila:
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.
Evidentně se to hodně zlepšilo. Jsou ale všechny problémy vyřešeny? Změňme dotaz na vyhledávání objednávek, kde celková cena zboží přesahuje 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.Máme vtipnou situaci: plán dotazů není o moc horší než předchozí, ale skutečný počet logických čtení je téměř dvakrát větší než při úplném skenování tabulky. Existuje cesta ven - pokud vytvoříme složený index z již existujícího indexu a přidáme celkovou cenu zboží jako druhé pole, dostaneme opět 165 logických čtení:
CREATE INDEX IX_SalesOrderHeader_OrderDate_SubTotal on Sales.SalesOrderHeader(OrderDate, SubTotal);
V této sérii příkladů lze pokračovat ještě dlouho, ale dvě hlavní myšlenky, které zde chci vyjádřit, jsou:
- Přidání jakéhokoli nového kritéria nebo pořadí řazení k vyhledávacímu dotazu může mít významný dopad na rychlost vyhledávacího dotazu.
- Pokud ale potřebujeme odečíst pouze část dat a ne všechny výsledky, které odpovídají hledaným výrazům, existuje mnoho způsobů, jak takový dotaz optimalizovat.
Nyní přejděme k druhému dotazu zmíněnému na samém začátku – k tomu, který počítá počet záznamů splňujících vyhledávací kritérium. Vezměme si stejný příklad – vyhledávání objednávek, které jsou vyšší než 100 USD:
SELECT COUNT(1) FROM Sales.SalesOrderHeader
WHERE SubTotal > 100
Vzhledem ke složenému indexu uvedenému výše získáme:
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.Skutečnost, že dotaz prochází celým indexem, není překvapivá, protože pole Mezisoučet není na první pozici, takže jej dotaz nemůže použít. Problém je vyřešen přidáním dalšího indexu do pole Mezisoučet a výsledkem je pouze 48 logických čtení.
Můžete uvést několik dalších příkladů požadavků na počítání množství, ale podstata zůstává stejná: přijetí kusu dat a započítání celkové částky jsou dva zásadně odlišné požadavkya každý z nich vyžaduje svá vlastní optimalizační opatření. Obecně platí, že nebudete schopni najít kombinaci indexů, která by fungovala stejně dobře pro oba dotazy.
Jedním z důležitých požadavků, které by měly být při vývoji takového vyhledávacího řešení objasněny, je tedy to, zda je pro podnik skutečně důležité vidět celkový počet nalezených objektů. Často se stává, že ne. A navigace podle konkrétních čísel stránek je podle mého názoru řešením s velmi úzkým rozsahem, protože většina scénářů stránkování vypadá jako „přejít na další stránku“.
Možnost stránkování #2
Předpokládejme, že uživatelům nezáleží na tom, aby znali celkový počet nalezených objektů. Zkusme zjednodušit stránku vyhledávání:
Ve skutečnosti se změnilo pouze to, že neexistuje způsob, jak přejít na konkrétní čísla stránek, a tato tabulka nyní nepotřebuje vědět, kolik jich může být, aby je mohla zobrazit. Vyvstává však otázka - jak tabulka ví, zda existují data pro další stránku (aby se správně zobrazil odkaz „Další“)?
Odpověď je velmi jednoduchá: z databáze můžete načíst o jeden záznam více, než je potřeba pro zobrazení, a přítomnost tohoto „dodatečného“ záznamu ukáže, zda existuje další část. Tímto způsobem stačí spustit jeden požadavek, abyste získali jednu stránku dat, což výrazně zlepšuje výkon a usnadňuje podporu takové funkce. V mé praxi se vyskytl případ, kdy odmítnutí započítání celkového počtu záznamů zrychlilo doručení výsledků 4-5x.
Pro tento přístup existuje několik možností uživatelského rozhraní: příkazy „zpět“ a „vpřed“, jako ve výše uvedeném příkladu, tlačítko „načíst více“, které jednoduše přidá k zobrazeným výsledkům novou část, „nekonečné posouvání“, které funguje na principu "načíst více" ", ale signálem k získání další části je, aby uživatel posouval všechny zobrazené výsledky až do konce. Bez ohledu na vizuální řešení zůstává princip vzorkování dat stejný.
Nuance implementace stránkování
Všechny výše uvedené příklady dotazů používají přístup „offset + počet“, kdy samotný dotaz určuje, v jakém pořadí budou řádky výsledků a kolik řádků je třeba vrátit. Nejprve se podívejme, jak v tomto případě nejlépe uspořádat předávání parametrů. V praxi jsem se setkal s několika způsoby:
- Sériové číslo požadované stránky (pageIndex), velikost stránky (pageSize).
- Pořadové číslo prvního vráceného záznamu (startIndex), maximální počet záznamů ve výsledku (count).
- Pořadové číslo prvního záznamu, který má být vrácen (startIndex), pořadové číslo posledního záznamu, který má být vrácen (endIndex).
Na první pohled se může zdát, že je to tak elementární, že v tom není žádný rozdíl. Ale není tomu tak - nejpohodlnější a nejuniverzálnější možností je druhá (startIndex, count). Důvodů je několik:
- U výše uvedeného přístupu korektury +1 je první možnost s pageIndex a pageSize extrémně nepohodlná. Chceme například zobrazit 50 příspěvků na stránku. Podle výše uvedeného algoritmu musíte přečíst o jeden záznam více, než je nutné. Pokud toto „+1“ není na serveru implementováno, ukáže se, že pro první stránku musíme požadovat záznamy od 1 do 51, pro druhou - od 51 do 101 atd. Pokud zadáte velikost stránky 51 a zvýšíte pageIndex, vrátí se druhá stránka z 52 na 102 atd. Podle první možnosti je tedy jediným způsobem, jak správně implementovat tlačítko pro přechod na další stránku, nechat server zkontrolovat řádek „extra“, což bude velmi implicitní nuance.
- Třetí možnost nedává vůbec smysl, protože pro spouštění dotazů ve většině databází budete stále muset předat počet, nikoli index posledního záznamu. Odečítání startIndex od endIndex může být jednoduchá aritmetická operace, ale zde je nadbytečná.
Nyní bychom měli popsat nevýhody implementace stránkování pomocí „offset + množství“:
- Načítání každé následující stránky bude dražší a pomalejší než předchozí, protože databáze bude stále muset projít všechny záznamy „od začátku“ podle kritérií vyhledávání a řazení a poté se zastavit na požadovaném fragmentu.
- Ne všechny DBMS mohou tento přístup podporovat.
Existují alternativy, ale také nedokonalé. První z těchto přístupů se nazývá „stránkování sady klíčů“ nebo „metoda vyhledávání“ a je následující: po obdržení části si můžete zapamatovat hodnoty polí v posledním záznamu na stránce a poté je použít k získání další část. Spustili jsme například následující dotaz:
SELECT * FROM Sales.SalesOrderHeader
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
A v posledním záznamu jsme dostali hodnotu data objednávky '2014-06-29'. Chcete-li získat další stránku, můžete zkusit provést toto:
SELECT * FROM Sales.SalesOrderHeader
WHERE OrderDate < '2014-06-29'
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
Problém je v tom, že Datum objednávky je nejedinečné pole a výše uvedená podmínka pravděpodobně vynechá mnoho požadovaných řádků. Chcete-li do tohoto dotazu přidat jednoznačnost, musíte do podmínky přidat jedinečné pole (předpokládejme, že 75074 je poslední hodnotou primárního klíče z první části):
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
Tato možnost bude fungovat správně, ale obecně bude obtížné ji optimalizovat, protože podmínka obsahuje operátor OR. Pokud se hodnota primárního klíče zvyšuje se zvyšujícím se datem objednávky, lze podmínku zjednodušit ponecháním pouze filtru podle SalesOrderID. Pokud však neexistuje přísná korelace mezi hodnotami primárního klíče a polem, podle kterého je výsledek seřazen, nelze se tomuto NEBO ve většině DBMS vyhnout. Výjimku, o které vím, je PostgreSQL, který plně podporuje porovnávání n-tic a výše uvedenou podmínku lze zapsat jako "WHERE (Datum objednávky, ID objednávky) < ('2014-06-29', 75074)". Vzhledem ke složenému klíči s těmito dvěma poli by měl být dotaz jako tento poměrně snadný.
Druhý alternativní přístup lze nalézt např nebo — když požadavek kromě dat vrací speciální identifikátor, pomocí kterého můžete získat další část dat. Pokud má tento identifikátor neomezenou životnost (jako v Comsos DB), pak je to skvělý způsob, jak implementovat stránkování se sekvenčním přechodem mezi stránkami (možnost #2 zmíněná výše). Jeho možné nevýhody: není podporován ve všech DBMS; výsledný identifikátor dalšího bloku může mít omezenou životnost, což obecně není vhodné pro implementaci uživatelské interakce (jako je ElasticSearch scroll API).
Komplexní filtrování
Pojďme si úkol dále zkomplikovat. Předpokládejme, že existuje požadavek na implementaci tzv. fasetovaného vyhledávání, které je všem velmi dobře známé z internetových obchodů. Výše uvedené příklady vycházející z tabulky objednávek nejsou v tomto případě příliš ilustrativní, přejděme tedy na tabulku Produkt z databáze AdventureWorks:
Jaká je myšlenka fasetovaného hledání? Faktem je, že pro každý filtrační prvek je uveden počet záznamů, které splňují toto kritérium s přihlédnutím k filtrům vybraným ve všech ostatních kategoriích.
Pokud například v tomto příkladu vybereme kategorii Kola a barvu Černá, tabulka zobrazí pouze černá kola, ale:
- Pro každé kritérium ve skupině Kategorie bude počet produktů z dané kategorie zobrazen černě.
- Pro každé kritérium skupiny „Barvy“ se zobrazí počet kol této barvy.
Zde je příklad výstupu výsledku pro takové podmínky:
Pokud zaškrtnete i kategorii „Oblečení“, v tabulce se zobrazí i černé oblečení, které je skladem. Počet černých produktů v sekci „Barva“ bude také přepočítán podle nových podmínek, pouze v sekci „Kategorie“ se nic nezmění... Doufám, že tyto příklady postačí k pochopení obvyklého fasetového vyhledávacího algoritmu.
Nyní si představme, jak to lze realizovat na relační bázi. Každá skupina kritérií, jako je Kategorie a Barva, bude vyžadovat samostatný dotaz:
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
Co je na tomto řešení špatného? Je to velmi jednoduché – špatně se měří. Každá sekce filtru vyžaduje samostatný dotaz pro výpočet množství a tyto dotazy nejsou nejjednodušší. V internetových obchodech mohou mít některé kategorie několik desítek sekcí filtru, což může být vážný problém s výkonem.
Obvykle po těchto prohlášeních se mi nabízí některá řešení, a to:
- Spojte všechny počty množství do jednoho dotazu. Technicky je to možné pomocí klíčového slova UNION, ale výkonu to moc nepomůže – databáze bude muset stále provádět každý z fragmentů od začátku.
- Množství mezipaměti. To se mi navrhuje téměř pokaždé, když popisuji problém. Upozornění je, že to obecně není možné. Řekněme, že máme 10 „fazet“, z nichž každá má 5 hodnot. To je velmi „skromná“ situace ve srovnání s tím, co lze vidět ve stejných internetových obchodech. Volba jednoho fasetového prvku ovlivňuje veličiny v 9 dalších, jinými slovy, pro každou kombinaci kritérií mohou být veličiny různé. V našem příkladu existuje celkem 50 kritérií, která si uživatel může vybrat, takže možných kombinací bude 250. Na naplnění takového pole dat není dostatek paměti ani času. Zde můžete namítnout a říci, že ne všechny kombinace jsou skutečné a uživatel málokdy vybere více než 5-10 kritérií. Ano, je možné provádět líné načítání a ukládat do mezipaměti množství pouze toho, co bylo kdy vybráno, ale čím více výběrů bude, tím méně efektivní bude taková mezipaměť a tím znatelnější budou problémy s dobou odezvy (zejména soubor dat se pravidelně mění).
Naštěstí má takový problém už dávno docela účinná řešení, která fungují předvídatelně na velkých objemech dat. Pro kteroukoli z těchto možností má smysl rozdělit přepočet faset a příjem stránky s výsledky na dvě paralelní volání na server a uspořádat uživatelské rozhraní tak, aby načítání dat podle faset „nerušilo“ zobrazení Výsledky vyhledávání.
- Kompletní přepočet „fazet“ volejte co nejméně. Například nepřepočítávejte vše pokaždé, když se změní vyhledávací kritéria, ale místo toho vyhledejte celkový počet výsledků, které odpovídají aktuálním podmínkám, a vyzvěte uživatele, aby je ukázal – „1425 záznamů nalezeno, zobrazit?“ Uživatel může buď pokračovat ve změně hledaných výrazů, nebo kliknout na tlačítko „zobrazit“. Pouze ve druhém případě budou vyřízeny všechny požadavky na získání výsledků a přepočet množství na všech „fazetách“. V tomto případě, jak snadno uvidíte, budete muset řešit požadavek na získání celkového počtu výsledků a jeho optimalizaci. Tento způsob lze nalézt v mnoha malých internetových obchodech. Je zřejmé, že to není všelék na tento problém, ale v jednoduchých případech to může být dobrý kompromis.
- Použijte vyhledávače k nalezení výsledků a počítání aspektů, jako je Solr, ElasticSearch, Sphinx a další. Všechny jsou navrženy tak, aby stavěly „fazety“ a dělaly to docela efektivně díky obrácenému indexu. Jak fungují vyhledávače, proč jsou v takových případech efektivnější než univerzální databáze, jaké tam jsou praktiky a úskalí – to je téma na samostatný článek. Zde upozorňuji na skutečnost, že vyhledávač nemůže nahradit hlavní datové úložiště, slouží jako doplněk: veškeré změny v hlavní databázi relevantní pro vyhledávání se synchronizují do vyhledávacího indexu; Vyhledávač obvykle komunikuje pouze s vyhledávačem a nemá přístup k hlavní databázi. Jedním z nejdůležitějších bodů je, jak tuto synchronizaci spolehlivě zorganizovat. Vše závisí na požadavcích na „dobu reakce“. Pokud není doba mezi změnou v hlavní databázi a jejím „projevem“ ve vyhledávání kritická, můžete vytvořit službu, která každých pár minut vyhledává nedávno změněné záznamy a indexuje je. Pokud chcete co nejkratší dobu odezvy, můžete implementovat něco jako k odesílání aktualizací vyhledávací službě.
Závěry
- Implementace stránkování na straně serveru je významnou komplikací a má smysl pouze pro rychle rostoucí nebo jednoduše velké soubory dat. Neexistuje žádný absolutně přesný recept, jak hodnotit „velký“ nebo „rychle rostoucí“, ale držel bych se tohoto přístupu:
- Pokud příjem kompletního souboru dat s přihlédnutím k času serveru a síťovému přenosu normálně vyhovuje požadavkům na výkon, nemá smysl implementovat stránkování na straně serveru.
- Může nastat situace, kdy se v blízké budoucnosti neočekávají žádné problémy s výkonem, protože dat je málo, ale sběr dat neustále roste. Pokud některá sada dat v budoucnu již nemusí splňovat předchozí bod, je lepší začít se stránkováním hned.
- Pokud ze strany podniku neexistuje žádný striktní požadavek na zobrazení celkového počtu výsledků nebo zobrazení čísel stránek a váš systém nemá vyhledávač, je lepší tyto body neimplementovat a zvážit možnost #2.
- Pokud existuje jasný požadavek na vyhledávání tváří, máte dvě možnosti, aniž byste obětovali výkon:
- Nepřepočítávejte všechna množství pokaždé, když se změní vyhledávací kritéria.
- Používejte vyhledávače jako Solr, ElasticSearch, Sphinx a další. Je však třeba chápat, že nemůže být náhradou za hlavní databázi a měl by být používán jako doplněk hlavního úložiště pro řešení problémů s vyhledáváním.
- V případě fasetovaného vyhledávání má také smysl rozdělit načítání stránky s výsledky vyhledávání a počítání do dvou paralelních požadavků. Počítání množství může trvat déle než získání výsledků, zatímco výsledky jsou pro uživatele důležitější.
- Pokud pro vyhledávání používáte databázi SQL, měla by být každá změna kódu související s touto částí dobře otestována na výkon na příslušném množství dat (přesahujícím objem v živé databázi). Dále je vhodné využít sledování doby provádění dotazu na všech instancích databáze a zejména na té „živé“. I když bylo s plány dotazů ve fázi vývoje vše v pořádku, s rostoucím objemem dat se situace může znatelně změnit.
Zdroj: www.habr.com