Lösung zum Zuweisen eindeutiger Werte zu Zeilen mit endlicher Zusammenarbeitsentfernung

Ich habe eine Tabelle, die mit dem folgenden Code erstellt und gefüllt werden kann:

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

Für alle Zeilen mit einer endlichen Kollaborationsentfernung, die auf einer RecordKeyanderen Zeile basiert , möchte ich einen eindeutigen Wert zuweisen. Es ist mir egal, wie oder welcher Datentyp der eindeutige Wert ist.

Mit der folgenden Abfrage kann eine korrekte Ergebnismenge generiert werden, die meinen Anforderungen entspricht:

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;

Um besser zu helfen, was ich frage, erkläre ich, warum GroupKeys 1–3 dasselbe haben SupergroupKey:

• GroupKey1 enthält den RecordKeyEuler, der wiederum in GroupKey2 enthalten ist; also müssen GroupKeys 1 und 2 dasselbe haben SupergroupKey.
• Da Gauß sowohl in GroupKeys 2 als auch in s 3 enthalten ist, müssen auch sie dasselbe haben SupergroupKey. Dies führt dazu, dass GroupKeys 1–3 dasselbe hat SupergroupKey.
• Da GroupKeys 1–3 keine RecordKeys mit den verbleibenden GroupKeys teilen , sind sie die einzigen, denen der SupergroupKeyWert 1 zugewiesen wurde .

Ich sollte hinzufügen, dass die Lösung generisch sein muss. Die obige Tabelle und Ergebnismenge war nur ein Beispiel.

Nachtrag

Ich habe die Anforderung entfernt, dass die Lösung nicht iterativ sein muss. Obwohl ich eine solche Lösung bevorzugen würde, glaube ich, dass dies eine unangemessene Einschränkung ist. Leider kann ich keine CLR-basierte Lösung verwenden. Wenn Sie jedoch eine solche Lösung einbeziehen möchten, können Sie dies gerne tun. Ich werde es wahrscheinlich nicht als Antwort akzeptieren.

Die Anzahl der Zeilen in meiner realen Tabelle beträgt 5 Millionen, aber es gibt Tage, an denen die Anzahl der Zeilen "nur" etwa zehntausend beträgt. Im Durchschnitt gibt es 8 RecordKeys pro GroupKeyund 4 GroupKeys pro RecordKey. Ich stelle mir vor, dass eine Lösung eine exponentielle zeitliche Komplexität haben wird, aber ich bin trotzdem an einer Lösung interessiert.

Dies ist eine iterative T-SQL-Lösung für den Leistungsvergleich.

Es wird davon ausgegangen, dass der Tabelle eine zusätzliche Spalte zum Speichern des Supergruppenschlüssels hinzugefügt und die Indizierung geändert werden kann:

Konfiguration

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

Wenn Sie die Schlüsselreihenfolge des aktuellen Primärschlüssels umkehren können, ist der zusätzliche eindeutige Index nicht erforderlich.

Gliederung

Der Ansatz dieser Lösung lautet:

1. Setzen Sie die Supergruppen-ID auf 1
2. Suchen Sie den unverarbeiteten Gruppenschlüssel mit der niedrigsten Nummer
3. Wenn keine gefunden wird, beenden Sie das Programm
4. Legen Sie die Supergruppe für alle Zeilen mit dem aktuellen Gruppenschlüssel fest
5. Legen Sie die Supergruppe für alle Zeilen fest, die sich auf Zeilen in der aktuellen Gruppe beziehen
6. Wiederholen Sie Schritt 5, bis keine Zeilen mehr aktualisiert werden
7. Inkrementieren Sie die aktuelle Supergruppen-ID
8. Weiter zu Schritt 2

Implementierung

Kommentare inline:

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

Ausführungsplan

Für das Schlüsselupdate:

Ergebnis

Der Endzustand der Tabelle ist:

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

Demo: db <> Geige

Leistungstests

Unter Verwendung des erweiterten Testdatensatzes in Michael Green's Antwort sind die Timings auf meinem Laptop ^* :

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

_{* Microsoft SQL Server 2017 (RTM-CU13), Developer Edition (64-Bit), Windows 10 Pro, 16 GB RAM, SSD, 4-Kern-Hyperthread-i7, nominal 2,4 GHz.}

Bei diesem Problem geht es darum, Verknüpfungen zwischen Elementen zu folgen. Dies versetzt es in den Bereich der Grafiken und der Grafikverarbeitung. Insbesondere bildet der gesamte Datensatz ein Diagramm, und wir suchen nach Komponenten dieses Diagramms. Dies kann durch eine grafische Darstellung der Beispieldaten aus der Frage veranschaulicht werden.

Die Frage besagt, dass wir GroupKey oder RecordKey folgen können, um andere Zeilen zu finden, die diesen Wert gemeinsam haben. Wir können also beide als Scheitelpunkte in einem Diagramm behandeln. In der Frage wird weiter erläutert, wie GroupKeys 1–3 denselben SupergroupKey haben. Dies kann als der Cluster auf der linken Seite gesehen werden, der durch dünne Linien verbunden ist. Das Bild zeigt auch die beiden anderen Komponenten (SupergroupKey), die aus den Originaldaten bestehen.

SQL Server verfügt über einige in T-SQL integrierte Grafikverarbeitungsfunktionen. Zu diesem Zeitpunkt ist es jedoch recht dürftig und bei diesem Problem nicht hilfreich. SQL Server kann auch R und Python sowie die umfangreiche und robuste Suite von Paketen aufrufen, die ihnen zur Verfügung stehen. Eines davon ist igraph . Es wurde für "schnelle Handhabung großer Graphen mit Millionen von Eckpunkten und Kanten ( Link )" geschrieben.

Mit R und igraph konnte ich in lokalen Tests ¹ eine Million Zeilen in 2 Minuten 22 Sekunden verarbeiten . So wird es mit der derzeit besten Lösung verglichen:

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.

Bei der Verarbeitung von 1 Million Zeilen wurden 1 bis 40 Sekunden verwendet, um das Diagramm zu laden und zu verarbeiten und die Tabelle zu aktualisieren. 42s waren erforderlich, um eine SSMS-Ergebnistabelle mit der Ausgabe zu füllen.

Die Beobachtung des Task-Managers während der Verarbeitung von 1 Million Zeilen lässt darauf schließen, dass etwa 3 GB Arbeitsspeicher erforderlich sind. Dies war auf diesem System ohne Paging verfügbar.

Ich kann Ypercubes Einschätzung des rekursiven CTE-Ansatzes bestätigen. Mit ein paar hundert Aufnahmetasten verbrauchte es 100% der CPU und den gesamten verfügbaren RAM. Schließlich wuchs die Tempdb auf über 80 GB und die SPID stürzte ab.

Ich habe Pauls Tabelle mit der SupergroupKey-Spalte verwendet, damit es einen fairen Vergleich zwischen den Lösungen gibt.

Aus irgendeinem Grund lehnte R den Akzent auf Poincaré ab. Durch Ändern in ein einfaches "e" konnte es ausgeführt werden. Ich habe nicht nachgeforscht, da es für das vorliegende Problem nicht relevant ist. Ich bin sicher, es gibt eine Lösung.

Hier ist der 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);

Dies ist, was der R-Code tut

• @input_data_1 Auf diese Weise überträgt SQL Server Daten aus einer Tabelle in R-Code und übersetzt sie in einen R-Datenrahmen namens InputDataSet.

• library(igraph) Importiert die Bibliothek in die R-Ausführungsumgebung.

• df.g <- graph.data.frame(d = InputDataSet, directed = FALSE)Laden Sie die Daten in ein igraph-Objekt. Dies ist ein ungerichteter Graph, da wir Links von Gruppe zu Datensatz oder von Datensatz zu Gruppe folgen können. InputDataSet ist der Standardname von SQL Server für das an R gesendete Dataset.

• cpts <- components(df.g, mode = c("weak")) Verarbeiten Sie das Diagramm, um diskrete Unterdiagramme (Komponenten) und andere Kennzahlen zu finden.

• OutputDataSet <- data.frame(cpts$membership)SQL Server erwartet einen Datenrahmen von R. Der Standardname lautet OutputDataSet. Die Komponenten werden in einem Vektor gespeichert, der als "Mitgliedschaft" bezeichnet wird. Diese Anweisung übersetzt den Vektor in einen Datenrahmen.

• OutputDataSet$VertexName <- V(df.g)$nameV () ist ein Vektor von Eckpunkten im Diagramm - eine Liste von GroupKeys und RecordKeys. Dadurch werden sie in den Ausgangsdatenrahmen kopiert und eine neue Spalte mit dem Namen VertexName erstellt. Dies ist der Schlüssel, der zum Abgleichen mit der Quelltabelle zum Aktualisieren von SupergroupKey verwendet wird.

Ich bin kein R-Experte. Wahrscheinlich könnte dies optimiert werden.

Testdaten

Die Daten des OP wurden zur Validierung verwendet. Für Skalentests habe ich das folgende Skript verwendet.

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

Ich habe gerade festgestellt, dass ich die Verhältnisse aus der OP-Definition falsch herum ermittelt habe. Ich glaube nicht, dass dies das Timing beeinflussen wird. Datensätze und Gruppen sind für diesen Prozess symmetrisch. Für den Algorithmus sind sie alle nur Knoten in einem Diagramm.

Beim Testen bildeten die Daten immer eine einzelne Komponente. Ich glaube, das liegt an der gleichmäßigen Verteilung der Daten. Wenn ich anstelle des statischen 1: 8-Verhältnisses, das in der Generierungsroutine fest codiert ist, zugelassen hätte, dass das Verhältnis variiert, hätte es wahrscheinlich weitere Komponenten gegeben.

¹ Computerspezifikation: Microsoft SQL Server 2017 (RTM-CU12), Developer Edition (64-Bit), Windows 10 Home. 16 GB RAM, SSD, 4-Kern-Hyperthread-i7, nominal 2,8 GHz. Abgesehen von der normalen Systemaktivität (ca. 4% CPU) waren die Tests die einzigen Elemente, die zu diesem Zeitpunkt ausgeführt wurden.

Eine rekursive CTE-Methode - die in großen Tabellen wahrscheinlich schrecklich ineffizient ist:

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

Getestet in dbfiddle.uk