Performanter Zufall – gibts das?

Ich möchte das Problem des zufälligen Selektierens von Datensätzen nochmal betrachten, da die im Beitrag Zufälligen Datensatz auswählen gefundene Lösung nicht wirklich akzeptabel ist, da sie nicht zufällig ist. Bei aller Performance, die diese Abfrage bringt, sollte doch die ursprüngliche Funktionalität nicht verloren gehen: Die Datensätze müssen zufällig sein und keinem Schema folgen.

In der Foren-Diskussion zu diesem Thema wurde von langleY ein weiterer Ansatz geliefert, der zwar mehr Speicher benötigt, aber letztlich zu meiner Empfehlung hinführt. Seinen Vorschlag in etwas abgewandelter Form möchte ich hier kurz erörtern:

Wir fügen der Tabelle, aus der die zufälligen Datensätze selektiert werden sollen, eine zusätzliche Spalte hinzu, in die wir Zufallszahlen schreiben. Da Zufallszahlen der Funktion RAND() in MySQL Dezimalzahlen zwischen 0 und 1 sind, können wir als Datentyp UNSIGNED FLOAT wählen. Außerdem legen wir fest, dass die Spalte NOT NULL ist. Ich habe der Spalte den Namen rand_value gegeben – dies nur, damit die SQL-Anweisungen weiter unten verständlich sind.

Über die Anweisung

UPDATE tabelle SET rand_value=RAND()

schreiben wir willkürlich Zufallszahlen in die Tabellenspalte – für jeden Datensatz wird eine generiert. Das ganze dauert bei meiner Tabelle mit etwa 250000 Einträgen etwa 3 Sekunden – das ist die Zeit, die bei einem SELECT * FROM tabelle ORDER BY RAND() ebenfalls benötigt würde – nur eben bei jeder Abfrage und nicht nur ein mal, wie mit der Zusatzspalte.

Nun war langleYs Vorschlag, dass man in einem SELECT-Statement noch eine Zufallszahl per RAND() erzeugt und etwa 10 mal so viele Werte selektiert, wie man im Endeffekt haben möchte. Diese Werte ordnet man dann wieder in einer zufälligen Reihenfolge an und wählt daraus 10 Datensätze aus. Als SQL:

SELECT *   FROM (     
SELECT *     
FROM tabelle     
WHERE rand_value >= RAND()     
LIMIT 100   )t   
ORDER BY RAND()   
LIMIT 10

Und das funktioniert auf den ersten Blick auch recht gut. Wenn wir aber genauer hinsehen, bleibt der Zufall auf der Strecke.
Das Problem ist vor allem die WHERE-Bedingung. Da die RAND()-Funktion auf lange Sicht gleichverteilte Werte ermittelt (jeder mögliche Wert kommt ungefähr genauso oft vor wie alle anderen), passiert es also genauso oft, dass wir kleinere als auch größere Zufallszahlen generieren. Wir gehen ebenfalls davon aus, dass die Zufallszahlen in der Spalte rand_value über alle Datensätze ebenfalls etwa gleichverteilt sind.
Nun gehen wir von einem Beispiel aus: Als Zufallszahl im SELECT-Statement wird 0,3 ermittelt. Das bedeutet, dass etwa 70 % der Datensätze größere Zufallszahlen in der Spalte rand_value haben und ca 30% kleinere Werte. Wenn wir nun aber in der WHERE-Bedingung alle Datensätze wählen, die größer (bzw. gleich) dieser Zufallszahl sind und keine zusätzliche Sortierung vornehmen sondern einfach die ersten 100 Werte nehmen, die in der Datenbank stehen, führt das dazu, dass sehr viele Datensätze vom Anfang der Tabelle selektiert würden und sehr wenige vom Ende. Je kleiner die Zufallszahl des SELECT-Statements ist, desto größer ist die Wahrscheinlichkeit, dass einfach die ersten 100 Werte genommen werden, die in der Tabelle stehen. Und man stelle sich vor, dass einer der ersten Datensätze der Tabelle eine sehr hohe Zufallszahl bekommt. Dann ist er fortan in den meisten Fällen unter den von der Subquery selektierten Datensätzen.

Der andere Schwachpunkt der Lösung ist eine sehr hohe Zufallszahl, beispielsweise 0,98. Es kann niemand garantieren, dass es tatsächlich noch 10 Datensätze gibt, deren Zufallszahlen in der Spalte rand_value über diesem Wert liegen. Und in vielen Anwendungsfällen möchte man ja beim Einsatz von LIMIT exakt die angegebene Anzahl von Datensätzen zurückerhalten, nur selten weniger.

Also hab ich mir mal etwas Zeit genommen und an einer besseren Lösung gefeilt. Ich bin zu dem Schluss gekommen, dass man an der Lösung über die Extra-Spalte nicht vorbeikommt, da sonst in der Praxis per RAND()*MAX(ID) keine gleichverteilten Werte zustandekämen. Warum nicht, in der Theorie funktioniert das doch? Korrekt. (Wen die stochastischen Zusammenhänge nicht interessieren, dem gestatte ich den folgenden Abschnitt zu überspringen ???? )
Theoretisch ist gegen den Ansatz nix einzuwenden, allerdings ist die Spalte ID oft eine AUTO-INCREMENT-Spalte und wenn man Datensätze löscht, entstehen Lücken (auch als Löcher bezeichnet). Das ist nicht weiter wild, allerdings muss man sich nur mal eine Tabelle mit 2 Datensätzen vorstellen: Der erste hat die ID 1 und der zweite die ID 6 (die 4 Datensätze dazwischen wurden irgendwann mal gelöscht). Der Erwartungswert der RAND()-Funktion ist 0,5 (ist wie beim Münzwurf, nur diesmal mit einer stetigen Zufallsgröße, sorry hier schon mal für die vielen Mathe-Fachbegriffe). Der Erwartungswert von randID = RAND()*MAX(ID) ist somit 0,5*6 = 3. Wenn wir nun eine WHERE-Bedingung einsetzen WHERE ID>=randID (von mir aus auch kleiner-gleich, das macht keinen Unterschied), müsste eigentlich an der 3 gesplittet werden. Alles was kleiner 3 ist, müsste zu Datensatz 1 führen, alles, was größer ist zur 6. Doch das ist nicht der Fall. Auch wenn RAND()*MAX(ID) 1,1 ergibt, wird Datensatz 6 selektiert. Man kann durch die Ungleichung 1>=RAND()*6 einfach ermitteln, dass nur bei Zufallszahlen, die kleiner bzw. gleich 1/6 sind, Datensatz 1 selektiert würde. Sicherlich ist das ein extremes Beispiel, aber es verdeutlicht hoffentlich, warum diese Version nichts mit Zufall zu tun hat, wenn Löcher vorhanden sind (was in der Praxis wahrscheinlich in den meisten Tabellen der Fall ist).

So, jetzt weiter für Datenbankleute (ok, die Mathematiker dürfen auch dabei bleiben). Wir haben oben bereits festgestellt, dass die Funktion RAND() gleichverteilt ist – sie weist also keine Löcher auf. Deshalb müssen wir allein mit ihr arbeiten und können uns nicht auf die Spalte ID beziehen. Ebenfalls ist die Arbeit mit der WHERE-Klausel gefährlich, da es damit immer passieren kann, dass zu wenig Datensätze übrig bleiben, die der Bedingung entsprechen.
Mir ist nun eine mögliche Lösung eingefallen: Wir arbeiten mit ORDER BY. Back to the roots sozusagen, aber statt ORDER BY RAND() gehen wir einen kleinen Umweg:

  
SELECT artikelname 
FROM tabelle
JOIN (    SELECT RAND() 
AS random     
FROM tabelle     
LIMIT 1  ) 
AS randTable  
ORDER BY ABS(rand_value-random)  
LIMIT 10;

Wir ermitteln nur eine einzige Zufallszahl in der SELECT-Abfrage und joinen diese auf alle Datensätze aus der Tabelle tabelle. Anschließend sortieren wir nach dem Abstand der in der Tabellenspalte rand_value gespeicherten Zufallszahlen zu der soeben berechneten Zufallszahl. Da die Zufallszahlen in rand_value über alle Datensätze gleichverteilt sowie unabhängig von der Reihenfolge der Datensätze selbst sind, und die Funktion RAND() ebenfalls gleichverteilt ist, erhalten wir auch wirklich zufällig gewählte Datensätze.

Mit der Query bekomme ich nach 0,65 Sekunden 10 zufällige Datensätze zurück. Ich denke diese Lösung ist durchaus eine gute Sache, zumal man durch den Einsatz eines Indizes die Geschwindigkeit noch weiter steigern könnte.
Nachteil dieser Lösung ist, dass alle INSERTs in der Anwendung angepasst werden müssten, da die zusätzlche Spalte rand_value initial mit einem Zufallswert gefüllt werden muss. Eine andere Möglichkeit das zu realisieren wäre ein Trigger (ab MySQL 5 möglich).

CREATE TRIGGER rand_trigger  
AFTER INSERT ON tabelle  
FOR EACH ROW BEGIN    
UPDATE tabelle     
SET rand_value=RAND()     
WHERE ID=NEW.ID;  END;

Ich hoffe es war nicht zu mathematisch, aber der Zufall ist nunmal ein mathematischer Sachverhalt. Falls Dinge nicht ausreichend erklärt wurden, bitte ich um ein kurzes Feedback in den Kommentaren! Vielen Dank, Vorlesung beendet ????