Solución para asignar valores únicos a filas con distancia de colaboración finita

Tengo una tabla que se puede crear y completar con el siguiente 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 las filas que tienen una distancia de colaboración finita basada en RecordKeyotra fila, me gustaría asignar un valor único; no me importa cómo o qué tipo de datos es el valor único.

Se puede generar un conjunto de resultados correcto que cumpla con lo que estoy pidiendo con la siguiente 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 ayudar mejor a lo que pregunto, explicaré por qué GroupKeys 1–3 tienen lo mismo SupergroupKey:

• GroupKey1 contiene el RecordKeyEuler que a su vez está contenido en GroupKey2; entonces GroupKeys 1 y 2 deben tener lo mismo SupergroupKey.
• Como Gauss está contenido tanto en GroupKeys 2 como en 3, ellos también deben tener lo mismo SupergroupKey. Esto lleva a GroupKeys 1–3 a tener lo mismo SupergroupKey.
• Dado que GroupKeys 1–3 no comparte ninguna RecordKeys con las GroupKeys restantes , son las únicas que tienen asignado un SupergroupKeyvalor de 1.

Debo agregar que la solución debe ser genérica. La tabla anterior y el conjunto de resultados fue simplemente un ejemplo.

Apéndice

Eliminé el requisito de que la solución no sea iterativa. Si bien preferiría tal solución, creo que es una restricción irrazonable. Desafortunadamente, no puedo usar ninguna solución basada en CLR; pero si desea incluir tal solución, no dude en hacerlo. Sin embargo, es probable que no lo acepte como respuesta.

El número de filas en mi tabla real es tan grande como 5 millones, pero hay días en que el número de filas "solo" será de alrededor de diez mil. En promedio hay 8 RecordKeys por GroupKeyy 4 GroupKeys por RecordKey. Me imagino que una solución tendrá una complejidad de tiempo exponencial, pero de todos modos estoy interesado en una solución.

Esta es una solución iterativa de T-SQL para la comparación de rendimiento.

Se supone que se puede agregar una columna adicional a la tabla para almacenar la clave de supergrupo y se puede cambiar la indexación:

Preparar

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

Si puede invertir el orden de las claves de la clave primaria actual, no se requerirá el índice único adicional.

contorno

El enfoque de esta solución es:

1. Establezca la identificación del supergrupo en 1
2. Encuentre la clave de grupo sin procesar con el número más bajo
3. Si no se encuentra ninguno, salga
4. Establecer el supergrupo para todas las filas con la clave de grupo actual
5. Establecer el supergrupo para todas las filas relacionadas con las filas del grupo actual
6. Repita el paso 5 hasta que no se actualicen filas
7. Incrementar la identificación actual del supergrupo
8. Ir al paso 2

Implementación

Comentarios en línea:

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

Plan de ejecución

Para la actualización clave:

Resultado

El estado final de la tabla es:

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

Demostración: db <> fiddle

Pruebas de rendimiento

Utilizando el conjunto de datos de prueba ampliado proporcionado en la respuesta de Michael Green , los tiempos en mi computadora portátil ^* son:

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

_{* Microsoft SQL Server 2017 (RTM-CU13), Developer Edition (64-bit), Windows 10 Pro, 16GB RAM, SSD, 4 core hyperthreaded i7, 2.4GHz nominal.}

Este problema se trata de seguir enlaces entre elementos. Esto lo coloca en el ámbito de los gráficos y el procesamiento de gráficos. Específicamente, todo el conjunto de datos forma un gráfico y estamos buscando componentes de ese gráfico. Esto se puede ilustrar con una gráfica de los datos de muestra de la pregunta.

La pregunta dice que podemos seguir GroupKey o RecordKey para encontrar otras filas que compartan ese valor. Entonces podemos tratar a ambos como vértices en un gráfico. La pregunta continúa para explicar cómo GroupKeys 1–3 tienen la misma SupergroupKey. Esto se puede ver como el grupo a la izquierda unido por líneas finas. La imagen también muestra los otros dos componentes (SupergroupKey) formados por los datos originales.

SQL Server tiene alguna capacidad de procesamiento de gráficos integrada en T-SQL. Sin embargo, en este momento es bastante escaso y no ayuda con este problema. SQL Server también tiene la capacidad de llamar a R y Python, y al conjunto de paquetes rico y robusto disponible para ellos. Uno de ellos es igraph . Está escrito para "el manejo rápido de gráficos grandes, con millones de vértices y bordes ( enlace )".

Usando R e igraph pude procesar un millón de filas en 2 minutos y 22 segundos en la prueba local ¹ . Así es como se compara con la mejor solución actual:

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.

Al procesar filas de 1M, se usaron 1m40 para cargar y procesar el gráfico, y para actualizar la tabla. Se requirieron 42 para completar una tabla de resultados SSMS con la salida.

La observación del Administrador de tareas mientras se procesaban 1 millón de filas sugiere que se necesitaban unos 3 GB de memoria de trabajo. Esto estaba disponible en este sistema sin paginación.

Puedo confirmar la evaluación de Ypercube del enfoque recursivo de CTE. Con unos pocos cientos de claves de grabación consumió el 100% de la CPU y toda la RAM disponible. Finalmente, tempdb creció a más de 80 GB y el SPID se bloqueó.

Usé la tabla de Paul con la columna SupergroupKey para que haya una comparación justa entre las soluciones.

Por alguna razón, R se opuso al acento en Poincaré. Cambiarlo a una simple "e" le permitió ejecutarse. No investigué ya que no está relacionado con el problema en cuestión. Estoy seguro de que hay una solución.

Aqui esta el codigo

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

Esto es lo que hace el código R

• @input_data_1 es cómo SQL Server transfiere datos de una tabla a código R y los traduce a un marco de datos R llamado InputDataSet.

• library(igraph) importa la biblioteca al entorno de ejecución de R.

• df.g <- graph.data.frame(d = InputDataSet, directed = FALSE)cargar los datos en un objeto igraph. Este es un gráfico no dirigido ya que podemos seguir enlaces de grupo a registro o grabar a grupo. InputDataSet es el nombre predeterminado de SQL Server para el conjunto de datos enviado a R.

• cpts <- components(df.g, mode = c("weak")) procesar el gráfico para encontrar sub-gráficos discretos (componentes) y otras medidas.

• OutputDataSet <- data.frame(cpts$membership)SQL Server espera un marco de datos de R. Su nombre predeterminado es OutputDataSet. Los componentes se almacenan en un vector llamado "membresía". Esta declaración traduce el vector a un marco de datos.

• OutputDataSet$VertexName <- V(df.g)$nameV () es un vector de vértices en el gráfico, una lista de GroupKeys y RecordKeys. Esto los copia en el marco de datos de salida, creando una nueva columna llamada VertexName. Esta es la clave utilizada para coincidir con la tabla de origen para actualizar SupergroupKey.

No soy un experto en R. Probablemente esto podría optimizarse.

Datos de prueba

Los datos del OP se utilizaron para la validación. Para las pruebas de escala utilicé el siguiente 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);

Me acabo de dar cuenta de que obtuve las proporciones al revés de la definición del OP. No creo que esto afecte los tiempos. Los registros y grupos son simétricos a este proceso. Para el algoritmo, todos son nodos en un gráfico.

Al probar, los datos invariablemente formaron un solo componente. Creo que esto se debe a la distribución uniforme de los datos. Si en lugar de la relación estática 1: 8 codificada en la rutina de generación, hubiera permitido que la relación variara , probablemente habría habido más componentes.

¹ Especificaciones ^{de la} máquina: Microsoft SQL Server 2017 (RTM-CU12), Developer Edition (64 bits), Windows 10 Home. 16 GB de RAM, SSD, i7 de 4 núcleos hyperthreaded, 2.8GHz nominal. Las pruebas fueron los únicos elementos que se ejecutaron en ese momento, aparte de la actividad normal del sistema (aproximadamente 4% de CPU).

Un método CTE recursivo, que probablemente sea terriblemente ineficiente en tablas grandes:

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

Probado en dbfiddle.uk