(Firebird) SQL: 100x constraints in WHERE clause makes query extremely slow

Question

Hi,

I'm using Firebird and created a table, called EVENTS. The columns are:

id (INT) | name (VARCHAR) | category (INT) | website (VARCHAR) | lat (DOUBLE) | lon (DOUBLE)

Now a user wants to search for events in a certain radius around him, but entered only two or three letters of his home city. So we've got - lets say - 200 possible cities with their latitudes and longitudes. So my SQL query looks like:

SELECT id FROM events WHERE ((lat BETWEEN 30.09 AND 30.12) AND (lon BETWEEN 40.78 AND 40.81)) OR ((lat BETWEEN 30.09 AND 30.12) AND (lon BETWEEN 40.78 AND 40.81)) OR ...

So we get 200 constraints in the WHERE clause and it takes seconds to actually get the result.

I know the query might look horrible. But are the many constraints really the bottleneck? Can this query be optimized?

Thanks, Stefan

Answer 1

You could redesign database (if it is possible), to contain not only latitude and longitude, but also name of place of event. Your query would contain like statement, or similar (begins with?). I know, that this might be unusable solution, but constraining yourself to square (in spherical sense) cities or regions seems a bit odd to me ;)

Answer 2

My guess would be that the database engine decides that the criterion will likely return a lot of rows, so it wrongly full scans the table. Hint it to do the right thing, or perform some kind of rewrite of the query e.g. (which might or might not help)

SELECT id
  FROM cities c
  JOIN events e ON (e.lat BETWEEN c.lat - .01 AND c.lat + .01) AND (e.lon BETWEEN c.lon - .01 AND c.lon + .01)
 WHERE c.name LIKE 'x%'

In SQL server you could write

SELECT id
  FROM cities c
  INNER LOOP JOIN events e ON (e.lat BETWEEN c.lat - .01 AND c.lat + .01) AND (e.lon BETWEEN c.lon - .01 AND c.lon + .01)
 WHERE c.name LIKE 'x%'

to ensure the correct plan (you do have an index on the lat and lon columns together?)

Answer 3

Create a range search friendly index (a B-tree index) on events.lat and/or events.long (but not a single index on both!) That will at least get you in the ballpark.

What you really want is an R-Tree or similar, which allows indexing multi-dimensional data and gives you good range search performance. PostgreSQL has GiST for that; I don't know what kind of support Firebird has for this sort of problem.

Wiki links for more info: http://en.wikipedia.org/wiki/R-tree http://en.wikipedia.org/wiki/GiST

Answer 4

You should first use IBExpert over your query to check it's plan to see why is it so slow.

Answer 5

Tradeoff space for speed:

Cities don't move. Whenever you add an event, you can pre-calculate the distance between each event and each city, and store the distance to all nearby cities. You can index this by city, so you can directly find events somewhat near a given city (or near 200 cities with the same prefix). Actual longitude/latitude filtering can then be restricted to a much smaller set of events.

Answer 6

Try with a correlated subquery :

select *
from events e
where exists
( select *
  from cities c
  where c.name like 'X%' and
        e.lat BETWEEN c.lat - .01 AND c.lat + .01 and
        e.lon BETWEEN c.lon - .01 AND c.lon + .01
)

Im some scenarios it works faster than joins.