 <p>You friendship relationship here seems to be symmetrical.</p> <p>In this case, you should insert the friends' ids in strict order: say, least <code>id</code> first, greatest <code>id</code> second.</p> <p>This will make one record per friendship, not depending on who befriended whom.</p> <p>Use this query:</p> <pre><code>SELECT 1 FROM users_friends WHERE (user_id, friend_id) = (LEAST($user_id, $SESSION['user_id']), GREATEST($SESSION['user_id'], $user_id)) </code></pre> <p>to check the friendship status, and this one:</p> <pre><code>INSERT INTO users_friends (user_id, friend_id) VALUES (LEAST($user_id, $SESSION['user_id']), GREATEST($SESSION['user_id'], $user_id)) </code></pre> <p>to insert a new record.</p>