Multi column index for querying a range of values from two columns

Question

My SQLite database stores location data as latitude and longitude values. I will frequently have to query the database using the following query:

SELECT * FROM locations WHERE latitude > 22.2 && latitude < 22.3 && longitude > 50.7 && longitude < 50.8

Would a multi-column index on the latitude and then the longitude help to speed up the queries? This answer provides the way the query can be carried out with a multi-column index, but the comment accompanying it mentions that it will not work in SQLite.

Answer 1

Based on this SO answer just putting an index on the latitude column should help the query in a meaningful way. Assuming you can provide a narrow enough latitude range, SQLite would only have to scan a relatively few number of records by longitude.

Answer 2

Consulted the docs. I believe the multi column index would still be useful.

The right-most column that is used can employ inequalities.

Suppose your index is on (lat, long). Then lat will be "used" and long will not be "used". This all depends on what "used" means.

My guess is that "using" an index means applying access strategies which benefit from the index's sort order. Such a strategy would be to seek the first matching row with a search that relies on the order and read continuously to the last matching row.

I strongly suspect, that after using lat, the rows in the index will be scanned and compared for their long values. By filtering in the index, costly table lookups will be avoided. Only matching rows will have table lookups.

If the index were to be on (lat) only, then every qualifying lat row would table lookup.

As always in query optimization, examine execution plans and measure IO.