Query for suggested friends based on mutual friend count?

Question

I'd like to suggest users based on mutual friend count, like this.

Suggested Friends:

Amy Adams (42 mutual friends)
Brian Bautista (21 mutual friends)
Chris Cross (6 mutual friends)

Note: I have read several similar posts and answers, however the solutions are very dependent on the table structure, and I haven't been able to get anything to work with how our Friendships table is setup. See below.

USERS TABLE
id
name

FRIENDSHIPS TABLE
id
initiatingUserId (FK to Users Table)
targetUserId (FK to Users Table)
status ('active', 'denied', 'pending')

As you can see, there is a single row for each friendship. The user who sent the friend request is the initiating user, and the person who accepts the friend request is the target user. There are indexes on both those columns.

How can I efficiently get a list of users who are not yet friends with the current user, along with their mutual friend counts?

Here is a sample data set, as per @Strawberry's request...

CREATE TABLE `users` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `firstName` varchar(255) COLLATE utf8mb4_unicode_ci DEFAULT NULL,
  `lastName` varchar(255) COLLATE utf8mb4_unicode_ci DEFAULT NULL,
  PRIMARY KEY (`id`)
);

CREATE TABLE `friends` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `initiatingUserId` int(10) unsigned NOT NULL,
  `targetUserId` int(10) unsigned NOT NULL,
  `status` varchar(255) COLLATE utf8mb4_unicode_ci NOT NULL DEFAULT 'pending',
  PRIMARY KEY (`id`),
  UNIQUE KEY `compositeInitiatingUserIdTargetUserIdIndex` (`initiatingUserId`,`targetUserId`),
  KEY `friends_initiating_user_id` (`initiatingUserId`),
  KEY `friends_target_user_id` (`targetUserId`),
  CONSTRAINT `friends_ibfk_1` FOREIGN KEY (`initiatingUserId`) REFERENCES `users` (`id`) ON DELETE CASCADE ON UPDATE CASCADE,
  CONSTRAINT `friends_ibfk_2` FOREIGN KEY (`targetUserId`) REFERENCES `users` (`id`) ON DELETE CASCADE ON UPDATE CASCADE
);

INSERT INTO `users` (`id`, `firstName`, `lastName`) VALUES 
(1, 'A', 'A'),
(2, 'B', 'B'),
(3, 'C', 'C'),
(4, 'D', 'D'),
(5, 'E', 'E'),
(6, 'F', 'F'),
(7, 'G', 'G');

INSERT INTO `friends` (`id`, `initiatingUserId`, `targetUserId`, `status`) VALUES 
( 1, 1, 2, 'active'),
( 2, 1, 3, 'active'),
( 3, 4, 1, 'active'),
( 4, 2, 3, 'active'),
( 5, 2, 4, 'active'),
( 6, 5, 2, 'active'),
( 7, 2, 6, 'active'),
( 8, 2, 7, 'active'),
( 9, 3, 5, 'active'),
(10, 6, 3, 'active'),
(11, 4, 5, 'active'),
(12, 6, 7, 'active');

...and SQL Fiddle of same

The desired output, assuming we're pulling suggested users for User ID 1, would be:

+----------------+-------------+
| strangerUserId | mutualCount |
+----------------+-------------+
| 5              | 2           |
+----------------+-------------+
| 6              | 2           |
+----------------+-------------+
| 4              | 1           |
+----------------+-------------+
| 7              | 1           |
+----------------+-------------+

I do have a solution, but it assumes we already have the ids of the user's friends, and I'm not sure how fast it'll run:

select
count(*) as 'mutualCount',
case when f.initiatingUserId in (2, 3) then f.targetUserId else f.initiatingUserId end as strangerUserId
from friends f
    join users initiating on f.initiatingUserId=initiating.id
    join users target on targetUserId=target.id
and (
(
    initiatingUserId in (2, 3)
    and targetUserId not in (1, 2, 3)
)
or 
(
    targetUserId in (2, 3)
    and initiatingUserId not in (1, 2, 3)
)
)
group by strangerUserId
order by mutualCount desc;

user_14902187 · Answer

I have come up with this quick (MySql only) solution.

Note: This query is not optimized for your existing indexes and overall is probably going to have performance issues on a larger data set. It will also be hard to modify the query should you need to add some extra criteria. I would use individual parts of the query to pull the list of friends first then the list of non-friends and then run individual queries to identify mutual friends counts.

So here is the query to pull the list of non friends with mutual friends counts for userId '1'. You will have to replace hardcoded userId value of '1' in the query with dynamic variable:

SELECT COUNT(fnf.friendOfNonFriendId) AS mutualFriednCount, fnf.nonFriendId
 FROM
    -- Subquery to pull the list of non-friends and their friends
    (SELECT
        IF(f.initiatingUserId = nf.nonFriendId, f.targetUserId, f.initiatingUserId) AS friendOfNonFriendId,
        nf.nonFriendId
    FROM friends f
    JOIN
        (SELECT u.id AS nonFriendId
        FROM users u
        LEFT JOIN (
            SELECT IF(f.initiatingUserId = 1, f.targetUserId, f.initiatingUserId) AS friendId
            FROM friends f
            WHERE f.status = 'active' AND (f.initiatingUserId = 1 OR f.targetUserId = 1)) f
                                           ON f.friendId = u.id
        WHERE f.friendId IS NULL AND u.id != 1) nf ON nf.nonFriendId = f.initiatingUserId
          OR  nf.nonFriendId = f.targetUserId) fnf
 -- Joining the subquery with the list of friends of a user with ID 1 to filter the above subquery to only mutual friends 
 JOIN 
    (SELECT IF(f.initiatingUserId = 1, f.targetUserId, f.initiatingUserId) AS friendId
    FROM friends f
    WHERE f.status = 'active' AND (f.initiatingUserId = 1 OR f.targetUserId = 1)) f
                                   ON f.friendId = fnf.friendOfNonFriendId
 GROUP BY fnf.nonFriendId

Query for suggested friends based on mutual friend count?

1 Answers