IPC 2014

Mit MySQL zufälligen Datensatz selektieren

Ich habe ja bereits zwei mal Beiträge geschrieben, wie man performant einen bzw. mehrere Datensätze per SQL selektieren kann. Heute möchte ich einen neuen, eleganteren Ansatz beschreiben, der allerdings etwas PHP benötigt (die anderen basierten allein auf MySQL).

Um eine Einleitung zu finden, möchte ich nochmal betonen, dass folgende Abfrage sehr schlecht ist:

SELECT spalte 
FROM tabelle 
WHERE andereSpalte='123' 
ORDER BY RAND()
LIMIT 1

Diese Möglichkeit sieht zwar im ersten Augenblick elegant aus und funktioniert ja auch, allerdings ist sie hochgradig langsam! Und mit langsam meine ich seeeehr langsam!
Das Problem bei dieser Abfrage ist, dass für jeden Datensatz, der die Bedingungen erfüllt (wenn man keine WHERE-Bedingung hat, wird es nur noch schlimmer) ein Zufallswert bestimmt werden muss und erst anschließend nach diesem Wert sortiert werden kann. Dazu muss dann noch eine temporäre Tabelle erstellt werden. Die entsprechende EXPLAIN-Ausgabe (von mir leicht gekürzt, da sonst zu breit) sieht dann beispielsweise so aus:

select_type table type possible_keys key ref rows Extra
SIMPLE tabelle ref andere andere const 5870 Using temporary; Using filesort

Insbesondere die letzte Spalte ist hier interessant: Es muss eine temporäre Tabelle erzeugt werden (Using temporary) anschließend sortiert werden (Using filesort – dazu kann natürlich kein Index benutzt werden). In den Query-Cache kann eine solche Abfrage natürlich auch nicht gespeichert werden, da die RAND()-Funktion ja bei jedem Aufruf andere Datensätze auswählt.

Nun kommt die Alternative, auf die mich ein sehr interessanter Beitrag von Tutsplus.com mit dem Titel Top 20+ MySQL Best Practices gebracht hat. Dazu sind 2 Querys und ein wenig PHP-Code nötig.
Und zwar selektiert man erstmal die Anzahl aller Datensätze, die die Bedingungen erfüllen. Dazu kann (eigentlich) immer ein Index genutzt werden:

SELECT COUNT(*)
FROM tabelle
WHERE andereSpalte='123'

Mit dieser Anzahl kann nun mit PHP eine Zufallszahl zwischen 0 und (Anzahl-1) gebildet werden:

$rs= mysql_query("SELECT COUNT(*) 
FROM tabelle 
WHERE andereSpalte='123'");
$anzID = mysql_result($rs,0);
$rand = mt_rand(0,$anzID - 1);

Und nun kommt das Interessante. Diese Zufallszahl kann nun das OFFSET für die eigentliche Nutzdaten-Query werden:

$rs = mysql_query("SELECT spalte 
FROM anzeigen 
WHERE andereSpalte='123' 
LIMIT ".$rand.",1");

Und das ist das ganze Geheimnis. Nun kann immer der Index für die Bedingung genutzt werden und dann wird einfach der x-te Datensatz zurückgeliefert, der die Bedingung erfüllt. Im EXPLAIN sieht das ganze dann so aus:

select_type table type possible_keys key ref rows Extra
SIMPLE tabelle ref andere andere const 5870  

Man beachte, dass in der Spalte Extra nichts steht – eine optimale Abfrage.
Wie groß der Geschwindigkeitsunterschied in der Praxis ist, hängt von der Anzahl der Datensätze ab, die die Bedingungen erfüllen. Je mehr Datensätze, desto langsamer ist ORDER BY RAND(). Auf jeden Fall spart man sich aber die temporäre Tabelle und das ist schon viel wert.

In meiner Testdatenbank erfüllten ca. 6000 von insgesamt ca. 500.000 Datensätzen die Bedingung andereSpalte='123'.
Die Abfrage mit ORDER BY RAND() LIMIT 1 brauchte 0,05 Sekunden.
Die Abfragen (inkl. PHP) mit der oben beschriebenen Art und Weise mit COUNT(*) und LIMIT $rand,1 benötigte 0,001 Sekunden.
Das bedeutet eine Beschleunigung um den Faktor 50.

Nun möchte man aber manchmal mehrere Datensätze zufällig selektieren und nicht nur einen. Hierzu ist die Vorgehensweise sehr ähnlich, nur der PHP-Code muss etwas erweitert werden.
Zuerst wird wieder die Gesamtanzahl an Datensätzen bestimmt, die die Bedingungen erfüllt (siehe oben).
Anschließend müssen x Zufallszahlen gebildet werden. Und mit diesen wird dann eine SQL-Abfrage mit UNIONs gebaut. Im Code sieht das so aus:

$einlesen = mysql_query("SELECT COUNT(*) 
FROM tabelle WHERE 
andereSpalte='123'");
$anz_cnt = mysql_result($einlesen,0);
$rands = array();
$x = 3;
while(count($rands)<$x && $anz_cnt>count($rands)) {
  $rand = mt_rand(0,$anz_cnt - 1);
  if(!isset($rands[$rand])) $rands[$rand] = $rand;
}
 
$queryparts = array();
foreach($rands as $rand) $queryparts[] = "SELECT spalte 
FROM tabelle 
WHERE andereSpalte='123' 
LIMIT ".$rand.",1";
 
$rs = mysql_query("(".implode(") UNION ALL (",$queryparts).")");

Die Schleife beim Erhalten der Zufallszahlen ist deshalb eine while- und keine for-Schleife, weil es sonst passieren kann, dass es zwar mehr als x Datensätze gibt, die die Bedingungen erfüllen, aber dummerweise 2 mal die gleiche Zufallszahl ermittelt wird. Die Bedingung $anz_cnt>count($rands) dient dazu, dass keine Endlosschleife entsteht, wenn weniger als x Datensätze die Bedingung erfüllen.
Bei der abschließenden Abfrage wird UNION ALL benutzt statt UNION, damit MySQL die Einzelergebnisse nicht noch versucht zu gruppieren (wir wissen ja durch die while-Schleife bereits, dass keine Duplikate selektiert werden können). UNION bedeutet nämlich in Wirklichkeit UNION DISTINCT.
Auch hier bleibt die Spalte Extra beim EXPLAIN leer.

Wie findet ihr diesen Ansatz? Habt ihr noch andere Vorschläge oder Vorschläge, wie man diese Vorgehensweise noch optimieren könnte? Ich freue mich auf Kommentare!


Schlagwörter: , , ,

19 Kommentare bisher »

  1. robo47 sagt

    am 28. November 2009 @ 13:10

    Für große Mengen kann man das

    if(!in_array($rand,$rands)) $rands[] = mt_rand(0,$anz_cnt – 1);

    noch etwas optimieren indem man anstatt mit in_array Werten in einem Array zu suchen, diese als Indizies des Arrays nutzt und dann via

    isset($rands[$rand])

    überprüft, das ist ein gutes stückchen schneller bei großen arrays

  2. Jan sagt

    am 28. November 2009 @ 16:18

    Du hast Recht, danke Dir. Ich habe den Beitrag angepasst (zumal da eh noch ein kleiner Fehler war, denn die Zufallszahl wurde 2 mal berechnet. Das passt aber nun auch).

  3. Phate sagt

    am 30. November 2009 @ 08:57

    Hallo!
    Recht interessanter Ansatz.
    Allerdings fehlt mir für den Union-Abschnitt ein wenig die Auswertung. Wenn ich den Code so richtig nachvollzogen habe, dann würde das effektiv doch bedeuten, dass auf Grundlage der oberhalb genannten 6000 Einträge auch 6000 Selects via Union All verknüpft würden?! Ich mag mich täuschen und weiß es auch nicht, aber im ersten Moment klingt gerade das für mich nicht nach einem sonderlich performanten Lösungsweg.

    Ich hätte es eher auf php-Basis gelöst wenn ich die Aufgabe bekommen hätte. Hätte zuerst alle Einträge ohne Sortierung selektiert und daraus ein Array erstellt. Dann hätte ich die core-Funktion array_rand angewendet und das Ergebnis ausgegeben.

    Sähe im groben so aus:

    $sql = "SELECT spalte
    FROM tabelle
    WHERE andereSpalte='123'";

    $res = mysql_query($sql, $db);
    while($data = mysql_fetch_assoc($res))
    {
    $values[] = $data['spalte'];
    }

    $order = array_rand($values, count($values));

    foreach($order as $index)
    echo $values[$index].";

    Vielleicht könntest du das mal auf Performance testen?! Mir fehlen dazu gerade die entsprechenden Notwendigkeiten.

    Gruß

  4. Jan sagt

    am 30. November 2009 @ 09:43

    @Phate: Nein, bei dem Union werden nicht 6000 Datensätze per Union verknüpft sondern pro Union-Bestandteil genau 1 Datensatz (denn Du hast ja LIMIT x,1)

    Bei Deinem Weg müssten zuerst alle Datensätze der Tabelle an PHP geschickt werden. Das können riesige Datenmengen werden! Denk mal daran, wenn Du keine WHERE-Bedingung hast und mehrere Spalten selektieren möchtest. Dann hat Deine Tabelle z.B. 1 Mio Datensätze und Du brauchst daraus 3 VARCHAR(255)-Datensätze (bei denen wir mal der Einfachheit halber mal davon ausgehen, dass sie alle mit 255 Zeichen gefüllt sind). Dann wären das
    10^6 * 3 * 256 Bytes = 768 * 10^6 Bytes = ca. 732 MB
    Und schon kommt man mit Deinem Script ganz schnell ans memory_limit.

  5. Phate sagt

    am 30. November 2009 @ 10:33

    Ahhh ok! Mir war bewusst geworden, dass es eigentlich nur um die $x Einträge ging. Hatte das garnicht so wahrgenommen und für eine blose Einschränkung für die Ausgabe gehalten. Daher auch meine Anmerkung auf die 6000 Selects. Dachte es solle um alle Einträge gehen. Sorry, das war mir irgendwie nicht klar geworden.
    Klar, bei nur 3 Elementen sieht das ganz anders aus. Zumal meine Lösung für eine derartige Aufgabe auch nicht in Frage käme.

  6. PH!L sagt

    am 30. November 2009 @ 14:03

    habs mal ausprobiert und scheint soweit einiges an performance auf meiner testseite zu bringen….genau das was ich gesucht habe. vielen dank

  7. GhostGambler sagt

    am 1. Dezember 2009 @ 10:51

    http://www.mysqlperformanceblog.com/2006/09/01/order-by-limit-performance-optimization/
    siehe: „Beware of large LIMIT“

    Als Gedankenanstoß:
    http://edrackham.com/featured/get-random-row-with-mysql-without-order-by-rand/
    oder auch die Frage „Muss der Zufall tatsächlich 100%tig zufällig sein?“.

  8. Jan sagt

    am 1. Dezember 2009 @ 11:15

    Die Methode von edrackham.com hatte ich ja in einem meiner früheren Artikel zu diesem Thema auch beschrieben. Schwierig wird dieser Ansatz aber vor allem dann, wenn man mehrere Datensätze selektieren möchte und nicht nur einen.

  9. GhostGambler sagt

    am 1. Dezember 2009 @ 12:33

    Man kann diese SELECT Statements genauso mit UNION verknüpfen wie deine.

  10. Christian Hünniger sagt

    am 1. Dezember 2009 @ 18:16

    TOP!

    Aber eins wäre noch anzupassen:

    SELECT COUNT(*) …

    — id oder der name einer spalte
    SELECT COUNT(id) …

  11. Jan sagt

    am 1. Dezember 2009 @ 18:21

    @Christian:
    Bei COUNT(*) kann MySQL die Tabellen-internen Statistiken bzw. einen Index benutzen, um die Anzahl zu bestimmen.

    COUNT(id) ist meist langsamer, weil es an verschiedene Bedingungen geknüpft ist. Hier dürfen NULL-Werte nicht mitgezählt werden, die Spalte sollte im Index enthalten sein usw.

    Das ganze habe in diesem Beitrag schon mal beschrieben.

  12. Christian Hünniger sagt

    am 4. Dezember 2009 @ 08:16

    @jan

    ok, hört sich plausibel an, aber hat die ID, wenn vorhanden (war auch nur ein beispiel), immer einen Index?

    Hatte das mit den NULL Werten übersehen :-)

    Gruß Christian und weiter so :-)

  13. MySQL, SEO und Wordpress - mysql,seo,wordpress,templates - Webworking sagt

    am 4. Dezember 2009 @ 10:03

    [...] Mit MySQL zufälligen Datensatz selektieren Ich glaube ich habs an der einen oder anderen Stelle bereits erwähnt: ORDER BY RAND() ist aus dem Reich des Bösen! :) Um genau zu sein: es ist die Performance-Bremse schlechthin! Wie ihr das zufällige Auslesen von Datensätzen trotzdem hin bekommt erklärt euch Jan. [...]

  14. Tobias sagt

    am 11. Januar 2010 @ 09:13

    Ich habe gerade vielleicht noch eine intresante Lösung gefunden um mehrende Einträge zufällig zu erhalten.
    Lohnt sich aber nur für Leute die eine ganze Liste durcheinander haben wollen (in mein Fall 10-20 Einträge)

    statt der while schleife:
    $rands = range(0, $num – 1);
    shuffle($rands);

    und statt dem foreach:
    do
    {
    $rand = current($rands);
    ….
    }
    while(next($rands) !== false);

  15. Jan sagt

    am 11. Januar 2010 @ 09:32

    @Tobias: Damit erhälst Du zwar eine Liste von durcheinander gewürfelten Zahlen, aber Du weißt ja im Voraus nicht, welche IDs es in der Tabelle überhaupt gibt. Und zuerst alle auszulesen, ist bei größeren Tabellen auch keine Lösung.

  16. Tobias sagt

    am 11. Januar 2010 @ 15:42

    @Jan: Wieso soll ich denn die IDs vorher raussuchen?
    Ich glaube hier ist ein kleines Missverständnis.
    Wie geschrieben, passe ich nur 2 Blöcke der "Nun möchte man aber manchmal mehrere Datensätze zufällig selektieren" Funktion an. Also die DB selects für "COUNT(*)" und nachher das "LIMIT $rand,1 " lasse ich unverändert.

    Also:
    $num = (SELECT COUNT(*) …)

    $rands = range(0, $num – 1);
    shuffle($rands);

    do
    {
    $rand = current($rands);
    $queryparts[] = "SELECT spalte
    FROM tabelle
    WHERE andereSpalte='123'
    LIMIT ".$rand.",1";
    }
    while(next($rands) !== false);

    ….

    ich hoffe es ist jetzt besser zu sehen was ich meine / was ich gemacht habe.

    Hab gerade keine Zeit den kompletten Src zu schreiben.

  17. Patrick sagt

    am 11. März 2010 @ 19:47

    Das war mal wieder ein toller Beitrag!

    Interessant wäre es auch einmal zu vergleichen, was schneller ist, wenn man wirklich alle 6000 Datensätze haben möchte. (Ich vermute, dass sich deine Methode nur lohnt wenn gewünschte Datensatzanzahl sehr viel kleiner ist, als deine 6000 Datensätze)

    Grüße Patrick

  18. Maik sagt

    am 21. März 2010 @ 18:30

    Ich danke dir für diesen super Beitrag, mit deiner Hilfe konnte ich die ewig leidige Performance Bremse in meinem Script beseitigen. :)

    Viele Grüße
    Maik

  19. r sagt

    am 25. Januar 2012 @ 13:56

    nur ein SELECT

    $r = nysql_query($r);
    $n = mysql_num_rows($r);
    if($n < 1) return false;

    $i = mt_rand(0,$n-1);
    mysql_data_seek($r,$i);
    return mysql_fetch_row($r);

    für mehrer einfach ein are von $i anlegen und sortieren und dann mehrfach den lese pointer setzen.

Komentar RSS · TrackBack URI

Hinterlasse einen Kommentar

Name: (erforderlich)

eMail: (erforderlich)

Website:

Kommentar: