Wie nehme ich eine effiziente einfache Zufallsstichprobe in SQL? Auf der betreffenden Datenbank wird MySQL ausgeführt. Meine Tabelle besteht aus 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
Für große Tabellen ist das zu langsam: Es ruft RAND () für jede Zeile auf (wodurch es bereits auf O (n) gesetzt wird) und sortiert sie, sodass es bestenfalls O (n lg n) ist. Gibt es eine Möglichkeit, dies schneller als O (n) zu tun?
Hinweis : Wie Andrew Mao in den Kommentaren ausführt, sollten Sie bei Verwendung dieses Ansatzes unter SQL Server die T-SQL-Funktion NEWID () verwenden, da RAND () möglicherweise für alle Zeilen denselben Wert zurückgibt .
EDIT: 5 JAHRE SPÄTER
Ich bin mit einer größeren Tabelle erneut auf dieses Problem gestoßen und habe schließlich eine Version der Lösung von @ ignorant mit zwei Verbesserungen verwendet:
- Probieren Sie die Zeilen auf das 2-5-fache meiner gewünschten Stichprobengröße aus, um günstig nach Rang zu bestellen ()
- Speichern Sie das Ergebnis von RAND () bei jeder Einfügung / Aktualisierung in einer indizierten Spalte. (Wenn Ihr Datensatz nicht sehr aktualisierungsintensiv ist, müssen Sie möglicherweise einen anderen Weg finden, um diese Spalte aktuell zu halten.)
Um ein 1000-Elemente-Beispiel einer Tabelle zu entnehmen, zähle ich die Zeilen und probiere das Ergebnis mit der Spalte Frozen_Rand auf durchschnittlich 10.000 Zeilen aus:
SELECT COUNT(*) FROM table; -- Use this to determine rand_low and rand_high
SELECT *
FROM table
WHERE frozen_rand BETWEEN %(rand_low)s AND %(rand_high)s
ORDER BY RAND() LIMIT 1000
(Meine eigentliche Implementierung erfordert mehr Arbeit, um sicherzustellen, dass ich nicht unterabtastet, und um rand_high manuell herumzuwickeln, aber die Grundidee ist, "Ihr N zufällig auf einige Tausend zu reduzieren".)
Dies bringt zwar einige Opfer, ermöglicht es mir jedoch, die Datenbank mithilfe eines Index-Scans herunterzufahren, bis sie klein genug ist, um erneut nach Rang () zu bestellen.
quelle
RAND()
bei jedem nachfolgenden Aufruf derselbe Wert zurückgegeben wird.Antworten:
Es gibt hier eine sehr interessante Diskussion über diese Art von Problem: http://www.titov.net/2005/09/21/do-not-use-order-by-rand-or-how-to-get-random-rows-from-table/
Ich denke ohne jegliche Annahmen über die Tabelle, dass Ihre O (n lg n) -Lösung die beste ist. Obwohl mit einem guten Optimierer oder einer etwas anderen Technik die von Ihnen aufgelistete Abfrage möglicherweise etwas besser ist, ist O (m * n), wobei m die Anzahl der gewünschten zufälligen Zeilen ist, da nicht unbedingt das gesamte große Array sortiert werden muss könnte es nur nach den kleinsten m mal suchen. Aber für die Art von Zahlen, die Sie gepostet haben, ist m sowieso größer als lg n.
Drei Annahmen, die wir ausprobieren könnten:
Die Tabelle enthält einen eindeutigen, indizierten Primärschlüssel
Die Anzahl der zufälligen Zeilen, die Sie auswählen möchten (m), ist viel kleiner als die Anzahl der Zeilen in der Tabelle (n).
Der eindeutige Primärschlüssel ist eine Ganzzahl im Bereich von 1 bis n ohne Lücken
Mit nur den Annahmen 1 und 2 kann dies meiner Meinung nach in O (n) durchgeführt werden, obwohl Sie einen ganzen Index in die Tabelle schreiben müssen, um mit der Annahme 3 übereinzustimmen, sodass es nicht unbedingt ein schnelles O (n) ist. Wenn wir ZUSÄTZLICH etwas anderes Nettes an der Tabelle annehmen können, können wir die Aufgabe in O (m log m) erledigen. Annahme 3 wäre eine einfache, nette zusätzliche Eigenschaft, mit der man arbeiten kann. Mit einem netten Zufallszahlengenerator, der beim Generieren von m Zahlen in einer Reihe keine Duplikate garantiert, wäre eine O (m) -Lösung möglich.
Unter Berücksichtigung der drei Annahmen besteht die Grundidee 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 momentan kein MySQL oder irgendetwas vor mir, also würde dies in einem leichten Pseudocode ungefähr so aussehen:
Wenn Sie sich wirklich Gedanken über die Effizienz machen, können Sie die Zufallsschlüsselgenerierung in einer prozeduralen Sprache durchführen und die Ergebnisse in die Datenbank einfügen, da fast alles andere als SQL wahrscheinlich besser für die Art der erforderlichen Schleifen- und Zufallszahlengenerierung geeignet ist .
quelle
Ich denke, die schnellste Lösung ist
Hier ist, warum ich denke, dass dies den Job machen sollte.
Dies setzt voraus, dass rand () Zahlen in einer gleichmäßigen Verteilung generiert. Dies ist der schnellste Weg.
Ich sah, dass jemand diese Lösung empfohlen hatte und sie ohne Beweise abgeschossen wurden. Hier ist, was ich dazu sagen würde -
MySQL ist sehr gut in der Lage, Zufallszahlen für jede Zeile zu generieren. Versuche dies -
Wählen Sie rand () aus INFORMATION_SCHEMA.TABLES Limit 10;
Da es sich bei der fraglichen Datenbank um mySQL handelt, ist dies die richtige Lösung.
quelle
SELECT * FROM table ORDER BY RAND() LIMIT 10000
? Es muss zuerst eine Zufallszahl für jede Zeile erstellt werden (genau wie die von mir beschriebene Lösung) und dann bestellt werden. Sortierungen sind teuer! Aus diesem Grund ist diese Lösung langsamer als die von mir beschriebene, da keine Sortierung erforderlich ist. Sie können der von mir beschriebenen Lösung ein Limit hinzufügen, das Ihnen nicht mehr als diese Anzahl von Zeilen gibt. Wie jemand richtig betont hat, erhalten Sie keine GENAUE Stichprobengröße, aber bei Zufallsstichproben ist EXACT meistens keine strenge Anforderung.Anscheinend gibt es in einigen SQL-Versionen einen
TABLESAMPLE
Befehl, der jedoch nicht in allen SQL-Implementierungen enthalten ist (insbesondere Redshift).http://technet.microsoft.com/en-us/library/ms189108(v=sql.105).aspx
quelle
TABLESAMPLE
dies im statistischen Sinne nicht zufällig ist.Schneller als BESTELLEN NACH RAND ()
Ich habe diese Methode getestet, um viel schneller zu sein als
ORDER BY RAND()
, daher läuft sie in O (n) -Zeit und ist beeindruckend schnell.Von http://technet.microsoft.com/en-us/library/ms189108%28v=sql.105%29.aspx :
Nicht-MSSQL-Version - Ich habe dies nicht getestet
MSSQL-Version:
Dadurch werden ~ 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 gewissen Sicherheitsabstand und pflücken Sie dann nach der zufälligen
ORDER BY RAND()
Methode zufällig überschüssige Datensätze aus dem resultierenden Satz .Noch schneller
Ich konnte diese Methode noch weiter verbessern, da ich einen bekannten indizierten Spaltenwertbereich hatte.
Wenn Sie beispielsweise eine indizierte Spalte mit gleichmäßig verteilten Ganzzahlen [0..max] haben, können Sie damit N kleine Intervalle zufällig auswählen. Führen Sie dies dynamisch in Ihrem Programm durch, um für jeden Abfragelauf einen anderen Satz zu erhalten. Diese Teilmengenauswahl ist O (N) , was viele Größenordnungen kleiner sein kann als Ihr vollständiger Datensatz.
In meinem Test habe ich die Zeit, die benötigt wird, um 20 (aus 20 mil) Probendatensätzen mit ORDER BY RAND () von 3 Minuten zu erhalten , auf 0,0 Sekunden reduziert !
quelle
Benutz einfach
um 10% der Aufzeichnungen zu erhalten oder
um 1% der Aufzeichnungen usw. zu erhalten.
quelle
RAND()
wird für nachfolgende Aufrufe (zumindest unter MSSQL) derselbe Wert zurückgegeben, was bedeutet, dass Sie mit dieser Wahrscheinlichkeit entweder die gesamte Tabelle oder keine davon erhalten.Ich möchte darauf hinweisen, dass alle diese Lösungen scheinbar ersatzlos getestet werden. Wenn Sie die oberen K Zeilen aus einer zufälligen Sortierung auswählen oder eine Tabelle mit eindeutigen Schlüsseln in zufälliger Reihenfolge erstellen, erhalten Sie eine ersatzlose Zufallsstichprobe.
Wenn Sie möchten, dass Ihre Probe unabhängig ist, müssen Sie sie mit Ersatz probieren. In Frage 25451034 finden Sie ein Beispiel für die Verwendung eines JOIN auf ähnliche Weise wie bei der Lösung von user12861. Die Lösung ist für T-SQL geschrieben, aber das Konzept funktioniert in jeder SQL-Datenbank.
quelle
Beginnend mit der Beobachtung, dass wir die IDs einer Tabelle (z. B. Anzahl 5) basierend auf einer Menge abrufen können:
Wir können zu dem Ergebnis kommen, dass wir
"(4, 1, 2, 5, 3)"
einen effizienteren Weg hätten als wenn wir den String generieren könntenRAND()
.Zum Beispiel in Java:
Wenn IDs Lücken aufweisen, ist die anfängliche Arrayliste
indices
das Ergebnis einer SQL-Abfrage für IDs.quelle
Wenn Sie genau
m
Zeilen benötigen , generieren Sie realistischerweise Ihre Teilmenge von IDs außerhalb von SQL. Die meisten Methoden erfordern irgendwann die Auswahl des "n-ten" Eintrags, und SQL-Tabellen sind überhaupt keine Arrays. Die Annahme, dass die Schlüssel aufeinanderfolgend sind, um nur zufällige Ints zwischen 1 und der Anzahl zu verbinden, ist ebenfalls schwer zu erfüllen - MySQL unterstützt dies beispielsweise nicht nativ und die Sperrbedingungen sind ... schwierig .Hier ist eine
O(max(n, m lg n))
Time-Space-O(n)
Lösung, bei der nur einfache BTREE-Schlüssel vorausgesetzt werden:O(n)
m
dem Tauschen[0:m-1]
an und extrahieren Sie das Subarray hineinϴ(m)
SELECT ... WHERE id IN (<subarray>)
) inO(m lg n)
Jede Methode, die die zufällige Teilmenge außerhalb von SQL generiert, muss mindestens diese Komplexität aufweisen. Der Join kann nicht schneller sein als
O(m lg n)
mit BTREE (daher sindO(m)
Behauptungen für die meisten Engines Fantasie), und das Shuffle ist unten begrenztn
undm lg n
beeinflusst das asymptotische Verhalten nicht.Im pythonischen Pseudocode:
quelle
Wählen Sie 3000 zufällige Datensätze in Netezza aus:
quelle
Vielleicht könntest du es tun
quelle