, если вы не используете первичный ключ, потому что ваш запрос требует объединения на основе других столбцов
убедитесь, что у вас правильный индекс в столбцах ON и WHERE *
SELECT user_views.view
FROM user_views
JOIN user_departments ON user_views.user_id = user_departments.user_id
WHERE user_departments.department_id = 123
в вашем случае
on table user_views composite index on (user_id, view)
добавлен столбец представления для того, чтобы значение непосредственно формировало индекс, а также избегало доступа к таблице данных
on table user_departments index on (department_id, user_id)
таким образом, представление правильно управляется ..
Обновлено для OP обновленная версия
в силу того, что все таблицы заполнены первичным и внешним ключами, разница между двумя запросами должна быть очень мала.
и стратегии, принятые движком SQL
SELECT user_views.view
FROM users JOIN user_views ON users.id = user_views.user_id
JOIN user_departments ON users.id = user_departments.user_id
WHERE user_departments.department_id = 1234;
SELECT user_views.view
FROM users
JOIN user_views ON users.id = user_views.user_id
JOIN user_departments ON users.id = user_departments.user_id
JOIN departments ON departments.id = user_departments.department_id
WHERE departments.id = 1234;
Наилучшая производительность может быть получена при использовании составного индекса, получающего всю информацию для фильтрации и выбираемого непосредственно в таблице индексов и избегающего доступа (и пустой траты времени) к данным таблицы.