Parece que você precisa usar
GROUP BY e HAVING cláusulas. 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 */
Certifique-se de ter um índice exclusivo em
product_id e attr_id para que isso funcione corretamente (você já deve ter isso, pois provavelmente não faria sentido para um produto ter vários registros com o mesmo attr_id ). Você também precisa ter certeza de que está escapando seus valores para uso em seu SQL, se ainda não estiver. Estou mostrando essas variáveis aqui com
? que, se você estiver usando instruções preparadas, seria uma maneira de escrever esse SQL. 
