Медленный запрос MySQL: JOIN + multiple WHERES + ORDER BY

давно скрывающийся, первый вопрос!

Я пытается оптимизировать этот запрос, который выбирает товары с самой низкой ценой, которые соответствуют выбранным фильтрам:

SELECT product_info.*, MIN(product_all.sale_price) as sale_price, product_all.buy_link
FROM product_info
NATURAL JOIN (SELECT * FROM product_all WHERE product_all.date = '2010-09-30') as product_all
WHERE (product_info.category = 2  
AND product_info.gender = 'W' )
GROUP BY product_all.prod_id
ORDER BY MIN(product_all.sale_price) ASC LIMIT 13

Объяснение:

| id | select_type | table        | type   | possible_keys                                             | key     | key_len | ref                 | rows   | Extra                           |  
+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+  
|  1 | PRIMARY     | <derived2>   | ALL    | NULL                                                     | NULL    | NULL    | NULL                | 89801  | Using temporary; Using filesort | 
|  1 | PRIMARY     | product_info | eq_ref | PRIMARY,category_prod_id_retail_price,category_ret...     | PRIMARY | 4       | product_all.prod_id | 1      | Using where                     | 
|  2 | DERIVED     | product_all  | ref    | date_2                                                    | date_2  | 3       |                     | 144107 |                                 | 

Я попытался удалить подзапрос, -какие индексы оптимизировали бы этот запрос?
-не важно: как меняется подход к индексации при добавлении или удалении предложений WHERE или использовании другого ORDER BY, например сортировки по% off:

ORDER BY (1-(MIN(product_all.sale_price)/product_info.retail_price)) DESC  

edit: естественное соединение обоих запросов действует на prod_id (одна запись в product_info может иметь несколько экземпляров в product_all, поэтому их нужно сгруппировать)