How to query for address "predictions" while applying constraints Let's say I have this simplified database scheme.

The scheme consists of three tables, street, city and zipcode that all have a many-to-many relationship to each other.

What I want to do is a prediction that queries the database for possible matches as well as predicting missing data. To put it more into an example:
Let's say the user starts typing in a city, perhaps "Wash". He already had a street typed in, for sake of me not knowing any streets, let's call it "New Street Avenue". This is a constraint, meaning it must be fulfilled in our prediction. Now I want the city to query for possible finishers of "Wash" as well as supplying missing data, in this case, zipcodes, that have a street called "New Street Avenue"

Here's how the naive approach would be: 


Filter street for all keys whose name match "New Street Avenue"
Filter street_city for all the street keys and return the city keys
Inner join the city keys on city_zipcode, and then Inner join those onto zipcode


The issue with this approach: The knowledge between street and zipcode is completely ignored. That means we could end up with zipcodes and city pairs, where we know the city contains the street we seek for, but the zipcode doesn't necessarily. This would be an invalid prediction to return, because the address doesn't exist!

That means I need to "persist" the information about street further down the line. 

My approach would be this:


Filter down street for the keys that fulfil our condition.
Inner Join street onto city for the keys from #1. Keep both key columns.
Inner join onto city_zipcode keeping the zipcode keys as well
Filter out all the street and zipcode pairs that are not present in street_zipcode


(On a sidenote: to "hopefully" improve performance, after each "prediction" I would put a LIMIT 10 (or similar) command since we only need a sensible amount of predictions).

This approach should work. It might not be the best optimized, but it would return the correct results. However this not only feels very dirty to me, but also opens up another problem:

I'm pretty sure it scales horribly, in table size as well as in additional tables

There is a good likelyhood there will be another table that has Many-to-Many relationships towards, for the sake of argument, street and zipcode. Now if I wanted to search for a city with a street constraint, I need to do what I did above, and add even more to also filter out any relationships between street and the new table.

I feel like I'm going into a dead end with this approach. I'd love someone to help me out here on how to approach this problem better.
3 tables is what I call "over-normalizing" -- it leads to performance problems.

"Normalizing" is used for two purposes, neither of which really apply to your use case.


Isolate something, say "city" so that it can be easily changed.  In real life, that rarely happens for cities.  ("Bombay" -> "Mumbai" (India), "Hot Springs" -> "Truth or Consequences" (New Mexico))
Save space.  Even if you have all 3 million cities on earth, spelling them out the country each time is not much burden of space.  (For countries, I recommend the standard 2-letter country-codes and use CHARACTER SET ascii.  Optionally, have a table mapping them to spelled out names.)


Zip codes:  In the US, there are about 42K zip-codes.  To normalize you could use a 2-byte SMALLINT UNSIGNED.  But the zipcode, itself, can be stored in a 3-byte MEDIUMINT(5) UNSIGNED ZEROFILL.  Zipcodes do change.  But that usually involves forcing half the users of one zipcode to adopt a 'new' zipcode.  You would have to go through all users of that zipcode (which could be INDEXed) to figure out which ones to change.

Similarly for the split-up of Yugoslavia and Czechoslovakia.  On the other hand, changing "The Republic of Upper Volta" to "Burkina Faso" is easy if you have 'normalized' it.

Plan A (millions of locations):  Simply spell out the location of each item.

Plan B (billions of locations):  Split in two:  Street address and zip+city+country

Think about it another way:  What will you do with the address?


Only for sending mail?  Then why split up the pieces; simply have some text that can be readily printed as-is.
Also used for statistics?  Then you need, say, the "country" (or "country_code") so you can do SELECT SUM... GROUP BY country_code.  This implies that country_code is a separate column.