Группировка диапазонов

Тээкс... в очередной раз туплю.

Упрощённая задача:

MS SQL 2008, в табличку последовательно сыпятся события с одного источника аля

DECLARE @T TABLE
(
  ID int NOT NULL, -- unique
  Parent_ID int NULL,
  StartEndFlag bit NULL, -- 0 - operation start, 1 - operation end, NULL - ordinary message
  Msg nvarchar(260)
);
                                                                      -- Parent_ID:
INSERT @T (ID, StartEndFlag, Msg) VALUES (1,  NULL, N'Msg1');         -- NULL
INSERT @T (ID, StartEndFlag, Msg) VALUES (2,  NULL, N'Msg2');         -- NULL
INSERT @T (ID, StartEndFlag, Msg) VALUES (3,  0,    N'Op1');          -- NULL
INSERT @T (ID, StartEndFlag, Msg) VALUES (4,  NULL, N'Op1\Msg1');     -- 3
INSERT @T (ID, StartEndFlag, Msg) VALUES (5,  NULL, N'Op1\Msg2');     -- 3
INSERT @T (ID, StartEndFlag, Msg) VALUES (6,  0,    N'Op1\Op2');      -- 3
INSERT @T (ID, StartEndFlag, Msg) VALUES (7,  NULL, N'Op1\Op2\Msg1'); -- 6
INSERT @T (ID, StartEndFlag, Msg) VALUES (8,  1,    N'Op1\Op2');      -- 6
INSERT @T (ID, StartEndFlag, Msg) VALUES (9,  NULL, N'Op1\Msg3');     -- 3
INSERT @T (ID, StartEndFlag, Msg) VALUES (10, 1,    N'Op1');          -- 3
INSERT @T (ID, StartEndFlag, Msg) VALUES (11, NULL, N'Msg3');         -- NULL

Требуется сохранить в Parent_ID ID операции, в рамках которой появилось сообщение.
Другими словами - выбрать начало последнего незакрытого диапазона.

Грабли в том, что msg на деле содержит мусор и диапазоны можно определять только по (ID, StartEndFlag). Если повезёт и я таки договорюсь с источником, текст в сообщении о завершении операции будет соответствовать тексту сообщения о начале операции. Но никто не гарантирует что не будет вложенных операций с одинаковым текстом.

Чорд, я запутался уже с CTEшками. Помогите, а?;)

Ну сделать то можно, только это будет ни разу не быстро на таких данных.

Рекурсией - например, так:

with q as (select ID, StartEndFlag, Msg, cast(null as char(10)) Parent_ID, cast('' as varchar(8000)) SpiParent 
from @T where ID=1
union all 
select T.ID, T.StartEndFlag, T.Msg, cast(right(SpiParent,10) as char(10)),
case T.StartEndFlag 
	when 0 then SpiParent+str(T.ID,10)
	when 1 then substring(SpiParent,1,len(SpiParent)-10)
	else SpiParent end
from q
inner join @T T on T.ID=q.ID+1
)
select ID, StartEndFlag, Msg, cast(nullif(Parent_ID,'') as int) Parent_ID from q

Но на больших данных курсор окажется быстрее.

ЗЫ. Будет работать при отсутствии дырок в нумерации ID. Если дырки есть - предварительно нумеруйте выборку.

Anddros, спасибо.
Уже сделал на курсорах, наверно так и оставлю пока голова и руки не освободятся.

Вааах, какой кошмарик получился!

Как бы это упростить...

DECLARE @T TABLE
(
  ID int NOT NULL, -- unique
  StartEndFlag bit NULL, -- 0 - range start, 1 - range end
  Msg nvarchar(260)
);

INSERT @T (ID, StartEndFlag, Msg) VALUES (1,  NULL, N'1'); 
INSERT @T (ID, StartEndFlag, Msg) VALUES (2,  0,    N'\'); 
INSERT @T (ID, StartEndFlag, Msg) VALUES (3,  NULL, N'|1');
INSERT @T (ID, StartEndFlag, Msg) VALUES (4,  NULL, N'|2');
INSERT @T (ID, StartEndFlag, Msg) VALUES (5,  0,    N'|\');
INSERT @T (ID, StartEndFlag, Msg) VALUES (6,  NULL, N'||1');
INSERT @T (ID, StartEndFlag, Msg) VALUES (7,  1,    N'|/');
INSERT @T (ID, StartEndFlag, Msg) VALUES (8,  0,    N'|\');
INSERT @T (ID, StartEndFlag, Msg) VALUES (9,  0,    N'||\');
INSERT @T (ID, StartEndFlag, Msg) VALUES (11, NULL, N'|||1');
INSERT @T (ID, StartEndFlag, Msg) VALUES (12, 0,    N'|||\');
INSERT @T (ID, StartEndFlag, Msg) VALUES (13, NULL, N'||||1');
INSERT @T (ID, StartEndFlag, Msg) VALUES (14, 1,    N'|||/')
INSERT @T (ID, StartEndFlag, Msg) VALUES (15, NULL, N'|||1');
INSERT @T (ID, StartEndFlag, Msg) VALUES (16, 1,    N'||/');
INSERT @T (ID, StartEndFlag, Msg) VALUES (17, 1,    N'|/');
INSERT @T (ID, StartEndFlag, Msg) VALUES (18, 1,    N'/');

---

WITH Nested
AS
(
  SELECT T1.ID, T1.StartEndFlag, T2.StartCount - T3.EndCount AS NestingLevel
    FROM @T T1
      OUTER APPLY (
        SELECT COUNT (T2.ID) AS StartCount
          FROM @T T2 WHERE T1.ID > T2.ID AND T2.StartEndFlag = 0) AS T2
      OUTER APPLY (
        SELECT COUNT (T3.ID) AS EndCount
          FROM @T T3 WHERE T1.ID > T3.ID AND T3.StartEndFlag = 1) AS T3
),
StartMessages
AS
(
  SELECT ID, NestingLevel,
      ROW_NUMBER()OVER(PARTITION BY NestingLevel ORDER BY ID) AS Ord
    FROM Nested
    WHERE StartEndFlag = 0
),
EndMessages
AS
(
  SELECT ID, NestingLevel-1 AS NestingLevel,
      ROW_NUMBER()OVER(PARTITION BY NestingLevel ORDER BY ID) AS Ord
    FROM Nested
    WHERE StartEndFlag = 1
),
Ranges
AS
(
SELECT SM.ID, EM.ID AS EndID
  FROM StartMessages SM LEFT JOIN EndMessages EM
    ON SM.NestingLevel = EM.NestingLevel
    AND SM.Ord = EM.Ord
)
SELECT T.ID, P.Parent_ID, T.StartEndFlag, T.Msg  FROM @T T
  OUTER APPLY (SELECT MAX(R.ID) AS Parent_ID
    FROM Ranges R WHERE R.ID < T.ID AND (R.EndID>=T.ID OR R.EndID IS NULL)) AS P;

Редкостное творение... чо там мучатьси?

DECLARE @T TABLE
(
  ID int NOT NULL, -- unique
  Parent_ID int NULL,
  StartEndFlag bit NULL, -- 0 - operation start, 1 - operation end, NULL - ordinary message
  Msg nvarchar(260)
);
                                                                      -- Parent_ID:
INSERT @T (ID, StartEndFlag, Msg) VALUES (1,  NULL, N'Msg1');         -- NULL
INSERT @T (ID, StartEndFlag, Msg) VALUES (2,  NULL, N'Msg2');         -- NULL
INSERT @T (ID, StartEndFlag, Msg) VALUES (3,  0,    N'Op1');          -- NULL
INSERT @T (ID, StartEndFlag, Msg) VALUES (4,  NULL, N'Op1\Msg1');     -- 3
INSERT @T (ID, StartEndFlag, Msg) VALUES (5,  NULL, N'Op1\Msg2');     -- 3
INSERT @T (ID, StartEndFlag, Msg) VALUES (6,  0,    N'Op1\Op2');      -- 3
INSERT @T (ID, StartEndFlag, Msg) VALUES (7,  NULL, N'Op1\Op2\Msg1'); -- 6
INSERT @T (ID, StartEndFlag, Msg) VALUES (8,  1,    N'Op1\Op2');      -- 6
INSERT @T (ID, StartEndFlag, Msg) VALUES (9,  NULL, N'Op1\Msg3');     -- 3
INSERT @T (ID, StartEndFlag, Msg) VALUES (10, 1,    N'Op1');          -- 3
INSERT @T (ID, StartEndFlag, Msg) VALUES (11, NULL, N'Msg3');         -- NULL

select * FROM @T

;with cte
as
(
select ID, Parent_ID, StartEndFlag, Msg, null CurrOpStartID
FROM @T WHERE ID=(select min(ID) FROM @T)
union all
select T.ID, T.Parent_ID, T.StartEndFlag, T.Msg
       , CASE T.StartEndFlag 
           WHEN 0 then T.ID 
           WHEN 1 THEN (select ID FROM @T X WHERE X.StartEndFlag=0 AND X.ID<CTE.CurrOpStartID) 
           ELSE CTE.CurrOpStartID END CurrOpStartID
FROM 
@T T
INNER JOIN
CTE 
ON T.ID=CTE.ID+1
)
select * FROM cte

Только это будет абсолютным тормозом на приличных объемах.

Вуаля;)

DECLARE @T TABLE
(
  ID int NOT NULL, -- unique
  StartEndFlag bit NULL, -- 0 - range start, 1 - range end
  Msg nvarchar(260)
);

INSERT @T (ID, StartEndFlag, Msg) VALUES (1,  NULL, N'1'); 
INSERT @T (ID, StartEndFlag, Msg) VALUES (2,  0,    N'\'); 
INSERT @T (ID, StartEndFlag, Msg) VALUES (3,  NULL, N'|1');
INSERT @T (ID, StartEndFlag, Msg) VALUES (4,  NULL, N'|2');
INSERT @T (ID, StartEndFlag, Msg) VALUES (5,  0,    N'|\');
INSERT @T (ID, StartEndFlag, Msg) VALUES (6,  NULL, N'||1');
INSERT @T (ID, StartEndFlag, Msg) VALUES (7,  1,    N'|/');
INSERT @T (ID, StartEndFlag, Msg) VALUES (8,  0,    N'|\');
INSERT @T (ID, StartEndFlag, Msg) VALUES (9,  0,    N'||\');
INSERT @T (ID, StartEndFlag, Msg) VALUES (10, 0,    N'|||1');
INSERT @T (ID, StartEndFlag, Msg) VALUES (11, NULL, N'|||2');
INSERT @T (ID, StartEndFlag, Msg) VALUES (12, 0,    N'|||\');
INSERT @T (ID, StartEndFlag, Msg) VALUES (13, NULL, N'||||1');
INSERT @T (ID, StartEndFlag, Msg) VALUES (14, 1,    N'|||/')
INSERT @T (ID, StartEndFlag, Msg) VALUES (15, NULL, N'|||1');
INSERT @T (ID, StartEndFlag, Msg) VALUES (16, 1,    N'||/');
INSERT @T (ID, StartEndFlag, Msg) VALUES (17, 1,    N'|/');
INSERT @T (ID, StartEndFlag, Msg) VALUES (18, 1,    N'/');
INSERT @T (ID, StartEndFlag, Msg) VALUES (19, 0,    N'\');
INSERT @T (ID, StartEndFlag, Msg) VALUES (20, 1,    N'/');

WITH Nested
AS
(
  SELECT T1.ID, T1.Msg, T1.StartEndFlag, T2.StartCount - T3.EndCount AS NestingLevel
    FROM @T T1
      OUTER APPLY (
        SELECT COUNT (T2.ID) AS StartCount
          FROM @T T2 WHERE T1.ID > T2.ID AND T2.StartEndFlag = 0) AS T2
      OUTER APPLY (
        SELECT COUNT (T3.ID) AS EndCount
          FROM @T T3 WHERE T1.ID > T3.ID AND T3.StartEndFlag = 1) AS T3
)
SELECT ID, Msg, Parent_ID, StartEndFlag FROM Nested N
  OUTER APPLY (
    SELECT MAX(ID) AS Parent_ID
      FROM Nested N2
      WHERE N2.ID < N.ID AND N2.NestingLevel = N.NestingLevel-1) AS N2;

Впрочем, чо-то я лоханулся

declare @s table(n int identity primary key clustered, id int not null)
insert @s(ID)
select ID
FROM @T
WHERE StartEndFlag=0

select * FROM @s


;with cte
as
(
select ID, Parent_ID, StartEndFlag, Msg, null CurrOpStartID, 0 OpLevel
FROM @T WHERE ID=(select min(ID) FROM @T)
union all
select T.ID, T.Parent_ID, T.StartEndFlag, T.Msg
       , CASE T.StartEndFlag 
           WHEN 0 then T.ID 
           WHEN 1 THEN (select ID FROM @s X WHERE X.n=CTE.OpLevel-1) 
           ELSE CTE.CurrOpStartID END CurrOpStartID
       , CASE T.StartEndFlag 
           WHEN 0 then CTE.OpLevel+1
           WHEN 1 THEN CTE.OpLevel-1 
           ELSE CTE.OpLevel END OpLevel
FROM 
@T T
INNER JOIN
CTE 
ON T.ID=CTE.ID+1
)
select * FROM cte

Временную таблицу @s можно заменить CTE, но будет дюже тормозно...

Sinix

Вуаля;)

Дарагуля, OUTER APPLY - это для лохов или когда уж совсем неча делать.

aleks2,
ваш вариант упадёт, если

WHEN 1 THEN (select ID FROM @T X WHERE X.StartEndFlag=0 AND X.ID<CTE.CurrOpStartID) 

вернёт больше одного значения.

Пусть пока будет как есть.