Re: Statistics used by optimizer.
MyISAM and InnoDB get their statistics different ways:
MyISAM always maintains COUNT(*) for the table; it uses ANALYZE TABLE to get some statistics for cardinality of indexes.
InnoDB probes 10 random spots in the table whenever you 'open' the table. This is fast, but can be inadequate for a good query plan choice.
When optimizing a particular SELECT, with particular values in the WHERE clause, MySQL (both engines) will look into the index to get a better feel for the cardinality for the particular value. It will use the information gleaned to pick the 'best' query plan. Different values can lead to different query plans. This might be an example of such:
CREATE TABLE x
...
INDEX (a), -- a is usually 0; a = 999 once
INDEX (b), -- b is usually 0; b = 999 once
);
SELECT ... WHERE a=0 AND b=999; -- will use INDEX(b)
SELECT ... WHERE a=999 AND b=0; -- will use INDEX(a)
(I won't delve into the theory of histograms.)