[MySQL] Snel en efficient indexeren en zoeken

[Verwijderd]

Tot nu toe heb ik eigenlijk alleen ervaring met kleine databases, maar voor een nieuw project gaat de database zeker honderd miljoen records bevatten. Het gaat om het indexeren van berichten zoals emails, waarbij door de subject van de email gezocht moet kunnen worden. De database is nu nog leeg omdat ik eerst wil weten hoe ik deze het beste kan vullen.

Wat ik uiteindelijk wil bereiken is dat de gebruiker met een zoekopdracht "eten jan piet" de volgende onderwerpen zal vinden, en dan uiteraard binnen enkele milliseconden:

- eten jan-piet
- etentje jan piet
- RE: etentje janpiet

Wat ik heb geprobeerd is het onderwerp filteren zodat alleen kleine letters en cijfers overblijven. De bovenstaande onderwerpen zouden dan zo in de database staan:

- etenjanpiet
- etentjejanpiet
- reetentjejanpiet

Om vervolgens met ieder trefwoord in een LIKE QUERY door de onderwerpen te zoeken:

SELECT * FROM table WHERE indx LIKE %eten% AND indx LIKE %jan% AND indx LIKE %piet%;

Ik ben alleen bang dat dit traag gaat worden naarmate de database groter gaat worden.

Wat is in dit geval wijsheid qua indexeren en zoeken in de database?
Berichten worden overigens nooit geupdate, het is eenmalig inserten en daarna alleen zoeken.

[moto-moi]

Ik denk dat deze blogposting wel zo'n beetje alles zegt: http://www.mysqlperforman...ta-retrieval-accelerator/

Je kunt beter naar een extern product kijken voor je zoekmachine, bijvoorbeeld sphinx zoals aangegeven wordt in die blogposting, of iets als xapian omega zoals we hier op GoT gebruiken

[Verwijderd]

Gebruik van een extern product zou eventueel mogelijk zijn, maar liever niet

[Mafkees]

Is FULLTEXT search geen optie? Heb ik vrij weinig ervaring mee maar ik weet wel dat het goed werkt. Voor fulltext searches werkt het ding met indexes wat sneller is.

[Janoz]

In dit geval is het geen optie. TS wil ook op delen van woorden kunnen zoeken. Dat is bij fulltext niet (zommaar) mogenlijk.

[Mafkees]

Hm da's waar, dan zou je bij elk woord een sterretje ervoor en achter moeten doen. Maar goed, da's meer een workaround

Maar om terug te komen op de TS.. Je kunt natuurlijk zelf gaan testen hoe de database performed zodra je een selectie uit een paar honder duizend records gaat maken. Maak een mooi benchmark scriptje oid en je bent er snel genoeg achter. Dan krijg je iig een indruk

[Verwijderd]

Uiteraard ga ik testen

Ik vind het daarnaast ook interessant om erover te discussieren met mensen die er ervaring mee of verstand van hebben. Misschien zit ik wel vreselijk op het verkeerde spoor

LIKE Queries zijn van nature vrij traag, dat ben ik mij bewust. Het belangrijkste punt is op dit moment nog, hoe moet ik de boel indexeren in de SQL database. Doe ik het juist door ruis en spaties weg te filteren, of kan ik beter ieder woord in een losse record plakken?

Dat laatste lijkt mij persoonlijk geen goed idee, want dan is het ook niet meer mogelijk om bijvoorbeeld te zoeken op "jan piet" inclusief quotes, zoals je bijvoorbeeld in Google ook kunt zoeken.

[ Voor 53% gewijzigd door Verwijderd op 25-01-2007 11:40 ]

[curry684]

Kerel, wat je hier probeert te doen heeft een groot bedrijf als Google al problemen mee, en jij denkt het even met een DB als MySQL te doen op een tabel met miljoenen records? Op z'n zachtst gezegd: succes

Realistisch: zoek een out-of-the-box oplossing. Hier zijn algoritmes voor, maar die implementeer je niet zo even tussen neus en lippen door zelf.

[__fred__]

Je zou eens kunnen beginnen met alleen de stam van je woorden opslaan in een woordenboek.
Implementeer een aantal regels om grofweg de stam van een woord te bepalen en sla die op in een clustered index. (hash desnoods om bytes te besparen)

verwijder woorden die nietszeggend zijn (lidwoorden, voorzetsels, etc.etc.)

vervolgens leg je per subject vast welke stammen van woorden erin voorkomen via een parent child relatie.

Is een aardig begin.

[Voutloos]

Onthouden: LIKE '%waEenWildcardAanHetBegin' is een absolute no-go.

Met een aantal andere zaken kan je vrij ver komen, maar puntje bij paaltje wil je iets snellers dan wat mysql te bieden heeft, van fulltext-search ga je bij dit soort aantallen ook al vrij snel balen.

__fred__ schreef op donderdag 25 januari 2007 @ 22:42:
Is een aardig begin.

Een begin ja, helaas kost dat begin al meer tijd dan het onder de knie krijgen van een oplossing als spynx.

[__fred__]

Voutloos schreef op donderdag 25 januari 2007 @ 22:59:
Een begin ja, helaas kost dat begin al meer tijd dan het onder de knie krijgen van een oplossing als spynx.

Gebruik van een extern product zou eventueel mogelijk zijn, maar liever niet

Ik weet natuurlijk niet wat zwaarder weegt voor hem. Het superieure open source product, maar wel extern of het wiel opnieuw uitvinden.

Ik geef alleen een minder vierkant wiel aan dan like over 100m records. ;-)

[kmf]

Misschien een echte indexer gebruiken in plaats van MySQL?
http://www.sphinxsearch.com/
http://xapian.org/

Zoeken door miljoenen records gaat met full text ook niet lekker...

[PrisonerOfPain]

__fred__ schreef op donderdag 25 januari 2007 @ 22:42:
vervolgens leg je per subject vast welke stammen van woorden erin voorkomen via een parent child relatie.

Andersom (Inverted Index) geeft een hogere performance (zie onderandere Lucene of de PHP implementatie Zend_Search_Lucene). Je slaat dus voor ieder woord welke documenten er aan gelinked zijn in plaats van per document de woorden opslaan.

code:

stam  | documenten
fiets | 1, 4, 6, 10
kaas  | 1, 9, 3, 2

In plaats van

code:

stam_id | stam
1       | fiets
2       | kaas

stam     | document
1        | 1
1        | 4
1        | 6
1        | 10
2        | 1
2        | 9
2        | 3
2        | 2

of

code:

document | stammen
1        | fiets kaas
2        | kaas
3        | kaas
4        | fiets
6        | fiets
9        | kaas
10       | fiets

[ Voor 11% gewijzigd door PrisonerOfPain op 25-01-2007 23:19 ]

[Verwijderd]

Bedankt voor de reacties zover

De genoemde "echte indexers" zijn zeker interessant en gaan we zeker in overweging nemen, maar we moeten nog overleggen qua licenties en eventueel extra hardware, op dit moment worden alleen Windows servers gebruikt voor dit project.

Het wiel twee keer uitvinden is natuurlijk niet de bedoeling, maar we willen wel volledige vrijheid en controle over de broncode houden. Het idee van stammen gebruiken en lidwoorden weglaten ziet er interessant uit, met een beetje geluk kan de performance hier nog iets mee omhoog geschroefd worden.

Niemand ervaring met grote databases doorzoeken?

[Verwijderd]

Verwijderd schreef op vrijdag 26 januari 2007 @ 01:28:


Niemand ervaring met grote databases doorzoeken?

jawel, maar text retrieval op grote databases koop je meestal in.
vraag me af of jullie wel weten waar je mee bezig bent, als je dit
soort zaken op een forum moet vragen, zeker gezien in combinatie
met je startpost met minieme info

[Verwijderd]

mischien kun je iets meer opheldering geven waarvoor het precies wordt gebruikt, neem niet aan dat je 100miljoen emailtjes per maand te verwerken hebt, dus tenzij je een flink pak werknemers ofzo hebt is die 100miljoen mischien ook wel wat hoog geschat, meende dat amazon slecht iets van 13miljoen record had dus.

verder lijkt mij vooral dat je ook wel een beest van een server configuratie nodig hebt, en eigenlijk over hoeveel bezoekers per minuut spreken we eigenlijk, dat bepaalt ook wel welke methode beter is.

ik denk dat fulltext searching nog best te doen is als je niet massa's van mensen per minuute query invullen, dan zou een zoektijd van 1seconden nog best redelijk zijn. miliseconden haal ze zowieso niet omdat alleen het opbouwen van de connectie al zo 20miliseconden duurt.

ik zelf heb niet echt veel ervaring met echt grote databases maar heb wel eens een test-case gemaakt waarbij ik enkele honderdduizend records nog binnen 1 seconde kon doorzoeken. ik was dan wel de enige bezoeker maar de server was dan ook maar ahtlonXP2800+ met 512mb ram en ik had mysql absoluut niet geoptimaliseerd.

verder zou ik inderdaad LIKE vermijden. wat je simple zou kunnen doen is van elk word de stam pakken en die als appart record in de database zetten. dubbelen uiteraard vermijden en ook lidwoorden en tussenvoegsels etc. verwijderen.

verder als het echt groot wordt kun je inderdaad beter voor een totaal oplossing gaan dan het wiel proberen opnieuw uit te vinden. kies dan natuurlijk voor een GPL oplossing zodat je de code in eigen beheerhebt en dus kunt aanpassen wanneer nodig.

[Verwijderd]

Het gaat om een soortgelijke website als Google Discussiegroepen:
http://groups.google.nl/g...&oe=UTF-8&hl=nl&tab=wg&q=

Alleen wil de klant daarnaast ook door ruim 6000 binary niewsgroepen kunnen zoeken. Bij binaries hoef je uiteraard alleen door de onderwerpen te zoeken, niet door de inhoud zelf. Honderd miljoen is wellicht overdreven, maar ik ga uit van een worst case scenario.

In ieder geval bedankt voor de reacties.

[curry684]

Verwijderd schreef op vrijdag 26 januari 2007 @ 01:28:
we willen wel volledige vrijheid en controle over de broncode houden. Het idee van stammen gebruiken en lidwoorden weglaten ziet er interessant uit, met een beetje geluk kan de performance hier nog iets mee omhoog geschroefd worden.

Niemand ervaring met grote databases doorzoeken?

Jawel, Gathering of Tweakers met een database van 40 gigabyte. Daarom gebruiken zij Xapian, dat open source is, stammen gebruikt en lidwoorden negeert, en als zuivere C++ oplossing heel performant is.

[Verwijderd]

Curry, ik waardeer je reacties, maar ik ben inmiddels op de hoogte dat er kant en klare pakketten voor beschikbaar zijn. Wat ik nog meer zou waarderen zijn wat tips en het liefste ervaringen van mensen die zelf aan de slag zijn geweest, dit is immers het "Devschuur" forum en niet het "Softe goederen" forum.

curry684 schreef op vrijdag 26 januari 2007 @ 10:08:
[...]

dat stammen gebruikt en lidwoorden negeert, en als zuivere C++ oplossing heel performant is.

Dat zijn nuttige tips

[curry684]

Verwijderd schreef op vrijdag 26 januari 2007 @ 11:47:
Curry, ik waardeer je reacties, maar ik ben inmiddels op de hoogte dat er kant en klare pakketten voor beschikbaar zijn. Wat ik nog meer zou waarderen zijn wat tips en het liefste ervaringen van mensen die zelf aan de slag zijn geweest, dit is immers het "Devschuur" forum en niet het "Softe goederen" forum.

Ja, en ik ben 2 jaar moderator in de Devschuur geweest, en kan je uit ervaring vertellen dat je niet de eerste bent die in een project dacht dat een intelligente search wel even zo met een LIKE-query te bouwen was. Ik ben de realist die je vertelt dat dat kansloos is en het inkopen van een kant en klare oplossing (gratis zelfs vaak) kostentechnisch de enige aantrekkelijke optie is als je het in 2007 nog live wil hebben.

Dat zijn nuttige tips

Astu