Optimizing Sqlite query for INDEX

Question

Hello, I have a table of 320000 rows which contains lat/lon coordinate points. When a user selects a location my program gets the coordinates from the selected location and executes a query which brings all the points from the table that are near. This is done by calculating the distance between the selected point and each coordinate point from my table row. This is the query I use:

select street from locations 
where (  ( (lat - (-34.594804)) *(lat - (-34.594804)) ) + ((lon - (-58.377676 ))*(lon - (-58.377676 ))) <= ((0.00124)*(0.00124))) 
group by street;

As you can see the WHERE clause is a simple Pythagoras formula to calculate the distance between two points. Now my problem is that I can not get an INDEX to be usable. I've tried with

CREATE INDEX indx ON location(lat,lon) 

also with

CREATE INDEX indx ON location(street,lat,lon) 

with no luck. I've notice that when there is math operation with lat or lon, the index is not being called . Is there any way I can optimize this query for using an INDEX so as to gain speed results?

Thanks in advance!

Answer 1

Surely you have a primary key in locations? Probably called id?

Why not just select the id along with the street?

select id, street from locations 
where (  ( (lat - (-34.594804)) *(lat - (-34.594804)) ) + ((lon - (-58.377676 ))*(lon - (-58.377676 ))) <= ((0.00124)*(0.00124))) 
group by street;

Answer 2

Did you try adjusting the page size? A table like this might gain from having a different (i.e. the largest?) available page size.

PRAGMA page_size = 32768;

(Or any power of 2 between 512 and 32768 (http://sqlite.org/pragma.html#pragma_page_size). If you change the page_size, don't forget to vacuum the database (assuming you are using SQLite 3.5.8. Otherwise, you can't change it and will need to start a fresh new database).

Also, running the operation on floats might not be as fast as running it on integers (big maybe), so that you might gain speed if you record all your coordinates times 1 000 000.

Finally, euclydian distance will not yield very accurate proximity results. The further you get from the equator, the more the circle around your point will flatten to ressemble an ellipse. There are fast approximations which are not as calculation intense as a Great Circle Distance Calculation (avoid at all cost!)

Answer 3

Hey! Thanks for your answer!!, i've tried using the Great Circle Distance Calculation and as you said it is a very intense calculation, do you know any faster way to calculate coordinate distances?