Meines Erachtens wäre es effizienter, eine weitere Tabelle anzulegen, die die Felder stadt_id und plz enthält und einen Unique-Index über beide Felder zu legen, dann bräuchte man keinen Full-Table-Scan.
Die Idee hatte ich auch schon. Gute Idee, danke für deine Überlegungen :)