I don't know much about InnoDB's clustered index, but if it is like Oracles IOT's, then normally its more expensive to do inserts (than for a heap table) as it has to put the data into a specific place, but cheaper to find related data when its queried due to all the data being stored together.

In this case, that extra 'expense' was easily off-set by the savings giving a great speed up. It does teach a good lesson though, which is index as little as possible by using composite indexes where you can!

In databases its amazing how 1 bad table/query/index can hose the performance of the either database - and once you find it, you get such a performance boost!