1 on 1 Random Matchmaking

I am developing a random chat application that matches a client with another "random" client. Pseudo-Random because the client would query a list of "open" clients and pick from the top of the list.

I have searched for an answer but seemingly no resources exist for a matchmaking solution based off of a relational database in mySQL. The problem I ran into is that if all clients were set to "search", then each(user) would try to connect to one(a) while the one(a) would be trying to connect to another(b). {*user is chasing a while a is chasing b simultaneously.}

What would be the simplest structure and process to connect two random clients to exchange information when both are in a pool of unmatched-clients?