Hitta rader i A som inte har en tillhörande rad i B, där FK är på B?

Du letar efter NOT EXISTS :

SELECT 
  * 
FROM 
  a
WHERE
  NOT EXISTS (SELECT 1 FROM b WHERE a_id = a.id)

Att ha ett index på b.a_id hjälper den här frågans prestanda.