Tienes muchas formas de usar left join with is null o not exists
Select
un.user_id
from user_notifications un
left join user_push_notifications upn
on upn. user_id = un.user_id and un.notification_id = 'xxxxyyyyyzzzz'
where upn. user_id is null
Select
un.user_id
from user_notifications un
where
un.notification_id = 'xxxxyyyyyzzzz'
and not exists
(
select 1 from user_push_notifications upn
where
un.user_id = upn.user_id
and upn.notification_id = 'xxxxyyyyyzzzz'
)
Para aumentar el rendimiento, es posible que deba agregar un índice si aún no se ha agregado
alter table user_notifications add index user_notifi_idx(user_id,notification_id);
alter table user_push_notifications add index user_notifp_idx(user_id,notification_id);
