Vous pouvez utiliser l'agrégation ici :
SELECT job_id
FROM skill_usage
WHERE skill_id IN (3, 4)
GROUP BY job_id
HAVING MIN(skill_id) <> MAX(skill_id);
Cette requête doit bénéficier de l'index suivant :
CREATE INDEX idx ON skill_usage (skill_id, job_id);
Le WHERE
et HAVING
les clauses, telles qu'elles sont écrites, sont sargables , et devrait pouvoir profiter de cet index.