C, PHP, VB, .NET

Дневникът на Филип Петров


* Извеждане на няколко произволни реда

Публикувано на 17 май 2012 в раздел Бази от Данни.

Вече разгледахме методи за извеждане на един произволен ред от таблица. Понякога обаче ние се нуждаем от повече. Например "последни 10 статии", "последни 100 влизания в системата" и т.н. Затова в настоящата статия ще направя сравнение между методи за извеждане на множество от произволни редове. Ще се фокусираме върху сравнение между оптимизирания JOIN метод (който даде най-добри резултати при извеждането на един ред от таблица), метода с произволно id в WHERE и стандартния ORDER BY RAND().

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

Ще използваме примерната база от данни World и по-специално нейната таблица city, която има 4079 реда. Създаваме 3 съхранени процедури. Test1 се базира на класическия ORDER BY RAND() метод. Test2 се базира на метода "произволно id в WHERE". При него създаваме временна MEMORY (записана в паметта) таблиза от произволни id и търсим по тях. При Test6 използваме модифицирания JOIN метод:

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

CREATE TABLE row_ids(
  id INT(11)
)ENGINE = Memory;
DELIMITER //
CREATE PROCEDURE test2(tests INT, rows INT)
BEGIN
  DECLARE rows_counter INT;
  label1: LOOP
    SET tests = tests - 1;
    IF tests > 0 THEN
     SET rows_counter = rows;
     SELECT MAX(id) INTO @maxid FROM city;
     WHILE(rows_counter>0)
     DO
        INSERT INTO row_ids(id)
        VALUES (CEIL(RAND()*@maxid));
        SET rows_counter = rows_counter-1;
     END WHILE;
     SELECT name FROM city
     WHERE id IN (SELECT id FROM row_ids);
     TRUNCATE TABLE row_ids;
     ITERATE label1;
    END IF;
    LEAVE label1;
  END LOOP label1;
END//
DELIMITER ;

DELIMITER //
CREATE PROCEDURE test6(tests INT, rows INT)
BEGIN
  label1: LOOP
    SET tests = tests - 1;
    IF tests > 0 THEN
     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 rows) AS tmp 
          ON tmp.num = city.id;
     ITERATE label1;
    END IF;
    LEAVE label1;
  END LOOP label1;
END//
DELIMITER ;

Резултати

Резултатите от тестовете са показателни:

CALL test1(1000, 1);
Query OK, 0 rows affected (4.31 sec)

CALL test2(1000, 1);
Query OK, 0 rows affected (3.53 sec)

CALL test6(1000, 1);
Query OK, 0 rows affected (0.69 sec)

CALL test1(1000, 10);
Query OK, 0 rows affected (5.92 sec)

CALL test2(1000, 10);
Query OK, 0 rows affected (8.58 sec)

CALL test6(1000, 10);
Query OK, 0 rows affected (4.01 sec)

CALL test1(1000, 100);
Query OK, 0 rows affected (50.69 sec)

CALL test2(1000, 100);
Query OK, 0 rows affected (37.78 sec)

CALL test6(1000, 100);
Query OK, 0 rows affected (50.97 sec)

CALL test1(1000, 1000);
Query OK, 0 rows affected (10 min 2.53 sec)

CALL test2(1000, 1000);
Query OK, 0 rows affected (7 min 6.89 sec)

CALL test6(1000, 1000);
Query OK, 0 rows affected (9 min 54.92 sec)

Съвсем ясно се вижда, че първоначалната значителна преднина на test6 (модифицирания JOIN метод) се губи много бързо. Докато при извеждането на 10 произволни реда все още има някаква (но вече не голяма) преднина, то при 100 произволни реда вече тестовете са с изравнена бързина. Това се потвърждава и от теста с 1000 реда, при който разликите наистина са в рамките на нормалното отклонение.

Колкото до test2 - там нещата изглеждат странно. При тестовете с 1 и 10 реда виждаме, че метода определено губи. При увеличаване на броя редове обаче метода започва да печели, при това значимо.

Разлики между методите

Трябва сериозно да се отбележи една много важна разлика в резултатните таблици (не същината на алгоритъма) между двата метода - ORDER BY RAND() LIMIT X връща точно X различни реда (т.е. не са напълно произволни, а са зависими един от друг), докато оптимизирания JOIN метод може да върне и повтарящи се редове (имаме независимост между произволните редове). Ето пример за това:

SELECT DISTINCT name FROM city 
ORDER BY RAND() LIMIT 1000;
...
1000 rows in set (0.02 sec)

SELECT DISTINCT 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 1000) AS tmp 
     ON tmp.num = city.id;
...
861 rows in set (0.00 sec)

Виждате, че при оптимизирания JOIN метод се получиха 139 повторения, докато при ORDER BY RAND() нито едно. Същото ще се получи и при test2 метода - при него е възможно дублирането на редове.

Другата, наистина много важна разлика е, че JOIN метода и метода с произволно id в WHERE имат съществена нужда от поредни идентификационни номера без дупки! При ORDER BY RAND() това не е така. Ако ние имаме нужда от изтриване на редове от таблицата, то поддържането на поредни идентификационни номера не е никак приятна, нито пък препоръчителна операция (особено ако числата са по първичен ключ).

(Неуспешен) Опит за оптимизация на test2

Знаем, че в редица ситуации използването на EXISTS вместо IN може да доведе до подобрение. Да проверим. Модифицираме test2 по следния начин (продължаваме да имаме нужда от MEMORY таблица с име row_ids):

DELIMITER //
CREATE PROCEDURE test2_with_exists(tests INT, rows INT)
BEGIN
  DECLARE rows_counter INT;
  label1: LOOP
    SET tests = tests - 1;
    IF tests > 0 THEN
     SET rows_counter = rows;
     SELECT MAX(id) INTO @maxid FROM city;
     WHILE(rows_counter>0)
     DO
        INSERT INTO row_ids(id)
        VALUES (CEIL(RAND()*@maxid));
        SET rows_counter = rows_counter-1;
     END WHILE;
     SELECT name FROM city
     WHERE EXISTS(
	    SELECT * FROM row_ids
	    WHERE row_ids.id = city.id
	   );
     TRUNCATE TABLE row_ids;
     ITERATE label1;
    END IF;
    LEAVE label1;
  END LOOP label1;
END//
DELIMITER ;

Получаваме следните резултати:

CALL test2_with_exists(1000,1);
Query OK, 0 rows affected (3.25 sec)

CALL test2_with_exists(1000,10);
Query OK, 0 rows affected (8.23 sec)

CALL test2_with_exists(1000,100);
Query OK, 0 rows affected (39.70 sec)

CALL test2_with_exists(1000,1000);
Query OK, 0 rows affected (7 min 5.08 sec)

Виждаме, че разликите са незначителни. Върху тази примерна таблица IN и EXISTS дават напълно сходни резултати.

Заключение

Когато очакваме извеждане на резултат, то обикновено ние не се интересуваме от повтарящи се редове, а напротив - не ги искаме. Поради тази причина при извикване на повече от 10 произволни реда ще се окаже, че ORDER BY RAND() е по-добрия метод.

Когато очакваме наистина няколко произволни реда, а не различни (зависими от предишните) такива, то може да използвате JOIN метода, като преди това трябва да сте сигурни, че в реда няма дупки между идентификационните номера. Ако има такива, то ще се наложи да ги пренаредите с UPDATE заявка, която при всички положения ще е много тежка операция (допълнително ще трябва да се погрижите за AUTO_INCREMENT стойността, която ще трябва да се намали).

Ако имате поредни идентификатори без дупки и желаете МНОГО (десетки, стотици и най-вече хиляди) произволни редове, тогава се замислете за метода с "произволно id в WHERE". Кога подобно нещо би ви трябвало в реална ситуация? Това вече е друг въпрос.

 



2 коментара


  1. Защо просто не ползваме класическия метод:

    SELECT id,name FROM city
    ORDER BY RAND() LIMIT 1000;

    скоростта му е доста прилична.

Добави коментар

Адресът на електронната поща няма да се публикува


*