For a site im trying to make I need to implement a search that returns any SQL entries with postcodes within a specified radius.
I have found a php/sql script that calculated the distance between two points.
http://www.sloomedia.com/php_postcode_script.php
The database of entried to be matched will have > 10k entries so I would like an efficient solution.
All I can think is:
Loop through all entries
If the distance between the entry and the entered postcode is < x miles
Place entry into a temporary table with its distance
Retrieve the entries from the temporary table in order of distance
However this would be pretty intensive if many searches were being conducted, plus I cant think how I would do it at the moment.
can anyone think of any better solutions?
I would split it into groups (areas) and only search the area its in and then those immediately around it, will reduce the total number of searches a lot. You can hive them off into a temporary array.
Bubble sorts are horribly intensive but have a look through the other sort options.
Unfortunately Im very rusty on this sort of thing, havent done it in many years.
I think its called a Hash table.
Basically have a table holding the relative distances between every postcode (but just the postcode 1 ones. :) such as BD1 SW1 CF1 CW1) so you get rough distances between areas.
Use an index table to store the blocks for each regions postcodes.
Use the hash table + index to eliminate chunks of the database which are not within a rough distance.
For example if the postcode your looking for is:
SW10 then you can eliminate wales, central/midlands, north, scotland, northern island, and the ickle islands around the UK.
Just scan through the south east postcodes (which you know the location of in the database because you have an INDEX setup).
Look at your CM0239 work mate :P
Ok, cheers guys. I think im going to divide it into areas like Serious suggested.
Firstly though, ive got something mostly working ie the program displays all records and their distance from the postcode entered.
Whats the easiest way to arrange these into distance order? Serious mentioned You can hive them off into a temporary array. Whats that involve?
Cheers for the help guys.
Ps M3ta7, ive lost all my 239 work!
sorting them into distance... just make a 2D array. You must have done something similar for the auction website project in the first year mate :) Nab your code from that :)
But when I add the to the array (they will be in some random order as the appear in the database, how to i extract them or sort them into order?
Ive only every had to use ORBER BY in the select statement to order results. Thats not applicable here unless I INSERT the results into a temp table then SELECT with OREDER BY miles.
Well using the database method.
Use a VIEW to select the data into. then SELECT from the view using the orderby option :)
Remember Views = Temporary tables basically that can do select statements but wont alter the data in the initial table :)
Edit:
To do it the PHP way, php has array handling gubbins :) and will allow you to just "order" the array that you can create from the database data. Have a google though as its been ages since Ive needed to do it.
You want to store the absolute position of each postcode (latitude and longitude).
Then when you are given the a post code you find its location and then calculate the lat/long rang you need and do a search on that.
You will need to index both the postcode and the lat/long (which will consume a fair amount of space but it will be worth it).
If you are using MySQL then make sure you are using innodb tables with a good sized innodb buffer size.
We have tables with millions of records in which search pretty quickly on indexes so if your only working with entires in the order of n x 10,000 then you should be fine.
I would start off with that method then see how much you need to optimise before adding more tables and splitting the data up.
You could end up doing much more work than you really need - especially considering the database isnt going to really grow in size.
If its a site thats going to be hit lots then consider caching frequenent searches.
cornet: Im a bit of a n00b with databases Im not sure I get what I am meant to do :S
The database is set up like this
Pcode, Grid_N, Grid_E
BD1 416300 433300
LE7 463000 309300
The distance is calculated by using pythagoras to find the hypotenuse of a triangle drawn between the postcode grid references (if that makes sense).
It all works fine, except that I am selecting the whole business table and checking the distance to each value which cant be efficient.
I am thinking only selecting the records in the county but its not ideal.
What you can do is set up a seperate array giving those counties that are next to the target one a tick, it then searches through those too. It means that if someoe lives right on the edge of a county and the closest is in the next one it will find that. Because you are manually editing this array you can sort out some of the little problems although someone has to edit it if something changes..
Counties arent exactly regular though and it might not be the best option.
Quote from: sexytwThe database is set up like this
Pcode, Grid_N, Grid_E
BD1 416300 433300
LE7 463000 309300
The distance is calculated by using pythagoras to find the hypotenuse of a triangle drawn between the postcode grid references (if that makes sense).
It all works fine, except that I am selecting the whole business table and checking the distance to each value which cant be efficient.
Again if its mysql then it can deal with mathematic functions so you dont need to loop through every row manually.
Take a look at:
http://www.phptoast.org/blg3.html for an example of how to create what you want.
or if youre feeling more adventurous then check out the MySQL spatial functions
hereCornet
Cheers!
Quote from: cornetQuote from: sexytwThe database is set up like this
Pcode, Grid_N, Grid_E
BD1 416300 433300
LE7 463000 309300
The distance is calculated by using pythagoras to find the hypotenuse of a triangle drawn between the postcode grid references (if that makes sense).
It all works fine, except that I am selecting the whole business table and checking the distance to each value which cant be efficient.
Again if its mysql then it can deal with mathematic functions so you dont need to loop through every row manually.
Take a look at: http://www.phptoast.org/blg3.html for an example of how to create what you want.
or if youre feeling more adventurous then check out the MySQL spatial functions here
Cornet
The mans a legend! :D Great links there mate. Interesting stuffs! :)
This does seem like a more ideal way to calculate distances, cheers for the link! Im having trouble getting the SQL statement to work.
Ive got 2 tables postcodes and business both have their the lon and lat values stored in radians (as suggested by the site). The postcodes value has Pcode storing the "HR8" kind of value.
So I then have:
//MySQL connect stuff
$pcode = "HR8"; //Test values
$distance = "100";
$query= "select *,3963* 2 * ASIN(POW(POW(SIN((business.lat - postcodes.lat)/2 ), 2) +(COS(postcodes.lat) * COS(business.lat) * POW(SIN( (business.lon - postcodes.lon)/2) ,2)),0.5)) as D from business,postcodes where postcodes.PCode=$pcode and 3970* 2 * ASIN(POW(POW(SIN((business.lat - postcodes.lat)/2 ), 2) +(COS(postcodes.lat) * COS(business.lat) * POW(SIN( (business.lon-postcodes.lon)/2) ,2)),0.5)) < = $distance Order By D";
$result = mysql_query($query);
(Line 19) $res_count=mysql_numrows($result);
echo $res_count;
I get:
"Warning: mysql_numrows(): supplied argument is not a valid MySQL result resource on line 19"
So I assume there is something wrong with the SQL statement, can anyone spot it? Ive been staring at it for hours and I cant see anything.
The only thing(s) that strike me straight off are that youre not putting quotes around your parameters: i.e.
where postcodes.PCode=$pcode
should be: where postcodes.PCode=$pcode
or really: where postcodes.PCode=".chr(34).$pcode.chr(34).""
I also think you need to lose the space out this:
< = $distance
so: <= $distance
And finally, I am not entirely sure that you can use a Select alias in an Order By statement but I could be wrong. Its been a while since I used MySQL :)
You want
$res_count = mysql_num_rows($result);
mysql_numrows() is part of the MySQL Improved Extension library.
Cornet
Lol, mysql_num_rows was the only part I was sure of!
Thanks for the ongoing help. Its very much appriciated.
In the SQL statement that I am using (reminder: )
SELECT * , 3963 *2 * ASIN(
POW( POW( SIN( (
business.lat - postcodes.lat
) /2 ) , 2 ) + ( COS( postcodes.lat ) * COS( business.lat ) * POW( SIN( (
business.lon - postcodes.lon
) /2 ) , 2 ) ) , 0.5 )
) AS D
FROM business, postcodes
WHERE postcodes.PCode = $pcode
AND 3970 *2 * ASIN(
POW( POW( SIN( (
business.lat - postcodes.lat
) /2 ) , 2 ) + ( COS( postcodes.lat ) * COS( business.lat ) * POW( SIN( (
business.lon - postcodes.lon
) /2 ) , 2 ) ) , 0.5 )
) <= $distance
ORDER BY D
LIMIT 0 , 30
How do I select the value of D (representing the distance to the item) once the query has been executed? I have tried:
$row = mysql_fetch_row($result);
$D=$row[D];
To no avail, I also need to do this to pin down why the statement doesnt return any values unless the radius distance is set to 10000 miles of so. :-S
Quote from: sexytwIn the SQL statement that I am using (reminder: )
SELECT * , 3963 *2 * ASIN(
POW( POW( SIN( (
business.lat - postcodes.lat
) /2 ) , 2 ) + ( COS( postcodes.lat ) * COS( business.lat ) * POW( SIN( (
business.lon - postcodes.lon
) /2 ) , 2 ) ) , 0.5 )
) AS D
FROM business, postcodes
WHERE postcodes.PCode = $pcode
AND 3970 *2 * ASIN(
POW( POW( SIN( (
business.lat - postcodes.lat
) /2 ) , 2 ) + ( COS( postcodes.lat ) * COS( business.lat ) * POW( SIN( (
business.lon - postcodes.lon
) /2 ) , 2 ) ) , 0.5 )
) <= $distance
ORDER BY D
LIMIT 0 , 30
How do I select the value of D (representing the distance to the item) once the query has been executed? I have tried:
$row = mysql_fetch_row($result);
$D=$row[D];
To no avail, I also need to do this to pin down why the statement doesnt return any values unless the radius distance is set to 10000 miles of so. :-S
Not to be one of those annoying *nix types that tell you to rtfm all the time but please do so every so often ;)
http://uk.php.net/mysql_fetch_rowWhat you actually want is
http://uk.php.net/manual/en/function.mysql-fetch-assoc.phpCornet