Я полагаю что у вас в условиях опечатка и option_id все-таки уникально описывает возможный параметр.
Если это не так, мои запросы нужно будет переписать под уникальное условие (ну или навести порядок в структуре данных что больнее, но в целом правильнее)
Самый простой вариант решения:
select product.* from product where
product_id in ( select product_id from product_options where option_id = 5 and option_value = "Красный" )
and
product_id in ( select product_id from product_options where option_id = 6 and option_value = "35" )
В ряде случаев может быть выгоднее с точки зрения быстродействия делать подзапросы на получение id отвечающих каждой категории отдельно, а объединять их на языке программирования.
Заодно это позволит делать нечеткий поиск, например когда совпадения не полные.
Если хочется поизвращаться можно поэкспериментировать с запросом вида
select product.product_id, count(product_options.id) cnt from product
join product_options on product_options.product_id = product.product_id AND ((option_id = 5 and option_value = "Красный" ) or (option_id = 6 and option_value = "35" ))
group by product.product_id
having cnt = 2
На ряде запросов это может быть быстрее
PS Вообще есть мнение что решать это на Sql в реальном проекте не очень правильно с точки зрения нагрузки, лучше какой-нибудь elastic search прикрутить.