[MYSQL] Losowanie wyników Opcje

[Skie]

W taki sposób losuję, które rekordy z bazy danych mają być pobrane

Kod

$comrades = $db -> Execute("SELECT * FROM users WHERE id >= ".$sektor_id -> fields['id']." AND id <= ".$sektor_id -> fields['id']." + 2 ORDER BY rand() LIMIT 4");

Niestety ilość rekordów spełniających te kryteria wynosi 3, a LIMIT 4. W jaki sposób przerobić to by było to prawdziwe losowanie - tj. za każdym razem byłby losowany user z podanego przedziału id bez względu na poprzednie losowania (czyt. możliwe byłoby pobranie kilka razy tego samego usera).

[grzemach]

szczerze mówiąc do końca nie rozumiem co masz na myśli. Losowanie 4 użytkowników z bazy, gdy tylko 3 spełnia zależności? to tylko możesz kolejność ich zmienić, ale to już masz zrobione w tym zapytaniu. W jakim celu wykorzystujesz ten fragment 'id >= ".$sektor_id -> fields['id']." AND id <= ".$sektor_id -> fields['id']." + 2' Ja bym to zrobił po prostu:

Kod

$comrades = $db -> Execute("SELECT * FROM users ORDER BY rand() LIMIT 1");

I masz losowanie różnych użytkowników, nie ma możliwości aby za każdym razem był inny gdyż ich suma jest skończona a coś mi mówi że ilość wywoływań powyższego skryptu będzie większa niż ilość użytkowników.

[szopen]

Uprasza się o niezajeżdżanie serwera SQL zapytaniami w stylu podanego przez grzemacha Wszak dla każdego losowania biedna baza musi posortować wszytkie rekordy. I to za każdym razem! Przeszło mi przez myśl, że może to jakoś optymalizować. Sprawdziłem na bazie o 262885 rekordach -- wylosowanie jednej pozycji trwało średnio 10 sekund. Więc niezbyt ciekawie.

Problem sam w sobie jest ciekawy, więc postanowiłem się nieco pobawić. Zakładając że mamy MySQLa w wersji 5 możemy napisać sobie pomocne procedury składowane. W pierwszej wersji zakładamy, że istnieje jakiś unikalny `id` i nie ma "dziur", a jeśli nawet są, to nie mają one dużego znaczenia. Rozkład prawdopodobieństwa w przypadku z diurami nie jest jednostajny, czyli elementy znajdujące się na "krawędzi" dziury będą częściej losowane. Dlaczego? Bo odpowiada im więcej niż jedna wylosowana wartość.

Kod

DROP PROCEDURE IF EXISTS losuj1;

delimiter //

CREATE PROCEDURE losuj1( IN ileLosowac INT UNSIGNED)
BEGIN
   -- użytkownik o najwyższym ID
   DECLARE maxId INT UNSIGNED;

   -- tabelka przechowująca wylosowane identyfikatory
   DROP TEMPORARY TABLE IF EXISTS numbers;
   CREATE TEMPORARY TABLE numbers (`user_id` int unsigned not null) ENGINE=MEMORY;

   -- znajdź największy ID użytkownika
   SELECT MAX(`user_id`) FROM xxx INTO maxId;

   -- powtarzaj tyle razy, ile chcemy wyników
   WHILE ileLosowac > 0 DO
   BEGIN
      -- Wylosuj ID. UWAGA! Może on nie istnieć, dlatego dalej mamy >=
      DECLARE randomElement INT UNSIGNED;
      SELECT FLOOR( 1+ RAND()*maxId ) INTO randomElement;

      -- Dodaj do tabelki pierwszego usera o ID równym lub większym od wylosowanego
      INSERT INTO numbers SELECT `user_id` FROM xxx WHERE `user_id`>=randomElement LIMIT 1;

      -- Wylosowaliśmy kolejnego usera :) Zmniejsz ilość pzostałych do wylosowania
      SET ileLosowac = ileLosowac-1;
   END;
   END WHILE;

   -- Zwróć wylosowanych userów (zachowaj kolejność losowania)
   select xxx.* from numbers left join xxx on xxx.user_id=numbers.user_id;

   -- Jeśli kolejność nie ma znaczenia (w kolejności w jakiej są zapisani userzy) można użyć
   -- select * from numbers natural join xxx;

   -- Posprzątaj
   DROP TEMPORARY TABLE IF EXISTS numbers;
END;
//

delimiter;

Problem "dziur" możemy załatać ponownym losowaniem użytkownika, w przypadku gdy jego ID nie istnieje. Dalej nie jest to dobre rozwiązanie, gdyż teoretycznie może zdarzyć się sytuacja, w której ten sam nieistniejący `user_id` będzie losowany w nieskończoność. Bardziej realna wada -- przy "razdkich" danych (tj. duże dziury), będzie trzeba wykonać wiele losowań aby trafić w istniejący ID. Zmiany pojawiły się w okolicy pętli WHILE jednak dla czytelności wstawiam jeszcze raz pełny kod.

Kod

DROP PROCEDURE IF EXISTS losuj2;

delimiter //

CREATE PROCEDURE losuj2( IN ileLosowac INT UNSIGNED)
BEGIN
   -- użytkownik o najwyższym ID
   DECLARE maxId INT UNSIGNED;

   -- tabelka przechowująca wylosowane identyfikatory
   DROP TEMPORARY TABLE IF EXISTS numbers;
   CREATE TEMPORARY TABLE numbers (`user_id` int unsigned not null) ENGINE=MEMORY;

   -- znajdź największy ID użytkownika
   SELECT MAX(`user_id`) FROM xxx INTO maxId;

   -- powtarzaj tyle razy, ile chcemy wyników
   losowanieUsera: WHILE ileLosowac > 0 DO
   BEGIN
      DECLARE randomElement INT UNSIGNED;
      SELECT FLOOR( 1+ RAND()*maxId ) INTO randomElement;

      -- Dodaj do tabelki pierwszego usera o ID równym wylosowanemu (może takiego nie być!)
      INSERT INTO numbers SELECT `user_id` FROM xxx WHERE `user_id`=randomElement LIMIT 1;

      -- Jeśli nie ma usera o takim ID, losujemy jeszcze raz
      IF ROW_COUNT()=0 THEN ITERATE losowanieUsera; END IF;

      -- Wylosowaliśmy kolejnego usera :) Zmniejsz ilość pzostałych do wylosowania
      SET ileLosowac = ileLosowac-1;
   END;
   END WHILE;

   -- Zwróć wylosowanych userów (zachowaj kolejność losowania)
   select xxx.* from numbers left join xxx on xxx.user_id=numbers.user_id;

   -- Jeśli kolejność nie ma znaczenia (w kolejności w jakiej są zapisani userzy) można użyć
   -- select * from numbers natural join xxx;

   -- Posprzątaj
   DROP TEMPORARY TABLE IF EXISTS numbers;
END;
//

delimiter;

Ostatnia wersja, teoretycznie najlepsza, stosuje inne podejście. Wykorzystujemy tu frazę "LIMIT offset,1" w celu pobrania elementu o danym offsecie. Niestety MySQL nie umożliwia używania zmiennych w części LIMIT zapytania, więc musimy skorzystać z prepared statements, co nawet może nam wyjść na dobre . Zwróćcie uwagę na zmianę zakresu losowanych liczb -- teraz potrzebne są nam liczby z przedziału [0, count(*)) (czyli bez prawego końca), wcześniej potrzebowaliśmy [1, max(`user_id`)].

Kod

DROP PROCEDURE IF EXISTS losuj3;

delimiter //

CREATE PROCEDURE losuj3( IN ileLosowac INT UNSIGNED)
BEGIN
  -- użytkownik o najwyższym ID
  DECLARE itemCount INT UNSIGNED;

  -- tabelka przechowująca wylosowane identyfikatory
  DROP TEMPORARY TABLE IF EXISTS numbers;
  CREATE TEMPORARY TABLE numbers (`user_id` int unsigned not null) ENGINE=MEMORY;

  -- znajdź największy ID użytkownika
  SELECT count(*) FROM xxx INTO itemCount;

  -- przygotuj zapytanie do wywoływanie w pętli
  PREPARE stmt FROM "INSERT INTO numbers SELECT `user_id` FROM xxx LIMIT ?, 1";

  -- powtarzaj tyle razy, ile chcemy wyników
  WHILE ileLosowac > 0 DO
  BEGIN
     DECLARE randomOffset INT UNSIGNED;
     SELECT FLOOR( RAND()*itemCount ) INTO randomOffset;

     -- Dodaj użytkownika spod wylosowanego offsetu
     SET @a_hde9fhcdgva = randomOffset;
     EXECUTE stmt USING @a_hde9fhcdgva;

     -- Wylosowaliśmy kolejnego usera :) Zmniejsz ilość pzostałych do wylosowania
     SET ileLosowac = ileLosowac-1;
  END;
  END WHILE;
  DEALLOCATE PREPARE stmt;

  -- Zwróć wylosowanych userów (zachowaj kolejność losowania)
  select xxx.* from numbers left join xxx on xxx.user_id=numbers.user_id;

  -- Jeśli kolejność nie ma znaczenia (w kolejności w jakiej są zapisani userzy) można użyć
  -- select * from numbers natural join xxx;

  -- Posprzątaj
  DROP TEMPORARY TABLE IF EXISTS numbers;
END;
//

delimiter;

A teraz chwila prawdy -- testy Na sam początek wykonałem powyższe trzy punkty dla wcześniej wspomnienej tabeli z argumentem 100. Pierwsze dwie zwróciły wynik poniżej sekundy, natomiast trzecia dopiero po minucie. Dlaczego? Bo select dla dużej wartości OFFSETu w LIMIT działa wolno (przynajmniej na InnoDB).

Jeśli ktoś ma inne pomysły albo uwagi to śmiało

Ten post edytował szopen 31.08.2008, 15:52:06

[Skie]

Tylko teraz powstaje pytanie co jest bardziej wydajne i co mniej obciąży MySQL - Jeden z Twoich sposobów czy prosta funkcja while () zastosowana w PHP, losująca po 1 wyniku i dodająca ten wynik do tablicy?

[golaod]

No rzeczywiście w while wyciągnąć 30 tys. wyników wylosować je, przypisać do tablicy - nie wspominając, że baza musiała przekazać do php 30 tys. wyników... Pewnie jest znacznie wydajniejsze ;]

[szopen]

Tylko teraz powstaje pytanie co jest bardziej wydajne i co mniej obciąży MySQL - Jeden z Twoich sposobów czy prosta funkcja while () zastosowana w PHP, losująca po 1 wyniku i dodająca ten wynik do tablicy?

Jak pisałem na początku mojego posta, wylosowanie jednego usera taką "prostą funkcją" trwa na mojej tabelce ok 10 seknud. Razy ilość userów do wylosowania... odpowiedź oczywista co bardziej wydajne ;) Aczkolwiek może to się da jeszcze przyspieszyć stosując w szukaj1/szukaj2 Dynamic SQL...


---- edit

Poniżej wersja losująca unikalnych użytkowników. Stanowi ona wydajniejszą alternatywę dla zapytania w stylu:

[SQL] pobierz, plaintext 
SELECT * FROM xxx ORDER BY rand() LIMIT $mojLimit;
[SQL] pobierz, plaintext 

pod warunkiem, że tabela xxx jest duża (rzędu 100 000 rekordów), a wybieramy losowo małą ich ilość np. 500. Dla przykładu zapytanie (a) z limitem 1 dla bazy o 262885 trwało 1.20 sec podczas gdy (b) losuj2uniq(1) trwało 0.01 sec. Dla limitu 100 mamy: (a) 2.46 sec, (b) 0.11; 500: (a) 1.18, (b)0.72 ;ale już dla limit 1000: (a) 1.22 (b) 1.84

Kod

DROP PROCEDURE IF EXISTS losuj2uniq;

delimiter //

CREATE PROCEDURE losuj2uniq( IN ileLosowac INT UNSIGNED)
BEGIN
   -- użytkownik o najwyższym ID
   DECLARE maxId INT UNSIGNED;
   DECLARE CONTINUE HANDLER FOR SQLSTATE '23000' BEGIN SET ileLosowac = ileLosowac+1; END;

   -- tabelka przechowująca wylosowane identyfikatory
   DROP TEMPORARY TABLE IF EXISTS numbers;
   CREATE TEMPORARY TABLE numbers (`user_id` int unsigned not null primary key) ENGINE=MEMORY;

   -- znajdź największy ID użytkownika
   SELECT MAX(`user_id`) FROM xxx INTO maxId;

   -- powtarzaj tyle razy, ile chcemy wyników
   losowanieUsera: WHILE ileLosowac > 0 DO
   BEGIN
      DECLARE randomElement INT UNSIGNED;
      SELECT FLOOR( 1+ RAND()*maxId ) INTO randomElement;

      -- Dodaj do tabelki pierwszego usera o ID równym wylosowanemu (może takiego nie być!)
      INSERT INTO numbers SELECT `user_id` FROM xxx WHERE `user_id`=randomElement LIMIT 1;

      -- Jeśli nie ma usera o takim ID, losujemy jeszcze raz
      IF ROW_COUNT()=0 THEN ITERATE losowanieUsera; END IF;

      -- Wylosowaliśmy kolejnego usera :) Zmniejsz ilość pzostałych do wylosowania
      SET ileLosowac = ileLosowac-1;
   END;
   END WHILE;

   -- Zwróć wylosowanych userów (zachowaj kolejność losowania)
   select xxx.user_id from numbers left join xxx on xxx.user_id=numbers.user_id;

   -- Jeśli kolejność nie ma znaczenia (w kolejności w jakiej są zapisani userzy) można użyć
   -- select * from numbers natural join xxx;

   -- Posprzątaj
   DROP TEMPORARY TABLE IF EXISTS numbers;
END;
//

delimiter;

Ten post edytował szopen 1.09.2008, 15:45:51