Søg + sort = meget lang tid - kan det være rigtigt?

Jeg har lavet nogle tests på min sql-server, for at finde ud af hvorfor et specifikt sql-kald kørte meget langsomt.

Jeg laver 4 tests:
1: Jeg selecter alt
2: Jeg selecter alt og sorterer
3: Jeg søger på user_id = '0'
4: Jeg søger på user_id = '0' og sorterer

Test 1, 2 og 3 blev udført på under 0,0020 sekunder. Men test 4 tager omkring 1,5-1,6 sekunder.

Herunder kan i se kaldene/resultaterne:
SQL query:
SELECT *
FROM `spillere`
LIMIT 0 , 30
(168090 total, Query took 0.0018 sec)


SQL query:
SELECT *
FROM `spillere`
WHERE 1
ORDER BY `vaerdi` ASC
LIMIT 0 , 30
(168090 total, Query took 0.0020 sec)



SQL query:
SELECT *
FROM `spillere`
WHERE `klub_id` =0
LIMIT 0 , 30
(125531 total, Query took 0.0020 sec)



SQL query:
SELECT *
FROM `spillere`
WHERE `klub_id` =0
ORDER BY `vaerdi` ASC
LIMIT 0 , 30
(125531 total, Query took 1.6018 sec)

Kan det virkelig passe at test 4 skal være så langsom? Jeg kan jo se at det tager 0,002 sekunder at finde records med user_id = '0' (test 3), og min logiske sans siger mig at sorteringen vil tage kortere tid end i test 2 eftersom der er færre rækker at sortere på. Derfor kan jeg simpelthen ikke begribe hvorfor test 4 tager så lang tid? Det kan ikke være rigtigt! ;)

Så vidt jeg ved har det ingen effekt - men jeg har forsøgt at sætte et index på rating (og jeg har naturligvis index på user_id).

Test 4 giver i øvrigt følgende ved en EXPLAIN:

id      select_type      table      type      possible_keys      key      key_len      ref      rows      Extra
1     SIMPLE     spillere     ALL     klub_id     NULL     NULL     NULL     126068     Using where; Using filesort