Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / MySQL [игнор отключен] [закрыт для гостей] / Рекурсивный Left Joit / 9 сообщений из 9, страница 1 из 1
11.08.2013, 20:04:38
    #38362429
vladqa
vladqa
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсивный Left Joit
Здравствуйте!

Есть таблица people. У каждого человека есть отец и мать.
Соответственно, структура такая:

Код: sql
1.
2.
3.
4.
5.
6.
7.
CREATE TABLE `dog` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) DEFAULT NULL,
  `mother_id` int(11) DEFAULT NULL,
  `father_id` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=0 DEFAULT CHARSET=utf8



Задача: выбрать всех предков человека: по линии отца и матери. По сути, построить родословную.
Количество поколений для выборки ограничено 8.

Решил решать задачу, джойня таблицу саму с собой.

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
SELECT `D0`.`id` AS `D0_id`,
       `D0`.`name` AS `D0_name`,
       `D0`.`mother_id` AS `D0_mother_id`,
       `D0`.`father_id` AS `D0_father_id`,
       `D0`.`sex` AS `D0_sex`,

       `D1`.`id` AS `D1_id`,
       `D1`.`name` AS `D1_name`,
       `D1`.`mother_id` AS `D1_mother_id`,
       `D1`.`father_id` AS `D1_father_id`,
       `D1`.`sex` AS `D1_sex`,
       `D1`.`birth_year` AS `D1_birth_year`,

       `D2`.`id` AS `D2_id`,
       `D2`.`name` AS `D2_name`,
       `D2`.`mother_id` AS `D2_mother_id`,
       `D2`.`father_id` AS `D2_father_id`,
       `D2`.`sex` AS `D2_sex`,
       `D2`.`birth_year` AS `D2_birth_year`,

       `D3`.`id` AS `D3_id`,
       `D3`.`name` AS `D3_name`,
       `D3`.`mother_id` AS `D3_mother_id`,
       `D3`.`father_id` AS `D3_father_id`,
       `D3`.`sex` AS `D3_sex`,
       `D3`.`birth_year` AS `D3_birth_year`

FROM `people` AS `D0`

LEFT JOIN `people` `D1` ON D0.father_id = D1.id OR D0.mother_id = D1.id

LEFT JOIN `people` AS `D2` ON D1.father_id = D2.id OR D1.mother_id = D2.id

LEFT JOIN `people` AS `D3` ON D2.father_id = D3.id OR D2.mother_id = D3.id

WHERE D0.id = '1'



Вроде бы все нормально, но explain выдает грусть:

id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE D0 const PRIMARY PRIMARY 4 const 1
1 SIMPLE D1 range PRIMARY PRIMARY 4 NULL 2 Using where
1 SIMPLE D2 ALL PRIMARY NULL NULL NULL 562869 Range checked for each record (index map: 0x1)
1 SIMPLE D3 ALL PRIMARY NULL NULL NULL 562869 Range checked for each record (index map: 0x1)

Собственно в таблице 562 869 строк.

Как можно соптимизировать запрос? Можно ли выставить какие либо индексы, что бы джойны выполнялись быстрее? (Сейчас запрос занимает почти полторы секунды)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.08.2013, 21:23:22
    #38362476
javajdbc
javajdbc
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсивный Left Joit
vladqaЗдравствуйте!

Есть таблица people. У каждого человека есть отец и мать.
Соответственно, структура такая:

Код: sql
1.
2.
3.
4.
5.
6.
7.
CREATE TABLE `dog` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(255) DEFAULT NULL,
  `mother_id` int(11) DEFAULT NULL,
  `father_id` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=0 DEFAULT CHARSET=utf8



Задача: выбрать всех предков человека: по линии отца и матери. По сути, построить родословную.
Количество поколений для выборки ограничено 8.

Решил решать задачу, джойня таблицу саму с собой.

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
SELECT `D0`.`id` AS `D0_id`,
       `D0`.`name` AS `D0_name`,
       `D0`.`mother_id` AS `D0_mother_id`,
       `D0`.`father_id` AS `D0_father_id`,
       `D0`.`sex` AS `D0_sex`,

       `D1`.`id` AS `D1_id`,
       `D1`.`name` AS `D1_name`,
       `D1`.`mother_id` AS `D1_mother_id`,
       `D1`.`father_id` AS `D1_father_id`,
       `D1`.`sex` AS `D1_sex`,
       `D1`.`birth_year` AS `D1_birth_year`,

       `D2`.`id` AS `D2_id`,
       `D2`.`name` AS `D2_name`,
       `D2`.`mother_id` AS `D2_mother_id`,
       `D2`.`father_id` AS `D2_father_id`,
       `D2`.`sex` AS `D2_sex`,
       `D2`.`birth_year` AS `D2_birth_year`,

       `D3`.`id` AS `D3_id`,
       `D3`.`name` AS `D3_name`,
       `D3`.`mother_id` AS `D3_mother_id`,
       `D3`.`father_id` AS `D3_father_id`,
       `D3`.`sex` AS `D3_sex`,
       `D3`.`birth_year` AS `D3_birth_year`

FROM `people` AS `D0`

LEFT JOIN `people` `D1` ON D0.father_id = D1.id OR D0.mother_id = D1.id

LEFT JOIN `people` AS `D2` ON D1.father_id = D2.id OR D1.mother_id = D2.id

LEFT JOIN `people` AS `D3` ON D2.father_id = D3.id OR D2.mother_id = D3.id

WHERE D0.id = '1'



Вроде бы все нормально, но explain выдает грусть:

id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE D0 const PRIMARY PRIMARY 4 const 1
1 SIMPLE D1 range PRIMARY PRIMARY 4 NULL 2 Using where
1 SIMPLE D2 ALL PRIMARY NULL NULL NULL 562869 Range checked for each record (index map: 0x1)
1 SIMPLE D3 ALL PRIMARY NULL NULL NULL 562869 Range checked for each record (index map: 0x1)

Собственно в таблице 562 869 строк.

Как можно соптимизировать запрос? Можно ли выставить какие либо индексы, что бы джойны выполнялись быстрее? (Сейчас запрос занимает почти полторы секунды)

1. главная проблeма: "OR". Интересно что OR в Д1 пошел по РАНЖЕ.
Очевидно оптимизатор учел что будет всего 2 запроса.
Далее для Д2 и Д3 оптимизатор пошел на фул-скан.
очевидно не зная сколько будет запросов.

2. Варинат решения: процедурка на 6-8 простых последовательных запросов выдаст
результат за 5 милисекунд

3. Варинат решения -- жестко за-форсируйте ПРИМАРИ индекс на связке с Д2 и Д3.
Может и пойдет

4. Вариант: Переписать СКЛ на "UNION ALL" вместо "OR" . Может получится
очень громоздкий СКЛ.

5. Вариант : переделать структуру --- посмотрите FAQ по этой теме,
там вроде есть алтернативные построения связок.

Советую работать в порядке: 3,2,4,5.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.08.2013, 22:58:48
    #38362529
vladqa
vladqa
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсивный Left Joit
1. главная проблeма: "OR". Интересно что OR в Д1 пошел по РАНЖЕ.
Очевидно оптимизатор учел что будет всего 2 запроса.
Далее для Д2 и Д3 оптимизатор пошел на фул-скан.
очевидно не зная сколько будет запросов.

2. Варинат решения: процедурка на 6-8 простых последовательных запросов выдаст
результат за 5 милисекунд

3. Варинат решения -- жестко за-форсируйте ПРИМАРИ индекс на связке с Д2 и Д3.
Может и пойдет

4. Вариант: Переписать СКЛ на "UNION ALL" вместо "OR" . Может получится
очень громоздкий СКЛ.

5. Вариант : переделать структуру --- посмотрите FAQ по этой теме,
там вроде есть алтернативные построения связок.

Советую работать в порядке: 3,2,4,5.[/quot]

Спасибо за такой основательный ответ!

Попробовал второй вариант, как самый простой и понятный мне.
Запрос получился такой
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
SELECT
....

FROM  `people` AS `D0`

LEFT JOIN `people` `D1` FORCE INDEX FOR JOIN (`PRIMARY`) ON D0.father_id = D1.id OR D0.mother_id = D1.id

LEFT JOIN `people` AS `D2` FORCE INDEX FOR JOIN (`PRIMARY`) ON D1.father_id = D2.id OR D1.mother_id = D2.id

LEFT JOIN `people` AS `D3` FORCE INDEX FOR JOIN (`PRIMARY`) ON D2.father_id = D3.id OR D2.mother_id = D3.id



Но, к сожалению, EXPLAIN выдает все ту же грусть (да и время запроса не сократилось)

Дальше рассматриваю вариант с хранимкой, но, мне кажется, что там не отделаться 6-8 простых запросов, т.к. для выборки всего дерева таким образом придется на каждом поколении для каждого человека придется выбирать его предков с глубиной 1.
То есть получится, что в зависимости от требуемой глубины нужно:
1 поколение - 1 запрос
2 поколения 1 + 2 запроса
3 поколения 1 + 2 + 4 запроса
4 поколения 1 + 2 + 4 + 8 запросов
6 поколений ....
8 поколений 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 запросов

Или я не очень понял Вашу мысль?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.08.2013, 23:09:46
    #38362537
javajdbc
javajdbc
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсивный Left Joit
vladqa,

так вы определитесь, сколько у вас будет поколений?
Изначальный запрос был на 3 уровня вверх, ну и в
процедуре будет максимум, кажется, полтора десятка запросов
(папу и маму ишем в двух отдельных запросах.).
По индексу то будет несколько милисекунд на всё-про-всё.

А 8 уровней в процедуре -- ну, навскидку, полтыши запросов
по индексу - полюбому лучше чем 7 фулсканов.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.08.2013, 23:25:31
    #38362548
vladqa
vladqa
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсивный Left Joit
так вы определитесь, сколько у вас будет поколений?
Изначальный запрос был на 3 уровня вверх

Изначально написал в задаче, что до 8 поколений включительно =)
Просто в примере привел запрос на выборку 3 поколений, чтобы легче было понять суть запроса.
Извиняюсь, если таким образом ввел в заблуждение.

Да, получится около полтыщи, если маму и папу отдельно выбирать.
У меня нет большого опыта в оптимизации производительности СУБД и, поэтому, меня смущает эта цифра =(
Не убьется ли сервер при хоть какой-либо нагрузке?
(конечно я понимаю, что с теми фулсканами что есть, он убьется гораздо быстрее)

Правильно ли я понимаю, что выходит так, что mysql не сможет использовать индексы в запросе с рекурсивным join и это никак не побороть?

Ну и вариант с UNION ALL я не совсем понял, если честно.

А что касается
5. Вариант : переделать структуру --- посмотрите FAQ по этой теме,
там вроде есть алтернативные построения связок.

Не могли бы "ткнуть носом", в какое именно faq?
Читал про хранение древовидных структур, знаю про всякие nested sets, но не смог применить у себя =(
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.08.2013, 05:14:14
    #38362646
javajdb
javajdb
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсивный Left Joit
vladqa,

1. переписать

select * from t where id = x OR id = Y
(в этом случае чаше будет фулскан)

можно так, 100% сохранив функциональность:

select * from t where id = x
union all
select * from t where id = y

(при этом случае индекс будет почти 100%).


2. Для справки, чисто для прикидки, единичный запрос
по индексу будет примерно доли милисекунды на средненьком железе.
т.е. 500 отдельных запросов займет десятки милисекунд
(если из процедуры). Каждый фулскан добавит, ну скажем по полсекунде,
т.е 4-5 секунд на 8-етажный жоинт (фулскан без индексов).
Т.е. разница в 2-3 порядка.

3. Идеи для алтернативных структур и алтернативных запросах
посмотрите вот в этой FAQ теме:

http://www.sql.ru/forum/684437/faq-drevovidnye-struktury-sredstvami-mysql-ili-roman-stendalya-krasnoe-i-chernoe
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.08.2013, 22:32:00
    #38363894
vladqa
vladqa
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсивный Left Joit
javajdbc, пытаюсь попробовать UNION ALL и не могу понять, куда его впихнуть. У меня же условие OR было в конструкции ON. А как переписать запрос на UNION ALL, не понятно. Не могли бы натолкнуть на мысть?

Попробовал также вариант с выборкой родителей как раз с помощью union ALL:
SELECT
D.id as D_id, D.name as D_name,
D.mother_id AS D_mother_id, D.father_id as D_father_id
FROM
people AS D
WHERE D.id = :mother_id

UNION ALL

SELECT
D.id as D_id, D.name as D_name,
D.mother_id AS D_mother_id, D.father_id as D_father_id
FROM
people AS D
WHERE D.id = :father_id

Работает, конечно, быстрее: ~0.2-0.5 секунды
Но у меня же требуемая вложенность для каждого запроса известна, очень хотелось бы все таки сконструировать пусть и большой. но все же один запрос
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.08.2013, 23:51:55
    #38363940
javajdbc
javajdbc
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсивный Left Joit
vladqa,

1. SELECT
D.id as D_id, D.name as D_name,
D.mother_id AS D_mother_id, D.father_id as D_father_id
FROM
people AS D
WHERE D.id = :father_id

Этот селект обязан отработать за доли милисекунды

2. да, похоже не будет номального СКЛ-а использую
union all для нескольких уровней

3. Сделайте линейную процедуру. будет проше и понятно.

4. сделайте рекурсивную процедуру -- будет красиво
(но не знаю, допускает ли mysql рекурсию?)

5. ну или ждите специалистов по деревьям,
тут люди есть, но они как-то не активны...

СПЕЦИАЛИСТЫ, ау!!!, помогите вырастить дерево! :-)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.08.2013, 06:09:21
    #38364041
tanglir
tanglir
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рекурсивный Left Joit
vladqaочень хотелось бы все таки сконструировать пусть и большой. но все же один запросзачем?
javajdbcСделайте линейную процедуру. будет проше и понятно.+1
понабивать всех предков во временную таблицу, на конечном этапе сделать select distinct из неё, вот и всё.
javajdbcпомогите вырастить дерево! :-)а это не дерево :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / MySQL [игнор отключен] [закрыт для гостей] / Рекурсивный Left Joit / 9 сообщений из 9, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 296ms
Закрыть
start [/forum/topic.php?fid=47&tablet=1&tid=1836261]:
 0ms
get settings:
 7ms
get forum list:
 10ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 39ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 26ms
get tp. blocked users:
 1ms
others: 198ms
total:  296ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]