Suggestions for best practice: mysql vs array sorting

[bill]

I am about to start on a module that will accept a location from
a user, use Google geolocation services to get the lat/lon and
then compute the distance from the site visitor to about 100
kennels (could grow to 1000 eventually).

Once I have the distance I need to sort the kennels by distance
and present those within 500 miles.

Approach 1: read the kennel lat/lon from the mysql kennel record
compute the distance
write the distance back into the kennel record
when done,
using the distance as an index, read back
the kennel data until I get 500 miles.
If I use this approach would I need to lock the database to
prevent a second site visitor from possibly colliding ?

Approach 2: read the kennel lat/lon from the mysql kennel record
compute the distance
put the kennel ID (20 char) and distance into an
associative array
when done,
sort the array
look up kennels by kennel ID that are within 500mi

Approach 3: read the kennel lat/lon from the mysql kennel record
compute the distance
put the data back into the $rows array, proceed as
in approach 2.
I don't know if one can add a column to an already
established array and/or re-use a dummy variable in the array.

I ask for suggestions on the best approach.
The kennel record has a row size of 1.118 bytes

bill

[=?UTF-8?B?SXbDoW4gU8OhbmNoZXogT3J0ZWdh?=]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

bill wrote:

Once I have the distance I need to sort the kennels by distance
and present those within 500 miles.

[...]

I ask for suggestions on the best approach.

First, do use MySQL's spatial extensions to store the lat-long coordinates
of every kennel.

Second, do use spatial operators to filter and sort by distance. It should
go like this:

select name,Distance(G eomFromText('') ,kennels.positi on) as dist from kennels
where dist < 1500 sort by dist asc;

Easy, huh? I think that letting the hard work to MySQL is the fastest way.

However, you may run on a problem: the earth is flat, and calculating the
distance on the surface of a (quasi-)sphere is not trivial. You may
research on earth projection models (mercator, etc) to "flatten" out the
earth, so MySQL returns a nice cartesian distance.

The kennel record has a row size of 1.118 bytes

Why? You can't change that or what?

- --
- ----------------------------------
Iván Sánchez Ortega -ivansanchez-algarroba-escomposlinux-punto-org-

Now listening to: Shirley Bassey - The Remix Album ... Diamonds Are
Forever0 - [9] Light My Fire (Twelftree's Lady Mix) (4:04) (95%)
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFFnUQhR56 dWuhgxGgRAkICAJ 93I7DECfOJ3plsE qE6kZAInt/QYQCgn0CE
DPiFh9QN3iUK6Dq meQd7PKE=
=l9d2
-----END PGP SIGNATURE-----

[Jerry Stuckle]

bill wrote:

I am about to start on a module that will accept a location from a user,
use Google geolocation services to get the lat/lon and then compute the
distance from the site visitor to about 100 kennels (could grow to 1000
eventually).

Once I have the distance I need to sort the kennels by distance and
present those within 500 miles.

Approach 1: read the kennel lat/lon from the mysql kennel record
compute the distance
write the distance back into the kennel record
when done,
using the distance as an index, read back
the kennel data until I get 500 miles.
If I use this approach would I need to lock the database to prevent
a second site visitor from possibly colliding ?

Approach 2: read the kennel lat/lon from the mysql kennel record
compute the distance
put the kennel ID (20 char) and distance into an
associative array
when done,
sort the array
look up kennels by kennel ID that are within 500mi

Approach 3: read the kennel lat/lon from the mysql kennel record
compute the distance
put the data back into the $rows array, proceed as in
approach 2.
I don't know if one can add a column to an already
established array and/or re-use a dummy variable in the array.

I ask for suggestions on the best approach.
The kennel record has a row size of 1.118 bytes

bill

Bill,

The spatial extensions are good, but if you have a large database it
could take significant time to calculate the distance for every row.

Another option:

If you want kennels within 500 miles:

Compute the latitude 500 miles north of your user's location (nlat)
Repeat for 500 miles south (slat)
Do the same for east and west longitude (elong & wlong)

Now use the spacial extensions in MySQL, but also filter on the
longitude and latitude values you computed (in your WHERE clause), i.e.

WHERE long >= elong AND long <= wlong AND lat >= nlat AND lat <= slat

This can filter out a lot of the values before the computations (have an
index on long-lat for even better performance).
--
=============== ===
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
js*******@attgl obal.net
=============== ===

[Hendri Kurniawan]

Assumption:
1. long/lat of kennels are already stored in database
2. Using MySQL database
3. ##SQRT(bla bla bla)## is the formula to find the distance

MySQL actually provide mathematical functions. So why not use it to your
advantage.
SELECT kennel.*, ##SQRT(bla bla bla)##
FROM kennel
WHERE ##SQRT(bla bla bla)## < 500
ORDER BY ##SQRT(bla bla bla)##

Albeit this will take some processing time for MySQL.
Unless if there is a MySQL buff here that knows how to optimize this further

Hope that helps

Hendri Kurniawan

bill wrote:

I am about to start on a module that will accept a location from a user,
use Google geolocation services to get the lat/lon and then compute the
distance from the site visitor to about 100 kennels (could grow to 1000
eventually).

Once I have the distance I need to sort the kennels by distance and
present those within 500 miles.

Approach 1: read the kennel lat/lon from the mysql kennel record
compute the distance
write the distance back into the kennel record
when done,
using the distance as an index, read back
the kennel data until I get 500 miles.
If I use this approach would I need to lock the database to prevent
a second site visitor from possibly colliding ?

Approach 2: read the kennel lat/lon from the mysql kennel record
compute the distance
put the kennel ID (20 char) and distance into an
associative array
when done,
sort the array
look up kennels by kennel ID that are within 500mi

Approach 3: read the kennel lat/lon from the mysql kennel record
compute the distance
put the data back into the $rows array, proceed as in
approach 2.
I don't know if one can add a column to an already
established array and/or re-use a dummy variable in the array.

I ask for suggestions on the best approach.
The kennel record has a row size of 1.118 bytes

bill

[=?UTF-8?B?SXbDoW4gU8OhbmNoZXogT3J0ZWdh?=]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Jerry Stuckle wrote:

Now use the spacial extensions in MySQL, but also filter on the
longitude and latitude values you computed (in your WHERE clause), i.e.

WHERE long >= elong AND long <= wlong AND lat >= nlat AND lat <= slat

No, you shouldn't do that. If you're using spatial extensions, then define a
bounding box (with GeomFromText('P OLYGON blahblahblah') ), then use a
spatial MBR intersection function to filter the data.

The result will be the same (filtering the points by a rectangle centered on
a point). However, by *only* using spatial functions, the Q-trees
algorithms can kick in, and filter the data faster than using four
non-spatial comparisons. After all, that's why Q-trees and spatial stuff
was invented.

- --
- ----------------------------------
Iván Sánchez Ortega -ivansanchez-algarroba-escomposlinux-punto-org-

Well, if you're not running Windows, how the hell else are you supposed to
get memory leaks? They don't just grow on B-Trees, y'know!
-- Tackhead, on Slashdot.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFFncO5R56 dWuhgxGgRAvvoAJ 9D2WBkImlUvuiXY Bc8q76ryiai9ACf Vfcv
vG4d6yRqt9IldEA iqDrwJ60=
=8y+S
-----END PGP SIGNATURE-----

[bill]

bill wrote:

I am about to start on a module that will accept a location from a user,
use Google geolocation services to get the lat/lon and then compute the
distance from the site visitor to about 100 kennels (could grow to 1000
eventually).

Once I have the distance I need to sort the kennels by distance and
present those within 500 miles.

Approach 1: read the kennel lat/lon from the mysql kennel record
compute the distance
write the distance back into the kennel record
when done,
using the distance as an index, read back
the kennel data until I get 500 miles.
If I use this approach would I need to lock the database to prevent
a second site visitor from possibly colliding ?

Approach 2: read the kennel lat/lon from the mysql kennel record
compute the distance
put the kennel ID (20 char) and distance into an
associative array
when done,
sort the array
look up kennels by kennel ID that are within 500mi

Approach 3: read the kennel lat/lon from the mysql kennel record
compute the distance
put the data back into the $rows array, proceed as in
approach 2.
I don't know if one can add a column to an already
established array and/or re-use a dummy variable in the array.

I ask for suggestions on the best approach.
The kennel record has a row size of 1.118 bytes

bill

The record size 1,118 bytes was just information.

Thanks to all who made suggestions.
Are the MySql spatial extensions part of 4.1.2 (which is what my
provider provides) or an extension that I need to install ?

the formula for distance is:

// Convert lattitude/longitude (degrees) to radians for
calculations
$lat1 = deg2rad($lat1);
$lon1 = deg2rad($lon1);
$lat2 = deg2rad($lat2);
$lon2 = deg2rad($lon2);

// Find the deltas
$delta_lat = $lat2 - $lat1;
$delta_lon = $lon2 - $lon1;

// Find the Great Circle distance
$temp = pow(sin($delta_ lat/2.0),2) + cos($lat1) *
cos($lat2) * pow(sin($delta_ lon/2.0),2);
$distance = 3956 * 2 * atan2(sqrt($tem p),sqrt(1-$temp));

[=?UTF-8?B?SXbDoW4gU8OhbmNoZXogT3J0ZWdh?=]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

bill wrote:

Are the MySql spatial extensions part of 4.1.2 (which is what my
provider provides) or an extension that I need to install ?

The spatial extensions are avaiable by default, in MySQL 4.1 and higher.

- --
- ----------------------------------
Iván Sánchez Ortega -ivansanchez-algarroba-escomposlinux-punto-org-

Afternoon very favorable for romance. Try a single person for a change.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)

iD8DBQFFnmW6R56 dWuhgxGgRAjZgAJ 9PNrbBfiqhxCYqQ KpmI/6dqr+rGQCfdPvg
cbP6I46fbViv5xe yrTh46pc=
=OV7v
-----END PGP SIGNATURE-----