Поддержание большого таблица уникальных значений в MySQL

Это, вероятно, обычная ситуация, но я не смог найти конкретного ответа на SO или Google.

У меня есть большая таблица (> 10 миллионов строк) дружественных отношений в базе данных MySQL, которая очень важна и должна поддерживаться таким образом, чтобы не было повторяющихся строк. В таблице хранятся идентификаторы пользователя. SQL для таблицы:

CREATE TABLE possiblefriends(
 id INT NOT NULL AUTO_INCREMENT, 
 PRIMARY KEY(id),
 user INT, 
 possiblefriend INT)

Таблица работает так, что у каждого пользователя есть около 1000 или около того «возможных друзей», которые обнаружены и должны быть сохранены, но следует избегать дублирования «возможных друзей».

Проблема состоит в том, что из-за конструкции программы в течение дня мне нужно добавить 1 миллион строк или более в таблицу, которые могут быть или не быть повторяющимися записями строк. Казалось бы, простой ответ - проверить каждую строку, чтобы увидеть, не является ли она дубликатом, а если нет, то вставить ее в таблицу. Но этот метод, вероятно, будет работать очень медленно, поскольку размер таблицы увеличится до 100 миллионов строк, 1 миллиарда строк или выше (что я ожидаю вскоре).

Каков наилучший (т.е. самый быстрый) способ поддерживать эту уникальную таблицу?

Мне не нужно всегда иметь под рукой таблицу только с уникальными значениями. Мне это нужно только раз в день для пакетных работ. В этом случае следует ли мне создать отдельную таблицу, которая просто вставляет все возможные строки (содержащие повторяющиеся строки и все), а затем в конце дня создать вторую таблицу, которая вычисляет все уникальные строки в первой таблице?

Если нет, то как лучше всего для этой таблицы в долгосрочной перспективе?

(Если индексы являются лучшим долгосрочным решением, скажите, пожалуйста, какие индексы использовать)