The assumption: based on OP data so far, a request for friendship is always expressed as records couples: (1|2, 2|1).
The solution: look for records that are singletons, no matter the request status: pending, denied, accepted.
The given: the friendship initiator always starts with the accepted value for status. However, this may change for the initiator, since, later on, it may choose to deny the friendship.
1.1 When user 1 initiates a friendship request, two records are inserted:
1.2 When user 1 denies the friendship it has initiated, the corresponding records are updated:
2.1 When the user 2 accepts the request, the corresponding record is updated:
2.2 When the user 2 denies the requests, the corresponding record is updated:
along with the rest of the variations.
The study case table:
user_id1 | user_id2 | request_status | id
1 | 2 | accepted | 1
2 | 1 | accepted | 2
1 | 3 | accepted | 3
3 | 1 | accepted | 4
2 | 3 | accepted | 5
3 | 2 | pending | 6
The cleanup scenario:
The record having id = 2 has been deleted.
The record having id = 1 is now unmatched.
It needs to be deleted.
The delete process will take id (PK) for the delete filter.
The id set to be deleted is determined like this:
FROM friends_requests fr
OUTER JOIN friends_requests AS fr2
ON ( fr.user_id1 = fr2.user_id2
AND fr.user_id2 = fr2.user_id1 )
WHERE fr2.request_status IS NULL
The query has an average execution time of about 1.5ms for the test table above.
To address the penalties issues.
The query proposed by Dave:
WHERE CAST(user_id1 AS CHAR(10))
|| CAST(user_id2 AS CHAR(10))
NOT IN ( SELECT CAST( user_id2 AS CHAR(10) )
|| CAST( user_id1 AS CHAR(10) )
FROM friends_requests )
has an average execution time of about 2.0ms for the same test table above.
The larger the data, I personally believe that this difference will become much much bigger.
Another thing that's plain wrong, to me.
( 1 = 1 AND 2 = 2 )
is far better comparison test, performance wise (or otherwise), then
( '1 2 ' = '1 2 ' )
All this while the WHERE...NOT IN, for me, it's a JOIN gone wrong.