Adding an index to an existing Mysql table turns out to be easy. And it is fast too. I added an index to a table with roughly 10 million rows. It took the database less than 2 minutes to add the index.
ALTER TABLE `table` ADD INDEX `product_id` (`product_id`)Source: stackoverflow.com/a/3002635