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

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

MIT IDS ALS (
     SELECT ID
     FROM MYTABLE;
)

SELECT ID FROM IDS ORDER BY mt_random() LIMIT 3000

Answer 2

Vielleicht könntest du

SELECT * FROM Tabelle LIMIT 10000 OFFSET FLOOR(RAND() * 190000)