SQLを用いて同一ユーザーのIDを紐付けしてIDを振るロジックに悩んでいます

Question

複数システムのそれぞれ独自のユーザーIDに対して、同一ユーザーのIDを紐付けるためのユニークIDを振りたいと考えています。
SQLでどのようなロジックにすれば良いか、頭を悩ませておりまして、助言いただけませんでしょうか。

同一ユーザーを紐付けたテーブルはあります。これを元に「同一ユーザーを区別するための」ユニークIDを振りたいです。
複数システムの同一ユーザーを紐付けるため、3システム以上にまたがるユーザーに、同一IDを振る点が難しいです。。。

・処理はSQLで実行します。（BigQueryのため、ある程度重い処理になっても問題はありません。なお、標準のSQLとほぼ同じなので、標準のSQLで考えていただいて大丈夫です）
・SQLの実行自体は別のプログラムで行うため、複数SQLを順序立てて実行することが可能です。ただしデータ件数が多いため、プログラム側にSELECTでデータを取ってきて処理を行うことは難しいです。(システムID一覧であれば件数が小さいので取得可能です)
・対象のシステムは百近くあるため、「まず２つのシステム分のデータだけを抜き出して紐付けをして・・・」の繰り返しだと5千ループくらい必要なため厳しいです。
　（ループがどうしても必要なら、せめてシステムの数＝百回ですむようにしたい）
・2つのシステムで、ユーザーは1対1で紐付きます。(紐付かないユーザーもありますが、1対多はありません)
・列[システムID1]と[システムID2]の値は、文字列で見た時に[システムID1]＜[システムID2]となっています(つまり、2つのシステムがあった時、どちらが[システムID1][システムID2]になるかは決まっている)
・BigQueryの特性上、UPDATE文、INSERT文、DELETE文は制限されており、使用は避けたいです
・中間テーブルの作成は可能です
・window関数も使用できます
・全てのひも付きが元デーブルに存在するわけではなく、複数行をたどって分かるひも付きもあります
　(下の例でいうと、3行目と5行目からA005＝B021、B021＝C101と分かりますが、A005＝C101となる行は元テーブルにはありません)　※追記しました

元テーブルの列
[システムID１，ユーザーID１，システムID２，ユーザーID２]

元テーブルの値の例　※行は何千万とあります
sys01, A001, sys02, B002
sys01, A003, sys02, B011
sys01, A005, sys02, B021
sys02, B001, sys03, C050
sys02, B021, sys03, C101
sys01, A001, sys03, C102
sys01, A003, sys03, C111
↑たとえば、A005＝B021＝C101なので、この3つには同じユニークIDを振りたい

作りたいテーブル
[システムID，ユーザーID, ユニークID]
sys01, A001, 0001
sys01, A003, 0002
sys01, A005, 0003
sys02, B002, 0001
sys02, B001, 0004 
sys02, B011, 0002
sys02, B021, 0005
sys03, C101, 0003
・・・

どうぞよろしくお願いいたします。

Accepted Answer

各ノードの情報と経路の起点となる情報を求めて、経路の起点に対してナンバリングします。
再帰を使用せずに行う場合、予めノードの深さ分の処理を記述する必要があります。

【解説】
ノード１は経路の先頭（ほかのデータからの参照が無い）である事を条件にし、その経路の先頭の情報を各ノードでは引継ぎます。
次に、ナンバリングの為に経路の先頭に対し情報を配列化(**array_agg**)し畳みます。
上記で畳んだ情報に対してナンバリングし、最後に配列を展開(**unnest**)します。
※質問のデータでは、３階層までですが、サンプル的に階層４までにしています
※複数の**unnest**で展開できるかは確認してないので、駄目な様なら、結合したもので**array_agg**して、展開後に分解して下さい。
※このselect文を元に**create table**や **insert** するなりして下さい。
```SQL
with node1 as (-- ノード1と経路起点の情報
        select システムID1 as node_key1, ユーザーID1 as node_key2
             , システムID1 システムID, ユーザーID1 as ユーザーID
        from tbl t
        where not exists(
                select 1 from tbl 
                where システムID2=t.システムID1 and ユーザーID2=t.ユーザーID1
              ) 
        group by システムID1, ユーザーID1
), node2 as (
    select n1.node_key1, n1.node_key2
         , n2.システムID2 as システムID, n2.ユーザーID2 as ユーザーID
    from  node1 n1 inner join tbl n2
          on    n1.システムID=n2.システムID1 and n1.ユーザーID=n2.ユーザーID1
), node3 as (
    select n2.node_key1, n2.node_key2
         , n3.システムID2 as システムID, n3.ユーザーID2 as ユーザーID
    from  node2 n2 inner join tbl n3
          on    n2.システムID=n3.システムID1 and n2.ユーザーID=n3.ユーザーID1
), node4 as (
    select n3.node_key1, n3.node_key2
         , n4.システムID2 as システムID, n4.ユーザーID2 as ユーザーID
    from  node3 n3 inner join tbl n4
          on    n3.システムID=n4.システムID1 and n3.ユーザーID=n4.ユーザーID1
), mrg as (
    select node_key1, node_key2
         , array_agg(システムID) システムIDリスト
         , array_agg(ユーザーID) ユーザーIDリスト
    from (
                  select * from node1
        union all select * from node2
        union all select * from node3
        union all select * from node4
    ) mrg
    group by node_key1, node_key2
), nmbr as (
    select *, row_number() over(order by node_key1, node_key2) as ユニークID
    from mrg
)
select unnest(システムIDリスト) システムID, unnest(ユーザーIDリスト) ユーザーID, ユニークID
from nmbr
```
ノードの深さ（最大で幾つのシステム跨るか）がどれ位なのか分かりませんが、多くなれば記述は冗長になりますが、敢えて再帰処理を作成して行うかどうかですね。

一応以下に参考になりそうなものをリンクしておきます
[経理処理の定式化とその実装、もしくはBigQueryにおける再帰](https://moneyforward.com/engineers_blog/2019/06/03/business-analysis/)

追記
--
ノード１時点でユニークIDを求めておけば、配列操作は不要だったので、追記。
```SQL
with node1 as (-- ノード1と経路起点の情報
      select *, row_number() over(order by システムID, ユーザーID) as ユニークID
      from (
        select システムID1 システムID, ユーザーID1 as ユーザーID
        from tbl t
        where not exists(
                select 1 from tbl 
                where システムID2=t.システムID1 and ユーザーID2=t.ユーザーID1
              ) 
        group by システムID1, ユーザーID1
      ) t
), node2 as (
    select n2.システムID2 as システムID, n2.ユーザーID2 as ユーザーID, n1.ユニークID
    from  node1 n1 inner join tbl n2
          on    n1.システムID=n2.システムID1 and n1.ユーザーID=n2.ユーザーID1
), node3 as (
    select n3.システムID2 as システムID, n3.ユーザーID2 as ユーザーID, n2.ユニークID
    from  node2 n2 inner join tbl n3
          on    n2.システムID=n3.システムID1 and n2.ユーザーID=n3.ユーザーID1
), node4 as (
    select n4.システムID2 as システムID, n4.ユーザーID2 as ユーザーID, n3.ユニークID
    from  node3 n3 inner join tbl n4
          on    n3.システムID=n4.システムID1 and n3.ユーザーID=n4.ユーザーID1
)
          select * from node1
union all select * from node2
union all select * from node3
union all select * from node4
```

Answer

以下のような深さ優先探索のロジックをSQLバッチで組めば、やりたいことを実現できると思います。ただしSQLはシステムIDの数の2乗回程度発行される可能性があります。

① 「作りたいテーブル」としてdstテーブルを作成する (ここではdstテーブル)

```sql
CREATE TABLE dst (
  systemid char(5),
  userid   char(5),
  uniqid integer,
  PRIMARY KEY(systemid, userid)
);
```

② 頂点どうしの紐づき関係を示すedgeテーブルを作成する。

```sql
CREATE TABLE edge (
  systemid1 char(5),
  userid1   char(5),
  systemid2 char(5),
  userid2   char(5)
);
INSERT INTO edge 
SELECT systemid1, userid1, systemid2, userid2 FROM src
UNION ALL
SELECT systemid2, userid2, systemid1, userid1 FROM src;
```

③ 根ノードとなるデータをdstテーブルに投入する。

```sql
SELECT DISTINCT 
  systemid1, 
  userid1, 
  DENSE_RANK() OVER (ORDER BY userid1) + COALESCE((SELECT MAX(uniqid) FROM dst), 0)
FROM edge E
WHERE systemid1 = 'sys01'
AND NOT EXISTS (
  SELECT *
  FROM dst D
  WHERE E.systemid1 = D.systemid
  AND E.userid1 = D.userid
);
```

④ dstテーブルの件数が増えなくなるまで以下のクエリを発行する。

```sql
INSERT INTO dst
SELECT DISTINCT E.systemid2, E.userid2, D1.uniqid
FROM edge E
JOIN dst D1 ON E.systemid1 = D1.systemid AND E.userid1 = D1.userid
WHERE NOT EXISTS (
  SELECT *
  FROM dst D2
  WHERE D2.systemid = E.systemid2
  AND D2.userid = E.userid2
);
```

⑤ ③のクエリを'sys02'に変えて実行したあと、④のクエリをdstテーブルの件数が増えなくなるまで発行する。

⑥ ⑤をすべてのsystemidで実行する。このときsystemidの昇順で実行していくこと。

---

個人的な経験で恐縮ですが、データ量が多いと、データ間に不整合や不備が発生していることが多いです。
SQLバッチだと、そのような異常データのハンドリングが難しいため、
SQLで処理するよりも、データをすべてファイルにダンプするなどして、
それを何かしらのプログラミング言語などで処理するほうがよいように思います。

追記

関連した質問