Ik zou die tweede manier niet eens overwegen.
Je moet dan in twee tabellen dezelfde gegevens gaan bijhouden.
Daarnaast bewijfel ik ten zeerste dat de performance daar mee op vooruit gaat.
Houdt er ook rekening mee dat het (meestal) niet zinvol is om een index te hebben op een kolom waar weinig variatie is tussen de waarden die ie bevat, de optimizer zal dan waarschijnlijk die index negeren.
Ik adviseer je ook dat als je zoveel kolommen nodig hebt om tot een unieke PK te komen, om dan een auto_increment kolom als PK te gebruiken.
@Ger: Toevoeging: Het is wel zo dat mijn referentie-tabel (in mijn 2de manier) qua grootte nooit erg groot wordt, omdat indien de status een bepaalde waarde heeft dit record wordt verwijderd. Hierdoor zal het zoeken nooit erg lang duren, omdat deze tabel nooit erg groot wordt.
De eerste tabel, daar in tegen, zal steeds groeien omdat dat daar ook de main-gegevens in staan, die bewaard moeten worden.