C, PHP, VB, .NET

В тази статия ще разгледам няколко различни алгоритми за прочитане на псевдопроизволен ред от таблица в MySQL, които намерих в интернет. Фокусирах се само и единствено върху чисто SQL методи. Съществуват и други, които комбинират генериране на произволно число в приложението и изпращане на готови стойности към базата от данни.

База от данни

За тестова таблица ще използваме „city“ от базата от данни „world“ (примерна тестова база от данни в сайта на MySQL). В нея първичен ключ е колона „id“, в който стойностите са поредни (AUTO_INCREMENT) и БЕЗ ДУПКИ (няма изтрити стойности). Последното е важно, защото повечето от методите разчитат именно на това свойство, за да се възползват от допълнителна бързина. Целта ни е с една заявка да извлечем едно произволно име (колона name) от базата от данни. Някои от методите позволяват и повече.

Test 1: Класически метод

Този метод се споменава в документацията на MySQL. В него се прави следното:

SELECT name FROM city 
ORDER BY RAND() LIMIT 1;

Той създава по едно произволно число за всеки ред от таблицата и след това сортира редовете спрямо тези произволни числа. Правейки LIMIT 1 ние взимаме само първия ред от резултатната таблица. Ако искате повече, то просто увеличете числото.

Класическият метод работи без да има значение какви са стойностите в колоната id. Използва се индекс по колоната „name“ и има „Using temporary; Using filesort“.

Test 2: Произволно id в WHERE

Методът е взаимстван от блога на Akinas. В тази заявка е много важно id да са поредни и „без дупки“. Първо се взима броя на редовете в таблицата (който се приема и за най-голямата стойност на id), след това се взима първото id, което е след тази стойност.

SELECT RAND()*COUNT(*) 
INTO @randid FROM city;

SELECT id, name FROM city 
WHERE id >= @randid
LIMIT 1;

С този метод НЕ можете да вземете повече от един произволен ред наведнъж. Също така е много важно броя на редовете в таблицата да отговаря на най-голямото id в нея, а също така разчита на равномерното разпределение на id-та (т.е. може да има „дупки“, но те също трябва да са равномерно разпределени).

Test 3: Произволно id в WHERE с непоредни числа

Методът отново е взаимстван от блога на Akinas. Този метод е абсолютно същия както предишния, но с тази разлика, че няма нужда по колоната „id“ да имаме поредни стойности от 1 до N, а може да са в произволен интервал от A до B:

SELECT FLOOR(MIN(id)+ RAND()*(MAX(id)-MIN(id)+1)) 
INTO @randid FROM city;

SELECT name
FROM city
WHERE id >= @randid
LIMIT 1;

Както и в предишния метод – тук силно се разчита на добро равномерно разпределение на id-тата. Липсата на „дупки“ между тях ще дава правилни резултати. Отново не можем да взимаме повече от един произволен ред наведнъж.

Test 4: ORDER BY RAND() с отрязване на част от таблицата

Този метод е предложен от Josh Hartman и се основава на намаляване на броя на редовете, които трябва да се сортират чрез ORDER BY RAND().

SELECT name FROM city 
WHERE RAND()<(SELECT ((1/COUNT(*))*10) FROM city) 
ORDER BY RAND() 
LIMIT 1;

Както се вижда от кода – в WHERE клаузата се взима произволно число, което се проверява дали е по-малко от дадена референтна стойност. Числото 1/count(*) е умножено по 10, за да не стане референтната стойност прекалено малка, което да създаде по-голям риск от „пропускане“ (вижте забележката след параграфа). Ако искате да се върнат N реда, то трябва да направите „…(N/COUNT(*))*10…“ и „…LIMIT N“. Накрая се извършва „ORDER BY RAND()“, за да не се дава предимство на по-малките id-та спрямо по-големите.

ВАЖНО: Този метод НЕ гарантира връщане на резултат! Винаги съществува възможност, макар и в случая минимална, RAND() да връща винаги стойности над референтната, с което накрая да се окаже, че не е върнат никакъв ред.

Test 5: JOIN метод

Това е класически начин за изваждане на произволен ред от таблица. Взима се оригиналната таблица и към нея по „id“ се присъединява едно единствено произволно число, което е от 1 до максималното в таблицата city:

SELECT city.name
FROM city JOIN
     (SELECT CEIL(RAND() * (SELECT MAX(id) FROM city)) AS id) AS tmp
     ON city.id >= tmp.id
LIMIT 1;

Задължително в този метод е id-тата да са поредни започващи от 1 нататък и да няма „дупки“ или поне да са равномерно разпределени. С този метод НЕ можете да вземете повече от един произволен ред накуп – увеличаването на стойността в LIMIT ще върне поредни редове, а не произволни!

Test 6: JOIN метод чрез използване на локална променлива

Предложен в MySQLDiary.com,  това е подобрение на предишния метод, тъй като позволява да взимаме повече от един произволен ред (увеличавайки стойността след LIMIT във вътрешната таблица):

SELECT city.name
FROM city JOIN
     (SELECT CEIL(RAND() * (SELECT MAX(id) FROM city)) AS num, @num:=@num+1 
      FROM (SELECT @num:=0) AS a, city LIMIT 1) AS tmp 
     ON tmp.num = city.id;

При така показания метод е задължително да НЯМА дупки.

Тест 7: OFFSET метод

Предложен от electrictoolbox.com. Методът се състои в следната последователност:

1. Намираме общия брой на редовете в таблицата и го записваме в променлива;
2. Генерираме произволно число и го умножаваме по общия брой редове от таблицата;
3. Извличаме ред от таблицата чрез LIMIT 1 и OFFSET намереното в т.2 число.

Първият проблем идва в това, че не можем да подаваме променливи в LIMIT. Затова се налага да използваме подготвени заявки:

SELECT FLOOR(RAND()*COUNT(*)) INTO @count 
FROM city;

PREPARE stmt 
FROM 'SELECT name INTO @temp FROM city LIMIT 1 OFFSET ?';

EXECUTE stmt USING @count;

При този метод имаме едно голямо предимство – за разлика от всички алтернативни на ORDER BY RAND() методи тук въобще НЕ зависим от колоната id, т.е. няма проблем да има „дупки“ в нея. Недостатък е, че не може да извлича повече от един произволен ред в една заявка – налага се за n реда да изпълните n заявки (при ORDER BY RAND() не е така).

Тестова постановка

Създаваме 7 съхранени процедури, всяка от която съдържа по един от методите. Входния параметър на тази заявка е число, което има смисъла на „брой повторения“, които ще направим на метода:

DELIMITER //
CREATE PROCEDURE test1(tests INT)
BEGIN
  label1: LOOP
    SET tests = tests - 1;
    IF tests > 0 THEN
      SELECT name INTO @temp FROM city 
      ORDER BY RAND() LIMIT 1;
      ITERATE label1;
    END IF;
    LEAVE label1;
  END LOOP label1;
END//
DELIMITER ;

DELIMITER //
CREATE PROCEDURE test2(tests INT)
BEGIN
  label1: LOOP
    SET tests = tests - 1;
    IF tests > 0 THEN
      SELECT RAND()*COUNT(*) INTO @randid FROM city;
	  SELECT name INTO @temp FROM city 
      WHERE id >= @randid
      LIMIT 1;
      ITERATE label1;
    END IF;
    LEAVE label1;
  END LOOP label1;
END//
DELIMITER ;

DELIMITER //
CREATE PROCEDURE test3(tests INT)
BEGIN
  label1: LOOP
    SET tests = tests - 1;
    IF tests > 0 THEN
      SELECT FLOOR(MIN(id)+ RAND()*(MAX(id)-MIN(id)+1)) INTO @randid 
      FROM city;
      SELECT name INTO @temp FROM city
      WHERE id >= @randid
      LIMIT 1;
      ITERATE label1;
    END IF;
    LEAVE label1;
  END LOOP label1;
END//
DELIMITER ;

DELIMITER //
CREATE PROCEDURE test4(tests INT)
BEGIN
  label1: LOOP
    SET tests = tests - 1;
    IF tests > 0 THEN
      SELECT name INTO @temp FROM city 
      WHERE RAND()<(SELECT ((1/COUNT(*))*10) FROM city) 
      ORDER BY RAND() 
      LIMIT 1;
      ITERATE label1;
    END IF;
    LEAVE label1;
  END LOOP label1;
END//
DELIMITER ;

DELIMITER //
CREATE PROCEDURE test5(tests INT)
BEGIN
  label1: LOOP
    SET tests = tests - 1;
    IF tests > 0 THEN
     SELECT city.name INTO @temp
     FROM city JOIN 
          (SELECT CEIL(RAND() * (SELECT MAX(id) FROM city)) AS id) AS tmp
	      ON city.id >= tmp.id
      LIMIT 1;
      ITERATE label1;
    END IF;
    LEAVE label1;
  END LOOP label1;
END//
DELIMITER ;

DELIMITER //
CREATE PROCEDURE test6(tests INT)
BEGIN
  label1: LOOP
    SET tests = tests - 1;
    IF tests > 0 THEN
     SELECT city.name INTO @temp
     FROM city JOIN
          (SELECT CEIL(RAND() * (SELECT MAX(id) FROM city)) AS num, 
                  @num:=@num+1 
           FROM (SELECT @num:=0) AS a, city LIMIT 1) AS tmp 
          ON tmp.num = city.id;
     ITERATE label1;
    END IF;
    LEAVE label1;
  END LOOP label1;
END//
DELIMITER ;

DELIMITER //
CREATE PROCEDURE test7(tests INT)
BEGIN
  label1: LOOP
    SET tests = tests - 1;
    IF tests > 0 THEN
      SELECT FLOOR(RAND()*COUNT(*)) INTO @count FROM city;
      PREPARE stmt 
      FROM 'SELECT name INTO @temp FROM city LIMIT 1 OFFSET ?';
      EXECUTE stmt USING @count;
      ITERATE label1;
    END IF;
    LEAVE label1;
  END LOOP label1;
END//
DELIMITER ;

Забележете, че при извикването на всяка заявка се прави „SELECT name INTO @temp“, за да записваме върнатия произволен ред в променлива, вместо да го връщаме към приложението като резултатна таблица. Освен това обърнете специално внимание на test7 – при него беше много по-подходящо да изместим „PREPARE stmt…“ заявката извън тялото на цикъла. Нарочно това не е направено, за да не се дава предимство на метода спрямо останалите. Впрочем разликата не е значителна (в порядъка 2-3 секунди), но все пак така е правилно.

След това изпълняваме всяка една процедура два пъти, като между пусканията на всеки две различни процедури спираме MySQL сървъра (за да сме сигурни, че няма вътрешни оптимизации, които да променят резултата):

mysql> CALL test1(10000);
Query OK, 1 row affected (39.56 sec)

mysql> CALL test1(10000);
Query OK, 1 row affected (39.52 sec)

mysql> CALL test2(10000);
Query OK, 1 row affected (18.33 sec)

mysql> CALL test2(10000);
Query OK, 1 row affected (18.13 sec)

mysql> CALL test3(10000);
Query OK, 1 row affected (19.11 sec)

mysql> CALL test3(10000);
Query OK, 1 row affected (18.97 sec)

mysql> CALL test4(10000);
Query OK, 1 row affected (38.77 sec)

mysql> CALL test4(10000);
Query OK, 1 row affected (38.64 sec)

mysql> CALL test5(10000);
Query OK, 1 row affected (1.91 sec)

mysql> CALL test5(10000);
Query OK, 1 row affected (1.84 sec)

mysql> CALL test6(10000);
Query OK, 1 row affected (1.42 sec)

mysql> CALL test6(10000);
Query OK, 1 row affected (1.41 sec)

mysql> CALL test7(10000);
Query OK, 1 row affected (27.44 sec)

mysql> CALL test7(10000);
Query OK, 1 row affected (27.66 sec)

Ясно се вижда, че класическия метод (test1) и предложената модификация (test4) дават възможно най-лоши резултати. При това test4 не гарантира въобще, че ще се върне какъвто и да е резултат – затова директно можете да го отхвърлите като възможност.

Тестовете с произволно число в where (test2 и test3) стоят непосредствено след това, като са двойно по-бързи. Те от своя страна помежду си дават несъществена разлика в бързодействието. Това ни насочва към това да препоръчаме „по-сигурния“ от тях – test3.

Абсолютните фаворити са JOIN методите (test5 и test6). При това втория, който дава по-добри възможности, дава и по-добри резултати.

Колкото до test7 – той определено се справя много по-добре от test1, при това няма недостатъците на останалите тестове. За жалост при него не е възможно да се извлече повече от един ред накуп в една заявка.

Извод

При напълно разнородни данни, т.е. такива без никаква подредба по идентификатор, използвайте класическия метод (test1) когато искате да изкарате множество редове накуп или методът с offset (test7) когато искате да изкарате един единствен произволен ред.

При напълно подредени стойности по колоната id – ако например тя е primary key с auto_increment и няма изтрити редове, то JOIN методите са в пъти по-бързи! При тях втория (test6) е за предпочитане, тъй като позволява връщане на повече от един произволен ред в една заявка.

Ако все пак има „дупки“ в колоната „id“, но преценявате, че те са сравнително равномерно разпределени, то може да се възползвате и от методите с произволно число в where (test2 и test3). При тях по-добър, пък макар и минимално по-бавен, е test3. Спрямо тях обаче test5 е безспорен победител и фаворит за избор. Отново напомням, та макар и с риск да стана досаден, че при едно извикване на заявката можете да взимате само един произволен ред, а не множество такива (това е сериозен недостатък ако ви трябват няколко произволни реда и в такъв случай обезсмисля метода).

Не използвайте test4, тъй като той е сбъркан по дизайн и неефективен по бързодействие.

Нека синтезираме казаното и да определим подходящите методи за взимане на :

• Подредни числа, без дупки: test6
• Равномерно разпределени числа, но с дупки и при нужда само от един произволен ред: test 5
• Без каквато и да е подредба или неравномерно разпределени числа и при нужда само от един произволен ред: test7
• Без каквато и да е подредба или неравномерно разпределени числа и при нужда от повече от един произволен ред: test1

П.П. Всички тестове са проведени при InnoDB таблица. Ако използвате MyISAM таблица, то всички методи, които използват COUNT(*) – тестове 2, 4 и 7 – ще работят по-бързо, понеже в MyISAM броят на редовете в таблиците се кешира.

Задача: Прехвърлете данните от таблица city в MyISAM хранилище и проведете същите тестове.

П.П.2. Последна редакция на 09.05.2012г.