query speed advice

I have the following query:
"
SELECT DISTINCT userid,few_other_fields
FROM search_index u FORCE INDEX(search_us_country)
WHERE u.gender=1 AND u.age_id=2 AND u.country_id=226
ORDER BY created DESC, photo_set DESC, last_login DESC
"
Where search_us_country is INDEX (gender,age_id,country_id,state_id,city_id,created,photo_set ,last_login)

Here information from Explain:
[id] => 1
[select_type] => SIMPLE
[table] => u
[type] => refble
[possible_keys] => search_us_country
[key] => search_us_country
[key_len] => 3
[ref] => const,const,const
[rows] => 78302
[Extra] => Using where; Using temporary; Using filesort

The query seems very slowly ( even when I am adding state_id=# AND city_id=# after country_id option in WHERE.)
Table search_index has ~ 400.000 records, but I think table gona be 2-3M in future.

I can’t understand how build INDEX or maybe serveral indexs to quickly queries with different ORDER BY. When I am use “ORDER BY”, query is very SLOW ) without ORDER BY - query seems fast. So, my idea that maybe to create right INDEX and use QUERY without ORDER BY.

ORDER BY could be in
1 variant: created DESC, photo_set DESC, last_login DESC
2 variant: last_login DESC, photo_set DESC
3 variant: total_view DESC, photo_set DESC, last_login DESC

photo_set is 0 or 1 ( like profile has photo or hasn’t photo)
total_view just intereger (0-10000)
created,last_login - datetime fields.

Can you give advice ? What’s right way ? Make several index (like - search_1(field1,field2,etc) ; search_2(field1,field4,etc) and don’t use ORDER BY somehow Or anyway I’ve to use ORDER BY if I want sort

Thank you so much.

Sorry, forgot in my post, I am use LIMIT #, 12 too…
Thanks.