Einfache Zufallsstichproben aus einer SQL-Datenbank

91

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.

ojrac
quelle
3
Dies funktioniert nicht einmal in SQL Server, da RAND()bei jedem nachfolgenden Aufruf derselbe Wert zurückgegeben wird.
Andrew Mao
1
Guter Punkt - Ich werde einen Hinweis hinzufügen, dass SQL Server-Benutzer stattdessen ORDER BY NEWID () verwenden sollten.
Ojrac
Es ist immer noch schrecklich ineffizient, weil es alle Daten sortieren muss. Eine Zufallsstichprobenmethode für einen bestimmten Prozentsatz ist besser, aber selbst nachdem ich hier eine Reihe von Beiträgen gelesen habe, habe ich keine akzeptable Lösung gefunden, die ausreichend zufällig ist.
Andrew Mao
Wenn Sie die Frage lesen, frage ich speziell, weil ORDER BY RAND () O (n lg n) ist.
Ojrac
Die Antwort von muposat unten ist großartig, wenn Sie nicht zu sehr von der statistischen Zufälligkeit von RAND () besessen sind.
Josh Greifer

Antworten:

24

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:

  1. Die Tabelle enthält einen eindeutigen, indizierten Primärschlüssel

  2. 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).

  3. 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:


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

-- generate m random keys between 1 and n
for i = 1 to m
  insert RandomKeysAttempt select rand()*n + 1

-- eliminate duplicates
insert RandomKeys select distinct RandomKey from RandomKeysAttempt

-- as long as we don't have enough, keep generating new keys,
-- with luck (and m much less than n), this won't be necessary
while count(RandomKeys) < m
  NextAttempt = rand()*n + 1
  if not exists (select * from RandomKeys where RandomKey = NextAttempt)
    insert RandomKeys select NextAttempt

-- get our random rows
select *
from RandomKeys r
join table t ON r.RandomKey = t.UniqueKey

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 .

user12861
quelle
Ich würde empfehlen, einen eindeutigen Index für die zufällige Schlüsselauswahl hinzuzufügen und möglicherweise Duplikate auf der Einfügung zu ignorieren. Dann können Sie die unterschiedlichen Elemente entfernen und der Join wird schneller.
Sam Saffron
Ich denke, der Zufallszahlenalgorithmus könnte einige Verbesserungen gebrauchen - entweder eine UNIQUE-Einschränkung wie erwähnt oder nur 2 * m-Zahlen generieren und SELECT DISTINCT, ORDER BY-ID (first-come-first-serve), sodass dies auf die UNIQUE-Einschränkung reduziert wird ) LIMIT m. Ich mag das.
Ojrac
Um der Auswahl der zufälligen Schlüssel einen eindeutigen Index hinzuzufügen und dann beim Einfügen Duplikate zu ignorieren, dachte ich, dies könnte Sie für eine Sortierung zum Verhalten von O (m ^ 2) anstelle von O (m lg m) zurückbringen. Sie sind sich nicht sicher, wie effizient der Server den Index verwaltet, wenn Sie nacheinander zufällige Zeilen einfügen.
user12861
In Bezug auf Vorschläge zur Erzeugung von 2 * m-Zahlen oder Ähnlichem wollte ich einen Algorithmus, der garantiert funktioniert, egal was passiert. Es besteht immer die (geringe) Wahrscheinlichkeit, dass Ihre 2 * m-Zufallszahlen mehr als m Duplikate enthalten, sodass Sie nicht genug für Ihre Abfrage haben.
user12861
1
Wie erhält man die Anzahl der Zeilen in der Tabelle?
Super-o
51

Ich denke, die schnellste Lösung ist

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

Hier ist, warum ich denke, dass dies den Job machen sollte.

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

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 -

  • Dies ist O (n), aber es ist keine Sortierung erforderlich, so dass es schneller als das O (n lg n) ist.
  • 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.

ignorant
quelle
1
Erstens haben Sie das Problem, dass dies die Frage nicht wirklich beantwortet, da eine halbzufällige Anzahl von Ergebnissen zurückgegeben wird, die nahe an einer gewünschten Anzahl, aber nicht unbedingt genau dieser Anzahl liegt, anstatt einer genau gewünschten Anzahl von Ergebnissen.
user12861
1
In Bezug auf die Effizienz ist Ihre O (n), wobei n die Anzahl der Zeilen in der Tabelle ist. Das ist bei weitem nicht so gut wie O (m log m), wobei m die Anzahl der gewünschten Ergebnisse ist und m << n. Sie könnten immer noch Recht haben, dass es in der Praxis schneller wäre, denn wie Sie sagen, könnte es sehr schnell sein, rand () zu generieren und sie mit einer Konstanten zu vergleichen. Sie müssten es testen, um es herauszufinden. Mit kleineren Tischen können Sie gewinnen. Mit riesigen Tabellen und einer viel geringeren Anzahl gewünschter Ergebnisse bezweifle ich es.
user12861
1
Während @ user12861 Recht hat, dass dies nicht die genau richtige Zahl ist, ist es eine gute Möglichkeit, den Datensatz auf die richtige grobe Größe zu reduzieren.
Ojrac
1
Wie bedient die Datenbank die folgende Abfrage - 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.
unwissend
Gibt es eine Möglichkeit, die Mindestanzahl von Zeilen anzugeben?
CMCDragonkai
4

Anscheinend gibt es in einigen SQL-Versionen einen TABLESAMPLEBefehl, der jedoch nicht in allen SQL-Implementierungen enthalten ist (insbesondere Redshift).

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

gatoatigrado
quelle
Sehr cool! Es sieht so aus, als ob es nicht von PostgreSQL oder MySQL / MariaDB implementiert wurde, aber es ist eine gute Antwort, wenn Sie eine SQL-Implementierung verwenden, die dies unterstützt.
Ojrac
Ich verstehe, dass TABLESAMPLEdies im statistischen Sinne nicht zufällig ist.
Sean
4

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

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 ~ 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 !

Muposat
quelle
3

Benutz einfach

WHERE RAND() < 0.1 

um 10% der Aufzeichnungen zu erhalten oder

WHERE RAND() < 0.01 

um 1% der Aufzeichnungen usw. zu erhalten.

David F. Mayer
quelle
1
Das ruft RAND für jede Zeile auf und macht es zu O (n). Das Plakat suchte nach etwas Besserem.
user12861
1
Darüber hinaus 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.
Andrew Mao
1

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.

Gazzman
quelle
0

Beginnend mit der Beobachtung, dass wir die IDs einer Tabelle (z. B. Anzahl 5) basierend auf einer Menge abrufen können:

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

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önnten RAND().

Zum Beispiel in Java:

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

Wenn IDs Lücken aufweisen, ist die anfängliche Arrayliste indicesdas Ergebnis einer SQL-Abfrage für IDs.

KitKat
quelle
0

Wenn Sie genau mZeilen 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:

  1. Rufen Sie alle Werte der Schlüsselspalte der Datentabelle in beliebiger Reihenfolge in ein Array in Ihrer bevorzugten Skriptsprache in ab O(n)
  2. Führen Sie einen Fisher-Yates-Shuffle durch , halten Sie nach mdem Tauschen [0:m-1]an und extrahieren Sie das Subarray hineinϴ(m)
  3. "Verbinden" Sie das Subarray mit dem Originaldatensatz (z. B. 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 sind O(m)Behauptungen für die meisten Engines Fantasie), und das Shuffle ist unten begrenzt nund m lg nbeeinflusst das asymptotische Verhalten nicht.

Im pythonischen 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])
concat
quelle
0

Wählen Sie 3000 zufällige Datensätze in Netezza aus:

WITH IDS AS (
     SELECT ID
     FROM MYTABLE;
)

SELECT ID FROM IDS ORDER BY mt_random() LIMIT 3000
Odysseus Ithaka
quelle
Abgesehen vom Hinzufügen einiger SQL-dialektspezifischer Notizen beantwortet dies meiner Meinung nach nicht die Frage, wie eine zufällige Stichprobe von Zeilen ohne 'ORDER BY rand () LIMIT $ 1' abgefragt werden kann.
Ojrac
-4

Vielleicht könntest du es tun

SELECT * FROM table LIMIT 10000 OFFSET FLOOR(RAND() * 190000)
staticsan
quelle
1
Es sieht so aus, als würde dies einen zufälligen Teil meiner Daten auswählen. Ich suche etwas Komplizierteres - 10.000 zufällig verteilte Zeilen.
Ojrac
Dann ist ORDER BY rand () Ihre einzige Option, wenn Sie dies in der Datenbank tun möchten.
Statik