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

Ich denke, die schnellste Lösung ist

select * from table where rand() <= .3

Hier ist der Grund, warum ich denke, dass das funktionieren sollte.

• Es wird eine Zufallszahl für jede Zeile erstellen. Die Zahl liegt zwischen 0 und 1
• Es überprüft, ob diese Zeile angezeigt werden soll, wenn die generierte Zahl zwischen 0 und .3 (30%) liegt.

Dies setzt voraus, dass rand() Zahlen in einer gleichmäßigen Verteilung generiert. Es ist der schnellste Weg, dies zu tun.

Ich habe gesehen, dass jemand diese Lösung empfohlen hat und ohne Beweis abgewiesen wurde.. hier ist, was ich dazu sagen würde -

• Dies ist O(n), aber keine Sortierung ist erforderlich, sodass es schneller ist als O(n lg n)

• mysql ist sehr fähig, für jede Zeile Zufallszahlen zu generieren. Versuchen Sie dies -

  select rand() from INFORMATION_SCHEMA.TABLES limit 10;

Da die betreffende Datenbank mySQL ist, ist dies die richtige Lösung.

Answer 2

Es gibt eine sehr interessante Diskussion zu diesem Thema hier: http://www.titov.net/2005/09/21/do-not-use-order-by-rand-or-how-to-get-random-rows-from-table/

Ich denke, dass ohne jegliche Annahmen über die Tabelle deine O(n lg n)-Lösung die beste ist. Obwohl mit einem guten Optimierer oder einer leicht unterschiedlichen Technik die von dir aufgelistete Abfrage vielleicht etwas besser sein könnte, O(m*n) wobei m die Anzahl der gewünschten zufälligen Zeilen ist, da es nicht unbedingt das gesamte große Array sortieren müsste, sondern nur m mal nach dem kleinsten Wert suchen könnte. Aber für die von dir geposteten Zahlen ist m sowieso größer als lg n.

Drei Annahmen, die wir ausprobieren könnten:

1. es gibt einen eindeutigen, indizierten Primärschlüssel in der Tabelle

2. die Anzahl der zufälligen Zeilen, die du auswählen möchtest (m), ist viel kleiner als die Anzahl der Zeilen in der Tabelle (n)

3. der eindeutige Primärschlüssel ist eine Ganzzahl, die von 1 bis n ohne Lücken reicht

Nur mit Annahmen 1 und 2 denke ich, dass dies in O(n) erledigt werden kann, obwohl du eine komplette Indexierung der Tabelle vornehmen musst, um Annahme 3 zu erfüllen, also ist es nicht unbedingt ein schnelles O(n). Wenn wir zusätzlich noch etwas Nettes über die Tabelle annehmen können, können wir die Aufgabe in O(m log m) lösen. Annahme 3 wäre eine einfache zusätzliche Eigenschaft, mit der man arbeiten könnte. Mit einem guten Zufallszahlengenerator, der garantiert, dass beim Generieren von m Zahlen in Folge keine Duplikate auftreten, wäre eine O(m)-Lösung möglich.

Unter Berücksichtigung der drei Annahmen besteht die grundlegende Idee darin, m eindeutige Zufallszahlen zwischen 1 und n zu generieren und dann die Zeilen mit diesen Schlüsseln aus der Tabelle auszuwählen. Ich habe gerade kein MySQL oder ähnliches vor mir, aber in leichter Pseudocode würde das etwas so aussehen:

create table RandomKeys (RandomKey int)
create table RandomKeysAttempt (RandomKey int)

-- generiere m zufällige Schlüssel zwischen 1 und n
für i = 1 bis m
  insert RandomKeysAttempt select rand()*n + 1

-- eliminiere Duplikate
insert RandomKeys select distinct RandomKey from RandomKeysAttempt

-- solange wir noch nicht genug haben, generiere weiter neue Schlüssel,
-- mit Glück (und m viel kleiner als n), wird dies nicht nötig sein
while count(RandomKeys) < m
  NextAttempt = rand()*n + 1
  if not exists (select * from RandomKeys where RandomKey = NextAttempt)
    insert RandomKeys select NextAttempt

-- bekomm unsere zufälligen Zeilen
select *
from RandomKeys r
join table t ON r.RandomKey = t.UniqueKey

Wenn du wirklich besorgt über die Effizienz bist, könntest du in Betracht ziehen, die Generierung der Zufallsschlüssel in einer Art prozeduraler Sprache zu machen und die Ergebnisse in die Datenbank einzufügen, da fast alles außer SQL wahrscheinlich besser für die Art von Schleifen und Zufallszahlenerzeugung geeignet wäre, die erforderlich sind.

Answer 3

Schneller als ORDER BY RAND()

Ich habe diese Methode getestet und festgestellt, dass sie viel schneller ist als ORDER BY RAND(), daher läuft sie in O(n) Zeit und das erstaunlich schnell.

Von http://technet.microsoft.com/en-us/library/ms189108%28v=sql.105%29.aspx:

Non-MSSQL Version -- Ich habe dies nicht getestet

SELECT * FROM Sales.SalesOrderDetail
WHERE 0.01 >= RAND()

MSSQL Version:

SELECT * FROM Sales.SalesOrderDetail
WHERE 0.01 >= CAST(CHECKSUM(NEWID(), SalesOrderID) & 0x7fffffff AS float) / CAST (0x7fffffff AS int)

Dadurch werden etwa ~1% der Datensätze ausgewählt. Wenn Sie also eine genaue Anzahl von Prozenten oder Datensätzen auswählen müssen, schätzen Sie Ihren Prozentsatz mit einem Sicherheitspuffer ab, und wählen Sie dann zufällig überschüssige Datensätze aus dem resultierenden Set aus, indem Sie die teurere Methode ORDER BY RAND() verwenden.

Noch schneller

Ich konnte diese Methode sogar noch weiter verbessern, weil ich einen bekanntermaßen indizierten Spaltenwertebereich hatte.

Zum Beispiel, wenn Sie eine indizierte Spalte mit gleichmäßig verteilten Ganzzahlen [0..max] haben, können Sie diese verwenden, um N kleine Intervalle zufällig auszuwählen. Führen Sie dies dynamisch in Ihrem Programm durch, um einen anderen Satz für jeden Abfrage-Durchlauf zu erhalten. Diese Teilmenge-Auswahl wird O(N) sein, was viele Größenordnungen kleiner als Ihr vollständiger Datensatz sein kann.

In meinem Test konnte ich die benötigte Zeit, um 20 (aus 20 Millionen) Beispielaufzeichnungen mit ORDER BY RAND() von 3 Minuten auf 0,0 Sekunden reduzieren!

Answer 4

Anscheinend gibt es in einigen Versionen von SQL ein TABLESAMPLE-Befehl, aber er ist nicht in allen SQL-Implementierungen vorhanden (insbesondere nicht in Redshift).

http://technet.microsoft.com/en-us/library/ms189108(v=sql.105).aspx

Answer 5

Nur verwenden Sie

WHERE RAND() < 0.1 

um 10% der Datensätze zu erhalten oder

WHERE RAND() < 0.01 

um 1% der Datensätze zu erhalten, usw.