MySQL database for storing city bounding boxes and names

Question

I need to design a mysql database which contains a table of cities which supports only a single query - given a point, return the city (or cities) which it falls in. I have the bounding box for each city. What should the column look like to store the city bounding box to fully take advantage of mysql's spatial-indexing, multiple POINT columns? POLYGON? And what does the query look like.

Most discussion I've seen of spatial indexing involves the inverse question - given a bounding box, return the set of entries which have a POINT column which falls within the bounding box, which they are able to do using MBRWITHIN to obtain.

Answer 1

(Not a full answer, but too long for a Comment.)

With 200 cities with 'retangular' bounding boxes, virtually anything will do. Even a simple table without a SPATIAL index, but with INDEX(latitude), INDEX(longitude).

3 million cities, on the other hand, needs some serious indexing. SPATIAL, as you are asking about, is probably the 'right' way to do it.

Here is an efficient way to do it without SPATIAL, using PARTITIONing and special code instead. (However, the code given is aimed at a different problem, so it is not directly applicable.)

Answer 2

Think - the spatial indexes would be right, but just some tricks which we use on one search project with MySQL 5.5

Look for problem from other side - how many cities could be on 1 degree lat/lon?

IF exclude some countries like Malta (where my son walking from Home to School cross 3 cities for 15 minutes) - common answer will be not too much.

So, with index for lat and longitude queries like:

SELECT something FROM cities 
WHERE 
(lat > xx - 1degree AND lat < xx + 1 degree) AND (lon > xx - 1degree AND lon < xx + 1 degree) 
AND (other conditions such as - distance from point and etc)

would be fast, just because first layer of filters return You less than 100 rows

this logic was successfully used with 10M+ rows tables

Answer 3

Here's a solution.

Assumptions:

• Possibly millions of cities.
• Most cities are not very big.
• The list of cities, and their 'bounding boxes', is mostly unchanging. (Occasional updates/additions will not hurt this algorithm.)

Design:

• Each city has a unique id, but it will not be the PRIMARY KEY in the table.
• The design will take advantage of the "clustering" nature of InnoDB's PRIMARY KEY.
• Two extra SMALLINT columns: lat2 = FLOOR(latitude * 2), lng2 = FLOOR(longitude * 2)
• PRIMARY KEY(lat2, lng2, id) -- Notes: Unique; all cities overlapping a spot will be "clustered" together, making the lookup efficient.
• lat2 is 35mi / 56km wide; lng2 is that wide, or less.
• Near the poles there are not many cities, and they are relatively small.
• Each "city" will be represented in the table as many times as necessary -- That is, a 'large' city or one that spills across a lat2 or lng2 boundary will be represented multiple times, but...
• There will be only perhaps 10% overhead due to such duplication. (That one 'city' in China will show up a few hundred times. But some cities of 1M will fit in one 'square'.)
• *2 is a guess as to what is optimal. *1 would lead to too many cities to do secondary filtering on. *10 would lead to more cities having to be duplicated. It's hard to predict the optimal spot; my gut says that the multiplier won't matter much.

Lookup - given that you are at $lat, $lng, then the list of cities you are possibly in is

SELECT id
    FROM ...
    WHERE lat2 = FLOOR($lat * 2)
    WHERE lng2 = FLOOR($lng * 2)

That will return a few, maybe a few dozen, rows. Then JOIN to the table table of cities (or have all the data in this table). Check each one against the bounding box (or polygon), thereby whittling the list down to very few cities.

This design allows searching much faster than checking the millions or rows. Possibly even less work than with a SPATIAL index.