Você pode usar uma junção interna para filtrar linhas que tenham uma linha correspondente em outra tabela:
SELECT DISTINCT records.id
FROM records
INNER JOIN data d1 on d1.id = records.firstname AND data.value = "john"
INNER JOIN data d2 on d2.id = records.lastname AND data.value = "smith"
Uma das muitas outras alternativas é um
in cláusula:SELECT DISTINCT records.id
FROM records
WHERE records.firstname IN (
select id from data where value = 'john'
) AND records.lastname IN (
select id from data where value = 'smith'
)
