Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase 123»»»

Optimize query for finding nearest airport based on latitude and longitude using STDistance Expand / Collapse
Author
Message
Posted Saturday, April 28, 2012 5:48 AM
SSC Journeyman

SSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC Journeyman

Group: General Forum Members
Last Login: Thursday, March 13, 2014 9:12 PM
Points: 80, Visits: 483
Hi guys. Good day to all.

This is the first time I've post in this forum though I was for sometime now looking at the posts of others to gain knowledge in this great RDBMS and to learn from the best on this field.

I wanted to ask some help from the community about optimizing the query I've made in finding the nearest airport based on latitude and longitude using STDistance method of the Geography datatype.

Here's the scenario, I've imported a csv file that contains all the airports in the world which is around 40k plus records. Also, I've imported another csv file which contain the logs from an airplane. It contains the lat/long, fuel used, altitude, etc. The size of this file will depend on how long the airplane is flying. One file I have imported consists of 12k rows. The table is structured something like this:

Log_Details table:
Log_Detail_ID,Log_Detail_Latitude,Log_Detail_Longitude,Log_Detail_Altitude
1, 40.3215, -112.35, 2000
2, 39.5423, -111.45, 1500
3, 41.2563, -113.53, 1500
......

Airport table:
Airport_Ident,Airport_Name,Airport_Latitude,Airport_Longitude,Airport_Geog
MCIAA, Mactan Cebu Airport, 10.6543, -15.1233, 0x00013213112
LAX, Los Angeles, 75.1235, -55.2135, 0x000132654546
NAIA, Ninoy Airport, 15.4566, -26.5463, 0x4564789797
....

Based on the Log_Details table records, I wanted to find the nearest airport based on the Latitude and Longitude. I made a test query to see how long does it take get the nearest airport based on the Log_Details. This is the only set based query I can think of to get the nearest airport.

SELECT Log_Detail_ID,Log_Detail_Latitude,Log_Detail_Longitude
FROM dbo.Log_Details l
CROSS APPLY (SELECT TOP(1) Airport_Ident,Airport_Name,Airport_Latitude,Airport_Longitude FROM dbo.Airport
ORDER BY Airport_Geog.STDistance((GEOGRAPHY::Point(Log_Detail_Latitude, Log_Detail_Longitude, 4326))));

When I ran this query, after it reached 1 min plus, I cancelled it.

That's why I wanted the help of the community if there is any other way that I could speed up the performance of the query considering there are many records in both table? Or is there another way of getting the record without using STDistance method. I don't if this method is slow. Just wanted to know if there is any faster alternatives.

Thank you in advance.
Post #1292019
Posted Saturday, April 28, 2012 11:38 AM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 10:19 PM
Points: 36,995, Visits: 31,523
The "nearest" airport anywhere in a given flight will never be more than half the distance between the start and end airports of the flight. One very easy and effective optimization to make is to calculate the min and max latitude based on that knowledge and limit the airports you look at to that. A secondary and slightly more complex calulation is to do the same with longitude.

--Jeff Moden
"RBAR is pronounced "ree-bar" and is a "Modenism" for "Row-By-Agonizing-Row".

First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #1292055
Posted Saturday, April 28, 2012 8:43 PM
SSC Journeyman

SSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC Journeyman

Group: General Forum Members
Last Login: Thursday, March 13, 2014 9:12 PM
Points: 80, Visits: 483
Hello Jeff.

Thanks for the immediate reply. Sorry it this long for me get back, don't have a computer at home. Have to go to an internet shop.
I kind of get a blur picture of your suggestion. Can you give me an example? Sorry my analytical skills are not really that good
Post #1292090
Posted Saturday, April 28, 2012 9:02 PM
SSC Journeyman

SSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC JourneymanSSC Journeyman

Group: General Forum Members
Last Login: Thursday, March 13, 2014 9:12 PM
Points: 80, Visits: 483
Hello Jeff.

I was thinking about your suggestion. Is it somehow similar to this?

I will get the min/max lat and long based on the flight log. Get the distance between the min/max lat/long and limit the airports based on that distance?

Thank you.
Post #1292095
Posted Saturday, April 28, 2012 9:09 PM


SSCarpal Tunnel

SSCarpal TunnelSSCarpal TunnelSSCarpal TunnelSSCarpal TunnelSSCarpal TunnelSSCarpal TunnelSSCarpal TunnelSSCarpal TunnelSSCarpal Tunnel

Group: General Forum Members
Last Login: Sunday, August 17, 2014 3:10 PM
Points: 4,013, Visits: 6,098
Here is a link to a blog by Isaac Kunen discussing "nearest neighbor" solutions using spatial functions in SQL 2008. (This query will actually become fairly easy in SQL 2012.)

http://blogs.msdn.com/b/isaac/archive/2008/10/23/nearest-neighbors.aspx


Edited to drop a lot of nonsense.


__________________________________________________

Against stupidity the gods themselves contend in vain. -- Friedrich Schiller
Stop, children, what's that sound? -- Stephen Stills
Post #1292096
Posted Sunday, April 29, 2012 12:44 PM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 10:19 PM
Points: 36,995, Visits: 31,523
facturan.antonio (4/28/2012)
Hello Jeff.

I was thinking about your suggestion. Is it somehow similar to this?

I will get the min/max lat and long based on the flight log. Get the distance between the min/max lat/long and limit the airports based on that distance?

Thank you.


Ummm... kind of but a little bit differently.

1. Get the distance between the two airports for the flight and divide that distance by two.
2. Convert that distance to degrees of Latitude.
3. Subtract and Add that those degrees of Latitude from the Latitude for the given flight point. Those should be your new min an max Latitudes to search for closest airports for points during the flight. It will greatly increase the speed of your original calculation because it can eliminate virtually all other airports in the world for shorter flights.

If you create the same limits for Longitude (taking curvature of the Earth into consideration), you can quickly focus in on a pretty tight window.


--Jeff Moden
"RBAR is pronounced "ree-bar" and is a "Modenism" for "Row-By-Agonizing-Row".

First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #1292187
Posted Sunday, April 29, 2012 12:52 PM


SSCertifiable

SSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiable

Group: General Forum Members
Last Login: Today @ 3:09 PM
Points: 6,251, Visits: 7,411
Jeff (and OP) if I read this problem correctly, he doesn't have an endpoint yet and is trying to find said endpoint. Also using that technique you could miss an airport near the center of the flightline if you're looking to locate emergency landing areas.

You're basically just trying to find the closest point in the list from a selected point. This means you'll always have to calculate all of the rows against that point, sort the result, and pick the minimum. That's going to be a very heavy handed process. What Jeff's trying to point out is you need to restrict the list of what you're comparing so you can get a better query, and it needs to be precomputed or an existing attribute.

Try restricting it to airports in the same country, or those on the same side of the equator, or similar. You'll find the process will take a lot less time. In the meanwhile I'll see if I can come up with anything. Is that table you described the FULL table and the only attributes you have available, or was it simplified for the purposes of this example? If there's more attributes we may have some other ideas.



- Craig Farrell

Never stop learning, even if it hurts. Ego bruises are practically mandatory as you learn unless you've never risked enough to make a mistake.

For better assistance in answering your questions | Forum Netiquette
For index/tuning help, follow these directions. |Tally Tables

Twitter: @AnyWayDBA
Post #1292190
Posted Sunday, April 29, 2012 1:04 PM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 10:19 PM
Points: 36,995, Visits: 31,523
Evil Kraig F (4/29/2012)
Jeff (and OP) if I read this problem correctly, he doesn't have an endpoint yet and is trying to find said endpoint. Also using that technique you could miss an airport near the center of the flightline if you're looking to locate emergency landing areas.

You're basically just trying to find the closest point in the list from a selected point. This means you'll always have to calculate all of the rows against that point, sort the result, and pick the minimum. That's going to be a very heavy handed process. What Jeff's trying to point out is you need to restrict the list of what you're comparing so you can get a better query, and it needs to be precomputed or an existing attribute.

Try restricting it to airports in the same country, or those on the same side of the equator, or similar. You'll find the process will take a lot less time. In the meanwhile I'll see if I can come up with anything. Is that table you described the FULL table and the only attributes you have available, or was it simplified for the purposes of this example? If there's more attributes we may have some other ideas.


Actually, it's simpler than all of that for restrictions if you don't know what the end point is. You can't fly much farther than you have fuel for and, hopefully, you know how much fuel you have so could estimate the range left. Convert that range to degrees of Latitutde and use the same suggestion as before.

So far as any "mid point" error goes, how would there be an error unless you were off course? You can't be more than half way away the total distance from either end point unless you're fairly well off course.


--Jeff Moden
"RBAR is pronounced "ree-bar" and is a "Modenism" for "Row-By-Agonizing-Row".

First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #1292192
Posted Sunday, April 29, 2012 1:20 PM


SSCertifiable

SSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiableSSCertifiable

Group: General Forum Members
Last Login: Today @ 3:09 PM
Points: 6,251, Visits: 7,411
Jeff Moden (4/29/2012)

So far as any "mid point" error goes, how would there be an error unless you were off course? You can't be more than half way away the total distance from either end point unless you're fairly well off course.


Unless I'm misunderstanding what you mean, a graphical example:


This is rough and isn't exactly computed (heck, the blue areas overlap a bit) so I fudged in the larger direction. However, with the blue circles being 'the halfway distances' as I understood what you were describing, notice that Chicago gets left out of the discussion. Depending on where you are on your flight line between Cleveland and Kansas City, there are positions in the flight line where that is the closest airport. At exact calculations I believe Indianapolis would get left out too, but it's a very close thing and GIMP doesn't give me exactly what I want for computations there.

That's more what I meant. If Indianapolis wasn't part of the discussion, the closest airport is definately Chicago, and it's left out of the search. Either that or I *really* didn't understand what you meant.



- Craig Farrell

Never stop learning, even if it hurts. Ego bruises are practically mandatory as you learn unless you've never risked enough to make a mistake.

For better assistance in answering your questions | Forum Netiquette
For index/tuning help, follow these directions. |Tally Tables

Twitter: @AnyWayDBA


  Post Attachments 
AirportExample.jpg (287 views, 74.06 KB)
Post #1292195
Posted Sunday, April 29, 2012 2:51 PM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 10:19 PM
Points: 36,995, Visits: 31,523
Nope... not the way I meant it. For the first and second optimizations, you would limit the lat/lons to the following yellow square.


That would be a bit conservative and would cover even the adventures of "Wrongway Peachfuzz" . If you really want to narrow it down quickly, you can use the more radical "mid point" approach as follows (again, use the yellow square limits):



--Jeff Moden
"RBAR is pronounced "ree-bar" and is a "Modenism" for "Row-By-Agonizing-Row".

First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems


  Post Attachments 
FirstSecondOptimization.gif (272 views, 39.51 KB)
ThirdFourthOptimization.gif (268 views, 41.75 KB)
Post #1292210
« Prev Topic | Next Topic »

Add to briefcase 123»»»

Permissions Expand / Collapse