Friend of a friend in PHP/MySQL?

Question

Ok I have searched before asking, all I found was several questions asking what I am but 0 answers so maybe someone who knows will see this or I will make it a more clear question.

I have a social network similar to myspace/facebook. In my code you are either a person's friend or not a friend, so I show all actions from people you are friends with (in this post I will refer to actions as bulletin posts alone to make it easier to visualize.

So you every time a person post a bulletin it will show up to any person who is there friend.

So in mysql you would get a persons friend list by doing something like this,

SELECT user_id FROM friends WHERE friend_id = 1 (user ID)

I want to know how a site like facebook and some others would show all bulletin post from your friends and from your friends' friends?

If anyone has an idea please show some code like what kind of mysql query?

Answer 1

you do a subquery:

SELECT DISTINCT user_id FROM friends WHERE friend_id IN (SELECT user_id FROM friends WHERE friend_id = 1)

Answer 2

Test both of these for performance:

SELECT DISTINCT user_id
FROM friends f1
JOIN friends f2 ON f1.friend_id = f2.user_id
WHERE f2.friend_id = 1

and

SELECT DISTINCT user_id
FROM friends
WHERE friend_id IN (SELECT user_id FROM friends WHERE friend_id = 1)

Often they're the same but sometimes they're not.

Make sure friend_id and user_id are indexed.

Answer 3

The answer is that they aren't doing selects on a friend table, they are most likely using a de-normalized news-event table. We implemented a news-feed similar to Facebooks on DoInk.com, here's how we did it:

There is the notion of a "NewsEvent" it has a type, an initiator (a user id) and a target user (also a user id). (You can also have additional column(s) for other properties relevant to the event, or join them in)

When a user posts something on another users wall we generate an event like this:

INSERT INTO events VALUES (wall_post_event, user1, user1)

When viewing user1's profile, you'd select for all events where user1 is either the initiator or the target. That is how you display the profile feed. (You can get fancy and filter out events depending on your privacy model. You may consider doing this in memory for performance reasons)

Example:

SELECT * FROM events WHERE initiator = user1 or target = user1 //to see their profile feed

SELECT * FROM events WHERE initiator IN (your set of friend ids) //to see your newsfeed

When you want to see the newsfeed for all events relative to your friends you might do a query selecting for all events where the initiator is in your set of friends.

Avoid implementations with sub-selects, depending on the complexity, they will not scale.

Answer 4

The simple approach would be to do some kind of simple nested clause. So say you have a table with posts and the posters id, and a friends table, the first layer would be

SELECT post FROM posts JOIN friends 
  on post.userid = friends.friend_id 
  WHERE friend.id = 1 (user ID)

then to get a friends of friends

SELECT post FROM posts JOIN
   (SELECT DISTINCT friends_2.friend_id FROM friends AS friends_1 
        JOIN friends as friends_2 
        on friends_1.friend_id = friends_2.id where friends_1.id = 1) 
AS friends 
wHERE post.userid = friends.friend_id AND mainid = 1 (user ID)

You can repeat this nesting each time you want to add another layer of friend abstraction. The problem with this approach is that it would take a very long time to execute. For every time you add a layer of friend abstraction you are increasing the complexity by a power of n (where n is the number of rows in your table).

It is more likely that they are saving the viewable friends in a table somewhere, so lets make a new tabled called friends_web

user_id, friend_id, level

when a user friends someone, it adds that new friend into friends_web at a level of 0(since that friend is no people away) then adds that friends friends at a level of 1 (since its 1 friend away). In order to keep the table integrity you would also want to add the inverted record. To clarify if A adds B as a friend and C is a friend of B, the following two records would get added to our new table

A, C, 1
C, A, 1

since now A can see C and C can see A.

now when we want a query we just do

 SELECT post FROM posts 
  JOIN friends_web ON post.user_id = friends_web.friend_id 
  WHERE friends_web.user_id = user_id AND friends_web.level < 2 (or however deep you want to look)

by doing that you minimized your query complexity when doing post lookups while being able to look more then 1 layer deep into a friend web.

Sorry for the long winded response.

Answer 5

This should pull out all the user's friend's posts.

SELECT * FROM posts WHERE uid IN (SELECT friend_uid FROM friends WHERE uid=1) ORDER BY post_id DESC

This should pull out all posts that are your friend's friend's.

SELECT * FROM posts WHERE uid IN (SELECT friend_uid FROM friends WHERE uid IN (SELECT friend_uid FROM friends WHERE uid=1)) ORDER BY post_id DESC