Решение для присвоения уникальных значений строкам с конечным расстоянием сотрудничества

У меня есть таблица, которую можно создать и заполнить следующим кодом:

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

Для всех строк с конечным расстоянием сотрудничества, основанным на RecordKeyдругой строке, я хотел бы назначить уникальное значение - мне все равно, каким образом или каким типом данных является уникальное значение.

Правильный набор результатов, который соответствует тому, что я запрашиваю, может быть создан с помощью следующего запроса:

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;

Чтобы лучше понять то, что я прошу, я объясню, почему GroupKeyс 1 по 3 имеют то же самое SupergroupKey:

• GroupKey1 содержит RecordKeyэйлер, который в свою очередь содержится в GroupKey2; таким образом, GroupKeys 1 и 2 должны иметь одинаковые значения SupergroupKey.
• Поскольку гаусс содержится как в GroupKeys 2, так и в 3, они тоже должны быть одинаковыми SupergroupKey. Это приводит к тому, что GroupKeys 1–3 будут одинаковыми SupergroupKey.
• Поскольку GroupKeys 1–3 не делят RecordKeys с остальными GroupKeys, они единственные, которым присвоено SupergroupKeyзначение 1.

Я должен добавить, что решение должно быть общим. Приведенная выше таблица и набор результатов были просто примером.

добавление

Я убрал требование, чтобы решение было не итеративным. Хотя я бы предпочел такое решение, я считаю, что это неразумное ограничение. К сожалению, я не могу использовать какое-либо решение на основе CLR; но если вы хотите включить такое решение, не стесняйтесь. Я скорее всего не приму это как ответ.

Количество строк в моей реальной таблице достигает 5 миллионов, но бывают дни, когда число строк «всего» будет около десяти тысяч. В среднем 8 RecordKeyс GroupKeyи 4 GroupKeyс RecordKey. Я полагаю, что решение будет иметь экспоненциальную временную сложность, но, тем не менее, я заинтересован в решении.

Это итеративное решение T-SQL для сравнения производительности.

Предполагается, что в таблицу можно добавить дополнительный столбец для хранения ключа супергруппы, а индексирование можно изменить:

Настроить

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

Если вы можете изменить порядок ключей текущего первичного ключа, дополнительный уникальный индекс не потребуется.

Контур

Подход этого решения:

1. Установите идентификатор супер группы на 1
2. Найти необработанный групповой ключ с наименьшим номером
3. Если ничего не найдено, выйдите
4. Установите супер группу для всех строк с текущим групповым ключом
5. Установите супер группу для всех строк, связанных со строками в текущей группе
6. Повторяйте шаг 5, пока строки не будут обновлены
7. Увеличить текущий идентификатор супергруппы
8. Перейти к шагу 2

Реализация

Встроенные комментарии:

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

План выполнения

Для обновления ключа:

Результат

Конечное состояние таблицы:

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

Демо: db <> скрипка

Тесты производительности

Используя расширенный набор тестовых данных, представленный в ответе Майкла Грина , время на моем ноутбуке ^* :

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

_{* Microsoft SQL Server 2017 (RTM-CU13), Developer Edition (64-разрядная версия), Windows 10 Pro, 16 ГБ ОЗУ, SSD, 4-ядерный Hyper-Threading i7, номинал 2,4 ГГц.}

Эта проблема касается следующих ссылок между элементами. Это помещает это в область графов и обработки графов. В частности, весь набор данных образует граф, и мы ищем компоненты этого графа. Это может быть проиллюстрировано графиком выборки данных из вопроса.

Вопрос говорит, что мы можем следовать GroupKey или RecordKey, чтобы найти другие строки, которые разделяют это значение. Таким образом, мы можем рассматривать обе вершины графа. Этот вопрос объясняет, почему у GroupKeys 1–3 одинаковый SupergroupKey. Это можно увидеть как кластер слева, соединенный тонкими линиями. На рисунке также показаны два других компонента (SupergroupKey), сформированные из исходных данных.

SQL Server имеет некоторые возможности обработки графиков, встроенные в T-SQL. В настоящее время это довольно скудно, но не помогает с этой проблемой. SQL Server также имеет возможность обращаться к R и Python, а также к богатому и надежному набору пакетов, доступных для них. Одним из таких является igraph . Он написан для «быстрой обработки больших графов с миллионами вершин и ребер ( ссылка )».

Используя R и igraph, я смог обработать миллион строк за 2 минуты 22 секунды в локальном тестировании ¹ . Вот как он сравнивается с текущим лучшим решением:

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.

При обработке 1М строк 1м40 использовались для загрузки и обработки графика, а также для обновления таблицы. 42 были обязаны заполнить таблицу результатов SSMS с выводом.

Наблюдение за диспетчером задач при обработке 1М строк позволяет предположить, что требовалось около 3 ГБ рабочей памяти. Это было доступно в этой системе без подкачки страниц.

Я могу подтвердить оценку Ypercube рекурсивного подхода CTE. С несколькими сотнями ключей записи он потребляет 100% процессорного времени и всей доступной оперативной памяти. В конце концов, tempdb выросла до 80 ГБ, и SPID потерпел крах.

Я использовал таблицу Пола со столбцом SupergroupKey, чтобы было справедливое сравнение между решениями.

По какой-то причине Р. возражал против акцента на Пуанкаре. Изменение его на обычное «е» позволило ему работать. Я не расследовал, так как это не относится к рассматриваемой проблеме. Я уверен, что есть решение.

Вот код

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

Это то, что делает код R

• @input_data_1 это то, как SQL Server передает данные из таблицы в код R и переводит их в кадр данных R с именем InputDataSet.

• library(igraph) импортирует библиотеку в среду выполнения R.

• df.g <- graph.data.frame(d = InputDataSet, directed = FALSE)загрузить данные в объект igraph. Это неориентированный график, поскольку мы можем переходить по ссылкам от группы к записи или записи к группе. InputDataSet - это имя SQL Server по умолчанию для набора данных, отправляемого в R.

• cpts <- components(df.g, mode = c("weak")) обработать график, чтобы найти дискретные подграфы (компоненты) и другие меры.

• OutputDataSet <- data.frame(cpts$membership)SQL Server ожидает фрейм данных от R. Его имя по умолчанию - OutputDataSet. Компоненты хранятся в векторе, называемом «членство». Этот оператор переводит вектор во фрейм данных.

• OutputDataSet$VertexName <- V(df.g)$nameV () - это вектор вершин графа - список GroupKeys и RecordKeys. Это копирует их в выходной фрейм данных, создавая новый столбец с именем VertexName. Этот ключ используется для сопоставления с исходной таблицей для обновления SupergroupKey.

Я не эксперт по R Скорее всего, это можно оптимизировать.

Тестовые данные

Данные ОП были использованы для проверки. Для масштабных тестов я использовал следующий скрипт.

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

Я только сейчас понял, что неправильно понял соотношения из определения ОП. Я не верю, что это повлияет на время. Записи и группы симметричны этому процессу. По алгоритму они все просто узлы на графике.

При тестировании данных неизменно формируется единый компонент. Я считаю, что это связано с равномерным распределением данных. Если бы вместо статического соотношения 1: 8, жестко запрограммированного в процедуру генерации, я бы позволил этому соотношению изменяться , скорее всего, были бы дополнительные компоненты.

¹ Спецификация машины: Microsoft SQL Server 2017 (RTM-CU12), Developer Edition (64-разрядная версия), Windows 10 Home. 16 ГБ ОЗУ, твердотельный накопитель, 4-ядерный Hyper-Threading i7, номинал 2,8 ГГц. Тесты были единственными элементами, запущенными в то время, кроме нормальной системной активности (около 4% ЦП).

Рекурсивный метод CTE - который, вероятно, будет ужасно неэффективным в больших таблицах:

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

Протестировано в dbfiddle.uk