0

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.

  • "Bounding box" usually refers to a rectangle aligned to the coordinate system; is that what you have? Or do you have an irregularly shaped outline? Is the coordinate system latitude and longitude? How many cities? – Rick James May 8 '17 at 23:16
  • I have the bounding rectangles in terms of minlat, minlon, maxlat, maxlon. Right now we are looking at ~200 cities, but ideally it would scale. – Obscura May 8 '17 at 23:45
0

(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.)

  • Suppose, I were to scale to 3 million cities. Is there a (relatively) simple way to solve this problem with SPATIAL? – Obscura May 9 '17 at 0:37
  • It's on my to-do list. (The trouble is, it has been there several years.) – Rick James May 9 '17 at 2:04
  • I would be interested in seeing a dataset (preferably of more than 200) of bounding boxes. Some day I might play with your question. – Rick James May 15 '17 at 23:30
  • Can convert these to bounding boxes. github.com/JamesChevalier/cities/tree/master/united_states – Obscura May 16 '17 at 2:01
  • Hmmm... download the files; write Perl script to open each file find max & min lat & lng for each file; store in table. At the same time, build long ugly string for polygon. – Rick James May 16 '17 at 4:07
0

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

  • Maybe I know too little about sql, but how does sql avoid checking all 10M+ cities to see if they fall within the range? Also, is there any advantage to this syntax over BETWEEN? – Obscura May 9 '17 at 5:02
  • SQL check all Cities, where City Centre +- 1 (or 0.5) degree from selected ... that all, choose any country and count number of cities on 150x150km - result will be not huge, over this 10-200 cities You can run any additional functions. BETWEEN - not a problem, I just provide as it in source. Really - I not sure how many Cities in the world? Our project was about objects in distance range from named City and it work as described – a_vlad May 9 '17 at 5:42
  • New York metro is the largest 'city' in area - 8683 sqKm ref , so its bounding box is very probably more than 1 degree in latitude and/or longitude. – Rick James May 15 '17 at 23:26
  • So, to make the single query work, you need to find the max size (lat and lng) of bounding boxes, not just 1 degree. This gets problematical near the poles, where 10 degrees longitude is not very far. – Rick James May 15 '17 at 23:28
  • Also, MySQL will not make full use of INDEX(lat, lng); it will only use lat. – Rick James May 15 '17 at 23:29
0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.