How do I add indexes to MySQL tables?

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, for a recent 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 one, so mysql now indexes the field, but when I try to run the above query, it runs very slowly. 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. 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 | +----+-------------+-------+------+--------------+------+---------+------+-------+------------------+ It might be helpful to note that I've just taken a look, and ID field is stored as INT whereas the PRODUCT_ID field is stored as VARCHAR. Could this be the source of the problem?