Rozwiązanie do przypisywania unikalnych wartości do wierszy o skończonej odległości współpracy

Mam tabelę, którą można utworzyć i wypełnić następującym kodem:

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

Dla wszystkich wierszy, które mają skończoną odległość współpracy w oparciu RecordKeyo inny wiersz, chciałbym przypisać unikalną wartość - nie obchodzi mnie, w jaki sposób lub jaki typ danych jest unikalną wartością.

Prawidłowy zestaw wyników, który spełnia to, o co proszę, można wygenerować za pomocą następującego zapytania:

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;

Aby lepiej pomóc w pytaniu, wyjaśnię, dlaczego GroupKeys 1–3 mają to samo SupergroupKey:

• GroupKey1 zawiera RecordKeyEuler, który z kolei jest zawarty w GroupKey2; zatem GroupKeys 1 i 2 muszą mieć to samo SupergroupKey.
• Ponieważ Gauss jest zawarty zarówno w GroupKeys 2, jak i 3, one również muszą mieć to samo SupergroupKey. Prowadzi to do tego, że GroupKeys 1–3 ma to samo SupergroupKey.
• Ponieważ GroupKeys 1–3 nie dzielą żadnych RecordKeyz pozostałymi GroupKey, są one jedynymi, którym przypisano SupergroupKeywartość 1.

Powinienem dodać, że rozwiązanie musi być ogólne. Powyższa tabela i zestaw wyników były jedynie przykładem.

Uzupełnienie

Usunąłem wymóg, aby rozwiązanie nie było iteracyjne. Chociaż wolałbym takie rozwiązanie, uważam, że jest to nieuzasadnione ograniczenie. Niestety nie mogę użyć żadnego rozwiązania opartego na CLR; ale jeśli chcesz dołączyć takie rozwiązanie, nie krępuj się. Prawdopodobnie jednak nie zaakceptuję tego jako odpowiedzi.

Liczba wierszy w mojej prawdziwej tabeli wynosi aż 5 milionów, ale są dni, kiedy liczba wierszy będzie „tylko” około dziesięciu tysięcy. Średnio jest 8 RecordKeys na GroupKeyi 4 GroupKeys na RecordKey. Wyobrażam sobie, że rozwiązanie będzie miało wykładniczą złożoność czasową, ale mimo to interesuje mnie rozwiązanie.

Jest to iteracyjne rozwiązanie T-SQL do porównywania wydajności.

Zakłada się, że do tabeli można dodać dodatkową kolumnę, aby przechowywać klucz super grupy, a indeksowanie można zmienić:

Ustawiać

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

Jeśli możesz odwrócić kolejność kluczy obecnego klucza podstawowego, dodatkowy unikalny indeks nie będzie wymagany.

Zarys

Podejście tego rozwiązania jest następujące:

1. Ustaw identyfikator super grupy na 1
2. Znajdź nieprzetworzony klucz grupy o najniższym numerze
3. Jeśli nie znaleziono, wyjdź
4. Ustaw super grupę dla wszystkich wierszy za pomocą bieżącego klucza grupy
5. Ustaw super grupę dla wszystkich wierszy powiązanych z wierszami w bieżącej grupie
6. Powtarzaj krok 5, aż żadne wiersze nie zostaną zaktualizowane
7. Zwiększ bieżący identyfikator super grupy
8. Przejdź do kroku 2

Realizacja

Komentarze w tekście:

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

W przypadku aktualizacji klucza:

Wynik

Ostateczny stan tabeli to:

╔═══════════════╦══════════╦══════════════╗
║ 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: skrzypce db <>

Testy wydajności

Korzystanie z rozszerzonego zestawu danych testu przewidzianego w Michaela Greena odpowiedź , czasy na moim laptopie ^* to:

╔═════════════╦════════╗
║ 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-rdzeniowy hyperthreaded i7, 2,4 GHz}

Ten problem dotyczy podążania za linkami między elementami. To umieszcza go w dziedzinie grafów i przetwarzania grafów. W szczególności cały zestaw danych tworzy wykres i szukamy składników tego wykresu. Można to zilustrować wykresem przykładowych danych z pytania.

Pytanie mówi, że możemy śledzić GroupKey lub RecordKey, aby znaleźć inne wiersze o tej samej wartości. Możemy więc traktować oba jako wierzchołki na wykresie. Pytanie wyjaśnia, w jaki sposób GroupKeys 1–3 mają ten sam SupergroupKey. Można to postrzegać jako skupisko po lewej połączone cienkimi liniami. Zdjęcie pokazuje również dwa inne komponenty (SupergroupKey) utworzone przez oryginalne dane.

SQL Server ma wbudowane możliwości przetwarzania grafów w T-SQL. W tej chwili jest to jednak dość skąpe i nie pomaga w rozwiązaniu tego problemu. SQL Server ma również możliwość wywoływania R i Pythona oraz bogatego i solidnego pakietu dostępnych dla nich pakietów. Jednym z nich jest Igraph . Jest napisany z myślą o „szybkiej obsłudze dużych wykresów z milionami wierzchołków i krawędzi ( link )”.

Używając R i igraph byłem w stanie przetworzyć milion wierszy w ciągu 2 minut 22 sekund w testach lokalnych ¹ . Oto porównanie z obecnym najlepszym rozwiązaniem:

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.

Podczas przetwarzania 1M wierszy zastosowano 1m40s do załadowania i przetworzenia wykresu oraz do aktualizacji tabeli. 42s były wymagane do zapełnienia tabeli wyników SSMS danymi wyjściowymi.

Obserwacja Menedżera zadań podczas przetwarzania 1M wierszy sugeruje, że wymagane było około 3 GB pamięci roboczej. To było dostępne w tym systemie bez stronicowania.

Mogę potwierdzić ocenę Ypercube dotyczącą rekurencyjnego podejścia CTE. Przy kilkuset kluczach zapisu zużywał 100% procesora i całą dostępną pamięć RAM. Ostatecznie tempdb wzrosło do ponad 80 GB i SPID się zawiesił.

Użyłem tabeli Paula z kolumną SupergroupKey, więc istnieje sprawiedliwe porównanie między rozwiązaniami.

Z jakiegoś powodu R sprzeciwił się akcentowi na Poincaré. Zmiana na zwykłe „e” pozwoliła na uruchomienie. Nie badałem, ponieważ nie ma on istotnego wpływu na omawiany problem. Jestem pewien, że istnieje rozwiązanie.

Oto kod

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

Tak właśnie działa kod R.

• @input_data_1 jest to, w jaki sposób SQL Server przesyła dane z tabeli do kodu R i tłumaczy je na ramkę danych R o nazwie InputDataSet.

• library(igraph) importuje bibliotekę do środowiska wykonawczego R.

• df.g <- graph.data.frame(d = InputDataSet, directed = FALSE)załadować dane do obiektu igraph. To jest nieukierunkowany wykres, ponieważ możemy podążać za linkami z grupy do zapisu lub zapisu do grupy. InputDataSet to domyślna nazwa programu SQL Server dla zestawu danych wysłanego do R.

• cpts <- components(df.g, mode = c("weak")) przetwarza wykres, aby znaleźć dyskretne podgrupy (komponenty) i inne miary.

• OutputDataSet <- data.frame(cpts$membership)SQL Server oczekuje ramki danych z powrotem od R. Jego domyślna nazwa to OutputDataSet. Komponenty są przechowywane w wektorze zwanym „członkostwem”. Ta instrukcja przekształca wektor w ramkę danych.

• OutputDataSet$VertexName <- V(df.g)$nameV () to wektor wierzchołków na wykresie - lista kluczy GroupKeys i RecordKeys. Spowoduje to skopiowanie ich do ramki danych wyjściowych, tworząc nową kolumnę o nazwie VertexName. Jest to klucz używany do dopasowania do tabeli źródłowej do aktualizacji SupergroupKey.

Nie jestem ekspertem od R. Prawdopodobnie można to zoptymalizować.

Dane testowe

Dane PO zostały wykorzystane do walidacji. Do testów skali użyłem następującego skryptu.

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

Właśnie zdałem sobie sprawę, że źle zrozumiałem współczynniki z definicji PO. Nie wierzę, że wpłynie to na czasy. Rekordy i grupy są symetryczne dla tego procesu. Według algorytmu wszystkie są tylko węzłami na wykresie.

Podczas testowania dane niezmiennie tworzyły pojedynczy komponent. Uważam, że jest to spowodowane jednolitym rozkładem danych. Gdyby zamiast statycznego stosunku 1: 8 zakodowanego na stałe w procedurze generowania pozwoliłbym na zmianę tego stosunku , bardziej prawdopodobne byłyby dalsze elementy.

¹ Specyfikacja komputera: Microsoft SQL Server 2017 (RTM-CU12), Developer Edition (64-bit), Windows 10 Home. 16 GB pamięci RAM, dysk SSD, 4-rdzeniowy hyperthreaded i7, 2,8 GHz nominalnie. Testy były jedynymi działającymi w tym czasie elementami, innymi niż normalna aktywność systemu (około 4% procesora).

Rekurencyjna metoda CTE - która może być okropnie nieefektywna w dużych tabelach:

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

Testowany w dbfiddle.uk