[MySQL] Select query te traag door tmp table: hoe beter?

[max3D]

Ik ben een nieuwkomer in SQL dus het kan zijn dat er een simpele oplossing is, maar ik kan nergens een goede hint vinden.

Ik zit met volgende probleem: ik moet zoeken op n criteria op hetzelfde veld in een tabel. Dit gaat in een aantal gevallen al mis als N nog maar 3 is; het duurt dan veel te lang omdat MySQL een temporary table gaat aanmaken met een groot aantal records.

Ik gebruik de query:

code:

 SELECT DISTINCT M1.Tekstnr FROM woordtekst M1, woordtekst M2, woordtekst M3 
WHERE M1.Tekstnr = M2.Tekstnr AND M1.Tekstnr = M3.Tekstnr AND 
M1.Wkey = 136290 AND M2.Wkey = 136437 AND M3.Wkey = 136449

De bedoeling is om een groot aantal teksten zoekbaar te maken door alle woorden (uitgezonderd stopwoorden) in een tabel op te nemen. Om efficiency redenen heb ik alle unieke woorden in een aparte tabel gezet. Die zijn gekoppeld aan een key, die leidt naar een woordnr/tekstnr tabel waar alle entries voor dat woord in staan en die wijzen dan naar een tabel met de echte teksten.

Als ik wil weten of een woord in een tekst voorkomt zoek ik dus eerst de unieke Wkey voor dat woord en doe daarmee een SELECT tekstnr FROM woordtekst WHERE wkey = xxx". Gaat razendsnel. (voor de duidelijkheid ik doe dit in dus vanuit VBA in losse queries, waarbij Wkey in een variabele gestopt wordt)

Bij twee woorden (xx AND yy) gaat het ook perfect, maar bij 3 woorden stort het tempo compleet in als de zoekwoorden te populair zijn omdat MySQL dan een temporary table gaat aanmaken voor de minst gebruikte zoekterm.

Kan ik dat efficienter oplossen? Als ik kijk naar de EXPLAIN output zie ik dat MyQL keurig het minst gebruikte zoekwoord neemt als basis voor de temporary table, maar het aantal rows totaal kan bij populaire termen oplopen tot 11615 USING WHERE; USING TEMPORARY TABLE X 32 X 32 en dat duurt oneindig.

Een oplossing voor N woorden is het dus al helemaal niet.

Hoe los ik dat slimmer op?

[ACM]

Ik schud er nu twee uit mijn mouw, een die ik al eerder genoemd heb ooit in een paar topics hier:

SELECT Tekstnr, COUNT(*) AS wordcount FROM woordtekst WHERE wkey IN ($1, $2, $3, ... $n) GROUP BY Tekstnr HAVING wordcount = n

Voor een OR-versie moet je wordcount > 1 nemen
Maar ook die is niet enorm snel met veel woorden.

Een andere oplossing kan zijn om steeds een soort boom te maken met "subqueries" en de resultaten daarvan in temporary tables te stoppen. Bijvoorbeeld door bij de woorden ook bij te houden in hoeveel documenten ze in totaal zitten en daarop gesorteerd (kleinsten eerst) de boel steeds te AND-en, het resultaat daarvan in een temporary table te stoppen en door te gaan met de volgende. Dan krijg je dus iets als:

SELECT Wkey FROM woorden WHERE woordtekst IN ($word1, ... $wordn) ORDER BY doccount
CREATE TEMPORARY TABLE subresult (docid integer) AS SELECT docid FROM woordtekst WHERE woordid = $wordid1;
while($wordid = $wordid2 ...)
{
CREATE TEMPORARY TABLE subresultX AS SELECT docid FROM woordtekst, subresult WHERE woordid = $wordid AND docid = subresult.docid;
}
SELECT * FROM subresultN

Maar of dat efficient is?

[max3D]

Die eerste oplossing lijkt me briljant! N termen zijn dan echt mogelijk. Net even getest en het gaat snel, maar het geeft andere resultaten dan mijn lelijke oplossing. Ik zal het wat exacter analyseren en morgen op terug komen.

De tweede oplossing had ik al eens geprogrammeerd (ik hou tbv debugging nog bij hoevaak de woorden gebruikt zijn in een veld FREQ, dus dat was gemakkelijk te implementeren). Helaas leek dat erg traag. Het aantal rijen in woordtekst is dan ook al iets van 4 miljoen.

[ Voor 46% gewijzigd door max3D op 16-03-2004 00:48 . Reden: onverwachte resultaten van query: morgen meer ]

[max3D]

Het heeft me uren gekost, maar ik ben erachter waarom ACM's eerste methode geheel andere resultaten oplevert. Hij gaat er impliciet van uit dat WKey maximaal een keer in een tekst staat. Dat is echter niet het geval (ik wil ook kunnen zoeken op woord NEAR woord dus sla ik alle instanties op in de woordtekst tabel incl hun positie).

De count conditie faalt dus voor woorden die vaker dan 1 x in een tekst staan
(want ook als slechts een van de gezochte argumenten drie keer voorkomt en de andere twee ontbreken krijg ik natuurlijk een hit zo)

Is daar een manier omheen te verzinnen? Zijn methode blijkt namelijk op zich razendsnel vergeleken met mijn eigen query.

[ Voor 12% gewijzigd door max3D op 16-03-2004 17:14 . Reden: kon nog duidelijker ]

[ACM]

COUNT(DISTINCT(Wkey)) =n gebruiken?

[beetle71]

Heb je niet toevallig de beschikking (of mogelijkheid) voor MySQL 4.x, dan kun je gebruik maken van de FULLTEXT index en de 'IN BOOLEAN' mode die daarbij zit,
zie http://www.mysql.com/doc/en/Fulltext_Search.html

[max3D]

@beetle71:
Dank voor de tip. Ik weet van het bestaan van de full text search, maar eigenwijs als ik ben, denk ik dat ik het sneller en compacter kan. Wie weet ga ik daar alsnog op over, maar voorlopig worstel ik nog even verder.

@ACM:
again: puike suggestie, maar wel wat haken en ogen die ik in de volgende post zet.

Nu waarom het zo'n perfecte oplossing is: de tijden!
De navolgende resultaten zijn op een database met 4 miljoen woorden (de woordtekst tabel)

De tijden zijn in seconden, gaan uit van 3 zoektermen en zijn gesorteerd op oplopende frequentie van de zoektermen.
Originele query / tijd ACM's oplossing
3 / 3
11 / 13
18 / 42
28 / 11233

die laatste is geen vergissing. In de worst case (de drie populairste zoektermen) duurt het dik 3 uur ipv een halve minuut!

Wie een AND constructie zoekt voor values in een zelfde tabel moet dus altijd voor de IN (....) constructie kiezen.

[max3D]

Nu het probleem wat mede ontstond door de noodzakelijke DISTINCT(Wkey)) toevoeging.

Ik wil desgewenst ook kunnen zoeken op term NEAR andere term (met NEAR een waarde naar eigen keuze van de gebruiker), vandaar dat ik alle woorden in tabel woordtekst heb staan met hun woordpositie.
Ik krijg iedere tekst nu nog maar eenmaal terug na deze noodzakelijke DISTINCT dus ik moest een nieuwe query bedenken voor de NEAR case.

Na lang puzzelen (SQL blijkt toch heel anders dan procedureel programmeren) kwam ik op het volgende statement:
SELECT DISTINCT db1.woordpositie, db2.woordpositie
FROM woordtekst db1, woordtekst db2
WHERE ABS((db2.woordpositie - db1.woordpositie)) < 10 AND (db2.woordpositie - db1.woordpositie) > 0
AND db1.wkey IN ('123', '456') AND db2.wkey IN ('123', '456')
AND db1.tekstnummer=12345 AND db1.tekstnummer = db2.tekstnummer;

Ik voer deze tbv efficiency pas uit nadat ik de eerste test op a AND b AND c etc gedaan heb. De waarden voor de twee Wkey's en het tekstnummer rollen daar uit.

De query is gebaseerd op het idee dat een woord (wkey) meerdere keren in een tekst kan staan, maar dat het genoeg is als hij EEN keer dicht bij de andere term staat (waarvoor natuurlijk hetzelfde geldt).

Nu het probleem: deze query werkt perfect, BEHALVE als beide termen maar een keer in de tekst staan! Wat ik ook doe en puzzel lukt het me niet meer om dit subprobleem ook in de query te krijgen.

Als gezegd, SQL blijft nieuw voor me; iemand een tip?

[ACM]

Goed, nu ga ik je een andere kant op schoppen

Smijt SQL weg voor een full text search, 't is er niet voor geschikt en zal er ook nooit geschikt voor worden. De record-based werking is gewoon dusdanig veel overhead dat je nooit de efficientie van andere systemen behaald. Wij hebben die keuze ruim een jaar geleden gemaakt en zijn voor een combinatie van MySQL (voor alles behalve de searchengine) en Xapian als searchbackend (maar dus verder niets dan dat) gegaan.
Zoek de mailinglists van Xapian na (op sourceforge of op gmame oid) en zie daar mijn discussies met allerlei developers voor als je vragen hebt
Vooral de discussies van de afgelopen maand zouden je moeten helpen bij specifieke vragen (er was toevallig iemand die een systeem met Xapian "from the ground up" aan het opzetten was en alles vroeg waar ie tegenaan liep).
Andere oplossingen dan Xapian zijn er uiteraard legio, ieder beter dan welke oplossing die je in MySQL kunt krijgen. Wellicht dat mnogosearch in MySQL je beste kans geeft in MySQL, maar ironisch genoeg is hun "snelste opslagformaat" eentje die niet in MySQL de data opslaat

Xapian bood ons iig veeel meer performance, een uitgebreidere zoektaal, phrase en near-searches.
Andere oplossingen zijn iig Lucene en mnogosearch, meer kan ik er zo uit mijn hoofd niet opnoemen (er zijn er aardig wat meer).

Mocht je het toch in SQL houden, dan loop je tegen de al ondervonden limitaties aan, die maar zelden echt naar voldoening op te lossen zijn. In tegenstelling tot de eerder genoemde searchengines worden de meeste sql-oplossingen die ik gezien heb slomer bij het toevoegen van meerdere keywords (zelfs met AND's!) terwijl andere oplossingen dus juist eerder sneller worden (snellere afname van het aantal daadwerkelijke documenten dat voldoet aan de query).

[max3D]

ACM, bedankt voor je uitgebreide visie op tekstretrieval. Ik heb je suggestie serieus genomen en bijgelezen op Xapian. Blijkt dat ik nota bene ruime ervaring heb met een vroege voorouder (Dialog). Voor dit project is Xapian niet geschikt, maar het hoe en waarom is buiten de scope van dit draadje. Ik open binnenkort wel een apart topic over tekst retrieval, want het interesseert me zeker.

Wat nog openstaat zijn twee dingen:

- iemand toch een idee hoe ik in mijn laatste query ook de gevallen met maar een instantie van ieder keywoord kan vinden?

- Het antwoord op mijn openingsvraag.
De self join methode die ik daar gebruik zou razendsnel moeten zijn, maar die temp table verpest het. Waarom doet MySQL dat?
Als ik het zelf programmeer (even in pseudo gebrabbel):
Lees frequentie van keywords uit tabel
Select zeldzaamste keyword en stop resultaat in array
Ga voor array waarden na of volgende keywoord qua populariteit gelijk tekstnummer heeft
If not, wis uit array
Ga voor resterende waarden naar volgende keywoord in populariteit
Etc. voor alle keywords.
gaat het werkelijk razendsnel. Waarom gaat dat mis in MySQL. De setsize van het minst frequente keyword is nu nog bij lange na niet zo groot dat het niet in het geheugen zou passen.

[max3D]

Ik vergat hierboven dat mijn pseudo algorithme in de praktijk natuurlijk faalt omdat alle records over de client-server lijn heen getrokken moeten worden. Dit zou zich dus binnen MySQL moeten afspelen...

[ACM]

SQL maakt in principe eerst een grote superset en gaat dan alles afstrepen wat niet aan de WHERE voldoet.

Uiteraard is dat vreselijk sloom en proberen dbms-optimisers handigere methoden te vinden om een specifieke query uit te voeren, maar of ie ook in staat is jouw 'beste manier' er uit te bedenken, dat is maar de vraag. SQL werkt dus met de joins die ergens aan moeten voldoen, niet echt met subset-intersecties enzo.

De recursieve-temptable manier die ik eerder hier gaf doet ongeveer wat jij voorstelt, maar dan wellicht wat minder efficient. Ik kan je helaas niet echt veel verder helpen dan de al gegeven ideeen en je eigen query.

Ik bedenk me trouwens nog een variant op de temptable versie. Maak per keyword een temptable aan en ga dan tussen die temptables je gewenste joins doen.
Dat zou zeer efficient moeten kunnen, zeker als je ze van het type HEAP maakt en evt ook een index op de documentids mee geeft.

De vraag is dan of de overhead van het aanmaken van de temptables opweegt tegen de performance winst (moet je dus niet bij slechts 2 keywords doen?)

[ Voor 8% gewijzigd door ACM op 19-03-2004 15:39 ]

[max3D]

Ik ga zodra ik weer even tijd heb testen met de temptable per keyword aanpak. Ik ken de keyword frequency dus ik weet wanneer de selfjoin aanpak te traag gaat worden en kan dus alleen in die gevallen de temptables aanmaken.

Het blijft wel onbevredigend; ik heb 25 jaar geleden SQL geleerd toen DB2 de enige implementatie was en set theorie heel populair op de universiteit. Alles moest met Union / Intersect en de query optimizer werd geacht zelf een bevredigende oplossing te vinden. Hoe je je query ook schreef: als het logisch hetzelfde opleverde was de performance ook identiek, aldus het toenmalig adagium. We hadden een groot vertrouwen in de optimizers

Sindsdien niets meer aan gedaan en een datastructuur ontworpen op mijn beeld van SQL. Lullig om dan nu te ontdekken dat MySQL geen intersect kent en ook geen efficiente optimizer voor dit soort problemen. DB2 is een beetje te duur voor een hobbyprojectje

[ACM]

Als je de geavanceerdheid van DB2 met de prijs van MySQL combineert kom je ongeveer bij PostgreSQL uit (en Firebird en SapDB/MaxSQL maar daar heb ik niet echt veel ervaring mee)

kent wel intersect, union, subselects, e.a En heeft een veel geavanceerdere query-optimiser/planner dan MySQL. Helaas is die laatste er wel de oorzaak van dat de simpelere queries wat trager uitgevoerd worden en dus veel MySQL-addicts de gedachte hebben dat Postgres dus altijd maar traag is (ja, met de meeste queries die juist in MySQL snel wel ja )

[ Voor 3% gewijzigd door ACM op 19-03-2004 18:16 ]