Einfache Zufallsstichproben aus einer SQL-Datenbank

Question

Wie erstelle ich eine effiziente einfache Zufallsstichprobe in SQL? Die Datenbank in Frage läuft MySQL; meine Tabelle hat mindestens 200.000 Zeilen, und ich möchte eine einfache Zufallsstichprobe von etwa 10.000.

Die "offensichtliche" Antwort lautet:

SELECT * FROM table ORDER BY RAND() LIMIT 10000

Bei großen Tabellen ist das zu langsam: Es ruft RAND() für jede Zeile auf (was es bereits auf O(n) setzt) und sortiert sie, was es im besten Fall zu O(n lg n) macht. Gibt es einen Weg, dies schneller als O(n) zu tun?

Hinweis: Wie Andrew Mao in den Kommentaren anmerkt: Wenn Sie diesen Ansatz auf SQL Server verwenden, sollten Sie die T-SQL-Funktion NEWID() verwenden, da RAND() möglicherweise für alle Zeilen den gleichen Wert zurückgeben kann.

BEARBEITEN: 5 JAHRE SPÄTER

I ran into this problem again with a bigger table, and ended up using a version of @ignorant's solution, with two tweaks:

• Die Zeilen auf 2-5x meine gewünschte Stichprobengröße beprobten, um günstig ORDER BY RAND() auszuführen
• Das Ergebnis von RAND() in einer indexierten Spalte bei jedem Einfügen/Aktualisieren speichern. (Wenn Ihr Datensatz nicht sehr update-heavy ist, müssen Sie möglicherweise einen anderen Weg finden, um diese Spalte aktuell zu halten.)

Um eine Stichprobe von 1000 Elementen aus einer Tabelle zu nehmen, zähle ich die Zeilen und reduziere das Ergebnis auf durchschnittlich 10.000 Zeilen mit der frozen_rand-Spalte:

SELECT COUNT(*) FROM table; -- Verwenden Sie dies, um rand_low und rand_high zu bestimmen

  SELECT *
    FROM table
   WHERE frozen_rand BETWEEN %(rand_low)s AND %(rand_high)s
ORDER BY RAND() LIMIT 1000

(Meine tatsächliche Implementierung erfordert mehr Arbeit, um sicherzustellen, dass ich nicht unterprobe, und um rand_high manuell anzupassen, aber die Grundidee lautet "schneiden Sie Ihr N zufällig auf ein paar tausend herunter.")

Obwohl dabei einige Kompromisse gemacht werden, ermöglicht es mir, die Datenbank mithilfe eines Indexscans zu sampeln, bis sie klein genug ist, um erneut nach RAND() zu sortieren.

Answer 1

In bestimmten Dialekten wie Microsoft SQL Server, PostgreSQL und Oracle (aber nicht MySQL oder SQLite) können Sie etwas wie

select distinct top 10000 customer_id from nielsen.dbo.customer TABLESAMPLE (20000 rows) REPEATABLE (123);

Der Grund dafür, nicht einfach (10000 rows) ohne das top zu verwenden, ist, dass die TABLESAMPLE Logik Ihnen eine extrem ungenaue Anzahl von Zeilen gibt (manchmal 75% davon, manchmal 1,25% davon), daher möchten Sie mehr übersampeln und die genaue Anzahl auswählen, die Sie möchten. Das REPEATABLE (123) dient der Bereitstellung eines zufälligen Startwerts.

Answer 2

Ich möchte darauf hinweisen, dass all diese Lösungen anscheinend ohne Zurücklegen auswählen. Wenn Sie die oberen K-Zeilen aus einer zufälligen Sortierung auswählen oder mit einer Tabelle verbinden, die eindeutige Schlüssel in zufälliger Reihenfolge enthält, wird eine zufällige Stichprobe ohne Zurücklegen generiert.

Wenn Sie möchten, dass Ihre Stichprobe unabhängig ist, müssen Sie mit Zurücklegen auswählen. Siehe Frage 25451034 für ein Beispiel, wie Sie dies mit einem JOIN ähnlich der Lösung von Benutzer12861 tun können. Die Lösung ist für T-SQL geschrieben, aber das Konzept funktioniert in jeder SQL-Datenbank.

Answer 3

Versuchen

SELECT TOP 10000 * FROM tabelle ORDER BY NEWID()

Würde das die gewünschten Ergebnisse liefern, ohne zu kompliziert zu sein?

Answer 4

Ausgehend von der Beobachtung, dass wir die IDs einer Tabelle (z. B. Anzahl 5) basierend auf einem Satz abrufen können:

select *
from table_name
where _id in (4, 1, 2, 5, 3)

kann man zu dem Ergebnis kommen, dass wir, wenn wir den String "(4, 1, 2, 5, 3)" generieren könnten, einen effizienteren Weg hätten als RAND().

Zum Beispiel in Java:

ArrayList indices = new ArrayList(rowsCount);
for (int i = 0; i < rowsCount; i++) {
    indices.add(i);
}
Collections.shuffle(indices);
String inClause = indices.toString().replace('[', '(').replace(']', ')');

Wenn IDs Lücken haben, dann ist die ursprüngliche ArrayList indices das Ergebnis einer SQL-Abfrage zu den IDs.

Answer 5

Wenn Sie genau m Zeilen benötigen, generieren Sie realistischerweise Ihre Teilmengen von IDs außerhalb von SQL. Die meisten Methoden erfordern zu einem bestimmten Zeitpunkt die Auswahl des "n-ten" Eintrags, und SQL-Tabellen sind wirklich keine Arrays. Die Annahme, dass die Schlüssel in aufeinanderfolgender Reihenfolge sind, um einfach zufällige ints zwischen 1 und der Anzahl zu verbinden, ist auch schwierig zu erfüllen — zum Beispiel unterstützt MySQL dies nicht nativ, und die Sperrbedingungen sind... knifflig.

Hier ist eine O(max(n, m lg n))-Zeit- und O(n)-Platzlösung, die nur einfache BTREE-Schlüssel voraussetzt:

1. Holen Sie alle Werte der Schlüsselspalte der Datentabelle in beliebiger Reihenfolge in ein Array in Ihrer bevorzugten Skriptsprache in O(n)
2. Führen Sie ein Fisher-Yates-Shuffle durch, wobei nach m Vertauschungen gestoppt wird, und extrahieren Sie das Teilarray [0:m-1] in (m)
3. "Verknüpfen" Sie das Teilarray mit dem ursprünglichen Datensatz (z.B. SELECT ... WHERE id IN ()) in O(m lg n)

Jede Methode, die die zufällige Teilmengen außerhalb von SQL generiert, muss mindestens diese Komplexität haben. Der Join kann mit BTREE nicht schneller sein als O(m lg n) (daher sind O(m)-Behauptungen für die meisten Engines illusorisch) und das Shuffle ist auf mindestens n und m lg n begrenzt und hat keinen Einfluss auf das asymptotische Verhalten.

In Pythonischem Pseudocode:

ids = sql.query('SELECT id FROM t')
for i in range(m):
  r = int(random() * (len(ids) - i))
  ids[i], ids[i + r] = ids[i + r], ids[i]

results = sql.query('SELECT * FROM t WHERE id IN (%s)' % ', '.join(ids[0:m-1])