Federico Razzoli

Letztes Update am 8. Dezember 2019

Zufällige Zeilen in zufälliger Reihenfolge aus einer relationalen Datenbank zurückzugeben ist ein sehr schwieriges Problem. In diesem Artikel werden wir ein Antipattern sehen, wir werden diskutieren, warum dieses Problem so schwer ist, und wir werden einige unvollkommene Lösungen untersuchen.

UPDATE: Einige DBMSs unterstützen TABLESAMPLE. Ich habe es nicht erwähnt, weil ich bis heute nur die SQL Server-Implementierung kannte, und ich halte sie nicht für geeignet, um beliebige Zeilen zu extrahieren (ich werde erklären, warum). Aber nach einer Frage von Daniël van Eeden auf Facebook habe ich einige Nachforschungen angestellt und entdeckt, dass die PostgreSQL-Implementierung viel besser geeignet sein könnte. Ich werde mehr darüber lesen und es ausprobieren, und dann werde ich wahrscheinlich einen zweiten Artikel darüber schreiben. Wie auch immer, MySQL und MariaDB unterstützen nicht TABLESAMPLE.

Der falsche Weg: ORDER BY RAND()

Viele Entwickler denken, dass sie es so machen können:

SELECT some_columns FROM some_table ORDER BY RAND() LIMIT 10;

Dies ist die einzige Abfrage, die genau das tut, was erwartet wird. Wenn die Funktion RAND() zuverlässig zufällig ist, gibt sie eine zufällige Menge von Zeilen zurück, wobei jede Zeile die gleiche Chance hat, zurückgegeben zu werden.

Das Problem ist, wie es unter der Haube funktioniert. Um Zufallswerte anzuordnen, muss man sie zuerst erstellen. Um einen Zufallswert für jede Zeile in einer Tabelle zu erzeugen, muss ein DBMS jede Zeile lesen. Das DBMS führt also einen zweistufigen Vorgang durch:

1. Kopieren der Zeilen plus Zufallswert in eine temporäre Tabelle, die sich hoffentlich im Speicher befindet;
2. Ordnen Sie die Zeilen in der temporären Tabelle.

Beachten Sie dieses Detail: hoffentlich im Speicher. Je nach DBMS kann es Gründe geben, warum die Tabelle auf der Festplatte erstellt werden muss. Normalerweise geschieht dies, wenn die Tabelle zu groß ist. Alte MySQL-Versionen erstellen auch temporäre Tabellen auf der Festplatte, wenn sie TEXT oder BLOB Spalten enthalten.

Wenn die Tabelle groß ist, ist dies natürlich ein langsamer Vorgang, der viele Ressourcen verbraucht.

Warum bieten relationale DBMS keine eingebaute Möglichkeit, zufällige Zeilen zurückzugeben?

Relationale Datenbanken basieren auf einem Zweig der Mathematik, der relationalen Algebra genannt wird. Sie basiert auf der Logik, weil sie sich mit wahr/falsch-Prädikaten befasst; und sie ähnelt der Mengenlehre, auch wenn eine Relation etwas Komplexeres ist als eine Menge, und selbst die Betrachtung als Tabelle ist mathematisch nicht korrekt. Dieser Artikel ist ein schönes Beispiel für das, was ich meine, aber es gibt noch komplexere Argumente.

Obwohl SQL keine präzise Implementierung des relationalen Modells ist, wird seine Algebra als Referenz verwendet. Wie alle Zweige der Mathematik verfügt sie über einen wohldefinierten Satz von Operationen. Zufällige Tupel aus einer Relation zu erhalten, gehört definitiv nicht dazu.

Diese Antwort klingt ein bisschen zu theoretisch, oder? ORDER BY und Tabellen ohne Primärschlüssel verletzen ebenfalls die Regeln der relationalen Algebra, aber SQL unterstützt sie.

Doch für Datenbanken ist Geschwindigkeit entscheidend. Relationale DBMS sind darauf ausgelegt, relationale Operationen sehr schnell durchzuführen. Es liegt auf der Hand, dass eine Datenstruktur, die für bestimmte Operationen optimiert ist, nicht für andere Operationen optimiert ist. So sind relationale DBMS nicht für zufällige Suchvorgänge optimiert.

Es sollte offensichtlich sein, dass es langsam wäre, eine Schleife über die Zeilen zu ziehen, um einige von ihnen zufällig auszuwählen. Theoretisch wäre das Lesen einer zufälligen Zeile mit Hilfe eines Index genauso schnell wie das Auffinden einer Zeile anhand des Primärschlüsselwerts. Aber dann hätten verschiedene Zeilen unterschiedliche Chancen, ausgewählt zu werden.

Das obige Bild stammt aus dem GitHub-Repository von Jeremy Cole, innodb_diagrams. Früher oder später sollte ich über seine Projekte zur Analyse von InnoDB-Datenstrukturen schreiben.

Was hier wichtig ist, ist, dass ein Index ein Baum ist, dessen Knoten Speicherseiten sind. Die Blattknoten enthalten die eigentlichen Daten; die oberen Ebenen enthalten nur Informationen, die benötigt werden, um den kürzesten Weg zum gewünschten Blattknoten zu wählen. Details sind in diesem Zusammenhang nicht wichtig.

Das DBMS könnte theoretisch eine zufällige Seite auswählen, indem es eine Reihe von Zufallsentscheidungen trifft: Gehe ich nach links oder nach rechts? Aber dann enthalten die Blattseiten eine variable Anzahl von Zeilen. Sie könnten sogar leer sein. Somit hätten verschiedene Zeilen unterschiedliche Chancen, ausgewählt zu werden.

Das Ergebnis liegt eindeutig außerhalb der beabsichtigten Anwendungsfälle von DBMS; und es kann langsam oder falsch sein, je nachdem, ob ein Index verwendet wird oder nicht. Die DBMS haben zu Recht beschlossen, diese Funktion nicht zu implementieren.

Einige Lösungen

Es gibt keine perfekten Lösungen. Es gibt Lösungen, die akzeptabel sein können, aber Nachteile haben. Wir sollten uns von Fall zu Fall für eine entscheiden.

Zufällig aus einem Bereich auswählen

Diese Lösung ist auf Tabellen anwendbar, die einen autoinkrementellen Primärschlüssel haben. Sie ist am einfachsten zu implementieren, aber ein „fragmentierter“ Primärschlüssel verursacht Probleme.

Sie besteht darin, die minimale und die maximale ID zu überprüfen und eine Zufallszahl in diesem Bereich zu erzeugen:

Nicht, dass Abfragen mit MIN() und MAX() auf einem beliebigen Index, ohne andere Klauseln, sehr schnell sind.

Das Ergebnis ist eine wirklich zufällige Zeile. Um mehr als eine Zeile auszuwählen, können wir diese Abfrage mehrfach wiederholen. Daraus ergeben sich zwei Nachteile:

• Wenn dieser Vorgang häufig durchgeführt wird, könnte diese Abfrage sehr oft ausgeführt werden.
• Es gibt keine Garantie, dass dieselbe Zeile nicht mehrfach ausgewählt wird. Wenn dies geschieht, kann die Anwendung die Abfrage erneut versuchen. Wenn die Tabelle groß ist, ist dieses Ereignis selten und kann ignoriert werden – es sei denn, die RAND()Funktion ist unzuverlässig. Bei kleinen Tabellen kann dies jedoch ein Problem darstellen.

Außerdem kann ein Primärschlüssel Löcher haben – mit anderen Worten, einige Zahlen können fehlen. Dies ist auf Löschungen und fehlgeschlagene Transaktionen zurückzuführen. Zahlen, die niedriger als das Maximum sind, werden nicht wiederverwendet. Um dieses Problem zu umgehen, können wir zwei Techniken anwenden.

Verwendung von >=

Wenn wir den Operator >= in der WHERE-Klausel verwenden, wird die Abfrage immer eine Zeile zurückgeben. Wenn die erzeugte Zahl nicht vorhanden ist, wird die nächste verwendet. Das bedeutet jedoch, dass Werte, die unmittelbar nach einem Loch liegen, eine größere Chance haben, ausgewählt zu werden. Je größer die Lücke ist, desto größer ist die Chance, ausgewählt zu werden.

Sie denken vielleicht, dass Sie sich nicht darum kümmern sollten, und Sie haben wahrscheinlich recht. Aber bevor Sie eine endgültige Entscheidung treffen, sollten Sie die Möglichkeit eines großen Lochs in Betracht ziehen.

Versuchen Sie es auf die harte Tour

Wenn die Abfrage keine Zeilen zurückgibt, können wir es einfach erneut versuchen. Bei großen Tabellen mit nur ein paar kleinen Löchern ist das völlig in Ordnung. Aber bei großen Löchern mit vielen Löchern oder großen Löchern könnte diese Technik zu viele Ressourcen verbrauchen.

Bitte seien Sie in dieser Hinsicht nicht zu paranoid. Rechnen Sie einfach ein wenig nach. Wie hoch ist der Anteil der fehlenden Werte in Ihrer Tabelle? Das sagt Ihnen, wie oft die Abfrage im Durchschnitt wiederholt wird.

Mehrere Zeilen auswählen

Um mehrere Zeilen mit dieser Technik auszuwählen, können wir:

• die Abfrage mehrmals wiederholen;
• oder für eine bessere Leistung den Operator >= verwenden und einen LIMIT größer als eins einsetzen. Dadurch werden die Ergebnisse jedoch viel weniger zufällig.

Verlagerung der Zufallsauswahl auf die Anwendung

In ihrer einfachsten Form besteht diese Technik in der zufälligen Auswahl eines Blocks von zusammenhängenden IDs. Die Anwendung wählt nach dem Zufallsprinzip aus, welche sie verwenden will, und wählt dann die passenden Zeilen aus.

Angenommen, Sie wollen aus Blöcken von 1000 Werten wählen:

Je größer der Block, desto mehr Ressourcen verbrauchen Sie, desto zufälliger ist das Ergebnis. Die Anwendung ist dafür verantwortlich, zufällige, eindeutige, existierende IDs aus den Blöcken auszuwählen, so dass es nie nötig sein sollte, eine Abfrage zu wiederholen.

Die MOD-Variante

Ein Problem bei dieser Technik ist, dass die Zeilen aus demselben Block zusammenhängender IDs zurückgegeben werden. Das kann durchaus akzeptabel sein, besonders wenn der Block groß ist. Ist dies jedoch nicht der Fall, könnten wir eine gewisse Komplexität hinzufügen, um einen Block mit nicht zusammenhängenden Zeilen auszuwählen.

Die Idee dieser Variante besteht darin:

• Makro-Blöcke mit größtenteils nicht zusammenhängenden Zeilen zu definieren;
• nach dem Zufallsprinzip einen Makro-Block auszuwählen;
• einen Block daraus zurückzugeben.

Dazu können wir den Modulus der ID berechnen und ihn zur Auswahl zufälliger Ergebnisse verwenden. Zum Beispiel können wir eine indizierte virtuelle Spalte mit einem Ausdruck wie (id MOD 4) definieren. Jede Zeile wird einen Wert zwischen 0 und 3 haben. Selbst wenn es Löcher gibt, werden die Zeilen aus diesen Makroblöcken meistens nicht zusammenhängend sein und sie sollten ungefähr die gleiche Anzahl haben.

Die Anwendung sollte eine Zufallszahl zwischen 0 und 3 erzeugen. Dann werden Blöcke aus diesen Makroblöcken ausgewählt:

SET @block_size := 1000;SELECT id FROM some_table WHERE id_mod = FLOOR(RAND() * 3) ORDER BY id LIMIT @block_size;

Eine ähnliche Möglichkeit, diese Idee umzusetzen, ist die Verwendung von Partitionen, wobei die Partitionsfunktion der Modulus der ID ist. Ich würde dies nur vorschlagen, wenn die Tabelle aus anderen Gründen von einer Partitionierung profitieren würde.

Auswahl einer Technik

Die Blocktechniken führen mehr Abfragen durch als die erste mit dem >=-Operator, und das Ergebnis könnte besser sein oder nicht. Im Vergleich zur Wiederholungsvariante können mehr oder weniger Abfragen ausgeführt werden, und das Ergebnis ist schlechter.

Im Allgemeinen sind die Blocktechniken besser, wenn wir Löcher im Primärschlüssel haben.

Zwischenspeichern von Zufallsreihen

Die vorherigen Methoden sind ein Kompromiss: Leistung gegen bessere Zufälligkeit, wobei schnellere Lösungen auch komplexer zu implementieren sind. Solange wir nicht das ORDER BY RAND()-Antipattern verwenden, sollte die Auswahl zufälliger Reihen keine Leistungsprobleme verursachen. Aber was, wenn doch?

Wir könnten einige zufällig sortierte IDs zwischenspeichern, die wir mit einer der vorherigen Lösungen erhalten haben. Wir könnten eine Abfrage wie die folgende verwenden (MySQL-Syntax):

Wir könnten die Reihen in aufsteigender oder absteigender Reihenfolge verwenden, nach dem Zufallsprinzip. Oder die Anwendung könnte sie mischen.

Probleme:

• Wenn ein Element hinzugefügt wird, sollten wir zufällig wählen, ob es in eine Serie eingefügt werden muss und ein zufälliges Element ersetzen.
• Wenn ein Element gelöscht wird, sollten wir es aus allen Serien löschen. Es sollte durch ein anderes zufälliges Element ersetzt werden.
• Wir sollten regelmäßig die ältesten Serien löschen und durch neue ersetzen, um die Zufälligkeit in der Benutzererfahrung zu verbessern.

Schlussfolgerungen

Wie immer, bitte kommentieren Sie und lassen Sie mich wissen, wenn Sie einen Fehler in diesem Artikel entdecken, wenn Sie mit etwas nicht einverstanden sind, wenn Sie mir Ihre persönlichen Erfahrungen mitteilen oder wenn Sie weitere Ideen hinzufügen möchten.