Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

The following query is looking for all towns that are between 5 and 10 kilometers from a hard-coded latitude/logitude (=another town actually). I have 37010 towns.

I'm using Symfony 2 which "creates" a query through Doctrine. This query is flagged by my MariaDB server as "not using indexes". I dont know what's going on, because: (1) Here's the query:

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;

Here's the time:

# 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

And here's the table:

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]>

If I do an explain on this query i get:

+------+-------------+-------+------+---------------+------+---------+------+-------+----------------+
| 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 row in set (0.00 sec)

I have 37010 towns and MariaBN tells me Rows_examined: 37030. I dont get that. Anyway, how would you optimize it?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

The problem is that you are only filtering by that large calculation so there is no choice but to do a full table scan and calculate that formula for every row.

You could limit the number of rows considered by adding an index on the lat and long columns and filter by an approximate square as well as the exact crow-flies calculation. That way the query runner should be able to seek using that index to find those in the larger area of the square ("x between n1 and n2 & y between n3 and n4" should use that index (an index seek followed by a partial scan)) then only need to lookup & read the full rows and do the calc & sort on those few matches to find the final filtered/limited set.

If you have the chance to consider changing database backend at this point in your project some (postgres with the PostGIS extensions for example) support special types and indexes for handling geometry data (even sometimes natively supporting lat/long based calculations), though that change may be overkill if this is the only part of your application that would make use of it.

share|improve this answer

The problem is this:

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

If this calculation is always the same you can add an extra DB field (sclr5) that holds this information. You may update the DB table with one query, if the table is static (no new rows will be imported) or with a trigger if you regularly add new rows.

Then you can add a B-tree index to the sclr5 DB field to accelerate the sclr5 > 4 AND sclr5 <= 10 and the ORDER BY sclr5 clauses.

share|improve this answer
    
I think i could pre-calculate COS(RADIANS(v0_.lat)) and make it a column lik lat_cos_rad and then lng_cos_rad and lat_sin_rad. But RADIANS(3.16710500)) and SIN(RADIANS(50.58907000)) are not static: they come from the town the user has chosen. –  Olivier Pons Apr 4 at 19:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.