Det låter som att du behöver använda GROUP BY och HAVING klausuler.
SELECT
`product_id`,
COUNT (`primary_key_id`) AS `attr_count` /* primary key field here */
FROM `products_attr_val`
WHERE
(`attr_id` = ? AND `value_id` = ?)
OR (`attr_id` = ? AND `value_id` = ?)
/* additional as necessary
OR (`attr_id` = ? AND `value_id` = ?)
*/
GROUP BY `product_id`
HAVING `attr_count` = ? /* value here should be equal to number of attributes you are checking for */
Se till att du har ett unikt index över product_id och attr_id för att detta ska fungera ordentligt (du borde redan ha detta eftersom det sannolikt inte skulle vara vettigt för en produkt att ha flera poster med samma attr_id ).
Du måste också se till att du undviker dina värden för användning i din SQL om du inte redan gör det. Jag visar dessa variabler här med ? vilket, om du använder förberedda satser, skulle vara ett sätt att skriva denna SQL.