Separate Address Table, Latitude, Longitude

Question

We are designing a DB for a limited functionality social networking application. Users (Registered Users), Retail Outlets, etc are several entities we need to store. We need to store Address of each of these entities. Also we need to store latitude and longitude of Registered Users, Retail Outlets, etc.

Initially we designed the tables as shown below. We created a separate Address tables as the format of the address will be same for Users, Retail Outlets and other entities.

User(UserID, UserName, AddressID)
RetailOutlet(RetailOutletID, OutletName, AddressID)
Address(AddressID, CityID, AddressLine1, AddressLine2, Latitude, Longitude)

Now we realized that we need to search for Retail Outlets near to User's current location(CurrentLatitude, CurrentLongitude) So we would need to run a query like

SELECT OutletName 
from RetaileOutlet 
INNER JOIN Address ON RetailOutlet.AddressID = Address.AddressId 
WHERE Address.Latitude BETWEEN CurrentLatitude - 10 and CurrentLatitude + 10 and
      Address.Longitude BETWEEN CurrentLongitude - 10 and CurrentLongitude + 10

Now we think that above query would run slow because the number of users will be much more than the number of retail outlets. From DB Design/Performance perspective which of the following should be done.

1. Create index on Latitude, Longitude in Address table and on AddressID in RetailOutlet table. So there would be no change in table structure.

2. Move Latitude, Longitude from Address table to RetailOutlet and User tables. Also create index on Latitude, Longitude in RetailOutlet table. So the table structure would be as shown below.

   User(UserID, UserName, AddressID, Latitude, Longitude)
   RetailOutlet(RetailOutletID, OutletName, AddressID, Latitude, Longitude)
   Address(AddressID, CityID, AddressLine1, AddressLine2)
   

3. Change table structure as shown below and create index on Lat, Lng in UserAddress table and on UserAddressID in User table.

   User(UserID, UserName, UserAddressID)
   UserAddress(AddressID, CityID, AddressLine1, AddressLine2, Latitude, Longitude)
   RetailOutlet(RetailOutletID, OutletName, AddressID)
   RetailOutletAddress(RetailOutletAddressID, CityID, AddressLine1, AddressLine2, Latitude, Longitude)
   

4. Introduce DB redundancy by copying Lat, Lng from Address table in the RetailOutlet table and create index on Lat, Lng in RetailOutlet table. With this option there will be no change in Address table and we will be able to use it for storing User address without change. Also we may be able to use it for storing Address of other entities.

   User(UserID, UserName, AddressID)
   RetailOutlet(RetailOutletID, OutletName, AddressID, Latitude, Longitude)
   Address(AddressID, CityID, AddressLine1, AddressLine2, Latitude, Longitude)
   

Answer 1

You were more or less on the right track with (b), but you want to make sure that latitude and longitude are handled independently. What you need are indexes that cover your query parameters. This is what you are looking for:

1. Segregate your retailer addresses (including lat/lon). This could be in a RetailerAddress table or it could be columns on the RetailOutlet table, whichever makes the most sense to you.

2. Create two indexes: (lat), (lon) on whichever table contains your retail outlet addresses. If you have a separate table for retail outlet addresses, be sure to include the FK to the retail outlet in these indexes (i.e. (lat, OutletID), (lon, OutletID)).

Now as long as your query starts from the perspective of a particular user, this is all you'll need for a very efficient lookup on lat/lon ranges. If you need to find the proximate retail locations for a bunch of users at one time, then you will want to have similar indexes on the table containing user addresses.

Answer 2

The right answer is choice #5: use PostGIS. An example from OpenGeo:

"Note the magic <-> operator in the ORDER BY clause. This is where the magic occurs. The <-> is a “distance” operator, but it only makes use of the index when it appears in the ORDER BY clause. Between putting the operator in the ORDER BY and using a LIMIT to truncate the result set, we can very very quickly (less than 10ms on a 2M record table, in this case) get the 10 nearest points to our test point."

(emphasis added)