Solution to assigning unique values to rows with finite collaboration distance I have a table that can be created and populated with the following code:

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


For all rows that have a finite collaboration distance based on RecordKey with another row, I would like to assign a unique value—I don't care how or what data type the unique value is.

A correct result set that meets what I'm asking for can be generated with the following query:

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;


To better aid what I'm asking, I'll explain why GroupKeys 1–3 have the same SupergroupKey:


GroupKey 1 contains the RecordKey Euler which in turn is contained in GroupKey 2; thus GroupKeys 1 and 2 must have the same SupergroupKey. 
Because Gauss is contained in both GroupKeys 2 and 3, they too must have the same SupergroupKey. This leads to GroupKeys 1–3 having the same SupergroupKey. 
Since GroupKeys 1–3 don't share any RecordKeys with the remaining GroupKeys, they are the only ones assigned a SupergroupKey value of 1.


I should add that the solution needs to be generic. The above table and result set was merely an example.

Addendum

I removed the requirement for the solution to be non-iterative. While I would prefer such a solution, I believe it's an unreasonable constraint. Unfortunately, I am unable to use any CLR-based solution; but if you want to include such a solution, feel free to. I will likely not accept it as an answer though.

The number of rows in my real table is as large as 5 million, but there are days when the number of rows will "only" be around ten thousand. On average there are 8 RecordKeys per GroupKey and 4 GroupKeys per RecordKey. I imagine that a solution will have exponential time complexity, but I am interested in a solution nonetheless.
This problem is about following links between items. This puts it in the realm of graphs and graph processing. Specifically, the whole dataset forms a graph and we are looking for components of that graph. This can be illustrated by a plot of the sample data from the question.



The question says we can follow GroupKey or RecordKey to find other rows that share that value. So we can treat both as vertexes in a graph. The question goes on to explain how  GroupKeys 1–3 have the same SupergroupKey. This can be seen as the cluster on the left joined by thin lines. The picture also shows the two other components (SupergroupKey) formed by the original data. 

SQL Server has some graph processing ability built into T-SQL. At this time it is quite meagre, however, and not helpful with this problem. SQL Server also has the ability to call out to R and Python, and the rich &amp; robust suite of packages available to them. One such is igraph. It is written for "fast handling of large graphs, with millions of vertices and edges(link)."

Using R and igraph I was able to process one million rows in 2 minutes 22 seconds in local testing1. This is how it compares against the current best solution:

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.


When processing 1M rows, 1m40s were used to  load &amp; process the graph, and to update the table. 42s were required to populate an SSMS result table with the output.

Observation of Task Manager while 1M rows were processed suggest about 3GB of working memory were required. This was available on this system without paging.

I can confirm Ypercube's assessment of the recursive CTE approach. With a few hundred record keys it consumed 100% of CPU and all available RAM. Eventually tempdb grew to over 80GB and the SPID crashed.

I used Paul's table with the SupergroupKey column so there's a fair comparison between the solutions.

For some reason R objected to the accent on Poincaré. Changing it to a plain "e" allowed it to run. I didn't investigate since it's not germane to the problem at hand. I'm sure there's a solution.

Here is the 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 &lt;- graph.data.frame(d = InputDataSet, directed = FALSE)
cpts &lt;- components(df.g, mode = c("weak"))
OutputDataSet &lt;- data.frame(cpts$membership)
OutputDataSet$VertexName &lt;- 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);



This is what the R code does  


@input_data_1 is how SQL Server transfers data from a table to R code and translates it to an R dataframe called InputDataSet.
library(igraph) imports the library into the R execution environment.
df.g &lt;- graph.data.frame(d = InputDataSet, directed = FALSE) load the data into an igraph object. This is an undirected graph since we can follow links from group to record or record to group. InputDataSet is SQL Server's default name for the dataset sent to R.
cpts &lt;- components(df.g, mode = c("weak")) process the graph to find discrete sub-graphs (components) and other measures.
OutputDataSet &lt;- data.frame(cpts$membership) SQL Server expects a data frame back from R. Its default name is OutputDataSet. The components are stored in a vector called "membership". This statement translates the vector to a data frame.
OutputDataSet$VertexName &lt;- V(df.g)$name V() is a vector of vertices in the graph - a list of GroupKeys and RecordKeys. This copies them into the ouput data frame, creating a new column called VertexName. This is the key used to match to the source table for updating SupergroupKey.


I'm not an R expert. Likely this could be optimised.

Test Data

The OP's data was used for validation. For scale tests I used the following 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 &lt; @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 &gt; @RecordKey 
order by RecordKey;

while @@ROWCOUNT &gt; 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 &gt; @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);



I've just now realised I've gotten the ratios the wrong way around from the OP's definition. I don't believe this will affect the timings. Records &amp; Groups are symmetrical to this process. To the algorithm they're all just nodes in a graph.

In testing the data invariably formed a single component. I believe this is due to the uniform distribution of the data. If instead of the static 1:8 ratio hard-coded into the generation routine I had allowed the ratio to vary there would more likely have been further components.


1 Machine spec: Microsoft SQL Server 2017 (RTM-CU12), Developer Edition (64-bit), Windows 10 Home. 16GB RAM, SSD, 4 core hyperthreaded i7, 2.8GHz nominal. The tests were the only items running at the time, other than normal system activity (about 4% CPU).