When optimizer considers different indexes for a query, for every index it needs to know

• what columns are part of the index
• the index cardinality
• records_in_range — number of values within a specific constant range

Note that the first question doesn't need the index to be created. And the other two can be answered from EITS, so they don't need an index either.

So, the optimizer should, technically, be able to create an execution plan that uses an index, even if the index does not exist! This could be incorporated into a new explain mode, say EXPLAIN SUGGEST_INDEXES that will return what indexes (if created) would reduce the query execution cost and how.