Jedan od tipičnih scenarija u svim aplikacijama koje su nam poznate je traženje podataka prema određenim kriterijima i njihovo prikazivanje u lako čitljivom obliku. Mogu postojati i dodatne opcije za sortiranje, grupisanje i stranice. Zadatak je, u teoriji, trivijalan, ali kada ga rješavaju, mnogi programeri prave niz grešaka, što kasnije uzrokuje smanjenje produktivnosti. Pokušajmo razmotriti različite opcije za rješavanje ovog problema i formulirati preporuke za odabir najefikasnije implementacije.
Opcija pejdžinga #1
Najjednostavnija opcija koja vam pada na pamet je prikaz rezultata pretrage stranica po stranicu u najklasičnijem obliku.
Recimo da vaša aplikacija koristi relacionu bazu podataka. U ovom slučaju, da biste prikazali informacije u ovom obliku, morat ćete pokrenuti dva SQL upita:
- Dobijte redove za trenutnu stranicu.
- Izračunajte ukupan broj redova koji odgovaraju kriterijima pretraživanja - ovo je neophodno za prikaz stranica.
Pogledajmo prvi upit koristeći testnu MS SQL bazu podataka kao primjer za 2016 server. U tu svrhu ćemo koristiti tablicu Sales.SalesOrderHeader:
SELECT * FROM Sales.SalesOrderHeader
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
Gornji upit će vratiti prvih 50 narudžbi sa liste, sortiranih prema opadajućem datumu dodavanja, drugim riječima, 50 najnovijih narudžbi.
Brzo radi na testnoj bazi, ali pogledajmo plan izvršenja i statistiku 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.Možete dobiti I/O statistiku za svaki upit pokretanjem naredbe SET STATISTICS IO ON u vremenu izvođenja upita.
Kao što možete vidjeti iz plana izvršenja, opcija sa najviše resursa je sortiranje svih redova izvorne tablice prema datumu dodavanja. A problem je u tome što što se više redova pojavi u tabeli, sortiranje će biti „teže“. U praksi takve situacije treba izbjegavati, pa dodajmo indeks datumu dodavanja i vidimo da li se potrošnja resursa promijenila:
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čigledno je postalo mnogo bolje. Ali da li su svi problemi rešeni? Promijenimo upit da tražimo narudžbe kod kojih ukupni trošak robe prelazi 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.Imamo smiješnu situaciju: plan upita nije mnogo lošiji od prethodnog, ali stvarni broj logičkih čitanja je skoro dvostruko veći nego kod skeniranja cijele tablice. Postoji izlaz - ako od već postojećeg indeksa napravimo kompozitni indeks i dodamo ukupnu cijenu robe kao drugo polje, opet ćemo dobiti 165 logičnih očitanja:
CREATE INDEX IX_SalesOrderHeader_OrderDate_SubTotal on Sales.SalesOrderHeader(OrderDate, SubTotal);
Ovaj niz primjera se može nastaviti još dugo, ali dvije glavne misli koje želim ovdje izraziti su:
- Dodavanje bilo kojeg novog kriterija ili redoslijeda sortiranja upitu za pretraživanje može imati značajan utjecaj na brzinu upita pretraživanja.
- Ali ako trebamo oduzeti samo dio podataka, a ne sve rezultate koji odgovaraju pojmovima za pretraživanje, postoji mnogo načina za optimizaciju takvog upita.
Pređimo sada na drugi upit naveden na samom početku - onaj koji broji broj zapisa koji zadovoljavaju kriterij pretraživanja. Uzmimo isti primjer - traženje narudžbi koje su veće od 100 USD:
SELECT COUNT(1) FROM Sales.SalesOrderHeader
WHERE SubTotal > 100
S obzirom na gore naveden kompozitni indeks, dobijamo:
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.Činjenica da upit prolazi kroz cijeli indeks nije iznenađujuća, jer polje SubTotal nije na prvoj poziciji, pa ga upit ne može koristiti. Problem je riješen dodavanjem još jednog indeksa na SubTotal polje i kao rezultat daje samo 48 logičkih čitanja.
Možete navesti još nekoliko primjera zahtjeva za brojanje količina, ali suština ostaje ista: primanje podatka i brojanje ukupnog iznosa su dva suštinski različita zahtjeva, a svaka zahtijeva svoje mjere za optimizaciju. Općenito, nećete moći pronaći kombinaciju indeksa koja jednako dobro funkcionira za oba upita.
U skladu s tim, jedan od važnih zahtjeva koji treba razjasniti prilikom razvoja ovakvog rješenja za pretraživanje je da li je za posao zaista važno vidjeti ukupan broj pronađenih objekata. Često se dešava da ne. A navigacija prema određenim brojevima stranica, po mom mišljenju, predstavlja rješenje s vrlo uskim opsegom, budući da većina scenarija stranica izgleda kao „idi na sljedeću stranicu“.
Opcija pejdžinga #2
Pretpostavimo da korisnicima nije stalo da znaju ukupan broj pronađenih objekata. Pokušajmo pojednostaviti stranicu za pretraživanje:
Zapravo, jedina stvar koja se promijenila je da ne postoji način za navigaciju do određenih brojeva stranica, a sada ova tabela ne mora znati koliko ih može biti da bi je prikazala. Ali postavlja se pitanje - kako tabela zna da li postoje podaci za sljedeću stranicu (kako bi se ispravno prikazala veza "Sljedeće")?
Odgovor je vrlo jednostavan: možete pročitati iz baze podataka jedan zapis više nego što je potrebno za prikaz, a prisustvo ovog „dodatnog“ zapisa će pokazati da li postoji sljedeći dio. Na ovaj način trebate pokrenuti samo jedan zahtjev da biste dobili jednu stranicu podataka, što značajno poboljšava performanse i olakšava podršku takve funkcionalnosti. U mojoj praksi je bio slučaj kada je odbijanje brojanja ukupnog broja zapisa ubrzalo isporuku rezultata za 4-5 puta.
Postoji nekoliko opcija korisničkog sučelja za ovaj pristup: naredbe "nazad" i "naprijed", kao u gornjem primjeru, dugme "učitaj više", koje jednostavno dodaje novi dio prikazanim rezultatima, "beskonačno pomicanje", što radi po principu "učitaj više"", ali signal za dobijanje sljedećeg dijela je da korisnik skroluje sve prikazane rezultate do kraja. Bez obzira na vizualno rješenje, princip uzorkovanja podataka ostaje isti.
Nijanse implementacije stranica
Svi gore navedeni primjeri upita koriste pristup “offset + count”, kada sam upit specificira kojim redoslijedom su redovi rezultata i koliko redova treba vratiti. Prvo, pogledajmo kako najbolje organizirati prosljeđivanje parametara u ovom slučaju. U praksi sam naišao na nekoliko metoda:
- Serijski broj tražene stranice (pageIndex), veličina stranice (pageSize).
- Serijski broj prvog zapisa koji treba vratiti (startIndex), maksimalni broj zapisa u rezultatu (broj).
- Redni broj prvog zapisa koji treba vratiti (startIndex), redni broj posljednjeg zapisa koji treba vratiti (endIndex).
Na prvi pogled može izgledati da je to toliko elementarno da nema razlike. Ali to nije tako - najprikladnija i univerzalna opcija je druga (startIndex, count). Postoji nekoliko razloga za to:
- Za pristup lektorisanja unosa +1 koji je gore naveden, prva opcija sa indeksom stranice i veličinom stranice je izuzetno nezgodna. Na primjer, želimo prikazati 50 postova po stranici. Prema gore navedenom algoritmu, potrebno je pročitati još jedan zapis nego što je potrebno. Ako ovaj "+1" nije implementiran na serveru, ispada da za prvu stranicu moramo tražiti zapise od 1 do 51, za drugu - od 51 do 101, itd. Ako navedete veličinu stranice od 51 i povećate pageIndex, onda će se druga stranica vratiti sa 52 na 102, itd. U skladu s tim, u prvoj opciji, jedini način da se pravilno implementira dugme za odlazak na sljedeću stranicu je da server lektorira “dodatni” red, što će biti vrlo implicitna nijansa.
- Treća opcija uopće nema smisla, jer da biste pokrenuli upite u većini baza podataka, i dalje ćete morati proslijediti broj umjesto indeksa posljednjeg zapisa. Oduzimanje startIndex-a od endIndex-a može biti jednostavna aritmetička operacija, ali je ovdje suvišna.
Sada bismo trebali opisati nedostatke implementacije stranica kroz “offset + količina”:
- Dohvaćanje svake naredne stranice bit će skuplje i sporije od prethodne, jer će baza podataka i dalje morati proći kroz sve zapise “od početka” prema kriterijima pretraživanja i sortiranja, a zatim se zaustaviti na željenom fragmentu.
- Ne mogu svi DBMS-ovi podržati ovaj pristup.
Postoje alternative, ali su i one nesavršene. Prvi od ovih pristupa naziva se „paging po skupu ključeva“ ili „metoda traženja“ i glasi kako slijedi: nakon što primite dio, možete zapamtiti vrijednosti polja u posljednjem zapisu na stranici, a zatim ih koristiti za dobivanje sljedeći dio. Na primjer, pokrenuli smo sljedeći upit:
SELECT * FROM Sales.SalesOrderHeader
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
A u posljednjem zapisu dobili smo vrijednost datuma narudžbe ‘2014-06-29’. Zatim da biste dobili sljedeću stranicu možete pokušati učiniti ovo:
SELECT * FROM Sales.SalesOrderHeader
WHERE OrderDate < '2014-06-29'
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
Problem je u tome što OrderDate nije jedinstveno polje i gore navedeni uslov će vjerovatno propustiti mnogo potrebnih redova. Da biste dodali nedvosmislenost ovom upitu, morate dodati jedinstveno polje u uslov (pretpostavimo da je 75074 posljednja vrijednost primarnog ključa iz prvog dijela):
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
Ova opcija će raditi ispravno, ali općenito će je biti teško optimizirati jer uvjet sadrži operator OR. Ako se vrijednost primarnog ključa povećava kako se OrderDate povećava, tada se uvjet može pojednostaviti ostavljanjem samo filtera po SalesOrderID-u. Ali ako ne postoji stroga korelacija između vrijednosti primarnog ključa i polja po kojem je rezultat sortiran, ovo OR se ne može izbjeći u većini DBMS-ova. Izuzetak kojeg sam svjestan je PostgreSQL, koji u potpunosti podržava poređenje tuple, a gornji uslov se može napisati kao "WHERE (OrderDate, SalesOrderID) < ('2014-06-29', 75074)". S obzirom na složeni ključ sa ova dva polja, upit poput ovog trebao bi biti prilično jednostavan.
Drugi alternativni pristup se može naći, na primjer, u ili — kada zahtjev, pored podataka, vraća poseban identifikator pomoću kojeg možete dobiti sljedeći dio podataka. Ako ovaj identifikator ima neograničen životni vijek (kao u Comsos DB-u), onda je ovo odličan način za implementaciju stranica sa sekvencijalnim prijelazom između stranica (opcija #2 spomenuta gore). Njegovi mogući nedostaci: nije podržan u svim DBMS-ovima; rezultirajući identifikator sljedećeg dijela može imati ograničen vijek trajanja, što općenito nije prikladno za implementaciju korisničke interakcije (kao što je ElasticSearch scroll API).
Kompleksno filtriranje
Hajde da dodatno zakomplikujemo zadatak. Pretpostavimo da postoji zahtjev da se implementira takozvana fasetirana pretraga, koja je svima dobro poznata iz online trgovina. Gore navedeni primjeri zasnovani na tabeli narudžbi nisu baš ilustrativni u ovom slučaju, pa se prebacimo na tablicu proizvoda iz baze podataka AdventureWorks:
Koja je ideja iza fasetirane pretrage? Činjenica je da je za svaki filterski element prikazan broj zapisa koji ispunjavaju ovaj kriterij uzimajući u obzir filtere odabrane u svim ostalim kategorijama.
Na primjer, ako odaberemo kategoriju Bicikli i crnu boju u ovom primjeru, tabela će prikazati samo crne bicikle, ali:
- Za svaki kriterij u grupi Kategorije, broj proizvoda iz te kategorije bit će prikazan crnom bojom.
- Za svaki kriterijum grupe „Boje“ biće prikazan broj bicikala ove boje.
Evo primjera izlaznog rezultata za takve uvjete:
Ako provjerite i kategoriju “Odjeća”, u tabeli će biti prikazana i crna odjeća koja je na zalihama. Broj crnih proizvoda u sekciji “Boja” takođe će biti preračunat prema novim uslovima, samo u odeljku “Kategorije” ništa se neće promeniti... Nadam se da su ovi primeri dovoljni da razumemo uobičajeni algoritam fasetirane pretrage.
Sada zamislimo kako se ovo može implementirati na relacijskoj osnovi. Za svaku grupu kriterijuma, kao što su kategorija i boja, biće potreban poseban upit:
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
Šta nije u redu sa ovim rješenjem? Vrlo je jednostavno - ne skalira se dobro. Svaki odjeljak filtera zahtijeva poseban upit za izračunavanje količina, a ti upiti nisu najlakši. U online trgovinama neke kategorije mogu imati nekoliko desetina odjeljaka filtera, što može predstavljati ozbiljan problem s performansama.
Obično mi se nakon ovih izjava ponude neka rješenja, i to:
- Kombinirajte sve količine u jedan upit. Tehnički, ovo je moguće pomoću ključne riječi UNION, ali neće mnogo pomoći performansama – baza podataka će i dalje morati da izvršava svaki od fragmenata ispočetka.
- Količina keša. Ovo mi se sugeriše skoro svaki put kada opišem problem. Upozorenje je da je to generalno nemoguće. Recimo da imamo 10 "faseta", od kojih svaka ima 5 vrijednosti. Ovo je vrlo “skromna” situacija u odnosu na ono što se može vidjeti u istim internet trgovinama. Izbor jednog elementa aspekta utiče na količine u 9 drugih, drugim riječima, za svaku kombinaciju kriterija količine mogu biti različite. U našem primjeru postoji ukupno 50 kriterija koje korisnik može odabrati, tako da će biti mogućih kombinacija 250. Nema dovoljno memorije ili vremena za popunjavanje takvog niza podataka. Ovdje možete prigovoriti i reći da nisu sve kombinacije stvarne i da korisnik rijetko bira više od 5-10 kriterija. Da, moguće je izvršiti lijeno učitavanje i keširati samo ono što je ikada odabrano, ali što je više odabira, to će takav keš biti manje efikasan i problemi s vremenom odziva će biti uočljiviji (posebno ako skup podataka se redovno mijenja).
Srećom, takav problem već dugo ima prilično efikasna rješenja koja rade predvidljivo na velikim količinama podataka. Za bilo koju od ovih opcija, ima smisla podijeliti ponovno izračunavanje aspekata i primanje stranice s rezultatima u dva paralelna poziva serveru i organizirati korisničko sučelje na takav način da učitavanje podataka po aspektima „ne ometa“ prikaz Rezultati pretrage.
- Što je rjeđe moguće, zovite kompletno ponovno izračunavanje „faseta“. Na primjer, nemojte sve preračunavati svaki put kada se promijene kriteriji pretraživanja, već umjesto toga pronađite ukupan broj rezultata koji odgovaraju trenutnim uvjetima i zatražite od korisnika da ih prikaže - „Pronađeno 1425 zapisa, prikaži?“ Korisnik može nastaviti mijenjati pojmove za pretraživanje ili kliknuti na dugme “prikaži”. Samo u drugom slučaju će se izvršiti svi zahtjevi za dobijanje rezultata i preračunavanje količina na svim „fasetima“. U ovom slučaju, kao što možete lako vidjeti, morat ćete se pozabaviti zahtjevom za dobivanje ukupnog broja rezultata i njegovu optimizaciju. Ova metoda se može naći u mnogim malim online trgovinama. Očigledno, ovo nije lijek za ovaj problem, ali u jednostavnim slučajevima može biti dobar kompromis.
- Koristite tražilice da pronađete rezultate i brojite aspekte, kao što su Solr, ElasticSearch, Sphinx i drugi. Svi su dizajnirani da grade „fasete“ i to rade prilično efikasno zbog obrnutog indeksa. Kako funkcionišu pretraživači, zašto su u takvim slučajevima efikasniji od baza podataka opšte namene, koje prakse i zamke postoje - to je tema za poseban članak. Ovdje bih želio skrenuti vašu pažnju na činjenicu da tražilica ne može biti zamjena za glavnu pohranu podataka, već se koristi kao dodatak: sve promjene u glavnoj bazi podataka koje su relevantne za pretraživanje sinkroniziraju se u indeks pretraživanja; Pretraživač obično komunicira samo sa tražilicom i ne pristupa glavnoj bazi podataka. Jedna od najvažnijih tačaka ovdje je kako pouzdano organizirati ovu sinhronizaciju. Sve ovisi o zahtjevima za "vrijeme reakcije". Ako vrijeme između promjene u glavnoj bazi podataka i njene „manifestacije“ u pretraživanju nije kritično, možete kreirati uslugu koja svakih nekoliko minuta traži nedavno promijenjene zapise i indeksira ih. Ako želite najkraće moguće vrijeme odgovora, možete implementirati nešto poput da pošaljete ažuriranja servisu pretrage.
nalazi
- Implementacija stranica na strani servera je značajna komplikacija i ima smisla samo za brzorastuće ili jednostavno velike skupove podataka. Ne postoji apsolutno tačan recept kako ocijeniti "velike" ili "brzo rastuće", ali bih slijedio ovaj pristup:
- Ako primanje kompletne zbirke podataka, uzimajući u obzir vrijeme servera i mrežni prijenos, normalno odgovara zahtjevima performansi, nema smisla implementirati stranica na strani servera.
- Može doći do situacije u kojoj se u bliskoj budućnosti ne očekuju problemi u performansama, jer podataka ima malo, ali prikupljanje podataka stalno raste. Ako neki skup podataka u budućnosti možda više ne zadovoljava prethodnu tačku, bolje je odmah početi sa stranicama.
- Ako ne postoji strogi zahtjev od strane poslovanja da se prikaže ukupan broj rezultata ili da se prikažu brojevi stranica, a vaš sistem nema pretraživač, bolje je ne implementirati ove tačke i razmotriti opciju #2.
- Ako postoji jasan zahtjev za fasetirano pretraživanje, imate dvije opcije bez žrtvovanja performansi:
- Nemojte preračunavati sve količine svaki put kada se promijene kriteriji pretraživanja.
- Koristite pretraživače kao što su Solr, ElasticSearch, Sphinx i drugi. Ali treba shvatiti da ne može biti zamjena za glavnu bazu podataka, već da se koristi kao dodatak glavnoj memoriji za rješavanje problema pretraživanja.
- Takođe, u slučaju fasetnog pretraživanja, ima smisla podijeliti preuzimanje stranice s rezultatima pretraživanja i brojanje na dva paralelna zahtjeva. Brojanje količina može trajati duže od dobijanja rezultata, dok su rezultati važniji za korisnika.
- Ako koristite SQL bazu podataka za pretraživanje, svaka promjena koda koja se odnosi na ovaj dio treba biti dobro testirana za performanse na odgovarajućoj količini podataka (premašivši volumen u živoj bazi podataka). Takođe je preporučljivo koristiti praćenje vremena izvršavanja upita na svim instancama baze podataka, a posebno na onoj „živoj“. Čak i ako je sve bilo u redu sa planovima upita u fazi razvoja, kako obim podataka raste, situacija se može primjetno promijeniti.
izvor: www.habr.com