SQL Performance: Using Union and Subqueries

Hi stackoverflow(My first question!),

We're doing something like an SNS, and got a question about optimizing queries.

Using mysql 5.1, the current table was created with:

CREATE TABLE friends(
 user_id BIGINT NOT NULL,
 friend_id BIGINT NOT NULL,
 PRI开发者_运维百科MARY KEY (user_id, friend_id)
) ENGINE INNODB;

Sample data is populated like:

INSERT INTO friends VALUES
(1,2),
(1,3),
(1,4),
(1,5),
(2,1),
(2,3),
(2,4),
(3,1),
(3,2),
(4,1),
(4,2),
(5,1),
(5,6),
(6,5),
(7,8),
(8,7);

The business logic: we need to figure out which users are friends or friends of friends for a given user. The current query for this for a user with user_id=1 is:

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

The expected result is(order doesn't matter):

2
3
4
5
1
6

As you can see, the above query performs the subquery "SELECT friend_id FROM friends WHERE user_id = 1" twice.

So, here is the question. If performance is your primary concern, how would you change the above query or schema?

Thanks in advance.

In this particular case, you can use a JOIN:

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

Examining each query suggests the JOIN will about as performant as the UNION in a big-O sense, though perhaps faster by a constant factor. Jasie's query looks like it might be big-O faster.

EXPLAIN SELECT friend_id FROM friends WHERE user_id = 1
  UNION
    SELECT DISTINCT friend_id FROM friends WHERE user_id IN (
      SELECT friend_id FROM friends WHERE user_id = 1
    );
+----+--------------------+------------+--------+---------------+---------+---------+------------+------+-------------------------------------------+
| id | select_type        | table      | type   | possible_keys | key     | key_len | ref        | rows | Extra                                     |
+----+--------------------+------------+--------+---------------+---------+---------+------------+------+-------------------------------------------+
|  1 | PRIMARY            | friends    | ref    | PRIMARY       | PRIMARY | 8       | const      |    4 | Using index                               |
|  2 | UNION              | friends    | index  | NULL          | PRIMARY | 16      | NULL       |   16 | Using where; Using index; Using temporary |
|  3 | DEPENDENT SUBQUERY | friends    | eq_ref | PRIMARY       | PRIMARY | 16      | const,func |    1 | Using index                               |
| NULL | UNION RESULT       | <union1,2> | ALL    | NULL          | NULL    | NULL    | NULL       | NULL |                                           |
+----+--------------------+------------+--------+---------------+---------+---------+------------+------+-------------------------------------------+


EXPLAIN SELECT DISTINCT f2.friend_id 
  FROM friends AS f1
    JOIN friends AS f2 
      ON f1.friend_id=f2.user_id OR f2.user_id=1
  WHERE f1.user_id=1;
+----+-------------+-------+-------+---------------+---------+---------+-------+------+---------------------------------------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref   | rows | Extra                                       |
+----+-------------+-------+-------+---------------+---------+---------+-------+------+---------------------------------------------+
|  1 | SIMPLE      | f1    | ref   | PRIMARY       | PRIMARY | 8       | const |    4 | Using index; Using temporary                |
|  1 | SIMPLE      | f2    | index | PRIMARY       | PRIMARY | 16      | NULL  |   16 | Using where; Using index; Using join buffer |
+----+-------------+-------+-------+---------------+---------+---------+-------+------+---------------------------------------------+


EXPLAIN SELECT DISTINCT friend_id FROM friends WHERE user_id IN (
    SELECT friend_id FROM friends WHERE user_id = 1
) OR user_id = 1;
+----+--------------------+---------+--------+---------------+---------+---------+------------+------+-------------------------------------------+
| id | select_type        | table   | type   | possible_keys | key     | key_len | ref        | rows | Extra                                     |
+----+--------------------+---------+--------+---------------+---------+---------+------------+------+-------------------------------------------+
|  1 | PRIMARY            | friends | index  | PRIMARY       | PRIMARY | 16      | NULL       |   16 | Using where; Using index; Using temporary |
|  2 | DEPENDENT SUBQUERY | friends | eq_ref | PRIMARY       | PRIMARY | 16      | const,func |    1 | Using index                               |
+----+--------------------+---------+--------+---------------+---------+---------+------------+------+-------------------------------------------+

No need for the UNION. Just include an OR with the user_id of the beginning user:

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

+-----------+
| friend_id |
+-----------+
|         2 |
|         3 |
|         4 |
|         5 |
|         1 |
|         6 |
+-----------+