ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Поиск по дереву
22 сообщений из 22, страница 1 из 1
Поиск по дереву
    #32105360
Фотография judge
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
judge
Участник
Всем привет.

Я с Oracle достаточно редко работаю и не очень хорошо знаю все тонкости. Столкнулся с проблемой (9i):

Есть табличка (сокращенная)

Код: plaintext
1.
2.
3.
4.
5.
6.
create table hr_archive (
id number,
programme varchar2( 100 ),
episode varchar2( 100 ),
parent_id number
)


Нужно построить запрос, который вернет дерево с учетом текстового поиска по полям (programme & episode), причем важно , если на любом и уровней ветки поиск успешен - то должна выводиться вся ветка.


Пробовал запрос
Код: plaintext
1.
2.
3.
4.
select * from hr_archive
where upper(episode) like '%INT%' or  upper(programme) like '%INT%'
start with parent_id = - 1 
connect by prior id = parent_id


Но естественно, ветки целиком не возвращаются.
Буду рад любым идеям.

Alex Sibilev
...
Рейтинг: 0 / 0
12.02.2003, 18:09
| Ответить | Цитировать | Написать  
Поиск по дереву
    #32105363
ShgGena
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ShgGena
Участник
Voznikaet seriozniy vopros otnositelno poddereviev:
ecli est

1 ABC-INT
-- 2 BCD
------ 3 CDE-INT
-----------4 DEF

to polychaetsia cho
a) perviy raz dolgno bit vibrano vsya vetv 1 ABC-INT a vtoroy raz vetv 3 CDE-INT
b) ili tolko 1 raz 1 ABC-INT (a podvetvi pri povtornom sovpadenii uge ne vivodiatsya)

Nado utochnit zadachu.
...
Рейтинг: 0 / 0
12.02.2003, 18:15
| Ответить | Цитировать | Написать  
Поиск по дереву
    #32105366
Фотография judge
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
judge
Участник
Вариант b.
Подветви при повторном совпадении не выводятся вторично.

Alex
...
Рейтинг: 0 / 0
12.02.2003, 18:20
| Ответить | Цитировать | Написать  
Поиск по дереву
    #32105406
.dba
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
.dba
Участник
мне кажется, что одним иерархическим запросом эту задачу не решить. Условие where будет применяться на последнем этапе (после построения дерева) и как к результатам обычного плоского запроса, а о возможности отбора ветвей я не слышал.

Может быть решением является построение всех возможных ветвей начиная с перебора стартового ID снизу, при удовлетворении условиям текстового поиска в родительской записи. А затем из этого набора строк построения конечного дерева. Это первое, что приходит в голову.

Хотя кажется есть целый раздел математики, изучающий графы :-)
...
Рейтинг: 0 / 0
12.02.2003, 19:32
| Ответить | Цитировать | Написать  
Поиск по дереву
    #32105410
Фотография judge
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
judge
Участник
мда :(
а если упростить задачу? известно что уровней может быть от 1 до 3 и поиск нужно производить только на 1 и 3 уровне (2ой не важен но в выборке должне присутствовать).

По идее это же "стандартная" задача. Найти все ветви в которых встречаются опред. значения.

Alex
...
Рейтинг: 0 / 0
12.02.2003, 19:43
| Ответить | Цитировать | Написать  
Поиск по дереву
    #32105411
.dba
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
.dba
Участник
может тогда псевдостолбцы level и rownum как-то помогут?
Т.е. получить выборку во временную таблицу с двумя дополнительными полями в которые поместить значения level и rownum от первой выборки, а затем по этим данным отобрать необходимые ветви?
...
Рейтинг: 0 / 0
12.02.2003, 19:50
| Ответить | Цитировать | Написать  
Поиск по дереву
    #32105413
ShgGena
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ShgGena
Участник
Ideya sostoit v sleduyuschem:

- postroit spisok kornevih uzlov dlya kotorih ne suschestvuet ni odnogo uzla po doroge ot nego k
kornu dereva s tem ze samim ogranicheniem;
- ispolzovat etot spisok kak kornevye uzly v konstrukcii START WITH

Код: plaintext
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.
drop table train.test_tree ;

create table train.test_tree (
node_id number,
root_id number,
txt     varchar2( 20 ),
constraint pk_test_tree primary key (node_id)
);

insert into train.test_tree values (  1 ,   0 , 'node-1');
insert into train.test_tree values (  2 ,   1 , 'node-b');
insert into train.test_tree values (  3 ,   1 , 'node-a');
insert into train.test_tree values (  4 ,   1 , 'node-d');
insert into train.test_tree values (  5 ,   2 , 'node-a');
insert into train.test_tree values (  6 ,   2 , 'node-e');
insert into train.test_tree values (  7 ,   3 , 'node-f');
insert into train.test_tree values (  8 ,   3 , 'node-d');
insert into train.test_tree values (  9 ,   3 , 'node-a');
insert into train.test_tree values (  10 ,  4 , 'node-a');
insert into train.test_tree values (  11 ,  4 , 'node-x');
insert into train.test_tree values (  12 ,  4 , 'node-c');
insert into train.test_tree values (  13 ,  7 , 'node-v');
insert into train.test_tree values (  14 ,  7 , 'node-a');
insert into train.test_tree values (  15 ,  10 , 'node-n');
insert into train.test_tree values (  16 ,  10 , 'node-m');
insert into train.test_tree values (  17 ,  10 , 'node-l');
insert into train.test_tree values (  18 ,  12 , 'node-k');
insert into train.test_tree values (  19 ,  12 , 'node-j');
Postroili derevo a teper viberem nuznoe:
Код: plaintext
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.
select t.node_id, substr(lpad('.',(level- 1 )* 2 ,'.') || t.txt, 1 , 40 ) txt
from train.test_tree t
connect by prior t.node_id = t.root_id
start with t.node_id in ( select i.node_id from train.test_tree i
                          where txt = 'node-a'
                          and
                          not exists ( select null from train.test_tree z
                                       where z.txt = 'node-a' and level >  1 
                                       connect by prior z.root_id = z.node_id
                                       start with z.node_id = i.node_id )
                          )
;
   NODE_ID TXT
 ---------- ----------------------------------------
 
	  3  node-a
	  7  ..node-f
	 13  ....node-v
	 14  ....node-a
	  8  ..node-d
	  9  ..node-a
	  5  node-a
	 10  node-a
	 15  ..node-n
	 16  ..node-m
	 17  ..node-l

Dlya podtvergdeniya - polnoe derevo:
Код: plaintext
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.
select t.node_id, substr(lpad('.',(level- 1 )* 2 ,'.') || t.txt, 1 , 40 ) txt
from train.test_tree t
connect by prior t.node_id = t.root_id
start with t.node_id =  1 ;
   NODE_ID TXT
 ---------- ----------------------------------------
 
	  1  node- 1 
	  2  ..node-b
	  5  ....node-a
	  6  ....node-e
	  3  ..node-a
	  7  ....node-f
	 13  ......node-v
	 14  ......node-a
	  8  ....node-d
	  9  ....node-a
	  4  ..node-d
	 10  ....node-a
	 15  ......node-n
	 16  ......node-m
	 17  ......node-l
	 11  ....node-x
	 12  ....node-c
	 18  ......node-k
	 19  ......node-j

Gelau udachi.
...
Рейтинг: 0 / 0
12.02.2003, 19:52
| Ответить | Цитировать | Написать  
Поиск по дереву
    #32105443
Фотография judge
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
judge
Участник
Большое спасибо!

То что нужно.

Alex

PS. Может в FAQ это?
...
Рейтинг: 0 / 0
13.02.2003, 01:01
| Ответить | Цитировать | Написать  
Поиск по дереву
    #32105452
Фотография judge
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
judge
Участник
Оказалось немного не так.
У меня дерево например такое:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
  NODE_ID TXT
 ---------- ----------------------------------------
 
	  1  node- 1 
	  2  ..node-b
	  3  ....node-a
	  4  ....node-e
	  5  node- 1 
	  6  ..node-f
	  7  ....node-v
	  8  ......node-a
	  9  ....node-d
	 10  ....node-a
	 11  node- 1 
	 12  ..node-e
	 13  ....node-a


и если выбирать например node-e, то результат должен быть

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
  NODE_ID TXT
 ---------- ----------------------------------------
 
	  1  node- 1 
	  2  ..node-b
	  3  ....node-a
	  4  ....node-e
	 11  node- 1 
	 12  ..node-e
	 13  ....node-a


т.е. вся ветвь (это наверное уже под-дерево) начиная от корневого узла (у которого родитель null) должна включаться в выборку.

Alex
...
Рейтинг: 0 / 0
13.02.2003, 01:26
| Ответить | Цитировать | Написать  
Поиск по дереву
    #32105453
vskv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
vskv
Участник
Нет под рукой Оракула, чтобы проверить, но, по-моему, должно сработать следующее:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
select t.node_id, substr(lpad('.',(level- 1 )* 2 ,'.') || t.txt, 1 , 40 ) txt
from train.test_tree t
connect by prior t.node_id = t.root_id
start with t.node_id in (
        select distinct z.node_id from (
                 select i.node_id, i.root_id
                 from train.test_tree i
                 connect by prior i.root_id = i.node_id
                 start with i.txt = 'node-a'
       ) z
       where z.root_id is null
)

Основная идея -- расскрутить дерево обратно от ключевого листа и отобрать вершины деревьев.
...
Рейтинг: 0 / 0
13.02.2003, 02:18
| Ответить | Цитировать | Написать  
Поиск по дереву
    #32105467
ShgGena
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ShgGena
Участник
Значит я несколько недопонял задачу.
Но в этой постановке она решается намного проще.
1) Получить корневые узлы САМОГО ВЕРХНЕГО УРОВНЯ для каждого узла у которого выполняется требуемое условие.
2) Построить поддеревья для каждого ВЫБРАННОГО КОРНЕВОГО УЗЛА.

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

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
truncate table train.test_tree;
insert into train.test_tree values (  2 ,   0 , 'node-b');
insert into train.test_tree values (  3 ,   0 , 'node-a');
insert into train.test_tree values (  4 ,   0 , 'node-d');
insert into train.test_tree values (  5 ,   2 , 'node-s');
insert into train.test_tree values (  6 ,   2 , 'node-e');
insert into train.test_tree values (  7 ,   3 , 'node-f');
insert into train.test_tree values (  8 ,   3 , 'node-d');
insert into train.test_tree values (  9 ,   3 , 'node-a');
insert into train.test_tree values (  10 ,  4 , 'node-a');
insert into train.test_tree values (  11 ,  4 , 'node-x');
insert into train.test_tree values (  12 ,  4 , 'node-c');
insert into train.test_tree values (  13 ,  7 , 'node-v');
insert into train.test_tree values (  14 ,  7 , 'node-a');
insert into train.test_tree values (  15 ,  10 , 'node-n');
insert into train.test_tree values (  16 ,  10 , 'node-m');
insert into train.test_tree values (  17 ,  10 , 'node-l');
insert into train.test_tree values (  18 ,  12 , 'node-k');
insert into train.test_tree values (  19 ,  12 , 'node-j');


Запрос теперь выглядит так:
-- внутренний подзапрос выбирает ТОЛЬКО корневые узлы обратным проходом
от узлов для которых выполняется условие.
Код: plaintext
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.
select t.node_id, substr(lpad('.',(level- 1 )* 2 ,'.') || t.txt, 1 , 40 ) txt
from train.test_tree t
connect by prior t.node_id = t.root_id
start with t.node_id in ( select i.node_id from train.test_tree i
                          where i.root_id =  0 
                          connect by prior i.root_id = i.node_id
                          start with i.txt = 'node-a')
;
   NODE_ID TXT
 ---------- ----------------------------------------
 
          3  node-a
          7  ..node-f
         13  ....node-v
         14  ....node-a
          8  ..node-d
          9  ..node-a
          4  node-d
         10  ..node-a
         15  ....node-n
         16  ....node-m
         17  ....node-l
         11  ..node-x
         12  ..node-c
         18  ....node-k
         19  ....node-j
 15  rows selected.


Примечание запрос проверен и при множественных узлах в поддеревьях.
Для узла = node-a
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
   NODE_ID TXT
 ---------- ----------------------------------------
 
          3  node-a
          7  ..node-f
         13  ....node-v
         14  ....node-a
          8  ..node-d
          9  ..node-a
          4  node-d
         10  ..node-a
         15  ....node-n
         16  ....node-m
         17  ....node-l
         11  ..node-a
         12  ..node-c
         18  ....node-a
         19  ....node-j
 15  rows selected.
...
Рейтинг: 0 / 0
13.02.2003, 06:22
| Ответить | Цитировать | Написать  
Поиск по дереву
    #32106018
Фотография judge
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
judge
Участник
Всем спасибо!

Оба примера работают отлично. Есть еще вопрос о том как можно оптимизировать этот запрос?
У меня в таблице всего 3371 записей.
Когда я выполняю запросы, то например, запрос возвращающий 1181 записей выполняется около 14 секунд! Можно ли как нибудь ускорить выполнение запроса или для этого придется отказаться от использования connect by / start with ? Я использую PLSQL/Developer и воспользовался функцией explain plan (optimizer goal = choose) для этого запроса

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
select t.id, t.programme, t.episode
from hr_archive t
connect by prior t.id = t.parent_id
start with t.id in ( select i.id from hr_archive i
                          where i.parent_id = - 1 
                          connect by prior i.parent_id = i.id
                          start with upper(i.episode) like  '%ON%')


Вот какой план мне выдал oracle:

Код: plaintext
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.
SELECT STATEMENT, GOAL = CHOOSE					
 CONNECT BY WITH FILTERING					
  NESTED LOOPS					
   NESTED LOOPS					
    VIEW	SYS	VW_NSO_1			
     SORT UNIQUE					
      FILTER					
       CONNECT BY WITH FILTERING					
        NESTED LOOPS					
         TABLE ACCESS FULL	TMDDBA	HR_ARCHIVE			
         TABLE ACCESS BY USER ROWID	TMDDBA	HR_ARCHIVE			
        NESTED LOOPS					
         BUFFER SORT					
          CONNECT BY PUMP					
         TABLE ACCESS BY INDEX ROWID	TMDDBA	HR_ARCHIVE			
          INDEX RANGE SCAN	TMDDBA	HR_ARCHIVE_ID_IDX			
    INDEX RANGE SCAN	TMDDBA	HR_ARCHIVE_ID_IDX			
   TABLE ACCESS BY USER ROWID	TMDDBA	HR_ARCHIVE			
  NESTED LOOPS					
   BUFFER SORT					
    CONNECT BY PUMP					
   TABLE ACCESS BY INDEX ROWID	TMDDBA	HR_ARCHIVE			
    INDEX RANGE SCAN	TMDDBA	HR_ARCHIVE_PARENT_ID_IDX			
  FILTER					
   CONNECT BY WITH FILTERING					
    NESTED LOOPS					
     TABLE ACCESS FULL	TMDDBA	HR_ARCHIVE			
     TABLE ACCESS BY USER ROWID	TMDDBA	HR_ARCHIVE			
    NESTED LOOPS					
     BUFFER SORT					
      CONNECT BY PUMP					
     TABLE ACCESS BY INDEX ROWID	TMDDBA	HR_ARCHIVE			
      INDEX RANGE SCAN	TMDDBA	HR_ARCHIVE_ID_IDX


Alex
...
Рейтинг: 0 / 0
13.02.2003, 15:42
| Ответить | Цитировать | Написать  
Поиск по дереву
    #32106037
.dba
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
.dba
Участник
статистика собиралась? Когда и какая?
Как установлен параметер optimizer_index_cost_adj?
...
Рейтинг: 0 / 0
13.02.2003, 16:00
| Ответить | Цитировать | Написать  
Поиск по дереву
    #32106051
Фотография judge
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
judge
Участник
Нет не собиралась. А как ее собирать? и какую?
optimizer_index_cost_adj = 100 (как я понимаю по умолчанию установлен)

Я по администрированию Oracle очень мало чего знаю. В основном с MSSQL работаю, но иногда приходится и под Oracle писать.

Alex
...
Рейтинг: 0 / 0
13.02.2003, 16:12
| Ответить | Цитировать | Написать  
Поиск по дереву
    #32106063
.dba
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
.dba
Участник
Ну в общем тут надо осторожно, т.к. если база боевая и некоторые запросы заточены на то, что статистики нет, то при сборе они могут начать тормозить.
Но если можно пробовать, то:

SQL> analyze table hr_archive compute statistics;

SQL>alter session set optimizer_index_cost_adj = 1;

SQL>alter session set sort_area_size = 10000000;

ну и теперь запрос.
...
Рейтинг: 0 / 0
13.02.2003, 16:25
| Ответить | Цитировать | Написать  
Поиск по дереву
    #32106074
Фотография judge
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
judge
Участник
База тестовая.
Попробовал - те же 14 секунд.

Alex
...
Рейтинг: 0 / 0
13.02.2003, 16:31
| Ответить | Цитировать | Написать  
Поиск по дереву
    #32106089
.dba
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
.dba
Участник
а... там full сканы идут из-за
Код: plaintext
like  '%ON%'
. Но, думаю, что от этого не избавится, если только это не стоит в начале или конце строки. Или если уж производительность суперкритична, то я бы добавил столбец в котором можно искать вот так
Код: plaintext
like  'ON%'
или вот так
Код: plaintext
like  '%ON'
.

а план после сбора статистики и изменении параметров не поменялся? Можно еще попробовать собрать вот так:

SQL> analyze table hr_archive compute statistics for all indexed columns size 100;
...
Рейтинг: 0 / 0
13.02.2003, 16:41
| Ответить | Цитировать | Написать  
Поиск по дереву
    #32106155
Фотография Scott Tiger
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Scott Tiger
Участник
А с какого бодуна на '%ON' будут использоваться индексы?
...
Рейтинг: 0 / 0
13.02.2003, 17:17
| Ответить | Цитировать | Написать  
Поиск по дереву
    #32106157
.dba
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
.dba
Участник
>А с какого бодуна на '%ON' будут использоваться индексы?

с реверсивного :-) Реверсный индекс строить надо.
...
Рейтинг: 0 / 0
13.02.2003, 17:18
| Ответить | Цитировать | Написать  
Поиск по дереву
    #32106158
Фотография judge
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
judge
Участник
Мне кажется? проблема в том, что даже без ограничений по like, если я просто строю все целиком дерево из 3100 записей - он строится > 10 сек :(

Наверное, connect by/start width - можно использовать на небольших деревьях
,но для больших это не подходит

Alex
...
Рейтинг: 0 / 0
13.02.2003, 17:19
| Ответить | Цитировать | Написать  
Поиск по дереву
    #32106209
ShgGena
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ShgGena
Участник
Ya stroil derevya na 100 000 (primerno), sobiraus testirovat dlia 500 000 i 1 000 000.
Vremia vipolneniya zavisit ot dvux osnovnih parametrov
-- "shirota" dereva (bolsee kolichestvo uzlov pri menshem kolichestve urovney) --> chem shire tem medlennee
-- kolichestvo uzlov

No na 100000 pri dostatochno tyagelom zaproce, kogra dlya kazdogo uzla stroilsya obratniy prohod po derevy v korrelirovannom podzaprose maksimalnoe vremya bilo 1 min. 23 sek (na pamiyat)
I eto na domashney mashine:
-- oracle 9.2.0
-- Suse 8.0
-- op 512 /sga 80/ dbcache - 128
-- amd athlon 1600 (vagno poskolky nekotorie zaprosy porogdaut ogromnoe kolichestvo korotkih
sortirovok v pamyati (dlya kotorih ne trebuetsya passhirenie sort_area a tolko CPU perfomance)
...
Рейтинг: 0 / 0
13.02.2003, 18:21
| Ответить | Цитировать | Написать  
Поиск по дереву
    #32106227
Фотография Scott Tiger
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Scott Tiger
Участник
Реверсивный бодун - это мощно! Надо попробовать :)
...
Рейтинг: 0 / 0
13.02.2003, 18:52
| Ответить | Цитировать | Написать  
22 сообщений из 22, страница 1 из 1
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Поиск по дереву
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=52&msg=32106018&tid=1991825]:
 0ms
get settings:
 10ms
get forum list:
 20ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 425ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 56ms
get tp. blocked users:
 2ms
others: 232ms
total:  763ms
созд. / загр.: 763ms
x
x
Закрыть


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