Jedným z typických scenárov vo všetkých aplikáciách, ktoré poznáme, je vyhľadávanie údajov podľa určitých kritérií a ich zobrazenie v ľahko čitateľnej forme. Môžu existovať aj ďalšie možnosti triedenia, zoskupovania a stránkovania. Úloha je teoreticky triviálna, no pri jej riešení veľa vývojárov robí množstvo chýb, ktoré neskôr spôsobujú utrpenie produktivity. Pokúsme sa zvážiť rôzne možnosti riešenia tohto problému a sformulovať odporúčania na výber najefektívnejšej implementácie.
Možnosť stránkovania #1
Najjednoduchšia možnosť, ktorá vás napadne, je zobrazenie výsledkov vyhľadávania po stránke v tej najklasickejšej podobe.
Povedzme, že vaša aplikácia používa relačné databázy. V tomto prípade na zobrazenie informácií v tomto formulári budete musieť spustiť dva SQL dotazy:
- Získajte riadky pre aktuálnu stránku.
- Vypočítajte celkový počet riadkov zodpovedajúcich kritériám vyhľadávania - je to potrebné na zobrazenie stránok.
Pozrime sa ako príklad na prvý dotaz pomocou testovacej databázy MS SQL pre server 2016. Na tento účel použijeme tabuľku Sales.SalesOrderHeader:
SELECT * FROM Sales.SalesOrderHeader
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
Vyššie uvedený dotaz vráti prvých 50 objednávok zo zoznamu zoradených podľa zostupného dátumu pridania, inými slovami, 50 najnovších objednávok.
Beží rýchlo na testovacej základni, ale pozrime sa na plán vykonávania a štatistiky 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.Vstupno-výstupnú štatistiku pre každý dotaz môžete získať spustením príkazu SET STATISTICS IO ON v runtime dotazu.
Ako môžete vidieť z plánu vykonávania, najnáročnejšia možnosť je zoradiť všetky riadky zdrojovej tabuľky podľa dátumu pridania. A problém je, že čím viac riadkov sa v tabuľke objaví, tým „ťažšie“ bude triedenie. V praxi sa takýmto situáciám treba vyhýbať, preto pridajte index k dátumu pridania a zistite, či sa spotreba zdrojov zmenila:
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.
Očividne sa to výrazne zlepšilo. Sú však všetky problémy vyriešené? Zmeňme dotaz na vyhľadávanie objednávok, kde celková cena tovaru presahuje 100 USD:
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 vtipnú situáciu: plán dotazov nie je oveľa horší ako predchádzajúci, ale skutočný počet logických čítaní je takmer dvakrát väčší ako pri skenovaní celej tabuľky. Existuje východisko - ak vytvoríme zložený index z už existujúceho indexu a ako druhé pole pridáme celkovú cenu tovaru, opäť dostaneme 165 logických čítaní:
CREATE INDEX IX_SalesOrderHeader_OrderDate_SubTotal on Sales.SalesOrderHeader(OrderDate, SubTotal);
V tejto sérii príkladov by sa dalo pokračovať dlho, ale dve hlavné myšlienky, ktoré tu chcem vyjadriť, sú:
- Pridanie akéhokoľvek nového kritéria alebo poradia triedenia do vyhľadávacieho dotazu môže mať významný vplyv na rýchlosť vyhľadávacieho dotazu.
- Ak však potrebujeme odčítať len časť údajov a nie všetky výsledky, ktoré zodpovedajú hľadaným výrazom, existuje mnoho spôsobov, ako takýto dopyt optimalizovať.
Teraz prejdime k druhému dotazu uvedenému na úplnom začiatku – k tomu, ktorý počíta počet záznamov, ktoré spĺňajú kritérium vyhľadávania. Vezmime si rovnaký príklad – vyhľadávanie objednávok, ktoré sú vyššie ako 100 USD:
SELECT COUNT(1) FROM Sales.SalesOrderHeader
WHERE SubTotal > 100
Vzhľadom na vyššie uvedený zložený index získame:
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.Skutočnosť, že dopyt prechádza celým indexom, nie je prekvapujúca, pretože pole Medzisúčet nie je na prvej pozícii, takže ho dopyt nemôže použiť. Problém je vyriešený pridaním ďalšieho indexu do poľa Medzisúčet a výsledkom je iba 48 logických čítaní.
Môžete uviesť niekoľko ďalších príkladov žiadostí o počítanie množstiev, ale podstata zostáva rovnaká: príjem údajov a započítanie celkovej sumy sú dve zásadne odlišné požiadavkya každý si vyžaduje vlastné opatrenia na optimalizáciu. Vo všeobecnosti nebudete môcť nájsť kombináciu indexov, ktorá by fungovala rovnako dobre pre oba dotazy.
V súlade s tým je jednou z dôležitých požiadaviek, ktoré by sa mali objasniť pri vývoji takéhoto riešenia vyhľadávania, či je pre podnik skutočne dôležité vidieť celkový počet nájdených objektov. Často sa stáva, že nie. A navigácia podľa konkrétnych čísel stránok je podľa môjho názoru riešením s veľmi úzkym rozsahom, pretože väčšina scenárov stránkovania vyzerá ako „prejsť na ďalšiu stránku“.
Možnosť stránkovania #2
Predpokladajme, že používatelia sa nestarajú o to, aby poznali celkový počet nájdených objektov. Skúsme zjednodušiť stránku vyhľadávania:
V skutočnosti sa zmenilo iba to, že neexistuje spôsob, ako prejsť na konkrétne čísla strán, a táto tabuľka teraz nepotrebuje vedieť, koľko ich môže byť, aby sa zobrazila. Vynára sa však otázka - ako tabuľka vie, či existujú údaje pre ďalšiu stránku (aby sa správne zobrazil odkaz „Ďalej“)?
Odpoveď je veľmi jednoduchá: z databázy môžete prečítať o jeden záznam viac, ako je potrebné na zobrazenie, a prítomnosť tohto „dodatočného“ záznamu ukáže, či existuje ďalšia časť. Týmto spôsobom stačí spustiť jednu požiadavku na získanie jednej stránky údajov, čo výrazne zlepšuje výkon a uľahčuje podporu takejto funkcionality. V mojej praxi sa vyskytol prípad, keď odmietnutie spočítať celkový počet záznamov urýchlilo doručenie výsledkov 4-5 krát.
Pre tento prístup existuje niekoľko možností používateľského rozhrania: príkazy „späť“ a „vpred“, ako v príklade vyššie, tlačidlo „načítať viac“, ktoré jednoducho pridá k zobrazeným výsledkom novú časť, „nekonečné posúvanie“, ktoré funguje na princípe „načítať viac“ “, ale signálom na získanie ďalšej časti je, aby používateľ posunul všetky zobrazené výsledky až do konca. Bez ohľadu na vizuálne riešenie zostáva princíp vzorkovania údajov rovnaký.
Nuansy implementácie stránkovania
Všetky vyššie uvedené príklady dotazov používajú prístup „offset + počet“, keď samotný dotaz určuje, v akom poradí sú riadky výsledkov a koľko riadkov je potrebné vrátiť. Najprv sa pozrime, ako najlepšie usporiadať odovzdávanie parametrov v tomto prípade. V praxi som sa stretol s niekoľkými spôsobmi:
- Sériové číslo požadovanej strany (pageIndex), veľkosť strany (pageSize).
- Poradové číslo prvého záznamu, ktorý sa má vrátiť (startIndex), maximálny počet záznamov vo výsledku (count).
- Poradové číslo prvého záznamu, ktorý sa má vrátiť (startIndex), poradové číslo posledného záznamu, ktorý sa má vrátiť (endIndex).
Na prvý pohľad sa môže zdať, že je to také elementárne, že v tom nie je žiadny rozdiel. Ale nie je to tak - najpohodlnejšia a najuniverzálnejšia možnosť je druhá (startIndex, count). Existuje na to niekoľko dôvodov:
- Pre vyššie uvedený prístup korektúry záznamu +1 je prvá možnosť s pageIndex a pageSize mimoriadne nepohodlná. Napríklad chceme zobraziť 50 príspevkov na stránku. Podľa vyššie uvedeného algoritmu musíte prečítať o jeden záznam viac, ako je potrebné. Ak toto „+1“ nie je implementované na serveri, ukáže sa, že pre prvú stránku musíme požiadať o záznamy od 1 do 51, pre druhú - od 51 do 101 atď. Ak zadáte veľkosť strany 51 a zvýšite pageIndex, potom sa druhá strana vráti z 52 na 102 atď. V súlade s tým je v prvej možnosti jediným spôsobom, ako správne implementovať tlačidlo na prechod na ďalšiu stránku, nechať server skontrolovať riadok „extra“, čo bude veľmi implicitná nuansa.
- Tretia možnosť vôbec nedáva zmysel, pretože na spustenie dotazov vo väčšine databáz budete musieť zadať počet, a nie index posledného záznamu. Odčítanie startIndex od endIndex môže byť jednoduchá aritmetická operácia, ale tu je zbytočná.
Teraz by sme mali opísať nevýhody implementácie stránkovania prostredníctvom „offset + množstvo“:
- Načítanie každej nasledujúcej stránky bude drahšie a pomalšie ako predchádzajúce, pretože databáza bude stále musieť prejsť všetky záznamy „od začiatku“ podľa kritérií vyhľadávania a triedenia a potom sa zastaviť na požadovanom fragmente.
- Nie všetky DBMS môžu podporovať tento prístup.
Existujú alternatívy, ale sú tiež nedokonalé. Prvý z týchto prístupov sa nazýva „stránkovanie sady kľúčov“ alebo „metóda vyhľadávania“ a je nasledovný: po prijatí časti si môžete zapamätať hodnoty polí v poslednom zázname na stránke a potom ich použiť na získanie ďalšia porcia. Spustili sme napríklad nasledujúci dotaz:
SELECT * FROM Sales.SalesOrderHeader
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
A v poslednom zázname sme dostali hodnotu dátumu objednávky '2014-06-29'. Potom na získanie ďalšej stránky môžete skúsiť urobiť 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 OrderDate je nejedinečné pole a podmienka špecifikovaná vyššie pravdepodobne vynechá veľa požadovaných riadkov. Ak chcete dodať tomuto dotazu jednoznačnosť, musíte do podmienky pridať jedinečné pole (predpokladajme, že 75074 je posledná hodnota primárneho kľúča z prvej časti):
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
Táto možnosť bude fungovať správne, ale vo všeobecnosti bude ťažké ju optimalizovať, pretože podmienka obsahuje operátor OR. Ak sa hodnota primárneho kľúča zvyšuje so zvyšujúcim sa dátumom objednávky, potom je možné podmienku zjednodušiť tak, že ponecháte iba filter podľa SalesOrderID. Ak však neexistuje prísna korelácia medzi hodnotami primárneho kľúča a poľom, podľa ktorého je výsledok zoradený, vo väčšine DBMS sa tomuto ALEBO nedá vyhnúť. Výnimku, o ktorej viem, je PostgreSQL, ktorý plne podporuje porovnávanie n-tic a vyššie uvedená podmienka môže byť napísaná ako "WHERE (Dátum objednávky, ID objednávky) < ('2014. 06. 29', 75074)". Vzhľadom na zložený kľúč s týmito dvoma poľami by mal byť takýto dotaz pomerne jednoduchý.
Druhý alternatívny prístup možno nájsť napríklad v alebo — keď požiadavka okrem údajov vráti aj špeciálny identifikátor, pomocou ktorého môžete získať ďalšiu časť údajov. Ak má tento identifikátor neobmedzenú životnosť (ako v Comsos DB), potom je to skvelý spôsob, ako implementovať stránkovanie so sekvenčným prechodom medzi stránkami (možnosť #2 uvedená vyššie). Jeho možné nevýhody: nie je podporovaný vo všetkých DBMS; výsledný identifikátor ďalšieho bloku môže mať obmedzenú životnosť, čo vo všeobecnosti nie je vhodné na implementáciu interakcie používateľa (ako je napríklad ElasticSearch scroll API).
Komplexné filtrovanie
Poďme si úlohu ešte skomplikovať. Predpokladajme, že existuje požiadavka implementovať takzvané fazetové vyhľadávanie, ktoré je každému veľmi známe z internetových obchodov. Vyššie uvedené príklady založené na tabuľke objednávok nie sú v tomto prípade príliš názorné, preto prejdime na tabuľku Produkt z databázy AdventureWorks:
Aká je myšlienka fazetovaného hľadania? Faktom je, že pre každý prvok filtra sa zobrazuje počet záznamov, ktoré spĺňajú toto kritérium berúc do úvahy filtre vybrané vo všetkých ostatných kategóriách.
Ak napríklad v tomto príklade vyberieme kategóriu Bicykle a farbu Čierna, v tabuľke sa zobrazia iba čierne bicykle, ale:
- Pre každé kritérium v skupine Kategórie sa počet produktov z danej kategórie zobrazí čiernou farbou.
- Pre každé kritérium skupiny „Farby“ sa zobrazí počet bicyklov tejto farby.
Tu je príklad výstupu výsledku pre takéto podmienky:
Ak zaškrtnete aj kategóriu “Oblečenie”, v tabuľke sa zobrazí aj čierne oblečenie, ktoré je skladom. Počet čiernych produktov v sekcii „Farba“ bude tiež prepočítaný podľa nových podmienok, len v sekcii „Kategórie“ sa nič nezmení... Dúfam, že tieto príklady stačia na pochopenie bežného fazetového vyhľadávacieho algoritmu.
Teraz si predstavme, ako sa to dá realizovať na relačnej báze. Každá skupina kritérií, ako napríklad kategória a farba, bude vyžadovať 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
Čo je na tomto riešení zlé? Je to veľmi jednoduché – neškáluje sa dobre. Každá sekcia filtra vyžaduje samostatný dotaz na výpočet množstiev a tieto dotazy nie sú najjednoduchšie. V internetových obchodoch môžu mať niektoré kategórie niekoľko desiatok filtračných sekcií, čo môže predstavovať vážny problém s výkonom.
Zvyčajne po týchto vyhláseniach sa mi ponúkajú nejaké riešenia, a to:
- Skombinujte všetky počty množstiev do jedného dopytu. Technicky je to možné pomocou kľúčového slova UNION, ale výkonu to veľmi nepomôže – databáza bude musieť aj tak spustiť každý z fragmentov od začiatku.
- Množstvo vyrovnávacej pamäte. Toto sa mi navrhuje takmer vždy, keď popisujem problém. Výhradou je, že to je vo všeobecnosti nemožné. Povedzme, že máme 10 „faziet“, z ktorých každá má 5 hodnôt. Toto je veľmi „skromná“ situácia v porovnaní s tým, čo možno vidieť v rovnakých internetových obchodoch. Výber jedného fazetového prvku ovplyvňuje množstvo v 9 ďalších, inými slovami, pre každú kombináciu kritérií môžu byť množstvá odlišné. V našom príklade je celkovo 50 kritérií, ktoré si používateľ môže vybrať, takže možných kombinácií bude 250. Na naplnenie takéhoto poľa údajov nie je dostatok pamäte ani času. Tu môžete namietať a povedať, že nie všetky kombinácie sú skutočné a používateľ si málokedy vyberie viac ako 5-10 kritérií. Áno, je možné urobiť lenivé načítanie a uložiť do vyrovnávacej pamäte len to, čo bolo kedy vybraté, ale čím viac výberov bude, tým menej efektívna bude takáto vyrovnávacia pamäť a tým výraznejšie budú problémy s dobou odozvy (najmä ak súbor údajov sa pravidelne mení).
Našťastie, takýto problém má už dávno celkom efektívne riešenia, ktoré fungujú predvídateľne na veľkých objemoch dát. Pre ktorúkoľvek z týchto možností má zmysel rozdeliť prepočet faziet a prijímanie stránky s výsledkami na dve paralelné volania na server a organizovať používateľské rozhranie tak, aby načítanie údajov podľa faziet „nezasahovalo“ do zobrazenia Výsledky vyhľadávania.
- Úplný prepočet „faziet“ volajte čo najmenej. Neprepočítavajte napríklad všetko pri každej zmene kritérií vyhľadávania, ale namiesto toho nájdite celkový počet výsledkov, ktoré zodpovedajú aktuálnym podmienkam, a požiadajte používateľa, aby ich ukázal – „1425 záznamov nájdených, zobraziť?“ Používateľ môže pokračovať v zmene hľadaných výrazov alebo kliknúť na tlačidlo „zobraziť“. Iba v druhom prípade sa vykonajú všetky požiadavky na získanie výsledkov a prepočítanie množstiev na všetkých „fazetách“. V tomto prípade, ako môžete ľahko vidieť, budete musieť riešiť požiadavku na získanie celkového počtu výsledkov a jeho optimalizáciu. Túto metódu možno nájsť v mnohých malých internetových obchodoch. Je zrejmé, že to nie je všeliek na tento problém, ale v jednoduchých prípadoch to môže byť dobrý kompromis.
- Použite vyhľadávacie nástroje na nájdenie výsledkov a počítanie aspektov, ako sú Solr, ElasticSearch, Sphinx a ďalšie. Všetky sú navrhnuté tak, aby vytvárali „fazety“ a robili to celkom efektívne vďaka obrátenému indexu. Ako fungujú vyhľadávače, prečo sú v takýchto prípadoch efektívnejšie ako univerzálne databázy, aké tam sú praktiky a úskalia – to je téma na samostatný článok. Tu by som chcel upozorniť na skutočnosť, že vyhľadávač nemôže byť náhradou za hlavné dátové úložisko, používa sa ako doplnok: akékoľvek zmeny v hlavnej databáze, ktoré sú relevantné pre vyhľadávanie, sa synchronizujú do indexu vyhľadávania; Vyhľadávač zvyčajne komunikuje iba s vyhľadávačom a nepristupuje k hlavnej databáze. Jedným z najdôležitejších bodov je, ako túto synchronizáciu spoľahlivo zorganizovať. Všetko závisí od požiadaviek na „čas reakcie“. Ak čas medzi zmenou v hlavnej databáze a jej „prejavením“ pri vyhľadávaní nie je kritický, môžete vytvoriť službu, ktorá každých pár minút vyhľadáva nedávno zmenené záznamy a indexuje ich. Ak chcete čo najkratší čas odozvy, môžete implementovať niečo ako odosielať aktualizácie vyhľadávacej službe.
Závery
- Implementácia stránkovania na strane servera je významnou komplikáciou a má zmysel len pre rýchlo rastúce alebo jednoducho veľké súbory údajov. Neexistuje absolútne presný recept, ako hodnotiť „veľký“ alebo „rýchlo rastúci“, ale ja by som postupoval takto:
- Ak príjem kompletnej kolekcie údajov, berúc do úvahy čas servera a sieťový prenos, normálne vyhovuje požiadavkám na výkon, nemá zmysel implementovať stránkovanie na strane servera.
- Môže nastať situácia, že v blízkej budúcnosti sa neočakávajú žiadne problémy s výkonom, keďže údajov je málo, ale zber údajov neustále rastie. Ak niektorý súbor údajov v budúcnosti už nemusí spĺňať predchádzajúci bod, je lepšie začať stránkovať ihneď.
- Ak zo strany podniku neexistuje striktná požiadavka na zobrazenie celkového počtu výsledkov alebo na zobrazenie čísel stránok a váš systém nemá vyhľadávací nástroj, je lepšie tieto body neimplementovať a zvážiť možnosť #2.
- Ak existuje jasná požiadavka na fazetové vyhľadávanie, máte dve možnosti bez obetovania výkonu:
- Neprepočítavajte všetky množstvá pri každej zmene kritérií vyhľadávania.
- Používajte vyhľadávače ako Solr, ElasticSearch, Sphinx a iné. Malo by sa však chápať, že nemôže byť náhradou za hlavnú databázu a mal by sa používať ako doplnok k hlavnému úložisku na riešenie problémov s vyhľadávaním.
- V prípade fazetového vyhľadávania má tiež zmysel rozdeliť získavanie stránky s výsledkami vyhľadávania a počítanie do dvoch paralelných požiadaviek. Počítanie množstiev môže trvať dlhšie ako získanie výsledkov, zatiaľ čo výsledky sú pre používateľa dôležitejšie.
- Ak na vyhľadávanie používate databázu SQL, každá zmena kódu súvisiaca s touto časťou by mala byť dobre otestovaná na výkon na príslušnom množstve údajov (presahujúcich objem v živej databáze). Taktiež je vhodné využívať sledovanie času vykonania dotazu na všetkých inštanciách databázy a najmä na tej „živej“. Aj keď bolo všetko v poriadku s plánmi dotazov vo fáze vývoja, s rastúcim objemom údajov sa situácia môže výrazne zmeniť.
Zdroj: hab.com