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 quotient 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.

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.