Domnívám se, že váš dotaz pravděpodobně odpovídá velkému procentu dat v tabulce. V situacích, jako je tato, se optimalizátor MySQL často rozhodne prohledat tabulku a zcela ignorovat indexy, protože je to ve skutečnosti rychlejší, než procházet potížemi s dalším čtením celého indexu a jeho používáním k vybírání dat. Takže v tomto případě předpokládám, že public_private='yes' and approved='yes' odpovídá velké části vašeho stolu. Pokud tedy MySQL přeskočí použití indexu kvůli tomu, pak není k dispozici ani pro řazení.
Pokud opravdu chcete, aby používal index, řešením by bylo použít FORCE INDEX :
select * from videos FORCE INDEX (approved_2) where public_private='public' and approved='yes' order by number_of_views desc;
Provedl bych však nějaké testy, abych se ujistil, že to, co získáváte, je ve skutečnosti rychlejší než to, co se rozhodl dělat optimalizátor MySQL. Zřejmě optimalizátor má nějaké problémy s výběrem pro objednávání, takže byste to určitě mohli zkusit a zjistit, zda dosáhnete lepšího výkonu.