Database Reference
In-Depth Information
How about finding all friends of a user's friends? This time you'd typically join the
t_user_friend table with itself before querying:
select count(distinct uf2.*) from t_user_friend uf1
inner join t_user_friend uf2 on uf1.user_1 = uf2.user_2
where uf1.user_1 = ?
Popularsocialnetworksusuallyhaveafeaturewheretheysuggestpeoplefromyourfriend-
ship network as potential friends or contacts, up to a certain degree of separation, or depth.
If you wanted to do something similar to find friends of friends of friends of a user, you'd
need another
join
operation:
select count(distinct uf3.*) from t_user_friend uf1
inner join t_user_friend uf2 on uf1.user_1 = uf2.user_2
inner join t_user_friend uf3 on uf2.user_1 = uf3.user_2
where uf1.user_1 = ?
Similarly, to iterate through a fourth level of friendship, you'd need four joins. To get all
connections for the famous six degrees of separation problem, six joins would be required.
There's nothing unusual about this approach, but there's one potential problem: although
you'reonlyinterestedinfriendsoffriendsofasingleuser,youhavetoperformajoinofall
data in the t_user_friend table, and then discard all rows that you're not interested in. On a
small data set, this wouldn't be a big concern, but if your social network grows large, you
could start running into serious performance problems. As you'll see, this can put a huge
strain on your relational database engine.
To illustrate the performance of such queries, we ran the friends-of-friends query a few
times against a small data set of 1,000 users, but increased the depth of the search with
each invocation and recorded the results each time. On a small data set of 1,000 users,
where each user has on average 50 friends, table t_user contains 1,000 records, whereas
table t_user_friend contains 1,000 × 50 = 50,000 records.
At each depth, we ran the query 10 times—this was simply to warm up any caches that
could help with performance. The fastest execution time for each depth was recorded. No
additionaldatabaseperformancetuningwasperformed,apartfromcolumnindexesdefined
in the SQL script from
listing 1.1
.
Table 1.1
shows the results of the experiment.
