MySQL kæmper med forespørgsler i et til mange forhold, der matcher flere betingelser

Dette er en relationel opdeling problem.

Den måde, du foreslår med COUNT er nok den nemmeste i 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

Der er en anden tilgang med dobbelt NOT EXISTS i den linkede artikel, men da MySQL ikke understøtter CTE'er, ville det være ret besværligt.