Jak pobrać wydajną, prostą próbkę losową w języku SQL? Wspomniana baza danych korzysta z MySQL; moja tabela ma co najmniej 200 000 wierszy, a potrzebuję prostej losowej próbki około 10 000.

„Oczywista” odpowiedź brzmi:

SELECT * FROM table ORDER BY RAND() LIMIT 10000

W przypadku dużych tabel jest to zbyt wolne: wywołuje RAND()każdy wiersz (który już umieszcza go w pozycji O (n)) i sortuje je, tworząc w najlepszym przypadku O (n lg n). Czy istnieje sposób, aby to zrobić szybciej niż O (n)?

Uwaga : Jak wskazuje Andrew Mao w komentarzach, jeśli używasz tego podejścia na serwerze SQL, powinieneś użyć funkcji T-SQL NEWID(), ponieważ RAND () może zwrócić tę samą wartość dla wszystkich wierszy .

EDYCJA: 5 LAT PÓŹNIEJ

Ponownie natknąłem się na ten problem z większą tabelą i ostatecznie użyłem wersji rozwiązania @ ignorant, z dwoma poprawkami:

• Wypróbuj wiersze, aby uzyskać 2-5x żądany rozmiar próbki, aby tanio ORDER BY RAND()
• Zapisz wynik w RAND()indeksowanej kolumnie przy każdym wstawieniu / aktualizacji. (Jeśli zestaw danych nie wymaga dużej ilości aktualizacji, może być konieczne znalezienie innego sposobu, aby zachować aktualność tej kolumny).

Aby pobrać próbkę tabeli zawierającą 1000 pozycji, liczę wiersze i próbuję wynik do średnio 10000 wierszy z kolumną frozen_rand:

SELECT COUNT(*) FROM table; -- Use this to determine rand_low and rand_high

  SELECT *
    FROM table
   WHERE frozen_rand BETWEEN %(rand_low)s AND %(rand_high)s
ORDER BY RAND() LIMIT 1000

(Moja rzeczywista implementacja wymaga więcej pracy, aby upewnić się, że nie zaniżam próbki, i aby ręcznie zawijać rand_high, ale podstawową ideą jest „losowe zmniejszenie liczby N do kilku tysięcy”).

Chociaż wymaga to pewnych poświęceń, pozwala mi na próbkowanie bazy danych za pomocą skanowania indeksu, dopóki nie będzie wystarczająco mała, aby ORDER BY RAND()ponownie.

Jest tutaj bardzo interesująca dyskusja na ten temat: http://www.titov.net/2005/09/21/do-not-use-order-by-rand-or-how-to-get-random-rows-from-table/

Myślę, że bez żadnych założeń dotyczących tabeli, twoje rozwiązanie O (n lg n) jest najlepsze. Chociaż w rzeczywistości z dobrym optymalizatorem lub nieco inną techniką zapytanie, które podajesz, może być nieco lepsze, O (m * n) gdzie m to liczba żądanych losowych wierszy, ponieważ nie musiałoby to koniecznie sortować całej dużej tablicy , może po prostu wyszukać najmniejsze m razy. Ale dla rodzaju liczb, które opublikowałeś, i tak m jest większe niż lg n.

Trzy założenia, które możemy wypróbować:

1. w tabeli znajduje się unikalny, indeksowany klucz podstawowy

2. liczba losowych wierszy, które chcesz zaznaczyć (m) jest znacznie mniejsza niż liczba wierszy w tabeli (n)

3. unikalny klucz podstawowy to liczba całkowita w zakresie od 1 do n bez przerw

Przy tylko założeniach 1 i 2 myślę, że można to zrobić w O (n), chociaż będziesz musiał zapisać cały indeks do tabeli, aby pasował do założenia 3, więc niekoniecznie jest to szybkie O (n). Jeśli możemy DODATKOWO założyć coś fajnego w tabeli, możemy wykonać zadanie w O (m log m). Założenie 3 byłoby łatwą, przyjemną dodatkową właściwością do pracy. Z ładnym generatorem liczb losowych, który gwarantowałby brak duplikatów podczas generowania m liczb w rzędzie, możliwe byłoby rozwiązanie O (m).

Biorąc pod uwagę te trzy założenia, podstawową ideą jest wygenerowanie m unikalnych liczb losowych od 1 do n, a następnie wybranie wierszy z tymi kluczami z tabeli. Nie mam teraz mysql ani nic przed sobą, więc w nieco pseudokodzie wyglądałoby to mniej więcej tak:

create table RandomKeys (RandomKey int)
create table RandomKeysAttempt (RandomKey int)

-- generate m random keys between 1 and n
for i = 1 to m
  insert RandomKeysAttempt select rand()*n + 1

-- eliminate duplicates
insert RandomKeys select distinct RandomKey from RandomKeysAttempt

-- as long as we don't have enough, keep generating new keys,
-- with luck (and m much less than n), this won't be necessary
while count(RandomKeys) < m
  NextAttempt = rand()*n + 1
  if not exists (select * from RandomKeys where RandomKey = NextAttempt)
    insert RandomKeys select NextAttempt

-- get our random rows
select *
from RandomKeys r
join table t ON r.RandomKey = t.UniqueKey

Jeśli naprawdę martwisz się o wydajność, możesz rozważyć wykonanie losowego generowania kluczy w jakimś języku proceduralnym i wstawienie wyników do bazy danych, ponieważ prawie wszystko inne niż SQL prawdopodobnie byłoby lepsze w rodzaju pętli i generowaniu liczb losowych .

Myślę, że najszybszym rozwiązaniem jest

select * from table where rand() <= .3

Oto dlaczego uważam, że to powinno wystarczyć.

• Stworzy losową liczbę dla każdego wiersza. Liczba zawiera się w przedziale od 0 do 1
• Ocenia, czy wyświetlić ten wiersz, jeśli wygenerowana liczba zawiera się w przedziale od 0 do 0,3 (30%).

Zakłada się, że rand () generuje liczby w równomiernym rozkładzie. To najszybszy sposób, aby to zrobić.

Widziałem, że ktoś polecił to rozwiązanie i został zestrzelony bez dowodu ... oto, co bym na to powiedział -

• To jest O (n), ale sortowanie nie jest wymagane, więc jest szybsze niż O (n lg n)

• mysql jest bardzo zdolny do generowania liczb losowych dla każdego wiersza. Spróbuj tego -

  wybierz rand () z INFORMATION_SCHEMA.TABLES limit 10;

Ponieważ ta baza danych to mySQL, jest to właściwe rozwiązanie.

Najwyraźniej w niektórych wersjach SQL jest TABLESAMPLEpolecenie, ale nie we wszystkich implementacjach SQL (zwłaszcza w Redshift).

http://technet.microsoft.com/en-us/library/ms189108(v=sql.105).aspx

Po prostu użyj

WHERE RAND() < 0.1 

aby uzyskać 10% rekordów lub

WHERE RAND() < 0.01 

uzyskać 1% rekordów itp.

Szybciej niż ZAMÓWIENIE LASEM ()

Przetestowałem tę metodę jako znacznie szybszą niż ORDER BY RAND(), dlatego działa w czasie O (n) i robi to imponująco szybko.

Z http://technet.microsoft.com/en-us/library/ms189108%28v=sql.105%29.aspx :

Wersja inna niż MSSQL - nie testowałem tego

SELECT * FROM Sales.SalesOrderDetail
WHERE 0.01 >= RAND()

Wersja MSSQL:

SELECT * FROM Sales.SalesOrderDetail
WHERE 0.01 >= CAST(CHECKSUM(NEWID(), SalesOrderID) & 0x7fffffff AS float) / CAST (0x7fffffff AS int)

Spowoduje to wybranie ~ 1% rekordów. Więc jeśli potrzebujesz dokładnej liczby procent lub rekordów do wybrania, oszacuj swój procent z pewnym marginesem bezpieczeństwa, a następnie losowo wyciągnij nadmiar rekordów z wynikowego zestawu, używając droższej ORDER BY RAND()metody.

Nawet szybciej

Udało mi się ulepszyć tę metodę jeszcze bardziej, ponieważ miałem dobrze znany indeksowany zakres wartości kolumn.

Na przykład, jeśli masz indeksowaną kolumnę z równomiernie rozłożonymi liczbami całkowitymi [0..max], możesz użyć jej do losowego wybrania N małych przedziałów. Zrób to dynamicznie w swoim programie, aby uzyskać inny zestaw dla każdego uruchomienia zapytania. Ten podzbiór będzie O (N) , który może być o wiele rzędów wielkości mniejszy niż pełny zestaw danych.

W moim teście zredukowałem czas potrzebny do uzyskania 20 (z 20 milionów) przykładowych rekordów z 3 minut przy użyciu funkcji ORDER BY RAND () do 0,0 sekundy !

Chcę zaznaczyć, że wszystkie te rozwiązania wydają się próbkować bez wymiany. Wybranie górnych K wierszy z losowego sortowania lub dołączenie do tabeli zawierającej unikalne klucze w losowej kolejności spowoduje wygenerowanie losowej próbki bez zastępowania.

Jeśli chcesz, aby Twoja próbka była niezależna, musisz pobrać próbkę z wymianą. Zobacz pytanie 25451034, aby zapoznać się z jednym przykładem, jak to zrobić za pomocą JOIN w sposób podobny do rozwiązania user12861. Rozwiązanie jest napisane dla T-SQL, ale koncepcja działa w każdej bazie danych SQL.

Zaczynając od obserwacji, że możemy pobrać identyfikatory tabeli (np. Count 5) na podstawie zbioru:

select *
from table_name
where _id in (4, 1, 2, 5, 3)

możemy dojść do wyniku, że gdybyśmy mogli wygenerować ciąg "(4, 1, 2, 5, 3)", mielibyśmy bardziej wydajny sposób niż RAND().

Na przykład w Javie:

ArrayList<Integer> indices = new ArrayList<Integer>(rowsCount);
for (int i = 0; i < rowsCount; i++) {
    indices.add(i);
}
Collections.shuffle(indices);
String inClause = indices.toString().replace('[', '(').replace(']', ')');

Jeśli identyfikatory mają luki, początkowa lista arraylista indicesjest wynikiem zapytania sql dotyczącego identyfikatorów.

Jeśli potrzebujesz dokładnie mwierszy, realistycznie wygenerujesz podzbiór identyfikatorów poza SQL. Większość metod wymaga w pewnym momencie wybrania pozycji „nth”, a tabele SQL w rzeczywistości nie są tablicami. Założenie, że klucze są kolejne, aby po prostu łączyć losowe liczby między 1 a liczbą, również jest trudne do spełnienia - na przykład MySQL nie obsługuje go natywnie, a warunki blokady są ... trudne .

Oto rozwiązanie czasowe O(max(n, m lg n))i O(n)przestrzenne, zakładające zwykłe klucze BTREE:

1. Pobierz wszystkie wartości kolumny klucza tabeli danych w dowolnej kolejności do tablicy w swoim ulubionym języku skryptowym w O(n)
2. Przeprowadzić Fisher-Yates shuffle, zatrzymując się po mswapach, i wyodrębnić subarray [0:m-1]wϴ(m)
3. „Połącz” podtablicę z oryginalnym zbiorem danych (np. SELECT ... WHERE id IN (<subarray>)) W formacieO(m lg n)

Każda metoda, która generuje losowy podzbiór poza SQL, musi mieć co najmniej taką złożoność. Łączenie nie może być szybsze niż w O(m lg n)przypadku BTREE (więc O(m)twierdzenia są fantastyczne w przypadku większości silników), a tasowanie jest ograniczone poniżej ni m lg nnie wpływa na asymptotyczne zachowanie.

W pseudokodzie Pythonic:

ids = sql.query('SELECT id FROM t')
for i in range(m):
  r = int(random() * (len(ids) - i))
  ids[i], ids[i + r] = ids[i + r], ids[i]

results = sql.query('SELECT * FROM t WHERE id IN (%s)' % ', '.join(ids[0:m-1])

Wybierz 3000 losowych rekordów w Netezza:

WITH IDS AS (
     SELECT ID
     FROM MYTABLE;
)

SELECT ID FROM IDS ORDER BY mt_random() LIMIT 3000

Próbować

SELECT TOP 10000 * FROM table ORDER BY NEWID()

Czy przyniosłoby to pożądane rezultaty, nie będąc zbyt skomplikowanym?

W niektórych dialektach, takich jak Microsoft SQL Server, PostgreSQL i Oracle (ale nie MySQL lub SQLite), możesz zrobić coś takiego

select distinct top 10000 customer_id from nielsen.dbo.customer TABLESAMPLE (20000 rows) REPEATABLE (123);

Powodem, dla którego nie wystarczy (10000 rows)obejść się bez tego, topjest to, że TABLESAMPLElogika daje bardzo niedokładną liczbę wierszy (np. 75% tej, czasami 1,25% razy więcej), więc chcesz przesadzić i wybrać dokładną liczbę, którą chcesz. Służy REPEATABLE (123)do dostarczania losowego ziarna.

Może mógłbyś to zrobić

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