Does MySQL exectution plan depend on available indexes?
MySQL's optimizer looks only at what indexes are available.

There is an exception in 5.6:  If you have a subqueries such as
FROM ( SELECT ... ) JOIN ( SELECT ... ) ..., there are no indexes on the temporary tables that are created.  This used to lead to terrible performance.  Now, the optimizer will try out various indexes, and create the best one for the tmp table.  I suspect it only looks for single-column indexes, not "compound" indexes

InnoDB is getting the most attention these days.  MyISAM does not have any tricks up its sleeve.

Try out my Cookbook for creating the best index, given a SELECT.  It may save you some false starts.