Wie SELECT mit Suche nach String beschleunigen?

[mgutt]

Hallo,

ich ermittle statistisch, wie oft welches Wort auf meinen Seiten gesucht wird.

Jedes Wort erhält eine ID (autoincrement) und alle folgenden Abfragen beziehen sich dann aus Geschwindigkeitsgründen auf die ID (z.B. um die letzte Suchzeit oder die Anzahl der Suchversuche zu aktualisieren).

Doch leider ist bereits die erste Abfrage zu langsam (aktuell 1 Millionen Einträge):

SELECT id
FROM keywords
WHERE kw = '" . mysql_real_escape_string($q) . "'"

Sie ist an sich nicht langsam, doch dadurch, dass die Tabelle immer größer wird, merkt man einfach, dass die Ausführungszeit nachlässt.

Nun dachte ich an folgende Varianten, wo ich mir aber nicht sicher bin, welche den meisten Erfolg verspricht:

V1:
Ich lese den ersten Buchstaben von $q aus und wandle ihn in einen INT um:

$first = ord($q{0})

Und vergleiche diesen an Hand einer neuen Spalte:

SELECT id
FROM keywords
WHERE first = '" . $first . "'
AND kw = '" . mysql_real_escape_string($q) . "'"

V2:
Ich erstelle für jeden Buchstaben eine eigene Tabelle:

SELECT id
FROM keywords_" . $first . "
WHERE kw = '" . mysql_real_escape_string($q) . "'"

Bei späteren Abfragen benötige ich dann weiterhin $first, um die richtige Tabelle aktualisieren zu können.

Denkbarer Nachteil ist hier die Darstellung von "häufigsten" bzw. "letzten" Suchwörtern bei der statistischen Auswertung. Ich müsste dann erst alle Tabellen auslesen und die mit in eine FROM bringen oder ich müsste für jede Tabelle einzeln Statistiken machen und diese nachträglich zusammenfügen.

Gruß

[Crisps]

Zitat von mgutt

SELECT id
FROM keywords
WHERE kw = '" . mysql_real_escape_string($q) . "'"

Hat das kw Feld einen Index?

Und was zeigt die Ausgabe der folgenden Query an:

EXPLAIN SELECT id
          FROM keywords
         WHERE kw = '" . mysql_real_escape_string($q) . "'"

[mgutt]

> Index
Nein, weil ein Index auf VARCHAR ziemlich unsinnig ist, wenn VARCHAR wie bei mir viele unterschiedliche Werte mit teilweise langen Phrasen enthält. MySQL dazu:
http://www.mysql.com/news-and-events...000000075.html

Es wird also empfohlen nur einen Teil des VARCHAR zu nutzen, z.B. die ersten 10 Zeichen. Daher auch meine Idee, erstmal nur den INT-Wert des ersten Buchstabens zu nutzen, da damit die Filterung schon um den Faktor 20-40 reduziert wird und im Gegensatz zu MySQLs Tipps sogar ein noch schnellerer INT-Vergleich möglich ist (so die Idee).

Einen INDEX auf kw würde die Anzahl der Reihen auf schätzungsweise 943k reduzieren, also nicht wirklich viel und es sind identisch viele Reihen wie der INDEX auf project, da die Keywords pro Projekt ermittelt werden und damit in jeder Zeile ein anderes Keyword steht.

Bei einem Test mit einer anderen Tabelle ähnlicher Größe resultierte ein Index auf VARCHAR einen großen Performance-Nachteil, daher habe ich mich bisher nicht getraut einen bei dieser Tabelle zu setzen. Wenn Du aber meinst, dass es sinnvoll ist, dann teste ich das gerne noch mal.

> EXPLAIN
Nur auf kw:

id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE keywords ALL NULL NULL NULL NULL 1090221 Using where

auf kw und project

id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE keywords ref project project 3 const 943219 Using where

auf kw, project und first

id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE keywords ref first,project first 1 const 17778 Using where

EDIT:
Den Index auf project habe ich wieder entfernt, weil dadurch ein ORDER BY auf search_time 10 und mehr Sekunden dauert.

Gruß

[Crisps]

Ich hab mir deinen Link mal angesehen und kann dort nichts finden was einem Index auf Varchar Spalten wiedersprechen würde (Was mich auch sehr überrascht hätte). Es wird dort nur gesagt, dass Ein Index auf Varchar nicht sehr platzsparend ist (nicht so wild) und langsam sei (langsam beim einfügen) - Das ist aber alles relativ, denn bei der Abfrage selbst wirst Du einen deutlichen Geschwindigkeitsvorteil merken - die Inserts selbst brauchen vielleicht ein paar tausendstel (!) Sekunden länger als sonst.

Es wird also empfohlen nur einen Teil des VARCHAR zu nutzen, z.B. die ersten 10 Zeichen. Daher auch meine Idee, erstmal nur den INT-Wert des ersten Buchstabens zu nutzen, da damit die Filterung schon um den Faktor 20-40 reduziert wird und im Gegensatz zu MySQLs Tipps sogar ein noch schnellerer INT-Vergleich möglich ist (so die Idee).

Ich glaube nicht, dass Du das so umständlich machen musst. Kopier doch mal deine gesamte Tabelle auf eine zweite DB, in der Du das ganze dann durchtesten kannst.

Das mit der reduzierten Indexlänge ist schon mal ein guter Ansatz:

ALTER TABLE keywords ADD INDEX ix_first (kw (1));

Hier werden nur die ersten Buchstaben deiner Keywords indexiert. Ich glaube Du wirst staunen um wie viel schneller so ein einfacher Index bereits deine Abfragen beschleunigt. Ich würde aber mit der Indexlänge noch etwas höher gehen, wie hoch? Ich würde mal sagen so um die ersten 6-8, was natürlich auch von der Wörterlänge abhängt. Aber wie gesagt, probier das doch mal auf einer seperaten Datenbank/Tabelle aus.

Bei einem Test mit einer anderen Tabelle ähnlicher Größe resultierte ein Index auf VARCHAR einen großen Performance-Nachteil, daher habe ich mich bisher nicht getraut einen bei dieser Tabelle zu setzen. Wenn Du aber meinst, dass es sinnvoll ist, dann teste ich das gerne noch mal.

Ich bin mir sehr sicher. ;) Deine negativen Erfahrungen mit einer anderen Tabelle - hm, nun das kann ich von hier natürlich nicht beurteilen, es gibt allerdings keinen Grund, dass Indexe auf Varchar generell einen Performance Nachteil hätten.

auf kw und project

Wenn du eine solche Abfrage hast, wäre es unter Umständen noch besser einen Composite-Index anzulegen - etwa so:

ALTER TABLE keywords ADD INDEX ix_projekte_kw (projekte, kw (6));

Da MySQL nur einen Index pro Abfrage nutzen kann, legen wir einen Index an der die Projekt Spalte und die ersten sechs Buchstaben der Keywords kombiniert. Die Where-Condition muss dann aber auch mit "WHERE projekte AND kw = ''" beginnen, nicht andersrum.

[defabricator]

Use index on prefix: Indexes on varchar columns take a lot of space and so generally can be slow. If your data is very different even by the start of the string you may benefit from creating index on column prefix:
ALTER TABLE MYTABLE ADD KEY NAME_KEYT (NAME(20))

Das solltest Du tun - wenn Du MyISAM verwendest.
Damit begrenzt Du den Index (in diesem Beispiel) auf die ersten zwanzig Zeichen. Deine Vorgehensweise, nur den ersten Buchstaben zu betrachten, entspricht (und das ist mit viel Vorsicht zu genießen) ungefähr einem Index Feldname(1) - nur sinnvoller.

p.s.: Das soll jetzt übrigens nicht heißen, dass Du einen Index der Länge 1 setzen sollst ;) Aber vielleicht 4, 8, 20 ....je nachdem, wie Deine Daten aussehen.

[mgutt]

>langsam beim einfügen
Das gilt nicht nur beim INSERT, sondern auch beim SELECT. Umso größer der Datensatz, umso mehr Festplattenzugriff ist nötig, um den Zieldatensatz zu finden. Besonders wenn es so viele Zeilen sind wie in der Tabelle. Die Begrenzung des Indexes auf die ersten X Zeichen ist im Grund nichts anderes als was ich bei V1 und V2 vorschlage, nur ist eben die Frage was besser ist (V1, V2 oder begrenzender Index).

> Composite-Index
Indexe über mehrere Spalten verstehe ich ehrlich gesagt nicht. Immer wieder wenn ich die einsetze ist das Resultat grausam. Gibt es dazu irgendwo Erklärungen mit Beispielen wann ich mehrere Indexe setzen sollte? Mir fehlt da immer das Verständnis, wenn ich 3-4 WHERE-Vergleiche habe und 1-2 ORDER BY, welche Spalten einen einzelnen Index brauchen und welche multiple. Häufig wird die eine Abfrage dadurch schneller und eine andere wird grottenlangsam.

>Deine Vorgehensweise ... entspricht ... ungefähr einem Index Feldname(1)
Genau so bin ich auch auf meine Variante gekommen. Die Frage ist jetzt was besser ist. Ich glaube, dass wenn ich über INT vergleiche, bessere Resultate erhalte, als wenn ich mit einem begrenzenden Index arbeite.

>oben genannter Link
In dem Link steht ja zusätzlich, dass VARCHAR(255) langsamer ist als VARCHAR(50). Kann ich die Tabelle so sortieren, dass der längste Wert ermittelt werden kann? Dann würde ich analysieren, wie lang mein längster Wert ist und VARCHAR entsprechend optimieren. Ansonsten würde müsste ich zeilenweise alles durcharbeiten und per PHP auswerten.

[Crisps]

Das gilt nicht nur beim INSERT, sondern auch beim SELECT. Umso größer der Datensatz, umso mehr Festplattenzugriff ist nötig, um den Zieldatensatz zu finden. Besonders wenn es so viele Zeilen sind wie in der Tabelle.

Gut, wenn dir so ein minimaler Verlust wichtiger ist als ein deutlich beschleunigte SELECT Abfrage.....................

Die Begrenzung des Indexes auf die ersten X Zeichen ist im Grund nichts anderes als was ich bei V1 und V2 vorschlage, nur ist eben die Frage was besser ist (V1, V2 oder begrenzender Index).

Begrenzter Index. Mit den Datensätzen direkt in MySQL zu arbeiten ist eigentlich immer vorzuziehen und auch sauberer.

Indexe über mehrere Spalten verstehe ich ehrlich gesagt nicht. Immer wieder wenn ich die einsetze ist das Resultat grausam. Gibt es dazu irgendwo Erklärungen mit Beispielen wann ich mehrere Indexe setzen sollte? Mir fehlt da immer das Verständnis, wenn ich 3-4 WHERE-Vergleiche habe und 1-2 ORDER BY, welche Spalten einen einzelnen Index brauchen und welche multiple. Häufig wird die eine Abfrage dadurch schneller und eine andere wird grottenlangsam.

Das kann man nicht so pauschal sagen, dazu muss man die Query genauer kennen.

Kann ich die Tabelle so sortieren, dass der längste Wert ermittelt werden kann? Dann würde ich analysieren, wie lang mein längster Wert ist und VARCHAR entsprechend optimieren.

SELECT MAX(LENGTH(kw)) FROM keywords;

(Kann bei deiner großen DB ggf. länger dauern)

[defabricator]

Zitat von mgutt

Ich glaube, dass wenn ich über INT vergleiche, bessere Resultate erhalte, als wenn ich mit einem begrenzenden Index arbeite.

Was veranlasst Dich zu diesem Glauben?
Ich sehe da erstmal etwas, das Du "per Hand" machen musst, einen Zusätzlichen Funktionsaufruf in PHP+Zuweisung, eine zusätzliche Vergleichsoperation in SQL und einen Eingriff in den "Kernbereich" von dem, was Datenbanken tun sollen. Dafür reicht mir bloßer Glaube als Argument nicht aus ;)

[mgutt]

>LENGHT()
Ok, der Name war eigentlich naheliegend ;) Danke!

Es wurde zwar jegliche Länge genutzt, aber auf Grund der prozentualen Verteilung, habe ich VARCHAR auf 100 reduziert.

>Mit den Datensätzen direkt in MySQL zu arbeiten ist eigentlich immer vorzuziehen und auch sauberer.
Nun sauber bringt ja nichts, wenn die genannte Idee schneller ist.

Ich werde aber mal alle Varianten außer V2 durchtesten:

A) Index auf first
Abfrage nach kw: 0.19071723937988
Abfrage nach projekt und kw: 0.22569104194642
Abfrage nach projekt, first und kw: 0.030680880546565
Die Abfrage projekt,first,kw ist damit also 7x schneller als projekt,kw geworden.

B) Mit dem index auf first und kw(5):
Abfrage nach kw: 0.0021519637107848
Abfrage nach projekt und kw: 0.0017872953414916
Abfrage nach projekt, first und kw: 0.0041718840599059
Die Abfrage projekt,kw ist 2x schneller als projekt,first,kw und ingesamt viel schneller als in A) also ist das der richtige Weg

C) Mit dem index auf kw(5):
Abfrage nach kw: 0.0025481438636782
Abfrage nach projekt und kw: 0.0031441688537598

D) Mit dem index auf kw(10):
Abfrage nach kw: 0.0011384558677673
Abfrage nach projekt und kw: 0.0021649360656737

E) Mit dem index auf kw:
Abfrage nach kw: 0.0024761486053465
Abfrage nach projekt und kw: 0.002344229221344

F) Mit dem index auf projekt+kw(10):
Serverabsturz, weil die Abfrage mit WHERE projekt = 1 ORDER BY tries LIMIT 100 zu lange dauert.

G) Mit dem index auf kw(10):
Abfrage nach kw: 0.0022609758377075
Abfrage nach projekt und kw: 0.0017019295692445
Abfrage nach kw und projekt: 0.0020268511772155

Die Tests resultieren übrigens aus dem Schnitt von 100 Abfragen in zufälliger Reihenfolge im Live-Betrieb.

Fazit:
Meine Idee war sinnlos :P Wie man jetzt noch einen Index auf projekt setzen könnte weiß ich nicht. Dem Test zufolge war die Wahl von kw(10) mit die Beste, die ich jetzt auch aktiv nutze.

Wie erkenne ich eigentlich welche Größe der Index haben soll? Ich mein jetzt ergibt der Index 363434 Zeilen, also ca. 1/3 der gesamten Zeilen. Kann man das als Richtwert nehmen?

[Crisps]

Wie erkenne ich eigentlich welche Größe der Index haben soll? Ich mein jetzt ergibt der Index 363434 Zeilen, also ca. 1/3 der gesamten Zeilen. Kann man das als Richtwert nehmen?

Ich würde sagen, dass das von der Wörterlänge abhängt - das habe ich jedenfalls bis vor kurzem so gedacht. Allerdings hat sich bei einem Test von Strings mit etwa 10 Buchstaben und einem zweiten Test mit Strings von 30 Buchstaben gezeigt, dass bei beiden bereits eine Indexlänge von 5-6 reicht, bei einem längeren Index konnte ich praktisch keinen Vorteil messen. Das ganze muss man aber mit den gegebenen Daten ausprobieren.