I wrote a post detailing how to pick indexes to get the most out of mySQL here.
Here is a post about the mySQL optimizer and what you can do to speed up your SQL SELECT statements.
What I would like to share with you today, is that UPDATE and DELETE statements can also use optimizer tricks that SELECT uses. Its not documented on the mysql.com but it is possible to do something like
UPDATE [YOUR TABLE] USE INDEX(`your_index_name`) SET col='val' WHERE [columns that satisfy your index].
To see if you have problems with your UPDATE statements taking to much time I recommend 1st running INNODB as your storage engine since SHOW INNODB STATUS will indicate what index your long running UPDATE is using. This can be achieved by looking for /RECORD LOCKS space id.* index/ of SHOW INNODB STATUS.
Another indicator that you might need to force the optimizer to do the right thing is to track "Deadlock detected" from concurrent update statements; look at the where clause of your UPDATE statement.
Next solve your issues by telling mySQL to use the correct index when setting exclusive locks via the USE INDEX statement above.
Hope this helps.