Alternativen zu MySQLs "ORDER BY RAND()"

Das Problem

Wer kennt dieses Problem nicht - man möchte eigentlich nur eine oder mehrere zufällige Einträge aus einer MySQL-Tabelle haben. Sicherlich denken die Leser dieses Blogs sofort an "ORDER BY RAND()". Auf den ersten Blick eine schöne Lösung - möchte man denken? Einfach alle gewünschten Felder im SELECT angebem, vielleicht ein paar JOINs und dann nur noch ein ORDER BY RAND() und ein LIMIT?

Für kleine Anwendungen und auf kleine Tabellen angewendet mag dies höchstens als Notlösung akzeptabel sein! Doch was macht man. wenn nicht nur ein paar tausend sondern vielleicht zehntausend, hunderttausend oder gar ein paar Millionen Zeilen in der Tabelle sind?

Mit genau dieser Frage habe ich mich im Rahmen der Entwicklung von rhCMS 2.0 befasst. Man merkt schnell, dass die Abfrage an ihre Grenzen stößt und in keinster Weise akzeptabel ist, wenn es darum geht, sie in eine Webseite einzubinden.

Dabei scheint das Problem so einfach: Das Verlangen nach ein paar zufällig angezeigten Datensätzen ist hoch. Ein paar Bilder hier - ein paar Benutzer dort und hier noch ein paar Banner. Schnell kommen einige Abfragen zusammen. Was gerade auf viel besuchten Seiten - wie man anfangs nicht vermuten mag - ein Problem werden kann. Doch warum?

Problem-Analyse

Zur Klärung dieser Frage muss man sich etwas mit MySQL auskennen und verstehen, was bei so einer "ORDER BY RAND()"-Abfrage passiert.

MySQL wird zuerst einmal alle Daten sammeln. Im Anschluss wird das ganze dann sortiert. Dafür wird dann ein Index oder wie bei der Option RAND() eine temporäre Tabelle verwendet. Womit wir auch schon bei unserem Übeltäter wären: Der temporären Tabelle. In ihr werden alle unsere Datensätze gespeichert und entsprechend sortiert. Und dort geht die Abfrage dann kaputt.

Lösungs-Ansätze

Doch wie kann man dieses Problem umgehen? Genau das habe ich mich gefragt und habe mich auf die Suche gemacht und bin zuerst einmal auf eine PHP-Lösung gestoßen. Die Idee ist bei Betrachtung recht simpel:

Eine PHP-Lösung

Man fragt die Gesamtzahl der Zeilen ab:

SELECT COUNT(*) FROM table

<?php
  $random_id = mt_rand(1, [ COUNT(*) - Ergebnis ]);
?>

SELECT colA, colB FROM table WHERE idCol = ...

1. Was ist, wenn es den Datensatz nicht gibt?
2. Was ist, wenn man mehr als einen Datensatz benötigt?

Die erste Frage lässt sich leicht beantworten: Man muss so lange eine Abfrage machen, bis ein passender Datensatz zurück gegeben wird. Doch wie verhält es sich mit mehreren Datensätzen? Die einfachste Variante erscheint wohl, einfach mehrmals das gleiche auszuführen (und die Gesamt-Anzahl der Datensätze natürlich nur einmal zu speichern). Dies klingt auf den ersten Blick auch recht vernünftig und scheint besser als die reine MySQL-Variante zu sein. Doch war auch dies für mich nicht befriedigend.

Ich suchte also weiter - gab es die perfekte oder ideale Lösung für eine solche Abfrage? Ich stieß schließlich auf eine reine MySQL-Lösung. Die Idee so einfach wie folgt:

MySQL-Lösung

Man erstellt eine MySQL Prozedur, die eine temporäre Tabelle mit Datensätzen füllt, die aus zufälligen IDs besteht und gibt diese dem Benutzer zurück. Doch auch hier gab es ein Problem: Was ist, wenn die ID nicht vorhanden ist und was ist, wenn zufällig eine ID zwei mal auftaucht?

Schließlich blieb es doch an mir hängen und daher habe ich diese kleine MySQL-Prozedur zum Abfragen beliebig vieler, zufälligen IDs einer Tabelle entwickelt, die auf der gleichen Idee basiert.

1. Erstelle eine temporäre Tabelle zur Zwischenspeicherung der IDs und füge sie zu einem UNIQUE Key hinzu.
2. Frage die maximale ID ab
3. Fülle die Tabelle mit einer bestimmten Anzahl von Datensätzen.
4. Gebe die Datensätze zurück

Damit war nun die Lösung das Problems fertig:

DROP PROCEDURE IF EXISTS proc_get_random_post_id;
 
DELIMITER //
 
CREATE PROCEDURE proc_get_random_post_id (IN cnt INT)
BEGIN
  DECLARE max_id INTEGER;
  
  DECLARE EXIT HANDLER FOR SQLEXCEPTION
  BEGIN
    CALL proc_get_random_post_id(cnt);
  END;
  
  IF cnt >= 1 THEN
    DROP TEMPORARY TABLE IF EXISTS random;
    CREATE TEMPORARY TABLE random ( post_id INTEGER(11) unsigned, UNIQUE KEY(post_id) );
    
    insert_loop : LOOP
      IF cnt < 1 THEN
        LEAVE insert_loop;
      END IF;
      
      SELECT MAX(post_id) FROM posts INTO max_id;
      
      INSERT INTO random
        SELECT
         p.post_id
        FROM
          posts AS p
        JOIN
          (SELECT (RAND() *  max_id) AS random_id) AS r
        WHERE
          p.post_id >= r.random_id
        ORDER BY
          p.post_id
        LIMIT
          1;
      
      SET cnt = cnt - 1;
    END LOOP insert_loop;
    
    SELECT post_id FROM random;
  END IF;
END//
 
DELIMITER ;

Dies soll nun die heilige Lösung sein? So etwas kompliziertes soll einem so viel Ärger ersparen? Auch ich habe anfangs gezweifelt. Doch ein paar kurze Tests brachten das eindeutige Ergebnis. Das einzige Problem, was ein fleißiger Tester nun habe könnte ist, dass er keine Prozeduren erstellen darf. Doch meiner Meinung nach sollte dies entweder nicht verboten sein. Denn jemand der sich mit so einem Problem befasst wird doch sicherlich entsprechenden Zugriff auf einen MySQL-Server haben, oder?

Ein weiteres Problem könnte eine Fehlermeldung der Rekursion sein. Diese tritt auf, wenn die Standard-Einstellung auf 0 ist. Dann ist ein rekursiver Aufruf verboten und man muss ihn manuell setzen:

SET max_sp_resursion_depth = 2;

Hinweis: Die 2 entspricht anschaulich dargestellt den Kollisionen. Wenn ihr eine große Tabelle habt, solltet ihr einen kleinen Wert nehmen als bei einer kleinen Tabelle mit weniger Zeilen.

Bei nur wenigen Zeilen (~ 25000) war die Prozedur minimal schneller. Bei etwa 230.000 Zeilen war die Prozedur um etwa den Faktor 7-10 schneller. Dann stand der wirkliche Test an: Ich erstelle eine Prozedur für zufällige IDs eines Beitrags aus dem Forum - das Ergebnis war überraschend.
Der erste Aufruf dauert mit folgendem Code rund 72 Sekunden lang - dabei wurden etwa 4 einhalb Millionen Zeilen durchsucht:

SELECT post_id FROM posts ORDER BY RAND() LIMIT 20

mysql> SELECT post_id FROM posts ORDER BY RAND() LIMIT 20;
+---------+
| post_id |
+---------+
| 2013034 |
| 3579000 |
| 3316421 |
| 4093120 |
| 2359496 |
| 1885511 |
| 3835027 |
| 1046873 |
| 1185652 |
| 4331911 |
| 4890819 |
|  240006 |
| 2437795 |
| 1712680 |
|  868551 |
| 2096902 |
| 3083704 |
|  856132 |
| 2190370 |
| 4862958 |
+---------+
20 rows in set (52.66 sec)

Beim zweiten mal immerhin noch rund 35 Sekunden. Beim dritten, vierten, ... mal varierte die Zeit dann stark, lag jedoch im Durchschnitt bei etwa 25 Sekunden.

Hinweis: Bei Abfrage von einer ID zusammen mit einer anderen Spalte (in diesem Fall eines DATETIME-Feldes) war die Abfrage deutlich schneller und lag im Durchschnitt bei etwa 5 Sekunden.

CALL proc_get_random_post_id(20);

mysql> CALL proc_get_random_post_id(20);
  +---------+
  | post_id |
  +---------+
  |  354319 |
  |  436352 |
  |  762503 |
  |  924832 |
  | 1395933 |
  | 1515758 |
  | 1633515 |
  | 1731376 |
  | 1789180 |
  | 2512748 |
  | 2549002 |
  | 2854479 |
  | 2863860 |
  | 3103881 |
  | 3233293 |
  | 4337101 |
  | 4560893 |
  | 4596010 |
  | 4609112 |
  | 4960802 |
  +---------+
  20 rows in set (0.04 sec)

Dieser simple, kleine Aufruf, der nichts anderers macht, als die Prozedur im Hintergrund aufzurufen, brauchte dagegen bei jedem Aufruf (auch beim Ersten) im Durchschnitt nur rund 0,034 Sekunden. Die Zeit bleibt dabei unverändert, wenn man noch weitere Felder aus dem Datensatz abfragt.

Diese noch kleine Tabelle zeigt also, dass schon bei einigen Millionen Zeilen ein gewaltiger Unterschied zwischen diesen beiden Möglichkeiten besteht. Die Prozedur ist selbstverständlich beliebig erweiterbar und kann für alle Bedüfnisse angepasst werden.

Eine weitere PHP-Lösung

Auf Anfrage habe ich mir zu dem Prozedur-Problem Gedanken gemacht. Und habe die reine MySQL-Variante auf eine PHP-Klasse reduziert, die im Grunde das gleiche macht. Auch hier zeigten einige Performance-Tests, dass diese Variante noch deutlich schneller ist, als eine ORDER BY RAND() Methode!

<?php
  /**
   * Default Random ID Class
   * 
   * @author Robert Hartung
   * @copyright www.rhcms.de, 2010
   */
   
  class randomIdList
  {
    /**
     * MySQLI instance
     * 
     * @var mysqli
     */
    
    protected $mysqli;
    
    /**
     * Maximum duplicate key errors
     * 
     * @var integer
     */
    
    private $max_errors = 10;
    
    /**
     * Random ID Count
     * 
     * @var integer
     */
    
    private $count;
    
    /**
     * Table to select from
     * 
     * @var string
     */
    
    private $table;
    
    /**
     * Column that contains the ID
     * 
     * @var string
     */
    
    private $column_id;
    
    /**
     * Constructor
     */
    
    public function __construct(mysqli $mysqli, $table, $column_id)
    {
      $this->mysqli = $mysqli;
      $this->table = $table;
      $this->column_id = $column_id;
    }
    
    /**
     * Returns a result set of random IDs
     * 
     * @param boolean $return Query for the results?
     * 
     * @return mysqli_result
     */
    
    public function getIDs($count, $return = true)
    {
      $this->count = $count;
      
      /* Do some preparing stuff */
      
      $this->mysqli->multi_query("DROP TEMPORARY TABLE IF EXISTS random;
      CREATE TEMPORARY TABLE random ( random_id INTEGER(11) unsigned, UNIQUE KEY(random_id) );
      SELECT @max_id := MAX(post_id) FROM pmcms_forum_posts");
      
      /* Fetch the results otherwise: Command out of sync error */
      
      while($this->mysqli->more_results())
      {
        $this->mysqli->next_result();
        $this->mysqli->use_result();
      }
      
      /* Prepare the statement so the query needs to be parsed only once! */
      
      $stmnt = $this->mysqli->prepare("INSERT INTO random
          SELECT
           ".$this->column_id."
          FROM
            ".$this->table." AS p
          JOIN
            (SELECT (RAND() * @max_id) AS random_id) AS r
          WHERE
            ".$this->column_id." >= r.random_id
          ORDER BY
            ".$this->column_id."
          LIMIT
            1");
      
      /* Get Random IDs */
      
      while($this->count > 0 && $this->max_errors > 0)
      {
         $stmnt->execute();
          
         /* if there was an error - go on */
         if($this->mysqli->errno === 1062)
         {
           $this->max_errors -= 1;
         }
         else
         {
           $this->count -= 1;
         }
      }
      
      /* If requested, return the result otherwise null*/
      
      if($return)
        return $this->mysqli->query("SELECT random_id FROM random");
      
      return null;
    }
  }
?>

Die Klasse erwartet im Konstruktur eine MySQLI Instanz (NULL nicht kontrolliert), sowie Tabellen- und Spaltenname. Über die Methode getIDs($count, [ $return = true ]) ist es nun mögliche eine bestimmte Anzahl an zufälligen IDs abzufragen. Dabei wird das gleiche wie auch im MySQL-Beispiel gemacht:

1. Eine Temporäre Tabelle erstellen
2. Maximum herausfinden
3. Zufällige IDs finden
4. IDs abfragen

Diese Objekt-Orientierte Lösung bietet noch einen weiteren Vorteil. Man kann dieses Verfahren schnell auf andere Tabellen ausweiten und braucht nicht ständig eine neue Prozedur zu erstellen, indem man die alte umschreibt. Man kann dadurch schnell eine eigene Klasse schreiben, die noch mehr bietet als nur nackte IDs:

<?php
  /**
   * Example Class for Posts
   * 
   * @author Robert Hartung
   * @copyright www.rhcms.de, 2010
   */
  
  final class randomPosts extends randomIdList
  {
    public function __construct(mysqli $mysqli)
    {
      parent::__construct($mysqli, 'pmcms_forum_posts', 'post_id');
    }
    
    /**
     * Returns a different result set
     * 
     * @return mysqli_result
     */
    
    public function getIDs($count)
    {
      parent::getIDs($count, false);
      
      return $this->mysqli->query("SELECT post_id FROM random JOIN pmcms_forum_posts ON post_id = random_id");
    }
    
    public function getRandomPosts($count)
    {
      parent::getIDs($count, false);
      
      return $this->mysqli->query("SELECT post_id, post_datetime, post_topic_id FROM random JOIN pmcms_forum_posts ON post_id = random_id");
    }
  }
?>

Diese Klassen könnten wir nun beispielsweise wie folgt ausführen:

<?php
  /** Basic */
  
  $random = new randomIdList($mysqli, 'pmcms_forum_posts', 'post_id');
  $qry_random = $random->getIDs(5);
  
  while($number = $qry_random->fetch_assoc())
  {
    /* Do something */
  }
  
  /** Basic 2 */
  
  $qry_random = $random->getIDs(10);
  
  while($number = $qry_random->fetch_assoc())
  {
    /* Do something */
  }
  
  /** Inherited class */
  
  $random = new randomPosts($mysqli);
  $qry_random = $random->getIDs(5);
  
  while($number = $qry_random->fetch_assoc())
  {
    /* Do something */
  }
  
  $qry_random = $random->getRandomPosts(5);
  
  while($post = $qry_random->fetch_assoc())
  {
    /* Do something */
  }
?>

Dies sollte einen kleinen Eindruck in die Möglichkeiten von Alternativen zu MySQLs ORDER BY RAND() geben. Ich würde mich über jegliche Art von Feedback sowie konstruktiver Kritik würde ich mich freuen!