Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / MySQL Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3 4   вперед  Ctrl      все
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
Arhat109
Member

Откуда: из СССР
Сообщений: 3282
miksoft,

Ну для себя - решил везде где можно использовать таблицу связей... в реальности она больше таблицы узлов раза в 3 для питовых задач (из моих)... а Мускуль вполне нормально переваривает таблицы в 10 миллионов записей, особенно таких (из трех полей)... там, кстати нет серъезного ограничения на множественность родителей узла. :)

Если не проходит вариант с таблицей (много сильно глубоких деревьев), то или вариант "а" с запросом через переменные или разбивка на несколько таблиц (где-то в ваших ссылках есть вполне нормальное описание про фиксированное вложение каталогов)...
12 июл 12, 18:32    [12859020]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
RXL
Member

Откуда:
Сообщений: 1600
miksoft
вроде бы, MySQL вообще не имеет специализированных решений и способов для хранения и обработки иерархических структур данных.


В ответвлении MariaDB есть "движок" для графов - OQGRAPH, но с готовые бинарники его включают не во все, т.к. он основан на boost довольно высокой версии. Кроме того, по отзывам пользователей, на больших масштабах (порядка млн узлов) скорость работы неудовлетворительная.
13 июл 12, 11:53    [12862015]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
miksoft
Member

Откуда:
Сообщений: 36314
Топик, в котором родилось решение для написания иерархических запросов.
http://www.sql.ru/forum/actualthread.aspx?bid=6&tid=984179
20 дек 12, 16:23    [13660966]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
Arhat109
Member

Откуда: из СССР
Сообщений: 3282
miksoft, пасибки. Поисследовал этот вопрос ишо раз.

Вот "тот самый" запрос о котором писал впервые тут 12858390 "поизвращавшись с переменными" (дали добро):

SELECT
  @idx := substring_index(@array, ',', 3) AS child
  , @array := CONCAT( REPLACE(@array, @idx, ''), (
      SELECT IFNULL(GROUP_CONCAT(CONCAT(',',`id`,',') SEPARATOR ''), '')
      FROM `tree`
      WHERE `parent_id` = REPLACE(@idx, ',', '')
  )) AS array
FROM (SELECT @array:=',9,') AS dummy
, `tree`
WHERE LENGTH(@array) > 0
;


Фактически он не отличается от решения bochkov'а, но работает чуть медленнее. Общий недостаток обоих решений - строковый результат и сложность (я бы сказал неудобство) его использования в дальнейшем. Феноменальные "тормоза" этого решения вызываются необходимостью подселекта на каждом шаге выполнения...

В ряде относительно простых случаев (ограничения на структуру таблицы), подходит вот такое "скоростное" решение:
SELECT
  ch.`id` AS child, ch.`parent_id` AS parent, ch.`level` AS level
  , @array := CONCAT(@array, CONCAT(',',ch.`id`,',')) AS array
FROM (SELECT @array:=',9,') AS dummy
, `tree1` AS ch  FORCE INDEX (level)
WHERE
  LOCATE(CONCAT(',',ch.`parent_id`,','), @array) > 0
;
--# индекс: `level` (`level`,`parent_id`,`id`) лучше делать единственным и первичным ключом таблицы
--# тогда можно не прибивать гвоздями...
--# В этом случае надо забыть про автоинтремент, требующий собственного отдельного индекса...


оно также НЕ избегает фулл-скана, но уже только индекса и НЕ содержит некешируемых подселектов... собственно никаких не содержит. Это вариант "чистого" курсора.
... 1. "поизвращавшись с переменными" ещё немного, можно во втором варианте также сделать удаление ненужных узлов из накапливаемого массива @array.
... 2. "поизвращавшись с переменными" можно слегка улучшить первый вариант, устранив подселект для конечных листьев, где он дает гарантированно пустой результат. Вообще-то их - много, и как правило больше чем рабочих веток.

Общий итог: нормального (на одном статическом запросе), полностью рабочего решения для деревьев с одним полем `parent_id` -- нет.
Или надо делать динамически вложенные join-ы
, или надо делать фулл-скан с подселектом, что очень медленно
, или надо специально готовить табличку
, или надо запрещать перенос старых узлов (с малым идентом), в новые и глубже вложенные ветки (с бОльшими идентами)...

Не надо ТАК делать.
Для себя - как вопрос "самообразования" - задача интересна, но и только. Везде где можно, заменил на нормальную и полноценную таблицу связи. Пусть уж жрет память, чем тормозит не по-детски.
24 дек 12, 07:49    [13674855]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
DBConstructor
Member [заблокирован]

Откуда: RU-SPE
Сообщений: 716
Никаких "фул сканов", выбираются только строки потомков. Результат в строковой переменной @branch, в виде идентификаторов всех членов ветви, разделенных запятой.

SET @branch='3';
SELECT @branch as branch
  FROM `Catalog`
  WHERE EXISTS (SELECT 
         @branch:=Concat_ws(',', @branch, group_concat(`ID`)) branch
       FROM `Catalog`
       WHERE Find_in_set(`ParentID`, @branch)
         AND NOT Find_in_set(`ID`, @branch)
       GROUP BY `ParentID`
       ORDER BY `branch` DESC LIMIT 1)
  ORDER BY `branch` DESC LIMIT 1;
19 фев 13, 19:13    [13950928]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
tanglir
Member

Откуда:
Сообщений: 30154
DBConstructor
Никаких "фул сканов", выбираются только строки потомков.
А разве Find_in_set умеет использовать индексы?
19 фев 13, 21:21    [13951378]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
DBConstructor
Member [заблокирован]

Откуда: RU-SPE
Сообщений: 716
tanglir
DBConstructor
Никаких "фул сканов", выбираются только строки потомков.
А разве Find_in_set умеет использовать индексы?


Извини, не понял вопроса. Причем тут индексы? Это один из вариантов, использующий строку в качестве хранения идентификаторов членов ветви. Но этот вариант, благодаря тому, что подзапрос с группировкой и объединением идентификаторов потомков перестает возвращать строки в случае, если идентификаторы всех членов ветви уже находятся в переменной @branch, не использует "фул скан" и выполняет ровно то количество итераций, которое необходимо для получения результата.
19 фев 13, 22:07    [13951498]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
tanglir
Member

Откуда:
Сообщений: 30154
DBConstructor, я имел в виду, что, хотя этот запрос может и не добраться до конца таблицы и тем самым "снаружи" фулскана, скорее всего, не получится, но подзапрос в EXISTS будет фулсканить таблицу `Catalog`, т.к. Find_in_set-у никакие индексы тут не помогут.
20 фев 13, 06:06    [13952565]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
DBConstructor
Member [заблокирован]

Откуда: RU-SPE
Сообщений: 716
tanglir, не вижу большой разницы между выборкой всех страниц индексов связывания двух таблиц с последующим совмещением этих индексов и последовательной проверкой значения одного поля одной таблицы с константной строкой.
Мне, почему-то даже кажется, что второе будет быстрее первого.
20 фев 13, 08:22    [13952671]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
Arhat109
Member

Откуда: из СССР
Сообщений: 3282
DBConstructor,

протестил:

1. Таблица 10 деревьев по 1 листу в уровне, всего 300 уровней (3000 записей всего!)
2. Решение Бочкова дает выборку от 0,5 до 1 сек.
3. Решение с составным индексом (моё тут последнее) дает 50-80мсек.
4. Ваше решение проработало больше (уже 705сек и ещё пашет)... сколько точно - не знаю.

как-то так. :)
20 фев 13, 22:37    [13957782]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
Arhat109
Member

Откуда: из СССР
Сообщений: 3282
Arhat109,

а конкретно, всё банально: подселект выполняется также как и в варианте Бочкова, только там есть ещё группировка и сортировка... и применить индексы - практически некуда.
20 фев 13, 23:03    [13957904]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
DBConstructor
Member [заблокирован]

Откуда: RU-SPE
Сообщений: 716
Arhat109
Arhat109,

а конкретно, всё банально: подселект выполняется также как и в варианте Бочкова, только там есть ещё группировка и сортировка... и применить индексы - практически некуда.


Нет, не банально! Простой пример:

DROP TABLE IF EXISTS `catalog`;
CREATE TABLE IF NOT EXISTS `catalog` (
    `id`    INT UNSIGNED NOT NULL AUTO_INCREMENT,
    `parent_id` INT UNSIGNED DEFAULT NULL,
    `status`    ENUM('USED', 'DELETED') DEFAULT 'USED' NOT NULL,
  CONSTRAINT `categories__pk` PRIMARY KEY (`id`)
);

DROP PROCEDURE IF EXISTS `fill__catalog`;
DELIMITER //
CREATE PROCEDURE `fill__catalog`(
    IN rowCount INT UNSIGNED)
  LANGUAGE SQL
  NOT DETERMINISTIC
  CONTAINS SQL
  SQL SECURITY INVOKER
BEGIN
  DECLARE i INT UNSIGNED DEFAULT 0;
  DECLARE ParentId INT UNSIGNED DEFAULT 0;
  REPEAT
    SET ParentId = (SELECT Round(Rand()*Max(`id`),0)
      FROM `catalog`
    );
    IF ParentId = 0 THEN
      SET ParentId = NULL;
    END IF;
    INSERT INTO `catalog` (`parent_id`) VALUES (ParentId);
    SET i = i + 1;
  UNTIL NOT i < rowCount END REPEAT;
END//
DELIMITER ;

CALL fill__catalog(3000);


Таким образом, получаем таблицу с произвольным уровнем вложения и произвольным количеством одноуровневых потомков одного предка. Если после заполнения таблицы у потомков не менялись предки на предков с идентификатором старше, чем идентификатор потомка, то следующий запрос дает результат за один проход и очень быстро:

SELECT @branch:=Concat_ws(',', @branch, c.`id`) branch
  FROM `catalog` c
  WHERE Find_in_set(c.`parent_id`, @branch)
    AND NOT Find_in_set(c.`id`, @branch)
  ORDER BY `branch` DESC LIMIT 1


Как видно, на моем домашнем железе запрос отработал за 16 миллисекунд.
/* 0 rows affected, 1 rows found. Duration for 1 query: 0,016 sec. */

Выводы?
21 фев 13, 16:26    [13962137]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
DBConstructor
Member [заблокирован]

Откуда: RU-SPE
Сообщений: 716
Надо только задать интересующих предков в переменной @branch. К примеру:
  SET @branch = '3';
21 фев 13, 16:32    [13962176]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
DBConstructor
Member [заблокирован]

Откуда: RU-SPE
Сообщений: 716
Arhat109
DBConstructor,

протестил:

1. Таблица 10 деревьев по 1 листу в уровне, всего 300 уровней (3000 записей всего!)
2. Решение Бочкова дает выборку от 0,5 до 1 сек.
3. Решение с составным индексом (моё тут последнее) дает 50-80мсек.
4. Ваше решение проработало больше (уже 705сек и ещё пашет)... сколько точно - не знаю.

как-то так. :)


У нас не получится повторить опыты друг друга, ввиду слишком разных условий их проведения.

Попробуй на своей таблице, с одинаковыми для предыдущих тестов условиями, следующий вариант:
SET @branch = ?;
SELECT @exists:=EXISTS (
    SELECT @branch:=Concat_ws(',', @branch, c.`id`) branch
      FROM `catalog` c
      WHERE Find_in_set(c.`parent_id`, @branch)
        AND NOT Find_in_set(c.`id`, @branch)
      ORDER BY `branch` DESC LIMIT 1)
  FROM `catalog`
  WHERE @exists;


Результат будет в переменной @branch
21 фев 13, 20:24    [13963429]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
DBConstructor
Member [заблокирован]

Откуда: RU-SPE
Сообщений: 716
Немного усложнил свой вариант, чтобы чуть-чуть сравнять условия опыта, и прогнал оба алгоритма:

-- by DBConstructor
SET @branch='1';
SET @exists = 1;
SELECT `id`
  FROM `catalog`, (
    SELECT @branch as branch, @exists:=EXISTS (
      SELECT @branch:=Concat_ws(',', @branch, c.`id`) branch
        FROM `catalog` c
        WHERE Find_in_set(c.`parent_id`, @branch)
          AND NOT Find_in_set(c.`id`, @branch)
        ORDER BY `branch` DESC LIMIT 1) rowsExists
    FROM `catalog`
    WHERE @exists
    ORDER BY `branch` DESC LIMIT 1) as branch
  WHERE Find_in_set(`id`, `branch`.`branch`)
/* 0 rows affected, 1 667 rows found. Duration for 3 queries: 0,390 sec. */


-- by Bochkov
SET @a='1';
SELECT id FROM(
    SELECT @index:=INSTR(@a,',') as coma_index,
        @id:=SUBSTRING_INDEX(@a, ',', 1)  as id,
        @a:=SUBSTRING(@a,IF(@index,@index+1,0)),
        @a:=CONCAT_WS(IF(LENGTH(@a)>0,',',''),@a,
        (SELECT group_concat(id)
           FROM `catalog`
           WHERE parent_id=@id)) as array
      FROM `catalog`
      WHERE LENGTH(@a)>0) childs;
/* 0 rows affected, 1 667 rows found. Duration for 2 queries: 1,575 sec. */


Первый алгоритм отработал в 4 раза быстрее.
21 фев 13, 21:09    [13963585]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
Arhat109
Member

Откуда: из СССР
Сообщений: 3282
DBConstructor
Arhat109
DBConstructor,

протестил:

1. Таблица 10 деревьев по 1 листу в уровне, всего 300 уровней (3000 записей всего!)
2. Решение Бочкова дает выборку от 0,5 до 1 сек.
3. Решение с составным индексом (моё тут последнее) дает 50-80мсек.
4. Ваше решение проработало больше (уже 705сек и ещё пашет)... сколько точно - не знаю.

как-то так. :)


У нас не получится повторить опыты друг друга, ввиду слишком разных условий их проведения.

Попробуй на своей таблице, с одинаковыми для предыдущих тестов условиями, следующий вариант:
SET @branch = ?;
SELECT @exists:=EXISTS (
    SELECT @branch:=Concat_ws(',', @branch, c.`id`) branch
      FROM `catalog` c
      WHERE Find_in_set(c.`parent_id`, @branch)
        AND NOT Find_in_set(c.`id`, @branch)
      ORDER BY `branch` DESC LIMIT 1)
  FROM `catalog`
  WHERE @exists;


Результат будет в переменной @branch


Только сегодня заметил.
В переменной @branch оказывается только исходное значение "3" за 46мсек. Увы.
22 фев 13, 23:58    [13969549]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
Arhat109
Member

Откуда: из СССР
Сообщений: 3282
Тут приведен код тестового примера и результаты сравнений:
# test(in integer search_num) {
BEGIN

SET @C='Special create table for ver.2: with composed primary key';
DROP TABLE IF EXISTS `tree`;
CREATE TABLE IF NOT EXISTS `tree` (
   `level`     int(11)          NOT NULL
  ,`parent_id` int(11) unsigned NOT NULL
  ,`id`        int(11) unsigned NOT NULL # auto_increment
  ,`data`      varchar(255) character set 'utf8' default ''
  ,PRIMARY KEY  (`level`,`parent_id`,`id`)
#  ,UNIQUE KEY `id` (`id`) -- for autoincrement needs!
  ,KEY `parent_id` (`parent_id`)
  ,KEY `id`        (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;

SET @C='Inserting tree into table';
SET @depth = 10;
SET @maxLevel = 300;

SET @level = 0;
REPEAT
  SET @d = 1;
  REPEAT
    INSERT INTO `tree` SET
        `level`     = @level
      , `parent_id` = @parent:=IF(@level=0, 0, @d + (@level-1) * @depth) #FLOOR( RAND()*@level*@depth ) )
      , `id`        = @d + @level * @depth
      , `data`      = CONCAT('data for parent = ',@parent)
    ;
    SET @d = @d + 1;
  UNTIL @d > @depth END REPEAT;
  SET @level = @level + 1;
UNTIL @level > @maxLevel END REPEAT;
COMMIT;

SET @C='Ver.1: with subquery for each childs... correct for simple query and any tables but stuppid...';
SELECT
  @idx := CAST(SUBSTRING_INDEX(@array, ',', 1) AS SIGNED) AS idx
  , @array := CONCAT_WS(
          IF(LENGTH(@array) > LENGTH(@idx), ',', '')
          , SUBSTRING(@array, CHAR_LENGTH(@idx)+2)
          , (SELECT GROUP_CONCAT(`id`) FROM `tree` WHERE `parent_id` = @idx)
  ) AS array
FROM (SELECT @array:=CONCAT('',search_num), @idx:=0) AS dummy
, `tree` AS ch
WHERE
  LENGTH(@array) > 0
;
# selected=301 items by 0.59 .. 0.61sec. (10 times).

SET @C='Ver.2: table must composed primary key (level, parent_id, id)... quickly,  full index scan...';
SELECT
  ch.`level` AS LEVEL
  , IF( @pr<>ch.`parent_id`, GREATEST(
        @array:=REPLACE(@array, @prc, '')
        , @prc:=CONCAT(',',ch.`parent_id`,',')
        , @pr:=ch.`parent_id`
    ), @pr) AS parent
  , GREATEST(ch.`id`
    , IF( LOCATE(@prc, @array) > 0
        , @array := CONCAT(@array, CONCAT(',',ch.`id`,','))
        , ''
  )) AS childs
FROM (SELECT @prc:=@array:=CONCAT(',',@pr:=search_num,',')) AS dummy
, `tree` AS ch FORCE INDEX (`PRIMARY`) # if present other index!
WHERE LOCATE( CONCAT(',',ch.`parent_id`,','), @array) > 0;
# selected=300 items by 0.21 .. 0.8 sec.


SET @branch=CONCAT('', search_num);
SELECT @branch as branch
  FROM `tree`
  WHERE EXISTS (SELECT 
         @branch:=CONCAT_WS(',', @branch, GROUP_CONCAT(`id`)) branch
       FROM `tree`
       WHERE FIND_IN_SET(`parent_id`, @branch)
         AND NOT FIND_IN_SET(`id`, @branch)
       GROUP BY `parent_id`
       ORDER BY `branch` DESC LIMIT 1)
  ORDER BY `branch` DESC LIMIT 1;
#selected=string by 2min 15sec. (one time starting index was added)


SET @branch = CONCAT('', search_num);
SELECT @exists:=EXISTS (
    SELECT @branch:=Concat_ws(',', @branch, c.`id`) branch
      FROM `tree` c
      WHERE Find_in_set(c.`parent_id`, @branch)
        AND NOT Find_in_set(c.`id`, @branch)
      ORDER BY `branch` DESC LIMIT 1)
  FROM `tree`
  WHERE @exists;
SELECT @branch;
# selected by 0.046sec, but only 1 result: @branch = '3' (one result only!);


SET @branch=CONCAT('', search_num);
SET @exists = 1;
SELECT `id`
  FROM `tree`, (
    SELECT @branch as branch, @exists:=EXISTS (
      SELECT @branch:=Concat_ws(',', @branch, c.`id`) branch
        FROM `tree` c
        WHERE Find_in_set(c.`parent_id`, @branch)
          AND NOT Find_in_set(c.`id`, @branch)
        ORDER BY `branch` DESC LIMIT 1) rowsExists
    FROM `tree`
    WHERE @exists
    ORDER BY `branch` DESC LIMIT 1) as branch
  WHERE Find_in_set(`id`, `branch`.`branch`)
;
# selected=301 items by 0.398sec (three time starting)

END
23 фев 13, 00:05    [13969570]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
Arhat109
Member

Откуда: из СССР
Сообщений: 3282
Arhat109,

была слеплена такая вот процедура, в которой ненужный код (на момент проверки) просто тупо комментился.
23 фев 13, 00:07    [13969575]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
Arhat109
Member

Откуда: из СССР
Сообщений: 3282
Arhat109,

Во втором примере очепятка, следует читать 0.021 .. 0.08 sec. Неправильно перевел 21 .. 80 миллисекунд в секунды. :)
23 фев 13, 00:09    [13969583]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
Arhat109
Member

Откуда: из СССР
Сообщений: 3282
Arhat109,

последний пример запускался три раза с одним временным результатом.
23 фев 13, 00:11    [13969588]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
Arhat109
Member

Откуда: из СССР
Сообщений: 3282
Arhat109,

Лицензионное соглашение короткое: "Пользуйтесь на здоровье!" :)
23 фев 13, 00:12    [13969595]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
DBConstructor
Member [заблокирован]

Откуда: RU-SPE
Сообщений: 716
Arhat109
Только сегодня заметил.
В переменной @branch оказывается только исходное значение "3" за 46мсек. Увы.


Я малость тупанул. Забыл написать, что после "SET @branch = ..." надо еще "SET @exists = 1;"
В конечном варианте:
SET @branch = ?;
SET @exists = 1;
SELECT @exists:=EXISTS (
    SELECT @branch:=Concat_ws(',', @branch, c.`id`) branch
      FROM `catalog` c
      WHERE Find_in_set(c.`parent_id`, @branch)
        AND NOT Find_in_set(c.`id`, @branch)
      ORDER BY `branch` DESC LIMIT 1)
  FROM `catalog`
  WHERE @exists;
23 фев 13, 00:48    [13969692]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
DBConstructor
Member [заблокирован]

Откуда: RU-SPE
Сообщений: 716
Развитие темы Bochkov'а с небольшим увеличением производительности:
SET @fifo = ?;
SELECT `id` FROM (
  SELECT
      @id:=Cast(Substring_index(@fifo, ',', 1) AS UNSIGNED INTEGER) as id,
      @fifo_len:=Length(@fifo)-Length(@id)-1 as fifo_len,
      @fifo:=Concat_ws(',', If(@fifo_len > 0, Right(@fifo, @fifo_len), NULL),
           (
            SELECT Group_concat(`id`)
              FROM `catalog`
              WHERE `parent_id`=@id
           )) as fifo
    FROM `catalog`
    WHERE Length(@fifo) > 0) branch
23 фев 13, 01:00    [13969713]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
DBConstructor
Member [заблокирован]

Откуда: RU-SPE
Сообщений: 716
И наконец, самое быстрое решение - решение "молния":

SET group_concat_max_len = 65533;
SET character_set_connection = latin1;
SET @seq = '3';
SET @next_seq = NULL;
SELECT `id`
  FROM (
    SELECT
        @id:=Cast(Substring_index(@seq, ',', 1) AS UNSIGNED INTEGER) as id,
        @seq_len:=Length(@seq)-Length(@id)-1 as seq_len,
        @next_seq:=IfNull(If(@seq_len > 0, @next_seq, NULL),
           (
            SELECT Group_concat(`id`)
              FROM `catalog`
              WHERE Find_in_set(`parent_id`, IfNull(@next_seq, @seq))
           )
        ) as next_seq,
        @seq:=If(@seq_len > 0, Right(@seq, @seq_len), IfNull(@next_seq,'')) as seq
    FROM `catalog`
    WHERE Length(@seq) > 0) branch;


Как говорится, ENJOY!
23 фев 13, 02:39    [13969815]     Ответить | Цитировать Сообщить модератору
 Re: FAQ: Древовидные структуры средствами MySQL или роман Стендаля "Красное и Черное"  [new]
Arhat109
Member

Откуда: из СССР
Сообщений: 3282
DBConstructor,

Потестил в той куче данных: selected = 301 items by 0.7 .. 0.93 sec. Нисколько оно не "скоростной вариант". Точно такой же. :)

1. Справедливости ради: тема - моя и работают у меня эти запросы уже больше года, Бочков самостоятельно(!) нашел решение, которое я тогда не мог выложить. И самое быстрое решение - это:

SET @C='Ver.2: table must composed primary key (level, parent_id, id)... quickly,  full index scan...';
SELECT
  ch.`level` AS LEVEL
  , IF( @pr<>ch.`parent_id`, GREATEST(
        @array:=REPLACE(@array, @prc, '')
        , @prc:=CONCAT(',',ch.`parent_id`,',')
        , @pr:=ch.`parent_id`
    ), @pr) AS parent
  , GREATEST(ch.`id`
    , IF( LOCATE(@prc, @array) > 0
        , @array := CONCAT(@array, CONCAT(',',ch.`id`,','))
        , ''
  )) AS childs
FROM (SELECT @prc:=@array:=CONCAT(',',@pr:=search_num,',')) AS dummy
, `tree` AS ch FORCE INDEX (`PRIMARY`) # if present other index!
WHERE LOCATE( CONCAT(',',ch.`parent_id`,','), @array) > 0;
# selected=300items by 0.021 .. 0.080 sec.


Кстати, почему вы так любите Find_in_set()? LOCATE() -- существенно быстрее. :)
23 фев 13, 10:16    [13970000]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3 4   вперед  Ctrl      все
Все форумы / MySQL Ответить