MySQL retrieve friends of friends structure and performance

Question

I would simply like to find a database structure in MySQL to get all users friends of friends and the corresponding query to retrieve them. (friend links are bi-directional)

I have found a couple posts related to that, but my concern is the performance:

Structure 1

Many posts suggest a structure where you have a table in which each row represents a friendship link e.g:

    CREATE TABLE `friends` (
    `user_id` int(10) unsigned NOT NULL,
    `friend_id` int(10) unsigned NOT NULL,
    )

saying the user '1' has three friend '2','3','4' and user '2' has two friend '1','5' . Your friend table would look like this:

    user_id    |    friend_id
    1          |    2
    1          |    3
    1          |    4
    2          |    1
    2          |    5

friends of friends query: How to select friends of friends can be seen here SQL to get friends AND friends of friends of a user. The rsult of the query for user '1' is supposed to give (1,2,3,4,5)

My concern: The average fb-user has about 140 friends. Frequent users will have a lot more. If I have 20.000 users this will end up in at least 3million rows.

Structure 2

If I could use a structure like this:

    CREATE TABLE `friends` (
    `user_id` int(10) unsigned NOT NULL,
    `friend_1` int(10) unsigned NOT NULL,
    `friend_2` int(10) unsigned NOT NULL,
    `friend_3` int(10) unsigned NOT NULL,
    `friend_4` int(10) unsigned NOT NULL,
    ....
    )

My table would look like this (taking example from above):

    user_id  |  friend_1  |  friend_2  |  friend_3  |  ...
    1        |  2         |  3         |  4         |
    2        |  1         |  5         |            |...

Now I have only 20.000 rows.

friends of friends query: To select user friends of friends I tried

    Select * FROM friends as a
    WHERE a.user_id 
    IN (
        SELECT * FROM friends AS b
        WHERE b.user_id = '1'
    )

but I get an error "#1241 - Operand should contain 1 column(s) ". I think the problem is, that the sub-selection passes a row, not a column?

Questions

I hope you understand my concern. I would be really really happy about any input to these questions

1) find a query that returns all friends of friends for a specified user in structure 2?

2) Which structure allows me to return friends of friends quicker? In structure 2 I think the "join row with column" could be slow, if its even possible to use a join here. Thank you for any suggestions. If you could think of any other structures, maybe taking advantage of the small-world-network-type I'd be happy to hear them.

THANK YOU!!

Answer 1

Definitely use the first structure. Queries for the second structure will be huge, hard to maintain and slow because of complicated clauses.

A fast enough query for the first approach:

(
    select friend_id 
    from friends 
    where user_id = 1
) union (
    select distinct ff.friend_id 
    from 
        friends f
        join friends ff on ff.user_id = f.friend_id
    where f.user_id = 1
)

For the best performance you need to have these indexes:

ALTER TABLE `friends` ADD UNIQUE INDEX `friends_idx` (`user_id` ASC, `friend_id` ASC);
ALTER TABLE `friends` ADD INDEX `friends_user_id_idx` (`user_id` ASC);

Answer 2

I'd say you ought to use the first structure. It's more flexible in my opinion. My solution for the query would be a simple sub-query, like this:

SELECT friend_id FROM friends WHERE user_id IN (

       SELECT friend_id FROM friends WHERE user_id='$USER_ID'

);

EDIT: Sorry I just woke up and realized after posting a reply that this wasn't at all what you were looking for. Sry.