Radius Search Shortcuts

You've all seen those nifty searches which enable you to search for things near something else.  A few years ago I was faced with this problem and tackled it the only way I know how, by cheating. :)  Really, querying this isn't such a problem when your pool of available things isn't very big.  I mean really, How many Chicken-Marts are there in the country?  What happens when you need to search over, oh I don't know, let's say 10 million things.  Well, ideally I would have has access to a spatially enabled database.  Of course, if I did, then the story would have ended here.

Cheat #1

The biggest time saver I was able to do was get everyone to agree that nobody really cares down to the street level if a location is 25 miles from a certain zip.  You're already searching from the centroid of a zip as your focus point for the radius search.  The distance we're showing isn't going to be exact, so we make it a little worse by only geocoding our destinations down to the zip code level.  I just cut my possible search from 10 million to 40-something thousand.  Nice.  In case you are wondering, my zip coordinates table looks like this:

create table zip_coords(
   zip number,
   latitude number,
   longitude number

Cheat #2

I just did this one and this made a HUGE difference in the speed.  Of course, this is at the expense of disk space.  I precalculated the distances from one zip to every other zip within 150 miles.  I wrote a little program that pulled in my zip_coords values and did a nested loop over them to calculate the distances and only spooled out those less than 150 miles. This gave me a 67 million row table which looks like this:

create table zip_radius_map(
   zip_from number,
   zip_to number,
   radius number

Throw an index on this table and you are ready to faux-geo search with the quickness. Your radius search query is now as simple as:

select count(1) from records
inner join addresses using(address_id)
where zip in (
  select zip_to from zip_radius_map where zip_from=:zip and radius < :radius