Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Oracle Новый топик    Ответить
Топик располагается на нескольких страницах: 1 2 3 4 5 6 7 8      [все]
 Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Это очередная вариация на тему интервалов. Мне подобное на форуме не попадалось, но сорри если баян.

Есть интервалы двух цветов и требуется получить результирующую разбивку как показано ниже.
with t (x1, x2, c) as
(
select 1, 4, 'red' from dual
union all select 7, 10, 'red' from dual
union all select 13, 16, 'red' from dual
union all select 3, 14, 'black' from dual
union all select 16, 19, 'black' from dual
union all select 18, 22, 'red' from dual
union all select 22, 25, 'black' from dual
union all select 26, 28, 'red' from dual
union all select 29, 30, 'black' from dual
union all select 32, 33, 'black' from dual
)
select ...
/

        X1         X2 RESULT
---------- ---------- -------
         1          2 red
         3          4 overlap
         5          6 black
         7         10 overlap
        11         12 black
        13         14 overlap
        15         15 red
        16         16 overlap
        17         17 black
        18         19 overlap
        20         21 red
        22         22 overlap
        23         25 black
        26         28 red
        29         30 black
        31         31 none
        32         33 black

17 rows selected.
Входные интервалы каждого отдельного цвета не пересекаются и не соприкасаются.

Картинка вероятно нагляднее покажет как получен результат.

К сообщению приложен файл. Размер - 24Kb
13 ноя 20, 14:42    [22231442]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
env
Member

Откуда: Россия, Москва
Сообщений: 6749
Кобанчег,

Верхняя и нижняя граница всегда определены имеющимися интервалами?
13 ноя 20, 15:09    [22231455]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
env,

Не совсем понял вопрос. На выходе должен быть диапазон от начала первого до конца последнего.
13 ноя 20, 15:21    [22231468]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
env
Member

Откуда: Россия, Москва
Сообщений: 6749
Кобанчег,

Напрашивается решение через непрерывный список от min до max и start of group, но это видимо слишком простое и очевидное.

+
with t (x1, x2, c) as
(
select 1, 4, 'red' from dual
union all select 7, 10, 'red' from dual
union all select 13, 16, 'red' from dual
union all select 3, 14, 'black' from dual
union all select 16, 19, 'black' from dual
union all select 18, 22, 'red' from dual
union all select 22, 25, 'black' from dual
union all select 26, 28, 'red' from dual
union all select 29, 30, 'black' from dual
union all select 32, 33, 'black' from dual
),
minmax as (
    select
        min(x1)     mn,
        max(x2)     mx
    from
        t
), 
nums as (
    select
        mn + level - 1 n
    from
        minmax
    connect by
        level <= mx - mn + 1
), 
vect as (
    select
        n,
        decode(count(distinct t.c), 1, max(c), 0, 'none', 'overlap') c
    from
        nums,
        t
    where
        nums.n between t.x1 (+) and t.x2 (+)
    group by
        nums.n
), 
sog as (
    select
        n,
        c,
        decode(c, lag(c, 1, c) over(order by n), 0, 1) g
    from
        vect
), 
grp as (
    select
        n,
        c,
        sum(g) over(order by n) gr
    from
        sog
)
select
    min(n),
    max(n),
    max(c)
from
    grp
group by
    gr
order by
    gr;

    MIN(N)     MAX(N) MAX(C)
---------- ---------- -------
         1          2 red
         3          4 overlap
         5          6 black
         7         10 overlap
        11         12 black
        13         14 overlap
        15         15 red
        16         16 overlap
        17         17 black
        18         19 overlap
        20         21 red
        22         22 overlap
        23         25 black
        26         28 red
        29         30 black
        31         31 none
        32         33 black


Сообщение было отредактировано: 13 ноя 20, 15:49
13 ноя 20, 15:51    [22231486]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
Кобанчег,

red =1
black=2
суммируем с перекрытием
3-overlap
0-прозрачный


.....
stax
13 ноя 20, 15:56    [22231491]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Вячеслав Любомудров
Member

Откуда: Владивосток
Сообщений: 18486
model + overlap ?
13 ноя 20, 15:58    [22231492]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Elic
Member

Откуда:
Сообщений: 29991
Кобанчег
если баян
join с подинтервальчиками.
13 ноя 20, 16:00    [22231497]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Вячеслав Любомудров
Member

Откуда: Владивосток
Сообщений: 18486
Кстати, насколько помню была какая-то не[полностью]документированная функция типа именно overlap для работы с датами и числами
Или только датами/диапазонами(?)
13 ноя 20, 16:01    [22231499]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
Stax
Кобанчег,

red =1
black=2
суммируем с перекрытием
3-overlap
0-прозрачный


зі
нашел
https://www.sql.ru/forum/1297132/razdelit-na-neperesekaushhiesya-intervaly-dat-otrezki-s-ssumirovaniem-summy-v-peresecheniyah

.....
stax
13 ноя 20, 16:08    [22231507]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
env
Кобанчег,

Напрашивается решение через непрерывный список от min до max и start of group, но это видимо слишком простое и очевидное.

+
with t (x1, x2, c) as
(
select 1, 4, 'red' from dual
union all select 7, 10, 'red' from dual
union all select 13, 16, 'red' from dual
union all select 3, 14, 'black' from dual
union all select 16, 19, 'black' from dual
union all select 18, 22, 'red' from dual
union all select 22, 25, 'black' from dual
union all select 26, 28, 'red' from dual
union all select 29, 30, 'black' from dual
union all select 32, 33, 'black' from dual
),
minmax as (
    select
        min(x1)     mn,
        max(x2)     mx
    from
        t
), 
nums as (
    select
        mn + level - 1 n
    from
        minmax
    connect by
        level <= mx - mn + 1
), 
vect as (
    select
        n,
        decode(count(distinct t.c), 1, max(c), 0, 'none', 'overlap') c
    from
        nums,
        t
    where
        nums.n between t.x1 (+) and t.x2 (+)
    group by
        nums.n
), 
sog as (
    select
        n,
        c,
        decode(c, lag(c, 1, c) over(order by n), 0, 1) g
    from
        vect
), 
grp as (
    select
        n,
        c,
        sum(g) over(order by n) gr
    from
        sog
)
select
    min(n),
    max(n),
    max(c)
from
    grp
group by
    gr
order by
    gr;

    MIN(N)     MAX(N) MAX(C)
---------- ---------- -------
         1          2 red
         3          4 overlap
         5          6 black
         7         10 overlap
        11         12 black
        13         14 overlap
        15         15 red
        16         16 overlap
        17         17 black
        18         19 overlap
        20         21 red
        22         22 overlap
        23         25 black
        26         28 red
        29         30 black
        31         31 none
        32         33 black
Да, это весьма неэффективно и завязано на натуральные числа.
Интервалы могут быть произвольной длины и не обязательно с целыми границами.
13 ноя 20, 16:19    [22231521]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Stax
Stax
Кобанчег,

red =1
black=2
суммируем с перекрытием
3-overlap
0-прозрачный


зі
нашел
https://www.sql.ru/forum/1297132/razdelit-na-neperesekaushhiesya-intervaly-dat-otrezki-s-ssumirovaniem-summy-v-peresecheniyah

.....
stax
Идея понятна, но можно без джойнов и подзапросов.
13 ноя 20, 16:23    [22231526]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Elic
Кобанчег
если баян
join с подинтервальчиками.
Наиболее эффективно без джойнов.
Но некоторая баянистость просматривается, да.
13 ноя 20, 16:25    [22231530]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Вячеслав Любомудров
model + overlap ?
В тяжелой артиллерии нет особой необходимости.
Вячеслав Любомудров
Кстати, насколько помню была какая-то не[полностью]документированная функция типа именно overlap для работы с датами и числами
Или только датами/диапазонами(?)
overlaps

Но недокументированное это неспортивно (и для данной задачи нет надобности).
13 ноя 20, 16:29    [22231536]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
Кобанчег

Наиболее эффективно без джойнов.
Но некоторая баянистость просматривается, да.


unpivot можно?

для
union all select 7, 10, 'red' from dual
union all select 10, 14, 'black' from dual

10 10 overlap?

.....
stax
13 ноя 20, 16:36    [22231545]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Stax
unpivot можно?
Да всё что угодно можно.
Stax
10 10 overlap?
Да.

PS. На самом деле мне стоило состряпать более адекватный пример с real numbers
(тогда бы 10 10 было касание а не перекрытие на единицу) но уже есть как есть.
13 ноя 20, 16:43    [22231550]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Кобанчег
завязано на натуральные числа
Должен признать что моя постановка именно это и подразумевает, но всё равно генерить диапазоны connect by - не самый удачный вариант.
13 ноя 20, 16:47    [22231555]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
Кобанчег,

была идейка red full outer join black on пересекаются
но плюнул перебирать случаи пересечений
.....
stax
14 ноя 20, 12:11    [22231976]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Stax
Кобанчег,

red =1
black=2
суммируем с перекрытием
3-overlap
0-прозрачный


.....
stax

Суммировать хорошая идея, правда как без трансформации запроса это делать я не знаю.

Вижу примерно следующий алгоритм, x1 и x2 в один столбец, каждый признак (red, black) отдельным столбцом, для начала периода (x1) признаку +1, там где кончается период (x2) признаку -1, если накопительная сумма с учетом периода больше нуля значит признак в периоде (в вертикальном виде, период это две ближайшие строки) включен, если нет значит выключен, потом преобразовать обратно в периоды.

PS: реализовывать лень)))
14 ноя 20, 12:41    [22231997]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Stax
Кобанчег,

была идейка red full outer join black on пересекаются
но плюнул перебирать случаи пересечений
.....
stax
Да, при том подходе надо скурпулёзно все перебирать и солжно для понимания и поддержки имхо.

Более просто и эффективно развернуть все отрезки в один ряд (cross join/pivot) и определить что есть что в результате (аналитика/pattern matching).

В общем мое решение выглядит так
select x1, x2, result
from t unpivot (x for type in (x1, x2))
match_recognize
(
  order by x, type
  measures
    case when type = 'X2' and next(type) = 'X1' and next(x) - x =1 then 1 end touch,
    case when next(x) = x and next(type) = type then 1 end same_bound,
    x + decode(type, 'X2', 1, 0) x1,
    next(x) - decode(next(type), 'X1', 1, 0) x2,
    decode(sum(decode(c, 'red', 1, 'black', 2) * decode(type, 'X1', 1, 'X2', -1)),
           1, 'red', 2, 'black', 3, 'overlap', 'none') result    
  all rows per match
  pattern (x+)
  define x as next(x) is not null
)
where touch is null and same_bound is null


touch используется для фильтра когда конец одного соприкасается с началом другого,
а same_bound для исключения из результата первой из точек когда начала либо концы совпадают.
14 ноя 20, 15:38    [22232069]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
В общем эта была разминка, теперь предлагается задачка посложнее.

Необходимо наложить интервалы из источника на приемник с приоритетом из источника (если есть пересечение).

with t (x1, x2, c, flag) as
(
select 1, 4, 'red', 'src' from dual
union all select 7, 10, 'yellow', 'src' from dual
union all select 13, 16, 'red', 'src' from dual
--union all select 3, 14, 'black' from dual
union all select 3, 7, 'black', 'tgt' from dual
union all select 9, 11, 'black', 'tgt' from dual
union all select 13, 14, 'black', 'tgt' from dual
--
union all select 16, 19, 'blue', 'tgt' from dual
union all select 18, 22, 'green', 'src' from dual
union all select 22, 25, 'black', 'tgt' from dual
union all select 26, 28, 'red', 'src' from dual
union all select 29, 30, 'red', 'tgt' from dual
union all select 32, 33, 'black', 'tgt' from dual
)
select ...
/

        X1         X2 RESULT
---------- ---------- ------
         1          4 red
         5          6 black
         7         10 yellow
        11         11 black
        12         12
        13         16 red
        17         17 blue
        18         22 green
        23         25 black
        26         30 red
        31         31
        32         33 black

12 rows selected.
Здесь не удастся выкрутиться с decode + sum ибо цветов потенциально неограниченное множество.

И снова картинка для наглядности.

К сообщению приложен файл. Размер - 36Kb
14 ноя 20, 16:06    [22232077]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
graycode

PS: реализовывать лень)))


https://www.sql.ru/forum/1297132/razdelit-na-neperesekaushhiesya-intervaly-dat-otrezki-s-ssumirovaniem-summy-v-peresecheniyah

ета задачка даж проще, токо одно пересечение

.....
stax
14 ноя 20, 16:17    [22232081]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
del

Сообщение было отредактировано: 14 ноя 20, 19:50
14 ноя 20, 19:53    [22232123]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Кобанчег
В общем мое решение выглядит так

Это называется без тяжелой артиллерии?

Я думал без тяжелой артиллерии выглядит примерно так:
with t (x1, x2, c) as
(
select 1, 4, 'red' from dual
union all select 7, 10, 'red' from dual
union all select 13, 16, 'red' from dual
union all select 3, 14, 'black' from dual
union all select 16, 19, 'black' from dual
union all select 18, 22, 'red' from dual
union all select 22, 25, 'black' from dual
union all select 26, 28, 'red' from dual
union all select 29, 30, 'black' from dual
union all select 32, 33, 'black' from dual
)
, t1 (x, red, black) as
(
select x1 as x, decode(c, 'red', 1, 0), decode(c, 'black', 1, 0) from t
union all
select x2 + 1 as x, decode(c, 'red', -1, 0), decode(c, 'black', -1, 0) from t
)
, t2 (x, red, black) as
(
select distinct x
     , sum(red) over (order by x range unbounded preceding)
     , sum(black) over (order by x range unbounded preceding)
  from t1
)
, t3 (x1, x2, c) as
(
select x
     , lead(x) over (order by x) - 1
     , case when red > 0 and black > 0 then 'overlap'
            when red > 0 then 'red'
            when black > 0 then 'black'
            else 'none' end
  from t2
)
select * from t3 where x2 is not null order by x1
15 ноя 20, 00:53    [22232231]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Одно из решений.

p(r,clr,cln) as
(
select 0, null, null from dual union all
select r+1,
       nvl((select max(c) from t where flag='src' and r+1 between x1 and x2),
           (select max(c) from t where flag='tgt' and r+1 between x1 and x2)),
       nvl((select max(c) from t where flag='src' and r+2 between x1 and x2),
           (select max(c) from t where flag='tgt' and r+2 between x1 and x2))
  from p where r < (select max(x2) from t)
)
select nvl(lag(r) over (order by r),1) as y1,
       r as y2,
       clr
from p where sys_op_map_nonnull(clr) != sys_op_map_nonnull(cln)
15 ноя 20, 01:01    [22232233]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Кобанчег
Здесь не удастся выкрутиться с decode + sum ибо цветов потенциально неограниченное множество.

не так изящно конечно и наверное можно упростить, но выкрутиться можно))
, t1 (x, c_src, c_tgt, gr_src, gr_tgt) as
(
select x1 as x
     , decode(flag, 'src', c, ''), decode(flag, 'tgt', c, '')
     , decode(flag, 'src', 1, 0), decode(flag, 'tgt', 1, 0)
from t
union all
select x2 + 1 as x
     , '', ''
     , decode(flag, 'src', 1, 0), decode(flag, 'tgt', 1, 0)
  from t
)
, t2 (x, c_src, c_tgt, gr_src, gr_tgt) as
(
select x, c_src, c_tgt
     , sum(gr_src) over (order by x range unbounded preceding)
     , sum(gr_tgt) over (order by x range unbounded preceding)
  from t1
)
, t3 (x, c) as
(
select x
     , coalesce(min(c_src) keep (dense_rank first order by x) over (partition by gr_src),
                min(c_tgt) keep (dense_rank first order by x) over (partition by gr_tgt))
  from t2
)
, t4 (x, c) as
(
select min(x), min(c) from (
    select x, c, sum(sog) over (order by x) as gr from (
        select x, c
             , case nvl(c, 'none') when nvl(lag(c) over (order by x), 'none') then 0 else 1 end as sog
          from t3))
group by gr
)
, t5 (x1, x2, c) as
(
select x
     , lead(x) over (order by x) - 1
     , c
  from t4
)
select * from t5 where x2 is not null order by x1
15 ноя 20, 01:04    [22232236]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
graycode
Это называется без тяжелой артиллерии?
Тяжесть модели в ее прожорливости к CPU & RAM. Cоответсвенно пользоваться ею когда она тривиально заменяется аналитикой/pattern matching это не самая лучшая идея.

Если продолжить разговор про перфоманс далее, то даже однослойная аналитика уступает в производительности match_recognize а у тебя два WINDOW SORT.

В плане других замечаний - не лучшая мысль сканировать исходную таблицу дважды.
select x1 as x, decode(c, 'red', 1, 0), decode(c, 'black', 1, 0) from t
union all
select x2 + 1 as x, decode(c, 'red', -1, 0), decode(c, 'black', -1, 0) from t
cross join будет быстрее, а unpivot еще быстрее.

range unbounded preceding
Нет особого смысла указывать то, что и так по умолчанию.

В остальном, в решении всё разложено по полочкам, вполне прилично.
15 ноя 20, 01:39    [22232242]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
НеофитSQL
Одно из решений.
Это, конечно, креативно, но более неэффективного подхода придумать сложно.
Сгенерировать диапазон от начала первого до конца последнего можно было (но генерировать вообще не стоит) и с помощью connect by + nvl по двум скалярам.
В недокументированных функциях тоже никакого смысла нет.
15 ноя 20, 02:00    [22232245]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Кобанчег
НеофитSQL
Одно из решений.
Это, конечно, креативно, но более неэффективного подхода придумать сложно.
Сгенерировать диапазон от начала первого до конца последнего можно было (но генерировать вообще не стоит) и с помощью connect by + nvl по двум скалярам.
В недокументированных функциях тоже никакого смысла нет.


Вы перечислили несколько недостатков моего решения, там наверное еще десяток можно насчитать :)

Я не знаю как применить connect by в этом контексте, и использовал корявое формирование диапазонов надеясь, что кто-то знает как это делать правильно и эффективно.

Вы можете мне показать, как из этого:

with t (n, c) as
(
select 1, 'red' from dual
union all select 2, 'red' from dual
union all select 3, 'blue' from dual
union all select 4, 'red' from dual
}


Сделать такое:

1 2 red
3 3 blue
4 4 red

?

Числа последовательные, без дырок. Граничные условия не важны интересен принцип
15 ноя 20, 02:18    [22232248]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
graycode
не так изящно конечно и наверное можно упростить, но выкрутиться можно

Если я ничего не упустил в
keep (dense_rank first order by x)
смысла нет, там можно просто min.

У меня с аналитикой что-то аналогичное.
По сути итоговый цвет получается с помощью
nvl(decode(src_active, 1, src_c), decode(tgt_active, 1, tgt_c))
остальное - вариация на тему start of group.
, tt as
(
select x1,
       nvl(decode(src_active, 1, src_c), decode(tgt_active, 1, tgt_c)) result,
       lag(nvl(decode(src_active, 1, src_c), decode(tgt_active, 1, tgt_c))) over(order by x1) prev_result
  from (select x1,
               sum(decode(flag, 'src', sign)) over(order by x1, type) src_active,
               sum(decode(flag, 'tgt', sign)) over(order by x1, type) tgt_active,
               last_value(decode(flag, 'src', c) ignore nulls) over(order by x1, type) src_c,
               last_value(decode(flag, 'tgt', c) ignore nulls) over(order by x1, type) tgt_c
          from (select c,
                       flag,
                       type,
                       x + decode(type, 'X2', 1, 0) x1,
                       decode(type, 'X1', 1, 'X2', -1) sign
                  from t unpivot(x for type in(x1, x2)))) t
)
select *
  from (select min(x1) x1,
               lead(min(x1)) over(order by grp) - 1 x2,
               min(result) result
          from (select tt.*, sum(decode(result, prev_result, 0, 1)) over(order by x1) grp from tt)
         group by grp)
 where x2 is not null

Но еще была попытка изящно решить с помощью pattern matching.
15 ноя 20, 02:58    [22232250]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
НеофитSQL,

Если воспользоваться генератором из запроса env то можно дописать как-то так
(но здесь не нужен генератор и коррелированные скаляры тоже не нужны)
select min(n) x1, max(n) x2, result
  from (select t.*,
               n - row_number() over(partition by result order by n) grp
          from (select t.*,
                       nvl((select max(c) from t where flag = 'src' and n between x1 and x2),
                           (select max(c) from t where flag = 'tgt' and n between x1 and x2)) result
                  from nums t) t)
 group by result, grp
 order by 1
15 ноя 20, 03:04    [22232251]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Я пропустил упражнение-разминку, ответы еще принимаются?

select y1,y2,nvl(c,'none') from 
  (select lag(x) over (order by x) as y1, x-1 as y2, 
          (select nvl(listagg(c,',') within group (order by c),'none')
           from t where x-0.5 between x1 and x2+1) as c
    from (select x1 x from t union select x2+1 x from t))
 where y1 is not null
 order by y1
15 ноя 20, 04:18    [22232255]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Кобанчег
НеофитSQL,

Если воспользоваться генератором из запроса env то можно дописать как-то так
(но здесь не нужен генератор и коррелированные скаляры тоже не нужны)


Спасибо, напомнили про connect-by для генерации чисел, я редко его вижу.

Я спросил про connect-by, думая про задачу схлопывания интервалов.
Вы это назвали "beginning of group". Есть ли оконное выражение, которое позволяет обрабатывать повторяющуеся группы, как partition by позволяет обрабатывать уникальные группы?

Например, в следующем отсортитованном резалтсете есть три группы (апельсины:2, яблоки:2 и апельсины:1)
апельсин 2
апельсин 3
яблоко 1
яблоко 1
апельсин 1

Как в таком случае эти группы извлечь? Есть специальный оператор, или придется ловить начало группы, подглядывая соседние строчки?
15 ноя 20, 04:37    [22232256]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Кобанчег
Тяжесть модели в ее прожорливости к CPU & RAM. Cоответсвенно пользоваться ею когда она тривиально заменяется аналитикой/pattern matching это не самая лучшая идея.

Если продолжить разговор про перфоманс далее, то даже однослойная аналитика уступает в производительности match_recognize а у тебя два WINDOW SORT.

Видимо я неправильно понял задачу, я исходил из посыла что все кроме трансформации исходного запроса и аналитики запрещено.

Если подходить с точки зрения производительности, то все вышеперечисленное проигрывает решению на PL/SQL, в котором даже unpivot не нужен.
15 ноя 20, 11:40    [22232286]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Elic
Member

Откуда:
Сообщений: 29991
graycode
Если подходить с точки зрения производительности,
Не нужно. Пятничные задачи они, скорее в "синтаксисе", в потенциях.
Монохромность изначальной постановки понизила градус полезности.

Как автор признал, задача-баян. Необходимость решать её не сопровождаемыми способами немотивирована.
Если в задаче подразумевались -лярды данных, то об этом не было заявлено.

В свете всего этого лучшее решение - сопровождаемое. Т.е. уровень вхождения в который меньше/проще.
15 ноя 20, 12:02    [22232293]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
НеофитSQL
Я пропустил упражнение-разминку, ответы еще принимаются?
Конечно, принимаются.
Только полезно читать другие ответы перед публикацией своего.
Возможно придёт понимание что в коррелированном скаляре нет смысла абсолютно никакого.
НеофитSQL
Вы это назвали "beginning of group". Есть ли оконное выражение, которое позволяет обрабатывать повторяющуеся группы, как partition by позволяет обрабатывать уникальные группы?
На форуме это вроде называют start of group.
Ты пробовал запустить 22232251?
15 ноя 20, 13:35    [22232326]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
graycode
Видимо я неправильно понял задачу, я исходил из посыла что все кроме трансформации исходного запроса и аналитики запрещено.
Странный посыл. Было замечено только что
1) модель не самое подходящее средство
2) решается без подзапросов и соединений
Казалось бы причем здесь вообще трансформации.
Даже при наличии подзапросов они могут быть а могут и не быть.
graycode
Если подходить с точки зрения производительности, то все вышеперечисленное проигрывает решению на PL/SQL, в котором даже unpivot не нужен.
И ты сможешь его продемонстрировать?
Я даже потружусь нагенерить данных чтоб показать несостоятельность этого заявления.
15 ноя 20, 13:43    [22232329]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Elic
Как автор признал, задача-баян.
А что относительно расширенной постановки? Сможешь дать конкретную ссылку на решение?
Elic
Необходимость решать её не сопровождаемыми способами немотивирована.
Если в задаче подразумевались -лярды данных, то об этом не было заявлено.

В свете всего этого лучшее решение - сопровождаемое. Т.е. уровень вхождения в который меньше/проще.
Если тебе по стариковски, понять многослойную аналитику проще чем pattern matching это не значит что стоит переносить сие восприятие на остальных.
На pattern matching, впрочем, свет тоже клином не сошелся.
15 ноя 20, 13:51    [22232336]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Elic
Member

Откуда:
Сообщений: 29991
Кобанчег
Если тебе по стариковски, понять многослойную аналитику проще чем pattern matching это не значит что стоит переносить сие восприятие на остальных.
Выводы из-за отсутствия информации - всегда ложные.
+
https://www.amazon.com/Practical-Oracle-SQL-Mastering-Database/dp/1484256166

Кобанчег
На pattern matching, впрочем, свет тоже клином не сошелся.
Если честно, то я не совсем понял в чём вызов.
Сопровождабельно решается джойном. Огласи систему ценностей.
15 ноя 20, 14:19    [22232351]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Elic
Выводы из-за отсутствия информации - всегда ложные.
Вот не могу не согласиться.
Elic

+
https://www.amazon.com/Practical-Oracle-SQL-Mastering-Database/dp/1484256166
Ты не поверишь, но я даже бегло читал читал эту книгу. А что предлагается из нее почерпнуть?
Elic
Огласи систему ценностей.
Перфоманс плюс сопровождаемость, пожалуй.
15 ноя 20, 14:38    [22232354]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Elic
Если честно, то я не совсем понял в чём вызов.
Вызова нет, тема была создана чтоб другие поразмялись... и вдруг какая новая идея всплывёт.
Для меня вызов был решить однопроходно в SQL, но еще до создания темы я пришел к тому что это невозможно.
15 ноя 20, 14:46    [22232357]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Собственно мой вариант таков.
select *
  from
(
select x1,
       nvl(decode(src_active, 1, src_c), decode(tgt_active, 1, tgt_c)) result
  from (select x1,
               sum(decode(flag, 'src', sign)) over(order by x1, type) src_active,
               sum(decode(flag, 'tgt', sign)) over(order by x1, type) tgt_active,
               last_value(decode(flag, 'src', c) ignore nulls) over(order by x1, type) src_c,
               last_value(decode(flag, 'tgt', c) ignore nulls) over(order by x1, type) tgt_c
          from (select c,
                       flag,
                       type,
                       x + decode(type, 'X2', 1, 0) x1,
                       decode(type, 'X1', 1, 'X2', -1) sign
                  from t unpivot(x for type in(x1, x2)))) t
)
match_recognize
(
  order by x1
  measures
    first(x.x1) x1,
    next(x.x1) - 1 x2,
    x.result result
  pattern (x+)
  define
    x as first(nvl(result, '~')) = nvl(result, '~') and next(x1) is not null
)
MATCH RECOGNIZE SORT DETERMINISTIC FINITE AUTOMATON + WINDOW SORT + UNPIVOT

При попытке решить однопроходно с match recognize упираешься в то, что "активный" цвет для текущей группы определяется по всему набору а match recognize не позволяет заглядывать в предыдущие группы.
15 ноя 20, 15:28    [22232370]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Под однопрохоность в контексте задачи понимается
одно сканирование таблицы (это неизбежно)
+
одна операция SORT сверху (это тоже неизбежно ибо порядок все определяет).

В моем решении как видно две сортировки.

В решении graycode WINDOW SORT * 5 + WINDOW BUFFER + HASH GROUP BY + 2 сканирования таблицы
15 ноя 20, 15:34    [22232374]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Elic
Member

Откуда:
Сообщений: 29991
Кобанчег
что предлагается из нее почерпнуть?
Ким в доходчивой форме объясняет"шаблонные" фичи в том числе и "старпёрам"
+
technical reviewer :)


Кобанчег
Вызова нет, тема была создана чтоб другие поразмялись... и вдруг какая новая идея всплывёт.
Для меня вызов был решить однопроходно в SQL,
Однопроходность с точки зрения пятничности - это меньше букв. А это, как правило, в ущерб сопровождаемости и производительности.
Подтверждаешь ухудшение пятничности?
+
Я, как старпёр, дотошен :\
15 ноя 20, 15:35    [22232375]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Elic,

Про однопроходность написано сообщением выше, критерии тоже озвучены. Мы не code golf тут занимаемся. ;)
15 ноя 20, 16:04    [22232386]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Жаль, критерий трудно определить объективно.

У меня получилось так. Обилие вложенных селектов и оконных функций кажется неэффективным, но зато нет подчиненных селектов, которые считаются злом.

Теперь пойду смотреть как другие решили.

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

p as (
select * from (
  select x, flag, decode(z,'X1',c,'-') c, z
    from (select x1, x2+1 x2, c, flag from t) tt
 unpivot (x for z in (x1,x2))) 
 pivot (max(c) for flag in ('src' s,'tgt' t))
),
q as (
select x x1, lead(x) over (order by x) -1 x2, c from (
  select x, c, lag(c) over (order by x) cp from (
    select x, decode(s,'-',t,s) c from (
      select x,
             last_value(s ignore nulls) over (order by x) s,
             last_value(t ignore nulls) over (order by x) t
        from p
      )
    )
  )
 where c != nvl(cp,' ')
)
select x1,x2,c from q
 where x1 <= x2  
15 ноя 20, 22:12    [22232512]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Заодно хочу сказать большое спасибо участникам форума за вклад в развитие новичков, включая меня.
Я еще месяц назад такой код со словарем не смог бы прочитать.
15 ноя 20, 22:13    [22232514]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Кобанчег

graycode
Если подходить с точки зрения производительности, то все вышеперечисленное проигрывает решению на PL/SQL, в котором даже unpivot не нужен.
И ты сможешь его продемонстрировать?
Я даже потружусь нагенерить данных чтоб показать несостоятельность этого заявления.


Я такого же мнения, что и graycode. Мне было бы интересно устроить гонки опубликованных подходов против компилированного Pl/SQL. Там все решится в один цикл без аналитических функций, повторных сортировок или временных таблиц в памяти.

PL/SQL процедуру я напишу, если будут данные.
16 ноя 20, 02:41    [22232567]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
Кобанчег
В общем эта была разминка, теперь предлагается задачка посложнее.

Необходимо наложить интервалы из источника на приемник с приоритетом из источника (если есть пересечение).


я так понимаю доминантный ето src, отределяется в строке, а не цветом

цветов много, поетому пересечений может быть больше двух

такое
union all select 7, 20, 'yellow', 'src' from dual
union all select 10, 30, 'red', 'src' from dual
union all select 8, 35, 'black', 'tgt' from dual
union all select 33, 40, 'yellow', 'tgt' from dual
возможно ?

ps
чтоб исключить соблазн генерации connect by, диапазаны ето даты или дробные

.....
stax
16 ноя 20, 10:40    [22232668]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Кобанчег
И ты сможешь его продемонстрировать?
Я даже потружусь нагенерить данных чтоб показать несостоятельность этого заявления.


Вроде нигде с условиями не накосячил))
+
create type res_rec_t as object (x1 number, x2 number, res varchar2(50));
/
create type res_tab_t as table of res_rec_t;
/
create type src_rec_t as object (x1 number, x2 number, c varchar2(50), flag varchar2(50));
/

create or replace function f_superimpose(p_refcur sys_refcursor) return res_tab_t pipelined is
    l_res        res_rec_t;
    l_src        src_rec_t;
    l_curr_flag  varchar2(50);
begin
    fetch p_refcur into l_src;
    if p_refcur%NOTFOUND then 
        return;
    end if;
    
    l_res := res_rec_t(l_src.x1, l_src.x2, l_src.c);
    l_curr_flag := l_src.flag;

    loop
        fetch p_refcur into l_src;
        exit when p_refcur%NOTFOUND;
        
        -- разрыв
        if l_src.x1 - l_res.x2 > 1 then
            pipe row (l_res);
            l_res.x1 := l_res.x2 + 1;
            l_res.x2 := l_src.x1 - 1;
            l_res.res := '';
            pipe row (l_res);
            l_res.x1  := l_src.x1;
            l_res.x2  := l_src.x2;
            l_res.res := l_src.c;
            l_curr_flag := l_src.flag;
            continue;
        end if;
        
        -- касание
        if l_src.x1 - l_res.x2 = 1 then
            if l_src.c = l_res.res then
                l_res.x2  := l_src.x2;
                l_curr_flag := l_src.flag;
            else
                pipe row (l_res);
                l_res.x1  := l_src.x1;
                l_res.x2  := l_src.x2;
                l_res.res := l_src.c;
                l_curr_flag := l_src.flag;
            end if;
            continue;
        end if;

        -- пересечение
        if l_src.x1 - l_res.x2 < 1 then
            if l_curr_flag = 'src' then
                if l_src.x2 > l_res.x2 then
                    if l_src.c = l_res.res then
                        l_res.x2  := l_src.x2;
                        l_curr_flag := l_src.flag;
                    else
                        pipe row (l_res);
                        l_res.x1  := l_res.x2 + 1;
                        l_res.x2  := l_src.x2;
                        l_res.res := l_src.c;
                        l_curr_flag := l_src.flag;
                    end if;
                end if;
            elsif l_curr_flag = 'tgt' then
                if l_src.x2 >= l_res.x2 then
                    if l_src.c = l_res.res then
                        l_res.x2  := l_src.x2;
                        l_curr_flag := l_src.flag;
                    else
                        if l_src.x1 > l_res.x1 then
                            l_res.x2 := l_src.x1 - 1;
                            pipe row (l_res);
                        end if;
                        l_res.x1  := l_src.x1;
                        l_res.x2  := l_src.x2;
                        l_res.res := l_src.c;
                        l_curr_flag := l_src.flag;
                    end if;
                else
                    if l_src.c != l_res.res then
                        if l_src.x1 > l_res.x1 then
                            pipe row (res_rec_t(l_res.x1, l_src.x1 - 1, l_res.res));
                        end if;
                        pipe row (res_rec_t(l_src.x1, l_src.x2, l_src.c));
                        l_res.x1 := l_src.x2 + 1;
                    end if;
                end if;
            end if;
        end if;
    end loop;

    pipe row (l_res);
    close p_refcur;
end;
/

select * from table(f_superimpose(cursor(
with t (x1, x2, c, flag) as
(
select 1, 4, 'red', 'src' from dual
union all select 7, 10, 'yellow', 'src' from dual
union all select 13, 16, 'red', 'src' from dual
union all select 3, 7, 'black', 'tgt' from dual
union all select 9, 11, 'black', 'tgt' from dual
union all select 13, 14, 'black', 'tgt' from dual
union all select 16, 19, 'blue', 'tgt' from dual
union all select 18, 22, 'green', 'src' from dual
union all select 22, 25, 'black', 'tgt' from dual
union all select 26, 28, 'red', 'src' from dual
union all select 29, 30, 'red', 'tgt' from dual
union all select 32, 33, 'black', 'tgt' from dual
)
select src_rec_t(x1, x2, c, flag) from t order by x1, flag
)));
16 ноя 20, 16:00    [22233043]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
НеофитSQL
Интересно, какого размера нужен дата сет, чтобы померять сравнительную производительность разных подходов?

По хорошему нужна реальная асимптота, поэтому разного размера и самый главный момент, это то что в сложных системах, в которых параллельно работает много автоматических процессов, чистый эксперимент на производительность провести невозможно.
16 ноя 20, 16:14    [22233057]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
graycode
НеофитSQL
Интересно, какого размера нужен дата сет, чтобы померять сравнительную производительность разных подходов?

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


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

П.С. Удивился длине процедуры, я почему-то думал что решение циклом будет намного короче.
16 ноя 20, 19:09    [22233256]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
НеофитSQL
"Невозможно сравнить скорость" это не не ответ для того, кто сказал что сделает быстрее :)
Если разница в разы в десятке замеров в разных ситуациях. я думаю понятно какое из решений быстрее.

Я к тому, что полученные циферки времени выполнения нужно рассматривать критически.

НеофитSQL
П.С. Удивился длине процедуры, я почему-то думал что решение циклом будет намного короче.

Перебрал варианты в лоб, можешь поискать закономерности и свернуть алгоритм в более короткий вид, главное чтобы в нем разобраться можно было))
16 ноя 20, 19:46    [22233304]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
НеофитSQL
Обилие вложенных селектов и оконных функций кажется неэффективным
На самом деле это вариант очень приличный!
Группировка пивотом позволила обойтись одной и той же сортировкой в аналитике на всех уровнях (order by x),
в результате чего у тебя только один WINDOW SORT и два WINDOW BUFFER.
Мелкий баг - decode(s,'-',t,s) может быть null если диапазоны начинаются с target.
16 ноя 20, 19:58    [22233311]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Stax
цветов много, поетому пересечений может быть больше двух
Диапазоны source не пересекаются и не соприкасаются. То же самое для target.
16 ноя 20, 19:59    [22233313]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
graycode
Вроде нигде с условиями не накосячил
Ну респект за усердие.

create table t(x1 int, x2 int, c varchar2(10), flag varchar2(3));

exec dbms_random.seed(111);

declare
  strt   constant int := 0;
  offset constant int := 100;
  len    constant int := 100;
  colors constant int := 9;
  qty    constant int := 1e6;
  x1 int;
  x2 int;
  c  varchar2(4000);
begin
  for r in (select 'src' flag from dual union all select 'tgt' from dual) loop
    x2 := strt;
    for i in 1 .. qty loop
      x1 := 1 + x2 + trunc(dbms_random.value(1, offset + 1));
      x2 := x1 + trunc(dbms_random.value(1, len + 1));
      c  := 'COL' || trunc(dbms_random.value(1, colors + 1));
      insert into t values (x1, x2, c, r.flag);
    end loop;
  end loop;
end;
/

commit;


+ ctest.sql
set timing off
column hash format 999999999999999999999999999999

alter session set workarea_size_policy = manual;
alter session set sort_area_size = 2147483647;

set timing on

----------------------------------------------------------------------------------------------------

prompt ==========> graycode

with t1 (x, c_src, c_tgt, gr_src, gr_tgt) as
(
select x1 as x
     , decode(flag, 'src', c, ''), decode(flag, 'tgt', c, '')
     , decode(flag, 'src', 1, 0), decode(flag, 'tgt', 1, 0)
from t
union all
select x2 + 1 as x
     , '', ''
     , decode(flag, 'src', 1, 0), decode(flag, 'tgt', 1, 0)
  from t
)
, t2 (x, c_src, c_tgt, gr_src, gr_tgt) as
(
select x, c_src, c_tgt
     , sum(gr_src) over (order by x range unbounded preceding)
     , sum(gr_tgt) over (order by x range unbounded preceding)
  from t1
)
, t3 (x, c) as
(
select x
     , coalesce(min(c_src) keep (dense_rank first order by x) over (partition by gr_src),
                min(c_tgt) keep (dense_rank first order by x) over (partition by gr_tgt))
  from t2
)
, t4 (x, c) as
(
select min(x), min(c) from (
    select x, c, sum(sog) over (order by x) as gr from (
        select x, c
             , case nvl(c, 'none') when nvl(lag(c) over (order by x), 'none') then 0 else 1 end as sog
          from t3))
group by gr
)
, t5 (x1, x2, c) as
(
select x
     , lead(x) over (order by x) - 1
     , c
  from t4
)
select sum(x1*x2) hash from t5;

----------------------------------------------------------------------------------------------------

prompt ==========> kaban analyt

with tt as
(
select x1,
       nvl(decode(src_active, 1, src_c), decode(tgt_active, 1, tgt_c)) result,
       lag(nvl(decode(src_active, 1, src_c), decode(tgt_active, 1, tgt_c))) over(order by x1) prev_result
  from (select x1,
               sum(decode(flag, 'src', sign)) over(order by x1, type) src_active,
               sum(decode(flag, 'tgt', sign)) over(order by x1, type) tgt_active,
               last_value(decode(flag, 'src', c) ignore nulls) over(order by x1, type) src_c,
               last_value(decode(flag, 'tgt', c) ignore nulls) over(order by x1, type) tgt_c
          from (select c,
                       flag,
                       type,
                       x + decode(type, 'X2', 1, 0) x1,
                       decode(type, 'X1', 1, 'X2', -1) sign
                  from t unpivot(x for type in(x1, x2)))) t
)
select sum(x1*x2) hash
  from (select min(x1) x1,
               lead(min(x1)) over(order by grp) - 1 x2,
               min(result) result
          from (select tt.*, sum(decode(result, prev_result, 0, 1)) over(order by x1) grp from tt)
         group by grp)
 where x2 is not null;

----------------------------------------------------------------------------------------------------

prompt ==========> kaban pattern matching

select sum(x1*x2) hash
from
(
select t.*,
       nvl(decode(src_active, 1, src_c), decode(tgt_active, 1, tgt_c)) result
  from (select x1,
               sum(decode(flag, 'src', sign)) over(order by x1, type) src_active,
               sum(decode(flag, 'tgt', sign)) over(order by x1, type) tgt_active,
               last_value(decode(flag, 'src', c) ignore nulls) over(order by x1, type) src_c,
               last_value(decode(flag, 'tgt', c) ignore nulls) over(order by x1, type) tgt_c
          from (select c,
                       flag,
                       type,
                       x + decode(type, 'X2', 1, 0) x1,
                       decode(type, 'X1', 1, 'X2', -1) sign
                  from t unpivot(x for type in(x1, x2)))) t
)
match_recognize
(
  order by x1
  measures
    first(x.x1) x1,
    next(x.x1) - 1 x2,
    x.result result
  pattern (x+)
  define
    x as first(nvl(result, '~')) = nvl(result, '~') and next(x1) is not null
);

----------------------------------------------------------------------------------------------------

prompt ==========> neofit

with p as (
select * from (
  select x, flag, decode(z,'X1',c,'-') c, z
    from (select x1, x2+1 x2, c, flag from t) tt
 unpivot (x for z in (x1,x2))) 
 pivot (max(c) for flag in ('src' s,'tgt' t))
),
q as (
select x x1, lead(x) over (order by x) -1 x2, c from (
  select x, c, lag(c) over (order by x) cp from (
    select x, decode(nvl(s,'-'),'-',t,s) c from (
      select x,
             last_value(s ignore nulls) over (order by x) s,
             last_value(t ignore nulls) over (order by x) t
        from p
      )
    )
  )
 where c != nvl(cp,' ')
)
select sum(x1*x2) hash from q
 where x1 <= x2;

----------------------------------------------------------------------------------------------------

prompt ==========> graycode plsql

select sum(x1*x2) hash
  from table(f_superimpose(cursor (select src_rec_t(x1, x2, c, flag)
                              from t
                             order by x1, flag)));


SQL>@ctest.sql

Session altered.


Session altered.

==========> graycode

                           HASH
-------------------------------
         9910778652543263460375

Elapsed: 00:00:21.78
==========> kaban analyt

                           HASH
-------------------------------
         9910778652543263460375

Elapsed: 00:00:17.14
==========> kaban pattern matching

                           HASH
-------------------------------
         9910778652543263460375

Elapsed: 00:00:12.04
==========> neofit

                           HASH
-------------------------------
         9910778652543263460375

Elapsed: 00:00:12.48
==========> graycode plsql

                           HASH
-------------------------------
         9910778652543263460375

Elapsed: 00:00:17.53

То есть у неофита та же производительность что у моего финального.
У pl/sql та же производительность что у моего с аналитикой.
Твой с аналитикой самый медленный - ну там слишком дофига сортировок.
16 ноя 20, 20:22    [22233322]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Там еще в начале теста можно было вставить
SQL> select count(*) cnt from t;

       CNT
----------
   2000000

Elapsed: 00:00:00.01
Чтоб показать что на ввод-вывод ресурсы не тратятся.
16 ноя 20, 20:25    [22233325]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Кобанчег,

Как раз то о чем я говорил, подобные результаты нужно оценивать критически, эксперимент поставлен весьма криво, собственно и доверять этим результатам не стоит.

PS: pl/sql вариант конечно нужно переписать без объектной обертки, не знаю сколько она отъедает.
16 ноя 20, 21:15    [22233341]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
o! o!

я тоже хочу PL/SQL сделать!

Спасибо за тесты, очень образовательно.
16 ноя 20, 21:41    [22233354]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
graycode,

Поставь ровнее, я ж только за.
16 ноя 20, 21:43    [22233355]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Кобанчег,

Ты сам взялся за тесты производительности))

Проводить тесты нужно независимо, т.е. не друг за другом, состояние системы перед каждым тестом нужно приводить в исходное состояние и очень желательно нивелировать влияние физических чтений исходной таблицы с диска, кроме того то что ты продемонстрировал вообще одного порядка, т.е. реально оно все выполнилось за одинаковое время, нужно было довести время выполнения хотя бы до трех минут (как известно чем больше N тем сильнее расходятся асимптоты).

И ой, прошу прощения, не все вычистил, там кое что совсем лишнее, flag в сортировке не нужен для работы функции))
select sum(x1*x2) hash
  from table(f_superimpose(cursor (select src_rec_t(x1, x2, c, flag)
                              from t
                             order by x1, flag)));
16 ноя 20, 21:51    [22233359]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
graycode,

В тесте важно избежать физических чтений таблицы и ухода в темп на сортировках.
Можно было еще чуть минимизировать расходы на получения хеша.
Всё остальное - лирика.

В реальных данных все намного сложнее и это была лишь примитивная симуляция.

Не та эта задача где PL/SQL блещет как ты ни крути. :)
16 ноя 20, 22:01    [22233366]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Кобанчег,

Еще раз, ты своим экспериментом продемонстрировал ... ничего, т.е. получил одинаковое время (одного порядка) и даже мой самый медленный и корявый вариант по твоему эксперименту не отличается от остальных))

Хочешь реально оценить, поставь эксперимент грамотно.
16 ноя 20, 22:05    [22233369]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
graycode,

А кто-то говорил про отличия на порядки?
Если хочешь увидеть на порядки - потести варианты с коррелированными подзапросами.

Ты волен делать какие угодно выводы на основании таймингов или показать свой тест, но подобная демагогия это слив.

Можешь еще увеличивать число до 3e6, 5e6 и так далее пока не начнет вылезать в темп. И строить асимптоты.
16 ноя 20, 22:28    [22233375]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
graycode,

Пример когда PL/SQL рулит - 11567017.
Но там альтернатива была только модель.
С графиками. Думаю тебе должно понравиться. :)
16 ноя 20, 22:40    [22233378]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Кобанчег,

Слив, это методика эксперимента))

Вот с графиками красиво и ... PL/SQL рулит ...

Переписал в виде пакета, без объектной обертки должно быть быстрее.
+
create or replace package dropme_pkg as
    type res_rec_t is record (x1 t.x1%type, x2 t.x2%type, res t.c%type);
    type res_tab_t is table of res_rec_t;
    type refcur_t is ref cursor return t%rowtype;
    function f_superimpose return res_tab_t pipelined;
end dropme_pkg;
/

create or replace package body dropme_pkg as
    function f_superimpose return res_tab_t pipelined is
        c_refcur_t   refcur_t;
        l_res        res_rec_t;
        l_res_tmp    res_rec_t;
        l_src        t%rowtype;
        l_curr_flag  t.flag%type;
    begin
        open c_refcur_t for select * from t order by x1;
    
        fetch c_refcur_t into l_src;
        if c_refcur_t%NOTFOUND then 
            return;
        end if;
        
        l_res := res_rec_t(l_src.x1, l_src.x2, l_src.c);
        l_curr_flag := l_src.flag;

        loop
            fetch c_refcur_t into l_src;
            exit when c_refcur_t%NOTFOUND;
            
            -- разрыв
            if l_src.x1 - l_res.x2 > 1 then
                pipe row (l_res);
                l_res.x1 := l_res.x2 + 1;
                l_res.x2 := l_src.x1 - 1;
                l_res.res := '';
                pipe row (l_res);
                l_res.x1  := l_src.x1;
                l_res.x2  := l_src.x2;
                l_res.res := l_src.c;
                l_curr_flag := l_src.flag;
                continue;
            end if;
            
            -- касание
            if l_src.x1 - l_res.x2 = 1 then
                if l_src.c = l_res.res then
                    l_res.x2  := l_src.x2;
                    l_curr_flag := l_src.flag;
                else
                    pipe row (l_res);
                    l_res.x1  := l_src.x1;
                    l_res.x2  := l_src.x2;
                    l_res.res := l_src.c;
                    l_curr_flag := l_src.flag;
                end if;
                continue;
            end if;

            -- пересечение
            if l_src.x1 - l_res.x2 < 1 then
                if l_curr_flag = 'src' then
                    if l_src.x2 > l_res.x2 then
                        if l_src.c = l_res.res then
                            l_res.x2  := l_src.x2;
                            l_curr_flag := l_src.flag;
                        else
                            pipe row (l_res);
                            l_res.x1  := l_res.x2 + 1;
                            l_res.x2  := l_src.x2;
                            l_res.res := l_src.c;
                            l_curr_flag := l_src.flag;
                        end if;
                    end if;
                elsif l_curr_flag = 'tgt' then
                    if l_src.x2 >= l_res.x2 then
                        if l_src.c = l_res.res then
                            l_res.x2  := l_src.x2;
                            l_curr_flag := l_src.flag;
                        else
                            if l_src.x1 > l_res.x1 then
                                l_res.x2 := l_src.x1 - 1;
                                pipe row (l_res);
                            end if;
                            l_res.x1  := l_src.x1;
                            l_res.x2  := l_src.x2;
                            l_res.res := l_src.c;
                            l_curr_flag := l_src.flag;
                        end if;
                    else
                        if l_src.c != l_res.res then
                            if l_src.x1 > l_res.x1 then
                                l_res_tmp.x1  := l_res.x1;
                                l_res_tmp.x2  := l_src.x1 - 1;
                                l_res_tmp.res := l_res.res;
                                pipe row (l_res_tmp);
                            end if;
                            l_res_tmp.x1  := l_src.x1;
                            l_res_tmp.x2  := l_src.x2;
                            l_res_tmp.res := l_src.c;
                            pipe row (l_res_tmp);
                            l_res.x1 := l_src.x2 + 1;
                        end if;
                    end if;
                end if;
            end if;
        end loop;

        pipe row (l_res);
        close c_refcur_t;
    end;
end dropme_pkg;
/

select * from table(dropme_pkg.f_superimpose)
16 ноя 20, 23:14    [22233388]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
graycode
Переписал в виде пакета
В этом не было особой необходимости, Оракл всё равно под капотом для таких функций создает типы SYS_PLSQL_%
Пакет бы пригодился когда понадобилось бы параллелить функцию и объявлять strong ref cursor. ;)
graycode
без объектной обертки должно быть быстрее
А это улучшение, да.
Теперь на уровне ведущих эскуэльных подходов.
Мир, равенство, братсво.
16 ноя 20, 23:35    [22233398]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Кобанчег,

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

+
declare
    l_timestamp timestamp;
    l_i         interval day to second;
    res         number;
begin
    l_timestamp := localtimestamp;

    select sum(x1*x2) into res
    from
    (
    select t.*,
           nvl(decode(src_active, 1, src_c), decode(tgt_active, 1, tgt_c)) result
      from (select x1,
                   sum(decode(flag, 'src', sign)) over(order by x1, type) src_active,
                   sum(decode(flag, 'tgt', sign)) over(order by x1, type) tgt_active,
                   last_value(decode(flag, 'src', c) ignore nulls) over(order by x1, type) src_c,
                   last_value(decode(flag, 'tgt', c) ignore nulls) over(order by x1, type) tgt_c
              from (select c,
                           flag,
                           type,
                           x + decode(type, 'X2', 1, 0) x1,
                           decode(type, 'X1', 1, 'X2', -1) sign
                      from t unpivot(x for type in(x1, x2)))) t
    )
    match_recognize
    (
      order by x1
      measures
        first(x.x1) x1,
        next(x.x1) - 1 x2,
        x.result result
      pattern (x+)
      define
        x as first(nvl(result, '~')) = nvl(result, '~') and next(x1) is not null
    );

    l_i := localtimestamp - l_timestamp;
    dbms_output.put_line('kaban pattern matching - ' || res || ' - ' ||
                         to_char(extract(second from l_i) * 1000 +
                                 extract(minute from l_i) * 60000));

    ----------------------------------------------------------------------------

    l_timestamp := localtimestamp;

    with tt as
    (
    select x1,
           nvl(decode(src_active, 1, src_c), decode(tgt_active, 1, tgt_c)) result,
           lag(nvl(decode(src_active, 1, src_c), decode(tgt_active, 1, tgt_c))) over(order by x1) prev_result
      from (select x1,
                   sum(decode(flag, 'src', sign)) over(order by x1, type) src_active,
                   sum(decode(flag, 'tgt', sign)) over(order by x1, type) tgt_active,
                   last_value(decode(flag, 'src', c) ignore nulls) over(order by x1, type) src_c,
                   last_value(decode(flag, 'tgt', c) ignore nulls) over(order by x1, type) tgt_c
              from (select c,
                           flag,
                           type,
                           x + decode(type, 'X2', 1, 0) x1,
                           decode(type, 'X1', 1, 'X2', -1) sign
                      from t unpivot(x for type in(x1, x2)))) t
    )
    select sum(x1*x2) into res
      from (select min(x1) x1,
                   lead(min(x1)) over(order by grp) - 1 x2,
                   min(result) result
              from (select tt.*, sum(decode(result, prev_result, 0, 1)) over(order by x1) grp from tt)
             group by grp)
     where x2 is not null;

    l_i := localtimestamp - l_timestamp;
    dbms_output.put_line('kaban analyt - ' || res || ' - ' ||
                         to_char(extract(second from l_i) * 1000 +
                                 extract(minute from l_i) * 60000));
  

    ----------------------------------------------------------------------------

    l_timestamp := localtimestamp;

    with p as (
    select * from (
      select x, flag, decode(z,'X1',c,'-') c, z
        from (select x1, x2+1 x2, c, flag from t) tt
     unpivot (x for z in (x1,x2))) 
     pivot (max(c) for flag in ('src' s,'tgt' t))
    ),
    q as (
    select x x1, lead(x) over (order by x) -1 x2, c from (
      select x, c, lag(c) over (order by x) cp from (
        select x, decode(nvl(s,'-'),'-',t,s) c from (
          select x,
                 last_value(s ignore nulls) over (order by x) s,
                 last_value(t ignore nulls) over (order by x) t
            from p
          )
        )
      )
     where c != nvl(cp,' ')
    )
    select sum(x1*x2) into res from q
     where x1 <= x2;

    l_i := localtimestamp - l_timestamp;
    dbms_output.put_line('neofit - ' || res || ' - ' ||
                         to_char(extract(second from l_i) * 1000 +
                                 extract(minute from l_i) * 60000));

    ----------------------------------------------------------------------------

    l_timestamp := localtimestamp;

    select sum(x1*x2) into res from table(dropme_pkg.f_superimpose);

    l_i := localtimestamp - l_timestamp;
    dbms_output.put_line('graycode plsql - ' || res || ' - ' ||
                         to_char(extract(second from l_i) * 1000 +
                                 extract(minute from l_i) * 60000));

end;
16 ноя 20, 23:47    [22233403]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Кобанчег,

У тебя в том топике еще и bulk collect ...

НеофитSQL
я тоже хочу PL/SQL сделать!

Сделай не пайплайнед, а как у Кобанчег, в топике на который он ссылку дал.
17 ноя 20, 00:08    [22233409]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
graycode
Кобанчег,

У тебя в том топике еще и bulk collect ...

НеофитSQL
я тоже хочу PL/SQL сделать!

Сделай не пайплайнед, а как у Кобанчег, в топике на который он ссылку дал.


Я уже написал пайплайном, на вашем примере.

create or replace function f_overlay(cur sys_refcursor) return res_tab_t pipelined is
  l_src     src_rec_t;
  l_back    src_rec_t := src_rec_t(0,0,null,null);
  l_last    res_rec_t;
  r         res_rec_t;
  function RangeUntil( x in number, c in varchar2 ) return res_rec_t is
    ret res_rec_t;
  begin
    if x <= l_last.x2 then return null; end if;
    
    if nvl(c,'clear') = nvl(l_last.res,'clear') then
      l_last.x2 := x;
      return null;
    end if;

    ret := res_rec_t(l_last.x1,l_last.x2-1,l_last.res);
    l_last.x1 := l_last.x2;
    l_last.x2 := x;
    l_last.res  := c;
    return ret;
  end;
begin
  loop
    fetch cur into l_src;
    exit when cur%NOTFOUND;
    l_src.x2 := l_src.x2+1;
    
    if l_last is null then 
      l_last := res_rec_t(l_src.x1, l_src.x1, l_src.c);
    end if;

    if l_src.flag = 'src' then
      r := RangeUntil( least(l_back.x2, l_src.x1), l_back.c );   if r is not null then pipe row (r); end if;
      r := RangeUntil( l_src.x1, null );                         if r is not null then pipe row (r); end if;
      r := RangeUntil( l_src.x2, l_src.c );                      if r is not null then pipe row (r); end if;
    else
      r := RangeUntil( l_back.x2, l_back.c );                    if r is not null then pipe row (r); end if;
      r := RangeUntil( l_src.x1, null );                         if r is not null then pipe row (r); end if;
      l_back := l_src;
    end if;
  end loop;
  close cur;

  r := RangeUntil( l_src.x2, l_src.c );  if r is not null then pipe row (r); end if;
  r := RangeUntil( l_src.x2+1, null );   if r is not null then pipe row (r); end if;
end;

Долго ломал голову как сделать условный pipe row (чтобы пустые строчки не плевало), но так и не смог.
Поэтому в правой части много повторяющегося кода.
17 ноя 20, 02:08    [22233450]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Без пайплайна возможно быстрее. Надеюсь Кобанчег или другие бенчмаркнут.

+
create or replace function f_overlay(cur sys_refcursor) return res_tab_t is
  l_src     src_rec_t;
  l_back    src_rec_t := src_rec_t(0,0,null,null);
  l_last    res_rec_t;
  rett      res_tab_t := res_tab_t();

  procedure RangeUntil( x in number, c in varchar2 ) is
  begin
    if x <= l_last.x2 then return; end if;
    
    if nvl(c,'clear') = nvl(l_last.res,'clear') then
      l_last.x2 := x;
      return;
    end if;

    rett.extend;
    rett(rett.last) := res_rec_t(l_last.x1,l_last.x2-1,l_last.res);
    l_last.x1 := l_last.x2;
    l_last.x2 := x;
    l_last.res  := c;
  end;

begin
  loop
    fetch cur into l_src;
    exit when cur%NOTFOUND;
    l_src.x2 := l_src.x2+1;
    
    if l_last is null then 
      l_last := res_rec_t(l_src.x1, l_src.x1, l_src.c);
    end if;

    if l_src.flag = 'src' then
      RangeUntil( least(l_back.x2, l_src.x1), l_back.c );
      RangeUntil( l_src.x1, null );
      RangeUntil( l_src.x2, l_src.c );
    else
      RangeUntil( l_back.x2, l_back.c );
      RangeUntil( l_src.x1, null );
      l_back := l_src;
    end if;
  end loop;
  close cur;

  RangeUntil( l_src.x2, l_src.c );
  RangeUntil( l_src.x2+1, null );
  return rett;
end;
17 ноя 20, 02:25    [22233452]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
НеофитSQL
Без пайплайна возможно быстрее. Надеюсь Кобанчег или другие бенчмаркнут.

С пайплайном мы по одной строчке перегоняем входящий отсортированный набор данных в выходной набор данных по которому потом еще идет суммирование, если весь входной набор отправить в коллекцию bulk collect-ом, обработать эту коллекцию не создавая новую и отдать ее в качестве результата, должно получиться быстрее.

PS: в реальных задачах нужно учитывать что коллекция будет содержать все данные таблицы и находиться она будет в UGA.
17 ноя 20, 12:47    [22233643]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
andrey_anonymous
Member

Откуда: Москва
Сообщений: 18398
graycode
пайплайном мы по одной строчке перегоняем входящий отсортированный набор данных в выходной набор данных

Точно? :)
17 ноя 20, 13:03    [22233657]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
andrey_anonymous
Точно? :)

Мы точно не ползаем по исходному набору и не модифицируем его, мы читаем по строке, формируем новую в PL/SQL и отдаем обратно в SQL, где поверх еще идет суммирование, в SQL решениях одно исполняющее ядро SQL и возможность по максимуму использовать исходный набор данных не перекачивая его через сторонние структуры построчно.
17 ноя 20, 14:17    [22233742]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
graycode
НеофитSQL
Без пайплайна возможно быстрее. Надеюсь Кобанчег или другие бенчмаркнут.

С пайплайном мы по одной строчке перегоняем входящий отсортированный набор данных в выходной набор данных по которому потом еще идет суммирование, если весь входной набор отправить в коллекцию bulk collect-ом, обработать эту коллекцию не создавая новую и отдать ее в качестве результата, должно получиться быстрее.

PS: в реальных задачах нужно учитывать что коллекция будет содержать все данные таблицы и находиться она будет в UGA.


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

по поводу обработки коллекции in-place, там довольно неочевидная (для меня) оценка размера результата.
Вроде бы худший случай это 2N если нужно выводить незакрашенные интервалы, и 2N-1 если их можно пропускать.
(N- число строк в исходной таблице)
17 ноя 20, 14:25    [22233757]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Кобанчег,

Погонял на таблице разного размера и генерации, однозначного победителя из трех вариантов kaban pattern matching, neofit, graycode plsql не выявил, лидером оказывается то один то другой то третий, причем pattern matching всегда очень близко к pl/sql варианту, neofit уходит то в плюс то в минус процентов на двадцать. Честно говоря от pl/sql варианта ожидал лучших результатов.
17 ноя 20, 14:28    [22233764]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
НеофитSQL,

Оценить размер результата сложно, там помимо пропусков может быть увеличение, например идет интервал tgt, а в его середине интервал src, на входе два интервала, на выходе три, если два интервала src в середине tgt, то исходных три интервала, а на выходе 5.
17 ноя 20, 14:33    [22233782]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
andrey_anonymous
Member

Откуда: Москва
Сообщений: 18398
graycode
мы читаем по строке, формируем новую в PL/SQL и отдаем обратно в SQL

Ну и откуда вывод, что выдача происходит по одной строке?
Из statement PIPE ROW?
Ну-ну.
Что до чтения - тут вообще странно Вас читать.
Ничто не мешает ни явному bulk collect, ни неявному (оптимизация курсорного цикла на PLSQL Optimizer Level 2).
17 ноя 20, 14:39    [22233789]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
graycode
Кобанчег,

Погонял на таблице разного размера и генерации, однозначного победителя из трех вариантов kaban pattern matching, neofit, graycode plsql не выявил, лидером оказывается то один то другой то третий, причем pattern matching всегда очень близко к pl/sql варианту, neofit уходит то в плюс то в минус процентов на двадцать. Честно говоря от pl/sql варианта ожидал лучших результатов.


Pl/SQL компилированный, я надеюсь?
17 ноя 20, 14:58    [22233819]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
graycode
НеофитSQL,

Оценить размер результата сложно, там помимо пропусков может быть увеличение, например идет интервал tgt, а в его середине интервал src, на входе два интервала, на выходе три, если два интервала src в середине tgt, то исходных три интервала, а на выходе 5.


Да, я уже решил полным перебором. Ответ 2N (2N-1 если не показывать пробелы) правильный.

Удвоение не так уж плохо. Тогда можно аллокировать массив двойной длины, собрать отсортированные по x1 данные в его вторую половину, оставляя первую пустой и не затирая непрочитанных данных обработать в том же пространстве.
17 ноя 20, 15:03    [22233830]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
НеофитSQL
Pl/SQL компилированный, я надеюсь?

Нет, так что еще есть пространство для оптимизации))
17 ноя 20, 15:38    [22233880]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
andrey_anonymous,

Еще не факт что пакетная обработка даст серьезный прирост производительности в этой задаче, потребление памяти даст точно))

SQL: сумма(вычисления(сортировка(исходные данные)))

PL/SQL: сортировка(исходные данные) -> черный ящик (PL/SQL вычисления) -> Сумма(результирующий набор из черного ящика построчно или пакетом/пакетами)
17 ноя 20, 15:45    [22233891]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
booby
Member

Откуда:
Сообщений: 2257
graycode,

я не очень следил за содержанием...
то, что было показано, в твоем pl/sql коде в частности, подозрительно,
поскольку, на беглый взгляд, плохо учитывает возможность множественного пересеченения каждого из исходных отрезков с порождением множества результатов пересечения из одного исходного отрезка.

что касается pl/sql против нет - ну, с Марса, имхо, так видится:
в случае pl/sql - ~nLog(n) для стартовой сортировки + ~nLog(n) сам алгоритм построения результата.

SQL, может быть, в виде pattern matching к этому подберется, если повезет с алгоритмами в его нутрях.
Join надо будет попотеть заставлять оставаться в рамках роста nLog(n) на больших бъемах.
17 ноя 20, 15:58    [22233903]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
booby

что касается pl/sql против нет - ну, с Марса, имхо, так видится:
в случае pl/sql - ~nLog(n) для стартовой сортировки + ~nLog(n) сам алгоритм построения результата.


Построение результата должно быть линейным, т.к. простой цикл без учета длины данных.
17 ноя 20, 16:07    [22233911]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
booby
то, что было показано, в твоем pl/sql коде в частности, подозрительно,
поскольку, на беглый взгляд, плохо учитывает возможность множественного пересеченения каждого из исходных отрезков с порождением множества результатов пересечения из одного исходного отрезка.

Не очень понял что имеется ввиду, у нас src это приоритетные отрезки, поэтому если на них накладываются отрезки tgt, то отрезки tgt частью попадающей на src просто игнорируются, остается только выступающая за src часть, а друг с другом src пересекаться не могут по условию задачи, да и приоритета по цветам у нас нет, пересечение отрезков src отрезками tgt обрабатывается.

booby
~nLog(n) сам алгоритм построения результата.

В цикле по отсортированной входной выборке только дерево условных операторов, т.е. ~(n), откуда логарифм?
17 ноя 20, 16:14    [22233919]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
booby
Member

Откуда:
Сообщений: 2257
graycode,

вы тут две задачи обсуждаете, формулировку второй я вообще не понял, правда и не вчитывался...

в общем, даже не важно про первую или вторую это задачу:
автор
у нас src это приоритетные отрезки, поэтому если на них накладываются отрезки tgt, то отрезки tgt частью попадающей на src просто игнорируются, остается только выступающая за src часть


здесь умолчанием подразумевается,что а) у src нет пересечений,
б) входной набор "правильно" сортирован и, значит, в) tgt относящийся к "другому" src не приедет преждевременно.

сколько, кстати, кусков от src должно остаться после наложения всех tgt, и почему следующий tgt не может резать внахлест уже разрезанное предыдущим?

Т.е. слишком много ифов зашито в первичную сортировку.
А так по виду - классическая задача на заметание, в любом случае, решаемая за ~nLog(n)

Сообщение было отредактировано: 17 ноя 20, 16:37
17 ноя 20, 16:42    [22233949]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
andrey_anonymous
Member

Откуда: Москва
Сообщений: 18398
booby
А так по виду - классическая задача на заметание, в любом случае, решаемая за ~nLog(n)

На базе SMJ вполне делается за две сортировки плюс линейный перебор.
17 ноя 20, 17:03    [22233968]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
booby
Member

Откуда:
Сообщений: 2257
andrey_anonymous,

что такое SMJ?
17 ноя 20, 17:11    [22233976]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
andrey_anonymous
Member

Откуда: Москва
Сообщений: 18398
booby
andrey_anonymous,
что такое SMJ?

Sort Merge Join :)
17 ноя 20, 17:22    [22233991]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
booby
Member

Откуда:
Сообщений: 2257
andrey_anonymous
booby
andrey_anonymous,
что такое SMJ?

Sort Merge Join :)

понял, это ты к тому, для join тоже можно гарантию nLog(n) обеспечить...
Ок.
17 ноя 20, 17:32    [22234000]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
booby
здесь умолчанием подразумевается,что а) у src нет пересечений,
б) входной набор "правильно" сортирован и, значит, в) tgt относящийся к "другому" src не приедет преждевременно.

Входной набор сортируется ~nLog(n), дальше идет цикл ~(n), пересечений src-src и tgt-tgt быть не может.

tgt относящийся к "другому" src может приехать и это не важно, проверки отрабатывают эту ситуацию, поскольку блоки приезжают в порядке x1, просто корректируется верхняя текущая граница x2 и ее тип, если следующим приезжает блок src, то он просто срезает текущую x2 по свой x1, так что тут все вполне линейно считается.

booby
сколько, кстати, кусков от src должно остаться после наложения всех tgt, и почему следующий tgt не может резать внахлест уже разрезанное предыдущим?

Автор задачи дал немного странные названия, src не режется, он приоритетный, т.е. src режет, но не наоборот, блоки одного типа не могут пересекаться.
17 ноя 20, 17:42    [22234011]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
andrey_anonymous
Member

Откуда: Москва
Сообщений: 18398
booby
понял, это ты к тому, для join тоже можно гарантию nLog(n) обеспечить...
Ок.

Это я к тому, что при наличии предварительно отсортированных наборов сам SMJ линеен и, вообще говоря, подходит под решение задачи.
Наличие пресортированных наборов можно обеспечить индексным доступом и тем самым решить за линейное время.
17 ноя 20, 17:45    [22234016]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
booby
Member

Откуда:
Сообщений: 2257
graycode
... пересечений src-src и tgt-tgt быть не может.

....

с чего бы это?
чтобы задачу упростить?
17 ноя 20, 17:50    [22234022]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
andrey_anonymous
Member

Откуда: Москва
Сообщений: 18398
booby

чтобы задачу упростить?

Задача аннулирования самопересечений достаточно тривиальна и не очень интересна в контексте.
17 ноя 20, 17:52    [22234026]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
andrey_anonymous
На базе SMJ вполне делается за две сортировки плюс линейный перебор.
Казалось бы, зачем джойн когда можно без оного и эффективнее.
Более того, если делать через джойн, то линейным перебором можно обойтись только в PL/SQL, SQL-но придется использовать еще один джойн (или pivot).
Я ж так понимаю речь про такое ядро
select *
  from (select * from t where flag = 'tgt') t
  full join (select * from t where flag = 'src') s
    on s.x1 <= t.x2
   and t.x1 <= s.x2
?
Ну так это уступает тому, что уже было показано.
У меня то есть финальный вариант но я не видел смысла его выкладывать в виду неконкуретноспособности.
17 ноя 20, 18:58    [22234084]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
Кобанчег

У меня то есть финальный вариант


для

select 10, 20, 'blue', 'tgt' from dual union all
select 15, 25, 'blue', 'src' from dual

результат одна строка 10, 25, 'blue' ?

.....
stax
17 ноя 20, 19:11    [22234095]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Stax,

Да.

PS. Если что можно же ответ сверять с имеющимися вариантами.
17 ноя 20, 19:13    [22234096]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Хм, сделал таблицу IOT с pk по всем полям, теперь pl/sql стабильно чуть быстрее, но именно чуть чуть, т.е. все равно все три варианта равноценны в практическом плане и вариант неофита лучше варианта pattern matching.

PS: pl/sql native и Optimizer Level 2
17 ноя 20, 19:14    [22234098]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
andrey_anonymous
Member

Откуда: Москва
Сообщений: 18398
Кобанчег
линейным перебором можно обойтись только в PL/SQL

Ага
17 ноя 20, 22:24    [22234225]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
andrey_anonymous
Кобанчег
линейным перебором можно обойтись только в PL/SQL

Ага


Да ну, я же публиковал линейный перебор в самом начале на SQL.
17 ноя 20, 23:07    [22234246]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
andrey_anonymous
Member

Откуда: Москва
Сообщений: 18398
НеофитSQL
andrey_anonymous
пропущено...
Ага

Да ну, я же публиковал линейный перебор в самом начале на SQL.

Что-то я не видел.
18 ноя 20, 00:33    [22234273]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
andrey_anonymous
Что-то я не видел.
Первым линейный перебор опубликовал господин graycode и без всяких SMJ.

22233043
18 ноя 20, 00:57    [22234286]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Это на PL/SQL.

Я про это: 22232233

Контекст:
,>линейным перебором можно обойтись только в PL/SQL

Сообщение было отредактировано: 18 ноя 20, 02:25
18 ноя 20, 02:25    [22234305]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
xtender
Member

Откуда: Мск
Сообщений: 5704
Кажется, я уже решал обе такие задачки, сходу только вспомнить и найти не смог, но нашёл чуть более сложный вариант усложненной задачки: https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set
18 ноя 20, 03:06    [22234308]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
xtender,


Мне эта видится проще,тут N слоев одиночных заплаток, перебор комбинаций меньше.

Соответственно и решение короче. Но задачка тоже классная, я попробую решить не глядя в ссылку.

А задачи про двухмерные заплатки никто не публиковал?

Например:
Каждая строка задаёт х1,х2,у1,у2 координаты покрашенного прямоугольника. Определить:
- площадь покрашенной поверхности
- максимальный полностью закрашенный прямоугольник
- максимальное число слоев на поверхности
- площадь поверхности содержащая ровно N слоев краски

Для супер одаренных:
- наибольший полностью закрашенный круг (центр и радиус)

Это монохромная версия. Можно добавить цвета..
18 ноя 20, 03:42    [22234310]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
xtender
Кажется, я уже решал обе такие задачки, сходу только вспомнить и найти не смог, но нашёл чуть более сложный вариант усложненной задачки: https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set


with t(lvl,x1,x2) as (
select 1,10,11 from dual union all
select 2,10,12 from dual union all
select 3, 8,13 from dual union all
select 4, 9,14 from dual union all
select 5, 3,15 from dual union all
select 6, 4,16 from dual union all
select 7, 5,17 from dual
)
select * from (
  select lvl, x1, nvl(lag(x1) over (order by lvl),x2) x2 from t union all
  select lvl, lag(x2) over (order by lvl) x1, x2 from t
) where x1 < x2 order by x1
18 ноя 20, 04:03    [22234312]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Почитал решения по ссылке, народ явно легких путей не ищет.

"Simplicate, and add lightness" (c)
18 ноя 20, 04:07    [22234313]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
НеофитSQL

А задачи про двухмерные заплатки никто не публиковал?

Например:
Каждая строка задаёт х1,х2,у1,у2 координаты покрашенного прямоугольника. Определить:
- площадь покрашенной поверхности
- максимальный полностью закрашенный прямоугольник
- максимальное число слоев на поверхности
- площадь поверхности содержащая ровно N слоев краски

Для супер одаренных:
- наибольший полностью закрашенный круг (центр и радиус)

Это монохромная версия. Можно добавить цвета..


-- порядок не задан, краска одинаковая
-- x,y - координаты границ а не номера колонок, 
-- т.е. 5-5 это пустой отрезок, а не один интервал
with t(x1,x2,y1,y2) as (
select 1, 5, 3, 5 from dual union all
select 2, 6, 2, 4 from dual union all
select 1, 7, 3, 6 from dual union all
select 4, 8, 2, 3 from dual union all
select 5, 6, 4, 9 from dual union all
select 5, 9, 2, 6 from dual union all
select 7, 8, 5, 7 from dual
)
select ...


С фотошопом я не дружу, поэтому иллюстрация в ASCII:


1 2 3 4 5 6 7 8
2 $ $ $ $ $ $ $
3 $ $ $ $ $ $ $ $
4 $ $ $ $ $ $ $ $
5 $ $ $ $ $ $ $ $
6 $ $
7 $
8 $

+
xx as (
select level x from dual where level >= (select min(x1) from t) 
connect by level < (select max(x2) from t) 
),
yy as (
select level y from dual where level >= (select min(y1) from t) 
connect by level < (select max(y2) from t) 
)
select null "row", (select listagg(x,'  ') within group (order by x) from xx) "columns"
  from dual union all
select y, (select listagg(decode(
   (select count(*) from t where x>=x1 and x<x2 and y>=y1 and y<y2),0,' ','$')
           ,'  ') within group (order by x) from xx) 
  from yy 
18 ноя 20, 04:56    [22234319]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
andrey_anonymous
Member

Откуда: Москва
Сообщений: 18398
НеофитSQL
А задачи про двухмерные заплатки никто не публиковал?

Приходилось как-то на проекте внедрения внезапно под вечер решать задачку вида "сделать из списка (с историей изменения) префиксов телефонных зон двумерную карту для быстрого определения корректной зоны вызова по параметрам (вызываемый номер, дата соединения)".
Не rocket science, хотя пару-тройку часов из жизни выкинул.
18 ноя 20, 13:10    [22234540]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
НеофитSQL
Почитал решения по ссылке, народ явно легких путей не ищет.

"Simplicate, and add lightness" (c)

А ты подставь данные из ссылки и сравни результат, ты решал какую то другую задачу.
18 ноя 20, 13:18    [22234547]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
НеофитSQL
Жаль, критерий трудно определить объективно.

У меня получилось так.


должно быть две строки?

with t (x1, x2, c, flag) as
(
              select 10, 30, 'blue', 'src' from dual
union all select 20, 30, 'red', 'tgt' from dual
union all select 31, 35, 'red', 'tgt' from dual
)
,p as (
select * from (
  select x, flag, decode(z,'X1',c,'-') c, z
    from (select x1, x2+1 x2, c, flag from t) tt
 unpivot (x for z in (x1,x2))) 
 pivot (max(c) for flag in ('src' s,'tgt' t))
),
q as (
select x x1, lead(x) over (order by x) -1 x2, c from (
  select x, c, lag(c) over (order by x) cp from (
    select x, decode(s,'-',t,s) c from (
      select x,
             last_value(s ignore nulls) over (order by x) s,
             last_value(t ignore nulls) over (order by x) t
        from p
      )
    )
  )
 where c != nvl(cp,' ')
)
select x1,x2,c from q
 where x1 <= x2  
/

SQL> /

        X1         X2 C
---------- ---------- ----
        10         30 blue


.....
stax
18 ноя 20, 15:09    [22234654]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
Кобанчег
Собственно мой вариант таков.
select *
  from
(
select x1,
       nvl(decode(src_active, 1, src_c), decode(tgt_active, 1, tgt_c)) result
  from (select x1,
               sum(decode(flag, 'src', sign)) over(order by x1, type) src_active,
               sum(decode(flag, 'tgt', sign)) over(order by x1, type) tgt_active,
               last_value(decode(flag, 'src', c) ignore nulls) over(order by x1, type) src_c,
               last_value(decode(flag, 'tgt', c) ignore nulls) over(order by x1, type) tgt_c
          from (select c,
                       flag,
                       type,
                       x + decode(type, 'X2', 1, 0) x1,
                       decode(type, 'X1', 1, 'X2', -1) sign
                  from t unpivot(x for type in(x1, x2)))) t
)
match_recognize
(
  order by x1
  measures
    first(x.x1) x1,
    next(x.x1) - 1 x2,
    x.result result
  pattern (x+)
  define
    x as first(nvl(result, '~')) = nvl(result, '~') and next(x1) is not null
)
MATCH RECOGNIZE SORT DETERMINISTIC FINITE AUTOMATON + WINDOW SORT + UNPIVOT

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



with t (x1, x2, c, flag) as
(
              select 20, 30, 'red', 'src' from dual
union all select 20, 30, 'red', 'tgt' from dual
)



X1 X2 RESULT
20 30 red
31 30 -
Download CSV
2 rows selected.

.....
stax
18 ноя 20, 15:30    [22234670]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Stax
должно быть две строки?

Да.
18 ноя 20, 15:31    [22234671]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Stax
.....

Всех замочил)))

PS: для проверки используйте PL/SQL вариант 22233043 ))
18 ноя 20, 15:35    [22234675]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Stax
должно быть две строки?
Да. Ну ты мастер тестирования!
Можешь использовать мой запрос, там верно возвращает.

Я в его решении поправил один баг, получается есть еще (странно что это не всплыло в моём чудо тесте)
Кобанчег
Мелкий баг - decode(s,'-',t,s) может быть null если диапазоны начинаются с target.


Fix
with p as (
select * from (
  select x, flag, decode(z,'X1',c,'-') c--, z
    from (select x1, x2+1 x2, c, flag from t) tt
 unpivot (x for z in (x1,x2))) 
 pivot (max(c) for flag in ('src' s,'tgt' t))
),
q as (
select x x1, lead(x) over (order by x) -1 x2, c from (
  select x, c, lag(c) over (order by x) cp from (
    select x, decode(nvl(s,'-'),'-',t,s) c from (
      select x,
             last_value(s ignore nulls) over (order by x) s,
             last_value(t ignore nulls) over (order by x) t
        from p
      )
    )
  )
 where c != nvl(cp,' ')
)
select sum(x1*x2) hash from q
 where x1 <= x2;
18 ноя 20, 15:38    [22234679]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
graycode,

у НеофитSQL-а одна, косяк

Ваш вариант не тестировал (что-то лень обьекты создавать)

если дойдут руки, заменю pipe на dbms_output и мож потестю

.....
stax
18 ноя 20, 15:40    [22234681]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Кобанчег
странно что это не всплыло в моём чудо тесте

Тестовые данные не покрывают много кейсов, а генератор на производительность вообще вырожденный и возможно это одна из причин удивительных результатов теста на производительность[/quot]
18 ноя 20, 15:43    [22234683]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Stax,

Здесь тот же вариант, только в исполнении в виде пакета 22233388
18 ноя 20, 15:46    [22234687]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
graycode
возможно это одна из причин
Наша песня хороша начинай сначала.
Я вчера уже поверил в твою адекватность когда ты признал что PL/SQL и SQL приверно одного уровня по производителности.
18 ноя 20, 15:49    [22234695]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
Кобанчег

Можешь использовать мой запрос, там верно возвращает.



для unpivot + pivot + lead сдаюсь

поспешил
SQL> ed
Wrote file afiedt.buf

  1  with t (x1, x2, c, flag) as
  2  (
  3                select 10, 30, 'blue', 'src' from dual
  4  union all select 20, 30, 'red', 'tgt' from dual
  5  union all select 31, 35, 'red', 'tgt' from dual
  6  )
  7  ,p as (
  8  select * from (
  9    select x, flag, decode(z,'X1',c,'-') c, z
 10      from (select x1, x2+1 x2, c, flag from t) tt
 11   unpivot (x for z in (x1,x2)))
 12   pivot (max(c) for flag in ('src' s,'tgt' t))
 13  ),
 14  q as (
 15  select x x1, lead(x) over (order by x) -1 x2, c from (
 16    select x, c, lag(c) over (order by x) cp from (
 17      select x, decode(s,'-',t,s) c from (
 18        select x,
 19               last_value(s ignore nulls) over (order by x) s,
 20               last_value(t ignore nulls) over (order by x) t
 21          from p
 22        )
 23      )
 24    )
 25   where c != nvl(cp,' ')
 26  )
 27  select x1,x2,c from q
 28*  where x1 <= x2
SQL> /

        X1         X2 C
---------- ---------- ----
        10         30 blue

SQL>



зі
match_recognize с ошибкой

зы

Сообщение было отредактировано: 18 ноя 20, 15:58
18 ноя 20, 15:57    [22234704]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Кобанчег,

Причина мне не совсем понятна, я убрал фактор сортировки, т.е. сортировок нет, просто прогоняется набор исходных данных через функцию, в функции только дерево условий, по идее должно быть быстрее, оно и быстрее но совсем незначительно, можешь объяснить причину?
18 ноя 20, 15:57    [22234705]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
graycode
Причина мне не совсем понятна, я убрал фактор сортировки, т.е. сортировок нет
open c_refcur_t for select * from t order by x1;
?
18 ноя 20, 16:00    [22234707]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Кобанчег,

IOT, pk по всем полям начиная с x1))
18 ноя 20, 16:02    [22234709]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
graycode,

Ну тогда смотри куда уходит время в dbms_hprof + dbms_sqltune.report_sql_monitor

Может что-то еще можно выжать из твоего подхода, но практической ценности для меня не несет.
18 ноя 20, 16:07    [22234713]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Stax
для unpivot + pivot + lead сдаюсь

поспешил
Ты fix тут увидел?
22234679

В моём сортировку в аналитике надо сделать идентичной с MR.
over(order by x1/*, type*/)
18 ноя 20, 16:19    [22234722]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
graycode
Stax,

Здесь тот же вариант, только в исполнении в виде пакета 22233388


SQL> create or replace package dropme_pkg as
  2      type res_rec_t is record (x1 t.x1%type, x2 t.x2%type, res t.c%type);
  3      type res_tab_t is table of res_rec_t;
  4      type refcur_t is ref cursor return t%rowtype;
  5      function f_superimpose return res_tab_t pipelined;
  6  end dropme_pkg;
  7  /

Package created.

...
104  end dropme_pkg;
105  /

Warning: Package Body created with compilation errors.

SQL> show err
Errors for PACKAGE BODY DROPME_PKG:

LINE/COL ERROR
-------- -----------------------------------------------------------------
16/9     PL/SQL: Statement ignored
16/18    PLS-00222: no function with name 'RES_REC_T' exists in this scope
SQL> l 16
 16*         l_res := res_rec_t(l_src.x1, l_src.x2, l_src.c);
SQL>


.....
stax
18 ноя 20, 16:22    [22234724]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
Кобанчег

Ты fix тут увидел?

увидел, сдался тестировать

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

звиняйте, поспешил

.....
stax
18 ноя 20, 16:30    [22234737]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
xtender
Кажется, я уже решал обе такие задачки, сходу только вспомнить и найти не смог, но нашёл чуть более сложный вариант усложненной задачки: https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set


Немного изменил условия, интервалы в целых числах, как в предыдущих задачах и добавил немного данных:

0   1   2   3   4   5   6   7   8...9...10...11...12...13...14....20.23...25

|--------------------------------------a------------------------------------|
|---b---|
|---c---|
|---d---|
|---e---|
|-f-|
|---------g--------|
|--h---|
|--i--|
|--j--|
|-k-|


with t (lvl, x1, x2) as
(
select 'a', 0, 25 from dual union all
select 'b', 2, 4 from dual union all
select 'c', 1, 3 from dual union all
select 'd', 4, 6 from dual union all
select 'e', 3, 5 from dual union all
select 'f', 7, 8 from dual union all
select 'g', 9, 13 from dual union all
select 'h', 10, 11 from dual union all
select 'i', 12, 13 from dual union all
select 'j', 13, 14 from dual union all
select 'k', 20, 23 from dual
)



select *magic* from t;
-- result:
+------+-------------+-----------+
| a | 0 | 0 |
| c | 1 | 1 |
| e | 3 | 5 |
| d | 6 | 6 |
| f | 7 | 8 |
| g | 9 | 9 |
| h | 10 | 11 |
| i | 12 | 12 |
| j | 13 | 14 |
| a | 15 | 19 |
| k | 20 | 23 |
| a | 24 | 25 |
+------+-------------+-----------+


Линейных решений не вижу, из того что вижу, возможно два разных перебора, перебор интервалов на дне стакана в момент когда падает новый блок или получение всех интервалов с последующим нахождением самого нижнего блока над отрезком по вертикали (то что реализовано у xtender).
18 ноя 20, 17:00    [22234770]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Stax
НеофитSQL
Жаль, критерий трудно определить объективно.

У меня получилось так.


должно быть две строки?

.....
stax


Нарушено условие задачи, интервалы одного уровня касаются.
18 ноя 20, 17:38    [22234790]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
xtender
Member

Откуда: Мск
Сообщений: 5704
graycode
Линейных решений не вижу, из того что вижу, возможно два разных перебора, перебор интервалов на дне стакана в момент когда падает новый блок или получение всех интервалов с последующим нахождением самого нижнего блока над отрезком по вертикали (то что реализовано у xtender).
имхо для больших наборов с большим количеством цветом наиболее эффективное решение было бы unpivot + sort + pl/sql цикл с ассоциативными массивами для не закончившихся интервалов (и удалением закончившихся). Сейчас пока некогда, да и довольно просто реализуется, так что попозже наваяю, если кто-то не сподобится сделать это раньше.
18 ноя 20, 17:45    [22234802]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Stax,

Пакет под тестирование производительности был сделан, таблица здесь 22233322
create table t(x1 int, x2 int, c varchar2(10), flag varchar2(3));

Сам тест кандидатов на лучшее время выполнения 22233403.
18 ноя 20, 17:46    [22234804]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
graycode
xtender
Кажется, я уже решал обе такие задачки, сходу только вспомнить и найти не смог, но нашёл чуть более сложный вариант усложненной задачки: https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set


Немного изменил условия, интервалы в целых числах, как в предыдущих задачах и добавил немного данных:

0   1   2   3   4   5   6   7   8...9...10...11...12...13...14....20.23...25

|--------------------------------------a------------------------------------|
|---b---|
|---c---|
|---d---|
|---e---|
|-f-|
|---------g--------|
|--h---|
|--i--|
|--j--|
|-k-|


with t (lvl, x1, x2) as
(
select 'a', 0, 25 from dual union all
select 'b', 2, 4 from dual union all
select 'c', 1, 3 from dual union all
select 'd', 4, 6 from dual union all
select 'e', 3, 5 from dual union all
select 'f', 7, 8 from dual union all
select 'g', 9, 13 from dual union all
select 'h', 10, 11 from dual union all
select 'i', 12, 13 from dual union all
select 'j', 13, 14 from dual union all
select 'k', 20, 23 from dual
)



select *magic* from t;
-- result:
+------+-------------+-----------+
| a | 0 | 0 |
| c | 1 | 1 |
| e | 3 | 5 |
| d | 6 | 6 |
| f | 7 | 8 |
| g | 9 | 9 |
| h | 10 | 11 |
| i | 12 | 12 |
| j | 13 | 14 |
| a | 15 | 19 |
| k | 20 | 23 |
| a | 24 | 25 |
+------+-------------+-----------+


Линейных решений не вижу, из того что вижу, возможно два разных перебора, перебор интервалов на дне стакана в момент когда падает новый блок или получение всех интервалов с последующим нахождением самого нижнего блока над отрезком по вертикали (то что реализовано у xtender).


Ответ в первой строчке должен быть а-0-1.
В этой задаче отрезки задаются границами интервалов (см картинку).
18 ноя 20, 17:46    [22234806]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
НеофитSQL
Ответ в первой строчке должен быть а-0-1.
В этой задаче отрезки задаются границами интервалов (см картинку).

Так я написал, что немного изменил условия, сделал их как в предыдущих задачах, т.е. интервалы 0-1 и 1-3 пересекаются, рассматривай их как блоки из кубиков.
18 ноя 20, 17:52    [22234813]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
graycode
НеофитSQL
Ответ в первой строчке должен быть а-0-1.
В этой задаче отрезки задаются границами интервалов (см картинку).

Так я написал, что немного изменил условия, сделал их как в предыдущих задачах, т.е. интервалы 0-1 и 1-3 пересекаются, рассматривай их как блоки из кубиков.


Зря изменил. Координаты для науки, кубики для детей :)

Теперь на иллюстрации длины отрезков не совпадают, и ответ все равно неверный.

По координатам должно быть: c[1-3] (так в оригинале)
По "кубикам" должно быть: c(1,2)
У тебя в ответе: c(1,1)
18 ноя 20, 18:22    [22234826]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
xtender
Member

Откуда: Мск
Сообщений: 5704
Почти линейный PL/SQL к 22232077
Кобанчег
задачка посложнее.


+
declare
  type varchars is table of varchar2(10);
  type avarchars is table of varchar2(10) index by varchar2(10);

  a_colors avarchars;
  idx varchar2(10); 
  x number;
  
  cursor c_data is 
      with t (x1, x2, c, flag) as
      (
                select 1, 4, 'red', 'src' from dual
      union all select 7, 10, 'yellow', 'src' from dual
      union all select 13, 16, 'red', 'src' from dual
      --union all select 3, 14, 'black' from dual
      union all select 3, 7, 'black', 'tgt' from dual
      union all select 9, 11, 'black', 'tgt' from dual
      union all select 13, 14, 'black', 'tgt' from dual
      --
      union all select 16, 19, 'blue', 'tgt' from dual
      union all select 18, 22, 'green', 'src' from dual
      union all select 22, 25, 'black', 'tgt' from dual
      union all select 26, 28, 'red', 'src' from dual
      union all select 29, 30, 'red', 'tgt' from dual
      union all select 32, 33, 'black', 'tgt' from dual
      )
      select *
      from t
      unpivot (x for type in (x1 as 1, x2 as 2))
      order by x, type;
      
   function iterate( idx in out nocopy varchar2, arr in out nocopy avarchars) 
      return boolean
   as pragma inline;
   begin
      if idx is null
         then idx:=arr.first; 
         else idx:=arr.next(idx);
      end if;
      return idx is not null;
   end;
 
  function keys(a in out nocopy avarchars) return varchars as
     res varchars:=varchars();
     idx varchar2(10);
     pragma inline;
  begin
     while iterate(idx,a) loop
        res.extend;
        res(res.count):=idx;
     end loop;
     return res;
  end;
begin
   for r in c_data loop
      if r.type=1 then
         a_colors(r.c):=r.c;
         x:=r.x;
      else
         a_colors.delete(r.c);
         x:=r.x+1;
      end if;
      
      dbms_output.put(x||': '||a_colors.count()||' colors:');
      while iterate(idx, a_colors) loop
         dbms_output.put(' '||a_colors(idx));
      end loop;
      dbms_output.put_line('.');
   end loop;
end;

+ output
1: 1 colors: red.
3: 2 colors: black red.
5: 1 colors: black.
7: 2 colors: black yellow.
8: 1 colors: yellow.
9: 2 colors: black yellow.
11: 1 colors: black.
12: 0 colors:.
13: 1 colors: black.
13: 2 colors: black red.
15: 1 colors: red.
16: 2 colors: blue red.
17: 1 colors: blue.
18: 2 colors: blue green.
20: 1 colors: green.
22: 2 colors: black green.
23: 1 colors: black.
26: 0 colors:.
26: 1 colors: red.
29: 0 colors:.
29: 1 colors: red.
31: 0 colors:.
32: 1 colors: black.
34: 0 colors:.
18 ноя 20, 18:41    [22234844]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Есть простое, в четыре строчки, решение для частного случая, когда при закрашивании не формируются дырки.

Общее решение пока не придумал. И по слоям, и по координатам накапливается state.
18 ноя 20, 18:43    [22234848]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
xtender
Member

Откуда: Мск
Сообщений: 5704
graycode
Немного изменил условия
зачем? в чем смысл?
18 ноя 20, 18:44    [22234849]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
xtender,

В пятничных задачах есть смысл?

На тетрис похоже))
18 ноя 20, 18:48    [22234853]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
xtender
Member

Откуда: Мск
Сообщений: 5704
graycode
xtender,

В пятничных задачах есть смысл?

На тетрис похоже))
я не понял смысла изменения, если от перевода в целые становится лишь легче, а изменение окончаний вообще странно...
18 ноя 20, 19:05    [22234866]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
НеофитSQL
По "кубикам" должно быть: c(1,2)
У тебя в ответе: c(1,1)

Да, ошибся должно быть c(1,2).
18 ноя 20, 19:10    [22234868]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Правильный ответ для задачи по отрезкам с координатами:
Также подправил картинку, а то левая часть была отрезками, а правая - "кубиками"


0 1 2 3 4 5 6 7 8...9...10...11...12...13...14...20...23...25

|--------------------------------------a----------------------------------|
|---b---|
|---c---|
|---d---|
|---e---|
|-f-|
|---------g--------|
|--h-|
|--i-|
|--j-|
|--k-|

LVL X1 X2
a 0 1
c 1 3
e 3 5
d 5 6
a 6 7
f 7 8
a 8 9
g 9 10
h 10 11
g 11 12
i 12 13
j 13 14
a 14 20
k 20 23
a 23 25

Исходные данные (от graycode), плюс мое решение "в лоб" для проверки:
with t (lvl, x1, x2) as
(
select 'a',  0, 25 from dual union all
select 'b',  2,  4 from dual union all
select 'c',  1,  3 from dual union all
select 'd',  4,  6 from dual union all
select 'e',  3,  5 from dual union all
select 'f',  7,  8 from dual union all
select 'g',  9, 13 from dual union all
select 'h', 10, 11 from dual union all
select 'i', 12, 13 from dual union all
select 'j', 13, 14 from dual union all
select 'k', 20, 23 from dual
),
p (lvl,x1,x2) as (
select lvl, x, lead(x) over (order by x) from (
  select * from (
    select x, lvl, lag(lvl) over (order by x) plvl from (
      select x, (select max(lvl) from t where x>=x1 and x <x2) lvl from (
        select level-1 x from dual where level-1 >= (select min(x1) from t) 
          connect by level <= (select max(x2) from t)+2) 
      ) 
    ) where nvl(lvl,'-') != nvl(plvl,'-')
  )
)
select * from p where lvl is not null
18 ноя 20, 19:51    [22234889]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
НеофитSQL,

Так если координаты, зачем кубики нагенерил?))

PS: решения с генерацией диапазона не очень интересны даже для кубиков, а для координат не подходят вообще.
18 ноя 20, 21:26    [22234939]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
graycode
НеофитSQL,

Так если координаты, зачем кубики нагенерил?))

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


Не кубики, а пробные значения :-Р

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

Кубики в постановке задачи элементарно переводятся в отрезки:
Х1-х2. -> [х1,х2+1)

Если отрезки целочисленные, обратное преобразование также есть, вычесть единичку.

Для работы с данными отрезки лучше, для распечатки можно перевести в кубики, в зависимости от того кто читать будет.
18 ноя 20, 22:36    [22234975]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
НеофитSQL,

Не, тут уж или крестик или трусы)))
18 ноя 20, 22:39    [22234978]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
graycode,


Лол, хорошо. +0.5 для подобных.


В pl/sql решается просто вдоль Х через стэк глубиной lvl.
В sql нащупывается рекурсивное решение, но пока не сделал
18 ноя 20, 22:55    [22234987]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
НеофитSQL
Нарушено условие задачи, интервалы одного уровня касаются.
Перечитай условие. Подумай ещё. Посмотри в чем фикс. Всё же было обсуждено.
graycode
Сам тест кандидатов на лучшее время выполнения 22233403.
Я конечно рад, что ты так проникся моим тестом 9-ти летней давности, но ты видимо так и не понял про сортировки и темп.
В той задаче были совсем другие объемы и поэтому не было надобности в alter session которые имеются в новом тесте.
19 ноя 20, 08:52    [22235082]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
xtender
Кажется, я уже решал обе такие задачки, сходу только вспомнить и найти не смог, но нашёл чуть более сложный вариант усложненной задачки: https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set
Смотря в чем измерять сложность. Однозначно это более общий вариант, но "общесть" отрубает многие приёмы которые можно было бы применять в частном случае.
xtender
Почти линейный PL/SQL к 22232077
Кобанчег
задачка посложнее.
Но ведь это абсолютный overkill когда число "слоёв" фиксировано.
+ output
select *
from
(
select x1,
       decode(src_active, 1, src_c) || decode(src_active+tgt_active, 2, ', ') || decode(tgt_active, 1, tgt_c) colors
  from (select x1,
               sum(decode(flag, 'src', sign)) over(order by x1) src_active,
               sum(decode(flag, 'tgt', sign)) over(order by x1) tgt_active,
               last_value(decode(flag, 'src', c) ignore nulls) over(order by x1) src_c,
               last_value(decode(flag, 'tgt', c) ignore nulls) over(order by x1) tgt_c
          from (select c,
                       flag,
                       type,
                       x + decode(type, 'X2', 1, 0) x1,
                       decode(type, 'X1', 1, 'X2', -1) sign
                  from t unpivot(x for type in(x1, x2)))) t
)
/

        X1 COLORS
---------- --------------
         1 red
         3 red, black
         5 black
         7 yellow, black
         8 yellow
         9 yellow, black
        11 black
        12
        13 red, black
        13 red, black
        15 red
        16 red, blue
        17 blue
        18 green, blue
        20 green
        22 green, black
        23 black
        26 red
        26 red
        29 red
        29 red
        31
        32 black
        34

24 rows selected.
19 ноя 20, 09:03    [22235086]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Challenge just for fun

Решить задачу отсюда
https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set

Не используя соединений или коррелированных подзапросов.

Ну и без завязывания на частные случаи. То есть
- границы не обязательно целочисленные - никакой генерации
- число приоритетов неограничено - никакого хардкодига
итд

У меня более одного варианта.
19 ноя 20, 09:09    [22235090]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
Кобанчег
Challenge just for fun

Решить задачу отсюда
https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set

Не используя соединений или коррелированных подзапросов.

Ну и без завязывания на частные случаи. То есть
- границы не обязательно целочисленные - никакой генерации
- число приоритетов неограничено - никакого хардкодига
итд

У меня более одного варианта.


и
1) а,b и b,c не пересекаются? соприкасаются? можно/надо слить в один a,c?
2) возможен ли диапазон a,a (зависит от ответа на п1)
3) одного цвета соприкасающиеся обьеденяем?
4) "чистый" sql или/и pl/sql?
итд

ps
у Неофита больше интервальчиков, мож и на его with тестировать
pss
жаль graycode забанили от публикаций

.....
stax
19 ноя 20, 09:57    [22235107]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Stax
1) а,b и b,c не пересекаются? соприкасаются? можно/надо слить в один a,c?
Соприкасаются (но не пересекаются) и сливаются.
Мы тут говорим про действительные числа уже.
Stax
2) возможен ли диапазон a,a (зависит от ответа на п1)
Я думаю это некорректные данные. По логике подразумевается что отрезки типа [start..end) то есть конец не входит.
Stax
3) одного цвета соприкасающиеся обьеденяем?
Да
Stax
4) "чистый" sql или/и pl/sql?
Чистый эксуэль конечно же!

Stax
жаль graycode забанили от публикаций
Да, совершенно непонятно за что забанили. Никаких предупреждений.
Более того это вообще может быть рандомный модератор любого форума.
Ну наверное самому забаненому что-то ясно.
19 ноя 20, 10:48    [22235134]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Stax,

Я тестировал на этом наборе
with ranges (name, range_start, range_end) as
(
select 'a', 0, 7 from dual
union all select 'b', 2, 4 from dual
union all select 'c', 1, 3 from dual
union all select 'd', 4, 6 from dual
union all select 'e', 3, 5 from dual
--
union all select 'x', 3, 3.1 from dual
union all select 'y', 3.5, 3.7 from dual
union all select 'z', 3.9, 5.1 from dual
union all select 'a', 8, 9 from dual
)

Последний отрезок ломает решения икстендера потому что до него дырка, но легко допиливается.
19 ноя 20, 10:50    [22235137]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Кобанчег
Последний отрезок ломает решения икстендера потому что до него дырка, но легко допиливается.
Ничего он не ломает, это провокация!
19 ноя 20, 11:05    [22235154]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
Кобанчег,

у икстендера есть главный/0 интервал покрывающий все, типа min()-x,max()+y цвета хаки
тогда дырок не будет

не знаю часть условия ли ето, или случайно

если я правильно понял то заливка уникальными цветами range_name

.....
stax
19 ноя 20, 11:10    [22235158]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Stax,

Да. У икстендера надо пустые интервалы выкинуть из результата.
19 ноя 20, 11:25    [22235169]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Кобанчег
Challenge just for fun

Решить задачу отсюда
https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set

Не используя соединений или коррелированных подзапросов.

Ну и без завязывания на частные случаи. То есть
- границы не обязательно целочисленные - никакой генерации
- число приоритетов неограничено - никакого хардкодига
итд

У меня более одного варианта.


У меня число приоритетов до 38 попугаев, т.к. я не сумел listagg() использовать в оконном режиме.

p as (
select c, x x1, lead(x) over (order by x ) x2 from (
  select c, x from (
    select c, lag(c) over (order by x) cp, x from (
      select chr(trunc(log(10,1+sum(c) over (order by x)))) c, x from (
        select  power(10,ascii(lvl)) c, x1 x from t union all
        select -power(10,ascii(lvl)) c, x2 x from t
      )
    )
  ) where nvl(c,'-') != nvl(cp,'-')
)
)
select * from p where x1 < x2 order by x1
19 ноя 20, 20:53    [22235701]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Кобанчег
НеофитSQL
Нарушено условие задачи, интервалы одного уровня касаются.
Перечитай условие. Подумай ещё. Посмотри в чем фикс. Всё же было обсуждено.


Перечитал, действительно. О несоприкосновении говорилось в разминке, но не во второй задаче. С фиксом понятно.
19 ноя 20, 20:58    [22235710]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
НеофитSQL

У меня число приоритетов до 38 попугаев, т.к. я не сумел listagg() использовать в оконном режиме.


Оно таки и не работает с окнами..
19 ноя 20, 21:44    [22235734]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
НеофитSQL
О несоприкосновении говорилось
Изначально в разрезе красное/черное, а потом подразумевалсь в разрезе src/tgt.
Но Stax уточнил 22233313.
Твой запрос поломало касание src и tgt - это допустимо.
20 ноя 20, 00:10    [22235794]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Нарушено условие задачи, интервалы одного уровня касаются.

Stax
НеофитSQL
Жаль, критерий трудно определить объективно.

У меня получилось так.


должно быть две строки?

with t (x1, x2, c, flag) as
(
              select 10, 30, 'blue', 'src' from dual
union all select 20, 30, 'red', 'tgt' from dual
union all select 31, 35, 'red', 'tgt' from dual
)
,p as (
select * from (
  select x, flag, decode(z,'X1',c,'-') c, z
    from (select x1, x2+1 x2, c, flag from t) tt
 unpivot (x for z in (x1,x2))) 
 pivot (max(c) for flag in ('src' s,'tgt' t))
),
q as (
select x x1, lead(x) over (order by x) -1 x2, c from (
  select x, c, lag(c) over (order by x) cp from (
    select x, decode(s,'-',t,s) c from (
      select x,
             last_value(s ignore nulls) over (order by x) s,
             last_value(t ignore nulls) over (order by x) t
        from p
      )
    )
  )
 where c != nvl(cp,' ')
)
select x1,x2,c from q
 where x1 <= x2  
/

SQL> /

        X1         X2 C
---------- ---------- ----
        10         30 blue


.....
stax
20 ноя 20, 02:50    [22235818]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
НеофитSQL,

Да, верно.
Это заодно и объясняет почему тест производительности не выявил различий.
Данные были нагенерированы без таких случаев.
20 ноя 20, 04:30    [22235833]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Пятница, господа!

Челендж еще активен
Кобанчег
Challenge just for fun

Решить задачу отсюда
https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set

Не используя соединений или коррелированных подзапросов.

Ну и без завязывания на частные случаи. То есть
- границы не обязательно целочисленные - никакой генерации
- число приоритетов неограничено - никакого хардкодига
итд

У меня более одного варианта.


Данные для тестирования
with ranges (name, range_start, range_end) as
(
select 'a', 0, 7 from dual
union all select 'b', 2, 4 from dual
union all select 'c', 1, 3 from dual
union all select 'd', 4, 6 from dual
union all select 'e', 3, 6 from dual
--
union all select 'x', 3, 3.1 from dual
union all select 'y', 3.5, 3.7 from dual
union all select 'z', 3.9, 5.1 from dual
union all select 'a', 8, 9 from dual
union all select 'a', 8, 9.9 from dual
)


Constraints
(name, range_start, range_end) - уникально
(range_end > range_start)
20 ноя 20, 15:22    [22236090]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
xtender
Member

Откуда: Мск
Сообщений: 5704
Кобанчег
- число приоритетов неограничено
name может быть от a,...,z,aa,...,az,...,zzzzzzzzzzzzz?
20 ноя 20, 15:35    [22236098]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
xtender
Member

Откуда: Мск
Сообщений: 5704
Кобанчег,

model, рекурсивные запросы?
20 ноя 20, 15:35    [22236100]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
xtender
Кобанчег,

model, рекурсивные запросы?
Затрудняюсь представить как можно обойтись без джойна в рекурсивном члене.

Модель - конено, почему бы нет. Ну разве что итеративная модель - это не спортивно.
20 ноя 20, 15:42    [22236105]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
xtender
Кобанчег
- число приоритетов неограничено
name может быть от a,...,z,aa,...,az,...,zzzzzzzzzzzzz?
Не вижу смысла ограничивать, но если с какими-то подобнми особенностями получается что-то изящное - интересно было бы посмотреть.
Ну на единичную длину закладываться не стоит.
20 ноя 20, 15:46    [22236111]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
Кобанчег
xtender
пропущено...
name может быть от a,...,z,aa,...,az,...,zzzzzzzzzzzzz?
Не вижу смысла ограничивать, но если с какими-то подобнми особенностями получается что-то изящное - интересно было бы посмотреть.
Ну на единичную длину закладываться не стоит.

имхо
удобнее было-б уровень задавать числами (int), цвет varchar2(хх)

....
stax
20 ноя 20, 16:17    [22236127]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Stax,

Мне кажется примерно индифферентно для чего делать max.
20 ноя 20, 16:59    [22236152]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
Кобанчег
Stax,

Мне кажется примерно индифферентно для чего делать max.

a
aa
ab
c
d
...
z

мне удобнее числа
и легче тестовые добавлять (+ не надо помнить алфавит)

в етой пятничной наверное менять не надо, у народа наработки уже на буквах

.....
stax
20 ноя 20, 17:06    [22236153]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Собственно варианты следующие.

Раз

select *
  from (select x, max(decode(y, 1, name)) name
          from (select *
                  from (select x, name, sum(r) r
                          from ranges unpivot(x for r in(range_start as '1', range_end as '-1'))
                         group by x, name)
                 model dimension by(x, name) measures(r, 0 y)
                 rules upsert all
                 (
                   y[x, for name in (select distinct name from ranges)] = sign(sum(r)[x <= cv(x), name = cv(name)])
                 ))
         group by x)
match_recognize
(
  order by x
  measures
    first(x) range_start,
    next(x) range_end,
    name name
  pattern (x+)
  define x as first(name) = name
)
order by 1, 2
for loop + upsert all помогает получить все имена для каждого перехода.
Дальше берем max и склеиваем с помощью MR.

for loop однако требует отдельного обращения к таблице. По идее Оракл это мог бы брать из памяти.
------------------------------------------------------------------------
| Id  | Operation                                             | Name   |
------------------------------------------------------------------------
|   0 | SELECT STATEMENT                                      |        |
|   1 |  SORT ORDER BY                                        |        |
|   2 |   VIEW                                                |        |
|   3 |    MATCH RECOGNIZE SORT DETERMINISTIC FINITE AUTOMATON|        |
|   4 |     VIEW                                              |        |
|   5 |      HASH GROUP BY                                    |        |
|   6 |       VIEW                                            |        |
|   7 |        BUFFER SORT                                    |        |
|   8 |         SQL MODEL ORDERED                             |        |
|   9 |          HASH GROUP BY                                |        |
|  10 |           VIEW                                        |        |
|  11 |            UNPIVOT                                    |        |
|  12 |             TABLE ACCESS FULL                         | RANGES |
|  13 |          BUFFER SORT                                  |        |
|  14 |           HASH UNIQUE                                 |        |
|  15 |            TABLE ACCESS FULL                          | RANGES |
------------------------------------------------------------------------

22 rows selected.


Два

Получаем оригинальные и "нарезанные" интервалы.
Моделью возвращаем "нарезанные" с определенными новыми именами (return updated rows).
Последним шагом снова склеиваем через MR.

select *
  from (select *
          from (select range_start, range_end, name, 'original' type
                  from ranges
                union all
                select x as range_start, lead(x) over(order by x) as range_end, null, 'derived'
                  from (select distinct x
                          from ranges unpivot(x for r in(range_start, range_end))))
  model
  return updated rows
  dimension by (range_start, range_end, type)
  measures (name)
  rules
  (
    name[range_start, range_end, 'derived'] = max(name)[range_start < cv(range_end), range_end > cv(range_start), type = 'original']
  )
)
match_recognize
(
  order by range_start
  measures
    first(range_start) range_start,
    range_end range_end,
    name name
  pattern (x+)
  define x as first(name) = name
)
order by 1, 2


Если заморочиться можно обойтись одним обращением к таблице + двойной UNPIVOT + MODEL + MATCH RECOGNIZE
+

select *
  from (select *
          from (select name,
                       type,
                       x1 range_start,
                       nvl(x2, lead(x1) over(partition by type order by x1)) range_end
                  from (select distinct name, x x1, x2, type
                          from (select decode(type, 'original', name) name,
                                       range_start,
                                       decode(type, 'derived', range_end) range_end,
                                       decode(type, 'original', range_end) x2,
                                       type
                                  from (select r.*, 1 dummy from ranges r)
                                  unpivot (dummy for type in (dummy as 'original', dummy as 'derived'))
                                )
                          unpivot (x for r in (range_start, range_end))
                        )
                )
          model
          return updated rows
          dimension by (range_start, range_end, type)
          measures (name)
          rules
          (
            name[range_start, range_end, 'derived'] = max(name)[range_start < cv(range_end), range_end > cv(range_start), type = 'original']
          )
       )
match_recognize
(
  order by range_start
  measures
    first(range_start) range_start,
    range_end range_end,
    name name
  pattern (x+)
  define x as first(name) = name
)
order by 1, 2

------------------------------------------------------------------------
| Id  | Operation                                             | Name   |
------------------------------------------------------------------------
|   0 | SELECT STATEMENT                                      |        |
|   1 |  SORT ORDER BY                                        |        |
|   2 |   VIEW                                                |        |
|   3 |    MATCH RECOGNIZE SORT DETERMINISTIC FINITE AUTOMATON|        |
|   4 |     VIEW                                              |        |
|   5 |      BUFFER SORT                                      |        |
|   6 |       SQL MODEL ORDERED                               |        |
|   7 |        VIEW                                           |        |
|   8 |         WINDOW SORT                                   |        |
|   9 |          VIEW                                         |        |
|  10 |           HASH UNIQUE                                 |        |
|  11 |            VIEW                                       |        |
|  12 |             UNPIVOT                                   |        |
|  13 |              VIEW                                     |        |
|  14 |               UNPIVOT                                 |        |
|  15 |                TABLE ACCESS FULL                      | RANGES |
------------------------------------------------------------------------

20 ноя 20, 19:39    [22236199]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
with ranges (name, range_start, range_end) as
(
          select 'a', 0, 7 from dual
union all select 'b', 2, 4 from dual
union all select 'c', 1, 3 from dual
union all select 'd', 4, 6 from dual
union all select 'e', 3, 5 from dual
),
p (r,c,a,b) as (
          select dense_rank() over (order by name), name, range_start, range_end   from ranges
union all select dense_rank() over (order by name), null, -100500,     range_start from ranges
union all select dense_rank() over (order by name), null, range_end,   +100500     from ranges
),
cte (n, clr, x, y) as (
select max(r)+1, null, -100500, +100500 from p union all
select n-1, c, greatest(x,a), least(y,b)
  from cte e, p 
 where n > 1 and r=n-1 and clr is null and x < y
)
select * from cte where x < y and clr is not null order by x


Вместо 100500 можно +/- бесконечность (быстрее) или min(start)/max(end) (медленнее).
Приоритет вычисляется по значению name, как в оригинальной задаче.
Кобанчег, у тебя в последней строчке 'e',3,6 вместо 'е',3,5 - намеренно или опечатка?
20 ноя 20, 19:42    [22236201]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Сравним скорость, или подождем PL/SQL варианта?
20 ноя 20, 19:43    [22236202]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
НеофитSQL
Кобанчег, у тебя в последней строчке 'e',3,6 вместо 'е',3,5 - намеренно или опечатка?
Опечатка скорее. Предполагалось исходные данные оставить как есть.
Но "опечатка" была использована ранее для тестирования.
НеофитSQL
from cte e, p
Я вижу джойн, а ты?
20 ноя 20, 19:45    [22236203]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
НеофитSQL
Сравним скорость, или подождем PL/SQL варианта?
Если хотя бы отдалённо понимать принцип работы, то абсолютно очевидно что PL/SQL здесь несомненный лидер.
SQL-но и безджойно было "just for fun".

PS. Икстендер публиковал PL/SQL подход.
20 ноя 20, 19:49    [22236205]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Ну и по приколу линейный проход.
Но это не спортивно ибо xmlquery (которым вообще-то можно реализовать какие-угодно джойны)
+ ограничение на длину конкатенации + предполагается что входные имена не содержат запятых.
+
SQL> with ranges (name, range_start, range_end) as
  2  (
  3  select 'a', 0, 7 from dual
  4  union all select 'b', 2, 4 from dual
  5  union all select 'c', 1, 3 from dual
  6  union all select 'd', 4, 5 from dual
  7  union all select 'e', 3, 5 from dual
  8  --
  9  union all select 'x', 3, 3.1 from dual
 10  union all select 'y', 3.5, 3.7 from dual
 11  union all select 'z', 3.9, 5.1 from dual
 12  union all select 'a', 8, 9 from dual
 13  union all select 'a', 8, 9.9 from dual
 14  )
 15  select --+ no_xml_query_rewrite
 16    x, s str, xmlcast(xmlquery('max(tokenize(.,","))' passing(t.s) returning content) as varchar2(4000)) name
 17    from
 18  (
 19    select x, max(s) keep (dense_rank last order by name) s
 20      from
 21    (
 22      select *
 23        from (select x, name, sum(sum(r)) over (partition by name order by x) r
 24                from ranges unpivot(x for r in(range_start as '1', range_end as '-1'))
 25               group by x, name)
 26      model
 27      dimension by(row_number() over (order by x, name) i)
 28      measures(x, name, r, cast('' as varchar2(4000)) s)
 29      rules
 30      (
 31        s[i] = case
 32                 when r[cv()] = 0 then replace(s[cv()-1], name[cv()] || ',')
 33                 else
 34                   case
 35                     when nvl(instr(s[cv()-1], name[cv()] || ','), 0) > 0 then s[cv()-1]
 36                     else s[cv()-1] || name[cv()] || ','
 37                   end
 38               end
 39      )
 40    )
 41    group by x
 42  ) t
 43  order by 1;

         X STR        NAME
---------- ---------- ----------
         0 a,         a
         1 a,c,       c
         2 a,c,b,     c
         3 a,b,e,x,   x
       3.1 a,b,e,     e
       3.5 a,b,e,y,   y
       3.7 a,b,e,     e
       3.9 a,b,e,z,   z
         4 a,e,z,d,   z
         5 a,z,       z
       5.1 a,         a
         7
         8 a,         a
         9 a,         a
       9.9

15 rows selected.
20 ноя 20, 20:00    [22236211]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Кобанчег

НеофитSQL
from cte e, p
Я вижу джойн, а ты?


Я его написал :)

Понадеялся что джойн по константе исполняется эффективно.

Не всякий "from a, b" стоит циклов, бывают бесплатные или дешёвые. Например, "from a,b where b.rowid=x" ничего не должен стоить.

Больше беспокоит многопроходность.
В худшем случае мой алгоритм дает О(n*n) шагов и 3n памяти.

В лучшем, O(n).
20 ноя 20, 22:37    [22236254]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Сделал пару быстрых проверок на таблице из 10К строк.
Самое простое решение с подчиненным циклом оказалось довольно медленным, несмотря на наличие индексов:

-- без агрегации групп, формат вывода как у xtender
SQL> select x, (select max(color) from test_ranges where range_start <= x and range_end > x) from
  2  (select range_start x from test_ranges union select range_end from test_ranges) order by x;

20000 rows selected.

Elapsed: 00:02:59.52

Execution Plan
----------------------------------------------------------

| Id  | Operation                         | Name             | Rows  | Bytes |TempSpc| Cost (%CPU)|

---------------------------------------------------------------------------------------------------

|   0 | SELECT STATEMENT                  |                  |  1999K|    24M|     | 28455   (2)|
|   1 |  SORT AGGREGATE                   |                  |     1 |    49 |     |            |
|   2 |   TABLE ACCESS BY INDEX ROWID     | TEST_RANGES      |  2500 |   119K|     |   981   (1)|
|   3 |    BITMAP CONVERSION TO ROWIDS    |                  |       |       |     |            |
|   4 |     BITMAP AND                    |                  |       |       |     |            |
|   5 |      BITMAP CONVERSION FROM ROWIDS|                  |       |       |     |            |
|   6 |       SORT ORDER BY               |                  |       |       | 800K|            |
|   7 |        INDEX RANGE SCAN           | TEST_RANGES_IDX1 |       |       |     |    43   (0)|
|   8 |      BITMAP CONVERSION FROM ROWIDS|                  |       |       |     |            |
|   9 |       SORT ORDER BY               |                  |       |       | 800K|            |
|  10 |        INDEX RANGE SCAN           | TEST_RANGES_IDX2 |       |       |     |    44   (0)|
|  11 |  SORT ORDER BY                    |                  |  1999K|    24M|  38M| 28455   (2)|
|  12 |   VIEW                            |                  |  1999K|    24M|     | 18871   (1)|
|  13 |    SORT UNIQUE                    |                  |  1999K|    41M|  53M| 18871  (51)|
|  14 |     UNION-ALL                     |                  |       |       |     |            |
|  15 |      TABLE ACCESS FULL            | TEST_RANGES      |   999K|    20M|     |  2753   (1)|
|  16 |      TABLE ACCESS FULL            | TEST_RANGES      |   999K|    20M|     |  2754   (1)|

Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
   45481209  consistent gets
          0  physical reads
          0  redo size
     653151  bytes sent via SQL*Net to client
      15023  bytes received via SQL*Net from client
       1335  SQL*Net roundtrips to/from client
      40002  sorts (memory)
          0  sorts (disk)
      20000  rows processed


Рекурсивное решение:
SQL> with p (r,c,a,b) as (
  2            select color, color, range_start, range_end from test_ranges
  3  union all select color, null, null, range_start       from test_ranges
  4  union all select color, null, range_end, null         from test_ranges
  5  ),
  6  cte (n, clr, x, y) as (
  7  select max(color)+1, null, min(range_start), max(range_end) from test_ranges union all
  8  select n-1, c, nvl2(a,greatest(x,a),x), nvl2(b,least(y,b),y)
  9    from cte e, p
 10   where n > 1 and r=n-1 and clr is null and x < y
 11  )
 12  select * from cte where x < y and clr is not null order by x;

31 rows selected.

Elapsed: 00:00:46.25

Execution Plan
----------------------------------------------------------

| Id  | Operation                                  | Name        | Rows  | Bytes | Cost (%CPU)|

-----------------------------------------------------------------------------------------------

|   0 | SELECT STATEMENT                           |             |     4 |   208 | 13793   (1)|
|   1 |  SORT ORDER BY                             |             |     4 |   208 | 13793   (1)|
|   2 |   VIEW                                     |             |     4 |   208 | 13792   (1)|
|   3 |    UNION ALL (RECURSIVE WITH) BREADTH FIRST|             |       | |            |
|   4 |     SORT AGGREGATE                         |             |     1 |    49 |            |
|   5 |      TABLE ACCESS FULL                     | TEST_RANGES |   999K|    46M|  2754   (1)|
|   6 |     HASH JOIN                              |             |     3 |   312 | 11038   (1)|
|   7 |      RECURSIVE WITH PUMP                   |             |       | |            |
|   8 |      VIEW                                  |             |  2999K|   148M|  8262   (1)|
|   9 |       UNION-ALL                            |             |       | |            |
|  10 |        TABLE ACCESS FULL                   | TEST_RANGES |   999K|    46M|  2754   (1)|
|  11 |        TABLE ACCESS FULL                   | TEST_RANGES |   999K|    25M|  2753   (1)|
|  12 |        TABLE ACCESS FULL                   | TEST_RANGES |   999K|    25M|  2754   (1)|

--------------------------------------------------------------------------------
Statistics
----------------------------------------------------------
          2  recursive calls
      60582  db block gets
    2389761  consistent gets
          0  physical reads
          0  redo size
       2341  bytes sent via SQL*Net to client
        382  bytes received via SQL*Net from client
          4  SQL*Net roundtrips to/from client
       8049  sorts (memory)
          0  sorts (disk)
         31  rows processed


Как заполнялась тест таблица:

SQL> insert into test_ranges select level, dbms_random.value(0,10), null from dual connect by level <= 10000;
10000 rows inserted
Executed in 0,156 seconds

SQL> update test_ranges set range_end=dbms_random.value(range_start,10);
10000 rows updated
Executed in 0,578 seconds

SQL> alter index test_ranges_idx1 rebuild online;

Index altered.

Elapsed: 00:00:00.09
SQL> alter index test_ranges_idx2 rebuild online;

Index altered.

Elapsed: 00:00:00.11
23 ноя 20, 18:47    [22237422]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Вячеслав Любомудров
Member

Откуда: Владивосток
Сообщений: 18486
Можно попробовать запретить использование планов с виртуальным преобразованием в виртуальные битовые индексы и обратно (это крайне было полезно в 9-ке, но, возможно, не утратило актуальности и в новых версиях)
alter session set "_b_tree_bitmap_plans"=false
24 ноя 20, 01:19    [22237584]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2 3 4 5 6 7 8      [все]
Все форумы / Oracle Ответить