이 문제는 항목 사이의 링크를 따르는 것입니다. 이것은 그래프 와 그래프 처리 영역에 넣습니다 . 특히, 전체 데이터 세트는 그래프를 형성하며 해당 그래프의 구성 요소 를 찾고 있습니다. 이것은 질문에서 얻은 샘플 데이터의 플롯으로 설명 할 수 있습니다.

문제는 GroupKey 또는 RecordKey를 따라 해당 값을 공유하는 다른 행을 찾을 수 있다고 말합니다. 따라서 그래프에서 둘 다 꼭지점으로 취급 할 수 있습니다. GroupKey 1–3이 동일한 SupergroupKey를 갖는 방법을 설명하는 질문이 계속됩니다. 이것은 왼쪽의 클러스터가가는 선으로 결합 된 것으로 볼 수 있습니다. 그림은 또한 원래 데이터에 의해 형성된 두 개의 다른 구성 요소 (SupergroupKey)를 보여줍니다.

SQL Server에는 T-SQL에 내장 된 일부 그래프 처리 기능이 있습니다. 그러나 현재로서는 매우 빈약하며이 문제에 도움이되지 않습니다. 또한 SQL Server는 R 및 Python을 호출 할 수있는 기능과 풍부하고 강력한 패키지를 사용할 수 있습니다. 하나는 igraph 입니다. “수백만 개의 정점과 모서리가있는 큰 그래프를 빠르게 처리하기 위해 작성되었습니다 ( link ).

R과 igraph를 사용하여 로컬 테스트 ¹ 에서 2 분 22 초 만에 백만 개의 행을 처리 할 수있었습니다 . 이것이 현재 최고의 솔루션과 비교하는 방법입니다.

Record Keys     Paul White  R
------------    ----------  --------
Per question    15ms        ~220ms
100             80ms        ~270ms
1,000           250ms       430ms
10,000          1.4s        1.7s
100,000         14s         14s
1M              2m29        2m22s
1M              n/a         1m40    process only, no display

The first column is the number of distinct RecordKey values. The number of rows
in the table will be 8 x this number.

1M 행을 처리 할 때 1m40을 사용하여 그래프를로드 및 처리하고 테이블을 업데이트했습니다. SSMS 결과 테이블을 출력으로 채우려면 42가 필요했습니다.

1M 행이 처리되는 동안 작업 관리자를 관찰하면 약 3GB의 작업 메모리가 필요합니다. 페이징없이이 시스템에서 사용할 수있었습니다.

재귀 CTE 접근법에 대한 Ypercube의 평가를 확인할 수 있습니다. 수백 개의 레코드 키로 100 %의 CPU와 사용 가능한 모든 RAM을 소비했습니다. 결국 tempdb는 80GB 이상으로 증가하고 SPID가 충돌했습니다.

Paul의 테이블을 SupergroupKey 열과 함께 사용했기 때문에 솔루션간에 공정한 비교가 이루어졌습니다.

어떤 이유로 R은 Poincaré의 악센트에 반대했습니다. 일반 “e”로 변경하면 실행할 수있었습니다. 나는 그것이 당면한 문제와 관련이 없기 때문에 조사하지 않았다. 해결책이 있다고 확신합니다.

여기 코드가 있습니다

-- This captures the output from R so the base table can be updated.
drop table if exists #Results;

create table #Results
(
    Component   int         not NULL,
    Vertex      varchar(12) not NULL primary key
);


truncate table #Results;    -- facilitates re-execution

declare @Start time = sysdatetimeoffset();  -- for a 'total elapsed' calculation.

insert #Results(Component, Vertex)
exec sp_execute_external_script
    @language = N'R',
    @input_data_1 = N'select GroupKey, RecordKey from dbo.Example',
    @script = N'
library(igraph)
df.g <- graph.data.frame(d = InputDataSet, directed = FALSE)
cpts <- components(df.g, mode = c("weak"))
OutputDataSet <- data.frame(cpts$membership)
OutputDataSet$VertexName <- V(df.g)$name
';

-- Write SuperGroupKey to the base table, as other solutions do
update e
set
    SupergroupKey = r.Component
from dbo.Example as e
inner join #Results as r
    on r.Vertex = e.RecordKey;

-- Return all rows, as other solutions do
select
    e.SupergroupKey,
    e.GroupKey,
    e.RecordKey
from dbo.Example as e;

-- Calculate the elapsed
declare @End time = sysdatetimeoffset();
select Elapse_ms = DATEDIFF(MILLISECOND, @Start, @End);

이것이 R 코드의 기능입니다

• @input_data_1 SQL Server가 테이블에서 R 코드로 데이터를 전송하고 InputDataSet이라는 R 데이터 프레임으로 변환하는 방법입니다.

• library(igraph) 라이브러리를 R 실행 환경으로 가져옵니다.

• df.g <- graph.data.frame(d = InputDataSet, directed = FALSE)데이터를 igraph 객체에로드합니다. 그룹 간 링크를 따라 기록하거나 그룹별로 링크를 따라갈 수 있기 때문에 무 방향 그래프입니다. InputDataSet은 R로 전송 된 데이터 집합에 대한 SQL Server의 기본 이름입니다.

• cpts <- components(df.g, mode = c("weak")) 그래프를 처리하여 이산 하위 그래프 (구성 요소) 및 기타 측정 값을 찾습니다.

• OutputDataSet <- data.frame(cpts$membership)SQL Server는 R에서 데이터 프레임을 다시 기대합니다. 기본 이름은 OutputDataSet입니다. 컴포넌트는 “멤버쉽”이라는 벡터에 저장됩니다. 이 문장은 벡터를 데이터 프레임으로 변환합니다.

• OutputDataSet$VertexName <- V(df.g)$nameV ()는 그래프에서 꼭짓점으로 구성된 벡터입니다 (GroupKey 및 RecordKey 목록). 그러면 출력 데이터 프레임으로 복사되어 VertexName이라는 새 열이 만들어집니다. SupergroupKey를 업데이트하기 위해 소스 테이블과 일치시키는 데 사용되는 키입니다.

저는 R 전문가가 아닙니다. 아마도 이것은 최적화 될 수 있습니다.

테스트 데이터

OP의 데이터는 유효성 검사에 사용되었습니다. 규모 테스트를 위해 다음 스크립트를 사용했습니다.

drop table if exists Records;
drop table if exists Groups;

create table Groups(GroupKey int NOT NULL primary key);
create table Records(RecordKey varchar(12) NOT NULL primary key);
go

set nocount on;

-- Set @RecordCount to the number of distinct RecordKey values desired.
-- The number of rows in dbo.Example will be 8 * @RecordCount.
declare @RecordCount    int             = 1000000;

-- @Multiplier was determined by experiment.
-- It gives the OP's "8 RecordKeys per GroupKey and 4 GroupKeys per RecordKey"
-- and allows for clashes of the chosen random values.
declare @Multiplier     numeric(4, 2)   = 2.7;

-- The number of groups required to reproduce the OP's distribution.
declare @GroupCount     int             = FLOOR(@RecordCount * @Multiplier);


-- This is a poor man's numbers table.
insert Groups(GroupKey)
select top(@GroupCount)
    ROW_NUMBER() over (order by (select NULL))
from sys.objects as a
cross join sys.objects as b
--cross join sys.objects as c  -- include if needed


declare @c int = 0
while @c < @RecordCount
begin
    -- Can't use a set-based method since RAND() gives the same value for all rows.
    -- There are better ways to do this, but it works well enough.
    -- RecordKeys will be 10 letters, a-z.
    insert Records(RecordKey)
    select
        CHAR(97 + (26*RAND())) +
        CHAR(97 + (26*RAND())) +
        CHAR(97 + (26*RAND())) +
        CHAR(97 + (26*RAND())) +
        CHAR(97 + (26*RAND())) +
        CHAR(97 + (26*RAND())) +
        CHAR(97 + (26*RAND())) +
        CHAR(97 + (26*RAND())) +
        CHAR(97 + (26*RAND())) +
        CHAR(97 + (26*RAND()));

    set @c += 1;
end


-- Process each RecordKey in alphabetical order.
-- For each choose 8 GroupKeys to pair with it.
declare @RecordKey varchar(12) = '';
declare @Groups table (GroupKey int not null);

truncate table dbo.Example;

select top(1) @RecordKey = RecordKey
from Records
where RecordKey > @RecordKey
order by RecordKey;

while @@ROWCOUNT > 0
begin
    print @Recordkey;

    delete @Groups;

    insert @Groups(GroupKey)
    select distinct C
    from
    (
        -- Hard-code * from OP's statistics
        select FLOOR(RAND() * @GroupCount)
        union all
        select FLOOR(RAND() * @GroupCount)
        union all
        select FLOOR(RAND() * @GroupCount)
        union all
        select FLOOR(RAND() * @GroupCount)
        union all
        select FLOOR(RAND() * @GroupCount)
        union all
        select FLOOR(RAND() * @GroupCount)
        union all
        select FLOOR(RAND() * @GroupCount)
        union all
        select FLOOR(RAND() * @GroupCount)
    ) as T(C);

    insert dbo.Example(GroupKey, RecordKey)
    select
        GroupKey, @RecordKey
    from @Groups;

    select top(1) @RecordKey = RecordKey
    from Records
    where RecordKey > @RecordKey
    order by RecordKey;
end

-- Rebuild the indexes to have a consistent environment
alter index iExample on dbo.Example rebuild partition = all
WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF,
      ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON);


-- Check what we ended up with:
select COUNT(*) from dbo.Example;  -- Should be @RecordCount * 8
                                   -- Often a little less due to random clashes
select
    ByGroup = AVG(C)
from
(
    select CONVERT(float, COUNT(1) over(partition by GroupKey))
    from dbo.Example
) as T(C);

select
    ByRecord = AVG(C)
from
(
    select CONVERT(float, COUNT(1) over(partition by RecordKey))
    from dbo.Example
) as T(C);

방금 OP의 정의에서 비율을 잘못 알았습니다. 나는 이것이 타이밍에 영향을 줄 것이라고 믿지 않는다. 레코드 및 그룹은이 프로세스와 대칭입니다. 알고리즘은 모두 그래프의 노드 일뿐입니다.

데이터를 테스트 할 때 항상 단일 구성 요소가 형성되었습니다. 나는 이것이 데이터의 균일 한 분포 때문이라고 생각합니다. 정적 1 : 8 비율 대신 생성 루틴에 하드 코딩 된 경우 비율을 변경 하도록 허용 한 경우 추가 구성 요소가있을 수 있습니다.

¹ 기계 사양 : Microsoft SQL Server 2017 (RTM-CU12), Developer Edition (64 비트), Windows 10 Home. 16GB RAM, SSD, 4 코어 하이퍼 스레딩 i7, 2.8GHz 공칭. 테스트는 정상적인 시스템 활동 (약 4 %의 CPU)을 제외하고 당시에 실행중인 유일한 항목이었습니다.

답변

WITH rCTE AS
(
    -- Anchor
    SELECT
        GroupKey, RecordKey,
        CAST('|' + CAST(GroupKey AS VARCHAR(10)) + '|' AS VARCHAR(100)) AS GroupKeys,
        CAST('|' + CAST(RecordKey AS VARCHAR(10)) + '|' AS VARCHAR(100)) AS RecordKeys,
        1 AS lvl
    FROM Example

    UNION ALL

    -- Recursive
    SELECT
        e.GroupKey, e.RecordKey,
        CASE WHEN r.GroupKeys NOT LIKE '%|' + CAST(e.GroupKey AS VARCHAR(10)) + '|%'
            THEN CAST(r.GroupKeys + CAST(e.GroupKey AS VARCHAR(10)) + '|' AS VARCHAR(100))
            ELSE r.GroupKeys
        END,
        CASE WHEN r.RecordKeys NOT LIKE '%|' + CAST(e.RecordKey AS VARCHAR(10)) + '|%'
            THEN CAST(r.RecordKeys + CAST(e.RecordKey AS VARCHAR(10)) + '|' AS VARCHAR(100))
            ELSE r.RecordKeys
        END,
        r.lvl + 1
    FROM rCTE AS r
         JOIN Example AS e
         ON  e.RecordKey = r.RecordKey
         AND r.GroupKeys NOT LIKE '%|' + CAST(e.GroupKey AS VARCHAR(10)) + '|%'
         -- 
         OR e.GroupKey = r.GroupKey
         AND r.RecordKeys NOT LIKE '%|' + CAST(e.RecordKey AS VARCHAR(10)) + '|%'
)
SELECT
    ROW_NUMBER() OVER (ORDER BY GroupKeys) AS SuperGroupKey,
    GroupKeys, RecordKeys
FROM rCTE AS c
WHERE NOT EXISTS
      ( SELECT 1
        FROM rCTE AS m
        WHERE m.lvl > c.lvl
          AND m.GroupKeys LIKE '%|' + CAST(c.GroupKey AS VARCHAR(10)) + '|%'
        OR    m.lvl = c.lvl
          AND ( m.GroupKey > c.GroupKey
             OR m.GroupKey = c.GroupKey
             AND m.RecordKeys > c.RecordKeys
              )
          AND m.GroupKeys LIKE '%|' + CAST(c.GroupKey AS VARCHAR(10)) + '|%'
          AND c.GroupKeys LIKE '%|' + CAST(m.GroupKey AS VARCHAR(10)) + '|%'
      )
OPTION (MAXRECURSION 0) ;