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 😉

Jan hat 152 BeitrÀge geschrieben

10 Kommentare zu “Performanter Zufall – gibts das?

  1. handyaner sagt:

    hallo

    habe nun mal das script angewendet. jedoch werden immer die selben ergebnisse angezeigt.

    obwohl, die auswahl bei 500 einträgen recht groß ist.

  2. FrÀnzchen sagt:

    Hi

    Der Zufall funktionert einwandfrei. Der Trigger allerdings nicht… Möglicherweise mache ich aber auch einfach nur einen Fehler!

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

    Die Tabelle „aufgaben“ besitzt zahlreiche Felder, darunter auch „ID“ (Primärschlüssel) und „rand_value“. Nun gebe ich die gesamte CREATE TRIGGER-Query in die SQL-Benutzerobefläche von phpMyAdmin ein. Ist doch korrekt oder?

    Allerdings bekomme ich den Fehler #1064, in dem die Syntax um „END“ als fehlerhaft beschrieben wird.

    Warum?

  3. FrÀnzchen sagt:

    Hey, also die Syntax ist jetzt korrekt und wird auch von phpMyAdmin angenommen, WENN das standardmäßige Semikolon als SQL-Zeilenbegrenzer in phpMyAdmin durch ein anderes Zeichen ersetzt wird (zum Beispiel ein Ausrufezeichen).

    Es ist ein wenig eigenartig, dass ausgerechnet ein Zeichen, was innerhalb einer SQL-Syntax eine große Rolle spielt, gleichzeitig als Zeilenbegrenzer eingesetzt wird….

    Naja… das soll dich nicht weiter stören! VIELEN DANK für deine kompetenten und stets freundlichen Tipps, die du hier verteilst! 🙂

  4. FrÀnzchen sagt:

    Hab mich doch ein bisschen früh gefreut… Bei jedem Versuch einen Datensatz einzufügen, sei es manuell oder per automatischen Import erhalte ich folgende Fehlermeldung:

    MySQL meldet:

    #1442 – Can’t update table ‚aufgaben‘ in stored function/trigger because it is already used by statement which invoked this stored function/trigger.

    Der Trigger besteht jetzt in dieser Form:

    DROP TRIGGER IF EXISTS `kompetenzcheck`.`rand_trigger`//
    CREATE TRIGGER `kompetenzcheck`.`rand_trigger` AFTER INSERT ON `kompetenzcheck`.`aufgaben`
    FOR EACH ROW BEGIN
    UPDATE aufgaben
    SET rand_value=RAND()
    WHERE ID=NEW.ID;
    END
    //

    Was ist noch falsch?

  5. FrÀnzchen sagt:

    achso… das heißt, ich kann innerhalb eines triggers keine zusätzliche abfrage auf die selbe tabelle starten, auf die sich auch der trigger bezieht…

    das ist natürlich ein bisschen bescheiden!

    die lösung wäre demnach eine extra tabelle zu erstellen, auf die ich dann in meiner „aufgaben“-tabelle verweise!

    mal sehen, ob’s klappt! ich meld mich wieder…

  6. FrÀnzchen sagt:

    Also, wer eine Lösung mithilfe eines TRIGGERS (besonders geeignet für Importe) anstrebt, macht das folgendermaßen:

    1. Anstelle des Feldes „rand_value“ in „tabelle“ wird eine neue Tabelle namens rand_table angelegt. Diese enthält zwei Felder, ein Feld „value“ (in dem alle Zufallswerte stehen) und ein Feld „tab_ID“ (welches die jeweiligen ID der Datensätze aus „tabelle“ enthält).

    2. Die Abfrage muss entsprechend angepasst werden:

    SELECT artikelname
    FROM rand_table, tabelle
    JOIN (
    SELECT RAND() AS random
    FROM tabelle
    LIMIT 1
    ) AS randTable
    WHERE rand_table.tab_ID = tabelle.ID
    ORDER BY ABS(rand_table.value-random)
    LIMIT 10;

    3. Der TRIGGER wird wie folgt angelegt:

    CREATE TRIGGER rand_trigger AFTER INSERT ON tabelle FOR EACH ROW INSERT INTO rand_table (tab_ID, value) VALUES ((SELECT MAX(ID) FROM tabelle), RAND())

    Der Grund für diesen etwas umständlichen Weg ist, dass ein Trigger nicht gleichzeitig auf eine Tabelle verweisen (AFTER INSERT ON tabelle) und die selbe Tabelle ändern (FOR EACH ROW UPDATE tabelle) darf.

    Mit freundlichen Grüßen
    Franz’l

  7. Marko sagt:

    Hi,

    bin grade durch google hier her gestolpert.
    Soweit feine Ausführungen. Danke.

    Wenn mal wieder jemand das Problem mit dem Trigger hat (auch über 1 Jahr nach dem letzten Eintrag 🙂 dann sollte er das so machen:

    Kurzform (ohne Test)
    create trigger trg_ZIELTABELLE
    before insert on ZIELTABELLE
    for each row
    SET NEW.RANDOM_SPALTE = rand();

    sollte funktionieren, ohne Zwischentabelle

Eine Antwort schreiben

Ihre E-Mail-Adresse wird nicht veröffentlicht. Benötigte Felder sind markiert mit *

You may use these HTML tags and attributes: <a href=""> <blockquote cite=""> <pre lang=""> <b> <strong> <i> <em>