Solution pour attribuer des valeurs uniques aux lignes avec une distance de collaboration finie

J'ai une table qui peut être créée et remplie avec le code suivant:

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

Pour toutes les lignes qui ont une distance de collaboration finie basée sur RecordKeyune autre ligne, je voudrais attribuer une valeur unique — peu m'importe le type ou le type de données de la valeur unique.

Un jeu de résultats correct qui répond à ce que je demande peut être généré avec la requête suivante:

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;

Pour mieux aider ce que je demande, je vais expliquer pourquoi les GroupKeyarticles 1 à 3 ont la même chose SupergroupKey:

• GroupKey1 contient l' RecordKeyEuler qui à son tour est contenu dans GroupKey2; donc GroupKeys 1 et 2 doivent avoir la même chose SupergroupKey.
• Parce que Gauss est contenu à la fois dans GroupKeys 2 et 3, ils doivent aussi avoir la même chose SupergroupKey. Cela conduit à ce que les GroupKeyarticles 1 à 3 soient identiques SupergroupKey.
• Puisque les GroupKeys 1 à 3 ne partagent aucun RecordKeys avec les GroupKeys restants , ils sont les seuls à avoir une SupergroupKeyvaleur de 1.

Je dois ajouter que la solution doit être générique. Le tableau et l'ensemble de résultats ci-dessus n'étaient qu'un exemple.

Addenda

J'ai supprimé l'exigence que la solution soit non itérative. Bien que je préfère une telle solution, je pense que c'est une contrainte déraisonnable. Malheureusement, je ne peux utiliser aucune solution basée sur CLR; mais si vous souhaitez inclure une telle solution, n'hésitez pas à. Je ne l'accepterai probablement pas comme réponse cependant.

Le nombre de lignes de ma vraie table peut atteindre 5 millions, mais il y a des jours où le nombre de lignes ne sera "que" d'environ dix mille. En moyenne, il y a 8 RecordKeys par GroupKeyet 4 GroupKeys par RecordKey. J'imagine qu'une solution aura une complexité temporelle exponentielle, mais je suis néanmoins intéressé par une solution.

Il s'agit d'une solution T-SQL itérative pour la comparaison des performances.

Il suppose qu'une colonne supplémentaire peut être ajoutée à la table pour stocker la clé de super groupe et l'indexation peut être modifiée:

Installer

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 vous pouvez inverser l'ordre des clés de la clé primaire actuelle, l'index unique supplémentaire ne sera pas requis.

Contour

L'approche de cette solution est:

1. Définissez l'ID du super groupe sur 1
2. Rechercher la clé de groupe non traitée au numéro le plus bas
3. Si aucun n'a été trouvé, quittez
4. Définissez le super groupe pour toutes les lignes avec la clé de groupe actuelle
5. Définir le super groupe pour toutes les lignes liées aux lignes du groupe actuel
6. Répétez l'étape 5 jusqu'à ce qu'aucune ligne ne soit mise à jour
7. Incrémenter l'ID de super groupe actuel
8. Passez à l'étape 2

la mise en oeuvre

Commentaires en ligne:

-- 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 d'exécution

Pour la mise à jour clé:

Résultat

L'état final du tableau est:

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

Démo: db <> violon

Des tests de performance

En utilisant l'ensemble de données de test étendu fourni dans la réponse de Michael Green , les horaires sur mon ordinateur portable ^* sont:

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

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

Ce problème concerne les liens entre les éléments. Cela le place dans le domaine des graphiques et du traitement des graphiques. Plus précisément, l'ensemble de données forme un graphique et nous recherchons des composants de ce graphique. Cela peut être illustré par un tracé des données de l'échantillon de la question.

La question dit que nous pouvons suivre GroupKey ou RecordKey pour trouver d'autres lignes qui partagent cette valeur. Nous pouvons donc traiter les deux comme des sommets dans un graphique. La question continue pour expliquer comment les GroupKeys 1 à 3 ont la même SupergroupKey. Cela peut être vu comme le cluster à gauche rejoint par des lignes fines. L'image montre également les deux autres composants (SupergroupKey) formés par les données d'origine.

SQL Server a une certaine capacité de traitement graphique intégrée à T-SQL. À l'heure actuelle, il est cependant assez maigre et n'aide pas avec ce problème. SQL Server a également la possibilité d'appeler R et Python, ainsi que la suite riche et robuste de packages à leur disposition. Un tel est l' igraph . Il est écrit pour "une gestion rapide des grands graphes, avec des millions de sommets et d'arêtes ( lien )".

En utilisant R et igraph, j'ai pu traiter un million de lignes en 2 minutes 22 secondes dans les tests locaux ¹ . Voici comment il se compare à la meilleure solution actuelle:

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.

Lors du traitement de 1M de lignes, 1m40 a été utilisé pour charger et traiter le graphique et mettre à jour le tableau. Il a fallu 42 secondes pour remplir une table de résultats SSMS avec la sortie.

L'observation du gestionnaire de tâches pendant le traitement de 1 million de lignes suggère qu'il fallait environ 3 Go de mémoire de travail. C'était disponible sur ce système sans pagination.

Je peux confirmer l'évaluation par Ypercube de l'approche CTE récursive. Avec quelques centaines de clés d'enregistrement, il a consommé 100% du CPU et toute la RAM disponible. Finalement, tempdb est passé à plus de 80 Go et le SPID s'est écrasé.

J'ai utilisé la table de Paul avec la colonne SupergroupKey afin qu'il y ait une comparaison équitable entre les solutions.

Pour une raison quelconque, R s'est opposé à l'accent sur Poincaré. Le changer en un simple "e" lui a permis de s'exécuter. Je n'ai pas enquêté car ce n'est pas lié au problème actuel. Je suis sûr qu'il y a une solution.

Voici le code

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

C'est ce que fait le code R

• @input_data_1 est la façon dont SQL Server transfère les données d'une table au code R et les convertit en une trame de données R appelée InputDataSet.

• library(igraph) importe la bibliothèque dans l'environnement d'exécution R.

• df.g <- graph.data.frame(d = InputDataSet, directed = FALSE)charger les données dans un objet igraph. Il s'agit d'un graphique non orienté car nous pouvons suivre les liens d'un groupe à l'autre ou d'un enregistrement à un autre. InputDataSet est le nom par défaut de SQL Server pour l'ensemble de données envoyé à R.

• cpts <- components(df.g, mode = c("weak")) traiter le graphique pour trouver des sous-graphiques discrets (composants) et d'autres mesures.

• OutputDataSet <- data.frame(cpts$membership)SQL Server attend une trame de données à partir de R. Son nom par défaut est OutputDataSet. Les composants sont stockés dans un vecteur appelé "appartenance". Cette instruction traduit le vecteur en un bloc de données.

• OutputDataSet$VertexName <- V(df.g)$nameV () est un vecteur de sommets dans le graphique - une liste de GroupKeys et RecordKeys. Cela les copie dans le bloc de données de sortie, créant une nouvelle colonne appelée VertexName. Il s'agit de la clé utilisée pour correspondre à la table source pour la mise à jour de SupergroupKey.

Je ne suis pas un expert en R. Cela pourrait probablement être optimisé.

Données de test

Les données du PO ont été utilisées pour la validation. Pour les tests d'échelle, j'ai utilisé le script suivant.

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

Je viens juste de réaliser que j'ai obtenu les rapports dans le mauvais sens à partir de la définition de l'OP. Je ne pense pas que cela affectera les horaires. Les enregistrements et les groupes sont symétriques à ce processus. Pour l'algorithme, ce ne sont que des nœuds dans un graphique.

Lors des tests, les données formaient invariablement un seul composant. Je pense que cela est dû à la distribution uniforme des données. Si, au lieu du rapport statique 1: 8 codé en dur dans la routine de génération, j'avais permis au rapport de varier, il y aurait probablement eu d'autres composants.

¹ Spécifications de la machine: Microsoft SQL Server 2017 (RTM-CU12), Developer Edition (64 bits), Windows 10 Home. 16 Go de RAM, SSD, i7 hyperthreadé à 4 cœurs, 2,8 GHz nominal. Les tests étaient les seuls éléments exécutés à l'époque, à l'exception de l'activité normale du système (environ 4% du processeur).

Une méthode CTE récursive - qui risque d'être terriblement inefficace dans les grands tableaux:

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

Testé dans dbfiddle.uk