Каждое обновление или удаление в указанном столбце требует, чтобы база данных проверила все ссылающиеся столбцы на наличие нарушений целостности. Каждая из этих проверок требует проверки ссылочных столбцов, чтобы определить, используют ли они значение, которое должно быть изменено или удалено.
Таким образом, проверка целостности FK требует большого количества запросов к столбцам, которые ссылаются на него. Добавление индексов к этим столбцам значительно ускоряет проверку целостности. Если бы не было индексов в ссылочных столбцах, то изменение ссылочного столбца (или удаление строки, на которую указывают FK) потребовало бы сканирования таблицы для каждой таблицы, которая ссылается на него. Сканирование таблиц не ваш друг, но ФК, безусловно, являются.