Een van de typische scenario's in alle applicaties die we kennen is het zoeken naar gegevens volgens bepaalde criteria en deze in een gemakkelijk leesbare vorm weergeven. Er kunnen ook extra opties zijn voor sorteren, groeperen en paging. De taak is in theorie triviaal, maar bij het oplossen ervan maken veel ontwikkelaars een aantal fouten, waardoor de productiviteit er later onder lijdt. Laten we proberen verschillende opties te overwegen om dit probleem op te lossen en aanbevelingen te formuleren voor het kiezen van de meest effectieve implementatie.
Oproepoptie #1
De eenvoudigste optie die in je opkomt is een pagina-voor-pagina weergave van zoekresultaten in de meest klassieke vorm.
Stel dat uw toepassing een relationele database gebruikt. In dit geval moet u twee SQL-query's uitvoeren om informatie in dit formulier weer te geven:
- Haal rijen op voor de huidige pagina.
- Bereken het totale aantal regels dat overeenkomt met de zoekcriteria - dit is nodig om pagina's weer te geven.
Laten we eens kijken naar de eerste query, waarbij we als voorbeeld een MS SQL-testdatabase gebruiken voor 2016-server. Voor dit doel gebruiken we de tabel Sales.SalesOrderHeader:
SELECT * FROM Sales.SalesOrderHeader
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
De bovenstaande zoekopdracht retourneert de eerste 50 bestellingen uit de lijst, gesorteerd op aflopende datum van toevoeging, met andere woorden, de 50 meest recente bestellingen.
Het werkt snel op de testbasis, maar laten we eens kijken naar het uitvoeringsplan en de I/O-statistieken:
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.U kunt voor elke query I/O-statistieken verkrijgen door de opdracht SET STATISTICS IO ON uit te voeren tijdens de runtime van de query.
Zoals u kunt zien in het uitvoeringsplan, is de meest resource-intensieve optie het sorteren van alle rijen van de brontabel op toegevoegde datum. En het probleem is dat hoe meer rijen er in de tabel verschijnen, hoe “moeilijker” het sorteren zal zijn. In de praktijk moeten dergelijke situaties worden vermeden, dus laten we een index toevoegen aan de datum van toevoeging en kijken of het verbruik van hulpbronnen is veranderd:
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.
Het is duidelijk een stuk beter geworden. Maar zijn alle problemen opgelost? Laten we de zoekopdracht wijzigen om te zoeken naar bestellingen waarbij de totale kosten van goederen hoger zijn dan € 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.We hebben een grappige situatie: het queryplan is niet veel slechter dan het vorige, maar het werkelijke aantal logische reads is bijna twee keer zo groot als bij een volledige tabelscan. Er is een uitweg: als we een samengestelde index maken van een reeds bestaande index en de totale prijs van goederen als tweede veld toevoegen, krijgen we opnieuw 165 logische waarden:
CREATE INDEX IX_SalesOrderHeader_OrderDate_SubTotal on Sales.SalesOrderHeader(OrderDate, SubTotal);
Deze reeks voorbeelden kan nog lang worden voortgezet, maar de twee belangrijkste gedachten die ik hier wil uiten zijn:
- Het toevoegen van een nieuw criterium of een nieuwe sorteervolgorde aan een zoekopdracht kan een aanzienlijke impact hebben op de snelheid van de zoekopdracht.
- Maar als we slechts een deel van de gegevens moeten aftrekken, en niet alle resultaten die overeenkomen met de zoektermen, zijn er veel manieren om een dergelijke zoekopdracht te optimaliseren.
Laten we nu verder gaan met de tweede zoekopdracht die helemaal aan het begin werd genoemd: de zoekopdracht die het aantal records telt dat aan het zoekcriterium voldoet. Laten we hetzelfde voorbeeld nemen: zoeken naar bestellingen van meer dan $ 100:
SELECT COUNT(1) FROM Sales.SalesOrderHeader
WHERE SubTotal > 100
Gegeven de hierboven aangegeven samengestelde index, verkrijgen we:
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.Het feit dat de query de gehele index doorloopt is niet verrassend, aangezien het veld SubTotaal niet op de eerste positie staat en de query er dus geen gebruik van kan maken. Het probleem wordt opgelost door nog een index toe te voegen aan het veld SubTotaal, waardoor er slechts 48 logische leesbewerkingen worden uitgevoerd.
Je kunt nog een paar voorbeelden geven van verzoeken om hoeveelheden te tellen, maar de essentie blijft hetzelfde: het ontvangen van een stukje gegevens en het tellen van het totale bedrag zijn twee fundamenteel verschillende verzoeken, en elk vereist zijn eigen maatregelen voor optimalisatie. Over het algemeen zult u geen combinatie van indexen kunnen vinden die voor beide zoekopdrachten even goed werkt.
Een van de belangrijke vereisten die bij het ontwikkelen van een dergelijke zoekoplossing moet worden verduidelijkt, is dan ook of het voor een bedrijf echt belangrijk is om het totale aantal gevonden objecten te zien. Het komt vaak voor dat nee. En navigatie op specifieke paginanummers is naar mijn mening een oplossing met een zeer beperkte reikwijdte, aangezien de meeste pagingscenario's eruitzien als 'ga naar de volgende pagina'.
Oproepoptie #2
Laten we aannemen dat het gebruikers niets uitmaakt om het totale aantal gevonden objecten te kennen. Laten we proberen de zoekpagina te vereenvoudigen:
Het enige dat veranderd is, is dat er geen manier is om naar specifieke paginanummers te navigeren, en nu hoeft deze tabel niet te weten hoeveel er kunnen zijn om deze weer te geven. Maar de vraag rijst: hoe weet de tabel of er gegevens zijn voor de volgende pagina (om de link "Volgende" correct weer te geven)?
Het antwoord is heel eenvoudig: u kunt één record meer uit de database lezen dan nodig is voor weergave, en de aanwezigheid van dit “extra” record zal laten zien of er een volgend deel is. Op deze manier hoeft u slechts één verzoek uit te voeren om één pagina met gegevens op te halen, wat de prestaties aanzienlijk verbetert en het eenvoudiger maakt om dergelijke functionaliteit te ondersteunen. In mijn praktijk was er een geval waarin de weigering om het totale aantal records te tellen de levering van resultaten met 4-5 keer versnelde.
Er zijn verschillende gebruikersinterface-opties voor deze aanpak: "terug" en "vooruit" -opdrachten, zoals in het bovenstaande voorbeeld, een knop "meer laden", die eenvoudigweg een nieuw gedeelte toevoegt aan de weergegeven resultaten, "oneindig scrollen", wat werkt op het principe van "laad meer" ", maar het signaal om het volgende deel te krijgen is dat de gebruiker alle weergegeven resultaten naar het einde scrollt. Wat de visuele oplossing ook is, het principe van databemonstering blijft hetzelfde.
Nuances van paging-implementatie
Alle bovenstaande queryvoorbeelden gebruiken de “offset + count”-benadering, waarbij de query zelf specificeert in welke volgorde de resultaatrijen zijn en hoeveel rijen moeten worden geretourneerd. Laten we eerst eens kijken hoe we in dit geval het doorgeven van parameters het beste kunnen organiseren. In de praktijk ben ik verschillende methoden tegengekomen:
- Het serienummer van de opgevraagde pagina (pageIndex), paginaformaat (pageSize).
- Het serienummer van het eerste record dat moet worden geretourneerd (startIndex), het maximale aantal records in het resultaat (count).
- Het volgnummer van het eerste record dat moet worden geretourneerd (startIndex), het volgnummer van het laatste record dat moet worden geretourneerd (endIndex).
Op het eerste gezicht lijkt het misschien dat dit zo elementair is dat er geen verschil is. Maar dit is niet zo - de handigste en meest universele optie is de tweede (startIndex, tellen). Hier zijn verschillende redenen voor:
- Voor de hierboven gegeven aanpak voor het proeflezen van +1 items is de eerste optie met pageIndex en pageSize uiterst lastig. We willen bijvoorbeeld 50 berichten per pagina weergeven. Volgens het bovenstaande algoritme moet u één record meer lezen dan nodig is. Als deze "+1" niet op de server is geïmplementeerd, blijkt dat we voor de eerste pagina records van 1 tot 51 moeten opvragen, voor de tweede - van 51 tot 101, enz. Als u een paginaformaat van 51 opgeeft en pageIndex vergroot, keert de tweede pagina terug van 52 naar 102, enz. Dienovereenkomstig is bij de eerste optie de enige manier om een knop om naar de volgende pagina te gaan correct te implementeren, het door de server laten nalezen van de "extra" regel, wat een zeer impliciete nuance zal zijn.
- De derde optie heeft helemaal geen zin, omdat je voor het uitvoeren van queries in de meeste databases nog steeds de telling moet doorgeven in plaats van de index van het laatste record. Het aftrekken van startIndex van endIndex kan een eenvoudige rekenkundige bewerking zijn, maar is hier overbodig.
Nu moeten we de nadelen beschrijven van het implementeren van paging via “offset + hoeveelheid”:
- Het ophalen van elke volgende pagina zal duurder en langzamer zijn dan de vorige, omdat de database nog steeds alle records “vanaf het begin” moet doorlopen volgens de zoek- en sorteercriteria, en dan moet stoppen bij het gewenste fragment.
- Niet alle DBMS'en kunnen deze aanpak ondersteunen.
Er zijn alternatieven, maar die zijn ook onvolmaakt. De eerste van deze benaderingen wordt “keyset paging” of “zoekmethode” genoemd en is als volgt: nadat u een deel heeft ontvangen, kunt u de veldwaarden in het laatste record op de pagina onthouden en deze vervolgens gebruiken om het volgende deel. We hebben bijvoorbeeld de volgende query uitgevoerd:
SELECT * FROM Sales.SalesOrderHeader
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
En in de laatste record kregen we de orderdatumwaarde '2014-06-29'. Om vervolgens de volgende pagina te krijgen, kunt u het volgende proberen:
SELECT * FROM Sales.SalesOrderHeader
WHERE OrderDate < '2014-06-29'
ORDER BY OrderDate DESC
OFFSET 0 ROWS
FETCH NEXT 50 ROWS ONLY
Het probleem is dat OrderDate een niet-uniek veld is en dat de hierboven gespecificeerde voorwaarde waarschijnlijk veel vereiste rijen zal missen. Om eenduidigheid aan deze query toe te voegen, moet je een uniek veld aan de voorwaarde toevoegen (neem aan dat 75074 de laatste waarde is van de primaire sleutel uit het eerste deel):
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
Deze optie zal correct werken, maar zal over het algemeen moeilijk te optimaliseren zijn, omdat de voorwaarde een OR-operator bevat. Als de waarde van de primaire sleutel toeneemt naarmate OrderDate toeneemt, kan de voorwaarde worden vereenvoudigd door alleen een filter op SalesOrderID achter te laten. Maar als er geen strikte correlatie bestaat tussen de waarden van de primaire sleutel en het veld waarop het resultaat wordt gesorteerd, kan deze OR in de meeste DBMS'en niet worden vermeden. Een uitzondering die ik ken is PostgreSQL, dat tupelvergelijkingen volledig ondersteunt, en de bovenstaande voorwaarde kan worden geschreven als "WHERE (OrderDate, SalesOrderID) < ('2014-06-29', 75074)". Gegeven een samengestelde sleutel met deze twee velden, zou een zoekopdracht als deze vrij eenvoudig moeten zijn.
Een tweede alternatieve benadering is bijvoorbeeld te vinden in of — wanneer een verzoek, naast gegevens, een speciale identificatie retourneert waarmee u het volgende deel van de gegevens kunt verkrijgen. Als deze identificatie een onbeperkte levensduur heeft (zoals in Comsos DB), dan is dit een geweldige manier om paging te implementeren met sequentiële overgang tussen pagina's (optie #2 hierboven vermeld). De mogelijke nadelen: het wordt niet in alle DBMS'en ondersteund; de resulterende next-chunk-identifier kan een beperkte levensduur hebben, wat over het algemeen niet geschikt is voor het implementeren van gebruikersinteractie (zoals de ElasticSearch-scroll-API).
Complexe filtering
Laten we de taak nog ingewikkelder maken. Stel dat er een vereiste is om de zogenaamde facetzoekopdracht te implementeren, die bij iedereen uit online winkels zeer bekend is. De bovenstaande voorbeelden op basis van de ordertabel zijn in dit geval niet erg illustratief, dus laten we overschakelen naar de Producttabel uit de AdventureWorks-database:
Wat is het idee achter gefacetteerd zoeken? Feit is dat bij ieder filterelement het aantal records wordt weergegeven dat aan dit criterium voldoet rekening houdend met filters die in alle andere categorieën zijn geselecteerd.
Als we in dit voorbeeld bijvoorbeeld de categorie Fietsen en de kleur Zwart selecteren, worden in de tabel alleen zwarte fietsen weergegeven, maar:
- Voor elk criterium in de groep Categorieën wordt het aantal producten uit die categorie in het zwart weergegeven.
- Voor elk criterium van de groep “Kleuren” wordt het aantal fietsen van deze kleur weergegeven.
Hier is een voorbeeld van de resultaatuitvoer voor dergelijke omstandigheden:
Als u ook de categorie ‘Kleding’ aanvinkt, ziet u in de tabel ook zwarte kleding die op voorraad is. Het aantal zwarte producten in de sectie “Kleur” zal ook opnieuw worden berekend volgens de nieuwe voorwaarden, alleen in de sectie “Categorieën” zal er niets veranderen... Ik hoop dat deze voorbeelden voldoende zijn om het gebruikelijke facetzoekalgoritme te begrijpen.
Laten we ons nu eens voorstellen hoe dit op relationele basis kan worden geïmplementeerd. Voor elke groep criteria, zoals Categorie en Kleur, is een afzonderlijke zoekopdracht vereist:
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
Wat is er mis met deze oplossing? Het is heel eenvoudig: het schaalt niet goed. Elke filtersectie vereist een afzonderlijke query om hoeveelheden te berekenen, en deze query's zijn niet de gemakkelijkste. In online winkels kunnen sommige categorieën enkele tientallen filtersecties hebben, wat een ernstig prestatieprobleem kan zijn.
Meestal krijg ik na deze uitspraken enkele oplossingen aangeboden, namelijk:
- Combineer alle aantallen in één zoekopdracht. Technisch gezien is dit mogelijk met het trefwoord UNION, maar het zal de prestaties niet veel ten goede komen: de database zal nog steeds elk fragment helemaal opnieuw moeten uitvoeren.
- Cache-hoeveelheden. Dit wordt mij bijna elke keer aangeraden als ik een probleem beschrijf. Het voorbehoud is dat dit doorgaans onmogelijk is. Laten we zeggen dat we 10 "facetten" hebben, die elk 5 waarden hebben. Dit is een zeer “bescheiden” situatie vergeleken met wat te zien is in dezelfde online winkels. De keuze voor één facetelement heeft invloed op de hoeveelheden van 9 andere facetelementen, met andere woorden: voor elke combinatie van criteria kunnen de hoeveelheden verschillend zijn. In ons voorbeeld zijn er in totaal 50 criteria die de gebruiker kan selecteren, dus er zijn 250 mogelijke combinaties. Er is niet genoeg geheugen of tijd om zo'n reeks gegevens te vullen. Hier kunt u bezwaar maken en zeggen dat niet alle combinaties reëel zijn en dat de gebruiker zelden meer dan 5-10 criteria selecteert. Ja, het is mogelijk om lazyloading uit te voeren en een hoeveelheid te cachen van alleen wat ooit is geselecteerd, maar hoe meer selecties er zijn, hoe minder efficiënt een dergelijke cache zal zijn en hoe merkbaarder de responstijdproblemen zullen zijn (vooral als de dataset verandert regelmatig).
Gelukkig bestaan er voor een dergelijk probleem al lange tijd behoorlijk effectieve oplossingen die voorspelbaar werken op grote hoeveelheden gegevens. Voor elk van deze opties is het zinvol om de herberekening van facetten en het ontvangen van de resultatenpagina te verdelen in twee parallelle oproepen naar de server en de gebruikersinterface zo te organiseren dat het laden van gegevens per facet “niet interfereert” met de weergave van Zoekresultaten.
- Roep zo zelden mogelijk een volledige herberekening van "facetten" op. Bereken bijvoorbeeld niet alles opnieuw telkens wanneer de zoekcriteria veranderen, maar zoek in plaats daarvan het totale aantal resultaten dat voldoet aan de huidige voorwaarden en vraag de gebruiker om deze weer te geven - “1425 records gevonden, weergeven?” De gebruiker kan doorgaan met het wijzigen van de zoektermen of op de knop ‘toon’ klikken. Alleen in het tweede geval zullen alle verzoeken voor het verkrijgen van resultaten en het herberekenen van hoeveelheden op alle "facetten" worden uitgevoerd. In dit geval krijgt u, zoals u gemakkelijk kunt zien, te maken met een verzoek om het totale aantal resultaten te verkrijgen en de optimalisatie ervan. Deze methode is te vinden in veel kleine online winkels. Uiteraard is dit geen wondermiddel voor dit probleem, maar in eenvoudige gevallen kan het een goed compromis zijn.
- Gebruik zoekmachines om resultaten te vinden en facetten te tellen, zoals Solr, ElasticSearch, Sphinx en anderen. Ze zijn allemaal ontworpen om “facetten” te bouwen en doen dit vrij efficiënt dankzij de omgekeerde index. Hoe zoekmachines werken, waarom ze in dergelijke gevallen effectiever zijn dan databases voor algemene doeleinden, welke praktijken en valkuilen er zijn - dit is een onderwerp voor een apart artikel. Hier wil ik uw aandacht vestigen op het feit dat de zoekmachine geen vervanging kan zijn voor de hoofdgegevensopslag, maar wordt gebruikt als aanvulling: alle wijzigingen in de hoofddatabase die relevant zijn voor het zoeken worden gesynchroniseerd met de zoekindex; De zoekmachine communiceert doorgaans alleen met de zoekmachine en heeft geen toegang tot de hoofddatabase. Een van de belangrijkste punten hier is hoe u deze synchronisatie betrouwbaar kunt organiseren. Het hangt allemaal af van de vereisten voor "reactietijd". Als de tijd tussen een wijziging in de hoofddatabase en de “manifestatie” ervan in de zoekopdracht niet kritisch is, kunt u een service maken die om de paar minuten naar recent gewijzigde records zoekt en deze indexeert. Als u de kortst mogelijke reactietijd wilt, kunt u zoiets implementeren om updates naar de zoekservice te verzenden.
Bevindingen
- Het implementeren van paging op de server is een aanzienlijke complicatie en is alleen zinvol voor snelgroeiende of eenvoudigweg grote datasets. Er bestaat geen absoluut exact recept voor de beoordeling van ‘groot’ of ‘snelgroeiend’, maar ik zou deze aanpak volgen:
- Als het ontvangen van een volledige verzameling gegevens, rekening houdend met servertijd en netwerktransmissie, normaal gesproken voldoet aan de prestatie-eisen, heeft het geen zin om paging aan de serverzijde te implementeren.
- Er kan zich een situatie voordoen waarin er in de nabije toekomst geen prestatieproblemen worden verwacht, omdat er weinig gegevens zijn, maar de gegevensverzameling groeit voortdurend. Als een bepaalde reeks gegevens in de toekomst mogelijk niet langer aan het vorige punt voldoet, is het beter om meteen te beginnen met paging.
- Als er geen strikte eis van de kant van het bedrijf bestaat om het totale aantal resultaten of paginanummers weer te geven, en uw systeem beschikt niet over een zoekmachine, dan is het beter om deze punten niet te implementeren en optie #2 te overwegen.
- Als er een duidelijke vereiste is voor gefacetteerd zoeken, hebt u twee opties zonder dat dit ten koste gaat van de prestaties:
- Bereken niet alle hoeveelheden opnieuw telkens wanneer de zoekcriteria veranderen.
- Gebruik zoekmachines zoals Solr, ElasticSearch, Sphinx en anderen. Maar het moet duidelijk zijn dat het geen vervanging kan zijn voor de hoofddatabase, en moet worden gebruikt als aanvulling op de hoofdopslag voor het oplossen van zoekproblemen.
- Ook is het bij facetzoeken zinvol om het ophalen van de zoekresultatenpagina en het tellen op te splitsen in twee parallelle verzoeken. Het tellen van hoeveelheden kan langer duren dan het verkrijgen van resultaten, terwijl de resultaten belangrijker zijn voor de gebruiker.
- Als u een SQL-database gebruikt om te zoeken, moet elke codewijziging met betrekking tot dit onderdeel goed worden getest op prestaties op de juiste hoeveelheid gegevens (die het volume in de live-database overschrijdt). Het is ook raadzaam om monitoring van de uitvoeringstijd van query's te gebruiken op alle exemplaren van de database, en vooral op de 'live' versie. Zelfs als alles in orde was met de queryplannen in de ontwikkelingsfase, kan de situatie merkbaar veranderen naarmate de hoeveelheid gegevens groeit.
Bron: www.habr.com