Wenn man eine Anfrage auf Name und Nachname oder auf Strasse und Ort hat und dann den entsprechenden Datensatz aus einer Datenbank haben will muss man mit einem ‚%parameter%‘ Pattern arbeiten, um Fehler oder teilweise Eingaben abzudecken.
Das ist viel zu teuer.
Wie kann ich die Indices legen?
Eine Suche auf Integern wäre auch günstiger -> vielleicht ASCII-Zahlenwerte??
Wenn man Snapshots mit eindeutigen IDs benutzt, quadriert sich die Datenmenge - wird das am Ende schneller oder langsamer???
Kann man etwas erreichen, wenn man on-the-fly views erzeugt, die mit (für parameter) ‚p%‘ und GROUP BY erzeugt wurden?
Welche Möglichkeiten und Ideen gibt es noch zu diesem Thema?
Hallo Raimund!
Wenn du ein Wort innerhalb eines Strings sicher und schnell finden willst, dann gibt’s (leider) nur eine Lösung: Volltextindizierung.
Dabei wird jeder String in einzelne Wörter zerlegt, die Wörter in einer Liste aufgesammelt und zu jedem Wort vermerkt, in welchem Datensatz dieses Wort vorkommt (nennt man invertierte Wortliste). Jetzt kann man schnell ermitteln, in welchen Datensätzen z.B. das Wort „Müller“ vorkommt.
Wenn man noch eine Schreibfehlertoleranz einbauen will, dann gibt sucht man nach allen Wörtern, die „ähnlich“ wie „Müller“ sind: „Muller“, „Mueller“, „Müler“, … Hier gibt es ausgefuchste Verfahren, die z.B. auch typische Schreibfehler bzw. OCR-Lesefehler besonders berücksichtigen. Bei der Behandlung von Sonderzeichen (deutsche Umlaute, ß, französiche accents, etc.) wird ähnlich vorgegangen.
Wenn man eine phonetische Suche braucht, dann braucht man einen Algorithmus, der Wörter nach phonetischen Kriterien klassifiziert. Für Englisch gibt es ein sehr brauchbares und einfaches Verfahren, für Deutsch sieht die Sache etwas schwieriger aus.
Wenn du eine Suche nach Teilwörtern brauchst, dann müssen nicht nur Wörter, sondern auch Teilwörter (bon links trunktiert) indiziert werden: „Müller“, „üller“, „ller“, … Dann wird auch eine Suche nach „üll%“ blitzschnell beantwortet. Genug der Theorie!
Den einfachsten Fall der invertierten Wortliste kann man mit Trigger, Views, etc. noch selbst implementieren. Bei den komplizierteren Dingen steckt aber viel Arbeit dahinter und der Teufel im Detail.
Inzwischen bieten aber alle RDBMS-Hersteller auch Volltexterweiterungen an. Alle diese Systeme arbeiten mit den oben vorgestellten Prinzipien. Liste ohne Gewähr auf Vollständigkeit und Korrektheit. Ändert sich ständig…
- Oracle8i mit interMedia Text
- MS SQL-Server mit Verity Search Engine
- Informix auch mit Verity Search Engine
- IBM DB/2 mit IBM-eigenen Produkt
Bei Oracle funktioniert das z.B. so, dass du über ein Attribut einen Volltextindex legst, Beispiel:
create table test (
test\_id number constraint pk\_test primary key,
text varchar2 (2000)
)
create index dtx\_test\_text on test (text)
indextype is ctxsys.context parameters ('lexer my\_lexer');
Dann kannst du in einer Query den Operator contains verwenden, der die Volltextrecherche realisiert:
select \* from test
where contains (text, 'Müller') \> 0
Dabei gibt’s Funktionalität bis zum umfallen: bool’sche Bedingungen (‚Müller & Meier‘), Nachbarschaftsbeziehungen (NEAR), tippfehlertolerante Suche, phonetische Suche, Wortstammsuche (besonders im Deutschen interessant: Suche nach ‚Schule‘ liefert auch ‚Handelsschulen‘ als Treffer), Suche nach Teilwörtern,…
hoffe, dass dir das weiterhilft,
ciao,
Bernhard
Da hätte ich aber mehr erwartet.
Die Volltext suche von den meisten namhaften Herstellern
ist viel zu langsam.
Da muss es noch andere Lösungen geben…
Ahhhh - da geht’s ja um eine richtig anspruchsvolle Anwendung - spannend! *freu* *händereib*
Zum besseren Verständnis brauche ich ein paar Infos:
- Anzahl Datensätze
- Datenmenge Text insgesamt
- ein paar Infos zur Verteilung und Selektivität der Textdaten
- Transaktionlast
- Komplexität der Recherchen (auch relationale Selektionskriterien mit dabei?)
- geforderte Rechercheperformance (Anzahl parallel durchgeführter Queries, geforderte Antwortzeit)
Wenn es darum geht, Performance 'rauszuholen, gibt’s folgende Aspekte:
- Generell: Je aufwendiger die Indizierungsstrategie, um so besser die Rechercheperformance, um so schlechter dafür DML-statements, außerdem kostet jeder Index Speicherplatz
- Applikationssemantik ausnutzen, Volltextindex (oder was auch immer) darauf ausrichten (tradeoff Performance - Flexibilität)
- Applikationssemantik ausnutzen, Treffermengen bzw. Teilmengen im voraus berechnen (Stichwort „materialized views“) (tradeoff Performance Recherche - Performance DML / Datenmenge)
- hohe parallele Recherchelast: Parallelisierung der Systemarchitektur
- spezifisch implementierte Ansätze sind typischerweise deutlich schneller als Standardlösungen (bei den Implementierungen die ich kenne war das Faktor 2-10), sind dafür teuer, dauern lange. Bis man fertig ist, ist schon die nächste Rechnergeneration in Sicht, von der RDBMS gibt’s schon wieder zwei neue Versionen…
Aus deinem ersten Posting:
Eine Suche auf Integern wäre auch günstiger -> vielleicht
ASCII-Zahlenwerte??
Wenn man Snapshots mit eindeutigen IDs benutzt, quadriert sich
die Datenmenge - wird das am Ende schneller oder langsamer???
Kann man etwas erreichen, wenn man on-the-fly views erzeugt,
die mit (für parameter) ‚p%‘ und GROUP BY erzeugt wurden?
Wenn ich dich richtig verstanden habe, dann denkst du an ein hashing-Verfahren, das aus den Strings eine Integer-Wert berechnet? Das mit den Snapshots und GROUP BY habe ich ehrlichgesagt noch nicht richtig verstanden, kannst du sie nochmal konkret erläutern? Danke!
happy hacking!
Bernhard
2 „Gefällt mir“
Ahhhh - da geht’s ja um eine richtig anspruchsvolle Anwendung
- spannend! *freu* *händereib*
Zum besseren Verständnis brauche ich ein paar Infos:
- Anzahl Datensätze
Europaweite Address-DB mit mehreren Mio Einträgen
- Datenmenge Text insgesamt
(Name, Vorname, Strasse, Ort, Telnr) * Anzahl der Datensätze
- ein paar Infos zur Verteilung und Selektivität der Textdaten
?
- Transaktionlast
Soll eine Application fürs Internet mit werden (ähnlich einem Tel-Buch)
- Komplexität der Recherchen (auch relationale
Selektionskriterien mit dabei?)
Eigentlich keine Joins -> zu teuer
es sollen Suchen nach jedem Feld ermöglicht werden
realistisch ist aber eher ein mindest Kriterium auf zwei der Felder
- geforderte Rechercheperformance (Anzahl parallel
durchgeführter Queries, geforderte Antwortzeit)
Anzahl der Queries geht gegen unendlich
Antwortzeit sollte gegen null gehen (wobei die
Einheiten pro Zeit der Schwerpunkt sein müssen, da User
nicht ewig warten)
Wenn es darum geht, Performance 'rauszuholen, gibt’s folgende
Aspekte:
- Generell: Je aufwendiger die Indizierungsstrategie, um so
besser die Rechercheperformance, um so schlechter dafür
DML-statements, außerdem kostet jeder Index Speicherplatz
Indices sollen auf jeden fall da sein, der Speicherlpatz ist
sekundär
- Applikationssemantik ausnutzen, Volltextindex (oder was auch
immer) darauf ausrichten (tradeoff Performance - Flexibilität)- Applikationssemantik ausnutzen, Treffermengen bzw.
Teilmengen im voraus berechnen (Stichwort „materialized
views“) (tradeoff Performance Recherche - Performance DML /
Datenmenge)
kommt man mit snapshots in diese Richtung?
Wieviel bringen Referenz Tabellen, in denen zB
Vorname1 hat NameN
Vorname1 hat NameM
Vorname1 hat NameO
sprich jedes Feld1 hat eine eindeutige ID, die
mit den Feld2-IDs verknüpft wird, die bei unterschiedlichem
wert in Feld2 den gleichen wert in Feld1 hat.
- hohe parallele Recherchelast: Parallelisierung der
Systemarchitektur
Loadballancer sind eingerichtet, die Server sind dedicated ??
- spezifisch implementierte Ansätze sind typischerweise
deutlich schneller als Standardlösungen (bei den
Implementierungen die ich kenne war das Faktor 2-10), sind
dafür teuer, dauern lange. Bis man fertig ist, ist schon die
nächste Rechnergeneration in Sicht, von der RDBMS gibt’s schon
wieder zwei neue Versionen…
Oracle 8.1.7
die Rechner sind auch neu, und wir haben ein paar Leute, die sich damit beschäftigen
Was meinst du mit spezifisch Standart
Aus deinem ersten Posting:
Eine Suche auf Integern wäre auch günstiger -> vielleicht
ASCII-Zahlenwerte??
Wenn man Snapshots mit eindeutigen IDs benutzt, quadriert sich
die Datenmenge - wird das am Ende schneller oder langsamer???
Kann man etwas erreichen, wenn man on-the-fly views erzeugt,
die mit (für parameter) ‚p%‘ und GROUP BY erzeugt wurden?Wenn ich dich richtig verstanden habe, dann denkst du an ein
hashing-Verfahren, das aus den Strings eine Integer-Wert
berechnet? Das mit den Snapshots und GROUP BY habe ich
ehrlichgesagt noch nicht richtig verstanden, kannst du sie
nochmal konkret erläutern? Danke!happy hacking!
Bernhard
Also ich habe überlegt, daß man die Wörter entweder komplett oder in dreier Gruppen zerhackt und in Zahlenwerte umwandelt
(sprich die entsprechenden Ascii-Codes). Das würde bedeuten,
daß man eine Tabelle mit einer Spalte pro Buchtstabe bekommt…
Zu den Views (wahrscheinlich sind da auch Snapshots oder meterialized Views besser)
wenn man weiss, das die Addresse in Deutschlad ist, sucht man nicht mehr in der Haupttabelle tabelle sondern in einem Snapshot, der nur deutsche Addressen beinhaltet. Das Gleiche zB für Postlaitzahlen …
Genauso könnte ich mir vorstellen, daß man alle Nachnamen, die mit „M“ anfangen zusammenfasst und ihnen eindeutige IDs erteilt.
Sodaß bei einem Maier in der Tabelle (mit Nachenamen und ID) gesucht wird und der komplette Datensatz dann per ID aufgerufen wird.
Raimund
(Freut mich, daß du dich damit beschäftigen willst!)
Lösungvorschläge
Hi Raimund!
Jo, inzwischen bin ich wieder nüchtern (ein Frohes Neues noch…) und möchte meine Vorschläge mal zusammenfassen:
Annahmen
- Relation Adresse: Vorname, Name, Strasse, Ort, Telnr
- ca. 50-100 Byte pro Datensatz, Annahme 10 Mio. Tupel, 0.5 - 1 GB Daten netto
- Restriktion soll möglich sein bzgl. jedem Feld bzw. jeder Feldkombination
- Recherche-Performance hat Priorität, DML-Performance (insert, update, delete) und Speicherplatz sekundär
Ansatz "combined indexes"
Theorie: für jede Attribut-Permutation wird ein combined index angelegt. In der Praxis machen eigentlich nur Indizes mit 3 (oder max. 4) Attributen Sinn. So ein Index sieht z.B. so aus:
CREATE INDEX x01 ON Adresse (Vorname, Name, Strasse);
Wenn jemand Vorname, Name und Strasse angegeben hat, dann wird die entsprechende volle Adresse über den Index blitzschnell gefunden. Bei einer Relation mit 5 Attribute und Indizes mit 3 Attributen gibt es allerdings insgesamt 3! * (3 aus 5) = 60 Permutationen. Also
CREATE INDEX x01 ON Adresse (Vorname, Name, Strasse);
CREATE INDEX x02 ON Adresse (Vorname, Name, Ort);
CREATE INDEX x03 ON Adresse (Vorname, Name, Telnr);
CREATE INDEX x04 ON Adresse (Vorname, Strasse, Name);
CREATE INDEX x05 ON Adresse (Vorname, Strasse, Ort);
CREATE INDEX x06 ON Adresse (Vorname, Strasse, Telnr);
...
CREATE INDEX xyz ON Adresse (Strasse, Telnr, Vorname);
...
Damit kann man dann alle Restriktionen mit bis zu drei angegeben Feldern *ausschließlich* über den entsprechenden Index auswerten. Die von dir vorgeschlagenen Referenz-Tabellen werden nicht benötigt, sie stecken implizit in diesen Indizes: „Welche Namen gibt es zum Vorname Bernhard“ oder „In welchen Ort gibt es einen Bernhard Schaefers“ kann z.B. über x01 ausgewertet werden, und zwar ausschließlich über den Index! Ein Zugriff auf die Relation Adresse ist nicht notwendig. Es ist aber Overkill, alle 60 Permutationen tatsächlich anzulegen, die unwichtigen bitte weglassen, man kommt wohl mit 10 aus. Hier kommt die Semnatik wieder ins Spiel: Ist es wirklich notwendig, zu wissen „Welche Vornamen gibt es in der Bahnhofstraße, deren TelNr mit 4711 beginnt?“ Dafür ist Index xyz da; braucht man diesen Recherchezugang nicht, kann auch den Index weglassen.
"combined indexes" mit Wortzerlegung und Wortnormalisierung
Zwei Probleme: Performante Recherche nach einzelnen Wörtern mehreren Vornamen, Namen, etc. und die Behandlung von Groß-/Kleinschreibung, Sonderzeichen (Umlauten, accents, …)
Lösung: Vorname, Namen, etc. in Einzelwörter zerlegen, diese normalisieren un alle Permutationen in einer Relation Daten (mit Verweis auf primary key Adresse) ablegen. Dann „combined indexes“ auf Daten anlegen. Beispiel:
Adresse: 4711, „Karl-Heinz“, „Günther-Hergé“, … wird zu
Daten: 4711, KARL, GUENTHER
Daten: 4711, KARL, HERGE
Daten: 4711, HEINZ, GUENTHER
Daten: 4711, HEINZ, HERGE
Volltextindizierung
Wenn mehr Funktionalität erforderlich ist (Rechtstrunkierung, Tippfehlertoleranz, Ranking), dann hilft nur noch Volltextindizierung. Da gibt’s Sachen, die auch funktionieren sollten. Oracle interMedia sollte (halbwegs brauchbare) Antwortzeiten zusammenbringen (im Sekundenbereich bei gut getunter Oracle). Dann ist es gut wenn der Volltextindex nicht zu groß wird. Wenn z.B. der Anwender IMMER zuerst das Land auswählen muss, dann haben wir das Problem schon wieder reduziert.
DB-tuning
DB-tuning ausnutzen. Ist bei Oracle eine beliebig eklige Sache, bringt aber was (Faktor 2-5). Man muss aber wissen, an welcher Stelle anzusetzen ist, sonst ist man im Wald. Also: Entweder viel Zeit und Lust, um sich in die Materie einzuarbeiten oder Oracle-Profi engagieren.
non-standard Implementierung, richtig schnell
Eigenes Programm schreiben, das die Daten komplett in den RAM schaufelt (AVL-Baum oder so was…, 1 GB RAM?? müsste man mal nachrechnen), optimiert auf die eigene Volltextrecherche-Funktionalität. Ein AVL-Baum hat bei diesen Datenmengen eine Höhe von ca. 20-30. D.h. mit 20-30 mal im RAM positionieren bist du am Ziel. Performance-Problem ist die Schnittmengenbildung von Treffermengen, hier ggf. Code-Optimierung. Das ist zwar viel Arbeit, das Ergebnis einer Recherche ist aber unmittelbar da!
noch ein paar Hinweise:
- Zerlegen von Strings in Buchstaben und deren ASCII-Werte bringt eigentlich nichts, denn rechnerintern sind Strings eh schon so abgelegt.
- Snapshots oder materialized views machen nur Sinn, wenn joins, Aggregatsfunktionen, group by, etc. vorkommen: Wenn du z.B. wissen willst: „WIEVIELE Bernhard Schaefers gibt es in Deutschland?“, dann macht sowas Sinn. In allen anderen Fällen genügen combined indexes, da steckt bereits alle Information drin.
- Eigene indexartige Strukturen mit Fremdschlüsselbeziehnungen zur Originalrelation (etwa Referenztabellen) sind nicht performant. Der Zugriff über eine eindeutige ID ist nur die zweitbeste Wahl. Die Datenbanksysteme verwenden bei den eigenen Indexstrukturen eindeutige !interne! IDs (bei Oracle: ROWID), damit ist der schnellste Zugriff auf einen Datensatz gegeben. Also besser entsprechend kombinierten Index verwenden.
So, ich hoffe, dass ich dich nicht zugetextet habe, und dass dir meine Ideen weiterhelfen…
Und: Wenn das Teil fertig ist, dann sag mir bitte, wie du es gemacht hast!
Wenn noch Fragen sind… melden!
ciao,
Bernhard
2 „Gefällt mir“
Danke, Bernhard!
Auch ein frohes neues Jahr!
Ich werde sehen, wie wird das alles implementieren und anwenden.
Auf jeden fall wirst du von mir hören, wenn wir damit fertig sind.
Vielen Dank für die Mühe, die du dir gemacht hast!
Raimund