MySQL se potýká s dotazem v jednom až mnoha vztazích, které odpovídají více podmínkám

Toto je relační rozdělení problém.

Způsob, který navrhujete pomocí COUNT je pravděpodobně nejjednodušší v 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

Existuje další přístup s dvojitým NOT EXISTS v odkazovaném článku, ale protože MySQL nepodporuje CTE, bylo by to docela těžkopádné.