January 25th, 2007 by depesz | Tags: | 8 comments »
Did it help? If yes - maybe you can help me?

czy stanęliście kiedyś przed problemem wylosowania rekordu z tabeli? dowolnego rekordu?
oczywistym pomysłem jest:

# SELECT * FROM tabelka ORDER BY random() LIMIT 1;

no ale to jest wolne. wymaga posortowania całej tabeli. co w najlepszym układzie ma złożoność "n log n".
przykładowo u mnie na testowej tabelce trwało to 90 sekund! (1.7 miliona rekordów).
no nie za dobrze.
niektórzy mogą sugerować takie rozwiązanie:

  1. znajdź maksymalne
  2. SELECT * FROM tabelka WHERE id <= random() * maksymalne_id limit 1;

na oko jest ok. tzn. akurat nie jest, bo random jest funkcją volatile, i trzeba by raczej … WHERE id <= (select random() * maksymalne_id) LIMIT 1, ale to już szczegół.
czemu to jest złe?
bo wprowadza pewien istotny problem. jeśli numeracja pola id w naszej tabelce zawiera dziury (czyli jest takie id, które jest większe od minimalnego i mniejsze od maksymalnego, dla którego nie ma rekordu) – to te losowane rekordy wcale nie będą dobrze losowane.
jako ekstremalny przykład (ale dobrze pokazujący rzeczywistość) podajmy tabelkę z dwoma rekordami, o id odpowiednio: 1 i 100. rekord z id = 1 będzie wypadał 99 razy częściej niż rekord z id = 100!.
cóż więc pozostaje? siąść i płakać?
nie.
można użyć inteligencji. czyli funkcji/procedury.
przykładowo taka funkcja:

CREATE OR REPLACE FUNCTION random_record() RETURNS tabelka AS $BODY$
DECLARE
    id_min INT8;
    id_max INT8;
    range INT8;
    temp_id INT8;
    temprec RECORD;
BEGIN
    SELECT min(id) INTO id_min FROM tabelka;
    SELECT max(id) INTO id_max FROM tabelka;
    range:= 1 + ( id_max - id_min );
    LOOP
        temp_id := id_min + (random() * range::float8)::INT8;
        SELECT * INTO temprec FROM tabelka WHERE id = temp_id;
        IF found THEN
            RETURN temprec;
        END IF;
    END LOOP;
END;
$BODY$ language 'plpgsql';

co ona robi?zwraca losowy rekord. całkowicie losowy – każdy rekord ma te same szanse bycia wylosowanym.
warunki brzegowe? pole id musi być unikatowe (szokujące, nie?). no i: im więcej dziur w numeracji tym wolniej działa. ale co znaczy wolniej?
ta moja testowa tabelka ma takie dane:

# select min(id), max(id), count(*) from tabelka;
 min |   max    |  count
-----+----------+---------
   3 | 36574227 | 1721217
(1 row)

czyli jak widać – dziur jest sporo. w szczególności – dziur jest 21 razy więcej niż istniejących rekordów!
przypomnę, że

select * from tabelka order by random() limit 1;

działało na tej tabelce w około 90 sekund.
ile czasu zajmuje to funkcji?
6 kolejnych wywołań. czasy odpowiednio: 124.700, 141.442, 201.708, 94.413, 145.128, 110.076. milisekund!
jak widać – jest szybko.
problemem tej funkcji jest to, że teoretycznie może się zdarzyć, że nigdy się nie skończy. ale w/g mnie jest to gdybanie. zresztą – zawsze można dorobić warunek, że jeśli np. wykonano już 1000 strzałów niecelnych, to zwróćmy pierwszy rekord z brzegu.
i już.
czy można to jakoś dopalić?
tak.
jeśli wiecie, że tabelka w której szukacie ma dużo dziur, to dodajcie do niej jedno pole:

create sequence random_thing_seq;
alter table tabelka add column random_thing int8;
alter table tabelka alter column random_thing set default nextval('random_thing_seq');
update tabelka set random_thing = nextval('random_thing_seq') where random_thing is null;
alter table tabelka alter column random_thing set not null;
create unique index ui_random_thing on tabelka (random_thing);

i potem używajcie w funkcji random_thing a nie id.
cel ćwiczenia?
jak sie pojawi za dużo dziur w numeracji (random_thing też będzie miał dziury) to zawsze możecie:

update tabelka set random_thing = nextval('random_thing_seq');

i już dziur nie ma,
a ponieważ random_thing nie jest do niczego innego używane – jest to w pełni bezpieczne.
oczywiście po takim update'cie dobrze jest zrobić vacuum'a. a najlepiej vacuum full'a.

  1. 8 comments

  2. # slaweks
    Jan 28, 2007

    Ciekawy artykuł.
    Dwie kwestie do funkcji:
    1) Czy w definicji funkcja linia:
    “range:= 1+( id_max – id_min );”
    nie powinna być bez dodawania 1 ?
    2) Linie
    SELECT min(id) INTO id_min FROM tabelka;
    SELECT max(id) INTO id_max FROM tabelka;
    lepiej zapisać:
    SELECT max(id),min(id) INTO id_max,id_min FROM tabelka;

  3. # Acid
    Jul 10, 2007

    hm,.. wlasnie probuje zmodyfikowac random_record aby moza bylo w nim podac ilosc zwracanych elementow

    http://phpfi.com/248703

    nie za bardzo wiem czy/jak do temprec dodawac wiecej rekordów ;/ baze mam bez dziur, wiec nie musze sie martwic o nieznalezienie jakiegos rekordu

    moglbys pomoc? podac jakas wskazowke?

  4. Jul 10, 2007

    musisz zrobić “returns setof words” i zwracać rekordy przez “return next;”

    niedługo będzie post znowu o losowaniu rekordów 🙂 tyle, że po angielsku i z kilkoma przykładami więcej.

  5. # Acid
    Jul 10, 2007

    ok dziala http://phpfi.com/248716

    co prawda dla 1000 rekordów czeka sie 5sek…

    no ale wszystkiego miec nie mozna, wkoncu to robi te 1000 selectów ;]

  6. Feb 23, 2009

    A może zrobić to na poziomie PHP? Czy jakiegokolwiek innego języka skryptowego a nie obciążać bazę?

    http://www.chemikk.pl/wpis/44/Losowy%20rekord%20tabeli%20z%20MySQL

  7. Feb 23, 2009

    @Chemikk:
    możesz. tę pętlę która tam jest możesz wykonać w czymkolwiek poza bazą. ale obciążenie bazy będzie najprawdopodobniej większe ze względu na dodatkowy narzut przesyłania danych i zapytań tam i z powrotem.

    zobaczyłem co masz na stronie – fajnie, ale wszystkie te sposoby wymagają skanowania sekwencyjnego z tabeli, co oznacza, że dla dużych tabel będą relatywnie wolne.

  8. Aug 24, 2009

    @depesz
    W sumie późno może pisze, ale teraz zauważyłem, że odpisałeś. Widocznie mam za małe doświadczenie z bazami danych, bo przynajmniej przy moich testach (1000 zapytań takich, na małą bazę danych) to dawało i tak najlepsze rozwiązania.

  9. Feb 6, 2010

    http://blog.piklus.pl/entry/44/Losowy%20rekord%20tabeli%20z%20MySQL

    Podaje nowy uaktualniony link 🙂

Sorry, comments for this post are disabled.