Chcę losowy wybór wierszy w PostgreSQL, próbowałem tego:

select * from table where random() < 0.01;

Ale niektórzy inni polecają to:

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

Mam bardzo duży stół z 500 milionami rzędów, chcę, żeby był szybki.

Które podejście jest lepsze? Jakie są różnice? Jaki jest najlepszy sposób wyboru losowych wierszy?

Biorąc pod uwagę specyfikację (plus dodatkowe informacje w komentarzach),

• Masz kolumnę identyfikatora numerycznego (liczby całkowite) z niewielkimi (lub umiarkowanie małymi) przerwami.
• Oczywiście nie ma żadnych operacji zapisu.
• Twoja kolumna identyfikacyjna musi zostać zaindeksowana! Klucz podstawowy służy ładnie.

Poniższe zapytanie nie wymaga sekwencyjnego skanowania dużej tabeli, tylko skanowanie indeksu.

Najpierw uzyskaj oszacowania dla głównego zapytania:

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

Jedyną prawdopodobnie kosztowną częścią jest count(*)(dla dużych stołów). Biorąc pod uwagę powyższe specyfikacje, nie potrzebujesz go. Kosztorys będzie wystarczający, dostępny prawie za darmo ( szczegółowe wyjaśnienie tutaj ):

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

Tak długo, jak ctnie jest dużo mniejszy id_span, zapytanie będzie przewyższać inne podejścia.

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

• Generuj losowe liczby w idprzestrzeni. Masz „kilka luk”, więc dodaj 10% (wystarczająco, aby łatwo zakryć puste miejsca) do liczby wierszy do odzyskania.

• Każdą z nich idmożna wybrać wiele razy przypadkowo (choć jest to mało prawdopodobne przy dużej przestrzeni identyfikatora), więc zgrupuj wygenerowane liczby (lub użyj DISTINCT).

• Dołącz iddo dużego stołu. Powinno to być bardzo szybkie przy założonym indeksie.

• Na koniec przytnij nadwyżki id, które nie zostały zjedzone przez duplikaty i luki. Każdy rząd ma całkowicie taką samą szansę na wybranie.

Krótka wersja

Możesz uprościć to zapytanie. CTE w powyższym zapytaniu służy wyłącznie celom edukacyjnym:

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

Udoskonal za pomocą rCTE

Zwłaszcza jeśli nie masz pewności co do luk i szacunków.

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

Możemy pracować z mniejszą nadwyżką w zapytaniu podstawowym. Jeśli jest zbyt wiele luk, więc nie znajdziemy wystarczającej liczby wierszy w pierwszej iteracji, rCTE kontynuuje iterację z terminem rekurencyjnym. Wciąż potrzebujemy stosunkowo niewielkich przerw w przestrzeni ID lub rekursja może wyschnąć przed osiągnięciem limitu - lub musimy zacząć od wystarczająco dużego bufora, który nie pozwala na optymalizację wydajności.

Duplikaty są eliminowane przez UNIONw rCTE.

Zewnętrzne LIMITpowoduje, że CTE zatrzymuje się, gdy tylko mamy wystarczającą liczbę rzędów.

To zapytanie jest starannie opracowane, aby użyć dostępnego indeksu, wygenerować faktycznie losowe wiersze i nie zatrzymywać się, dopóki nie osiągniemy limitu (chyba że rekursja nie będzie sucha). Istnieje wiele pułapek, jeśli zamierzasz go przepisać.

Zawiń w funkcję

Do wielokrotnego użytku z różnymi parametrami:

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;

Połączenie:

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

Możesz nawet sprawić, by ten ogólny działał dla dowolnej tabeli: Weź nazwę kolumny PK i tabeli jako typ polimorficzny i użyj EXECUTE... Ale to wykracza poza zakres tego pytania. Widzieć:

• Refaktoryzuj funkcję PL / pgSQL, aby zwracać dane wyjściowe różnych zapytań SELECT

Możliwa alternatywa

JEŻELI twoje wymagania zezwalają na identyczne zestawy dla powtarzanych połączeń (a mówimy o powtarzanych połączeniach), rozważyłbym widok zmaterializowany . Wykonaj powyższe zapytanie raz i zapisz wynik w tabeli. Użytkownicy otrzymują quasi-losowy wybór z prędkością błyskawicy. Odśwież swój losowy wybór w odstępach czasu lub wybranych wydarzeniach.

Wprowadzono Postgres 9.5 TABLESAMPLE SYSTEM (n)

Gdzie njest procent. Instrukcja:

BERNOULLII SYSTEMmetody próbkowania każdego przyjmować jeden argument, który stanowi frakcję tabeli w próbce wyrażono jako procent między 0 a 100 . Ten argument może być dowolnym realwyrażeniem wartościowanym.

Odważny nacisk moje. Jest bardzo szybki , ale wynik nie jest dokładnie losowy . Instrukcja ponownie:

SYSTEMSposób jest znacznie szybszy niż BERNOULLImetoda w przypadku małych procenty próbkowania jest określony, ale może powrócić do mniej wybranych losowo stół w wyniku grupowania efekty.

Liczba zwracanych wierszy może się znacznie różnić. W naszym przykładzie, aby uzyskać około 1000 wierszy:

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

Związane z:

• Szybki sposób na sprawdzenie liczby wierszy tabeli w PostgreSQL

Lub zainstaluj dodatkowy moduł tsm_system_rows, aby dokładnie uzyskać liczbę żądanych wierszy (jeśli jest ich wystarczająco dużo) i umożliwić wygodniejszą składnię:

SELECT * FROM big TABLESAMPLE SYSTEM_ROWS(1000);

Szczegółowe informacje można znaleźć w odpowiedzi Evana .

Ale to wciąż nie jest przypadkowe.

Możesz sprawdzić i porównać plan wykonania obu za pomocą

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

Szybki test na dużym stole ¹ pokazuje, że ORDER BYpierwszy sortuje cały stół, a następnie wybiera pierwsze 1000 przedmiotów. Sortowanie dużej tabeli nie tylko czyta tę tabelę, ale obejmuje również odczytywanie i zapisywanie plików tymczasowych. where random() < 0.1Tylko skanuje całą tabelę raz.

W przypadku dużych tabel może to nie być pożądane, ponieważ nawet jedno pełne skanowanie tabeli może potrwać długo.

Trzecia propozycja byłaby

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

Ten zatrzymuje skanowanie tabeli, jak tylko zostanie znalezione 1000 wierszy, i dlatego wraca wcześniej. Oczywiście to trochę zmniejsza losowość, ale być może jest to wystarczające w twoim przypadku.

Edycja: Oprócz tych rozważań możesz sprawdzić już zadane pytania. Użycie zapytania [postgresql] randomzwraca sporo trafień.

• szybki losowy wybór wiersza w Postgres
• Jak odzyskać losowe wiersze danych z tabeli postgreSQL?
• postgres: pobierz losowe wpisy z tabeli - zbyt wolno

I powiązany artykuł o depezie opisujący kilka innych podejść:

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

¹ „duży” jak w „cała tabela nie zmieści się w pamięci”.

posgresql order by random (), wybierz wiersze w losowej kolejności:

select your_columns from your_table ORDER BY random()

kolejność postgresql losowo () z wyraźnym:

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

zamówienie postgresql według losowego limitu jednego wiersza:

select your_columns from your_table ORDER BY random() limit 1

Począwszy od PostgreSQL 9.5, dostępna jest nowa składnia przeznaczona do pobierania losowych elementów z tabeli:

SELECT * FROM mytable TABLESAMPLE SYSTEM (5);

Ten przykład da ci 5% elementów z mytable.

Zobacz więcej wyjaśnień w tym poście na blogu: http://www.postgresql.org/docs/current/static/sql-select.html

Ten z ORDER BY będzie wolniejszy.

select * from table where random() < 0.01;zapisuje rekord po rekordzie i decyduje o losowym filtrowaniu go lub nie. Stanie się tak, O(N)ponieważ wystarczy sprawdzić każdy rekord tylko raz.

select * from table order by random() limit 1000;posortuje cały stół, a następnie wybierze pierwsze 1000. Oprócz magii voodoo za kulisami, kolejność jest O(N * log N).

Minusem tego random() < 0.01jest to, że otrzymasz zmienną liczbę rekordów wyjściowych.

Uwaga: istnieje lepszy sposób na tasowanie zestawu danych niż sortowanie losowe: losowanie Fisher-Yates , które jest uruchamiane O(N). Implementacja przetasowania w SQL wydaje się jednak sporym wyzwaniem.

Oto decyzja, która działa dla mnie. Myślę, że to bardzo proste do zrozumienia i wykonania.

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;

Jeśli wiesz, ile wierszy chcesz, sprawdź tsm_system_rows.

tsm_system_rows

moduł udostępnia metodę próbkowania tabeli SYSTEM_ROWS, której można użyć w klauzuli TABLESAMPLE komendy SELECT.

Ta metoda próbkowania tabeli przyjmuje pojedynczy argument liczby całkowitej, który jest maksymalną liczbą wierszy do odczytania. Wynikowa próbka zawsze będzie zawierała dokładnie tyle wierszy, chyba że tabela nie zawiera wystarczającej liczby wierszy, w którym to przypadku wybrana jest cała tabela. Podobnie jak wbudowana metoda próbkowania SYSTEM, SYSTEM_ROWS wykonuje próbkowanie na poziomie bloku, dzięki czemu próbka nie jest całkowicie losowa, ale może podlegać efektom grupowania, zwłaszcza jeśli wymagana jest tylko niewielka liczba wierszy.

Najpierw zainstaluj rozszerzenie

CREATE EXTENSION tsm_system_rows;

Twoje zapytanie

SELECT *
FROM table
TABLESAMPLE SYSTEM_ROWS(1000);

Jeśli chcesz tylko jeden wiersz, możesz użyć obliczenia offsetwyprowadzonego z count.

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

Możliwa jest odmiana zmaterializowanego widoku „Możliwa alternatywa” nakreślonego przez Erwina Brandstettera .

Powiedz na przykład, że nie chcesz duplikatów zwracanych losowych wartości. Musisz więc ustawić wartość logiczną w tabeli podstawowej zawierającej (nielosowy) zestaw wartości.

Zakładając, że jest to tabela wejściowa:

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

W ID_VALUESrazie potrzeby wypełnij tabelę. Następnie, zgodnie z opisem Erwina, utwórz zmaterializowany widok, który ID_VALUESraz losuje tabelę:

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

Zauważ, że zmaterializowany widok nie zawiera użytej kolumny, ponieważ szybko stanie się nieaktualna. Widok nie musi także zawierać innych kolumn, które mogą znajdować się w id_valuestabeli.

W celu uzyskania (i „zużywać”) wartości losowych, wymaga modernizacji-ZWROTU o id_valueswybranie id_valuesz id_values_randomizedz łączeniem i zastosowanie odpowiednich kryteriów uzyskać tylko istotne możliwości. Na przykład:

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;

Zmień LIMITw razie potrzeby - jeśli potrzebujesz tylko jednej losowej wartości naraz, zmień LIMITna 1.

Przy odpowiednich indeksach id_valuesuważam, że UPDATE-RETURNING powinien być wykonywany bardzo szybko przy niewielkim obciążeniu. Zwraca losowe wartości z jedną bazą danych w obie strony. Kryteria dla „kwalifikujących się” wierszy mogą być tak złożone, jak to konieczne. Nowe wiersze można dodawać do id_valuestabeli w dowolnym momencie i będą one dostępne dla aplikacji, gdy tylko zmaterializowany widok zostanie odświeżony (co może być prawdopodobnie uruchomione poza godzinami szczytu). Tworzenie i odświeżanie zmaterializowanego widoku będzie powolne, ale trzeba go wykonać tylko wtedy, gdy nowe identyfikatory zostaną dodane do id_valuestabeli.

Jedna lekcja z mojego doświadczenia:

offset floor(random() * N) limit 1nie jest szybszy niż order by random() limit 1.

Myślałem, że offsetpodejście będzie szybsze, ponieważ powinno zaoszczędzić czas sortowania w Postgres. Okazuje się, że nie było.

Dodaj kolumnę o nazwie rz typem serial. Index r.

Załóżmy, że mamy 200 000 wierszy, wygenerujemy liczbę losową n, gdzie 0 n<<= 200 000.

Wybierz wiersze za pomocą r > n, posortuj je ASCi wybierz najmniejszy.

Kod:

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

Kod jest zrozumiały. Podzapytanie w środku służy do szybkiego oszacowania liczby wierszy tabeli z https://stackoverflow.com/a/7945274/1271094 .

Na poziomie aplikacji musisz ponownie wykonać instrukcję, jeśli n> liczba wierszy lub musisz wybrać wiele wierszy.

Wiem, że jestem trochę spóźniony na imprezę, ale właśnie znalazłem to niesamowite narzędzie o nazwie pg_sample :

pg_sample - wyodrębnij mały, przykładowy zestaw danych z większej bazy danych PostgreSQL, zachowując spójność referencyjną.

Próbowałem tego z bazą danych o wielkości 350 mln wierszy i było to naprawdę szybkie, nie wiem o losowości .

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