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

どうぞよろしくお願いいたします。

Comments

[takasima20]

なんでユニークIDをふりなおしたいのかな?

[TeSe]

ご質問ありがとうございます。
ユニークIDをふれば、そのIDで検索することで全ての紐づくシステムIDとユーザーIDを取得できるためです。
例に上げたテーブルの場合、「sys01, A005」＝「sys03, C101」であることがすぐには分かりません(間にB021を挟んでいるため)。順に検索していけばいつかたどり着きますが、何度もこのテーブルに対する検索を繰り返す必要があります。

[sazi]

この作りたいテーブルは一度作成すれば良いものですか？
再帰を使用すればループなどは使用しなくて出来そうですけど、bigqueryには再帰は実装されていないので、例えばデータをpostgresなどに投入してデータ作成し、そのデータをbigqueryに投入する方法もあります。
bigqueryで再帰を実現しようとするとストアドファンクションで実装する事になるので、面倒そうですが。

[sazi]

再帰使わないなら、システムにまたがっているユーザーの最大システム数ネストさせれば同じことは出来そうですけど。

[TeSe]

＞saziさん
ご質問ありがとうございます。
はい、テーブルは一度作成すれば良いものです。正確には元データに変更があるため日次で作成しますが、その都度、新規テーブルを作成します。
再帰を利用する方法ですか！良ければ具体的なやり方を教えていただけませんか？
環境とデータ数の観点から、BigQueryから別DBにデータを移動させて処理を行うのは難しいのですが、ご教授いただいた方法に工夫を加えたり、何かを妥協するなどして、本課題に適用できないか考えたいです。

Answer 1

各ノードの情報と経路の起点となる情報を求めて、経路の起点に対してナンバリングします。
再帰を使用せずに行う場合、予めノードの深さ分の処理を記述する必要があります。

【解説】
ノード１は経路の先頭（ほかのデータからの参照が無い）である事を条件にし、その経路の先頭の情報を各ノードでは引継ぎます。
次に、ナンバリングの為に経路の先頭に対し情報を配列化(array_agg)し畳みます。
上記で畳んだ情報に対してナンバリングし、最後に配列を展開(unnest)します。
※質問のデータでは、３階層までですが、サンプル的に階層４までにしています
※複数のunnestで展開できるかは確認してないので、駄目な様なら、結合したものでarray_aggして、展開後に分解して下さい。
※このselect文を元にcreate tableや insert するなりして下さい。

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における再帰

追記

ノード１時点でユニークIDを求めておけば、配列操作は不要だったので、追記。

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

Comments

[TeSe]

具体的なSQLと共に助言いただきまして、ありがとうございます！
>ノード１時点でユニークIDを求めておけば
こちらがとても素晴らしいと感じました。
[sys01]のデータを起点とするのではなく、システムID2とユーザーID2に同じデータが無い全てのユーザーIDを起点とすれば、システム問わず、ひも付きの最初に出てくるユーザーIDだけを起点に出来ますね！
あとは、対象のシステムが百近くあり増えることもあるため、処理量が気になります。。。
もう一歩の工夫で解決できそうな気がしてきました！私もこの方向性で考えてみます！
・システムの数だけjoinしなくても良い方法はないか　⇢考える
・ノードの深さを動的にする必要あり　⇢再起、ないしは動的に作成するSQLで可能

[TeSe]

rownumberと、[システムID2とユーザーID2に同じデータが無いデータ][システムID2とユーザーID2に同じデータが有るデータ]、集計関数を上手く使えば、最大ネスト数を1つのSQLで出せないかな。。。考えます

[sazi]

> ・ノードの深さを動的にする必要あり　
動的にする必要はありませんよ。
例えば最大が１００なら１００のノード分のSQLとしておけば、inner joinしている事によって、存在しないノードは抽出されませんので。
質問のデータのノードは3までですが、ノードが多めに記述されていても影響ない事を示すために敢えてノード４までで回答しています。

> システムの数だけjoinしなくても良い方法はないか
最大でどれくらい跨っているか想定できるなら、それよりも少し余裕を持たせたノード数にしておけば良いかと思います。

尚、再帰（recursive）の場合、上記のunion部分を一つのwithに記述するので、内部的には同様なことをしていると思われますので、それが固定の記述かどうかだけだと。

[TeSe]

＞saziさん
実際のデータにご教授いただいたSQL([追記]にあるもの)を流してみましたところ、素晴らしい結果が出ました。
特に、nodeの数を増やしてもディスクから読み取るデータ量が増えないため、BigQieryの課金額が増えないところが最高です！
大変助かりました！本当にありがとうございます！
そうですね、実際は全てのシステムをまたぐユーザーの存在は考えにくく、実データを集計すると最大でどのくらいのシステムをまたぐユーザーが居るかを把握できるので、運用に支障が出ないように対応できそうです。(もしくは、この方法だと仮に100ノード作っても、処理対象データが減っていくので負荷的にも問題なさそうです)
＞尚、再帰（recursive）の場合、上記のunion部分を一つのwithに記述するので、内部的には同様なことをしていると思われますので、それが固定の記述かどうかだけだと。
ごめんなさい、教えていただいたこちらの内容を理解することが出来ませんでした。
再帰処理を書いた場合は、node〜 を一定数書かなくても、必要な回数だけnodeを自動的に作成＆joinするような処理に出来るという意味であっておりますでしょうか？

[sazi]

> 再帰処理を書いた場合は、、node〜 を一定数書かなくても、必要な回数だけnodeを自動的に作成＆joinするような処理に出来る

bigqueryにrecursiveが実装されたとしたらの話です。
recursiveが使用できる他のDBMSではそうなります。

[TeSe]

お返事ありがとうございます。
なるほど、それでは今回はSQLをベタ書き、ないしは指定したノード数の分だけSQLを動的に組み立てて実行する方法で実装しようと思います。
ありがとうございました！大変助かりました！

[sazi]

再帰では無いので、無限ループはしませんが、ノードが循環しているデータが無い事だけは気を付けて下さい。
そういったデータがあり、補正しない場合は、最終的にgroup by する必要があります。

[TeSe]

了解しました！確かにそうですね。。。補足ありがとうございます！
元データは「システムID1＜システムID2」となっているので、現状は発生しないと思いますが、今後の改修でそのような自体が発生しないようにします。

Answer 2

以下のような深さ優先探索のロジックをSQLバッチで組めば、やりたいことを実現できると思います。ただしSQLはシステムIDの数の2乗回程度発行される可能性があります。

① 「作りたいテーブル」としてdstテーブルを作成する (ここではdstテーブル)

CREATE TABLE dst (
  systemid char(5),
  userid   char(5),
  uniqid integer,
  PRIMARY KEY(systemid, userid)
);

② 頂点どうしの紐づき関係を示すedgeテーブルを作成する。

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テーブルに投入する。

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テーブルの件数が増えなくなるまで以下のクエリを発行する。

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で処理するよりも、データをすべてファイルにダンプするなどして、
それを何かしらのプログラミング言語などで処理するほうがよいように思います。

Comments

[TeSe]

ありがとうございます！具体的なSQLまで載せていただいて、大変感謝です！
私の理解が誤っていたら大変申し訳無いのですが・・・
ご教授いただいた方法は、④のSQLを繰り返す数が予め見えないことと、加えて⑤と⑥を経たときのテーブルのデータ読み込み量が大きくなることから、ちょっと実現が難しそうな所感です。
(私が例に書いた元テーブルを、[on ユーザーID2＝ユーザーID1]で自己結合をシステム数だけ繰り返すのと同じかなと、見受けました。私の理解が間違っていたら申し訳ありません)
しかし、この紐付けをエッジや根で表現するという発想はありませんでした。ご教授いただいたこの発想を使って、解決出来ないか考えます。