Я бы использовал внутренние соединения. Это даст меньший набор результатов и тот, который вы хотите.
Вы пробовали этот запрос?
select r.recordname
from records r
left join values link on link.recordid = r.id and link.valname = 'myvalue'
left join keys k on r.keyid = link.key.id and k.keyname = 'mykey'
Тем не менее, я думаю, что реальный способ сделать это состоит в том, чтобы иметь 4 таблицы
table records: id recordname
table keys: id keyname
table values : id valuename
table joins : id recordid keyid valueid
Тогда (с правильными индексами) вы можете получить запрос, подобный этому
select r.recordname
from joins j
left join records r on j.recordid = r.id
left join keys k on j.keyid = k.id
left join values v on j.valueid = v.id
where v.valuename = 'myvalue' and k.keyname = 'mykey'
Это должно быть довольно быстро ... все, что нужно сделать, это найти идентификатор в значениях и ключах, а затем выполнить сканирование на j. Если у вас есть правильные индексы, они будут быстрыми.