Otimize a consulta com índices

A consulta a seguir procura todas as cidades que estão entre 5 e 10 quilômetros de uma latitude/logitude codificada (=outra cidade, na verdade). Eu tenho 37010 cidades.

Estou usando o Symfony 2 que "cria" uma consulta através do Doctrine. Esta consulta é sinalizada pelo meu servidor MariaDB como "não usando índices". Não sei o que está acontecendo, porque: (1) Aqui está a consulta:

SELECT
    v0_.id AS id0,
    v0_.nom AS nom1,
    v0_.url AS url2,
    v0_.cp AS cp3,
    v0_.insee AS insee4,
    ROUND(
        6371 *
        ACOS(COS(RADIANS(50.58907000)) *
        COS(RADIANS(v0_.lat)) *
        COS(RADIANS(v0_.lng) -
        RADIANS(3.16710500)) +
        SIN(RADIANS(50.58907000)) *
        SIN(RADIANS(v0_.lat))), 2
    ) AS sclr5
    FROM ville v0_
    HAVING sclr5 > 4 AND sclr5 <= 10
    ORDER BY sclr5 ASC LIMIT 20 OFFSET 0;

Aqui está a hora:

# User@Host: x[x] @ localhost []
# Thread_id: 1514  Schema: mydatabase  QC_hit: No
# Query_time: 0.071503  Lock_time: 0.000137  Rows_sent: 20  Rows_examined: 37030

E aqui está a tabela:

MariaDB [mydatabase]> desc ville;
+-----------------+---------------------+------+-----+---------+----------------+
| Field           | Type                | Null | Key | Default | Extra          |
+-----------------+---------------------+------+-----+---------+----------------+
| id              | bigint(20) unsigned | NO   | PRI | NULL    | auto_increment |
| id_origine      | bigint(20) unsigned | YES  | MUL | NULL    |                |
| date_v_creation | datetime            | YES  | MUL | NULL    |                |
| date_v_debut    | datetime            | YES  | MUL | NULL    |                |
| date_v_fin      | datetime            | YES  | MUL | NULL    |                |
| article         | varchar(4)          | YES  |     |         |                |
| nom             | varchar(150)        | NO   | MUL |         |                |
| url             | varchar(150)        | NO   | MUL |         |                |
| cp              | varchar(10)         | NO   | MUL | NULL    |                |
| insee           | varchar(10)         | NO   |     |         |                |
| id_region       | bigint(20) unsigned | NO   | MUL | NULL    |                |
| id_departement  | bigint(20) unsigned | NO   | MUL | NULL    |                |
| lat             | decimal(15,8)       | NO   | MUL | NULL    |                |
| lng             | decimal(15,8)       | NO   |     | NULL    |                |
| sound           | varchar(252)        | YES  | MUL | NULL    |                |
+-----------------+---------------------+------+-----+---------+----------------+
15 rows in set (0.01 sec)

MariaDB [mydatabase]>

Se eu fizer uma explicação sobre esta consulta, recebo:

+------+-------------+-------+------+---------------+------+---------+------+-------+----------------+
| id   | select_type | table | type | possible_keys | key  | key_len | ref  | rows  | Extra          |
+------+-------------+-------+------+---------------+------+---------+------+-------+----------------+
|    1 | SIMPLE      | v0_   | ALL  | NULL          | NULL | NULL    | NULL | 36510 | Using filesort |
+------+-------------+-------+------+---------------+------+---------+------+-------+----------------+

1 carreira em conjunto (0,00 seg)

Eu tenho 37.010 cidades e MariaBN me diz Rows_examined: 37030. Eu não entendo isso. De qualquer forma, como você o otimizaria?