Manage Latitude and Longitude
claudia
If I've the lati/long of the user... is it possible make a query for
show only records near 500km (for example) to the user!
Thanks
Captain Paralytic
Jerry Stuckle
Claudia,
There are several ways to do it. MySQL has math functions built in, so
you could do the distance calculations in your WHERE statement, i.e.
SELECT mycols FROM mytable WHERE (long expression here) <= 500;
The long expression is on the order of:
acos(cos(lat1)*cos(lon1)*cos(lat2)*cos(lon2) +
cos(lat1)*sin(lon1)*cos(lat2)*sin(lon2) + sin(lat1)*sin(lat2)) * 6378;
lat1 and lon1 are the latitude and longitude of the location you're
using as a reference; you could figure things like cos(lat1) and
sin(lat1) in advance and use them instead of calculating each time.
lat2 and lon2 are the latitude and longitude from your tables. All are
in radians, so you'll have to convert degrees to radians (might be
easier to keep the data in the table in radians).
However, this will require a table scan and the entire expression be
processed on every query. If you have a lot of entries, this will be
significant overhead.
What I've done in the past is to define a box of a certain size (1000k
square for a 500K distance) centered on the location. It's easy then to
find the longitude and latitude of the 4 sides of this box; using a
WHERE clause to limit initial selection to be within that box. Of
course, you need to be careful when you approach 0 degrees latitude or
longitude, or 180 degrees longitude. You still need to calculate
distance, but limiting your selection speeds things up a lot.
To get even more speed for large tables, you could define a box 707 km
on a side (for a 500 km radius). Again, find the longitude and latitude
of the sides, and anything within this box is within 500 km - no need to
check further.
To summarize - once you have the equation working, getting the data is
pretty easy. However, getting the data with reasonable performance on
large tables can be a bit more difficult.
--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstu...@attglobal.net
==================
Erick T. Barkhuis
>claudia wrote:
>>Hi! I've a table with latitude and longitude of X records (My SQL
>>5.x)
[...]
>To get even more speed for large tables, you could define a box 707
>km on a side (for a 500 km radius). Again, find the longitude and
>latitude of the sides, and anything within this box is within 500 km
>- no need to check further.
I agree with Jerry.
However, to get really good performance while still using circles
instead of boxes, you would rather want to use Gauss-Krï¿œger or UTM
coordinates. That way, you can easily use Pythagoras instead of
trigonometry.
Is there any way you can transform the coordinates (or easier: buy the
UTM coordinates from a supplier, who will also provide updates
(necessary when geographical names change, for instance)).
--
Erick
(who uses the Killetsoft.de geodata, that work like a charm, even with
very large tables)
claudia
claudia
SELECT longitude,latitude,
(((acos(sin((51.75733*pi()/180)) * sin((latitude*pi()/180))
+ cos((51.75733*pi()/180))
* cos((latitude*pi()/180))
* cos(((-0.341325 - longitude)*pi()/180))))*180/pi())*60*1.1515)
as distance FROM events
HAVING distance <= 500
ORDER BY distance ASC LIMIT 5
I've 2 problems:
1 - In this query 500 as miles ... how can I have 500 kilometers?
2 - Why use a LIMIT?? Do you think that this query can have problems
without LIMIT?
Doug Miller
>I've read all posts, I've found a query that seems works
>
>SELECT longitude,latitude,
>(((acos(sin((51.75733*pi()/180)) * sin((latitude*pi()/180))
>+ cos((51.75733*pi()/180))
>* cos((latitude*pi()/180))
>* cos(((-0.341325 - longitude)*pi()/180))))*180/pi())*60*1.1515)
>as distance FROM events
>HAVING distance <= 500
>ORDER BY distance ASC LIMIT 5
>
>
>I've 2 problems:
>
>1 - In this query 500 as miles ... how can I have 500 kilometers?
http://lmgtfy.com/?q=how+many+kilometers+in+a+mile
>2 - Why use a LIMIT?? Do you think that this query can have problems
>without LIMIT?
What happens when you try?
Iain
news:Smr5n.90705$813....@tornado.fastwebnet.it...
The formula that I use (adapted for you) is:
$lat = 51.75733;
$lon = -0.341325;
$sql = "SELECT longitude, latitude,
(acos(cos(radians(".$lat."))*cos(radians(".$lon."))*cos(radians(latitude))*cos(radians(longitude))
+
cos(radians(".$lat."))*sin(radians(".$lon."))*cos(radians(latitude))*sin(radians(longitude))
+ sin(radians(".$lat."))*sin(radians(latitude))) * 6378) AS distance FROM
events WHERE distance <=500 ORDER BY distance LIMIT 5;";
distance is in kilometres.
The LIMIT is optional. It would depend upon the size of the table and
whether you want to limit the number of records in the result.
You can see the formula working here:
http://www.skychoice.net/my_test.php?pcfrom=51.75733%2C-0.341325&checkaddress=Check+§r=on&pcto=
You can see the query in red towards the bottom of the page.
That query is working on a table with 13276 records. The speed is quite
impressive.
Iain
Jerry Stuckle
To get kilometers, simply divide miles by 1.609344.
Whether to use LIMIT or not depends on what you want:
http://dev.mysql.com/doc/refman/5.5/en/select.html
Doug Miller
>
>To get kilometers, simply divide miles by 1.609344.
Wrong. You *multiply* miles by 1.609.
Jerry Stuckle
You're right - got it backwards :)
toby
> "claudia" <clau...@libero.it> wrote in message
> You can see the query in red towards the bottom of the page.
> That query is working on a table with 13276 records. The speed is quite
> impressive.
The cost of this kind of computation is negligible in the context of a
disk based query.
I would suggest to the OP that a stored function will clean up her
code considerably (in my experience, more usefully defined in MySQL
than in PHP - the application I work on uses a Great Circle
calculation based on the Haversine formula).
http://en.wikipedia.org/wiki/Great-circle_distance
>
> Iain
Jerry Stuckle
I would beg to differ. Data can be cached; calculations cannot. I've
seen this to be very slow when dealing with < 50K rows (U.S. zip code
database).
> I would suggest to the OP that a stored function will clean up her
> code considerably (in my experience, more usefully defined in MySQL
> than in PHP - the application I work on uses a Great Circle
> calculation based on the Haversine formula).
>
> http://en.wikipedia.org/wiki/Great-circle_distance
>
>> Iain
>
toby
I was surprised to find that neither the query cache nor VIEW caches
results when set up like this:
mysql> create view test2 as
select cityname, stateabbr,
greatcircledistance
(33.975719,-83.873930,latitude,longitude) as d
from usa_geo;
Query OK, 0 rows affected (0.00 sec)
mysql> select sum(d) from test2 where stateabbr='fl';
+-----------------+
| sum(d) |
+-----------------+
| 1391821.3177158 |
+-----------------+
1 row in set (0.18 sec)
The function is marked as DETERMINISTIC.
The failure of caching looks like a defect to me.
> I've
> seen this to be very slow when dealing with < 50K rows (U.S. zip code
> database).
In my USA ZIP table (of 80,117 InnoDB rows), a Haversine Great Circle
distance can be computed for every row in 3.6 seconds on this 6-year-
old P4 3.2 (22,254/sec) when implemented as a stored function in
5.0.70.
I don't know if you call that "slow" but it's probably "fast enough"
for many uses.
>
> > I would suggest to the OP that a stored function will clean up her
> > code considerably (in my experience, more usefully defined in MySQL
> > than in PHP - the application I work on uses a Great Circle
> > calculation based on the Haversine formula).
>
> >http://en.wikipedia.org/wiki/Great-circle_distance
>
> >> Iain
>
> --
> ==================
> Remove the "x" from my email address
> Jerry Stuckle
> JDS Computer Training Corp.
> jstuck...@attglobal.net
> ==================
Jerry Stuckle
No, I don't think any of the RDBMS's would cache something like that.
>> I've
>> seen this to be very slow when dealing with < 50K rows (U.S. zip code
>> database).
>
> In my USA ZIP table (of 80,117 InnoDB rows), a Haversine Great Circle
> distance can be computed for every row in 3.6 seconds on this 6-year-
> old P4 3.2 (22,254/sec) when implemented as a stored function in
> 5.0.70.
>
> I don't know if you call that "slow" but it's probably "fast enough"
> for many uses.
>
Yes, I would call that "slow". And it may be fast enough for you - but
it would never be fast enough on a web site, for instance. What do you
think would happen if you had 10 queries come in at about the same time,
for instance?
Implementing something like I suggested in application and SQL code will
get the results much faster - probably around 0.1 second or less,
depending on your data.
--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstu...@attglobal.net
==================
toby
Why not?
>
> >> I've
> >> seen this to be very slow when dealing with < 50K rows (U.S. zip code
> >> database).
>
> > In my USA ZIP table (of 80,117 InnoDB rows), a Haversine Great Circle
> > distance can be computed for every row in 3.6 seconds on this 6-year-
> > old P4 3.2 (22,254/sec) when implemented as a stored function in
> > 5.0.70.
>
> > I don't know if you call that "slow" but it's probably "fast enough"
> > for many uses.
>
> Yes, I would call that "slow". And it may be fast enough for you - but
> it would never be fast enough on a web site, for instance. What do you
> think would happen if you had 10 queries come in at about the same time,
> for instance?
You're assuming you need to search the whole table; plus concurrent
queries will overlap. It all depends exactly what you're doing,
doesn't it. It's certainly fast enough for our web site (which
actually does search subsets of the table, e.g. per state). (Yes I
know there are all kinds of optimisations, which I would do when and
if they become justified.)
>
> Implementing something like I suggested in application and SQL code will
> get the results much faster - probably around 0.1 second or less,
> depending on your data.
Well, depending on what "result" you want. Of course some C code in an
in-memory table can be faster. But that comes with its own costs too.
There is no single correct answer for all applications.
>
> --
> ==================
> Remove the "x" from my email address
> Jerry Stuckle
> JDS Computer Training Corp.
> jstuck...@attglobal.net
> ==================
Jerry Stuckle
Well, among other things, it would have to keep track of every row in
the table and whether the column(s) in the expression has/have changed
or not since the last time this statement was executed. That's a lot
different than just having a result set in memory (which can be updated
in memory). You're talking an entire new layer of complication. I
would guess that's why no RDBMS manufacturer caches these.
>>>> I've
>>>> seen this to be very slow when dealing with < 50K rows (U.S. zip code
>>>> database).
>>> In my USA ZIP table (of 80,117 InnoDB rows), a Haversine Great Circle
>>> distance can be computed for every row in 3.6 seconds on this 6-year-
>>> old P4 3.2 (22,254/sec) when implemented as a stored function in
>>> 5.0.70.
>>> I don't know if you call that "slow" but it's probably "fast enough"
>>> for many uses.
>> Yes, I would call that "slow". And it may be fast enough for you - but
>> it would never be fast enough on a web site, for instance. What do you
>> think would happen if you had 10 queries come in at about the same time,
>> for instance?
>
> You're assuming you need to search the whole table; plus concurrent
> queries will overlap. It all depends exactly what you're doing,
> doesn't it. It's certainly fast enough for our web site (which
> actually does search subsets of the table, e.g. per state). (Yes I
> know there are all kinds of optimisations, which I would do when and
> if they become justified.)
>
The way you're doing it requires a full table scan, and the expression
must be executed on every row in the table. You say you're searching a
subset of the table, by state - but that won't work here, where I am in
Maryland, but am within 3 miles of both DC and Virginia.
>> Implementing something like I suggested in application and SQL code will
>> get the results much faster - probably around 0.1 second or less,
>> depending on your data.
>
> Well, depending on what "result" you want. Of course some C code in an
> in-memory table can be faster. But that comes with its own costs too.
>
> There is no single correct answer for all applications.
>
The result my customers want is the correct data in a timely manner.
That's what I give them. No C code or in-memory tables, either. Just
code which has been optimized where necessary.
--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstu...@attglobal.net
==================
toby
Why can't the query cache cache it? (Given that the function is marked
NO SQL and DETERMINISTIC.)
>
>
>
> >>>> I've
> >>>> seen this to be very slow when dealing with < 50K rows (U.S. zip code
> >>>> database).
> >>> In my USA ZIP table (of 80,117 InnoDB rows), a Haversine Great Circle
> >>> distance can be computed for every row in 3.6 seconds on this 6-year-
> >>> old P4 3.2 (22,254/sec) when implemented as a stored function in
> >>> 5.0.70.
> >>> I don't know if you call that "slow" but it's probably "fast enough"
> >>> for many uses.
> >> Yes, I would call that "slow". And it may be fast enough for you - but
> >> it would never be fast enough on a web site, for instance. What do you
> >> think would happen if you had 10 queries come in at about the same time,
> >> for instance?
>
> > You're assuming you need to search the whole table; plus concurrent
> > queries will overlap. It all depends exactly what you're doing,
> > doesn't it. It's certainly fast enough for our web site (which
> > actually does search subsets of the table, e.g. per state). (Yes I
> > know there are all kinds of optimisations, which I would do when and
> > if they become justified.)
>
> The way you're doing it requires a full table scan,
That particular query is, of course; and is clearly only for benchmark
purposes. Of course 2 or 3 second query latency is unacceptable for a
typical web application.
> and the expression
> must be executed on every row in the table. You say you're searching a
> subset of the table, by state - but that won't work here, where I am in
> Maryland, but am within 3 miles of both DC and Virginia.
Right. But your case can use a box range and the same Great Circle
function.
>
> >> Implementing something like I suggested in application and SQL code will
> >> get the results much faster - probably around 0.1 second or less,
> >> depending on your data.
>
> > Well, depending on what "result" you want. Of course some C code in an
> > in-memory table can be faster. But that comes with its own costs too.
>
> > There is no single correct answer for all applications.
>
> The result my customers want is the correct data in a timely manner.
> That's what I give them. No C code or in-memory tables, either. Just
> code which has been optimized where necessary.
>
> --
> ==================
> Remove the "x" from my email address
> Jerry Stuckle
> JDS Computer Training Corp.
> jstuck...@attglobal.net
> ==================
Jerry Stuckle
Because it uses a calculation to determine the answer. And that could
be difficult to determine if the calculation needs to be recomputed or
not, as I indicated above.
Which is how I recommended doing it several posts ago.
>>>> Implementing something like I suggested in application and SQL code will
>>>> get the results much faster - probably around 0.1 second or less,
>>>> depending on your data.
>>> Well, depending on what "result" you want. Of course some C code in an
>>> in-memory table can be faster. But that comes with its own costs too.
>>> There is no single correct answer for all applications.
>> The result my customers want is the correct data in a timely manner.
>> That's what I give them. No C code or in-memory tables, either. Just
>> code which has been optimized where necessary.
>>
--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstu...@attglobal.net
==================
toby
All one needs to ask is whether it is deterministic or not. If it is
deterministic, then what are the inputs? In this case, one table,
`usa_geo`. The validity of the cached result depends on whether
`usa_geo` has been touched, in which case the query cache is
invalidated in the normal way. This seems quite feasible.
The apparently artificial limitation here may be that table references
must be in the FROM list of a query to be cached or invalidated. But I
am guessing whether that is the actual implementation shortcut. I
still do not see anything in this that would theoretically prevent
caching, as long as the input/dependency analysis continued into
referenced VIEWs or stored functions, etc. Perhaps this analysis is
deemed too expensive for individual queries.
Of course, it's an obvious optimisation. And given that, or other
indexable prunings, a stored function implementation is quite sensible
and convenient.
>
> >>>> Implementing something like I suggested in application and SQL code will
> >>>> get the results much faster - probably around 0.1 second or less,
> >>>> depending on your data.
> >>> Well, depending on what "result" you want. Of course some C code in an
> >>> in-memory table can be faster. But that comes with its own costs too.
> >>> There is no single correct answer for all applications.
> >> The result my customers want is the correct data in a timely manner.
> >> That's what I give them. No C code or in-memory tables, either. Just
> >> code which has been optimized where necessary.
>
> --
> ==================
> Remove the "x" from my email address
> Jerry Stuckle
> JDS Computer Training Corp.
> jstuck...@attglobal.net
> ==================
Jerry Stuckle
Not necessarily. The cache may not be big enough to hold the entire
result set, for instance. Or any of a number of reasons. As I said - I
don't know of ANY RDBMS manufacturers who cache calculated queries. If
you can do better, then by all means, have at it.
> The apparently artificial limitation here may be that table references
> must be in the FROM list of a query to be cached or invalidated. But I
> am guessing whether that is the actual implementation shortcut. I
> still do not see anything in this that would theoretically prevent
> caching, as long as the input/dependency analysis continued into
> referenced VIEWs or stored functions, etc. Perhaps this analysis is
> deemed too expensive for individual queries.
>
Quite possibly. But if you can do better, you're free to come up with
your own product.
Not so obvious that many people, including the original op in this
thread, don't see it. I've answered questions like this many times over
the years.
Also, a stored procedure is probably not the way to do it - at least in
MySQL. One can easily compute the appropriate box in an application and
pass those values to a SQL query. Much faster than a stored procedure -
especially in MySQL, which has a very poor implementation of stored
procedures.
And this would be a stored procedure, not a function.
>>>>>> Implementing something like I suggested in application and SQL code will
>>>>>> get the results much faster - probably around 0.1 second or less,
>>>>>> depending on your data.
>>>>> Well, depending on what "result" you want. Of course some C code in an
>>>>> in-memory table can be faster. But that comes with its own costs too.
>>>>> There is no single correct answer for all applications.
>>>> The result my customers want is the correct data in a timely manner.
>>>> That's what I give them. No C code or in-memory tables, either. Just
>>>> code which has been optimized where necessary.
--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstu...@attglobal.net
==================
toby
This is clearly not the reason in this case.
> Or any of a number of reasons. As I said - I
> don't know of ANY RDBMS manufacturers who cache calculated queries. If
> you can do better, then by all means, have at it.
Why is it different from any other query? As you know, the MySQL query
cache caches result set keyed by query text, and invalidates it when
an antecedent is modified. My best guess is, as above, that they take
a shortcut of not doing dependency analysis inside stored function
calls. But this function is marked DETERMINISTIC NO SQL so such
analysis is not required, afaics. Can somebody explain this? Axel?
>
> > The apparently artificial limitation here may be that table references
> > must be in the FROM list of a query to be cached or invalidated. But I
> > am guessing whether that is the actual implementation shortcut. I
> > still do not see anything in this that would theoretically prevent
> > caching, as long as the input/dependency analysis continued into
> > referenced VIEWs or stored functions, etc. Perhaps this analysis is
> > deemed too expensive for individual queries.
>
> Quite possibly. ...
Jerry Stuckle
How is the database to know without checking - on EVERY request?
>> Or any of a number of reasons. As I said - I
>> don't know of ANY RDBMS manufacturers who cache calculated queries. If
>> you can do better, then by all means, have at it.
>
> Why is it different from any other query? As you know, the MySQL query
> cache caches result set keyed by query text, and invalidates it when
> an antecedent is modified. My best guess is, as above, that they take
> a shortcut of not doing dependency analysis inside stored function
> calls. But this function is marked DETERMINISTIC NO SQL so such
> analysis is not required, afaics. Can somebody explain this? Axel?
>
Because other queries don't include calculations. Is that too hard for
you to understand?
Static data can be cached much more easily than computed values.
>>> The apparently artificial limitation here may be that table references
>>> must be in the FROM list of a query to be cached or invalidated. But I
>>> am guessing whether that is the actual implementation shortcut. I
>>> still do not see anything in this that would theoretically prevent
>>> caching, as long as the input/dependency analysis continued into
>>> referenced VIEWs or stored functions, etc. Perhaps this analysis is
>>> deemed too expensive for individual queries.
>> Quite possibly. ...
John Nagle
You guys are using the wrong tool for the job. Most of the
proposed solutions force a brute-force search of the entire
database. That's going to be slow and will scale very badly.
Look up "MySQL Spatial Extensions". MySQL has a type POINT
and useful functions for it. The syntax is:
CREATE TABLE gasstations (
brand VARCHAR(32),
location POINT NOT NULL, SPATIAL INDEX(location))
ENGINE=MyISAM;
Add some records:
INSERT INTO gasstations(brand, location)
VALUES ('BP', GeomFromText('POINT(150.25 200.13)'));
...
Search looks like this:
-- Define a selection rectangle from two corner points,
-- 45 45 and 55 55
SELECT brand, AsText(location) FROM gasstations WHERE
MBRContains(
Envelope(GeomFromText('LineString(45 45,55 55)')),
location);
So, if your location is stored as a latitude/longitude point, you
compute the lat/long of the corners of the bounding box of interest,
and SELECT accordingly. You use the index to get a small set of records
using a bounding rectangle for the neighborhood, then work on those
records with the appropriate trig operations to compute actual distances.
The final distance filtering can be done in a HAVING clause, or in
your own code. Or, if you don't need that much precision, the
bounding rectangle is probably sufficient.
Only MyISAM supports R-tree indices for 2D lookup. The only
index-supported operation is to find all points within a bounding
rectangle, which is what MBRContains does. That's fast. So
design your queries accordingly. An EXPLAIN for the above
query shows it as SIMPLE, with no ALL result indicating a need
for a search of the entire database.
Note that MySQL spatial indices use flat 2D geometry, so there will
be wrap problems near 180 E/W, out in mid-Pacific, and near the
South Pole. So some special casing is required out to do the
whole planet.
(The lat/long vs. distance geometry issues are well-understood and
code for that is available from the GPS community, so I'm not going to go
into that.)
John Nagle
Peter H. Coffin
> Note that MySQL spatial indices use flat 2D geometry, so there will
> be wrap problems near 180 E/W, out in mid-Pacific, and near the
> South Pole. So some special casing is required out to do the
> whole planet.
That's okay. There aren't many gas stations there either.
For that matter, most of the scales involved aren't going to be more
than 5-10 degrees, mostly below 70 latitude, and that 180 boundry is
more about putting that line as far away from anything civilized as
could be found at the time and in the opinion of those doing the drawing
than about putting the 0 line in Greenwich. So most *stuff* is going to
be mapped away from where much special casing and accounting for 3- to
2-D mapping is terribly significant.
--
50. My main computers will have their own special operating system that
will be completely incompatible with standard IBM and Macintosh
powerbooks.
--Peter Anspach's list of things to do as an Evil Overlord