[Resolved] Massive MySQL Query: Suggestions for Optimizing?

cbj4074

Hi everyone,

I'm undertaking the task of building a "store locator". I know one can purchase a pre-built store locator for a couple/few hundred dollars, but I'm not doing this to save money, I'm doing it to learn how.

I bought a zip code database that contains 70,467 rows of data and brought it into a MySQL database. I stripped the things I didn't need from each row, so I am left only with the following columns:

zip_id (PRIMARY), ZipCode, LatitudeRad, LongitudeRad

The lat./lon. values are in radians so they can be used with the Great Circle formula to calculate the distance between the center of two geographical regions, based on the zip codes of those regions.

I have a second database of retail store locations, which contains 78 rows. Each row has about 21 fields, such as id, store_name, several fields for the components of the address (e.g. line1, line2, area_code, phone_prefix, phone_suffix, zip), email_address, website, etc.

In summary, the code posted below gathers the zip codes (and row id's) of every record in the retail store database, and then calculates the distance, in miles, between the store zip code and the "user's" zip code. If the distance is within the specified search radius, the retail store id is added to an array for a future query of matching stores (which I haven't yet done).

This code works quite well, but I just want to ensure that it's being executed as quickly as possible. To check the 77 store locations against the zip code database, it takes almost exactly 3 seconds, which is the total execution time, not just the querying.

Dumping all of the superfluous information from the zip code database cut the execution time IMMENSELY; we're talking by a couple of minutes. I'm just wondering if anyone else sees something I can do to further reduce the execution time.

Thanks!

<?php
#<connect to the mysql database for forthcoming queries>
	//set the credentials for connecting to the mysql database
	$dbhostname = 'localhost';
	$dbuser = 'wnf';
	$dbpass = 'wnf1959';
	$dbname = 'wnf';

//connect to the MySQL database with the supplied credentials
$dbconnection = mysql_connect($dbhostname, $dbuser, $dbpass)

//message to display if there's an error
or die('Connection to the database failed for the following reason: ' . mysql_error());

//select the specified database
mysql_select_db($dbname, $dbconnection)

//message to display if there's an error
or die ('The requested database could not be selected for the following reason: ' . mysql_error());
#</connect to the mysql database for forthcoming queries>

//set a long timeout because we're dealing with a huge database
set_time_limit(120);

//these values will eventually come from a form
$source_zip = '04096';
$radius = 1000;

//initialize the array of results that are within range
$within_range = array();

//query the database for the lat/long coordinates of the source zip code
$query_source = 'SELECT `LatitudeRad`, `LongitudeRad` FROM `zipcodes` WHERE `ZIPCode` = "' . $source_zip . '"';
$result_source = mysql_query($query_source);
$row_source = mysql_fetch_array($result_source);

$lat_1 = $row_source['LatitudeRad'];
$long_1 = $row_source['LongitudeRad'];

//query the database for all of the retail location zip codes
$query_all_locs = 'SELECT `id`, `zip` FROM `retailers`';
$result_all_locs = mysql_query($query_all_locs);
$row_all_locs = mysql_fetch_array($result_all_locs);

//for every row in the `retailers` table...
for ($i = 0; $i < mysql_num_rows($result_all_locs); $i++) {
	$dest_zip = $row_all_locs['zip'];

$query_dest = 'SELECT `LatitudeRad`, `LongitudeRad` FROM `zipcodes` WHERE `ZIPCode` = "' . $dest_zip . '"';
$result_dest = mysql_query($query_dest);
$row_dest = mysql_fetch_array($result_dest);

$lat_2 = $row_dest['LatitudeRad'];
$long_2 = $row_dest['LongitudeRad'];

//the Great Circle formula for calculating the distance between two points on the surface of a sphere,
//that sphere being the Earth, in this case
$distance = 3963.0 * acos(sin($lat_1) *  sin($lat_2) + cos($lat_1) * cos($lat_2) * cos($long_2 - $long_1));

if ($distance < $radius) {
	$within_range[] = $row_all_locs['id'];
}

//increment the internal mysql result set pointer
$row_all_locs = mysql_fetch_array($result_all_locs);
}

//close the database connection
mysql_close($dbconnection);
?>

onion2k

You need to reduce the number of results that you're using to do the distance calculation. Obviously theres no point in comparing a zip code in Chicago with a store in New York.. so you need to work out a way of grouping zip codes together.. when the user enters a code you go to your table of grouped codes, find out what rough area the user is in, and then compare it with the zip codes in the same group rather than all of them.

Plus, you should think about caching zip codes in another table, so if someone enters a code thats been looked up before you just go to the cache table and get the data that was calculated previously.

cbj4074

Thanks for your reply, onion2k. I had thought about both of those things... but wasn't exactly sure how one might go about grouping zip codes together.

If I group them, then the radius within which the user can search becomes limited to some predefined number I've set. What, then, is a reasonable search radius? There are only 78 stores, and at present, 70 of those are in the same state (Maine). Supposing there are no stores in New York, if a user in western New York wants to know how far east he'll have to drive to visit the nearest location, he will ultimately be out of luck with his search, unless I make the radius about 500 miles.

Limiting the results used in the distance calculations will likely shave a fraction of a second off the query time, whereas leaving the option to enter any radius one wants could save minutes, or even hours, of visitor frustration. Am I wrong?

Onto the caching the distance results in a separate table. Following my previous example, a user in western NY searches in a 500 mile radius and finds a few stores in Maine. I then take the calculations used in finding those stores and stick them in another table, probably with columns like this:

cache_id, source_zip, store_id, distance

where source_zip is the zip code the user searched for (and presumably from), store_id is the (and possibly one of many) store that was found to be within 500 miles, and distance is the distance between the user's zip code and the store's zip code.

It sounds like a great idea. To take it a step further, would it be even better just to write a script that does a one-time calculation of the distances from every zip code in the country to each store location (and maybe rerun the script only when a new store is added?). Or would that just be creating a 6 million-row table that will make the queries even slower?

I guess in both cases, it's about finding a medium that achieves the fastest results - hence the term "optimization".

AstroTeg

In your algorithm, you're taking all retailers (78 or so of them from what you said) and then looping them. In each loop iteration, you then query all your zip codes (all 70k+ of them). For one user query, you're tapping about 5,460,000 rows of data (not taking into account caching and such).

Just a thought: You could do your calculating from within the SQL query. You'll find MySQL is faster doing it this way than trying to run 2 queries. I've done some experiments with this here with some instructions at the bottom of this page (database in use is Postgres). To see this in action with MySQL, you can go here but the zip code data set has been stripped to the bare minimum and is using the geodist MySQL custom function.

cbj4074

Thanks for the reply, AstroTeg. You've both definitely helped me to get on the right track and recognize the inefficiency of my method that I knew was there, but couldn't pinpoint on my own.

You make an outstanding point - why the hell would I query all 70,000 + zip codes when I only have stores in less than 50 of them?

cbj4074

After some fooling around (several hours worth, in fact), I came to a couple conclusions, that may or may not be correct.

I said to myself,

"Is there a way to select all of the zip_id's from the zipcodes table that have values for ZIPCode that match any of the corresponding values in the retailers table...in one query?"

I tried using JOIN, but quickly realized that JOIN is intended for use with primary key columns and returns only one resulting row.

Part of problem is that there was no primary key field (or one that could be used as such) on the zip code database that I bought, since multiple cities evidently have the same zip code, and by the same token, so no single column has entirely unique values.

It's starting to look like cacheing and a 2.5 second query is going to be where this falls.

P.S. I checked out Rob Bauer's website and his little zip code thing is pretty slick. The only real difference is that he is calculating distance using a SINGLE table (whereas I have two tables - retailers and zipcodes), and appears to be performing JOINs across two other tables to retrieve county and statistical data. His situation is much easier, given that he's working with a single table for the distance calculations.

AstroTeg

That pesky Rob Bauer guy! (its actually me 😃)

You're goal is a store locator, right?

It follows the same concept as the zip code look up. The only difference is actually you will have less zip codes to look up than what I had.

How it works:

User enters a zip code. You want to find all the stores within X amount of distance.

You'll need 2 queries. First query looks up the zip code the user entered and returns the lat/long coordinates. Query 1 is done.

Query 2 will take the lat/long coordinates of the users zip code (query 1) and then do the math for the 78 retailer's zip codes against the user's lat/long value. You'll get distance calculations for all 78 retailers. Toss in a where clause that says only return those records with distances < X distance you desire and you're done. The result set will contain the list of retailers within X distance of the user's zip.

So you'll still have two queries, but the first query is pretty light weight. It's a direct lookup (either by zip or maybe get creative and allow city/state if you have that data). Pull the coordinates out and then compare them against the retailers you have and weed out the matches.

The reason I say this is better than what I did with the zip code lookup is when you enter a zip, I look up the lat/long coordinates and then I have to go back to the same table and find the matching zips. I forgot how many rows there are, but its a ton (probably close to 70k). In your case, you just have the 78 rows to look up. This should definitely speed things up.

kpzani

why not do some of the calculations in mysql. generally database servers are very very fast so the more they do the better.

I take it you have added indexes to the zipcode fields in both tables?

// get lat_1 and long_1 first then fun this query
'SELECT
zipcodes.LatitudeRad AS zplat, zipcodes.LongitudeRad AS zplong,
retaliers.id, retailers.zip,
(3963.0
acos(' . sin($lat_1) . ' ' . sin($lat_2) . ' + ' . cos($lat_1) . ' COS($lat_2) COS($long_2 - ' . $long_1 . '))) AS distance ORDER BY distance ASC LIMIT 10'

or even add a where clause into this to ensure your distance is within bounds.

Let me know how it goes. Never tried anything quite like this.

cbj4074

As per everyone's suggestions, I finally nailed it 🙂 It's lightning fast (well, almost) and works perfectly!

I'm thrilled; thanks so much to all of you for your help and willingness to provide excellent suggestions!

kidgeek_dfw

Man I'm trying to build the same thing...

Can you send me a link to your site so I can check it out...