Otsingutulemuste väljund ja jõudlusprobleemid

Üks tüüpiline stsenaarium, millega me oma rakendustes kokku puutume, on andmete otsimine teatud kriteeriumide alusel ja nende kuvamine lugemiseks mugaval viisil. Samuti võivad olla lisavõimalused, nagu sortimine, rühmitamine ja leheküljed. Ülesanne näib esmapilgul triviaalne, kuid selle lahendamisel teevad paljud arendajad mitmeid vigu, mis mõjutavad hiljem jõudlust. Proovime vaadata erinevaid lahenduste variante ja formuleerida soovitusi, kuidas valida tõhusaim rakenduse täideviimine.

Leheküljendamise variant #1

Lihtsaim variant, mis pähe tuleb, on postitada otsingu tulemused klassikalisel viisil leheküljendatult.

Oletame, et rakenduses kasutatakse relationaalset andmebaasi. Sel juhul peab sellise vormingu jaoks toimuma kaks SQL päringut:

• Saama read praegusele leheküljele.
• Arvutama välja koguarvu read, mis vastavad otsingukriteeriumidele — see on vajalik lehtede näitamiseks.

Vaadakem esimest päringut testimise MS SQL andmebaasi põhjal AdventureWorks 2016 serveri jaoks. Selleks kasutame tabelit Sales.SalesOrderHeader:

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

Ülaltoodud päring kuvab esimesed 50 tellimust loendist, mis on sorteeritud lisamise kuupäeva järgi, teisisõnu — 50 viimast tellimust.

Käib see testimise andmebaasis kiiresti, kuid vaatame, mis juhtub plaaniga ja sisend-väljund statistikaga:

Tabel 'SalesOrderHeader'. Skaneeringute arv 1, loogilised lugemised 698, füüsilised lugemised 0, eelnevad lugemised 0, lob loogilised lugemised 0, lob füüsilised lugemised 0, lob eelnevad lugemised 0.

Iga päringu sisend-väljund statistika saamiseks saab käivitada päringute keskkonnas käsu SET STATISTICS IO ON.

Nagu täitmisplaanist näha, on kõige ressursimahukam kogu algsete tabeli ridade sortimine lisamise kuupäeva järgi. Probleem on siiski selles, et mida rohkem ridu tabelisse lisandub, seda 'raskem' on sortimine. Praktiliselt tuleks selliseid olukordi vältida, seetõttu lisame sortimisekuva kuupäevale indeksi ja vaatame, kas ressursikasutus on muutunud:

Tabel 'SalesOrderHeader'. Skaneeringute arv 1, loogilised lugemised 165, füüsilised lugemised 0, eelnevad lugemised 5, lob loogilised lugemised 0, lob füüsilised lugemised 0, lob eelnevad lugemised 0.

Ilmselt on asjad palju paremaks muutunud. Kuid kas kõik probleemid on lahendatud? Muudame päringu tellimuste leidmiseks, kus kaupade koguhind ületab 100 dollarit:

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

Tabel 'SalesOrderHeader'. Skaneerimise arv 1, loogilised lugemised 1081, füüsilised lugemised 0, lugemise eelvaated 0, lob loogilised lugemised 0, lob füüsilised lugemised 0, lob lugemise eelvaated 0.

Käes on naljakas olukord: päringu plaan ei ole palju halvem eelmisest, kuid tegelik loogiliste lugemiste arv on peaaegu kaks korda suurem kui kogu tabeli skaneerimise korral. Lahendus on olemas — kui olemasolevast indeksist teha kombineeritud ja teiseks väljaks lisada kaupade koguhind, saame jälle 165 loogilist lugemist:

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

Seda näidete seeriat saab jätkata veel kaua, kuid kaks peamist mõtet, mida siin soovin väljendada, on järgmised:

• Iga uue kriteeri või sortimisjärjestuse lisamine päringusse võib oluliselt mõjutada selle täitmise kiirus.
• Kuid kui me peame välja võtma ainult osa andmetest, mitte kõiki otsingutingimustele vastavaid tulemusi — on palju viise, kuidas sellist päringut optimeerida.

Nüüd liigume teise päringu juurde, mida mainiti alguses — selle juurde, mis loendab rekordite arvu, mis vastavad otsingutingimustele. Võtame sama näite — otsing tellimuste leidmiseks, mis maksavad rohkem kui 100 dollarit:

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

Kui vastata sellele koostatud indeksiga, saame:

Tabel 'SalesOrderHeader'. Skaneeringute arv 1, loogilised lugemised 698, füüsilised lugemised 0, eelnevad lugemised 0, lob loogilised lugemised 0, lob füüsilised lugemised 0, lob eelnevad lugemised 0.

Et päring läbib kogu indeksi, ei ole üllatav, kuna väli SubTotal ei ole esimeses positsioonis, seega ei saa päring seda ära kasutada. Probleem lahendatakse lisades veel ühe indeksi väljale SubTotal, mis annab kokku juba vaid 48 loogilist lugemist.

Võin tuua veel mõned näited päringute jaoks, mis loendavad arvu, kuid põhimõte jääb samaks: andmete kogumise ja koguarvu arvestamine — need on kaks fundamentaalselt erinevat päringut, ja igaüks nõuab oma meetmeid optimeerimiseks. Üldiselt ei ole võimalik leida indeksite kombinatsiooni, mis töötab sama hästi mõlema päringu jaoks.

Seega, üks olulisemaid nõudeid, mida tuleb sellise otsingulahenduse arendamisel täpsustada, on see, kas ettevõttele on oluline näha leitud objektide koguarvu. Sageli ei ole see nii. Ja navigeerimine konkreetsete lehekülgede numbrite vahel on minu arvates lahendus, millel on väga kitsas rakendamisala, kuna enamiku lehekülgede vahetamise stsenaariumide puhul on see pigem "mine järgmisele lehele".

Lehekülgede vahetamise variant #2

Oletame, et kasutajatele ei ole üldise leitud objektide arvu teadmine oluline. Proovime lihtsustada otsingulehte:

Fakt on, et muutunud on ainult see, et ei ole võimalik liikuda konkreetsete lehekülgede numbrite vahel ning nüüd ei pea sellele tabelile teadma, kui palju lehekülgi kokku võib olla. Kuid tekib küsimus — kuidas tabel saab teada, kas järgmise lehekülje andmed on olemas (et õigesti näidata linki „Järgmine”)?

Vastus on väga lihtne: andmebaasist saab lugeda ühe kirje rohkem, kui on vaja kuvada, ja see "lisakirje" näitabki, kas järgmine partii on olemas. Seega, et saada ühte andmelehte, tuleb teha vaid üks päring, mis oluliselt parandab jõudlust ja lihtsustab sellise funktsionaalsuse toetust. Minu praktikas oli juhtum, kus koguarvu arvestamisest loobumine kiirendas tulemuste väljundit 4-5 korda.

Selle lähenemise jaoks on olemas mitmeid kasutajaliidese valikuid: käsklused „tagasi” ja „edasi”, nagu eelnevas näites, nupp „lae veel”, mis lihtsalt lisab uue partii kuvatud tulemustele, „lõpmatu kerimine”, mis toimib „lae veel” põhimõtte järgi, kuid järgmise partii saamise signaaliks on kasutaja kerimine kõikide kuvatud tulemusteni lõpuni. Ükskõik, milline on visuaalne lahendus, jääb andmete valimise põhimõte samaks.

Lehekülgede vahetamise rakendamise nüansid

Kõigis ülaltoodud päringute näidetes kasutatakse lähenemist „silmus + arv”, kus päringus märgitakse ära, millise järjekorra järgi tulemus ja kui palju ridu tuleb tagastada. Esiteks vaatame, kuidas on parim korraldada parameetrite edastamine sellisel juhul. Praktikas olen kohanud mitmeid viise:

• Soovitava lehe järjestusnumber (pageIndex), lehe suurus (pageSize).
• Esimese salvestuse järjestusnumber, mille me saame (startIndex), maksimaalne salvestuste arv tulemuses (count).
• Esimese salvestuse järjestusnumber, mille me salvestame (startIndex), viimase salvestuse järjestusnumber, mille me salvestame (endIndex).

Esmapilgul võib tunduda, et see on nii elementaarne, et mingit vahet pole. Kuid see ei ole nii — kõige mugavam ja universaalsem variant on teine (startIndex, count). Sellel on mitu põhjust:

• Selle lähenemise puhul, kus loetakse +1 salvestust, on esimene variant pageIndex ja pageSize äärmiselt ebamugav. Näiteks tahame lehe peal kuvada 50 salvestust. Vastavalt eelmisele algoritmile tuleb lugeda ühe salvestuse võrra rohkem, kui tegelikult on vajalik. Kui see „+1“ pole serveris ette nähtud, siis selgub, et esimese lehe jaoks peame küsima salvestusi vahemikus 1 kuni 51, teise jaoks — 51 kuni 101 jne. Kui määrata lehe suuruseks 51 ja suurendada pageIndex, siis teine leht tagastab salvestused vahemikus 52 kuni 102 jne. Seega on esimese variandi puhul ainus viis korralikult rakendada järgmise lehe juurde mineku nuppu — ette näha serveris „ühe liigse“ rea lugemist, mis on väga ebaselge nüanss.
• Kolmas variant pole üldse mõistlik, kuna enamikus andmebaasides tuleb päringute tegemiseks edastada ikkagi arv, mitte viimase salvestuse indeks. Olgu see startIndex lahutamine endIndex'ist ja elementaarne aritmeetiline tehe, kuid see on siinkohal üleliigne.

Nüüd tuleks kirjeldada puudusi rakendamisel, mis kasutab „nihet + kogust“:

• Iga järgmise lehe saamine osutub kallimaks ja aeglasemaks kui eelmine, kuna andmebaas peab ikkagi läbi lugema kõik salvestused „algusest“ vastavalt otsingukriteeriumidele ja sortimisele ning seejärel peatuma vajalikul fragmendil.
• Kaugeltki mitte kõik andmebaaside haldamise süsteemid (СУБД) ei pruugi seda lähenemist toetada.

Alternatiive on, kuid needki ei ole ideaalsed. Esimene nendest lähenemistest nimetatakse „keyset paging” või „seek method” ja see seisneb järgmisest: pärast andmeportsjoni saamist saab salvestada viimasel lehel olevate salvestuste väljade väärtused ja seejärel kasutada neid järgmise portsjoni saamiseks. Näiteks sooritasime sellise päringu:

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

Ja viimasest kirjest saime tellimuse kuupäeva väärtuse '2014-06-29'. Siis järgmise lehe saamiseks saab proovida järgmist:

SELECT * FROM Sales.SalesOrderHeader
WHERE OrderDate < '2014-06-29'
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY

Probleem on selles, et OrderDate ei ole ainulaadne väli ja ülaltoodud tingimus lõpetab tõenäoliselt paljude vajalike ridade vahelejätmise. Selle päringu selguse tagamiseks tuleb tingimusele lisada ainulaadne väli (eeldame, et 75074 on viimane esmane võtme väärtus esimesest osast):

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

See variant töötab kenasti, kuid üldiselt on seda raske optimeerida, kuna tingimus sisaldab OR operaatorit. Kui OrderDate kasvab koos esmane võtme väärtusega, saab tingimust lihtsustada, jättes alles ainult SalesOrderID filtri. Kuid kui esmane võtme väärtuste ja tulemuste sorteerimise aluseks oleva väljade vahel ei ole ranget korrelatsiooni - enamikus andmebaasihaldussüsteemides ei õnnestu vältida seda OR-i. Minule teadaolev erand on PostgreSQL, kus ridade võrdlemine toetatakse täielikult ja ülaltoodud tingimust saab kirjutada kui "WHERE (OrderDate, SalesOrderID) < ('2014-06-29', 75074)". Kui on olemas komposiitvõti nende kahe välja jaoks, peaks selline päring olema piisavalt kerge.

Teine alternatiivne lähenemine võib esineda näiteks ElasticSearch scroll API või Cosmos DB — kus päring ei tagasta mitte ainult andmeid, vaid ka spetsiaalset identifikaatorit, mille abil saab saada järgmise andmepartii. Kui see identifikaator on piiramatu elueaga (nagu Cosmos DB-s), siis on see suurepärane viis lehekeste järkjärguliseks navigeerimiseks (ülaltoodud variants #2). Selle võimalikke puudusi: ei toetata kaugeltki kõigis andmebaaside haldamise süsteemides; saadud järgmise partii identifikaatoril võib olla piiratud eluiga, mis üldjuhul ei sobi kasutajate interaktsiooni rakendamiseks (näiteks ElasticSearch scroll API).

Kompleksne filtreerimine

Täitame ülesannet veelgi keerulisemaks. Oletame, et on tekkinud nõue rakendada nn faceted search, mida kõik kindlasti tunnevad e-poodide kontekstis. Ülaltoodud näited tellimuste tabelist ei ole siin väga näitlikud, seega lülitume AdventureWorks andmebaasi Product tabelisse:

Mis on faceted search idee? See seisneb selles, et iga filtri elemendi jaoks näidatakse vastava kriteeriumi kohta vastavate kirjeid arvu. arvestades filtreid, mis on valitud kõigis teistes kategooriates..

Näiteks, kui valime selles näites kategooria Bikes ja värvi Black, kuvab tabel ainult mustade värvi jalgrattaid, kuid samas:

• Iga "Categories" grupi kriteeriumi jaoks näidatakse musta värvi tooteid, mis kuuluvad sellesse kategooriasse.
• Iga "Colors" grupi kriteeriumi jaoks näidatakse mustade jalgrataste arvu.

Siin on näide selliste tingimuste tulemuste väljundist:

Kui lisaks valida kategooria "Clothing", kuvab tabel ka musta värvi riideid, mis on saadaval. Mustade toodete arvu "Color" sektsioonis arvutatakse samuti uute tingimuste järgi, ent "Categories" sektsioonis ei muutu midagi... Loodan, et need näited on piisavad, et mõista tuttavat faceted searchi töökorraldust.

Nüüd kujutame ette, kuidas seda relatsioonilises andmebaasis rakendada. Iga kriteeriumigrupp, nagu Category ja Color, vajab eraldi päringut:

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

Mis on valesti sellega lahendusega? Väga lihtne — see ei skaala hästi. Iga filtreerimisosakond nõuab eraldi päringut koguste arvestamiseks ja need päringud ei ole just kerged. E-poes võib mõnes kategoorias olla ka mitu tosinat filtreerimisosakonda, mis võib olla täiendavaks probleemiks jõudlusest.

Tavaliselt pärast neid väiteid pakuvad mulle mõned lahendused, nimelt:

• Kombineeri kõik koguse arvestused üheks päringuks. Tehniliselt on see võimalik kasutada UNION võtmesõna, kuid see ei paranda jõudlust — andmebaasil tuleb ikkagi iga osa "nullist" läbi viia.
• Kata arvestused. Seda soovitatakse mulle peaaegu igal korral, kui ma probleemi kirjeldan. Detail on see, et see on üldiselt võimatu. Oletame, et meil on 10 "fasaadi", milles igas on 5 väärtust. See on väga "moderne" olukord võrreldes sellega, mida näha sama internetipoe puhul. Ühe fasaadi elemendi valik mõjutab 9 teise koguseid, teisisõnu, iga kriteeriumi kombinatsiooni jaoks võivad kogused olla erinevad. Kokku on meie näites 50 kriteeriumi, mida kasutaja saab valida, seega on võimalikke kombinatsioone 250. Sellise andmemassiivi täitmiseks ei piisa ei mälust ega ajast. Siin võib vastu vaielda ja öelda, et mitte kõik kombinatsioonid ei ole reaalsed ja kasutaja valib harva rohkem kui 5-10 kriteeriumi. Jah, on võimalik teha laisk laadimine ja koguste cache ainult nende jaoks, mida on kunagi valitud, kuid mida rohkem on valikuvõimalusi, seda vähem efektiivne on selline cache ja seda silmatorkavamad on vastamise ajaga seotud probleemid (eriti kui andmekogum muutub regulaarselt).

Õnneks on sellisel ülesandel juba ammu olemas piisavalt efektiivsed lahendused, mis ennustatavalt töötavad suurte andmemahtude poole. Iga ühte neist variantidest on mõttekas jagada fassaadide ülearvutamine ja tulemuste lehe saamine kaheks paralleelseks päringuks serverisse ning korraldada kasutajaliides selliselt, et fassaadide andmete laadimine "ei sega" otsingutulemuste kuvamist.

• Kutsuge täielikku "fassaadide" ümberarvestust nii harva kui võimalik. Näiteks, ärge arvutage kõike iga otsingukriteeriumi muutmise korral, vaid leidke üldine vastuste arv, mis vastab praegustele tingimustele, ja pakkuda kasutajale nende kuvamist — "leidub 1425 kirjet, näidata?" Kasutaja võib kas jätkata otsingutingimuste muutmist või vajutada nuppu „näita“. Alles teisel juhul tehakse kõik päringud tulemuste saamiseks ja kõigi "fassaadide" arvu ümberarvestamiseks. Samuti tuleb silmas pidada, et tuleb tegeleda päringuga üldise vastuste arvu saamiseks ja selle optimeerimisega. Sellist meetodit võib leida paljudest väikestest veebipoodidest. On selge, et see ei ole imeravim, kuid lihtsates olukordades võib olla kokkuvõtteks hea kompromiss.
• Kasutage otsingumootoreid tulemuste otsimiseks ja fassaadide arvestamiseks, nagu Solr, ElasticSearch, Sphinx ja teised. Kõik need on loodud "fassaadide" loomiseks ja teevad seda piisavalt tõhusalt, kasutades pööratud indekseerimist. Kuidas otsingumootorid töötavad, miks nad nendes olukordades on tõhusamad kui tavalised andmebaasid, millised on praktika ja takistused — see on eraldi artikli teema. Kuid soovin tähelepanu juhtida sellele, et otsingumootor ei saa olla peamise andmehoidla asendaja; see on lisa: kõik muudatused peamises andmebaasis, mis on otsingu jaoks olulised, sünkroniseeritakse otsinguindeksisse; otsingumehhanism suhtleb tavaliselt ainult otsingumootoriga ega pöördu peamise andmebaasi poole. Üks olulisemaid aspekte on see, kuidas korraldada sünkroniseerimist usaldusväärselt. Kõik sõltub "reaktsiooniaja" nõuetest. Kui aeg peamise andmebaasi muutmise ja selle "kuvamise" vahel otsingus ei ole kriitiline, saab luua teenuse, mis vaatab iga paari minuti tagant hiljaaegu muudetud kirjeid ja indekseerib need. Kui nõutav on võimalikult minimaalne reaktsiooniaeg, saab rakendada midagi taolist. transactional outbox uuenduste saatmiseks otsinguteenusesse.

Järeldused

1. Server-side paging implementation is a serious complication, and it should only be applied for rapidly growing or simply large datasets. There is no absolutely precise recipe for evaluating what constitutes 'large' or 'rapidly growing,' but I would adhere to the following approach:
   • If obtaining the complete dataset, considering server time and data transfer, fits within performance requirements, then there is no point in implementing server-side paging.
   • It may happen that there are currently no performance issues due to having little data, but the data collection is constantly growing. If a dataset might eventually no longer satisfy the previous point, it's better to lay the groundwork for paging right away.
2. If there is no strict business requirement for showing the total number of results or displaying page numbers, and your system does not have a search engine, it is better not to implement these aspects and instead consider option #2.
3. If there is a clear requirement for faceted search, you have two options to avoid sacrificing performance:
   • Do not recalculate all counts with every change in search criteria.
   • Use search engines such as Solr, ElasticSearch, Sphinx, and others. However, it should be understood that it cannot replace the main database and should be used as a complement to the primary storage to solve search tasks.
4. Also, in the case of faceted search, it makes sense to separate the retrieval of the search results page and the count of quantities into two parallel requests. The count of quantities may take longer than retrieving the results, while the results are more important for the user.
5. If you are using an SQL database for searching, any code changes related to this part must be thoroughly tested for performance against the relevant volume of data (exceeding the volume in the 'live' database). It is also advisable to monitor query execution times on all database instances, especially on the 'live' one. Even if everything was fine during the development phase with the query plans, the situation may change significantly as the volume of data grows.

Allikas: habr.com