Il modo migliore per selezionare le righe casuali di PostgreSQL




performance random (8)

postgresql ordina per casuale (), seleziona le righe in ordine casuale: 

select your_columns from your_table ORDER BY random()

postgresql ordina per random () con un distinto: 

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

postgresql ordina per limite casuale una riga: 

select your_columns from your_table ORDER BY random() limit 1

Voglio una selezione casuale di righe in PostgreSQL, ho provato questo: 

select * from table where random() < 0.01;

Ma alcuni altri raccomandano questo: 

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

Ho un tavolo molto grande con 500 milioni di file, voglio che sia veloce.

Quale approccio è migliore? Quali sono le differenze? Qual è il modo migliore per selezionare le righe casuali?

È possibile esaminare e confrontare il piano di esecuzione di entrambi utilizzando 

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

Un rapido test su un grande tavolo 1 mostra che ORDER BY ordina prima la tabella completa e quindi preleva i primi 1000 elementi. L'ordinamento di una tabella di grandi dimensioni non solo legge quella tabella ma comporta anche la lettura e la scrittura di file temporanei. where random() < 0.1 esegue solo una scansione della tabella completa una volta sola.

Per le tabelle di grandi dimensioni questo potrebbe non essere ciò che si desidera, poiché anche una scansione completa della tabella potrebbe richiedere molto tempo.

Una terza proposta sarebbe 

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

Questo interrompe la scansione della tabella non appena sono state trovate 1000 righe e quindi torna prima. Ovviamente questo impallidisce un po 'la casualità, ma forse questo è abbastanza buono nel tuo caso.

Modifica: Oltre a queste considerazioni, è possibile verificare le domande già poste per questo. L'utilizzo della query [postgresql] random restituisce alcuni colpi in modo [postgresql] random .

E un articolo collegato di depez che delinea diversi altri approcci:

1 "grande" come in "il tavolo completo non si adatterà alla memoria".

Aggiungi una colonna chiamata r con tipo serial . Indice r .

Supponiamo di avere 200.000 righe, genereremo un numero casuale n , dove 0 < n <= 200, 000.

Seleziona le righe con r > n , ordinali ASC e seleziona il più piccolo.

Codice: 

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

Il codice è auto-esplicativo. La sottoquery al centro viene utilizzata per stimare rapidamente i conteggi delle righe della tabella da https://.com/a/7945274/1271094 .

Nel livello applicazione è necessario eseguire nuovamente l'istruzione se n > il numero di righe o se è necessario selezionare più righe.

Date le vostre specifiche (più informazioni aggiuntive nei commenti),

  • Hai una colonna ID numerica (numeri interi) con solo pochi (o moderatamente pochi) spazi vuoti.
  • Ovviamente nessuna o poche operazioni di scrittura.
  • La tua colonna ID deve essere indicizzata! Una chiave primaria serve bene.

La query seguente non richiede una scansione sequenziale della tabella grande, ma solo una scansione dell'indice.

Innanzitutto, ottieni le stime per la query principale: 

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

L'unica parte possibilmente costosa è il count(*) (per tabelle enormi). Date le specifiche sopra, non ne hai bisogno. Una stima andrà bene, disponibile quasi senza alcun costo ( spiegazione dettagliata qui ): 

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

Finché ct non è molto più piccolo di id_span , la query supererà gli altri approcci. 

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

  • Genera numeri casuali nello spazio id . Hai "poche lacune", quindi aggiungi il 10% (sufficiente per coprire facilmente gli spazi vuoti) al numero di righe da recuperare.

  • Ogni id può essere selezionato più volte per caso (anche se molto improbabile con un grande spazio id), quindi raggruppa i numeri generati (o usa DISTINCT ).

  • Unisciti agli id al grande tavolo. Questo dovrebbe essere molto veloce con l'indice in atto.

  • Infine, ritaglia i surplus id che non sono stati mangiati dai dotti e dagli spazi vuoti. Ogni riga ha una probabilità completamente uguale di essere selezionata.

Versione breve

Puoi semplificare questa query. Il CTE nella query sopra è solo per scopi didattici: 

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

Affina con rCTE

Soprattutto se non sei così sicuro di lacune e stime. 

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

Possiamo lavorare con un surplus più piccolo nella query di base. Se ci sono troppe lacune in modo da non trovare abbastanza righe nella prima iterazione, la rCTE continua ad iterare con il termine ricorsivo. Abbiamo ancora bisogno di un numero relativamente ridotto di spazi nello spazio ID o la ricorsione potrebbe esaurirsi prima che venga raggiunto il limite - oppure dobbiamo iniziare con un buffer sufficientemente grande che non consente di ottimizzare le prestazioni.

I duplicati vengono eliminati dall'UNION nella rCTE.

Il LIMIT esterno rende il CTE fermo non appena abbiamo abbastanza righe.

Questa query viene accuratamente elaborata per utilizzare l'indice disponibile, generare in realtà righe casuali e non fermarsi finché non rispettiamo il limite (a meno che la ricorsione non funzioni a secco). Ci sono un certo numero di insidie ​​qui se hai intenzione di riscriverlo.

Avvolgere in funzione

Per uso ripetuto con parametri variabili: 

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;

Chiamata: 

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

Potresti addirittura rendere questo generico funzionare per qualsiasi tabella: prendi il nome della colonna PK e della tabella come tipo polimorfo e usa EXECUTE ... Ma questo va oltre lo scopo di questa domanda. Vedere:

Alternativa possibile

SE i tuoi requisiti consentono serie identiche per chiamate ripetute (e stiamo parlando di chiamate ripetute) considererei una vista materializzata . Esegui sopra una query e scrivi il risultato su una tabella. Gli utenti ottengono una selezione quasi casuale alla velocità della luce. Aggiorna la scelta casuale a intervalli o eventi di tua scelta.

Postgres 9.5 introduce il TABLESAMPLE SYSTEM (n)

È molto veloce , ma il risultato non è esattamente casuale . Il manuale:

Il metodo SYSTEM è significativamente più veloce del metodo BERNOULLI quando vengono specificate piccole percentuali di campionamento, ma può restituire un campione meno casuale della tabella come risultato degli effetti di clustering.

E il numero di righe restituite può variare notevolmente. Per il nostro esempio, per ottenere circa 1000 righe, prova: 

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

Dove n è una percentuale Il manuale:

I metodi di campionamento BERNOULLI e SYSTEM accettano ciascuno un singolo argomento che è la frazione della tabella da campionare, espressa in percentuale tra 0 e 100 . Questo argomento può essere qualsiasi espressione valutata in modo real .

Grassetto enfasi mio.

Relazionato:

Oppure installa il modulo aggiuntivo tsm_system_rows per ottenere esattamente il numero di righe richieste (se ce ne sono abbastanza) e consenti la sintassi più comoda: 

SELECT * FROM big TABLESAMPLE SYSTEM_ROWS(1000);

Vedi la risposta di Evan per i dettagli.

Ma non è ancora esattamente casuale.

Ecco una decisione che funziona per me. Immagino che sia molto semplice da capire ed eseguire. 

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

Quello con l'ordine BY sarà il più lento.

select * from table where random() < 0.01; va registrato per record e decide di filtrarlo casualmente oppure no. Questo sarà O(N) perché deve solo controllare ogni record una volta.

select * from table order by random() limit 1000; sta per ordinare l'intero tavolo, quindi scegliere il primo 1000. A parte qualsiasi magia voodoo dietro le quinte, l'ordine di è O(N * log N) .

Lo svantaggio di quello random() < 0.01 è che otterrai un numero variabile di record di output.

Nota, c'è un modo migliore per mischiare un set di dati rispetto all'ordinamento casuale: The Fisher-Yates Shuffle , che viene eseguito in O(N) . Implementare lo shuffle in SQL sembra comunque una sfida.

So di essere un po 'in ritardo per la festa, ma ho appena trovato questo fantastico strumento chiamato pg_sample .

Ho provato questo con un database di 350M righe ed è stato molto veloce, non so sulla casualità . 

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

Una variante della vista materializzata "Possibile alternativa" delineata da Erwin Brandstetter è possibile.

Supponiamo, ad esempio, di non volere duplicati nei valori randomizzati che vengono restituiti. Quindi sarà necessario impostare un valore booleano sulla tabella primaria contenente il set di valori (non randomizzato).

Supponendo che questa sia la tabella di input: 

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

ID_VALUES tabella ID_VALUES secondo necessità. Quindi, come descritto da Erwin, crea una vista materializzata che randomizza la tabella ID_VALUES una volta: 

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

Si noti che la vista materializzata non contiene la colonna usata, perché questa diventerà presto obsoleta. Né la vista deve contenere altre colonne che possono trovarsi nella tabella id_values .

Per ottenere (e "consumare") valori casuali, utilizzare un UPDATE-RETURNING su id_values , selezionare id_values da id_values_randomized con un join e applicare i criteri desiderati per ottenere solo le possibilità rilevanti. Per esempio: 

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;

Cambia LIMIT se necessario: se hai solo bisogno di un valore casuale alla volta, modifica il LIMIT a 1 .

Con gli indici appropriati su id_values , credo che l'UPDATE-RETURNING dovrebbe essere eseguito molto rapidamente con poco carico. Restituisce valori randomizzati con un round-trip del database. I criteri per le righe "idonee" possono essere complessi come richiesto. È possibile aggiungere nuove righe alla tabella id_values in qualsiasi momento e diventeranno accessibili all'applicazione non appena viene aggiornata la vista materializzata (che probabilmente può essere eseguita in un momento non di punta). La creazione e l'aggiornamento della vista materializzata saranno lenti, ma deve essere eseguito solo quando nuovi ID vengono aggiunti alla tabella id_values .






sql   performance   postgresql   random  


random