MySQL alle prese con query in una relazione da uno a molti che soddisfa più condizioni

Questo è un divisione relazionale problema.

Il modo che suggerisci con il COUNT è probabilmente il più semplice 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

C'è un altro approccio con il doppio NOT EXISTS nell'articolo collegato ma poiché MySQL non supporta i CTE, sarebbe piuttosto ingombrante.