Creo que la consulta que tiene probablemente coincida con un gran porcentaje de los datos de la tabla. En situaciones como esta, el optimizador de MySQL a menudo elige hacer un escaneo de la tabla e ignorar los índices por completo, ya que en realidad es más rápido que pasar por el problema de la lectura adicional de todo el índice y usarlo para seleccionar los datos. Entonces, en este caso, supongo que public_private='yes' and approved='yes' coincide con una buena parte de su mesa. Por lo tanto, si MySQL omite el uso del índice debido a esto, tampoco estará disponible para ordenar.
Si realmente desea que use un índice, entonces la solución sería usar FORCE INDEX :
select * from videos FORCE INDEX (approved_2) where public_private='public' and approved='yes' order by number_of_views desc;
Sin embargo, ejecutaría algunas pruebas para asegurarme de que lo que está obteniendo es realmente más rápido que lo que el optimizador de MySQL ha elegido hacer. Aparentemente, el optimizador tiene algunos problemas con la realización de selecciones para realizar pedidos, por lo que definitivamente podría intentarlo y ver si obtiene un mejor rendimiento.
