1 - create a new country table like ...
create table country (id int auto_incremenet primary key, country varchar(100));
2 - create a new city table like ...
create city (id int auto_increment primary key , city varchar(100), fk_country_id int);
fk_country_id will have the id of the country that city is located in
3 - in your table mentioned above, remove the country and city columns and add only fk_city_id column. fk_city_id will have the id of the city that person is located in
4 - create table for phones like
create table user_phones(id int auto_increment primary key, fk_country_id int, phone_number varchar(15)) ;
5 - add unique index to that table like so ..
CREATE UNIQUE INDEX idx_country_phone ON user_phones(fk_country_id, phone_number);
remove phone number and search_phone_number from your table and add fk_user_phones_id column to your table.. it will have the id value of relevant row from user_phones table
6 - when user is doing a search, filter by country id and and the phone number