I've got a very large MySQL table with about 150,000 rows of data. Currently, when I try and run

SELECT * FROM table WHERE id = '1'; 

the code runs fine as the ID field is the primary index. However, recently for a development in the project, I have to search the database by another field. For example

SELECT * FROM table WHERE product_id = '1';

This field was not previously indexed, however, I've added it as an index but when I try to run the above query, the results is very slow. An EXPLAIN query reveals that there is no index for the product_id field when I've already added one and as a result the query takes any where from 20 minutes to 30 minutes to return a single row.

EDIT:

My full EXPLAIN results are:

| id | select_type | table | type | possible_keys        | key  | key_len | ref  | rows      | Extra       |
+----+-------------+-------+------+----------------------+------+---------+------+------+------------------+
|  1 | SIMPLE      | table | ALL  | NULL                 | NULL | NULL    | NULL |    157211 | Using where |
+----+-------------+-------+------+----------------------+------+---------+------+------+------------------+