Een zoekmachine bouwen #3 - 't Leed dat index heet
15 januari 2018In deze serie bespreek ik de ontwikkeling van mijn zoekmachine tot in detail, waarbij ik zowel alle zaken die goed gaan als zaken die niet goed gaan bespreek. In deze editie heb ik het o.a. over een aanpassing van het ranking algoritme en over de problemen die je kunt krijgen met indices in MySQL bij grotere datasets.
Aanpassing in het ranking algoritme
Een bekende feature die Google hanteert is dat content die bovenaan de pagina staat, of mogelijk zelfs aan het begin van een element (zoals een h1) meer waarde heeft dan wat onderaan staat.
Dit is logisch te verklaren: ook gebruikers 'scannen' een website voordat ze de content gaan lezen. Het is dus voor een bezoeker van belang dat belangrijke kernwoorden ('zoekwoorden') op een prominente plek staan. Anders klikken ze weer weg, wat resulteert in een hogere bounce rate. De conclusie: deze website is niet waar de gebruiker naar op zoek was.
Om dit te faciliteren heb ik de berekening zo gemaakt dat de waarde van een keyword of key phrase met 1% per woord afneemt. Als de kop "internet marketing blog voor ondernemers" is, wordt 100% score gerekend voor "internet", "internet marketing" en "internet marketing blog". Voor het keyword "marketing blog" wordt dan bijvoorbeeld slechts 99% van de score toegekend. En het keyword "ondernemers" krijgt 96% van de score toegekend.
Indices in MySQL
Het is algemeen bekend dat een index op een kolom toevoegen in MySQL een gigantische verbetering in de performance kan opleveren. In het geval van joins wordt wel eens gesproken van een cartesisch product van twee tabellen, ofwel het samenvoegen van twee losse tabellen tot één grote tabel op basis van de criteria in de join. Op deze manier wordt de hoeveelheid data in feite veel groter en dit kan performance issues met zich meebrengen. (Kleine kanttekening: het cartesisch product is een theoretisch concept en database engines gaan verschillend om met deze situatie, neem dit dus met een korrel zout.)
Met indices gebeurt in feite hetzelfde: bij het gebruik van twee indices wordt de hoeveelheid data waarin gezocht moet worden veel groter. En dit verschil is duidelijk merkbaar. Ik had de volgende query opgebouwd om niet-geindexeerde links te vinden:
SELECT url FROM link WHERE indexed = 0 and cache_id > 0 LIMIT 1
Op zowel "indexed" als "cache_id" zit een index. Toch merkte ik na verloop van tijd (na ca. een miljoen URL's te hebben verzameld) dat dit voor performanceproblemen ging zorgen. Denk dan niet aan 10% of 20% performanceverlies, maar een veelvoud daarvan. Deze query duurde op een zeker moment 0.3 seconden.
Verder optimaliseren was vanwege de opbouw geen optie, dus moest de database aangepast worden. Voor links met deze kenmerken is er een extra kolom toegevoegd (met een index) genaamd 'ready_for_indexing'. Het resultaat? 0.0002 seconden.
SELECT url FROM link WHERE ready_for_indexing = 1 LIMIT 1
Met een simpele handeling als dit, is wederom een performanceprobleem getackeld.
De huidige stand van zaken?
In totaal is de database 6,2 GiB groot, met 1,015,804 unieke URL's en 14,496,947 zoektermen. Op dit moment zijn er 436,460 pagina's geindexeerd. De gemiddelde download/preformatting (stage 1) snelheid is ~600 per minuut. De gemiddelde indexeersnelheid (stage 2) is nu ~700 pagina's per minuut en de grootste bottleneck lijkt nog altijd de database te zijn.
Nog lang niet voldoende voor mijn target van 25 miljoen, maar meer dan genoeg voor de eerste testing! :-)
To do voor volgende update:
- Als er een HTTPS variant beschikbaar is, deze prefereren boven de HTTP variant
- Als er een non-www variant is, deze prefereren boven de www variant
- Niet alleen de redirects op een pagina volgen, maar ook behandelen als nieuwe link
- Geen rel="nofollow" links volgen
- Robots.txt volgen
- Penalty voor keyword stuffing d.m.v. bovenmatig kommagebruik
- Extreem lange meta descriptions, titles, etc. afkorten en getrimd gedeelte niet meenemen in score
- Response header opslaan bij URL (200, 404, 301, etc.)
- Taalherkenning op basis van N-grams (zie
"N-gram models for language detection" door Carlos Ramisch)
Internet Marketing
Een zoekmachine bouwen #8 - PageRank, Zoeken, etc.Geplaatst op 5 december 2019
Een zoekmachine bouwen #7 - Backlinks & Tabellen
Geplaatst op 22 juli 2018
Een zoekmachine bouwen #6 - Full page cache
Geplaatst op 13 juli 2018
Een zoekmachine bouwen #5 - Een stap verder
Geplaatst op 11 juli 2018
Auteur: Edwin Dijk
TimeTick producten
Urenregistratie software
Gratis urenregistratie software