beste manier woordenlijst-zoekstructuur SQL

Pagina: 1
Acties:

  • link0007
  • Registratie: Augustus 2006
  • Niet online
Voor een website waar ik aan bezig ben heb ik een geavanceerde zoekfunctie gemaakt. Deze zoekfunctie heeft redelijk veel ANDs en ORs, en is moeilijk om via indexes te versnellen.

Hij accepteerd een zoek query als
code:
1
"aan elkaar" los


en dan nog een author query op dezelfde manier.

code:
1
"user 1" user twee


Hij zoekt dan in drie tabellen: Scenes, comments en tags naar "%aan elkaar%" of "%los%", met als author "%user 1%", "%user%" of "%twee%"

Daarnaast kan je bepalen in welke groep hij moet zoeken. Hiervoor nemen we even "group 1"


Dit levert dan deze query op:

SQL:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
SELECT DISTINCT scene_id, scene_group, scene_ip, scene_filename, scene_size, scene_title, scene_author, scene_description, scene_password, scene_datetime, scene_rating, scene_nr_downloads, scene_nr_views, scene_nr_comments, scene_nr_ratings, scene_response_to, scene_last_edit, scene_last_edit_by, scene_allow_comments, scene_allow_ratings, scene_allow_responses
FROM pbox_scenes, pbox_comments
comment , pbox_scene_tags tag
WHERE (
    scene_group =1
)
AND (
    scene_author LIKE '%user 1%'
    OR scene_author LIKE '%user%'
    OR scene_author LIKE '%twee%'
)
AND NOT (
    scene_group =0
)
AND (
    scene_title LIKE '%aan elkaar%'
    OR scene_title LIKE '%los%'
    OR scene_description LIKE '%aan elkaar%'
    OR scene_description LIKE '%los%'
    OR (
        (
            tag.tag_name LIKE '%aan elkaar%'
            OR tag.tag_name LIKE '%los%'
        )
        AND tag.tag_scene_id = scene_id
    )
    OR (
        (
            comment.comment_content LIKE '%aan elkaar%'
            OR comment.comment_content LIKE '%los%'
        )
        AND comment.comment_scene_id = scene_id
    )
)



Nu kost dit vaak nogal veel tijd, meer dan de bedoeling is.

Vandaar dat ik wil kijken naar een database met losse zoekwoorden, die linken naar een ID en een type (comment of scene).

Nu heb ik eerlijk gezegt geen idee wat de beste manier voor zoiets is, en internet geeft er niet al te veel over bloot.

Mijn idee is om een tabel te maken met 4 kolommen: id, linked_id, value, type

dan kan ik in ieder voorkomen dat SQL door grote texten gaat zoeken voor een woordje, door gewoon in de woordenlijst te zoeken naar een woordje van een bepaald type, en de linked_id gebruiken om de originele scene/comment te vinden.

Heeft iemand hier ervaring met zulke structuren? Wat zijn de voor en nadelen? Zijn er betere methoden dan wat ik van plan ben?

IF IF = THEN THEN THEN = ELSE ELSE ELSE = IF;


  • RobIII
  • Registratie: December 2001
  • Niet online

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

(overleden)
:X
Al eens gekeken naar fulltext search? Zo'n beetje ieder zichzelf respecterend RDBMS kan dat.
MySQL: http://dev.mysql.com/doc/refman/5.0/en/fulltext-search.html
MSSQL: http://msdn.microsoft.com/en-us/library/ms142571.aspx
link0007 schreef op donderdag 16 oktober 2008 @ 19:54:
Voor een website waar ik aan bezig ben heb ik een geavanceerde zoekfunctie gemaakt. Deze zoekfunctie heeft redelijk veel ANDs en ORs, en is moeilijk om via indexes te versnellen.
Sowieso kun je élke index wel op je buik schrijven bij een Like "%blah%".

[ Voor 125% gewijzigd door RobIII op 16-10-2008 20:04 ]

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Je eigen tweaker.me redirect

Over mij


  • CodeCaster
  • Registratie: Juni 2003
  • Niet online

CodeCaster

Can I get uhm...

Ik heb ooit zelf een indexer geschreven, het principe is heel simpel. Ieder document (hetzij een post op een forum, hetzij een nieuwsartikel op je frontpage) heeft een id, en ieder woord uit je documenten staat in een dictionary met ook z'n eigen id. In een koppeltabel laat je dus zien welke woord_id's voorkomen in welke document_id's, en eventueel een frequentie en/of een positie om de weight te bepalen, scoort een woord als het voorin je document staat hoger, of toch als het vaker voorkomt?

Dit is in principe prima te programmeren, tijdens het implementeren doe je één lange index-run en vervolgens laat je ieder gewijzigd of nieuw toegevoegd document opnieuw indexeren.

Wanneer dat voor te veel load zorgt doe je het gewoon net als GoT, laat de indexer om 1 uur 's nachts 'even' alle nieuwe en gewijzigde berichten opnieuw indexeren.

Het zoeken op groepen woorden kun je dan ook weer zelf afvangen, door te kijken of zoekwoord[1].pos == zoekwoord[0].pos + 1 of iets dergelijks.

De afweging voor het schrijven/aanschaffen/implementeren van een dergelijk systeem zul je echter zelf moeten doen.
AND (
scene_author LIKE '%user 1%'
OR scene_author LIKE '%user%'
OR scene_author LIKE '%twee%'
En dat doe je natuurlijk gewoon in een aparte query, om te kijken of de user waarop gezocht wordt wel bestaat.

[ Voor 16% gewijzigd door CodeCaster op 16-10-2008 20:21 ]

https://oneerlijkewoz.nl
Op papier is hij aan het tekenen, maar in de praktijk...


  • link0007
  • Registratie: Augustus 2006
  • Niet online
RobIII schreef op donderdag 16 oktober 2008 @ 20:00:
:X
Al eens gekeken naar fulltext search? Zo'n beetje ieder zichzelf respecterend RDBMS kan dat.
MySQL: http://dev.mysql.com/doc/refman/5.0/en/fulltext-search.html
MSSQL: http://msdn.microsoft.com/en-us/library/ms142571.aspx

[...]


Sowieso kun je élke index wel op je buik schrijven bij een Like "%blah%".
Zeg ik toch ook: hij bevat veel ANDs and ORs ( en dat is nu eenmaal traag), en hij is van nature moeilijk te indexeren.

Wat codecaster zegt is in principe mijn plan ook. Maar jij gebruikt dus 2 tabellen? Een met woorden, en een die woord-ids koppelt aan scenes of comments.

Dan krijg je dus

tabel words: word_id, word_value
tabel index: index_word_id, index_type, index_link_id, index_word_occurence

dat geeft inderdaad een voordeel dat je kan kijken hoe vaak een woord voorkomt in een stuk text.

Verder bedenk ik net dat ik gelijk alles naar lowercase kan brengen, en misschien zelfs de stam van de woorden kan achterhalen? (volgens mij is zoiets mogelijk in php?)

IF IF = THEN THEN THEN = ELSE ELSE ELSE = IF;


  • Voutloos
  • Registratie: Januari 2002
  • Niet online
(jarig!)
link0007 schreef op donderdag 16 oktober 2008 @ 20:25:
[...]
Zeg ik toch ook: hij bevat veel ANDs and ORs ( en dat is nu eenmaal traag), en hij is van nature moeilijk te indexeren.
Foute generalisatie. Dat hoeft helemaal geen probleem te zijn, zolang je maar ergens een selectieve index kan gebruiken. Punt is gewoon dat LIKE '%leading_wildcard_reutel_reutel%' niet goed een index kan gebruiken. ;)

[ Voor 6% gewijzigd door Voutloos op 16-10-2008 20:50 ]

{signature}


  • Sebazzz
  • Registratie: September 2006
  • Laatst online: 09:39

Sebazzz

3dp

Daarnaast is LIKE volgens mij ook stukken langzamer dan fulltext. ;)

[Te koop: 3D printers] [Website] Agile tools: [Return: retrospectives] [Pokertime: planning poker]


  • Gomez12
  • Registratie: Maart 2001
  • Laatst online: 17-10-2023
link0007 schreef op donderdag 16 oktober 2008 @ 20:25:
[...]
Zeg ik toch ook: hij bevat veel ANDs and ORs ( en dat is nu eenmaal traag), en hij is van nature moeilijk te indexeren.
even ter info, and's / or's zijn niet traag zolang je de indexen maar goed hebt staan. Je like %blah% verhindert alleen elke index.
Sowieso moet je je afvragen of het mogelijk is om dit om te schrijven naar een like blah%
Wat codecaster zegt is in principe mijn plan ook. Maar jij gebruikt dus 2 tabellen? Een met woorden, en een die woord-ids koppelt aan scenes of comments.

Dan krijg je dus

tabel words: word_id, word_value
tabel index: index_word_id, index_type, index_link_id, index_word_occurence
Persoonlijk zou ik gaan voor 3 tabellen, nog eentje erbij met alle woorden omgedraaid zodat je ook like halb% kan queryen wat neerkomt op like %blah, maar dat is puur persoonlijk, in theorie kan je die ook in je words tabel kwijt.
Filter alle niet letters / cijfers eruit alszijnde word delimiters.
Bij je index_word_id zou ik ook nog even toevoegen het hoeveelste woord in een zin het is, zodat je kan zoeken naar "woord blah" ( blah moet het volgende woord zijn na woord ).
Bij je index_word_id zou ik nog even een relevantie cijfer aangeven, in een h1 is relevanter dan ergens achteraan.
Verder bedenk ik net dat ik gelijk alles naar lowercase kan brengen, en misschien zelfs de stam van de woorden kan achterhalen? (volgens mij is zoiets mogelijk in php?)
Stemming zou ik opzich als apart traject zien, als het NL teksten bevat is stemming sowieso niet standaard mogelijk in php ( engels misschien ), die engelstaligen willen nog niet echt overgaan op onze vervoegingen van woorden...
Case insensitive zou ik sowieso aanzetten als het echt niet boeiend is. Is het wel boeiend dan zou ik wel case insensitive zoeken, maar de case sensitive een hogere waarde geven...

Oftewel, opzich is het allemaal niet zo moeilijk te bedenken, maar bouw het maar als totaalpakket...
Daarnaast is LIKE volgens mij ook stukken langzamer dan fulltext.
Misschien langzamer, maar je kan dan wel op tekstgedeeltes zoeken, dat voordeel weegt imho zwaar op tegen de snelheid ( en snelheid is volgens mij geen enkel verschil zolang het alletwee in memory tabellen zijn geworden, moet je alleen voldoende memory hebben )

[ Voor 7% gewijzigd door Gomez12 op 16-10-2008 21:00 ]


  • Voutloos
  • Registratie: Januari 2002
  • Niet online
(jarig!)
Sebazzz schreef op donderdag 16 oktober 2008 @ 20:52:
Daarnaast is LIKE volgens mij ook stukken langzamer dan fulltext. ;)
Dat is ook generaliseren, maar dit zal wel meestal kloppen. :P

Overigens weet ik er ook nog wel eentje: Daarnaast zijn zowel like als mysql fulltext bij een beetje tabel idioot veel langzamer dan Sphinx. :Y)
Gomez12 schreef op donderdag 16 oktober 2008 @ 20:56:
Je like %blah% verhindert alleen elke index.
Nee, hoor, dat is juist het nadeel van (mysql) fulltext. Bij fulltext worden andere indexen juist genegeerd. Maar een EenKolom LIKE '%e%' AND PrimairyKeyKolom = 1 is gegarandeerd snel hoor. ;)

[ Voor 57% gewijzigd door Voutloos op 16-10-2008 21:01 ]

{signature}


  • Gomez12
  • Registratie: Maart 2001
  • Laatst online: 17-10-2023
Voutloos schreef op donderdag 16 oktober 2008 @ 20:58:
[...]
Nee, hoor, dat is juist het nadeel van (mysql) fulltext. Bij fulltext worden andere indexen juist genegeerd. Maar een EenKolom LIKE '%e%' AND PrimairyKeyKolom = 1 is gegarandeerd snel hoor. ;)
Enige hint naar documentatie hieromtrent? Want afaik gebruikt like %e% geen indexen over die kolom, over andere kolommen en where's kunnen wel indexen gebruikt worden. Maar die like %e% is afaik toch echt een (temporary) table scan over die ene kolom.

Dus als ik 1 tabel id / keyword heb met maar 2 kolommen lijdt afaik een like %e% altijd tot een complete table scan, wat je niet altijd wilt hebben als je meer dan 2 miljoen keywords hebt...

[ Voor 15% gewijzigd door Gomez12 op 16-10-2008 21:11 ]


  • Voutloos
  • Registratie: Januari 2002
  • Niet online
(jarig!)
In dat voorbeeld staan EenKolom en PrimairyKeyKolom in dezelfde tabel he, en dan is het een triviaal voorbeeldje beste index pakken. ;)

{signature}


  • Gomez12
  • Registratie: Maart 2001
  • Laatst online: 17-10-2023
Voutloos schreef op donderdag 16 oktober 2008 @ 21:15:
In dat voorbeeld staan EenKolom en PrimairyKeyKolom in dezelfde tabel he, en dan is het een triviaal voorbeeldje beste index pakken. ;)
Maar afaik pakt een like %e% geen index omdat een waarde als "gggggggggggggeg" gewoon in geen enkele standaard index voorkomt met een "e" erin.

Uit mijn hoofd gezegd worden indexen ltr opgebouwd, kan je ze met een switch rtl laten opbouwen. Maar is er geen index die vanaf elke positie afzonderlijk indexeert. Wat wel nodig is voor een %e% ( vb. geg dient ook een ltr of rtl-index vanaf de 2e positie te hebben, maar ggegg dient een index vanaf de 3e positie te hebben ).

Waardoor er geen beste index is. Maar als jij een link naar documentatie hebt die zegt dat %e% wel te indexeren is ben ik zeer nieuwsgierig, in principe zou dat in mijn huidige project bijna een db-change veroorzaken omdat dat gewoon heel veel prog / optimaliseerwerk zou schelen...

[ Voor 16% gewijzigd door Gomez12 op 16-10-2008 21:28 ]


  • link0007
  • Registratie: Augustus 2006
  • Niet online
Gomez12 schreef op donderdag 16 oktober 2008 @ 20:56:
[...]

even ter info, and's / or's zijn niet traag zolang je de indexen maar goed hebt staan. Je like %blah% verhindert alleen elke index.
Sowieso moet je je afvragen of het mogelijk is om dit om te schrijven naar een like blah%


[...]

Persoonlijk zou ik gaan voor 3 tabellen, nog eentje erbij met alle woorden omgedraaid zodat je ook like halb% kan queryen wat neerkomt op like %blah, maar dat is puur persoonlijk, in theorie kan je die ook in je words tabel kwijt.
Kan je misschien uitleggen waarom zoiets handig is? Ik zie het nut nu even niet.
Filter alle niet letters / cijfers eruit alszijnde word delimiters.
Bij je index_word_id zou ik ook nog even toevoegen het hoeveelste woord in een zin het is, zodat je kan zoeken naar "woord blah" ( blah moet het volgende woord zijn na woord ).
Goed punt, ik was helemaal vergeten dat je anders onmogelijk "woord blah" kon zoeken!
Bij je index_word_id zou ik nog even een relevantie cijfer aangeven, in een h1 is relevanter dan ergens achteraan.
De informatie die geindext zal worden zijn beschrijvingen van scenes en comments. Ik neem aan dat zo'n relevantiesysteem dan minder van belang is?
[...]

Stemming zou ik opzich als apart traject zien, als het NL teksten bevat is stemming sowieso niet standaard mogelijk in php ( engels misschien ), die engelstaligen willen nog niet echt overgaan op onze vervoegingen van woorden...
De voertaal is Engels. Dus stemming moet in de meeste gevallen goed gaan. Doet stemming iets gevaarlijks bij niet-engelse woorden? (iets waardoor ik het links moet laten liggen)
Case insensitive zou ik sowieso aanzetten als het echt niet boeiend is. Is het wel boeiend dan zou ik wel case insensitive zoeken, maar de case sensitive een hogere waarde geven...
omzetten naar lowercase it is :)
Oftewel, opzich is het allemaal niet zo moeilijk te bedenken, maar bouw het maar als totaalpakket..
En dat is nu precies waarom ik hier even om hulp vraag :)

IF IF = THEN THEN THEN = ELSE ELSE ELSE = IF;


  • Gomez12
  • Registratie: Maart 2001
  • Laatst online: 17-10-2023
link0007 schreef op donderdag 16 oktober 2008 @ 22:23:
[...]
Kan je misschien uitleggen waarom zoiets handig is? Ik zie het nut nu even niet.
Zoeken naar 007 vindt met een "like 007%" geen link0007 maar is wel snel. Een "like %007" geeft wel het gewenste resultaat maar gebruikt afaik standaard geen index dus traag.
Je omgekeerde woordentabel bevat geen "link0007" maar "7000knil", hierin zoeken naar "like 700%" gaat gewoon weer via een ltr index en dus snel, link0007 en 7000knil verwijzen in je koppeltabel wel naar dezelfde artikelen / comments dus hiermee heb je simpel een %007 snel gemaakt...
[...]
De informatie die geindext zal worden zijn beschrijvingen van scenes en comments. Ik neem aan dat zo'n relevantiesysteem dan minder van belang is?
Mag je zelf bepalen... Opzich vind ik waarschijnlijk als ik naar link0007 zoek de comments door hemzelf gemaakt relevanter dan de comments waarin zijn naam genoemd is. Net zoals wanneer ik op star wars zoek dat ik waarschijnlijk de scenes relevanter vind dan een paar comments waarin gezegd wordt dat dit wel lijkt op star wars.
[...]
De voertaal is Engels. Dus stemming moet in de meeste gevallen goed gaan. Doet stemming iets gevaarlijks bij niet-engelse woorden? (iets waardoor ik het links moet laten liggen)
Gevaarlijk hangt ervanaf of je alleen de gestemde woorden opslaat of ook het origineel.
Qua mismatches zit je wel hoger als je gaat stemmen volgens engelse regels op nl teksten, omdat de regels gewoon anders zijn...

Btw bedenk je wel dat relevantie / woord-locatie etc je query's wel snel complexer gaan maken. Mits je de juiste indexen gebruikt is het snel / goed, maar verkeerde indexen kunnen zo ongeveer het hele systeem in elkaar laten zakken door de complexiteit die gaat ontstaan...

  • RobIII
  • Registratie: December 2001
  • Niet online

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

(overleden)
Een "like %foo%" kan geen index gebruiken; denk nou eens logisch na: zoek voor mij eens even iedereen uit het telefoonboek met %foo% in de naam. Of zoek je liever naar foo% ? Ik weet wel welke van de 2 ik liever zou doen. En met een reverse kolommetje erbij kun je het optimaliseren voor het %foo geval; denk maar even door daarover, hoewel Gomez het hierboven al uitlegt ;) Maar %foo% zal (AFAIK) altijd een full table scan moeten doen.

En stemming zit gewoon in fulltext...

[ Voor 9% gewijzigd door RobIII op 16-10-2008 23:35 ]

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Je eigen tweaker.me redirect

Over mij


  • link0007
  • Registratie: Augustus 2006
  • Niet online
RobIII schreef op donderdag 16 oktober 2008 @ 23:34:
Een "like %foo%" kan geen index gebruiken; denk nou eens logisch na: zoek voor mij eens even iedereen uit het telefoonboek met %foo% in de naam. Of zoek je liever naar foo% ? Ik weet wel welke van de 2 ik liever zou doen. En met een reverse kolommetje erbij kun je het optimaliseren voor het %foo geval; denk maar even door daarover, hoewel Gomez het hierboven al uitlegt ;) Maar %foo% zal (AFAIK) altijd een full table scan moeten doen.

En stemming zit gewoon in fulltext...
Goed, dat wilde ik dus weten, bedankt allebei! :)

reverse tabel erbij is dus wel noodzakelijk ja.

Goed ik denk dat ik er nu genoeg van begrijp om een implementatie te schrijven! Het is nu een beetje laat dus morgen zal ik alles zo ver krijgen (zowel backend zoekfuncties veranderen als de database klaarzetten natuurlijk).

Nog een ding: wat moet ik doen bij dubbel voorkomende woorden? Als ik gewoon ieder bericht splits op spaties en dan woord voor woord in de database stop, dan krijg ik natuurlijk dubbele woorden. Moet ik daar iets tegen doen, en zo ja: Wat is de snelste manier? (er is natuurlijk wel een kans dat iemand een text invoert van 8000 tekens lang, dus de snelheid moet ook wel goed zitten bij het invoeren O-) )

IF IF = THEN THEN THEN = ELSE ELSE ELSE = IF;


  • RobIII
  • Registratie: December 2001
  • Niet online

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

(overleden)
link0007 schreef op vrijdag 17 oktober 2008 @ 00:33:
[...]
Nog een ding: wat moet ik doen bij dubbel voorkomende woorden?
Ik zal je probleem wel verkeerd begrijpen maar ik zie niet waarom je geen fulltext search gebruikt. Moeilijk gaan zitten doen met allerlei tabellen, reverse fields enz. als alles wat je wil door fulltext ondersteund wordt. Kwestie van aanzetten als dat nog niet zo is, queries aanpassen en gaan met die banaan.
En anders kun je nog eens kijken naar Lucene, Xapian etc. i.p.v. het wiel opnieuw en vierkant gaan zitten uitvinden
link0007 schreef op vrijdag 17 oktober 2008 @ 00:33:
(er is natuurlijk wel een kans dat iemand een text invoert van 8000 tekens lang, dus de snelheid moet ook wel goed zitten bij het invoeren O-) )
Even out of curiosity*: die 8000; waar komt die vandaan? Je hebt toch geen varchars van 8000 tekens he?
* Omdat ~8000 zo'n 'magic number' is...

[ Voor 11% gewijzigd door RobIII op 17-10-2008 01:20 ]

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Je eigen tweaker.me redirect

Over mij


  • FragFrog
  • Registratie: September 2001
  • Laatst online: 10:49
RobIII schreef op vrijdag 17 oktober 2008 @ 01:16:
Ik zal je probleem wel verkeerd begrijpen maar ik zie niet waarom je geen fulltext search gebruikt. Moeilijk gaan zitten doen met allerlei tabellen, reverse fields enz. als alles wat je wil door fulltext ondersteund wordt. Kwestie van aanzetten als dat nog niet zo is, queries aanpassen en gaan met die banaan.
Seconded. Bovendien heeft MySQL fulltext search bijvoorbeeld twee geniale opties:

1. Query expansion. Stel je hebt twee woorden in artikel A: Appel en Fruit. Er komen twee woorden voor in artikel B, Peer en Fruit. Zoek je op peer, zal'ie ook een link naar artikel A vinden (met lagere relevantie uiteraard).
2. IN NATURAL LANGUAGE MODE: negeert kleine en veel voorkomende woorden. Als al je artikelen het woordje 'en' bevatten wil je ze (doorgaans) niet allemaal terug krijgen, dit wordt automatisch gedetecteerd en de resultaten die alleen op 'en' matchen worden eruit gefiltert.

Hij's bovendien ook nog eens verdraaid snel: ooit eens een grote site gebouwd die draaide op onder andere 3 dedicated database servers, om de een of andere reden was die soms compleet onbereikbaar omdat er queries in hingen van meer dan 10 minuten. Bleek een collega een search gebouwd te hebben op jou manier, like %woord%, op een kleine 200k records. Vervangen door een fulltext search en ineens veranderde die 10+ minuten search in een ~0.02 seconden search :Y)

Let wel, ik beweer niet dat een fulltext search beter of zelfs even goed is als een volledig custom made script wat precies doet wat jij wilt. Als ik je echter af hoor vragen wat je moet doen met dubbele woorden (artikel krijgt een hogere score voor dat specifieke woord ;)) denk ik dat't uiteindelijk niet zo gek veel uit gaat maken, handmatig text-searchqueries bouwen is een stuk gecompliceerder en bijna altijd langzamer.

[ Voor 11% gewijzigd door FragFrog op 17-10-2008 02:08 ]

[ Site ] [ twitch ] [ jijbuis ]

Pagina: 1