Dies ist ein relationale Teilung Problem.
So wie Sie es mit dem COUNT
vorschlagen ist wahrscheinlich das einfachste in MySQL
SELECT product_id
FROM product_attributes pa
WHERE (attribute='size' and value='medium')
OR (attribute='colour' and value='blue')
GROUP BY product_id
HAVING COUNT(DISTINCT CONCAT(attribute,value) ) = 2
Es gibt einen anderen Ansatz mit doppeltem NOT EXISTS
im verlinkten Artikel, aber da MySQL keine CTEs unterstützt, wäre das ziemlich umständlich.