[Animats]

Right. MySQL's optimizer knows how many records each table has, but not much else. It doesn't do statistical tests on the tables. Depending on table contents, "WHERE b=X" can select any number of records, from zero to the whole database. Whether the optimal strategy is to do the "WHERE b=X" first, possibly getting a large number of hits, or simply making a sequential pass, is not decidable from the database size only.

An alternative would be for the optimizer to do an indexed SELECT on b for "WHERE b=X", and if the number of hits exceeded some threshold, abandon that effort as inefficient and start over using a sequential pass. But MySQL doesn't abandon strategies once selected, or keep such statistics as a hint for future queries. As someone pointed out, Oracle's flagship database product does do that. Anyone know about Postgres?