W dniu 2012-04-21 16:08, M.M. pisze:
> Hey
>
> Moje pytanie jest proste. Jak efektywnie wybrać losowy
> rekord (ewentualnie kilka losowych) dużej tabeli w sqlu?
>
> Sztuczki tego typu:
> SELECT * FROM table ORDER BY rand LIMIT kilka
> zdaje się że przeglądają całą tabelę, a to jest niedopuszczalne.
>
> Pozdrawiam

Taki pomysł "z czapki":
Dodaj sobie dodatkowe pole RND, z góry wypełnij je wartościami
losowymi typu double z przedziału <0.0-1.0)
Jak przewidujesz bardzo dużo rekordów - być może warto rozważyć
dwa double

Zakładasz indeks.

Potem trzaskasz zapytania w rodzaju
select limit 1 where RND<=random()
(przy pechu może się zdarzyć, że wyskoczy 0, warto zadbać,
by w tabeli pojawił się rekordy brzegowe RND = 0.0 i 1.0)

Losowanie nie jest tu idealnie dokładne,
rekordy nie mają dokładnie takiego samego prawdopodobieństwa wybrania
- ale w wielu wypadkach w ogóle nas to nie boli, nie wiemy z góry, które to.
Za to przy joinach masz trochę łatwiej, np.
możesz wykonać sumę z trzech pól z różnych tabel i podzielić przez
3 - i znów masz liczbę losową o równomiernym rozkładzie,
dajesz limit 1. Tyle, że tu już jest trochę problem z brakiem indeksu.

Dodając nowe rekordy się nie przejmujesz tym, ile jest
już w tabeli, zawsze po prostu losujesz wartość.
Podobnie nie przejmujesz się, że powstaną dziury przy usuwaniu.
Problem będzie dopiero, jak usuniesz rekordy bezpośrednio
wg. warunków skonstruowanych wprost o kolumnę RND, ale
chyba nikt Cię do tego nie zmusza ?

do góry

zażółcony <r...@c...pl> napisał(a):

> W dniu 2012-04-21 16:08, M.M. pisze:
> > Hey
> >
> > Moje pytanie jest proste. Jak efektywnie wybrać losowy
> > rekord (ewentualnie kilka losowych) dużej tabeli w sqlu?
> >
> > Sztuczki tego typu:
> > SELECT * FROM table ORDER BY rand LIMIT kilka
> > zdaje się że przeglądają całą tabelę, a to jest niedopuszczalne.
> >
> > Pozdrawiam
>
> Taki pomysł "z czapki":
> Dodaj sobie dodatkowe pole RND, z góry wypełnij je wartościami
> losowymi typu double z przedziału <0.0-1.0)
> Jak przewidujesz bardzo dużo rekordów - być może warto rozważyć
> dwa double
>
> Zakładasz indeks.
>
> Potem trzaskasz zapytania w rodzaju
> select limit 1 where RND<=random()

Nie zadziała. Gdy rekord z małą wartością pola RND będzie się
pojawiał pierwszy w kolejności przeglądania to on zdecydowanie częściej
będzie się wyświetlał. Rekordowi pobranemu trzeba nadać nową losową
wartość:

Może tak:

rnd = rand();
rekord = MIN( T.rnd );
rekord.rnd = rand();

1) Nie powinno być kłopotów przy złączeniach
2) Można założyć index na T.rnd
3) Nie ma problemów z usuwaniem i "dziurami"
4) Rozkład... właśnie nie mam pewności jaki jest rozkład.

Pozdrawiam


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

AK <n...@n...com> napisał(a):

> Użytkownik " M.M." <m...@N...gazeta.pl> napisał:
>
> > No tak, dotarłem do tego, ale zdaje się że to zapytanie
> > jeździ po całej tabeli?
> > SELECT column FROM table ORDER BY RANDOM() LIMIT 1
>
> "Teoretycznie" wcale nie musi.
Zobaczmy. Tabela 100tys rekordów. Jeden rekord niecałe 300 bajtów.

Zapytanie 1)
SELECT * FROM test_rand OFFSET RANDOM() * (SELECT COUNT(*) FROM test_rand)
LIMIT 1;
Czasy wykonania:
54 ms.
33 ms.
41 ms.
41 ms.

Zapytanie 2)
SELECT * FROM test_rand ORDER BY RANDOM() LIMIT 1;
78 ms.
72 ms.
72 ms.
74 ms.

Zapytanie 3)
SELECT * FROM test_rand OFFSET RANDOM() * 100000 LIMIT 1;
33 ms.
32 ms.
27 ms.
31 ms.


Zapytanie 4)
SELECT * FROM test_rand ORDER BY test_rand.id LIMIT 1 // id to big-integer
63 ms.
63 ms.
62 ms.
66 ms.

Zapytanie 5)
SELECT * FROM test_rand ORDER BY test_rand.data3 LIMIT 1 // data3 to var char
92 ms.
90 ms.
82 ms.
84 ms.

Zapytanie 4 z indeksem btree na id)
SELECT * FROM test_rand ORDER BY test_rand.id LIMIT 1
37 ms.
27 ms.
53 ms.
23 ms.

Zapytanie 5 z indeksem btree na data3)
SELECT * FROM test_rand ORDER BY test_rand.data3 LIMIT 1
42 ms.
21 ms.
32 ms.
37 ms.

Zapytanie 6, idnex hash na data)
SELECT * FROM test_rand ORDER BY test_rand.data = random() * 100000 LIMIT 1 //
data to integer
124 ms.
163 ms.
104 ms.
106 ms.


Zapytanie 7, index hash na data)
SELECT * FROM test_rand ORDER BY test_rand.data = 56381 LIMIT 1
73 ms.
73 ms.
76 ms.
83 ms.

Zapytanie 7, bez indexu na data)
SELECT * FROM test_rand ORDER BY test_rand.data = 56381 LIMIT 1
102 ms.
75 ms.
85 ms.
72 ms.

Hmmmm wyniki trochę zdumiewające. 100tys rekordów a wszystkie
czasy w granicach 100ms na wolnym laptopie. Indeksy nie pomagają
w porażający sposób. Zapytanie nr. dwa nie działa tak wolno jak
się obawiałem. Może trzeba po prostu tego używać i nie kombinować
za dużo?

Pozdrawiam


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

M.M. <m...@N...gazeta.pl> napisał(a):
> AK <n...@n...com> napisał(a):
> Hmmmm wyniki trochę zdumiewające.

Chyba mam rozwiązanie. Poniższa procedura w psqlu na tabeli 3mln rekordów
działa średnio 40 razy szybciej niż sztuczka z sortowaniem po random.
Średni czas to 40ms na tabeli z 3mln rekordów. Chyba niezły wynik jak
na laptopa z jakimś tanim twardym dyskiem.

Dla losowego rekordu ze złączonych tabel też powinno zadziałać.
Pozdrawiam

create function get_ranodm() RETURNS record AS $$
DECLARE
r record;
BEGIN
SELECT * INTO r FROM test_rand ORDER BY random_field LIMIT 1;
UPDATE test_rand SET random_field=random()*1000000000 WHERE id = r.id;
return r;
END;
$$ LANGUAGE plpgsql;

select get_ranodm();



--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

W dniu 2012-04-23 18:49, M.M. pisze:
> zażółcony<r...@c...pl> napisał(a):
>
>> W dniu 2012-04-21 16:08, M.M. pisze:
>>> Hey
>>>
>>> Moje pytanie jest proste. Jak efektywnie wybrać losowy
>>> rekord (ewentualnie kilka losowych) dużej tabeli w sqlu?
>>>
>>> Sztuczki tego typu:
>>> SELECT * FROM table ORDER BY rand LIMIT kilka
>>> zdaje się że przeglądają całą tabelę, a to jest niedopuszczalne.
>>>
>>> Pozdrawiam
>>
>> Taki pomysł "z czapki":
>> Dodaj sobie dodatkowe pole RND, z góry wypełnij je wartościami
>> losowymi typu double z przedziału<0.0-1.0)
>> Jak przewidujesz bardzo dużo rekordów - być może warto rozważyć
>> dwa double
>>
>> Zakładasz indeks.
>>
>> Potem trzaskasz zapytania w rodzaju
>> select limit 1 where RND<=random()
>
> Nie zadziała. Gdy rekord z małą wartością pola RND będzie się

A fakt, kopnąłem sie ... Pierwotnie
była relacja w drugą stronę, sorry:
select limit 1 where RND>=random()
miał być jeszcze
order by RND
Wtedy idzie.


> pojawiał pierwszy w kolejności przeglądania to on zdecydowanie częściej
> będzie się wyświetlał. Rekordowi pobranemu trzeba nadać nową losową
> wartość:
>
> Może tak:
>
> rnd = rand();
> rekord = MIN( T.rnd );
> rekord.rnd = rand();

>
> 1) Nie powinno być kłopotów przy złączeniach
> 2) Można założyć index na T.rnd
> 3) Nie ma problemów z usuwaniem i "dziurami"
> 4) Rozkład... właśnie nie mam pewności jaki jest rozkład.

Rozkład jest ok, jak generator losowy jest ok :)

do góry

zażółcony <r...@c...pl> napisał(a):

> > 1) Nie powinno być kłopotów przy złączeniach
> > 2) Można założyć index na T.rnd
> > 3) Nie ma problemów z usuwaniem i "dziurami"
> > 4) Rozkład... właśnie nie mam pewności jaki jest rozkład.
>
> Rozkład jest ok, jak generator losowy jest ok :)
Właśnie tego nie umiem matematycznie dowieść :)
Pozdrawiam




--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

M.M. <m...@N...gazeta.pl> napisał(a):

> zażółcony <r...@c...pl> napisał(a):
>
> > > 1) Nie powinno być kłopotów przy złączeniach
> > > 2) Można założyć index na T.rnd
> > > 3) Nie ma problemów z usuwaniem i "dziurami"
> > > 4) Rozkład... właśnie nie mam pewności jaki jest rozkład.
> >
> > Rozkład jest ok, jak generator losowy jest ok :)
> Właśnie tego nie umiem matematycznie dowieść :)

Mamy n rekordów. Rekordom przypisaliśmy losową
liczbę z rozkładu równomiernego. Wybieramy
rekord z najmniejszą liczbą. Rozkład był
równomierny, więc każdy rekrod ma równą szansę
dostać liczbę najmniejszą co za tym idzie
zostać wylosowany. Czyli na początku jest ok.

Potem rekordy się podzieliły na dwa zbiory. Jeden
zbiór zawiera n-1 rekordów a drugi 1 rekrod,
ten wylosowany. Rekord wylosowany otrzymuje
na nowo losową liczbę. Szansa że otrzyma mniejszą
liczbę niż najmniejsza liczba ze zbioru n-1 wynosi
1/n, a więc szansa zdarzenia przeciwnego 1-1/n.
Więc szansa że za drugim razem zostanie wylosowany
ten sam rekord z n rekordów wynosi właśnie 1/n.
Pozostałe rekordy mają liczby z rozkładu równomiernego,
a więc wylosowania jednego z pozostałych też
wynosi 1/n.

Czyli na początku szansa wylosowania każdego
rekordu wynosi 1/n, a po losowaniu też wynosi
1/n. Czyżby to był koniec dowodu?

Pozdrawiam


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry