Как выбирать в базе данных уникальные значения, сравнивая два массива?

База данных имеет таблицу "Контакты", в которой ~100.000 строк.
Пользователям №1 и 2 принадлежит по 1000 строк (контактов) из этой таблицы.
Примерно 30% контактов этих пользователей совпадают (то есть это одни и те же строки из таблицы "Контакты").

Нужно сделать так, чтобы пользователь №1 получил список тех контактов пользователя №2, которых нет у пользователя №1.

Пользователь №1 может быстро добавлять себе контакты пользователя №2, после чего список не совпадающих контактов нужно обновлять.

Какую базу данных для этого использовать и как это правильно реализовать?
Мне не приходит в голову ничего, кроме простых регулярных функций. Но вот проблема, если у этих пользователей по 10.000 контактов и 90% из них совпадает, то регулярная функция уже будет тяжела. А если добавлять к каждому контакту список пользователей, у которых есть этот контакт, то проблемы будут, когда 1000+ пользователей добавят этот контакт, так как придется каждый раз запрашивать полный список пользователей, имеющих этот контакт, добавлять еще одного пользователя и сохранять потом все это.
С NoSQL не работал, но если это то, что мне нужно - то я изучу это.