SQLite - Index for rectangle intersection without GIS extension

Question

I have a quite large SQLite database to store some geo-data. I can't use the GIS extension and i'd also like everything to work with other databases as well.

My table structure is the following:

tbl(float fromLon, float fromLat, float toLon, float toLat, binary binaryData)

i store some binary-data within the database (the polygon of something) and store it's bounding-box in the form of fromLon,fromLat -> toLon,toLat.

Next i have some queries like "give me all binaryData (polygons) that are within this region (reqLlon1,reqLat1)-(reqLon2,reqLat2)". a sample query would be:

SELECT binaryData
FROM tbl WHERE
(reqLon1 < toLon) AND
(reqLat1 < toLat) AND
(reqLon2 > fromLon) AND
(reqLat2 > fromLat) 

The problem is, it seems that i can't figure the right index to speed things up.. a simple index like

idx1(fromLon,fromLat,toLon,toLat)

does not work out. I tried the same thing with MySQL (same layout, same index) and it states (explain select ..) that it only uses half of the index's length..

can someone give me a hint what the index should look like to work out? or could it be, that it's impossible?

Answer 1

You should consider using the R*Tree module.

An R-Tree is a special index that is designed for doing range queries. R-Trees are most commonly used in geospatial systems where each entry is a rectangle with minimum and maximum X and Y coordinates. Given a query rectangle, an R-Tree is able to quickly find all entries that are contained within the query rectangle or which overlap the query rectangle. This idea is easily extended to three dimensions for use in CAD systems. R-Trees also find use in time-domain range look-ups.