Wenn Sie das MySQL-Handbuch gelesen haben, haben Sie vielleicht ORDER BY RAND()gesehen, um die Zeilen zu randomisieren und mit LIMIT 1 nur eine der Zeilen zu nehmen.
SELECT name FROM random ORDER BY RAND() LIMIT 1;
Dieses Beispiel funktioniert gut und ist schnell, wenn Sie nur, sagen wir, 1000 Zeilen haben. Sobald Sie 10000 Zeilen haben, wird der Overhead beim Sortieren der Zeilen wichtig. Vergessen Sie nicht: Wir sortieren nur, um fast alle Zeilen wegzuwerfen.
Mir hat das nie gefallen. Und es gibt bessere Möglichkeiten, es zu tun. Ohne eine Sortierung.Solange wir einen numerischen Primärschlüssel haben.
Für die ersten Beispiele nehmen wir an, dass die be ID bei 1 beginnt und wir keine Lücken zwischen 1 und dem Maximalwert der ID haben.
Erste Idee: Wir können die ganze Arbeit vereinfachen, wenn wir die ID vorher in der Anwendung berechnen.
SELECT MAX(id) FROM random;## generate random id in applicationSELECT name FROM random WHERE id = <random-id>
Da MAX(id) == COUNT(id) ist, generieren wir einfach eine Zufallszahl zwischen1 und MAX(id) und übergeben sie an die Datenbank, um die zufällige Zeile abzurufen.
Das erste SELECT ist ein NO-OP und wird wegoptimiert. Das zweite ist ein eq_refgegen einen konstanten Wert und auch sehr schnell.
Verschiebe den Auftrag in die Datenbank
Aber ist es wirklich notwendig, dies in der Anwendung zu tun? Können wir es nicht in der Datenbank machen?
Ok, jetzt wissen wir, wie man die Zufalls-ID generiert, aber wie bekommt man die Zeile?
NO, NO, NO. Gehen Sie nicht diesen Weg. Der Grund: Das SELECT in der WHERE-Klausel wird für jede Zeile ausgeführt, die das äußere SELECT abruft, was je nach Glück zu 0 bis 4091 Zeilen führt.
Wir brauchen eine Möglichkeit, um sicherzustellen, dass die Zufalls-ID nur einmal generiert wird:
Das innere SELECT erzeugt eine konstante TEMPORÄRE Tabelle und der JOIN wählt nur eine einzige Zeile aus. Perfekt.
Keine Sortierung, keine Anwendung, die meisten Teile der Abfrage wegoptimiert.
Löcher zu den Zahlen hinzufügen
Um die letzte Lösung zu verallgemeinern, fügen wir die Möglichkeit von Löchern hinzu, wie bei DELETE Zeilen.
Der JOIN fügt nun alle IDs hinzu, die größer oder gleich unserem Zufallswert sind und wählt nur die direkte Nachbarschaft aus, wenn eine direkte Übereinstimmung nicht möglich ist. ABER sobald eine Zeile gefunden wurde, hören wir auf (die LIMIT 1). Und wir lesen die Zeilen entsprechend dem Index (ORDER BY id ASC). Da wir >= anstelle von = verwenden, können wir CEIL weglassen und erhalten das gleiche Ergebnis mit etwas weniger Arbeit.
Gleichverteilung
Sobald die Verteilung der IDs nicht mehr gleich ist, ist unsere Auswahl der Zeilen auch nicht mehr wirklich zufällig.
Die RAND-Funktion erzeugt IDs wie 9 bis 15, die alle dazu führen, dass die ID 16 als nächsthöhere Nummer ausgewählt wird.
Es gibt keine wirkliche Lösung für dieses Problem, aber deine Daten sind größtenteils konstant, du kannst eine Mapping-Tabelle hinzufügen, die die Zeilennummer auf die ID abbildet:
Die row_id ist nun wieder frei von Löchern und wir können unsere Zufallsabfrage erneut ausführen:
Nach 1000 Abfragen sehen wir wieder eine Gleichverteilung:
Beibehaltung der Löcher
Lassen Sie uns die Tabellen wie vorher nehmen:
Wenn wir etwas in r2 ändern, wollen wir, dass r2_equi_dist auch aktualisiert wird.
INSERT ist ganz einfach, bei DELETE müssen wir die equi-dist-id aktualisieren, um die lückenlose Einrichtung beizubehalten:
UPDATE ist wieder ganz einfach. Wir müssen nur die Fremdschlüssel-Beschränkung beibehalten:
Mehrere Zeilen auf einmal
Wenn Sie mehr als eine Zeile zurückbekommen wollen, können Sie das:
- die Abfrage mehrmals ausführen
- eine Stored Procedure schreiben, die die Abfrage ausführt und das Ergebnis in einer Temp-Tabelle speichert
- eine UNION machen
eine Stored Procedure
Stored Procedures bieten Ihnen die Strukturen, die Sie aus Ihrer bevorzugten Programmiersprache kennen:
- Schleifen
- Kontrollstrukturen
- Prozeduren
- …
Für diese Aufgabe brauchen wir nur eine LOOP:
Ich überlasse es dem Leser, die Probleme zu lösen:
- Verwenden Sie dynamisches SQL und geben Sie den Namen der temporären Tabelle an
- Verwenden Sie einen UNIQUE-Index für die Tabelle und fangen Sie die UNIQUE-Schlüsselverletzung ab, um die möglichen Duplikate in der Ergebnismenge zu entfernen
Leistung
Nun wollen wir mal sehen, was mit unserer Leistung passiert. Wir haben 3 verschiedene Abfragen, um unsere Probleme zu lösen.
- Q1. ORDER BY RAND()
- Q2. RAND() * MAX(ID)
- Q3. RAND() * MAX(ID) + ORDER BY ID
Q1 wird voraussichtlich N * log2(N) kosten, Q2 und Q3 sind nahezu konstant.
Um reale Werte zu erhalten, haben wir die Tabelle mit N Zeilen (eintausend bis eine Million) gefüllt und jede Abfrage 1000 Mal ausgeführt.