Der beste Weg, um zufällige Zeilen auszuwählen PostgreSQL

Question

Ich möchte eine zufällige Auswahl von Zeilen in PostgreSQL, habe ich 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 und möchte, dass sie schnell ist.

Welcher Ansatz ist besser? Was sind die Unterschiede? Wie wählt man am besten zufällige Zeilen aus?

Answer 1

Schnelle Wege

Unter Berücksichtigung Ihrer Angaben (und zusätzlicher Informationen in den Kommentaren),

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

Die folgende Abfrage erfordert keine sequentielle Suche in der großen Tabelle, sondern nur eine Indexsuche.

Ermitteln 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;

Das einzige möglicherweise teure Teil ist die count(*) (für große Tische). Bei den oben genannten Spezifikationen brauchen Sie das nicht. Eine Schätzung, um die vollständige Zählung zu ersetzen reicht völlig aus und ist fast kostenlos erhältlich:

SELECT (reltuples / relpages * (pg_relation_size(oid) / 8192))::bigint AS ct
FROM   pg_class
WHERE  oid = 'big'::regclass;  -- your table name

Ausführliche Erklärung:

• Schneller Weg zur Ermittlung der Zeilenzahl einer Tabelle in PostgreSQL

Solange ct ist nicht beaucoup 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 in der id Raum. Sie haben "wenige Lücken", also addieren Sie 10 % (genug, um die Lücken leicht abzudecken) zu der Anzahl der abzurufenden Zeilen.

• Jede id mehrmals zufällig ausgewählt werden kann (obwohl dies bei einem großen id-Raum sehr unwahrscheinlich ist), gruppieren Sie die generierten Zahlen (oder verwenden Sie DISTINCT ).

• Beitritt zum id s an den großen Tisch. Dies sollte sehr schnell gehen, wenn der Index vorhanden ist.

• Schließlich den Überschuss abschneiden id s, die nicht von Duplikaten und Lücken aufgefressen wurden. Jede Zeile hat eine völlig gleiche Chance gepflückt werden.

Kurzfassung

Sie können vereinfachen diese Abfrage. Der CTE in der obigen Abfrage ist nur für Lehrzwecke:

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

Verfeinern mit rCTE

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
   )
TABLE  random_pick
LIMIT  1000;  -- actual limit

Wir können mit einer geringerer Überschuss in der Basisabfrage. Wenn es zu viele Lücken gibt, so dass wir in der ersten Iteration nicht genügend Zeilen finden, fährt die rCTE mit dem rekursiven Term fort zu iterieren. Wir brauchen immer noch relativ wenige Lücken im ID-Raum oder die Rekursion kann versiegen, bevor die Grenze erreicht ist - oder wir müssen mit einem ausreichend großen Puffer beginnen, was dem Zweck der Leistungsoptimierung widerspricht.

Duplikate werden durch das UNION im rCTE.

Die äußere LIMIT sorgt dafür, dass der CTE stoppt, 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 erzeugen und nicht aufzuhören, bis wir das Limit erreicht haben (es sei denn, die Rekursion läuft aus). Es gibt hier eine Reihe von Fallstricken, wenn Sie die Abfrage neu schreiben wollen.

In Funktion umwandeln

Zur wiederholten Verwendung mit dem gleiche Tabelle mit unterschiedlichen Parametern:

CREATE OR REPLACE FUNCTION f_random_sample(_limit int = 1000, _gaps real = 1.03)
  RETURNS SETOF big
  LANGUAGE plpgsql VOLATILE ROWS 1000 AS
$func$
DECLARE
   _surplus  int := _limit * _gaps;
   _estimate int := (           -- get current estimate from system
      SELECT (reltuples / relpages * (pg_relation_size(oid) / 8192))::bigint
      FROM   pg_class
      WHERE  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
   )
   TABLE  random_pick
   LIMIT  _limit;
END
$func$;

Anrufen:

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

Allgemeine Funktion

Wir können dies generisch machen, damit es funktioniert für beliebige Tabelle mit einer eindeutigen Integer-Spalte (in der Regel die PK): Übergeben Sie die Tabelle als polymorphen Typ und (optional) den Namen der PK-Spalte und verwenden Sie EXECUTE :

CREATE OR REPLACE FUNCTION f_random_sample(_tbl_type anyelement
                                         , _id text = 'id'
                                         , _limit int = 1000
                                         , _gaps real = 1.03)
  RETURNS SETOF anyelement
  LANGUAGE plpgsql VOLATILE ROWS 1000 AS
$func$
DECLARE
   -- safe syntax with schema & quotes where needed
   _tbl text := pg_typeof(_tbl_type)::text;
   _estimate int := (SELECT (reltuples / relpages
                          * (pg_relation_size(oid) / 8192))::bigint
                     FROM   pg_class  -- get current estimate from system
                     WHERE  oid = _tbl::regclass);
BEGIN
   RETURN QUERY EXECUTE format(
   $$
   WITH RECURSIVE random_pick AS (
      SELECT *
      FROM  (
         SELECT 1 + trunc(random() * $1)::int
         FROM   generate_series(1, $2) g
         LIMIT  $2                 -- hint for query planner
         ) r(%2$I)
      JOIN   %1$s USING (%2$I)     -- eliminate misses

      UNION                        -- eliminate dupes
      SELECT *
      FROM  (
         SELECT 1 + trunc(random() * $1)::int
         FROM   random_pick        -- just to make it recursive
         LIMIT  $3                 -- hint for query planner
         ) r(%2$I)
      JOIN   %1$s USING (%2$I)     -- eliminate misses
   )
   TABLE  random_pick
   LIMIT  $3;
   $$
 , _tbl, _id
   )
   USING _estimate              -- $1
       , (_limit * _gaps)::int  -- $2 ("surplus")
       , _limit                 -- $3
   ;
END
$func$;

Aufruf mit Standardwerten (wichtig!):

SELECT * FROM f_random_sample(null::big);  --!

Oder genauer gesagt:

SELECT * FROM f_random_sample(null::"my_TABLE", 'oDD ID', 666, 1.15);

Ungefähr die gleiche Leistung wie bei der statischen Version.

Verwandt:

• Umstrukturierung einer PL/pgSQL-Funktion, um die Ausgabe verschiedener SELECT-Abfragen zurückzugeben - Kapitel "Verschiedene vollständige Tischtypen"
• SETOF-Zeilen von der PostgreSQL-Funktion zurückgeben
• Formatbezeichner für Integer-Variablen in format() für EXECUTE?
• INSERT mit dynamischem Tabellennamen in Triggerfunktion

Dies ist sicher gegen SQL-Injection. Siehe:

• Tabellenname als Parameter einer PostgreSQL-Funktion
• SQL-Injektion in Postgres-Funktionen und vorbereitete Abfragen

Mögliche Alternative

I Ihre Anforderungen erlauben identische Sätze für wiederholte Anrufe (und wir sprechen hier von wiederholten Anrufen) eine MATERIALIZED VIEW . Führen Sie die obige Abfrage einmal aus und schreiben Sie das Ergebnis in eine Tabelle. Die Benutzer erhalten eine quasi zufällige Auswahl in Windeseile. Aktualisieren Sie Ihre Zufallsauswahl in Intervallen oder bei Ereignissen Ihrer Wahl.

Postgres 9.5 wird eingeführt TABLESAMPLE SYSTEM (n)

Wo n ist ein Prozentsatz. Das Handbuch:

En BERNOULLI y SYSTEM Stichprobenverfahren akzeptieren jeweils eine einzige Argument, das den Teil der Tabelle angibt, aus dem eine Stichprobe gezogen werden soll, ausgedrückt als Prozentsatz zwischen 0 und 100 . Dieses Argument kann ein beliebiges sein real -bewerteten Ausdruck.

Fettgedruckte Hervorhebung von mir. Es ist sehr schnell aber das Ergebnis ist nicht ganz zufällig . Nochmals das Handbuch:

En SYSTEM Methode ist deutlich schneller als die BERNOULLI Methode wenn kleine Stichprobenprozentsätze angegeben werden, aber sie kann eine aufgrund von Clustereffekten eine weniger zufällige Stichprobe der Tabelle.

Die Anzahl der zurückgegebenen Zeilen kann stark variieren. Für unser Beispiel, um zu erhalten etwa 1000 Zeilen:

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

Verwandt:

• Schneller Weg zur Ermittlung der Zeilenzahl einer Tabelle in PostgreSQL

Oder das Zusatzmodul installieren tsm_system_rows um die Anzahl der angeforderten Zeilen genau zu ermitteln (wenn genug vorhanden sind) und die bequemere Syntax zu verwenden:

SELECT * FROM big TABLESAMPLE SYSTEM_ROWS(1000);

Siehe Evans Antwort für Einzelheiten.

Aber auch das ist nicht gerade zufällig.

Answer 2

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

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

Ein schneller Test auf einem großen Tisch 1 zeigt, dass die ORDER BY sortiert zunächst die gesamte Tabelle und wählt dann die ersten 1000 Einträge aus. Beim Sortieren einer großen Tabelle wird nicht nur diese Tabelle gelesen, sondern es werden auch temporäre Dateien gelesen und geschrieben. Die where random() < 0.1 durchsucht die gesamte Tabelle nur einmal.

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

Ein dritter Vorschlag würde lauten

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

Diese stoppt die Tabellendurchsuchung, sobald 1000 Zeilen gefunden wurden, und kehrt daher früher zurück. Natürlich wird dadurch die Zufälligkeit ein wenig gebremst, aber vielleicht ist das in Ihrem Fall gut genug.

Bearbeiten: Abgesehen von diesen Überlegungen können Sie sich auch die bereits gestellten Fragen dazu ansehen. Verwendung der Abfrage [postgresql] random liefert eine ganze Reihe von Treffern.

• schnelle zufällige Zeilenauswahl in Postgres
• Wie kann man randomisierte Datenzeilen aus einer postgreSQL-Tabelle abrufen?
• postgres: Zufällige Einträge aus Tabelle holen - zu langsam

Und ein verlinkter Artikel von Depez, in dem mehrere weitere Ansätze beschrieben werden:

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

---

1 "groß" im Sinne von "die gesamte Tabelle passt nicht in den Speicher".

Answer 3

Postgresql order by random(), Zeilen in zufälliger Reihenfolge auswählen:

Dies ist langsam, da die gesamte Tabelle geordnet wird, um sicherzustellen, dass jede Zeile die gleiche Chance hat, ausgewählt zu werden. Ein vollständiger Tabellenscan ist für perfekte Zufälligkeit unvermeidlich.

select your_columns from your_table ORDER BY random()

postgresql order by random() mit einem distinct:

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

postgresql order by random limit one row:

Dies ist ebenfalls langsam, da die Tabelle gescannt werden muss, um sicherzustellen, dass jede Zeile, die ausgewählt werden könnte, die gleiche Chance hat, in diesem Moment ausgewählt zu werden:

select your_columns from your_table ORDER BY random() limit 1

Konstante Zeit Select Random N rows mit periodischem Tabellenscan:

Wenn Ihr Tisch riesig ist, dann sind die oben genannten Tisch-Scans ein echter Hingucker und dauern bis zu 5 Minuten.

Um schneller zu sein, können Sie hinter den Kulissen eine nächtliche Neuindizierung der Tabellen planen, die eine vollkommen zufällige Auswahl in einer O(1) Die Geschwindigkeit ist konstant, außer während der nächtlichen Neuindizierung der Tabelle, bei der gewartet werden muss, bis die Wartung abgeschlossen ist, bevor Sie eine weitere zufällige Zeile erhalten können.

--Create a demo table with lots of random nonuniform data, big_data 
--is your huge table you want to get random rows from in constant time. 
drop table if exists big_data;  
CREATE TABLE big_data (id serial unique, some_data text );  
CREATE INDEX ON big_data (id);  
--Fill it with a million rows which simulates your beautiful data:  
INSERT INTO big_data (some_data) SELECT md5(random()::text) AS some_data
FROM generate_series(1,10000000);

--This delete statement puts holes in your index
--making it NONuniformly distributed  
DELETE FROM big_data WHERE id IN (2, 4, 6, 7, 8); 

--Do the nightly maintenance task on a schedule at 1AM.
drop table if exists big_data_mapper; 
CREATE TABLE big_data_mapper (id serial, big_data_id int); 
CREATE INDEX ON big_data_mapper (id); 
CREATE INDEX ON big_data_mapper (big_data_id); 
INSERT INTO big_data_mapper(big_data_id) SELECT id FROM big_data ORDER BY id;

--We have to use a function because the big_data_mapper might be out-of-date
--in between nightly tasks, so to solve the problem of a missing row, 
--you try again until you succeed.  In the event the big_data_mapper 
--is broken, it tries 25 times then gives up and returns -1. 
CREATE or replace FUNCTION get_random_big_data_id()  
RETURNS int language plpgsql AS $$ 
declare  
    response int; 
BEGIN
    --Loop is required because big_data_mapper could be old
    --Keep rolling the dice until you find one that hits.
    for counter in 1..25 loop
        SELECT big_data_id 
        FROM big_data_mapper OFFSET floor(random() * ( 
            select max(id) biggest_value from big_data_mapper 
            )
        ) LIMIT 1 into response;
        if response is not null then
            return response;
        end if;
    end loop;
    return -1;
END;  
$$; 

--get a random big_data id in constant time: 
select get_random_big_data_id(); 

--Get 1 random row from big_data table in constant time: 
select * from big_data where id in ( 
    select get_random_big_data_id() from big_data limit 1 
); 

   id                some_data              

 8732674  f8d75be30eff0a973923c413eaf57ac0  

--Get 4 random rows from big_data in constant time: 
select * from big_data where id in ( 
    select get_random_big_data_id() from big_data limit 3 
);

   id                some_data              

 2722848  fab6a7d76d9637af89b155f2e614fc96  
 8732674  f8d75be30eff0a973923c413eaf57ac0  
 9475611  36ac3eeb6b3e171cacd475e7f9dade56  

--Test what happens when big_data_mapper stops receiving 
--nightly reindexing.
delete from big_data_mapper where 1=1; 
select get_random_big_data_id();   --It tries 25 times, and returns -1
                                   --which means wait N minutes and try again.

Angepasst von: https://www.gab.lc/articles/bigdata_postgresql_order_by_random

Alternativ dazu, wenn das alles zu viel Arbeit ist.

Eine einfachere, gute Lösung für die konstante Zeit für die Auswahl einer zufälligen Zeile ist es, eine neue Spalte in der großen Tabelle mit dem Namen big_data . mapper_int mit einem eindeutigen Index nicht null machen. Jede Nacht wird die Spalte mit einer eindeutigen Ganzzahl zwischen 1 und max(n) zurückgesetzt. Um eine zufällige Zeile zu erhalten, "wählen Sie eine zufällige ganze Zahl zwischen 0 y max(id) " und geben die Zeile zurück, in der mapper_int das ist. Wenn es keine Zeile mit dieser ID gibt, weil sich die Zeile seit der Neuindizierung geändert hat, wird eine andere zufällige Zeile ausgewählt. Wenn eine Zeile zu big_data.mapper_int hinzugefügt wird, wird sie mit max(id) + 1 aufgefüllt.

Answer 4

Ab PostgreSQL 9.5 gibt es eine neue Syntax, um zufällige Elemente aus einer Tabelle zu erhalten:

SELECT * FROM mytable TABLESAMPLE SYSTEM (5);

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

Weitere Erläuterungen finden Sie in der Dokumentation: http://www.postgresql.org/docs/current/static/sql-select.html

Answer 5

Diejenige mit dem ORDER BY ist die langsamere.

select * from table where random() < 0.01; geht Datensatz für Datensatz durch und entscheidet, ob er zufällig gefiltert wird oder nicht. Dies wird sein O(N) weil es jeden Datensatz nur einmal überprüfen muss.

select * from table order by random() limit 1000; wird die gesamte Tabelle 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 der random() < 0.01 Eine davon ist, 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: Die Fisher-Yates-Mischung , die in O(N) . Die Implementierung der Zufallsgenerierung in SQL klingt allerdings nach einer ziemlichen Herausforderung.