Facetnavigatie performantie

13 juni 2013 Inzichten /

Het laatste jaar hebben we al enkele keren functionaliteit moeten bouwen waarbij men aan de hand van facetten door een dataset kan zoeken. Een facetnavigatie lijst een aantal facetten op waarmee je de zoekresultaten kan verfijnen. In sommige situaties plaatsen onze informatie-architecten ook cijfertjes naast elk facet. Als gebruiker zie je in een oogopslag hoeveel resultaten onder een bepaald facet zitten. Als developer wil dit zeggen dat je voor elk facet dat aantal resultaten moet berekenen. Op een dataset -en die moet zelfs niet heel groot zijn- wordt dit een heuse zoektocht om de meest performante oplossing te vinden.

Uitdaging/probleem

In een eenvoudige zoekmachine heb je zoekresultaten en een totaal aantal zoekresultaten. In het geval van facetnavigatie heb je dit ook, maar heb je ook het aantal zoekresultaten nodig achter elk van de mogelijke facetten. Dit wil zeggen dat je in het geval van 40 mogelijke facetten, je de count query 40-maal extra moet uitvoeren.

Dit komt neer op:

  • 1 query om de zoekresultaten op te halen voor de huidige zoekopdracht
  • 1 count query voor het totaal aantal zoekresultaten (voor o.a. paginering)
  • 1 query om alle facetten op te halen
  • 40 queries om per facet het aantal resultaten op te halen indien je dat facet zou selecteren

In totaal dus 43 queries per page request om die zoekpagina op te bouwen. Zelf als de dataset beperkt is (~2000 items) en zonder load, zit je hier al met een zeer trage zoekfunctie.

We gaan er hier ook van uit dat mensen veel en snel facetten aan- en uitschakelen om het verschil in resultaten te zien. Het aantal page requests is dan ook hoger op die pagina’s.  Als we dit in het achterhoofd houden, moeten we een performante oplossing vinden voor het zoeken met facetten.

Mogelijke oplossingen

Er zijn een aantal oplossingen die we overwogen en getest hebben doorheen de tijd. Elke situatie en dataset is anders, dus moeten we elke keer herbekijken wat de juiste oplossing is voor de huidige dataset. Toch zijn er een aantal zaken die we graag verduidelijken en waarvan we willen uitleggen waarom we ze wel of niet toegepast hebben:

  • niets doen, alle count queries in elke page request uitvoeren
  • counts asynchroon inladen via AJAX
  • een matrix van alle mogelijkheden + aantal resultaten berekenen
  • denormalisatie in combinatie met memcache en een aantal berekeningen in PHP

Alle count queries in elke page request uitvoeren

Dit is de meest voor de hand liggende oplossing, en is ook degene die we  in de uitdaging hierboven al aanhaalden. In elke page request worden de zoekresultaten en de facetten opgehaald voor de gebruiker. Het databaseschema voor zo'n aanpak is eenvoudig en duidelijk:

Alle mogelijke facetten worden in een tabel bijgehouden en via een link tabel aan de producten gekoppeld. Zoekopdrachten moeten enkele joins uitvoeren om tot de resultaten te komen. Op een kleine dataset en met een klein aantal facetten kan je hier goeie resultaten mee bereiken. Op een grotere dataset worden de queries al snel intensief, zeker als je die per facet opnieuw moet uitvoeren.

Counts asynchroon inladen via AJAX

In deze aanpak zorgen we ervoor dat de initiële page request enkel de zoekresultaten en het totaal aantal zoekresultaten ophaalt. Via een AJAX call halen we de counts per facet op. De count queries gebeuren dus asynchroon en de gebruiker hoeft niet te wachten. Deze aanpak hebben we echter snel naast ons neergelegd omdat het geen oplossing is voor het performantieprobleem, enkel een workaround. De load op de database blijft dezelfde, al is die meer gespreid.

Daarnaast is het voordeel voor de gebruiker ook een stuk verminderd. Hij moet namelijk wachten tot die counters klaar zijn en in veel gevallen is er ondertussen al een nieuwe klik of zoekopdracht gebeurd. De counts komen met andere woorden te laat.

Een matrix van alle mogelijkheden + aantal resultaten

In het geval dat de zoekfunctionaliteit enkel uit facetten bestaat en geen variabele input bevat (bv. locatie of zoekterm), dan zou men alle mogelijke facetcombinaties en het bijhorende aantal resultaten op voorhand kunnen berekenen.  Dat kan er dan uitzien als volgt:

  • facet1+facet2+facet3 = 342
  • facet2+facet3 = 643
  • facet2 = 3444

Op die manier kan je heel snel het aantal resultaten achter een combinatie van facetten ophalen. Dit heeft echter een aantal nadelen. Het is intensief om die matrix op te bouwen, en elke keer er data wijzigt, moet dit opnieuw gebeuren.  Je zou dit nà een admin-actie in het CMS kunnen uitvoeren, of via een cronjob op regelmatige tijdstippen. Je zal hoe dan ook voor korte tijd met een delay zitten (en dus even met foute counts). Dit is de reden waarom we deze oplossing niet verder geïmplementeerd hebben.

In de praktijk zou je enkel de eerste niveaus van combinaties kunnen berekenen en de dieperliggende niveaus op een andere manier. Op die manier heb je toch de meest voorkomende facetcombinaties al gedekt.

Denormalisatie + memcache + berekeningen in PHP

Deze aanpak bestaat uit 3 onderdelen die samen voor een oplossing zorgen die in de meeste van onze toepassingen performant werkt.

1. Denormalisatie 

De meest intensieve stukken bevinden zich rond de link tabel en de queries die moeten gebeuren om alle data samen te sprokkelen (via de link tabel). Onze eerste wijziging was het wegwerken van deze link tabel, en het voor elk facet bijhouden van de producten die ervoor van toepassing zijn. De database ziet er dan zo uit:

Het veld "products" bevat een serialized array met product ID's die van toepassing zijn voor dat facet. We hadden al een query om alle facetten op te halen, en door deze denormalisatie hebben we  in diezelfde query onmiddellijk ook alle product ID's. 

2. Memcache

We hebben alle product ID's per facet in stap 1 opgehaald via de facetten. In deze lijst van ID's zitten alle producten, dus ook producten die niet zichtbaar zijn, die vervallen zijn (op basis van publiceerdatum), .... We moeten deze ID's nog filteren zodat we enkel de zichtbare overhouden. Deze filtering voeren we uit door alle zichtbare product ID's op te halen en deze te matchen aan de ID's die in de facetten bewaard zijn. Hierna blijven per facet enkel nog de zichtbare ID's over.

Het ophalen van alle ID's is een vrij eenvoudige query:

SELECT p.id 
FROM products AS p  
WHERE p.visible = 'Y' AND p.language = 'nl' 
AND p.publish_on <= '2013-06-13' AND p.publish_until >= '2013-06-13';

Deze query is ook identiek voor elke zoekopdracht die de gebruiker uitvoert. De query zal uitgevoerd worden, ongeacht de combinatie van facetten. Sterker nog, deze query is identiek voor elke bezoeker die vandaag de Nederlandstalige producten bekijkt. Daarom kozen we ervoor om deze resultaten op te slaan in memcache. De eerste bezoeker van vandaag zal de query uitvoeren en opslaan in memcache. Alle andere bezoekers hoeven deze database query niet uit voeren.

3. Berekeningen in PHP

We hebben nu alle data beschikbaar om volgende zaken te bepalen, zonder nog  een query te moeten uitvoeren:

  • de zoekresultaten (enkel de product ID's)
  • het totaal aantal zoekresultaten
  • het aantal zoekresultaten per facet

Het is nu maar een kwestie van via PHP de ID's van de facetten te crossmatchen en het aantal zoekresultaten te bepalen. De ID's zitten in een array per facet. Onze eerste reflex was een array_intersect tussen alle geselecteerde facetten (je weet dan welke ID's voorkomen in alle geselecteerde facetten). Dit zijn de zoekresultaten die je gebruiker wil zien, en dat werkt perfect om enkel de zoekresultaten te bepalen.

Als we terug naar het voorbeeld van 40 facetten gaan, dan moet deze array_intersect ook weer 40 maal uitgevoerd worden om voor elk facet de counts te berekenen. Dit blijkt niet zo vlot te gaan. Tijdens een presentatie van Patrick Allaert op PHPBenelux 2012 leerden we dat PHP een stuk efficiënter omgaat met array keys dan met zijn values. We passen de array_intersect aan naar volgende code:

$resultIds = array_intersect_key(array_flip($facet1Ids), array_flip($facet2Ids));

Het resultaat is een stuk efficiënter en zorgt voor een vlotte berekening van alle 40 facetten.

Resultaat

Een zoekopdracht verloopt na deze optimalisaties als volgt:

  • alle facetten ophalen inclusief product ID's (query)
  • alle zichtbare product ID's ophalen (query of memcache)
  • zichtbare ID's crossmatchen aan facetten (in PHP)
  • per facet de counts berekenen (in PHP)
  • alle producten van de huidige pagina ophalen (query met een IN())

Disclaimer: de code en de voorbeelden zijn vereenvoudigd om het probleem en de oplossing duidelijk te maken.

Conclusie

De laatste oplossing, die een combinatie van verschillende optimalisaties implementeert, is in de meeste gevallen een goede keuze geweest. Indien nodig kunnen we hier nog verder optimaliseren door bepaalde stukken van de berekeningen in PHP ook in memcache te bewaren. Deze optimalisaties zijn sterk afhankelijk van elke dataset, wat maakt dat ze vaak projectafhankelijk zijn. In de toekomst willen we nog andere oplossingen implementeren zoals ElasticSearch.

Interesse om mee te werken?

We zijn nog op zoek naar developers met passie voor het web. Bekijk de vacature.

Lees meer

Nieuwsbrief

Doe zoals meer dan 1700 marketing en design experts en ontvang maandelijks onze nieuwsbrief vol inzichten, tips en verrassende nieuwigheden.