Unique index on 2 columns in mysql
One way to avoid your issue is to make it a business rule that the userid and friendid values be inserted in a specific order. You could add a row constraint (either by adding INSERT/UPDATE triggers, or by applying your changes via a Stored Procedure) to ensure that userid&lt;friendid so it would be okay to insert (userid, friendid) VALUES (1, 2) but any attempt to add (userid, friendid) VALUES (2, 1) would fail.

Example using TRIGGER:

DELIMITER $$
DROP TRIGGER IF EXISTS `userfriends_INSERT` $$
CREATE TRIGGER `userfriends_INSERT` 
BEFORE INSERT ON `userfriends`
FOR EACH ROW
BEGIN
    IF new.`userid` &gt;= new.`friendid` THEN
        SIGNAL SQLSTATE '45000';  # unhandled user-defined exception
    END IF;
END $$
DELIMITER ;


Test:

mysql&gt; SHOW VARIABLES LIKE "version";
+---------------+-------------------------+
| Variable_name | Value                   |
+---------------+-------------------------+
| version       | 5.5.29-0ubuntu0.12.04.1 |
+---------------+-------------------------+
1 row in set (0.00 sec)

mysql&gt; DESCRIBE userfriends;
+----------+---------+------+-----+---------+-------+
| Field    | Type    | Null | Key | Default | Extra |
+----------+---------+------+-----+---------+-------+
| userid   | int(11) | NO   | PRI | NULL    |       |
| friendid | int(11) | NO   | PRI | NULL    |       |
+----------+---------+------+-----+---------+-------+
2 rows in set (0.00 sec)

mysql&gt; SELECT ENGINE FROM information_schema.tables WHERE TABLE_NAME = "userfriends";
+--------+
| ENGINE |
+--------+
| InnoDB |
+--------+
1 row in set (0.00 sec)

mysql&gt; SELECT trigger_name FROM information_schema.triggers;
+--------------------+
| trigger_name       |
+--------------------+
| userfriends_INSERT |
+--------------------+
1 row in set (0.00 sec)

mysql&gt; SELECT * FROM userfriends;
Empty set (0.00 sec)

mysql&gt; INSERT INTO userfriends (userid, friendid) VALUES (2, 1);
ERROR 1644 (45000): Unhandled user-defined exception condition
mysql&gt; INSERT INTO userfriends (userid, friendid) VALUES (1, 2);
Query OK, 1 row affected (0.02 sec)

mysql&gt; INSERT INTO userfriends (userid, friendid) VALUES (2, 1);
ERROR 1644 (45000): Unhandled user-defined exception condition
mysql&gt; INSERT INTO userfriends (userid, friendid) VALUES (1, 2);
ERROR 1062 (23000): Duplicate entry '1-2' for key 'PRIMARY'