유한 한 협업 거리로 행에 고유 한 값을 할당하는 솔루션 GroupKey = 4 UNION ALL SELECT 3 AS

다음 코드로 작성하고 채울 수있는 테이블이 있습니다.

CREATE TABLE dbo.Example(GroupKey int NOT NULL, RecordKey varchar(12) NOT NULL);
ALTER TABLE dbo.Example
    ADD CONSTRAINT iExample PRIMARY KEY CLUSTERED(GroupKey ASC, RecordKey ASC);
INSERT INTO dbo.Example(GroupKey, RecordKey)
VALUES (1, 'Archimedes'), (1, 'Newton'), (1, 'Euler'), (2, 'Euler'), (2, 'Gauss'),
       (3, 'Gauss'), (3, 'Poincaré'), (4, 'Ramanujan'), (5, 'Neumann'),
       (5, 'Grothendieck'), (6, 'Grothendieck'), (6, 'Tao');

다른 행을 기반으로 유한 협업 거리 를 갖는 모든 행 RecordKey에 고유 한 값을 지정하고 싶습니다. 고유 한 값의 데이터 유형이 어떻게 또는 어떤지 상관하지 않습니다.

내가 원하는 것을 충족시키는 올바른 결과 집합은 다음 쿼리로 생성 할 수 있습니다.

SELECT 1 AS SupergroupKey, GroupKey, RecordKey
FROM dbo.Example
WHERE GroupKey IN(1, 2, 3)
UNION ALL
SELECT 2 AS SupergroupKey, GroupKey, RecordKey
FROM dbo.Example
WHERE GroupKey = 4
UNION ALL
SELECT 3 AS SupergroupKey, GroupKey, RecordKey
FROM dbo.Example
WHERE GroupKey IN(5, 6)
ORDER BY SupergroupKey ASC, GroupKey ASC, RecordKey ASC;

내가 원하는 것을 더 잘 돕기 위해, GroupKeys 1-3이 왜 같은지 설명 할 것이다 SupergroupKey.

  • GroupKey1은 RecordKey오일러를 포함하고, 이는 GroupKey2 에 차례로 포함되며 ; 따라서 GroupKeys 1과 2는 같아야 SupergroupKey합니다.
  • Gauss는 GroupKeys 2와 3 에 모두 포함되어 있기 때문에 그것들도 동일해야합니다 SupergroupKey. 이것으로 GroupKey1 ~ 3의 값이 같습니다 SupergroupKey.
  • 이후 GroupKey의 1-3 어떤 공유하지 않는 RecordKey나머지로들 GroupKey들, 그들은 할당 된 유일한 사람 SupergroupKey1의 값입니다.

솔루션이 일반적이어야한다고 덧붙여 야합니다. 위의 표와 결과 집합은 단지 예일뿐입니다.

추가

솔루션이 반복적이지 않다는 요구 사항을 제거했습니다. 나는 그러한 해결책을 선호하지만 그것이 불합리한 제약이라고 믿습니다. 불행히도 CLR 기반 솔루션을 사용할 수 없습니다. 그러나 그러한 솔루션을 포함하고 싶다면 자유롭게 느끼십시오. 그래도 대답으로 받아들이지 않을 것입니다.

내 실제 테이블의 행 수는 5 백만 개이지만 행 수가 “만”인 날이 있습니다. 평균적으로 RecordKey1 초 에 8 초 GroupKey와 4 GroupKey초가 RecordKey있습니다. 솔루션이 기하 급수적으로 복잡 할 것이라고 생각하지만 그럼에도 불구하고 솔루션에 관심이 있습니다.



답변

성능 비교를위한 반복적 인 T-SQL 솔루션입니다.

수퍼 그룹 키를 저장하기 위해 테이블에 추가 열을 추가 할 수 있으며 인덱싱을 변경할 수 있다고 가정합니다.

설정

DROP TABLE IF EXISTS
    dbo.Example;

CREATE TABLE dbo.Example
(
    SupergroupKey integer NOT NULL
        DEFAULT 0,
    GroupKey integer NOT NULL,
    RecordKey varchar(12) NOT NULL,

    CONSTRAINT iExample
    PRIMARY KEY CLUSTERED
        (GroupKey ASC, RecordKey ASC),

    CONSTRAINT [IX dbo.Example RecordKey, GroupKey]
    UNIQUE NONCLUSTERED (RecordKey, GroupKey),

    INDEX [IX dbo.Example SupergroupKey, GroupKey]
        (SupergroupKey ASC, GroupKey ASC)
);

INSERT dbo.Example
    (GroupKey, RecordKey)
VALUES
    (1, 'Archimedes'),
    (1, 'Newton'),
    (1, 'Euler'),
    (2, 'Euler'),
    (2, 'Gauss'),
    (3, 'Gauss'),
    (3, 'Poincaré'),
    (4, 'Ramanujan'),
    (5, 'Neumann'),
    (5, 'Grothendieck'),
    (6, 'Grothendieck'),
    (6, 'Tao');

현재 기본 키의 키 순서를 반대로 바꿀 수 있으면 추가 고유 인덱스가 필요하지 않습니다.

개요

이 솔루션의 접근 방식은 다음과 같습니다.

  1. 수퍼 그룹 ID를 1로 설정하십시오.
  2. 가장 낮은 번호의 처리되지 않은 그룹 키 찾기
  3. 찾을 수 없으면 종료
  4. 현재 그룹 키를 사용하여 모든 행의 수퍼 그룹을 설정하십시오.
  5. 현재 그룹의 행 과 관련된 모든 행에 대해 수퍼 그룹을 설정하십시오.
  6. 행이 업데이트되지 않을 때까지 5 단계를 반복하십시오.
  7. 현재 수퍼 그룹 ID 증가
  8. 2 단계로 이동

이행

주석 인라인 :

-- No execution plans or rows affected messages
SET NOCOUNT ON;
SET STATISTICS XML OFF;

-- Reset all supergroups
UPDATE E
SET SupergroupKey = 0
FROM dbo.Example AS E
    WITH (TABLOCKX)
WHERE
    SupergroupKey != 0;

DECLARE
    @CurrentSupergroup integer = 0,
    @CurrentGroup integer = 0;

WHILE 1 = 1
BEGIN
    -- Next super group
    SET @CurrentSupergroup += 1;

    -- Find the lowest unprocessed group key
    SELECT
        @CurrentGroup = MIN(E.GroupKey)
    FROM dbo.Example AS E
    WHERE
        E.SupergroupKey = 0;

    -- Exit when no more unprocessed groups
    IF @CurrentGroup IS NULL BREAK;

    -- Set super group for all records in the current group
    UPDATE E
    SET E.SupergroupKey = @CurrentSupergroup
    FROM dbo.Example AS E
    WHERE
        E.GroupKey = @CurrentGroup;

    -- Iteratively find all groups for the super group
    WHILE 1 = 1
    BEGIN
        WITH
            RecordKeys AS
            (
                SELECT DISTINCT
                    E.RecordKey
                FROM dbo.Example AS E
                WHERE
                    E.SupergroupKey = @CurrentSupergroup
            ),
            GroupKeys AS
            (
                SELECT DISTINCT
                    E.GroupKey
                FROM RecordKeys AS RK
                JOIN dbo.Example AS E
                    WITH (FORCESEEK)
                    ON E.RecordKey = RK.RecordKey
            )
        UPDATE E WITH (TABLOCKX)
        SET SupergroupKey = @CurrentSupergroup
        FROM GroupKeys AS GK
        JOIN dbo.Example AS E
            ON E.GroupKey = GK.GroupKey
        WHERE
            E.SupergroupKey = 0
        OPTION (RECOMPILE, QUERYTRACEON 9481); -- The original CE does better

        -- Break when no more related groups found
        IF @@ROWCOUNT = 0 BREAK;
    END;
END;

SELECT
    E.SupergroupKey,
    E.GroupKey,
    E.RecordKey
FROM dbo.Example AS E;

실행 계획

키 업데이트의 경우 :

업데이트 계획

결과

테이블의 최종 상태는 다음과 같습니다.

╔═══════════════╦══════════╦══════════════╗
║ SupergroupKey ║ GroupKey ║  RecordKey   ║
╠═══════════════╬══════════╬══════════════╣
║             1 ║        1 ║ Archimedes   ║
║             1 ║        1 ║ Euler        ║
║             1 ║        1 ║ Newton       ║
║             1 ║        2 ║ Euler        ║
║             1 ║        2 ║ Gauss        ║
║             1 ║        3 ║ Gauss        ║
║             1 ║        3 ║ Poincaré     ║
║             2 ║        4 ║ Ramanujan    ║
║             3 ║        5 ║ Grothendieck ║
║             3 ║        5 ║ Neumann      ║
║             3 ║        6 ║ Grothendieck ║
║             3 ║        6 ║ Tao          ║
╚═══════════════╩══════════╩══════════════╝

데모 : db <> fiddle

성능 테스트

마이클 그린에서 제공하는 확장 된 테스트 데이터 세트를 사용하여 답을 내 노트북에 타이밍 * 있습니다 :

╔═════════════╦════════╗
║ Record Keys ║  Time  ║
╠═════════════╬════════╣
║ 10k         ║ 2s     ║
║ 100k        ║ 12s    ║
║ 1M          ║ 2m 30s ║
╚═════════════╩════════╝

* Microsoft SQL Server 2017 (RTM-CU13), Developer Edition (64 비트), Windows 10 Pro, 16GB RAM, SSD, 4 코어 하이퍼 스레딩 i7, 2.4GHz 공칭.


답변

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

여기에 이미지 설명을 입력하십시오

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

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

R과 igraph를 사용하여 로컬 테스트 1 에서 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 비율 대신 생성 루틴에 하드 코딩 된 경우 비율을 변경 하도록 허용 한 경우 추가 구성 요소가있을 수 있습니다.

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


답변

재귀 CTE 방법-큰 테이블에서 끔찍하게 비효율적 일 수 있습니다.

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) ;

dbfiddle.uk 에서 테스트


답변