ваш id, friend_id друга
1 2
2 1
если есть пара, то вы друзья, если нет, тоесть только 1 2 или 2 1, то ещё нет ждёте подтверждения.
Вот такой запрос, выдаёт список друзей:
SELECT login, friends.id AS check_id, friends.friend_id AS check_friend_id,
(SELECT id FROM friends WHERE id=check_friend_id AND friend_id=check_id)AS checkout
FROM friends LEFT JOIN users ON (users.id=friends.friend_id)
WHERE friends.id=?i
HAVING checkout IS NOT NULL ORDER BY login
И два индекса на id, friend_id и наоборот friend_id, id
Есть вариант второй, делать только одну запись, но добавить поле friendship, а потом проверять её наличие и если есть, то апдейтить friendship=1. Надеюсь вам это поможет.