MySQL query for mutual friends [duplicate]

Question

Possible Duplicate:
MYSQL select mutual friends

I have a table for friendship, the friendship is stored only in one line. So there is no duplicate entries.

id  Person1    Person2  status
1         1          2  friend
2         1          3  friend
3         2          3  friend
4         3          4  friend

What MySQL query (join, inner join) will help me to find common (mutual) friends between person #1 and person #3? The input in this example is {1,3} and the output should be {2} since Person #2 is friend with bot #1 and #3.

Answer 1

Well, the only query that might work up to now is Simon's... but that's real overkill - such a complex nasty query (2 subqueries with 2 unions!) for so simple thing that you need to place a bounty? :-) And if you have like 1000+ users the query will be slow as hell - remeber, it's quadratic, and due to unions in subqueries, hardly any index would be used!

I'd suggest to re-think the design again and allow for 2 duplicate rows for a friendship:

id  Person1    Person2  status
1         1          2  friend
2         2          1  friend
3         1          3  friend
4         3          1  friend

You might think that's inefficient but following simplification will allow to rewrite the query to simple joins:

select f1.Person2 as common_friend
from friends as f1 join friends as f2
    using (Person2)
where f1.Person1 = '$id1' and f2.Person1 = '$id2' 
    and f1.status = 'friend' and f2.status = 'friend'

which will be fast as hell! (Don't forget to add indices for Person1,2.) I've advised a similar simplification (rewriting subqueries to joins) in other very nasty data structure and it has speeded up the query from eternity to blitz-instant!

So what might have been looking as a big overhead (2 rows for one friendship) is actually a big optimization :-)

Also, it will make queries like "find all friends of X" much more easier. And no more bounties will need to be spent :-)

Answer 2

This query works with the assumption that there is no self-friending and no duplicates in friendship table, if these conditions are not meet little tweaks needed to make it work.

SELECT fid FROM 
(
    --FIRST PERSON (X) FRIENDLIST
    SELECT 
        (CASE WHEN Person1 = X THEN Person2 ELSE Person1 END) AS fid
    FROM Friendships WHERE (Person1 = X OR Person2 = X) AND status = "friend"
    UNION ALL --DO NOT REMOVE DUPLICATES WITH ALL JOIN
    --SECOND PERSON (Y) FRIENDLIST
    SELECT 
        (CASE WHEN Person1 = Y THEN Person2 ELSE Person1 END) AS fid
    FROM Friendships WHERE (Person1 = Y OR Person2 = Y) AND status = "friend"
) FLIST
GROUP BY fid
HAVING COUNT(*) = 2

Answer 3

One more answer.

select 
    (case when f1.person1 = 1 then f1.person2 else f1.person1 end) as fid
from friends f1
where f1.person1 = 1 or f1.person2 = 1
and f1.status = 'friend'

intersect

select 
    (case when f1.person1 = 3 then f1.person2 else f1.person1 end) as fid
from friends f1
where f1.person1 = 3 or f1.person2 = 3
and f1.status = 'friend'

Answer 4

set search_path='tmp';

DROP TABLE friendship CASCADE;
CREATE TABLE friendship
        ( id integer not null PRIMARY KEY
        , person1 integer not null
        , person2 integer not null
        , status varchar
        , CONSTRAINT pk1 UNIQUE (status,person1,person2)
        , CONSTRAINT pk2 UNIQUE (status,person2,person1)
        , CONSTRAINT neq CHECK (person1 <> person2)
        );

INSERT INTO friendship(id,person1,person2,status) VALUES
 (1,1,2,'friend' ) ,(2,1,3,'friend' ) ,(3,2,3,'friend' ) ,(4,3,4,'friend' )
        ;

        -- -----------------------------------------
        -- For implementations that don't have CTEs, 
        -- a view can be used to emulate a CTE.
        -- -----------------------------------------
CREATE VIEW flip AS (
        SELECT person1 AS one
                , person2 AS two
        FROM friendship WHERE status = 'friend'
        UNION
        SELECT person2 AS one
                , person1 AS two
        FROM friendship WHERE status = 'friend'
        );

SELECT DISTINCT
        f1.two AS common
FROM flip f1
JOIN flip f2 ON f1.two = f2.two
WHERE f1.one = 1
AND f2.one = 3
        ;

DROP VIEW flip;

        -- ------------------------------
        -- The same query with a real CTE
        -- ------------------------------
with flip AS (
        SELECT person1 AS one
                , person2 AS two
        FROM friendship WHERE status = 'friend'
        UNION
        SELECT person2 AS one
                , person1 AS two
        FROM friendship WHERE status = 'friend'
        )
SELECT DISTINCT
        f1.two AS common
FROM flip f1
JOIN flip f2 ON f1.two = f2.two
WHERE f1.one = 1
AND f2.one = 3
        ;

RESULT:

SET
DROP TABLE
NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index "friendship_pkey" for table "friendship"
NOTICE:  CREATE TABLE / UNIQUE will create implicit index "pk1" for table "friendship"
NOTICE:  CREATE TABLE / UNIQUE will create implicit index "pk2" for table "friendship"
CREATE TABLE
INSERT 0 4
CREATE VIEW
 common 
--------
      2
(1 row)

DROP VIEW
 common 
--------
      2
(1 row)