Defining a two-way link

Question

I have a users table, and I want to define a "friends" relationship between two arbitrary users.

Up until now, I've used two different methods for this:

1. The friends table contains user1 and user2. Searching for users involves a query that looks like
   ... WHERE @userid IN (`user1`,`user2`), which is not terribly efficient
2. The friends table contains from and to fields. Initiating a friend request creates a row in that direction, and if it accepted then a second row is inserted with the opposite direction. There is additionally a status column that indicates that this has happened, making the search something like:
   ... WHERE `user1`=@userid AND `status`=1

I'm not particularly satisfied with either of these solutions. The first one feels messy with that IN usage, and the second seems bloated having two rows to define a single link.

So that's why I'm here. What would you suggest for such a link? Note that I don't need any more information saved with it, I just need two user IDs associated with each other, and preferably some kind of status like ENUM('pending','accepted','blocked'), but that's optional depending on what the best design for this is.

Answer 1

There are in general two approaches:

1. Store each friend pair once, storing the friend with the least id first.

   CREATE TABLE
           friend
           (
           l INT NOT NULL,
           g INT NOT NULL,
           PRIMARY KEY
                   (l, g),
           KEY (g)
           )
   

2. Store each friend pair twice, both ways:

   CREATE TABLE
           (
           user INT NOT NULL,
           friend INT NOT NULL,
           PRIMARY KEY
                   (user, friend)
           )
   

To store additional fields like friendship status, acceptance dates etc. you usually utilize a second table, for reasons I'll describe below.

To retrieve a list of friends for each user, you do:

SELECT  CASE @myuserid WHEN l THEN g ELSE l END
FROM    friend
WHERE   l = @myuserid 
        OR
        g = @myuserid

or

SELECT  g
FROM    friend
WHERE   l = @myuserid
UNION
SELECT  l
FROM    friend
WHERE   g = @myuserid

for the first solution; and

SELECT  friend
FROM    friend
WHERE   user = @friend

To check if two users are friends, you issue this:

SELECT  NULL
FROM    friend
WHERE   (l, g) =
        (
        CASE WHEN @user1 < @user2 THEN @user1 ELSE @user2 END,
        CASE WHEN @user1 > @user2 THEN @user1 ELSE @user2 END
        )

or

SELECT  NULL
FROM    friend
WHERE   (user, friend) = (@user1, @user2)

---

Storage-wise, the two solutions are almost the same. The first (least/greatest) solution stores twice as few rows, however, for it to work fast you should have a secondary index on g, which, in fact, has to store g plus the part of the table's primary key which is not in the secondary index (that is, l). Thus, each record is effectively store twice: once in the table itself, once again in the index on g.

Performance-wise, the solutions are almost the same too. The first one, though, requires two index seeks followed by index scans (for "all friends"), the second one just one index seek, so for the L/G solution I/O amount might be slighly more. This might be mitigated a little by the fact that the one single index may become one level deeper than two independent ones, so the initial search may take one page read more. This may slow down "are they friends" query a little for the "both pairs" solution, compared to L/G.

---

As for the additional table for extra data, you most probably want it because it's usually much less used than the two query I described above (and usually only for history purposes).

Its layout also depends on the kind of queries you are using. Say, if you want "show my last ten friendships", then you may want to store the timestamp in "both pairs" so that you don't have to do filesorts, etc.