[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).

[szopen]

Uprasza się o niezajeżdżanie serwera SQL zapytaniami w stylu podanego przez grzemacha (IMG:http://forum.php.pl/style_emoticons/default/smile.gif) 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 (IMG:http://forum.php.pl/style_emoticons/default/winksmiley.jpg) . 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 (IMG:http://forum.php.pl/style_emoticons/default/smile.gif) 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 (IMG:http://forum.php.pl/style_emoticons/default/smile.gif)

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