в вашем примере 1000 * 1000 означает, что каждый пользователь дружит со всеми. Зачем вообще хранить ассоциации?
Это действительно будет так? Или вы просто проверяете теоретический предел?
И вы собираетесь хранить две копии каждой ассоциации? Скажем, пользователь 1 и пользователь 2 - друзья. Вы собираетесь иметь таблицу с этими двумя строками:
UserId, Friend_UserId
1 2
2 1
Это удвоит объем необходимых данных. Вы должны установить правило, согласно которому нижний из двух идентификаторов всегда находится в одном столбце.
И, конечно же, убедитесь, что вы индексировали оба столбца.