Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Oracle Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
Валерий Юринский
Member

Откуда: Москва, "ФОРС Дистрибуция"
Сообщений: 1233
Задание 6. Иерархия блокировок (8 баллов)

В некоторой Системе существует таблица LOCKS с двумя столбцами - Locker и Locked, каждая запись в которой связывает 2 объекта - заблокированного (Locked) и того, кто его заблокировал (Locker). Необходимо отобразить SQL-запросом иерархию заблокированных объектов, включая те объекты, которые являются причинами всех блокировок. Уровни иерархии выделять отступами от левого края состоящими из пробелов - по одному на каждый новый уровень.

Пример:
LOCKS 
Locker Locked 
------ ------
A      B 
A      C 
B      D 
D      E 
C      F 
C      J 
C      H 
Надо вывести:
A 
 B 
  D 
   E 
 C 
  F 
  H 
  J 
Сдвиг - один пробел

Сообщение было отредактировано: 12 янв 09, 16:58
12 янв 09, 15:55    [6673142]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
Валерий Юринский
Member

Откуда: Москва, "ФОРС Дистрибуция"
Сообщений: 1233
Скрипт для создания и заполнения таблицы LOCKS содержится в файле,
прикрепленном к данному сообщению.

К сообщению приложен файл (TASK_06_DATA.sql - 496bytes) cкачать

Сообщение было отредактировано: 12 янв 09, 16:58
12 янв 09, 15:57    [6673171]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
Валерий Юринский
Member

Откуда: Москва, "ФОРС Дистрибуция"
Сообщений: 1233
Общие наблюдения

На практике такая задача возникает при построении цепочки блокирующих друг друга сессий Oracle для выявления "корня зла" – сессии, блокирующей всех.

Основная проблема заключается в том, что системные представления (view) выдают пары: блокирующий – заблокированный, и для построения иерархического запроса не хватает либо "корней", либо "листьев".

Задачу проще решать добавлением "корней" и последующим построением дерева блокировок с помощью обычного иерархического запроса к полученным виртуальным данным. Именно разными способами выявления "корней" и отличались решения участников.

Сообщение было отредактировано: 12 янв 09, 16:59
12 янв 09, 15:59    [6673188]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
Валерий Юринский
Member

Откуда: Москва, "ФОРС Дистрибуция"
Сообщений: 1233
Далее приведены решения участников Олимпиады 2008

Сообщение было отредактировано: 12 янв 09, 16:59
12 янв 09, 15:59    [6673193]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
Валерий Юринский
Member

Откуда: Москва, "ФОРС Дистрибуция"
Сообщений: 1233
Решение 1. NOT IN и "корневая" псевдозапись с идентификатором блокирующего равным '-1'

Недостаток решения – это предположение, что в реальных данных не может быть строк, содержащих LOCKER = '-1'.

SELECT LPAD(id, LEVEL, ' ') 
FROM (SELECT locker AS id_id, locked AS id  
      FROM locks  
      UNION   
      SELECT '-1', locker  
      FROM locks  
      WHERE locker NOT IN (SELECT locked FROM locks))  
CONNECT BY PRIOR id = id_id  
START WITH id_id = '-1';


Сообщение было отредактировано: 12 янв 09, 16:59
12 янв 09, 16:01    [6673213]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
Валерий Юринский
Member

Откуда: Москва, "ФОРС Дистрибуция"
Сообщений: 1233
Решение 2. NOT IN и "корневая" псевдозапись с NULL-идентификатором блокирующего

По сути, совпадает с решением 1, однако использование NULL не требует никаких дополнительных предположений о содержании данных.

SELECT LPAD(locked, LENGTH(locked)+(level-1), ' ') 
FROM   (SELECT * FROM locks
        UNION   
        SELECT NULL, locker 
        FROM locks  
        WHERE locker NOT IN (SELECT locked FROM locks))  
CONNECT BY PRIOR locked = locker  
START WITH locker IS NULL;


Сообщение было отредактировано: 12 янв 09, 16:59
12 янв 09, 16:02    [6673227]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
Валерий Юринский
Member

Откуда: Москва, "ФОРС Дистрибуция"
Сообщений: 1233
Решение 3. Использование операторов над множествами

Здесь для получения необходимого иерархического набора данных использованы только операторы над множествами (set operators).

SELECT LPAD('  ', (LEVEL-1), ' ') || locked  
FROM (SELECT NULL AS locker, Locker AS locked 
      FROM locks  
      MINUS   
      SELECT null AS locker, locked AS locked 
      FROM locks  
      UNION  
      SELECT Locker, locked 
      FROM locks) 
START WITH locker IS NULL  
CONNECT BY PRIOR locked = locker;


Сообщение было отредактировано: 12 янв 09, 17:00
12 янв 09, 16:03    [6673234]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
Валерий Юринский
Member

Откуда: Москва, "ФОРС Дистрибуция"
Сообщений: 1233
Решение 4. Группировка, заменяющая DISTINCT, и внешнее соединение, заменяющее NOT IN / NOT EXISTS

SELECT LPAD(locked, LEVEL, ' ') 
FROM (SELECT locker, locked FROM locks  
      UNION ALL 
      (SELECT null AS locker, locker AS locked 
       from   (SELECT locker FROM locks GROUP BY locker)  
               LEFT OUTER JOIN   
              (SELECT locked FROM locks GROUP BY locked)  
               ON locker = locked 
       WHERE locked IS NULL))  
START WITH locker IS NULL 
CONNECT BY PRIOR locked = locker;


Сообщение было отредактировано: 12 янв 09, 17:00
12 янв 09, 16:06    [6673267]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
Валерий Юринский
Member

Откуда: Москва, "ФОРС Дистрибуция"
Сообщений: 1233
Конец публикации Задания 6

Сообщение было отредактировано: 12 янв 09, 17:00
12 янв 09, 16:07    [6673270]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
vlock
Guest
Валерий Юринский
Общие наблюдения

Основная проблема заключается в том, что системные представления (view) выдают пары: блокирующий – заблокированный, и для построения иерархического запроса не хватает либо "корней", либо "листьев".


v$lock - основное вью, которое даёт достаточную информацию о блокировках.
Все блокировки в Oracle привязаны к ресурсам, которые определяются type, id1, id2. И если данная блокировка приводит к очереди, то BLOCK=1.
Для отображении иерархии ожидающих блокировок на одном уровне нужно знать время запроса блокировки на соответствующий ресурс, формально это можно по wait_time определить(то есть сделать сортировку по данному полю).

Не могли бы Вы уточнить, о каких системных вью идёт речь: "системные представления (view) выдают пары: блокирующий – заблокированный"?

Сообщение было отредактировано: 12 янв 09, 17:00
12 янв 09, 16:16    [6673355]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
GL
Member

Откуда: Харьков
Сообщений: 1513
Валерий Юринский,

в тексте задания ничего не написано о циклах. понятно, что ни одно из преведенных решений с ними не справляется. это так и задумано (и задание не полно) или это выпало из поля зрения?

Сообщение было отредактировано: 12 янв 09, 17:00
12 янв 09, 16:19    [6673381]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
hell
Member

Откуда:
Сообщений: 3001
https://www.sql.ru/forum/actualthread.aspx?bid=3&tid=423197&hl=
__________________
For more information, please proceed to http://www.ot-e.biz
12 янв 09, 17:13    [6673813]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
ziderzee
Member

Откуда: Москва
Сообщений: 17
Четвертый вариант с NOT EXISTS

SELECT lpad(' ', level - 1) || id txt
FROM (

	SELECT null as parent, l1.locker as id
	FROM locks l1
	WHERE not exists(
		select 1
		from locks l2
		where l2.locked = l1.locker
	)
	GROUP BY l1.locker

	UNION

	SELECT locker as parent, locked as id
	FROM locks

)
CONNECT BY parent = prior id
START WITH parent is null
/
12 янв 09, 17:40    [6674001]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
I00N
Member

Откуда:
Сообщений: 454
Зачем использовать UNION там, где достаточно UNION ALL?

Возник вопрос: возможно ли за одно обращение к таблице вывести все записи и дополнительное поле:
locker, locked, <заблокирован ли locker - 0 либо 1>
12 янв 09, 19:49    [6674579]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
Elic
Member

Откуда:
Сообщений: 29976
I00N
возможно ли за одно обращение к таблице вывести все записи и дополнительное поле: <заблокирован ли locker - 0 либо 1>
Можно. STFF подсчет деток
12 янв 09, 20:01    [6674605]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
ziderzee
Member

Откуда: Москва
Сообщений: 17
I00N
Зачем использовать UNION там, где достаточно UNION ALL?


Согласен. UNION ALL уберет затратную SORT UNIQUE.

I00N

Возник вопрос: возможно ли за одно обращение к таблице вывести все записи и дополнительное поле:
locker, locked, <заблокирован ли locker - 0 либо 1>



А там и так только к индексу обращения идут.

-----------------------------------------------------------------------------------
| Id  | Operation               | Name    | Rows  | Bytes | Cost (%CPU)| Time     |
-----------------------------------------------------------------------------------
|   0 | SELECT STATEMENT        |         |     8 |   224 |     8  (38)| 00:00:01 |
|   1 |  UNION-ALL              |         |       |       |            |          |
|   2 |   SORT GROUP BY NOSORT  |         |     1 |    28 |     5   (0)| 00:00:01 |
|   3 |    NESTED LOOPS ANTI    |         |     1 |    28 |     5   (0)| 00:00:01 |
|   4 |     INDEX FULL SCAN     | LOCKS#P |     7 |    98 |     2   (0)| 00:00:01 |
|*  5 |     INDEX FAST FULL SCAN| LOCKS#P |     7 |    98 |     0   (0)| 00:00:01 |
|   6 |   INDEX FAST FULL SCAN  | LOCKS#P |     7 |   196 |     2   (0)| 00:00:01 |
-----------------------------------------------------------------------------------
12 янв 09, 20:03    [6674610]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
ERROR MESSAGE
Member

Откуда: Москва
Сообщений: 376
ziderzee
Четвертый вариант с NOT EXISTS

SELECT lpad(' ', level - 1) || id txt
FROM (

	SELECT null as parent, l1.locker as id
	FROM locks l1
	WHERE not exists(
		select 1
		from locks l2
		where l2.locked = l1.locker
	)
	GROUP BY l1.locker

	UNION

	SELECT locker as parent, locked as id
	FROM locks

)
CONNECT BY parent = prior id
START WITH parent is null
/

Тута вообще можно обойтися без GROUP BY l1.locker
Оно здеся вовсе ненафиг не нужно
12 янв 09, 20:15    [6674643]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
I00N
Member

Откуда:
Сообщений: 454
ziderzee

А там и так только к индексу обращения идут.

Я имел ввиду одно упоминание таблицы в запросе
12 янв 09, 20:35    [6674704]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
ziderzee
Member

Откуда: Москва
Сообщений: 17
ERROR MESSAGE

Тута вообще можно обойтися без GROUP BY l1.locker
Оно здеся вовсе ненафиг не нужно



Без GROUP BY можно обойтись, тогда нужно использовать UNION

  1     SELECT null as parent, l1.locker as id
2 FROM locks l1
3 WHERE not exists(
4 select 1
5 from locks l2
6 where l2.locked = l1.locker
7 )
8 UNION
9 SELECT locker as parent, locked as id
10* FROM locks

-----------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-----------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 8 | 224 | 9 (56)| 00:00:01 |
| 1 | SORT UNIQUE | | 8 | 224 | 9 (56)| 00:00:01 |
| 2 | UNION-ALL | | | | | |
|* 3 | HASH JOIN ANTI | | 1 | 28 | 5 (20)| 00:00:01 |
| 4 | INDEX FAST FULL SCAN| LOCKS#P | 7 | 98 | 2 (0)| 00:00:01 |
| 5 | INDEX FAST FULL SCAN| LOCKS#P | 7 | 98 | 2 (0)| 00:00:01 |
| 6 | INDEX FAST FULL SCAN | LOCKS#P | 7 | 196 | 2 (0)| 00:00:01 |
-----------------------------------------------------------------------------------


а вот вариант с GROUP BY

  1     SELECT null as parent, l1.locker as id
2 FROM locks l1
3 WHERE not exists(
4 select 1
5 from locks l2
6 where l2.locked = l1.locker
7 )
8 GROUP BY l1.locker
9 UNION ALL
10 SELECT locker as parent, locked as id
11* FROM locks

-----------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-----------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 8 | 224 | 8 (38)| 00:00:01 |
| 1 | UNION-ALL | | | | | |
| 2 | SORT GROUP BY NOSORT | | 1 | 28 | 5 (0)| 00:00:01 |
| 3 | NESTED LOOPS ANTI | | 1 | 28 | 5 (0)| 00:00:01 |
| 4 | INDEX FULL SCAN | LOCKS#P | 7 | 98 | 2 (0)| 00:00:01 |
|* 5 | INDEX FAST FULL SCAN| LOCKS#P | 7 | 98 | 0 (0)| 00:00:01 |
| 6 | INDEX FAST FULL SCAN | LOCKS#P | 7 | 196 | 2 (0)| 00:00:01 |
-----------------------------------------------------------------------------------

Если отказаться от GROUP BY и от UNION, то из-за того что "A" встречается несколько раз в столбце locker, у иерархического дерева будет несколько одинаковых корней. Как следствие - несколько одинаковых деревьев в результате
12 янв 09, 20:42    [6674729]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
ERROR MESSAGE
Member

Откуда: Москва
Сообщений: 376
ziderzee
ERROR MESSAGE

Тута вообще можно обойтися без GROUP BY l1.locker
Оно здеся вовсе ненафиг не нужно

Без GROUP BY можно обойтись, тогда нужно использовать UNION
А у тебя тама что было, друже?
Разве тама ты впендюхал не UNION? ))

Ты уж реши, мил человек, что тебе нужнее UNION или GROUP BY для достижения нужной DISTINCTности ))
А ужо потома можешь планы автотрасс выставлять и синькой их подукрашивать ))
12 янв 09, 20:52    [6674752]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
ziderzee
Member

Откуда: Москва
Сообщений: 17
ERROR MESSAGE
ziderzee
ERROR MESSAGE

Тута вообще можно обойтися без GROUP BY l1.locker
Оно здеся вовсе ненафиг не нужно

Без GROUP BY можно обойтись, тогда нужно использовать UNION
А у тебя тама что было, друже?
Разве тама ты впендюхал не UNION? ))

Ты уж реши, мил человек, что тебе нужнее UNION или GROUP BY для достижения нужной DISTINCTности ))
А ужо потома можешь планы автотрасс выставлять и синькой их подукрашивать ))


Мне нужнее оптимальность. Поэтому GROUP BY там нужно. См. планы.
12 янв 09, 21:53    [6674930]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
I00N
Member

Откуда:
Сообщений: 454
Апаю свой вопрос
I00N
Возник вопрос: возможно ли за одно обращение к таблице вывести все записи и дополнительное поле:
locker, locked, <заблокирован ли locker - 0 либо 1>
12 янв 09, 22:54    [6675165]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
TRust
Member

Откуда: из самоизоляции
Сообщений: 286
GL
в тексте задания ничего не написано о циклах. понятно, что ни одно из преведенных решений с ними не справляется. это так и задумано (и задание не полно) или это выпало из поля зрения?

Конечно, исключение цикличности придало бы недостающую полноту решениям, однако все приведённые решения были засчитаны. В задании ведь речь идёт об абстрактных блокировках, не имея ввиду въюшку v$lock. Если предполагать наличие циклов, то всё становтся сложнее и неоднозначнее...
12 янв 09, 23:01    [6675185]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
Elic
Member

Откуда:
Сообщений: 29976
I00N
Апаю свой вопрос
Нужно обязательно разжевать? :)
13 янв 09, 08:32    [6675782]     Ответить | Цитировать Сообщить модератору
 Re: Oracle-Олимпиада 2008. Задание 6. Иерархия блокировок  [new]
I00N
Member

Откуда:
Сообщений: 454
Elic
I00N
Апаю свой вопрос
Нужно обязательно разжевать? :)


Нет, не нужно! Умудрился не заметить Ваш пост :)
13 янв 09, 08:42    [6675792]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Oracle Ответить