OR vs UNION in message tables I have a dilemma. I have a messages table containing fields id, sender, receiver, body I need to select all users a given user has had a conversation with. A conversation may be a single message without a response.

Here's a show create table for you to see the indexes (as I may have set them up incorrectly):

CREATE TABLE `messages` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `sender` int(10) unsigned NOT NULL,
  `receiver` int(10) unsigned NOT NULL,
  `body` text,
  `datetime` datetime DEFAULT NULL,
  `seen` enum('0','1') NOT NULL DEFAULT '0',
  PRIMARY KEY (`id`),
  KEY `message_receiver` (`receiver`),
  KEY `msg_snd` (`sender`),
  CONSTRAINT `msg_rcv` FOREIGN KEY (`receiver`) REFERENCES `users` (`id`) ON DELETE NO ACTION ON UPDATE CASCADE,
  CONSTRAINT `msg_snd` FOREIGN KEY (`sender`) REFERENCES `users` (`id`) ON DELETE NO ACTION ON UPDATE CASCADE
) ENGINE=InnoDB AUTO_INCREMENT=7 DEFAULT CHARSET=utf8


Here is basically the simplest way I could come up with to get the task done

SELECT DISTINCT
    (
        CASE SENDER
        WHEN 15 THEN
            receiver
        ELSE
            CASE receiver
        WHEN 15 THEN
            sender
        END
        END
    ) AS `user`
FROM
    messages
WHERE
    sender = 15
OR receiver = 15


However, I know that MySQL cannot take full advantage of indexes with OR comparisons (may be wrong), so I came up with an alternative of two queries which can both benefit from the indexes:

SELECT DISTINCT
    `user`
FROM
    (
        SELECT
            DISTINCT sender AS `user`
        FROM
            messages
        WHERE
            receiver = 15
        UNION
            SELECT
                DISTINCT receiver AS `user`
            FROM
                messages
            WHERE
                sender = 15
    ) AS conversations


Which one of these approaches is better in terms of performance and complexity?
Use OR
You should make it a habit to look at your queries' execution plan when in doubt. I recreated the table in SQL Fiddle (albeit, without containing data) and it shows that the query with OR is less complex.
Please note: SQL Fiddle does not support your FOREIGN KEY constraints, so I had to remove them.
First query with OR:

Second query with UNION:

As you can see, the complexity of the 2nd query is higher, which might make it slower (or faster!), albeit the direction (faster or slower) and how much difference it will have depends on a lot of other things too.
In MySQL (and many other DBMS), it's actually (and counter-intuitively) the UNION ALL is usually more efficient than the OR version. Of course, that's because the UNION ALL does not have to remove duplicate rows. In many cases, including this one, we have use UNION (so UNION DISTINCT).

The edit below has been suggested by @ypercube, from dba.SE, and voluntarily added by OP:
Also note that your second query has a unnecessary level and an extra DISTINCT that is redundant which will almost certainly drag efficiency down. Here are two simplifications:
 -- query 2b:  SELECT DISTINCT - UNION DISTINCT - SELECT DISTINCT
SELECT
    DISTINCT sender AS `user`
FROM
    messages
WHERE
    receiver = 15
UNION
    SELECT
        DISTINCT receiver 
    FROM
        messages
    WHERE
        sender = 15 ;


-- query 2c: SELECT ALL - UNION DISTINCT - SELECT ALL
SELECT
    sender AS `user`
FROM
    messages
WHERE
    receiver = 15
UNION
    SELECT
        receiver 
    FROM
        messages
    WHERE
        sender = 15 ;