I suppose what you say might be true for some database engines.
On other database engines the method would be a=something scan the index on a and put pointers to the rows where a=something in a result set, do the same for b in the index on b, sort and merge to get result.
On a proper engine and hardware this would be very fast.
It would never entail the calisthenics you suggest wouldn't be performed. What would happen where that one result set was created from the first operation (finding phone# in phonebook), then joined with the set of finding zip in zipbook.
Never would it lead to the zip being looked up in the phonebook.
What you need to do is put the most restrictive predicates first. That is, you need to know something about your data. If you know that it is way fewer matches to one part of the query than to another, use the one with fewest matches first:
select * from students
where
grade='A'
and
sex='female'
We know that there are fewer grade 'A' (say 5% of the population) students than there are female students (about 50% of the population).
Back to your query SELECT * FROM t1 WHERE col2=1 AND col4=1; If you never do a search on col4 only, then PRIMARY KEY (id), KEY foo (col2,col4); is acceptable. If you do need to search col4 only sometimes, you'll need your first indexing option.
If you don't need to access col2, then you'll shift the (col2,col4) to (col4,col2). Finally, if there are many different values in col4 and fewer in col2, then you'll go for the (col4,col2), if the converse is true, then you'll go for (col2,col4), because going through that order is more efficient.
In the end you need to anlyze your needs, and know abit of what you'll do, and which data you have.
