Ich möchte eine zufällige Auswahl von Zeilen in PostgreSQL, ich habe dies versucht:

select * from table where random() < 0.01;

Aber einige andere empfehlen dies:

select * from table order by random() limit 1000;

Ich habe eine sehr große Tabelle mit 500 Millionen Zeilen, ich möchte, dass sie schnell ist.

Welcher Ansatz ist besser? Was sind die Unterschiede? Was ist der beste Weg, um zufällige Zeilen auszuwählen?

Angesichts Ihrer Spezifikationen (plus zusätzliche Informationen in den Kommentaren),

• Sie haben eine numerische ID-Spalte (Ganzzahlen) mit nur wenigen (oder mäßig wenigen) Lücken.
• Offensichtlich keine oder wenige Schreibvorgänge.
• Ihre ID-Spalte muss indiziert werden! Ein Primärschlüssel dient gut.

Die folgende Abfrage erfordert keinen sequentiellen Scan der großen Tabelle, sondern nur einen Index-Scan.

Erhalten Sie zunächst Schätzungen für die Hauptabfrage:

SELECT count(*) AS ct              -- optional
     , min(id)  AS min_id
     , max(id)  AS max_id
     , max(id) - min(id) AS id_span
FROM   big;

Der einzig möglicherweise teure Teil ist der count(*)(für große Tische). Angesichts der oben genannten Spezifikationen benötigen Sie es nicht. Ein Kostenvoranschlag reicht völlig aus und ist fast kostenlos erhältlich ( ausführliche Erklärung hier ):

SELECT reltuples AS ct FROM pg_class WHERE oid = 'schema_name.big'::regclass;

Solange ctnicht viel kleiner als id_span, wird die Abfrage andere Ansätze übertreffen.

WITH params AS (
    SELECT 1       AS min_id           -- minimum id <= current min id
         , 5100000 AS id_span          -- rounded up. (max_id - min_id + buffer)
    )
SELECT *
FROM  (
    SELECT p.min_id + trunc(random() * p.id_span)::integer AS id
    FROM   params p
          ,generate_series(1, 1100) g  -- 1000 + buffer
    GROUP  BY 1                        -- trim duplicates
    ) r
JOIN   big USING (id)
LIMIT  1000;                           -- trim surplus

• Generieren Sie Zufallszahlen im idRaum. Sie haben "wenige Lücken", also addieren Sie 10% (genug, um die Leerzeichen leicht zu bedecken) zur Anzahl der abzurufenden Zeilen.

• Jeder idkann mehrmals zufällig ausgewählt werden (obwohl dies mit einem großen ID-Bereich sehr unwahrscheinlich ist). Gruppieren Sie daher die generierten Zahlen (oder verwenden Sie sie DISTINCT).

• Verbinden Sie die ids mit dem großen Tisch. Dies sollte sehr schnell sein, wenn der Index vorhanden ist.

• Zum Schluss Überschüsse idabschneiden, die nicht von Betrügern und Lücken gefressen wurden. Jede Reihe hat die gleiche Chance, ausgewählt zu werden.

Kurzfassung

Sie können diese Abfrage vereinfachen . Der CTE in der obigen Abfrage dient nur zu Bildungszwecken:

SELECT *
FROM  (
    SELECT DISTINCT 1 + trunc(random() * 5100000)::integer AS id
    FROM   generate_series(1, 1100) g
    ) r
JOIN   big USING (id)
LIMIT  1000;

Mit rCTE verfeinern

Vor allem, wenn Sie sich bei Lücken und Schätzungen nicht so sicher sind.

WITH RECURSIVE random_pick AS (
   SELECT *
   FROM  (
      SELECT 1 + trunc(random() * 5100000)::int AS id
      FROM   generate_series(1, 1030)  -- 1000 + few percent - adapt to your needs
      LIMIT  1030                      -- hint for query planner
      ) r
   JOIN   big b USING (id)             -- eliminate miss

   UNION                               -- eliminate dupe
   SELECT b.*
   FROM  (
      SELECT 1 + trunc(random() * 5100000)::int AS id
      FROM   random_pick r             -- plus 3 percent - adapt to your needs
      LIMIT  999                       -- less than 1000, hint for query planner
      ) r
   JOIN   big b USING (id)             -- eliminate miss
   )
SELECT *
FROM   random_pick
LIMIT  1000;  -- actual limit

Wir können mit einem kleineren Überschuss in der Basisabfrage arbeiten. Wenn zu viele Lücken vorhanden sind, sodass in der ersten Iteration nicht genügend Zeilen gefunden werden, iteriert der rCTE weiterhin mit dem rekursiven Term. Wir brauchen noch relativ wenige Lücken im ID-Bereich, oder die Rekursion läuft möglicherweise trocken, bevor das Limit erreicht ist - oder wir müssen mit einem ausreichend großen Puffer beginnen, der dem Zweck der Leistungsoptimierung widerspricht.

Duplikate werden UNIONim rCTE eliminiert.

Das Äußere LIMITlässt den CTE anhalten, sobald wir genügend Zeilen haben.

Diese Abfrage wurde sorgfältig entworfen, um den verfügbaren Index zu verwenden, tatsächlich zufällige Zeilen zu generieren und nicht anzuhalten, bis wir das Limit erreicht haben (es sei denn, die Rekursion läuft trocken). Hier gibt es eine Reihe von Fallstricken, wenn Sie es neu schreiben.

In Funktion einwickeln

Bei wiederholter Verwendung mit unterschiedlichen Parametern:

CREATE OR REPLACE FUNCTION f_random_sample(_limit int = 1000, _gaps real = 1.03)
  RETURNS SETOF big AS
$func$
DECLARE
   _surplus  int := _limit * _gaps;
   _estimate int := (           -- get current estimate from system
      SELECT c.reltuples * _gaps
      FROM   pg_class c
      WHERE  c.oid = 'big'::regclass);
BEGIN

   RETURN QUERY
   WITH RECURSIVE random_pick AS (
      SELECT *
      FROM  (
         SELECT 1 + trunc(random() * _estimate)::int
         FROM   generate_series(1, _surplus) g
         LIMIT  _surplus           -- hint for query planner
         ) r (id)
      JOIN   big USING (id)        -- eliminate misses

      UNION                        -- eliminate dupes
      SELECT *
      FROM  (
         SELECT 1 + trunc(random() * _estimate)::int
         FROM   random_pick        -- just to make it recursive
         LIMIT  _limit             -- hint for query planner
         ) r (id)
      JOIN   big USING (id)        -- eliminate misses
   )
   SELECT *
   FROM   random_pick
   LIMIT  _limit;
END
$func$  LANGUAGE plpgsql VOLATILE ROWS 1000;

Anruf:

SELECT * FROM f_random_sample();
SELECT * FROM f_random_sample(500, 1.05);

Sie können dieses Generikum sogar für jede Tabelle verwenden: Nehmen Sie den Namen der PK-Spalte und der Tabelle als polymorphen Typ und verwenden Sie EXECUTE... Aber das geht über den Rahmen dieser Frage hinaus. Sehen:

• Refaktorieren Sie eine PL / pgSQL-Funktion, um die Ausgabe verschiedener SELECT-Abfragen zurückzugeben

Mögliche Alternative

WENN Ihre Anforderungen identische Sätze für wiederholte Anrufe zulassen (und wir sprechen über wiederholte Anrufe), würde ich eine materialisierte Ansicht in Betracht ziehen . Führen Sie die obige Abfrage einmal aus und schreiben Sie das Ergebnis in eine Tabelle. Benutzer erhalten eine blitzschnelle Auswahl quasi zufällig. Aktualisieren Sie Ihre zufällige Auswahl in Intervallen oder Ereignissen Ihrer Wahl.

Postgres 9.5 stellt vor TABLESAMPLE SYSTEM (n)

Wo nist ein Prozentsatz. Das Handbuch:

Die BERNOULLIund die SYSTEMStichprobenmethode akzeptieren jeweils ein einzelnes Argument, das den Bruchteil der zu untersuchenden Tabelle darstellt, ausgedrückt als Prozentsatz zwischen 0 und 100 . Dieses Argument kann ein beliebiger realAusdruck sein.

Meine kühne Betonung. Es ist sehr schnell , aber das Ergebnis ist nicht gerade zufällig . Das Handbuch noch einmal:

Die SYSTEMMethode ist erheblich schneller als die BERNOULLIMethode, wenn kleine Stichprobenprozentsätze angegeben werden, kann jedoch aufgrund von Clustering-Effekten eine weniger zufällige Stichprobe der Tabelle zurückgeben.

Die Anzahl der zurückgegebenen Zeilen kann stark variieren. In unserem Beispiel erhalten Sie ungefähr 1000 Zeilen:

SELECT * FROM big TABLESAMPLE SYSTEM ((1000 * 100) / 5100000.0);

Verbunden:

• Schneller Weg, um die Zeilenanzahl einer Tabelle in PostgreSQL zu ermitteln

Oder installieren Sie das zusätzliche Modul tsm_system_rows , um die Anzahl der angeforderten Zeilen genau zu ermitteln (sofern genügend vorhanden sind) und die bequemere Syntax zu berücksichtigen :

SELECT * FROM big TABLESAMPLE SYSTEM_ROWS(1000);

Siehe Evans Antwort für Details.

Aber das ist immer noch nicht gerade zufällig.

Sie können den Ausführungsplan von beiden mithilfe von untersuchen und vergleichen

EXPLAIN select * from table where random() < 0.01;
EXPLAIN select * from table order by random() limit 1000;

Ein schneller Test an einer großen Tabelle ¹ zeigt, dass ORDER BYzuerst die gesamte Tabelle sortiert und dann die ersten 1000 Elemente ausgewählt werden. Beim Sortieren einer großen Tabelle wird nicht nur diese Tabelle gelesen, sondern auch temporäre Dateien gelesen und geschrieben. Daswhere random() < 0.1 einzige scannt die gesamte Tabelle nur einmal.

Bei großen Tabellen ist dies möglicherweise nicht das, was Sie möchten, da selbst ein vollständiger Tabellenscan zu lange dauern kann.

Ein dritter Vorschlag wäre

select * from table where random() < 0.01 limit 1000;

Dieser stoppt den Tabellenscan, sobald 1000 Zeilen gefunden wurden, und kehrt daher früher zurück. Natürlich blockiert dies die Zufälligkeit ein wenig, aber vielleicht ist dies in Ihrem Fall gut genug.

Bearbeiten: Neben diesen Überlegungen können Sie auch die bereits gestellten Fragen dazu überprüfen. Verwenden der Abfrage[postgresql] random liefert einige Treffer.

• schnelle zufällige Zeilenauswahl in Postgres
• Wie rufe ich zufällige Datenzeilen aus einer postgreSQL-Tabelle ab?
• postgres: zufällige Einträge aus der Tabelle holen - zu langsam

Und ein verlinkter Artikel von depez, der mehrere weitere Ansätze beschreibt:

• http://www.depesz.com/index.php/2007/09/16/my- Thoughts-on-getting-random-row/

¹ "groß" wie in "Die vollständige Tabelle passt nicht in den Speicher".

postgresql Reihenfolge nach Zufall (), Zeilen in zufälliger Reihenfolge auswählen:

select your_columns from your_table ORDER BY random()

postgresql order by random () mit einem eindeutigen:

select * from 
  (select distinct your_columns from your_table) table_alias
ORDER BY random()

postgresql Reihenfolge nach dem Zufallsprinzip eine Zeile:

select your_columns from your_table ORDER BY random() limit 1

Ab PostgreSQL 9.5 gibt es eine neue Syntax, mit der zufällige Elemente aus einer Tabelle abgerufen werden können:

SELECT * FROM mytable TABLESAMPLE SYSTEM (5);

In diesem Beispiel erhalten Sie 5% der Elemente aus mytable.

Weitere Erklärungen finden Sie in diesem Blogbeitrag: http://www.postgresql.org/docs/current/static/sql-select.html

Der mit dem ORDER BY wird der langsamere sein.

select * from table where random() < 0.01;geht Datensatz für Datensatz und entscheidet, ob er zufällig gefiltert wird oder nicht. Dies liegt daran, O(N)dass jeder Datensatz nur einmal überprüft werden muss.

select * from table order by random() limit 1000;wird den gesamten Tisch sortieren und dann die ersten 1000 auswählen. Abgesehen von jeglicher Voodoo-Magie hinter den Kulissen ist die Reihenfolge nach O(N * log N).

Der Nachteil random() < 0.01ist, dass Sie eine variable Anzahl von Ausgabedatensätzen erhalten.

Beachten Sie, dass es einen besseren Weg gibt, einen Datensatz zu mischen, als nach dem Zufallsprinzip zu sortieren: Der Fisher-Yates-Shuffle , der ausgeführt wird O(N). Das Implementieren des Shuffle in SQL klingt jedoch nach einer ziemlichen Herausforderung.

Hier ist eine Entscheidung, die für mich funktioniert. Ich denke, es ist sehr einfach zu verstehen und auszuführen.

SELECT 
  field_1, 
  field_2, 
  field_2, 
  random() as ordering
FROM 
  big_table
WHERE 
  some_conditions
ORDER BY
  ordering 
LIMIT 1000;

select * from table order by random() limit 1000;

Wenn Sie wissen, wie viele Zeilen Sie möchten, überprüfen Sie tsm_system_rows.

tsm_system_rows

Das Modul stellt die Tabellenabtastmethode SYSTEM_ROWS bereit, die in der TABLESAMPLE-Klausel eines SELECT-Befehls verwendet werden kann.

Diese Tabellenabtastmethode akzeptiert ein einzelnes ganzzahliges Argument, das die maximale Anzahl der zu lesenden Zeilen darstellt. Das resultierende Beispiel enthält immer genau so viele Zeilen, es sei denn, die Tabelle enthält nicht genügend Zeilen. In diesem Fall wird die gesamte Tabelle ausgewählt. Wie die integrierte SYSTEM-Stichprobenmethode führt SYSTEM_ROWS eine Stichprobenerfassung auf Blockebene durch, sodass die Stichprobe nicht vollständig zufällig ist, sondern Clustering-Effekten unterliegen kann, insbesondere wenn nur eine geringe Anzahl von Zeilen angefordert wird.

Installieren Sie zuerst die Erweiterung

CREATE EXTENSION tsm_system_rows;

Dann Ihre Anfrage,

SELECT *
FROM table
TABLESAMPLE SYSTEM_ROWS(1000);

Wenn Sie nur eine Zeile möchten, können Sie eine berechnete offsetaus verwenden count.

select * from table_name limit 1
offset floor(random() * (select count(*) from table_name));

Eine Variation der von Erwin Brandstetter skizzierten materialisierten Ansicht "Mögliche Alternative" ist möglich.

Angenommen, Sie möchten keine Duplikate in den zurückgegebenen zufälligen Werten. Sie müssen also einen booleschen Wert für die Primärtabelle festlegen, der Ihren (nicht randomisierten) Wertesatz enthält.

Angenommen, dies ist die Eingabetabelle:

id_values  id  |   used
           ----+--------
           1   |   FALSE
           2   |   FALSE
           3   |   FALSE
           4   |   FALSE
           5   |   FALSE
           ...

Füllen Sie die ID_VALUESTabelle nach Bedarf. Erstellen Sie dann, wie von Erwin beschrieben, eine materialisierte Ansicht, die die ID_VALUESTabelle einmal randomisiert :

CREATE MATERIALIZED VIEW id_values_randomized AS
  SELECT id
  FROM id_values
  ORDER BY random();

Beachten Sie, dass die materialisierte Ansicht nicht die verwendete Spalte enthält, da diese schnell veraltet ist. Die Ansicht muss auch keine anderen Spalten enthalten, die sich möglicherweise in der id_valuesTabelle befinden.

Um (und „verbrauchen“) Zufallswerte zu erhalten, verwenden Sie eine UPDATE-RüCKFüHRUNG auf id_values, die Auswahl id_valuesvon id_values_randomizedmit einer Verknüpfung, und die gewünschten Kriterien der Anwendung nur relevante Möglichkeiten zu erhalten. Zum Beispiel:

UPDATE id_values
SET used = TRUE
WHERE id_values.id IN 
  (SELECT i.id
    FROM id_values_randomized r INNER JOIN id_values i ON i.id = r.id
    WHERE (NOT i.used)
    LIMIT 5)
RETURNING id;

Bei LIMITBedarf ändern - Wenn Sie jeweils nur einen zufälligen Wert benötigen, wechseln Sie LIMITzu 1.

id_valuesIch bin der Meinung, dass UPDATE-RETURNING mit den richtigen Indizes sehr schnell und mit wenig Last ausgeführt werden sollte. Es werden zufällige Werte mit einem Datenbank-Roundtrip zurückgegeben. Die Kriterien für "berechtigte" Zeilen können so komplex wie erforderlich sein. Neue Zeilen können jederzeit zur id_valuesTabelle hinzugefügt werden und sind für die Anwendung zugänglich, sobald die materialisierte Ansicht aktualisiert wird (die wahrscheinlich außerhalb der Spitzenzeiten ausgeführt werden kann). Das Erstellen und Aktualisieren der materialisierten Ansicht ist langsam, muss jedoch nur ausgeführt werden, wenn der id_valuesTabelle neue IDs hinzugefügt werden.

Eine Lektion aus meiner Erfahrung:

offset floor(random() * N) limit 1ist nicht schneller als order by random() limit 1.

Ich dachte, der offsetAnsatz wäre schneller, weil er die Zeit für das Sortieren in Postgres sparen sollte. Es stellte sich heraus, dass es nicht war.

Fügen Sie eine Spalte mit dem Namen rtype hinzu serial. Index r.

Angenommen, wir haben 200.000 Zeilen, dann generieren wir eine Zufallszahl n, wobei 0 n<< = 200.000 .

Wählen Sie Zeilen mit aus r > n, sortieren Sie sie ASCund wählen Sie die kleinste aus.

Code:

select * from YOUR_TABLE 
where r > (
    select (
        select reltuples::bigint AS estimate
        from   pg_class
        where  oid = 'public.YOUR_TABLE'::regclass) * random()
    )
order by r asc limit(1);

Der Code ist selbsterklärend. Die Unterabfrage in der Mitte wird verwendet, um die Anzahl der Tabellenzeilen unter https://stackoverflow.com/a/7945274/1271094 schnell zu schätzen .

In der Anwendungsebene müssen Sie die Anweisung erneut ausführen, wenn n> die Anzahl der Zeilen oder mehrere Zeilen ausgewählt werden müssen.

Ich weiß, dass ich etwas spät zur Party komme, aber ich habe gerade dieses großartige Tool namens pg_sample gefunden :

pg_sample - Extrahieren Sie einen kleinen Beispieldatensatz aus einer größeren PostgreSQL-Datenbank, während Sie die referenzielle Integrität beibehalten.

Ich habe dies mit einer 350M-Zeilendatenbank versucht und es war sehr schnell, ich weiß nichts über die Zufälligkeit .

./pg_sample --limit="small_table = *" --limit="large_table = 100000" -U postgres source_db | psql -U postgres target_db