Solução para atribuir valores exclusivos a linhas com distância finita de colaboração

Eu tenho uma tabela que pode ser criada e preenchida com o seguinte código:

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

Para todas as linhas que possuem uma distância de colaboração finita com base em RecordKeyoutra linha, gostaria de atribuir um valor exclusivo - não me importo como ou que tipo de dados é o valor exclusivo.

Um conjunto de resultados correto que atenda ao que estou solicitando pode ser gerado com a seguinte consulta:

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;

Para ajudar melhor o que estou perguntando, explicarei por que os GroupKey1-3 são iguais SupergroupKey:

• GroupKey1 contém o RecordKeyEuler que por sua vez está contido em GroupKey2; portanto, GroupKeys 1 e 2 devem ter o mesmo SupergroupKey.
• Como Gauss está contido em GroupKeys 2 e 3, eles também devem ter o mesmo SupergroupKey. Isso leva a que GroupKeys 1–3 tenha o mesmo SupergroupKey.
• Como GroupKeys 1–3 não compartilha nenhum RecordKeys com os GroupKeys restantes , eles são os únicos com o SupergroupKeyvalor 1.

Devo acrescentar que a solução precisa ser genérica. A tabela acima e o conjunto de resultados foram apenas um exemplo.

Termo aditivo

Eu removi o requisito de a solução não ser iterativa. Embora eu prefira uma solução desse tipo, acredito que seja uma restrição irracional. Infelizmente, não consigo usar nenhuma solução baseada em CLR; mas se você quiser incluir essa solução, sinta-se à vontade. Eu provavelmente não aceitarei isso como resposta.

O número de linhas na minha tabela real é de até 5 milhões, mas há dias em que o número de linhas "apenas" será de cerca de dez mil. Em média, existem 8 RecordKeys por GroupKeye 4 GroupKeys por RecordKey. Imagino que uma solução tenha complexidade de tempo exponencial, mas, no entanto, estou interessado em uma solução.

Esta é uma solução T-SQL iterativa para comparação de desempenho.

Ele pressupõe que uma coluna extra possa ser adicionada à tabela para armazenar a chave do super grupo e a indexação pode ser alterada:

Configuração

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

Se você conseguir reverter a ordem das chaves da chave primária atual, o índice exclusivo extra não será necessário.

Esboço

A abordagem desta solução é:

1. Defina o ID do super grupo como 1
2. Encontre a chave de grupo não processado com o número mais baixo
3. Se nenhum foi encontrado, saia
4. Defina o super grupo para todas as linhas com a chave de grupo atual
5. Defina o super grupo para todas as linhas relacionadas às linhas no grupo atual
6. Repita a etapa 5 até que nenhuma linha seja atualizada
7. Incremente o ID do super grupo atual
8. Avance para o passo 2

Implementação

Comentários em linha:

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

Plano de execução

Para a atualização da chave:

Resultado

O estado final da tabela é:

╔═══════════════╦══════════╦══════════════╗
║ 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          ║
╚═══════════════╩══════════╩══════════════╝

Demonstração: db <> violino

Testes de performance

Usando o conjunto de dados de teste expandido fornecido na resposta de Michael Green , os tempos no meu laptop ^* são:

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

_{* Microsoft SQL Server 2017 (RTM-CU13), Developer Edition (64 bits), Windows 10 Pro, 16 GB de RAM, SSD, i7 hyperthreaded de 4 núcleos, nominal de 2,4 GHz.}

Esse problema é sobre seguir os links entre os itens. Isso o coloca no domínio de gráficos e processamento de gráficos . Especificamente, todo o conjunto de dados forma um gráfico e estamos procurando componentes desse gráfico. Isso pode ser ilustrado por um gráfico dos dados de amostra da pergunta.

A pergunta diz que podemos seguir GroupKey ou RecordKey para encontrar outras linhas que compartilham esse valor. Assim, podemos tratar ambos como vértices em um gráfico. A pergunta continua para explicar como as teclas de grupo 1 a 3 têm a mesma tecla de supergrupo. Isso pode ser visto como o cluster à esquerda unido por linhas finas. A imagem também mostra os outros dois componentes (SupergroupKey) formados pelos dados originais.

O SQL Server possui alguma capacidade de processamento gráfico incorporada ao T-SQL. No momento, porém, é bastante escasso e não ajuda com esse problema. O SQL Server também pode chamar R e Python, e o rico e robusto conjunto de pacotes disponíveis para eles. Um deles é o gráfico . Foi escrito para "manipulação rápida de gráficos grandes, com milhões de vértices e arestas ( link )".

Usando R e igraph, fui capaz de processar um milhão de linhas em 2 minutos e 22 segundos no teste local ¹ . É assim que ele se compara à melhor solução atual:

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.

Ao processar 1 milhão de linhas, 1m40s foram usados ​​para carregar e processar o gráfico e atualizar a tabela. 42s foram necessários para preencher uma tabela de resultados do SSMS com a saída.

A observação do Gerenciador de Tarefas enquanto as linhas de 1 milhão foram processadas sugere que são necessários cerca de 3 GB de memória de trabalho. Isso estava disponível neste sistema sem paginação.

Posso confirmar a avaliação de Ypercube da abordagem CTE recursiva. Com algumas centenas de chaves de registro, consumiu 100% da CPU e toda a RAM disponível. Eventualmente, o tempdb cresceu para mais de 80 GB e o SPID travou.

Eu usei a tabela de Paul com a coluna SupergroupKey, para que haja uma comparação justa entre as soluções.

Por alguma razão, R se opôs ao sotaque de Poincaré. Mudá-lo para um "e" simples permitiu a execução. Não investiguei, pois não é relevante para o problema em questão. Tenho certeza que há uma solução.

Aqui está o código

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

É isso que o código R faz

• @input_data_1 é como o SQL Server transfere dados de uma tabela para o código R e os converte em um dataframe R chamado InputDataSet.

• library(igraph) importa a biblioteca para o ambiente de execução R.

• df.g <- graph.data.frame(d = InputDataSet, directed = FALSE)carregar os dados em um objeto igraph. Este é um gráfico não direcionado, pois podemos seguir os links do grupo para gravar ou gravar para o grupo. InputDataSet é o nome padrão do SQL Server para o conjunto de dados enviado para R.

• cpts <- components(df.g, mode = c("weak")) processe o gráfico para encontrar subgráficos discretos (componentes) e outras medidas.

• OutputDataSet <- data.frame(cpts$membership)O SQL Server espera um quadro de dados de volta de R. Seu nome padrão é OutputDataSet. Os componentes são armazenados em um vetor chamado "associação". Esta declaração converte o vetor em um quadro de dados.

• OutputDataSet$VertexName <- V(df.g)$nameV () é um vetor de vértices no gráfico - uma lista de Teclas de Grupo e Teclas de Registro. Isso os copia no quadro de dados de saída, criando uma nova coluna chamada VertexName. Essa é a chave usada para corresponder à tabela de origem para atualizar o SupergroupKey.

Eu não sou um especialista em R. Provavelmente isso pode ser otimizado.

Dados de teste

Os dados do OP foram utilizados para validação. Para testes de escala, usei o seguinte script.

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

Acabei de perceber que entendi errado as proporções da definição do OP. Eu não acredito que isso afetará os horários. Registros e grupos são simétricos para esse processo. Para o algoritmo, todos são apenas nós em um gráfico.

No teste, os dados invariavelmente formaram um único componente. Eu acredito que isso se deve à distribuição uniforme dos dados. Se, em vez da proporção estática de 1: 8, codificada na rotina de geração, eu permitisse que a proporção variasse , provavelmente haveria outros componentes.

¹ Especificação da máquina: Microsoft SQL Server 2017 (RTM-CU12), Developer Edition (64 bits), Windows 10 Home. 16GB de RAM, SSD, i7 hyperthreaded de 4 núcleos, 2,8 GHz nominal. Os testes foram os únicos itens em execução no momento, exceto a atividade normal do sistema (cerca de 4% da CPU).

Um método CTE recursivo - que provavelmente será terrivelmente ineficiente em grandes tabelas:

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

Testado em dbfiddle.uk