ReSQL.ru
     
powered by simpleCommunicator - 2.0.28     © 2024 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Map
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / PostgreSQL [игнор отключен] [закрыт для гостей] / with recursion
6 сообщений из 6, страница 1 из 1
with recursion
    #40138931
Nicolle
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Nicolle
Участник
Здравствуйте! Есть рекурсивный запрос такого плана:
Код: PL/pgSQL
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
with recursive query(inIdParent, inIdType, level) as
    (select distinct v.inIdParent, v.inIdType, 1
     from view v
     where v.inIdChild = 123 /*idChild*/
     union
     select distinct l.inIdParent, l.inIdType, rec.Level + 1
     from (select distinct rec.inIdParent, rec.Level from query rec) rec
     inner join view v on v.inIdChild = rec.inIdParent
    )
    select *
    from query v
    inner join types tt on tt.inId = v.inIdType
    where v.inIdParent = 456--/*IdRoot*/
      and tt.inIdLink in (1/*IdLink1*/, 2/*IdLink2*/);
Для идентификатора idChild разматывается все дерево наверх до нужного родителя IdRoot по связям IdLink1 и IdLink2.
Не нравится такой момент - для idChild мы всегда находим все уровни до конца и уже потом ищем подходящего родителя по нужным нам условиям.
Можно ли как-то переписать запрос так, чтобы он останавливался и не разматывал дерево дальше, если найдет нужного родителя?

С помощью цикла while я такое поведение описала так:

Создаю временную таблицу tmp и задаю переменную v_inLevel = 1.
Код: PL/pgSQL
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.
insert into tmp (inIdParent, inIdType, inLevel)
  select distinct v.inIdParent, v.inIdType, v_inLevel as inLevel
  from view v
  where v.inIdChild = 123 /*idChild*/;

  while not v_done and v_inLevel < 4000 loop
    v_inLevel := v_inLevel + 1;

    --Если дошли до версии нужного родительского объекта, то выход
    if exists (select 1
               from tmp v
               inner join types tt on tt.inId = v.inIdType
               where v.inLevel = v_inLevel - 1
                 and v.inIdParent = 456--/*IdRoot*/
                 and tt.inIdLink in (1/*IdLink1*/, 2/*IdLink2*/)
               limit 1) then
      v_done := found;
      return;
    end if;

    insert into tmp (inIdParent, inIdType, inLevel)
    select distinct l.inIdParent, l.inIdType, v_inLevel as inLevel
    from (select distinct rec.inIdParent from tmp rec where rec.inLevel = v_inLevel - 1) rec
    inner join view l on l.inIdChild = rec.inIdParent
    where not exists (select 1 from tmp r where r.inIdParent = l.inIdParent and r.inIdTypeRel = l.inIdTypeRel);
    v_done := not found;
  end loop;
Возможно ли похожее поведение реализовать с помощью with recursive?
...
Рейтинг: 0 / 0
23.10.2024, 11:44
| Ответить | Цитировать | Написать | Ответы  
with recursion
    #40138936
Фотография SeaGate
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SeaGate
Участник
Nicolle [игнорируется] 

почему нерабочий запрос? что такое "l"? Зачем union и distinct?
Код: SQL
1.
2.
3.
select distinct l.inIdParent, l.inIdType, rec.Level + 1
     from (select distinct rec.inIdParent, rec.Level from query rec) rec
     inner join view v on v.inIdChild = rec.inIdParent
Что-нибудь такое:
https://onecompiler.com/postgresql/42vxnwxp5
Код: 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.
create view view(inIdChild, inIdParent, inIdType) as (
  values (123, 100, 1),
         (100, 200, 2),
         (200, 456, 2),
         (456, 789, 2)
  );

create view types(inId, inIdLink) as (
  values (1, 10),
         (2, 2)
);

  with recursive query(inIdParent, inIdType, level, done) as
    (select v.inIdParent, v.inIdType, 1, cast(null as integer)
     from view v
     where v.inIdChild = 123 /*idChild*/
     union all
     select v.inIdParent, v.inIdType, rec.Level + 1,
            (select case when v.inIdParent = 456 and tt.inIdLink in (1, 2) then tt.inIdLink end from types tt where tt.inId = v.inIdType)
     from query rec
     inner join view v on v.inIdChild = rec.inIdParent
     where done is null
    )
    select *
    from query v;
По explain analyze делает 3 loops. если убирать done, то 4.
Данные нужно предоставлять как в примере выше, если чего-то не хватает.
...
Рейтинг: 0 / 0
23.10.2024, 13:15
| Ответить | Цитировать | Написать  
with recursion
    #40138941
Nicolle
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Nicolle
Участник
Извиняюсь, поправила код, distinct можно убрать:
Код: PL/pgSQL
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
with recursive query(inIdParent, inIdType, level) as
    (select distinct v.inIdParent, v.inIdType, 1
     from view v
     where v.inIdChild = 123 /*idChild*/
     union
     select v.inIdParent, v.inIdType, rec.Level + 1
     from (select distinct rec.inIdParent, rec.Level from query rec) rec
     inner join view v on v.inIdChild = rec.inIdParent
    )
    select *
    from query v
    inner join types tt on tt.inId = v.inIdType
    where v.inIdParent = 456--/*IdRoot*/
      and tt.inIdLink in (1/*IdLink1*/, 2/*IdLink2*/);
Если в ваш пример добавить для объекта 123 еще одного родителя (например с ид 500, который удовлетворяет условиям - то будет работать неверно)
Код: PL/pgSQL
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.
--drop view view
create view view(inIdChild, inIdParent, inIdType) as (
  values (123, 100, 1),
         (100, 200, 2),
         (200, 456, 2),
         (456, 789, 2),
         (123, 500, 1)
  );

create view types(inId, inIdLink) as (
  values (1, 10),
         (2, 2)
);

  with recursive query(inIdParent, inIdType, level, done) as
    (select v.inIdParent, v.inIdType, 1, cast(null as integer)
     from view v
     where v.inIdChild = 123 /*idChild*/
     union all
     select v.inIdParent, v.inIdType, rec.Level + 1,
            (select case when v.inIdParent = 500 and tt.inIdLink in (1, 2) then tt.inIdLink end from types tt where tt.inId = v.inIdType)
     from query rec
     inner join view v on v.inIdChild = rec.inIdParent
     where done is null
    )
    select *
    from query v;
Результат - https://onecompiler.com/postgresql/42w23w2up
...
Рейтинг: 0 / 0
Вчера, 08:09
| Ответить | Цитировать | Написать | Ответы  
with recursion
    #40138946
Фотография SeaGate
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SeaGate
Участник
Nicolle [игнорируется] 
Код
1.
 (123, 500, 1)
не удовлетворяет условиям, т.к. inIdType=1 соответствует types.inIdLink = 10, а по условиям нужны inIdLink in (1,2).
Здесь нужно проверять условие на первой итерации для этого случая.
Код: 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.
create view view(inIdChild, inIdParent, inIdType) as (
  values (123, 100, 1),
         (100, 200, 2),
         (200, 456, 2),
         (456, 789, 2),
         (123, 500, 2)
  );

create view types(inId, inIdLink) as (
  values (1, 10),
         (2, 2)
);

  with recursive query(inIdParent, inIdType, level, done) as
    (select v.inIdParent, v.inIdType, 1, (select case when v.inIdParent = 500 and tt.inIdLink in (1, 2) then tt.inIdLink end from types tt where tt.inId = v.inIdType)
     from view v
     where v.inIdChild = 123 /*idChild*/
     union all
     select v.inIdParent, v.inIdType, rec.Level + 1,
            (select case when v.inIdParent = 500 and tt.inIdLink in (1, 2) then tt.inIdLink end from types tt where tt.inId = v.inIdType)
     from query rec
     inner join view v on v.inIdChild = rec.inIdParent
     where done is null
    )
    select *
    from query v;
Работает для 500 и 789. https://onecompiler.com/postgresql/42w2mp3mu
...
Рейтинг: 0 / 0
Вчера, 12:31
| Ответить | Цитировать | Написать | Ответы  
with recursion
    #40138951
Nicolle
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Nicolle
Участник
SeaGate [игнорируется] 

Понятно. Но при этом получается, что рекурсия все равно строит полностью все дерево вверх. А мне бы хотелось при первом нахождении нужного условия выходить из рекурсии. Получается рекурсия в данном случае проигрывает циклу или я не умею ее готовить.) В цикле если мы находим нужного родителя мы дальше не ищем - сразу выходим.
...
Рейтинг: 0 / 0
Сегодня, 09:38
| Ответить | Цитировать | Написать | Ответы  
with recursion
    #40138956
Фотография SeaGate
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SeaGate
Участник
Nicolle [игнорируется] 
Nicolle  Сегодня, 09:38
[игнорируется]
40138951
Но при этом получается, что рекурсия все равно строит полностью все дерево вверх.
Не совсем.
Код: 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.
37.
38.
create view view(inIdChild, inIdParent, inIdType) as (
  values (123, 100, 1),
         (100, 200, 2),
         (200, 456, 2),
         (456, 789, 2),
         (123, 500, 2),
         (500, 600, 1),
         (600, 700, 1)
  );

create view types(inId, inIdLink) as (
  values (1, 10),
         (2, 2)
);

create function raise_notice (i integer) returns integer language plpgsql  as
$$
begin
    raise notice '%', i;
    return i;
end;
$$;

  with recursive query(inIdParent, inIdType, level, done, log) as
    (select v.inIdParent, v.inIdType, 1, (select case when v.inIdParent = 500 and tt.inIdLink in (1, 2) then tt.inIdLink end from types tt where tt.inId = v.inIdType),
            raise_notice(v.inIdParent)
     from view v
     where v.inIdChild = 123 /*idChild*/
     union all
     select v.inIdParent, v.inIdType, rec.Level + 1,
            (select case when v.inIdParent = 500 and tt.inIdLink in (1, 2) then tt.inIdLink end from types tt where tt.inId = v.inIdType),
            raise_notice(v.inIdParent)
     from query rec
     inner join view v on v.inIdChild = rec.inIdParent
     where done is null
    )
    select *
    from query v;
Возвращает 5 строк.
Если убрать where done is null, то возвращает 7 строк.

Есть есть всегда как максимум один родитель, то рекурсия не пойдёт далее первой строки, удовлетворяющей условиям.
В случае нескольких родителей это уже не так, и, как мне известно, в PostgreSQL нет branch pruning (возможность просмотра других веток в рамках recursive CTE).
Также я бы не сказал, что ситуация наличия более одного родителя является типичной.

Если задача найти не более одного родителя, удовлетворяющего условиям, я бы использовал следующее:
Код: SQL
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
explain analyze
  with recursive query(inIdParent, inIdType, level, done) as
    (select v.inIdParent, v.inIdType, 1,
            (select case when v.inIdParent = 500 and tt.inIdLink in (1, 2) then tt.inIdLink end from types tt where tt.inId = v.inIdType)
     from view v
     where v.inIdChild = 123 /*idChild*/
     union all
     select v.inIdParent, v.inIdType, rec.Level + 1,
            (select case when v.inIdParent = 500 and tt.inIdLink in (1, 2) then tt.inIdLink end from types tt where tt.inId = v.inIdType)
     from query rec
     inner join view v on v.inIdChild = rec.inIdParent
     where done is null
    )
    select *
    from query v
    where done is not null
    fetch first 1 row only;
здесь используется breadth first traversal (что можно и явно задать через search).
1 строка удалена по фильтру done is not null, recursive CTE был из 2х строк:
Код: SQL
1.
2.
3.
4.
5.
6.
   CTE query
     ->  Recursive Union  (cost=0.00..6.60 rows=11 width=20) (actual time=0.011..0.016 rows=2 loops=1)
...
   ->  CTE Scan on query v  (cost=0.00..0.22 rows=11 width=16) (actual time=0.056..0.056 rows=1 loops=1)
         Filter: (done IS NOT NULL)
         Rows Removed by Filter: 1
Таким образом, обход иерархии выполнялся до первого найденного родителя, без прохода всех родителей в глубину.
Если, например, убрать fetch first 1 row only:
Код: SQL
1.
2.
3.
4.
5.
6.
 CTE Scan on query v  (cost=6.60..6.82 rows=11 width=20) (actual time=0.019..0.380 rows=1 loops=1)
   Filter: (done IS NOT NULL)
   Rows Removed by Filter: 4
...
   CTE query
     ->  Recursive Union  (cost=0.00..6.60 rows=11 width=20) (actual time=0.013..0.374 rows=5 loops=1)
Т.е. видно, что recursive CTE вернул 5 строк (всю иерархию), а фильтр отбросил 4.
Таким образом, для breadth first поиска не более одного родителя, можно использовать код, что выше.
Лучше также явно добавить search breadth first ...
...
Рейтинг: 0 / 0
Сегодня, 13:41
| Ответить | Цитировать | Написать  
6 сообщений из 6, страница 1 из 1
Форумы / PostgreSQL [игнор отключен] [закрыт для гостей] / with recursion
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru, Чат Кролика       Пашэ: Рисунки, Чат       Фотоальбом: Участники, Встречи
Закрыть
Start [/forum/topic.php?fid=53&msg=40138956&tid=2187056]:
 0ms
get settings:
 22ms
get forum list:
 12ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 57ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 145ms
get tp. blocked users:
 1ms
others: 274ms
total:  530ms
созд. / загр.: 530ms
x
x
Закрыть


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