Datenstruktur als DB Lösung

Hallo,

ich habe in einer Tabelle eine Menge von Dokumenten gespeichert, die
eine ID (INTEGER) und ein textfeld (MEDIUMTEXT) haben.

Ich möchte nun jeweils alle Dokumente ermitteln, die bestimmte
Begriffe aus dem Textfeld enthalten.

Was für mich eigentlich am besten wäre, ist eine HashMap auf die ich
über ein Wort aus dem textfeld sehr schnell zugreifen kann und ich
dann eine Liste von Dokument-Nummern erhalte.

Bei mehreren Suchbegriffen müssen dann noch Schnittmengen zwischen
allen Dokument-Nummern, die über die HashMap ermittelt wurden,
durchgeführt werden.

Ich wollte nun eine solche Struktur in einer Datenbank nachbilden,
scheitere aber an der Anfrage-Geschwindigkeit.

Ich habe es mit einem FULLTEXT INDEX versucht, das ist aber zu
langsam. Dann habe ich es noch mit einer Tabelle versucht, die nach 1
NF normalisiert ist und dann folgende form hat:

Schlüssel Doc#
-----------------------------------------------------
key_1 5
key_1 10
...
key_2 7
key_2 4



Die Frage ist nun, kann ich irgendwie eine schnelle Lösung für mein
Problem in einer Datenbank realisieren und wenn ja wie?

So etwas wie nested Tables wäre ganz nett, so dass ich von meinen
Schlüsseln direkt auf die Dokument-Nummern komme und zwischen diesen
die Schnittmengen bilden kann.

Gibt es hierfür eine schnell Lösung??

Re: Datenstruktur als DB Lösung

Hallo Mike,

> Was für mich eigentlich am besten wäre, ist eine HashMap auf die ich
> über ein Wort aus dem textfeld sehr schnell zugreifen kann und ich
> dann eine Liste von Dokument-Nummern erhalte.

SQL arbeitet mit Mengen von Datensätzen und nicht mit Mengen innerhalb
einzelner Felder.

> Die Frage ist nun, kann ich irgendwie eine schnelle Lösung für mein
> Problem in einer Datenbank realisieren und wenn ja wie?

Die Wortlisten umwandeln in Datensätze, Worte mit Dateien M:N verknüpfen.

> So etwas wie nested Tables wäre ganz nett, so dass ich von meinen
> Schlüsseln direkt auf die Dokument-Nummern komme und zwischen diesen
> die Schnittmengen bilden kann.

Das fällt dann nebenbei mit ab.


Siegfried
--
http://www.schmidt.ath.cx

Re: Datenstruktur als DB Lösung

On 17 Sep., 14:48, Siegfried Schmidt wrote:

> > Was für mich eigentlich am besten wäre, ist eine HashMap auf die ich
> > über ein Wort aus dem textfeld sehr schnell zugreifen kann und ich
> > dann eine Liste von Dokument-Nummern erhalte.
>
> SQL arbeitet mit Mengen von Datensätzen und nicht mit Mengen innerhalb
> einzelner Felder.

Klar ;-)


> > Die Frage ist nun, kann ich irgendwie eine schnelle Lösung für mein
> > Problem in einer Datenbank realisieren und wenn ja wie?
>
> Die Wortlisten umwandeln in Datensätze, Worte mit Dateien M:N verknüp=
fen.

Wollte ich schon machen, aber zu langsam.


> > So etwas wie nested Tables wäre ganz nett, so dass ich von meinen
> > Schlüsseln direkt auf die Dokument-Nummern komme und zwischen diesen
> > die Schnittmengen bilden kann.
>
> Das fällt dann nebenbei mit ab.

Also die einzige Variante, die mir spontan einfällt eingefallen ist
war vor meinem Posting:

wort1 =3D id_zu_wort_1 // in tabelle 1

id_zu_wort_1 =3D 5 // in tabelle 2
id_zu_wort_1 =3D 9
id_zu_wort_1 =3D 10
...
id_zu_wort_2 =3D 1
id_zu_wort_2 =3D 5
...

Das ist aber voll lahm bei etwa 20 Mio Einträgen!!


Gibts da nichts schnelleres??

Re: Datenstruktur als DB Lösung

Hallo Mike,

>> Die Wortlisten umwandeln in Datensätze, Worte mit Dateien M:N verknüp
> fen.
> Wollte ich schon machen, aber zu langsam.

Wieviel zu langsam? Wieviele Abfragen pro Sekunde brauchst du denn?

> Also die einzige Variante, die mir spontan einfällt eingefallen ist
> war vor meinem Posting:

Das ist doch M:N.

> Das ist aber voll lahm bei etwa 20 Mio Einträgen!!

Die Abfrage der Dateiliste für ein Wort (also Wortliste join MN-Liste join
Dateiliste) dauert hier bei 26Mio Datensätzen 30..50 ms. Beim Suchen der
Wörter per like etwa 500ms. Mit aktueller Hardware gings wahrscheinlich
etwas schneller. So ganz lahm finde ich das nicht.



Siegfried
--
http://www.schmidt.ath.cx

Re: Datenstruktur als DB Lösung

On 18 Sep., 04:32, Siegfried Schmidt wrote:

> >> Die Wortlisten umwandeln in Datensätze, Worte mit Dateien M:N verkn=
üp
> > fen.
> > Wollte ich schon machen, aber zu langsam.
>
> Wieviel zu langsam? Wieviele Abfragen pro Sekunde brauchst du denn?

Sorry, fehler von mir (s.u.)


> > Das ist aber voll lahm bei etwa 20 Mio Einträgen!!
>
> Die Abfrage der Dateiliste für ein Wort (also Wortliste join MN-Liste j=
oin
> Dateiliste) dauert hier bei 26Mio Datensätzen 30..50 ms. Beim Suchen der
> Wörter per like etwa 500ms. Mit aktueller Hardware gings wahrscheinlich
> etwas schneller. So ganz lahm finde ich das nicht.

Also zuerst mal, dachte ich, dass ein JOIN nicht besonders gut ist. So
weit ich weiss, ist der JOIN, die teuerste DB-Operation (hoffe, das
stimmt auch).
Ich habe noch etwas anderes versucht:

Ich wollte mir folgende Joins und verschiedene Tabellen, wie hier
angedeutet, sparen:

(wort, word_ID) -> (word_ID, doc#) -> (doc#, text)


So dachte ich, dass ich mir den Schritt zwischen (word, word_ID) ->
(word_ID, doc#) sparen kann. Dann habe ich eine Tabelle erstellt, die
gleich die Werte

(word, doc#)

enthält. So gibt es dann nur noch die Zuordnung (word, doc#) -> (doc#,
text).


Eine Abfrage wie diese benötigt, bei einem SELECT count(*) nicht lange
(zwischen 1-2 sec). Kann man das optimieren, in dem man, wie im ersten
Beispiel 3 Tabellen hat? Die erste Tabelle (word, word_ID) liegt im
Speicher (der Applikation, die die Anfrage ausführt), dann muss nur
noch eine Abfrage (word_ID, doc#) -> (doc#, text) durchgeführt werden.
Ist das schneller, als direkt eine Anfrage von (word, doc#)? Die Frage
lautet also, ist eine Anfrage nach einem Primary-Key in Textform
langsamer als eine Anfrage nach einem Primary-Key in Integer-Form?

Die nächste Sache, was ich noch getestet habe, war eine Volltextsuche
mit einem FULLTEXT INDEX über die Tabelle (doc#, text). Mit einer
Anfrage über MATCH AGAINST. Seltsamerweise kommen da mehr Zeilen bei
SELECT count(*) raus, als bei der JOIN-Variante und es ist etwas
langsamer (300-400ms). Die Frage ist aber, ob es nur langsamer ist,
weil mehr Zeilen herauskommen, oder ob es am Index selbst liegt? Weiss
das jemand?

Welches wäre für Euch die Bevorzugte Variante? Eine Query aus einem
Programm heraus dynamisch mit MATCH zu erzeugen ist etwas einfach und
weniger fehleranfällig für mich, als über einen JOIN. Ich würde den
JOIN nehmen, wenn ich eine Garantie hätte, dass schneller als die
Volltextsuche.

Re: Datenstruktur als DB Lösung

Hallo Mike,

> Also zuerst mal, dachte ich, dass ein JOIN nicht besonders gut ist. So
> weit ich weiss, ist der JOIN, die teuerste DB-Operation (hoffe, das
> stimmt auch).

Das lässt sich so pauschal nicht sagen. Joins gehören zum Kernrepertoire
eines DBMS, man kann davon ausgehen dass sie bestmöglichst laufen und
wegoptimieren nur in Spezialfällen lohnt (und dann auch nur wenn es
nachweislich am join liegt).

> So dachte ich, dass ich mir den Schritt zwischen (word, word_ID) ->
> (word_ID, doc#) sparen kann.

Ausgerechnet das spart kaum, u.a. weil du wahrscheinlich die Wortauswahl
stark einschränken wirst und gar nicht so viele Suchvorgänge über den
ersten Join anfallen. Oder suchst du auf einen Schlag nach 1000 Wörtern?

> Dann habe ich eine Tabelle erstellt, die
> gleich die Werte>
> (word, doc#)
>
> enthält. So gibt es dann nur noch die Zuordnung (word, doc#) -> (doc#,
> text).

Die eigentliche Schwerarbeit, d.h. Suche über den Textvergleich und
Aufbauen der Ergebnismenge werden durch das Weglassen des ersten Joins
nicht weniger - du optimiertst stattdessen das weg was am wenigsten
stört: ein paar wenige Suchvorgänge nach indizierten Zahlen.

> Eine Abfrage wie diese benötigt, bei einem SELECT count(*) nicht lange
> (zwischen 1-2 sec). Kann man das optimieren, in dem man, wie im ersten
> Beispiel 3 Tabellen hat?

Unwesentlich. Möglicherweise ist der count() der eigentliche Zeitfresser.

> Die erste Tabelle (word, word_ID) liegt im
> Speicher (der Applikation, die die Anfrage ausführt), dann muss nur
> noch eine Abfrage (word_ID, doc#) -> (doc#, text) durchgeführt werden.
> Ist das schneller, als direkt eine Anfrage von (word, doc#)? Die Frage
> lautet also, ist eine Anfrage nach einem Primary-Key in Textform
> langsamer als eine Anfrage nach einem Primary-Key in Integer-Form?

Integer-Keys sollten im Schnitt schneller sein, aber auch hier: das ist
bestenfalls ein Punkt für die letzten paar %.

> Die nächste Sache, was ich noch getestet habe, war eine Volltextsuche
> mit einem FULLTEXT INDEX über die Tabelle (doc#, text). Mit einer
> Anfrage über MATCH AGAINST. Seltsamerweise kommen da mehr Zeilen bei
> SELECT count(*) raus, als bei der JOIN-Variante und es ist etwas
> langsamer (300-400ms). Die Frage ist aber, ob es nur langsamer ist,
> weil mehr Zeilen herauskommen, oder ob es am Index selbst liegt? Weiss
> das jemand?

Das wird nur ein Programmersteller der Volltextsuche beantworten können.

> Welches wäre für Euch die Bevorzugte Variante? Eine Query aus einem
> Programm heraus dynamisch mit MATCH zu erzeugen ist etwas einfach und
> weniger fehleranfällig für mich, als über einen JOIN. Ich würde den
> JOIN nehmen, wenn ich eine Garantie hätte, dass schneller als die
> Volltextsuche.

Solche Garantien gibt es nicht, du kannst nur testen und dann
entscheiden. Und vor allem entscheiden ob du mit solchen minimalen
Verbesserungen überhaupt anfangen willst. Denn die Optimierung wird für
jeden Update wiederholt werden müssen, das Zeitverhalten der DB kann sich
jederzeit ändern oder ins Gegenteil verkehren.


Siegfried
--
http://www.schmidt.ath.cx

Re: Datenstruktur als DB Lösung

Mike Wesling schrieb:

> Die Frage ist nun, kann ich irgendwie eine schnelle Lösung für mein
> Problem in einer Datenbank realisieren und wenn ja wie?

So.


Ich habe dein Problem einmal Datenbank-Technisch gelöst. Mit der hier
schon beschriebenen M:N Tabelle.

So wurde die Suche bei www.idowa.de realisiert. Die M:N-Tabelle
funktioniert relativ gut für Abfragen die eine kleine Ergebnissmenge
zurück liefern.

Nach 2 Jahren Betrieb, und einer Documetanzahl von ca 1.5 Millionen
wurde das ganze dann aber arg langsam.

Vor allem aber bei kombinierten Abfragen mit Logischen Verknüpfungen
zwischen den Wörtern wie UND/ODER.

Deshalb hab ich dort das Nachfolgeprojekt myDbSearcher gestartet das die
Volltextsuche mit Lucene[1] macht. Den myDbSearcher gibt es hier:

[1]http://sourceforge.net/projects/mydbsearcher

btw, Eventuell will da mal jemand der hier mitliesst auch dran
rumschrauben? Das Projekt könnte einen 2nd-View brauchen :-)

Den schrecklich unübersichtlichen aber hoch optimierten Quellcode für
die Datenbanklösung hab ich mal hierher kopiert:

Der Indizierer: http://www.stowasser.tv/algo/SUCHE_wort_index.py
Die Suche : http://www.stowasser.tv/algo/SUCHE_suchen.py
Der Watchdog : http://www.stowasser.tv/algo/SUCHE_watchdog.py
Der ERD-DB : http://www.stowasser.tv/algo/suche.html
Leider nur der Vorentwurf. In der M:N Tabelle kam
dann später noch ne Bewertung und ein Zähler hinzu.
Die 'aktuellen' DB-Creates hab ich leider nicht mehr.

Vielleicht kannste Dir ja dort was ab gucken.
Der Indizierer lief als endloser Prozess auf einem Server. Methoden zu
Bereinigung und ein sind integriert. Der Watchdog wurde alle paar
Minuten von einem Cronjob aufgeführt, und guckt nach ob der Indizierer
auch tut. Und repariert bzw startet das Script neu.

Die Suche selber kombiniert über einen Kellerautomat die verknüpften
Begriffe.

*wink*
Harald

[1]http://lucene.apache.org/java/docs/

Re: Datenstruktur als DB Lösung

On 19 Sep., 03:12, Harald Stowasser wrote:

> Nach 2 Jahren Betrieb, und einer Documetanzahl von ca 1.5 Millionen
> wurde das ganze dann aber arg langsam.
>
> Vor allem aber bei kombinierten Abfragen mit Logischen Verknüpfungen
> zwischen den Wörtern wie UND/ODER.

Kann ich mir gut vorstellen.


> Deshalb hab ich dort das Nachfolgeprojekt myDbSearcher gestartet das die
> Volltextsuche mit Lucene[1] macht. Den myDbSearcher gibt es hier:
>
> [1]http://sourceforge.net/projects/mydbsearcher

Vielen, vielen Dank für die Bereitstellung! Ich werde mir das gleich
mal anschauen! Ist ja auch Java-Code von daher passt das sehr gut ;-)


Mal noch etwas anderes, hast Du schon mal mit dem MySQL FULLTEXT INDEX
gearbeitet?? Ich finde das im Grunde die einfachste Art aus einem Java-
Programm heraus dynamische Anfragen durchzuführen, vor allem, wenn man
Verknüpfungen mit UND/ODER machen muss. Viel einfacher als ein JOIN
dynamisch aufzubauen.

Was hälst Du davon?

Re: Datenstruktur als DB Lösung

Mike Wesling schrieb:

> Mal noch etwas anderes, hast Du schon mal mit dem MySQL FULLTEXT INDEX
> gearbeitet?? Ich finde das im Grunde die einfachste Art aus einem Java-
> Programm heraus dynamische Anfragen durchzuführen, vor allem, wenn man
> Verknüpfungen mit UND/ODER machen muss. Viel einfacher als ein JOIN
> dynamisch aufzubauen.
>
> Was hälst Du davon?

Der FULLTEXT INDEX ist toll. Leider kann er nicht mehrere Tabellen und
Datenbanken gleichzeitig durchsuchen, keine Teilworte, keine Unscharfe
suche, keine Gewichtung und mit InnoDb geht er auch nicht :-(

Für 'richtige' suchen in großen Datenmengen ist das also nix ;-)

Trotzdem hat er seine Berechtigung. Und wenn der Funktionsumfang genügt
währe es dumm ihn nicht zu benutzen.

--
Sie wollen mir was gutes tun? Amazon -Wunschliste:
http://www.amazon.de/gp/registry/2GU2EBXFCM49

Re: Datenstruktur als DB Lösung

Harald Stowasser schrieb:

> Der FULLTEXT INDEX ist toll. Leider kann er nicht mehrere Tabellen und
> Datenbanken gleichzeitig durchsuchen, keine Teilworte, keine Unscharfe
> suche, keine Gewichtung und mit InnoDb geht er auch nicht :-(

Ja, das stimmt. Für unscharfe Anfragen ist wahrscheinlich dann nur LIKE
eingeplant. Über die Gewichtung habe ich mal was überflogen, hab das
aber gerade nicht mehr zur Hand. Kann auch sein, dass sich das nur auf
die interne Gewichtung der Begriffe, wie sie vom System vorgenommen
wird, gehandelt hat.

Was ich für die MATCH(.,.) AGAINST(' +"A1 A2" +"B1 B2"' IN BOOLEAN)
option noch nicht gefunden habe, ist die Antwort auf die Frage, werden
hier Wort-Reihenfolgen berücksichtigt? Also ich habe zwei
Mehrwortbegriffe, nach denen ich suche. Wird hier die Reiheinfolge A
soll nach B auftreten berücksichtigt, oder kann B auch vor A auftreten?


> Für 'richtige' suchen in großen Datenmengen ist das also nix ;-)
>
> Trotzdem hat er seine Berechtigung. Und wenn der Funktionsumfang genügt
> währe es dumm ihn nicht zu benutzen.

Also ich brauche die Funktionalität nur in sehr rudimentärer Form.
Sprich: "gibt mir alle Dokumente zurück, die folgende Begriffe enthalten"


Trotzdem verhält es sich gelegentlich damit etwas "unperformant". Wenn
man mal misst, dass es teils bis zu 2sec dauern kann (1 Mio Dokumente),
ist man natürlich immer auf der Suche nach anderen Möglichkeiten ;-)

Re: Datenstruktur als DB Lösung

On Thu, 20 Sep 2007 04:52:22 +0200, Mike Wesling wrote:

> Harald Stowasser schrieb:
>
>> Der FULLTEXT INDEX ist toll. Leider kann er nicht mehrere Tabellen und
>> Datenbanken gleichzeitig durchsuchen, keine Teilworte, keine Unscharfe
>> suche, keine Gewichtung und mit InnoDb geht er auch nicht :-(
>
> Ja, das stimmt. Für unscharfe Anfragen ist wahrscheinlich dann nur LIKE
> eingeplant. Über die Gewichtung habe ich mal was überflogen, hab das
> aber gerade nicht mehr zur Hand. Kann auch sein, dass sich das nur auf
> die interne Gewichtung der Begriffe, wie sie vom System vorgenommen
> wird, gehandelt hat.
>
> Was ich für die MATCH(.,.) AGAINST(' +"A1 A2" +"B1 B2"' IN BOOLEAN)
> option noch nicht gefunden habe, ist die Antwort auf die Frage, werden
> hier Wort-Reihenfolgen berücksichtigt? Also ich habe zwei
> Mehrwortbegriffe, nach denen ich suche. Wird hier die Reiheinfolge A
> soll nach B auftreten berücksichtigt, oder kann B auch vor A auftreten?

Ja, die Reihenfolge wird beachtet. Mit "" definierst du Wortfolgen, die
exakt verglichen werden. Wortgruppen, bei denen die Reihenfolge egal ist,
werden mit () definiert.

Bei "" werden auch einige Limitierungen "abgesenkt", so muss nur ein Wort
in der Wortfolge die Mindestlänge haben und kein Stoppwort sein.

Beispiel (mit Mindestwortlänge = 4):
Das Pferd ist tot ==> Sucht effektiv nach "Pferd"

"Das Pferd ist tot" ==> Sucht zuerst nach "Pferd" und schränkt dann
weiter ein, auf die Zeilen die wirklich exakt "Das Pferd ist tot"
enthalten.

HTH
Björn

Re: Datenstruktur als DB Lösung

Harald Stowasser schrieb:
> Der ERD-DB : http://www.stowasser.tv/algo/suche.html
> Leider nur der Vorentwurf. In der M:N Tabelle kam
> dann später noch ne Bewertung und ein Zähler hinzu.
> Die 'aktuellen' DB-Creates hab ich leider nicht mehr.

Hab die creates noch von einem Ex-Kolegen bekommen:

mysql> show create table wort \G;
*************************** 1. row ***************************
Table: wort
Create Table: CREATE TABLE `wort` (
`wort_id` int(11) NOT NULL auto_increment,
`wort` char(64) collate latin1_general_ci NOT NULL default '',
`sound` char(48) collate latin1_general_ci NOT NULL default '',
`anzahl` int(11) NOT NULL default '0',
`gesucht` int(11) NOT NULL default '0',
PRIMARY KEY (`wort_id`),
UNIQUE KEY `UC_wort` (`wort`),
KEY `IDX_wort_1` (`sound`),
KEY `IDX_wort_2` (`anzahl`),
KEY `IDX_wort_3` (`gesucht`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1 COLLATE=latin1_general_ci

mysql> show create table zeilen_wort \G;
*************************** 1. row ***************************
Table: zeilen_wort
Create Table: CREATE TABLE `zeilen_wort` (
`FK_wort_id` int(11) NOT NULL default '0',
`FK_zeilen_id` int(11) NOT NULL default '0',
`bewertung` tinyint(4) NOT NULL default '0',
`anzahl` smallint(6) NOT NULL default '0',
PRIMARY KEY (`FK_wort_id`,`FK_zeilen_id`),
KEY `IDX_zeilen_wort_2` (`FK_zeilen_id`,`FK_wort_id`,`bewertung`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1 COLLATE=latin1_general_ci

mysql> show create table zeilen \G;
*************************** 1. row ***************************
Table: zeilen
Create Table: CREATE TABLE `zeilen` (
`zeilen_id` int(11) NOT NULL auto_increment,
`fk_id` int(11) NOT NULL default '0',
`FK_link_id` int(11) NOT NULL default '0',
`datum` date NOT NULL default '0000-00-00',
`gesamt_bewertung` decimal(3,2) NOT NULL default '0.00',
PRIMARY KEY (`zeilen_id`),
KEY `IDX_zeilen_1` (`FK_link_id`),
KEY `IDX_zeilen_2` (`fk_id`),
KEY `IDX_zeilen_3` (`datum`)
) ENGINE=MyISAM DEFAULT CHARSET=latin1 COLLATE=latin1_general_ci