[SQL] Search optimaliseren *

[Verwijderd]

Ik ben bezig met een kleine zoekmachine en heb de volgende tabellen:
tabel "links" met kolommen (id, naam, link)
tabel "woorden" met kolommen (id, woord)
tabel "koppel" met kolommen (id, wordid, linkid)

In de "woorden" tabel staan alle woorden die in de kolom "naam" staan van de "links" tabel". In de "koppel" tabel staat vervolgens aangegeven welk woord in welke linknaam voorkomt.

Misschien maakt het volgende het makkelijker te begijpen (dit zijn de koppelingen)

koppel.wordid=woorden.id
koppel.linkid=links.id

Om links te krijgen die voldoen aan voorwaarden "cafe" of "rock" doe ik de volgende query:

SELECT l.* from woorden w left join koppel k on w.id=k.wordid left join links l on k.linkid=l.id where w.woord in ( 'rock' , 'cafe' )

Om links te krijgen die voldoen aan voorwaarden "cafe" _en_ "rock" doe ik de volgende query:

SELECT l.* from woorden w left join koppel k on w.id=k.wordid left join links l on k.linkid=l.id where w.woord like '%rock%' and w.woord like '%cafe%'

Het mag duidelijk zijn dat de 2de query een stuk langer duurt dan de eerste (ivm met LIKE).

Is het mogelijk om de 2de query ("cafe" _en_ "rock") te versnellen?

De indexen op de verschillende kolommen staan overigens goed.

[justmental]

Die 2e query zal zo niet goed werken.
Je moet links 2x joinen met de andere 2 tabellen.
Dus een w2 en een k2 erbij, alle 5 de tabellen joinen en w.woord = "cafe" en w2.woord = "rock"

[Glimi]

Mjah, die tweede query zal nooit z'n indexen op de textkolommen gaan gebruiken omdat je op non-const (prefix-%) waardes gaat matchen. Zie daarvoor de manual (deel 'How MySQL uses indexes')
Waarom probeer je daar niet een FULLTEXT match op te maken?

[whoami]

Welk DBMS gebruik je?

Zoals Glimi zegt zal een query met een LIKE '%blaat%' nooit indexen kunnen gebruiken, waardoor de boel dus traag zal zijn.

[bigtree]

Aangezien een EN-zoekopdracht toch al vrij strikt is, waarom gebruik je dan geen WHERE w.woord = 'woord' in plaats van LIKE? Je zegt immers:

Om links te krijgen die voldoen aan voorwaarden "cafe" _en_ "rock" doe ik de volgende query

maar je zoekt feitelijk op de voorwaarden "*cafe*" _en_ "*rock*".

[Verwijderd]

Glimi, klopt dat had ik bij EXPLAIN al gezien, daarom vroeg ik of het niet wat efficienter kon Ik gebruik geen FULLTEXT omdat het momenteel nog gaat om een paar duizend records, maar als m'n spider aan de gang gaat kan het gauw oplopen tot een miljoen records, het bleek dat de setup die ik nu heb sneller was dan een fulltext search. Bovendien weet ik niet of ik met mysql blijf werken.

whoami, ik gebruik nu nog mysql 3.23.56.

bigtree, daar heb je gelijk in, maar dat is ook de bedoeling, ik zou graag links terug willen hebben die cafe en rock in hun omschrijving hebben, dat kan zijn als een apart woord, maar het kan ook zijn in een heel woord.

justmental, ik zie nu ook dat er iets verkeerd zit, maar ik begrijp niet helemaal wat je bedoeld, moet ik de woorden en koppel tabel 2x joinen?

[bigtree]

Verwijderd schreef op 04 July 2003 @ 12:18:
[...]ik zou graag links terug willen hebben die cafe en rock in hun omschrijving hebben, dat kan zijn als een apart woord, maar het kan ook zijn in een heel woord.

Dat kan ik je van harte afraden. Het is nooit handig om te zoeken op delen van woorden, performace-wise. Doet google ook niet trouwens. Dus zouden mensen hier op zitten te wachten?

[justmental]

Verwijderd schreef op 04 July 2003 @ 12:18:
justmental, ik zie nu ook dat er iets verkeerd zit, maar ik begrijp niet helemaal wat je bedoeld, moet ik de woorden en koppel tabel 2x joinen?

Je zoekt een topic waar het woord 'rock' en het woord 'cafe' in voorkomen.
In de woorden tabel zijn dit 2 verschillende records.
Bij deze 2 records zoek je links die via de koppeltabel aan deze beide woorden hangen.
w1->k1->l1
w2->k2/
Dus 5 tabellen om aan elkaar te hangen.

[bigtree]

edit:
foutje, ging uit van de OR-constructie.

[ Voor 109% gewijzigd door bigtree op 04-07-2003 13:34 ]

[Verwijderd]

Daar heb je een punt bigtree, die vereiste zal ik dan maar laten vallen

Ik begin het te snappen justmental, je bedoelt een query zoals:

===========
SELECT l.* from
woorden w1 left join koppel k1 on w1.id=k1.wordid
left join links l on k1.linkid=l.id

left join koppel k2 on k2.linkid=l.id
left join woorden w2 on w2.id=k2.wordid

where w1.woord ='cafe' and w2.woord ='rock'
===========

Net even getest en hij blijkt aardig te werken. Maar wat ik me afvraag is het niet inefficient om bij elk woord een 2 extra tabellen te joinen. Zo krijg ik bij 4 woorden een query zoals:

===========
SELECT l.* from
woorden w1 left join koppel k1 on w1.id=k1.wordid
left join links l on k1.linkid=l.id
left join koppel k2 on k2.linkid=l.id
left join woorden w2 on w2.id=k2.wordid
left join koppel k3 on k3.linkid=l.id
left join woorden w3 on w3.id=k3.wordid
left join koppel k4 on k4.linkid=l.id
left join woorden w4 on w4.id=k4.wordid
where w1.woord ='cafe' and w2.woord ='rock' and w3.woord='hoi' and w4.woord='daag'
===========

[bigtree]

Verwijderd schreef op 04 July 2003 @ 14:11:[...]
Maar wat ik me afvraag is het niet inefficient om bij elk woord een 2 extra tabellen te joinen.

Het hangt er van af of MySQL intern cached of het inefficient is of niet.
Een alternatieve (in mijn ogen minder nette) methode is selecteren met een OR, vervolgens een GROUP BY linkID en dan tellen hoe veel resultaten een link krijgt. Die moet gelijk zijn aan het aantal zoektermen (HAVING dus).

Voorbeeldje:

code:

SELECT l.*, COUNT(*) AS aantalhits FROM woorden w 
INNER JOIN koppel k ON w.id=k.wordid 
INNER JOIN links l ON k.linkid=l.id 
WHERE (w.woord = 'rock' OR w.woord = 'cafe') 
GROUP BY l.id 
HAVING aantalhits = 2

Op deze manier hoef je maar één join uit te voeren. Ben benieuwd wat sneller is.

* bigtree voelt een benchmark aankomen...

[bigtree]

Okee... we have a winner!

De testopstelling:
tabel woorden: 5000 woorden uit een engelse woordenlijst
tabel links: 100 links
tabel koppel: tussen de 6 en 600 koppelingen naar random woorden per link (29.000 records)

Er is één link die gekoppeld is met de woorden 'access' en 'abuse'. Die proberen we dus te vinden in zo kort mogelijke tijd.

Query 1 (de alias-methode):

code:

SELECT l.* from 
woorden w1 left join koppel k1 on w1.id=k1.wordid 
left join links l on k1.linkid=l.id 
left join koppel k2 on k2.linkid=l.id
left join woorden w2 on w2.id=k2.wordid
where w1.woord ='access' and w2.woord ='abuse'

Query 2 (de bigtree(c) GROUP BY-methode):

code:

SELECT l.*, COUNT(*) AS aantalhits FROM woorden w 
INNER JOIN koppel k ON w.id=k.wordid 
INNER JOIN links l ON k.linkid=l.id 
WHERE (w.woord = 'access' OR w.woord = 'abuse') 
GROUP BY l.id 
HAVING aantalhits = 2

resultaten:
query 1: 8.45 sec.
query 2: 0.26 sec. <--

Het maakt (i.v.m. eventuele caching) niet uit in welke volgorde ik de queries op de database afvuur.

Als ik in plaats van 2 trefwoorden zoek naar 4 trefwoorden, worden de tijden respectievelijk:
query 1: 14.28 sec.
query 2: 0.32 sec. <--

[ACM]

Dat vind ik wel bijzonder grote verschillen en erg hoge tijden...

En ik denk dat je de left joins wat vreemd geformuleerd hebt, hoe doet deze het?:

code:

SELECT l.*
FROM
  links l, koppel k1, woorden w1, koppel k2, woorden w2
WHERE
  l.id = k1.linkid AND l.id = k2.linkid
AND
  k1.wordid = w1.id AND w1.woord = 'access'
AND
  k2.wordid = w2.id AND w2.woord = 'abuse'

En dan op koppel uiteraard een index op woordid en op woorden een index op woord.

Heb je trouwens ook gechecked dat je dezelfde resultaten krijgt?

[ Voor 4% gewijzigd door ACM op 05-07-2003 01:29 ]

[bigtree]

ACM schreef op 05 July 2003 @ 01:28:
Dat vind ik wel bijzonder grote verschillen en erg hoge tijden...

Het kwam waarschijnlijk door die brakke left-join constructie. Dat het absoluut hoge getallen zijn komt wellicht dat mijn servertje een Celeron @ 400 Mhz is.

En ik denk dat je de left joins wat vreemd geformuleerd hebt, hoe doet deze het?:

Ah! Die doet het al een stuk beter. De tijden worden nu:

query 1: 0.25 sec.
query 2: 0.23 sec. <--

Dit ontloopt elkaar nauwelijks meer.

En dan op koppel uiteraard een index op woordid en op woorden een index op woord.

In koppel had ik al een UNIQUE op woordid en linkid (in die volgorde) dus dat komt op hetzelfde neer. Als ik in woorden een index zet op woord, vliegen de tijden nog verder naar benee:

query 1: 0.023 sec.
query 2: 0.011 sec. <--

Procentueel wordt query 2 nu sneller, maar query 1 blijkt gevoeliger voor caching. Als ik de test nogmaals uitvoer, worden de tijden:

query 1: 0.007 sec. <--
query 2: 0.011 sec.

Heb je trouwens ook gechecked dat je dezelfde resultaten krijgt?

Yep.

Voor de liefhebbers heb ik ook even een gedenormaliseerde koppeltabel gemaakt . Hierin zitten dan al de woorden in plaats van links naar de woordentabel, en er zit een index op woord + linkid. De tijden worden nu:

query 1: 0.009 sec. <--
query 2: 0.014 sec.

_{Als ik dinsdag terug kom ga ik weer verder experimenteren.}