Как реализовать хранение друзей в БД?
А что если хранить немного по другому?

Например не создавать дублирующую запись в обратную сторону, а изначально использовать еще одно поле в троичной системе счисления: ± 1 когда один пользователь добавил другого (знак указывает направление заявки) и 0 когда заявка подтверждена.

Тогда запрос будет один на выборку пары, а состояния отозвать/принять заявку и удалить из друзей будут определяться знаком числа в дополнительном поле.

Из очевидных плюсов. Места занимать будет примерно в два раза меньше — мелочь, а приятно.
Минусов не сразу не соображу.
теоретически вам надо два множества — друзья юзера, и обратное — те кто позвал в друзья вашего юзера. 
1. select f1.friend from friends f1 where f1.user=:user_id
2. select f1.user from friends f1 where f1.friend=:user_id

пересечение будет давать взаимных френдов, вычитания — невзимных с одной и с другой стороны.
синтаксис SQL говорит что это легко можно сделать полным join, который обычно не имплементируется но эмулируется обьединением left и right. То бишь:
select * from friends f1 LEFT join friends f2 on f1.user=f2.friend and f2.user=f1.friend where f1.user=:user_id
UNION
select * from friends f1 RIGHT join friends f2 on f1.user=f2.friend and f2.user=f1.friend where f2.friend=:user_id

и будет 3 варианта — обе f1 и f2 не null — взаимные друзья или один из них null

Но это не самый эффективный способ, я бы согласился с serso и посоветовал иметь доп колонку с типом ( заодно можно их иметь несколько — друзья, супруги/любовники, коллеги ) и при добавлении проверять обратное отношение и сразу заполнять колонку. На нагруженной системе это можно делать в отложенном режиме.


