[mysql] N:M und ORDER BY - kann Index nicht nutzen

mr_vista
Posts: 57
Joined: 2006-08-01 22:33
Location: Berlin

[mysql] N:M und ORDER BY - kann Index nicht nutzen

Post by mr_vista »

Hallo,

folgendes Problem:

Wir haben eine klassische n:m Relation zwischen zwei Tabellen.
Zum einem eine Tabelle, die die Verbindungen zwischen Usern enthält (so eine Art Freundesystem) und eine Tabelle, die die Aktionen aller Personen im System loggt.

tbl_verbindungen (user_id, hat_verbindung_zu_user_id) INDEX: (user_id)

tbl_log (user_id, hat_gemacht, datum, uhrzeit) INDEX: (user_id, datum, uhrzeit)

Nun soll abgefragt werden: "zeige alle Aktionen der Verbindungen (Freunde) von User xy UND sortiere sie nach Datum und Uhrzeit"

SQL (vereinfacht):

Code: Select all

SELECT * FROM tbl_log AS a LEFT JOIN tbl_verbindungen AS b ON b.user_id = '123' WHERE a.user_id = b.hat_verbindung_zu_user_id ORDER BY a.datum DESC, a.uhrzeit DESC


Es sollen also alle Aktionen der "Freunde" von User 123 angezeigt werden. Die Abfrage klappt auch so. Das Problem dabei ist, dass MySQL aufgrund dessen, dass mehrere Verbindungen mehrere Aktionen haben können (n:m), bei "ORDER BY" keinen INDEX benutzen kann. Stattdessen werden die gefundenen Datensätze mit Hilfe einer temporären Tabelle und filesort sortiert. Das ist natürlich sehr langsam, wenn viele Aktionen gefunden werden.

Frage: Gibt es iiirgendeine Möglichkeit die gleiche Funktionalität durch ein anderes Datenbankdesign performanter zu gestalten, so dass eine Abfrage den INDEX auch zur Sortierung nutzen kann?

Ich danke für eure Hilfe.
Gruß, Alex
Top

braindead
RSAC
Posts: 257
Joined: 2002-10-22 09:49
Location: vorm Rechner

Re: [mysql] N:M und ORDER BY - kann Index nicht nutzen

Post by braindead »

Dein Abfrage erscheint mir an mehreren Stellen unlogisch:

1: Vermutung: user_id ist ein int und du fragst string ab
2: Vermutung: dein Join macht so keinen Sinn, er muss so aussehen:

SELECT * FROM tbl_log AS a LEFT JOIN tbl_verbindungen AS b ON a.user_id = b.hat_verbindung_zu_user_id WHERE b.user_id = '123' ORDER BY a.datum DESC, a.uhrzeit DESC

3: Vermutung: du hast die Index spalten einzeln gesetzt und nicht einen index über die 3 spalten anglegt.

alter table tbl_log add index user_time (user_id desc, datum desc, uhrzeit desc);

Wenn das alles net hilft, mach ein explain <sql statement> und poste den output hier.
Top

mr_vista
Posts: 57
Joined: 2006-08-01 22:33
Location: Berlin

Re: [mysql] N:M und ORDER BY - kann Index nicht nutzen

Post by mr_vista »

erstmal Danke fürs Antworten.

Sorry, hab vergessen die Datentypen dazuzuschreiben.

tbl_verbindungen (user_id INT, hat_verbindung_zu_user_id INT) INDEX: (user_id)

tbl_log (user_id INT, hat_gemacht TINYINT, datum DATE, uhrzeit TIME) INDEX: (user_id, datum, uhrzeit)


zu Punkt 1: ist hier eigentlich egal, also es funktioniert mit und ohne Anführungszeichen

zu Punkt 2: nein, also die Abfrage funktioniert so wie ich sie gepostet habe. Deine Version macht genau das Selbe und ist genauso schnell. Wie man es schreibt ist egal, deins ist aber auch korrekt :)

punkt 3: auch nein :) der Index ist über 3 Spalten. Mein Problem beschreibt die MySQL-Doku wie folgt:

(ORDER BY kann keinen INDEX nutzen wenn: ...

Sie verknüpfen zahlreiche Tabellen, und die Spalten in der ORDER BY-Klausel stammen nicht alle aus der ersten nichtkonstanten Tabelle, die zum Abrufen von Datensätzen verwendet wird. (Dies ist die erste Tabelle in der Ausgabe von EXPLAIN, die nicht den Join-Typ const aufweist.)



Es ist also wohl die m:n Relation "schuld" ... also User 123 kann beispielswiese 100 (m) Freunde haben. Jeder dieser Freunde kann unterschiedlich viele Aktionen haben (n). Dadurch kann MySQL den Index nicht für die Sortierung nutzen.
ich erinner mich ganz dunkel zurück, dass man doch m:n Relationen mit Hilfe von Verknüpfungstabellen in 1:n Tabellen umwandeln kann. Kann das hier vielleicht jemand ausm Schlaf? Habe mich mal dran versucht, aber noch nichts Brauchbares erschaffen.


Code: Select all

id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE b ref user_id user_id 4 const 203 Using index; Using temporary; Using filesort
1 SIMPLE a ref user_id user_id 4 db1.b.hat_verbindung_zu_user_id 2
Top

braindead
RSAC
Posts: 257
Joined: 2002-10-22 09:49
Location: vorm Rechner

Re: [mysql] N:M und ORDER BY - kann Index nicht nutzen

Post by braindead »

zu Punkt 1: ist hier eigentlich egal, also es funktioniert mit und ohne Anführungszeichen


Mag funktionieren, dadurch kann es aber passieren das der INDEX nicht genutzt werden kann und selbst wenn der Index genutzt wird ist es einfach schlechter Stil.

zu Punkt 2: nein, also die Abfrage funktioniert so wie ich sie gepostet habe. Deine Version macht genau das Selbe und ist genauso schnell.


Mag wiederrum sein das es klappt, is trozdem falsch und verlangt dem Optimizer mehr ab als nötig (das selbe gilt übrigens für den * im select, das ist auch schlechter Stil)

Zu deinem Problem, du hast kein N:M Verbindung für diese Abfrage. Du musst nur die Abfrage rumdrehen:

SELECT * FROM tbl_log AS a STRAIGHT_JOIN tbl_verbindungen AS b ON a.user_id = b.hat_verbindung_zu_user_id WHERE a.user_id = 123 ORDER BY a.datum DESC, a.uhrzeit DESC

Damit sollte erst Tabelle a und dann b abgefragt werden. Damit ist dann alles in Tabelle a const und kann für den SORT genutzt werden.
Top

mr_vista
Posts: 57
Joined: 2006-08-01 22:33
Location: Berlin

Re: [mysql] N:M und ORDER BY - kann Index nicht nutzen

Post by mr_vista »

Nochmals Danke.

Ja das * ist auch nur, damit die Abfrage übersichtlich bleibt. In der richtigen Abfrage sind auch noch 3 andere Tabellen dabei, die aber nur 1:1 Relationen haben.

Leider funktioniert deine Abfrage diesmal nicht, da ist ein Logikfehler drin.
Bei "WHERE a.user_id = 123" würde er mir die geloggten Aktionen von User 123 anzeigen, nicht aber die Aktionen der Freunde von dem User.

SELECT * FROM tbl_log AS a STRAIGHT_JOIN tbl_verbindungen AS b ON b.user_id = 123 WHERE a.user_id = b.hat_verbindung_zu_user_id ORDER BY a.datum DESC, a.uhrzeit DESC

so funktioniert es wieder, aber natürlich kann er den Index wieder nicht nutzen :-/

andere Möglichkeit:
SELECT * FROM tbl_log AS a STRAIGHT_JOIN tbl_verbindungen AS b ON b.user_id = 123 AND b.hat_verbindung_zu_user_id = a.user_id ORDER BY a.datum DESC, a.uhrzeit DESC

aber auch hier genau das Gleiche. Index kann nicht genutzt werden.
Ich bin mir ziemlich sicher, dass es eine N:M Relation ist, das ergibt sich ja aus der Logik :) Ein User kann mehrere Freunde haben. Jeder dieser Freunde kann mehrere Aktionen haben. Man kann diese Logik ja nicht ändern, indem man die Abfrage umstellt. (Wäre mir neu)
Top

braindead
RSAC
Posts: 257
Joined: 2002-10-22 09:49
Location: vorm Rechner

Re: [mysql] N:M und ORDER BY - kann Index nicht nutzen

Post by braindead »

Der Logikfehler ist mir dann auch eingefallen. Also ein

SELECT * FROM tbl_log AS a where a.user_id in (select b.hat_verbindung_zu_user_id from tbl_verbindungen AS b where b.user_id = 123) ORDER BY a.datum DESC, a.uhrzeit DESC

und nein das ist kein N:M da ein record in der Logtb ja immer zu einem User passt und net zu X usern.
Top

mr_vista
Posts: 57
Joined: 2006-08-01 22:33
Location: Berlin

Re: [mysql] N:M und ORDER BY - kann Index nicht nutzen

Post by mr_vista »

ok Danke mal wieder :)

Leider löst es das Problem nicht :-/ ... die Abfrage an sich liefert die korrekten Ergebnisse, jedoch kann nun für Tabelle 'a' garkein Schlüssel verwendet werden (auch nicht für das "WHERE")

Daran, dass es eine N:M Relation ist, ändert es glaub ich auch nichts, denn die Subquery "(select b.hat_verbindung_zu_user_id from tbl_verbindungen AS b where b.user_id = 123)" liefert ja mehrere Verbindungen, von denen jeder wieder mehrere Aktionen haben kann.

Deine letzte Aussage ist vollkommen richtig, jedoch ist die Abfragelogik ganz anders. Es sind nun mal N User die jeweils M Aktionen haben können.

Eine reine Abfrage "liefer mir alle Aktionen des Users 123 und sortiere diese", wäre absolut kein Problem. Es hapert wirklich daran, dass es aber "liefer mir alle Aktionen aller Verbindungen von User 123" heisst ... und ich denke, da muss man einfach irgendwie vermeiden, dass es eine N:M Relation gibt indem man irgendwie eine Verknüpfungstabelle baut oder diese ganze Funktion irgendwie anders realisiert.
Top

braindead
RSAC
Posts: 257
Joined: 2002-10-22 09:49
Location: vorm Rechner

Re: [mysql] N:M und ORDER BY - kann Index nicht nutzen

Post by braindead »

*arg* ok, mein Fehler ;) Du machst die Abfrage doch sicher aus einer Software heraus. Wenn du da das ganze in 2 Teile teilst. Also erst die Subquery und dann den Output in die andere Query in das IN dann nimmt er auch den Index. Der andere weg geht in MySql leider nicht.

Mal ne ganz andere Frage, wie kommst du eigentlich drauf das er den Index nicht nutzt? Laut deinem Explain sieht das doch ganz gut aus.
Top

mr_vista
Posts: 57
Joined: 2006-08-01 22:33
Location: Berlin

Re: [mysql] N:M und ORDER BY - kann Index nicht nutzen

Post by mr_vista »

Also er nutzt den ersten Teil des Index fürs "WHERE a.user_id = b.hat_verbindung_zu_user_id", nicht aber für die Sortierung und die frisst die meiste Zeit. Die Abfrage ohne Sortierung läuft top :)

Hm ja , das ganze läuft unter PHP ... hab auch überlegt die Datensätze abzufragen und dann per Javascript zu sortieren (was nicht schlimm wäre, da Javascript Voraussetzung für unsere Software ist)... das Problem besteht dann nur darin, dass in der Originalabfrage nur 50 Datensätze ausgegeben werden sollen. Wenn nun aber 500 vorhanden sind, müssen erst alle abgefragt, sortiert und dann ausgegeben werden. Ist nicht gerade effizient :)

Wie meintest du das genau mit dem Teilen?
Top

braindead
RSAC
Posts: 257
Joined: 2002-10-22 09:49
Location: vorm Rechner

Re: [mysql] N:M und ORDER BY - kann Index nicht nutzen

Post by braindead »

Also du machst er die Abfrage:

select b.hat_verbindung_zu_user_id from tbl_verbindungen AS b where b.user_id = 123

den output packst du dann via php in (also csv draus machen und dann als String einfügen)

SELECT * FROM tbl_log AS a where a.user_id in ($data) ORDER BY a.datum DESC, a.uhrzeit DESC

Dann sollte das auf jeden Fall klappen. Ich verstehe nur immer noch nicht warum er den Index nicht zum sortieren nimmt.
Top

mr_vista
Posts: 57
Joined: 2006-08-01 22:33
Location: Berlin

Re: [mysql] N:M und ORDER BY - kann Index nicht nutzen

Post by mr_vista »

Hi, Danke!

Also ich muss langsam hier erstmal definieren.
So eine Abfrage dauert nun durchschnittlich bei uns 0,0050 Sekunden. Kann aber auch (je nach dem wieviele Datensätze sortiert werden müssen) bis 0,0200 Sekunden dauern.
Ohne Sortierung dauert die Abfrage allerdings nur 0,0003 bis 0,0006 Sekunden und das ist bei einer erheblichen Anzahl von Abfragen schon bemerkbar.

Ja, die Felder sind *wirklich* indiziert :) Ich arbeite mit vielen Tabellen und Abfragen, bei denen auch mehrspaltige Indizes - gerade für die Sortierung - zur Anwendung kommen. Das Problem, dass MySQL gerade das bei einer N:M Relation nicht nutzen kann, war mir auch neu und daher mein Schrei nach Hilfe :)

Den Tabellentyp "Memory" für diese Tabelle zu verwenden ist vielleicht eine gute Idee. Ich werde das gleich mal testen... *test* ... schade, die Mehrheit der Testabfragen war langsamer.

Die temporären Tabellen die zur Sortierung von MySQL angelegt werden, werden im Speicher gebaut... also ist dies dafür schon die beste Möglichkeit, jedoch sind grundsätzlich temporäre Tabellen zu vermeiden wenn es um Performance geht.

Gruß
Top

mr_vista
Posts: 57
Joined: 2006-08-01 22:33
Location: Berlin

Re: [mysql] N:M und ORDER BY - kann Index nicht nutzen

Post by mr_vista »

hmhm danke... also du hast mir verschiedene Denkansätze gegeben über die ich zur Zeit nachdenke

Datencaching wäääre eine Idee. Jetzt überlege ich, was besser wäre:

1. man cached die angezeigten Datensätze in einem SESSION array (wie es da mit der Performance aussieht, weiss ich aber auch nicht) und fragt, nach erstmaliger Abfrage, nur noch die Anzahl der Aktionen ab. Hat die Anzahl sich geändert, muss die ganze Abfrage wieder durchgeführt werden.
Auch möglich: Man cached einfach den html-code als PHP-String. Wäre eine sehr große Sessionvariable.
Weiss jemand wie sehr sowas die Performance beeinträchtigt?


2. man cached die Datensätze für jeden User in einer MEMORY Tabelle. Dadurch kommen sehr viele Datensätze zusammen. (Da man die N:M Relation in 1:N Relation umwandelt)

Problem bei der 2. Möglichkeit wäre eine Änderung bzw. ein Update. Da eine neue Aktion eines Users all seine Verbindungen (Freunde) betrifft (sagen wir mal 200), müsste auf diese Cachingtabelle 200 Inserts ausgeführt werden.
Top

Roger Wilco
Administrator
Administrator
Posts: 6001
Joined: 2004-05-23 12:53

Re: [mysql] N:M und ORDER BY - kann Index nicht nutzen

Post by Roger Wilco »

Mr_Vista wrote:Datencaching wäääre eine Idee. Jetzt überlege ich, was besser wäre: [...]

3. Man benutzt memcached und das entsprechende PECL-Paket für den Zugriff. Nur so als Vorschlag. ;)
Top

mr_vista
Posts: 57
Joined: 2006-08-01 22:33
Location: Berlin

Re: [mysql] N:M und ORDER BY - kann Index nicht nutzen

Post by mr_vista »

Also das Projekt möchte ich nicht öffentlich nennen, wenn es dich aber brennend interessiert, einfach kurz eine PM :)

Es ist im Grunde sowas wie MySpace... dort gibt es so eine Funktion "Dein Freund 'James Bond' hat neue Bilder zu seinem Profil hinzugefügt" oder so ähnlich.

Diese Art von Funktion gilt es nun so Performanceschonend wie möglich umzusetzen.


Danke@Roger ... memcached klingt interessant, hab mich eben mal reingelesen.

Anwendung

memcached eignet sich hervorragend um Objekte abzulegen, die zwischengespeichert werden müssen, die z.B. auf einer anderen Page wieder hergestellt werden sollen. Desweiteren kann man langsam die Ergebnisse langsamer Datenbank Anfragen ablegen (z.B. von Suchanfragen) oder Seitenfragmente cachen, um aufwendige Berechnungen zu reduzieren.
Ein weiterer denkbarer Einsatzzweck wäre der RSS Feed!


Das cachen von Seitenfragmenten ist ja soetwas, was geeignet wäre.
Top