Reached CPU Limit - any SQL gurus?

[jamesoks]

I am using a mySQL database on a site to calculate the distance of multiple points based on zipcodes, latitudes and longitudes. E.g. Point A at zip code 123456 has latitude 100 and longitude 200 Using a static formula, the distance between Point A and multiple other points are calculated and returned real time. The reference Point A may change to Point B with a different lat/long.

The issue is that the server CPU is maxing out and taking quite a long time to do these calculations on a dynamic basis. Putting the actual distances into a DB is not practical as it means a N x N lookup (999999 x 999999) and will increase exponentially as more datapoints are added.

I can of course increase CPU (currently on VPS Level 3), but seems a waste as this calculation is extremely bursty - most of the time the CPU is idle. Also the RAM/harddisk/bandwidth are all far under-utilised at the moment.

Any SQL gurus on whether such a calculation can be optimised or is a hardware upgrade the only way out?

[junkstuff]

Why are you re-inventing the wheel? There are a number of services and scripts you can use to do the distance for you. If you google you will probably find a few hundred and one (or maybe ten) probably would suit your needs.

[jamesoks]

Junkstuff, I didn't want to do the calculation offline as it would mean I'm dependent on someone else's engine.

The calculation itself is not that complicated based on the Haversine Formula:
Distance = ACOS(COS(RADIANS(90-Lat1)) *COS(RADIANS(90-Lat 2)) +SIN(RADIANS(90-Lat1)) *SIN(RADIANS(90-Lat2)) *COS(RADIANS(Long1-Long2))) *6371*1000

However, the challenge I'm facing is if I have 1,000,000 Latitude and Longitude pairs, what is the most efficient way of structuring/accessing a database such that I can find the distance between any given pair and say 50,000 other pairs.

If I did it using an external service, I would still have to send them 50,001 pairs, let them do the calculation, then return to me 50,001 distances, which I assume will take longer than doing it in-house, unless the third-party service had really powerful servers.

[rota919]

PM Sent...