Identity Graph and Identity Resolution in SQL

RudderStack
Jun 18 · 7 min read

In our previous blog, The Tale of Identity Graph and Identity Resolution, we described the problem of identity resolution. We used a concrete example of a user visiting an eCommerce site from multiple websites. Specifically, we showed how the app events can be associated with multiple identities and how these identities can be tied together using the identify() call. We captured the association using the following identity graph:

Identity Graph Capturing Associations

The identity graph is stored in a SQL database in the identify table as below:

The Identify Table in SQL Database

Anonymous IDUser IDMapped IDA-WebU-PhoneVirtual-ID-1A-WebU-EmailVirtual-ID-1A-MobU-PhoneVirtual-ID-1A-Web2U-EmailVirtual-ID-1The Identify table in SQL database

In this blog, we will show how we can associate a virtual ID with all these IDs. This association between (anonymous or user ID) and the virtual ID will let us tie all the events as originating from one end user. The system tags each of these events with individual IDs.

The Connected Components Algorithm

This article by David R. Maclver shows one way to implement the connected graph components algorithm. The idea is to keep a set of connected components, initially initialized to individual nodes as connected components. After this, you need to recursively merge the components if they have a link between them.

The algorithm requires a JOIN between the table of nodes with itself (self-join) and the table of edges (cartesian product). Unfortunately, self joins and cartesian products can be prohibitively costly to implement in distributed data warehouses. For example, BigQuery considers self joins anti-pattern and strongly discourages it.

Identity Graphs and ID Resolution: The Proposed Algorithm

The easiest way to do this is to keep two tables for edges and nodes. At each stage, we can join these two tables and update the node IDs. However, as explained earlier, these self joins and cartesian products can be very costly.

However, in the case of a bi-partite graph, we can simplify this quite a bit. Nodes on the right side can only update the nodes on the left side and vice versa. The following diagram shows the successive steps of this algorithm for the identity graph above:

Successive Steps to Implement Connected Components Algorithm for our Identity Graph

How it Works

  • The node A1 gets A1 (minimum of it’s ID A1 and neighbors U1, U2)
  • Node A2 gets A2 (minimum of it’s ID A2 and neighbors U1)
  • Node U1 gets A1 (minimum of ID’s ID and neighbors A1, A2)
  • and so on

You can see the node IDs after the subsequent steps in the above figure. The ID in bold is the latest ID associated with the node. As shown in the previous figure, above After-Step-2, the IDs have stabilized with each node getting assigned the same ID A1.

Code Implementation in SQL

  • orig_anon_id: Anonymous ID in the initial graph
  • orig_user_id: User ID in the initial graph
  • curr_anon_id: Anonymous ID at Nth iteration of the update
  • curr_user_id: User ID at the Nth iteration of the update

You can create ID_GRAPH_N+1 from ID_GRAPH_N by taking the min as described:

CREATE TABLE ID_GRAPH_0 (
orig_anon_id varchar(32),
orig_user_id varchar(32),
curr_anon_id varchar(32),
curr_user_id varchar(32),
version_anon_id int,
version_user_id int,
);
CREATE TABLE ID_GRAPH_1 AS
(
SELECT
orig_anon_id,
orig_user_id,
CASE
WHEN curr_anon_id is NULL THEN NULL
WHEN tmp_anon_id < curr_anon_id THEN tmp_anon_id
ELSE curr_anon_id
END AS curr_anon_id,
CASE
WHEN curr_user_id is NULL THEN NULL
WHEN tmp_user_id < curr_user_id THEN tmp_user_id
ELSE curr_user_id
END as curr_user_id,
CASE
WHEN curr_anon_id is NULL THEN version_anon_id
WHEN tmp_anon_id < curr_anon_id THEN curr_version
ELSE version_anon_id
END AS version_anon_id,
CASE
WHEN curr_user_id is NULL THEN version_usrer_id
WHEN tmp_user_id < curr_user_id THEN curr_version
ELSE version_user_id
END as version_user_id
FROM
(
SELECT
orig_anon_id,
orig_user_id,
curr_anon_id,
curr_user_id,
version_anon_id,
version_user_id,
MIN(curr_user_id)
OVER(PARTITION BY orig_anon_id)
as tmp_anon_id,
MIN(curr_anon_id)
OVER(PARTITION BY orig_user_id)
as tmp_user_id
FROM
ID_GRAPH_0
WHERE orig_anon_id IN (
SELECT orig_anon_id from ID_GRAPH_0 WHERE version_anon_id == curr_version
) OR
orig_user_id IN (
SELECT orig_user_id from ID_GRAPH_0 WHERE version_user_id == curr_version
)
) AS TMP_GRAPH_0
)

As noted above, you should run this as many times as the largest diameter of the connected component. Users rarely have more than three-four devices and identities (emails, phones). So, it would help if you ran this seven to eight times before the IDs stabilize. Moreover, you would have to run this continuously as new nodes and edges are added to the identity graph. As a result, large connected components that haven’t had IDs spread throughout will eventually do, as we discuss in the next section.

Incremental Updates

Unfortunately, that is not the most efficient way as the above code processes the entire graph in every run. Ideally, we should be able to process the new nodes and edges that the user introduces. Also, we should process the nodes/edges/connected components touched by those new edges. The latter is important because a new edge can connect two independent connected components, as shown in the following figure. In this case, the two connected components need to be merged and must be assigned the same ID as shown:

Identity Graph: Connected Components Merged

Using Version Numbers to Improve Efficiency

The Nth run of the ID mapping algorithm only touches nodes with edges with version N (or higher). You need to apply this process transitively. If the algorithm touches a node in the version N run, you need to process all the edges (even the older version ones) and nodes connected to those edges in the next run. This is required to handle the case described in the identity graph above. It is not enough to only process New Edge. You need to update all the nodes connected to New Edge. Furthermore, you need to update all the other edges from those nodes and their transitive closure.

CREATE TABLE ID_GRAPH_0 (
orig_anon_id varchar(32),
orig_user_id varchar(32),
curr_anon_id varchar(32),
curr_user_id varchar(32),
version_anon_id int,
version_user_id int,
);
CREATE TABLE ID_GRAPH_1 AS
(
SELECT
orig_anon_id,
orig_user_id,
CASE
WHEN curr_anon_id is NULL THEN NULL
WHEN tmp_anon_id < curr_anon_id THEN tmp_anon_id
ELSE curr_anon_id
END AS curr_anon_id,
CASE
WHEN curr_user_id is NULL THEN NULL
WHEN tmp_user_id < curr_user_id THEN tmp_user_id
ELSE curr_user_id
END as curr_user_id,
CASE
WHEN curr_anon_id is NULL THEN version_anon_id
WHEN tmp_anon_id < curr_anon_id THEN curr_version
ELSE version_anon_id
END AS version_anon_id,
CASE
WHEN curr_user_id is NULL THEN version_usrer_id
WHEN tmp_user_id < curr_user_id THEN curr_version
ELSE version_user_id
END as version_user_id
FROM
(
SELECT
orig_anon_id,
orig_user_id,
curr_anon_id,
curr_user_id,
version_anon_id,
version_user_id,
MIN(curr_user_id)
OVER(PARTITION BY orig_anon_id)
as tmp_anon_id,
MIN(curr_anon_id)
OVER(PARTITION BY orig_user_id)
as tmp_user_id
FROM
ID_GRAPH_0
WHERE orig_anon_id IN (
SELECT orig_anon_id from ID_GRAPH_0 WHERE version_anon_id == curr_version
) OR
orig_user_id IN (
SELECT orig_user_id from ID_GRAPH_0 WHERE version_user_id == curr_version
)
) AS TMP_GRAPH_0
)

Profiling

Conclusion

Sign up for Free and Start Sending Data

This blog was originally published at
https://rudderstack.com/blog/identity-graph-and-identity-resolution-in-sql

Geek Culture

Proud to geek out. Follow to join our 1M monthly readers.