 <p>20 million rows is not a lot for MySQL. Just index the zip/postal code and it will be fast. Way under 200ms fast. No need to split between tables. MySQL does get slow when the result set is large, but it doesn't seem like you would encounter that issue. MySQL will do just fine with hundreds of millions of records for basic queries like yours.</p> <p>You will need to adjust the MySQL settings so that it uses more memory. The default settings are pretty low. </p> <p>MySQL does support spacial indexes. So you could pull the longitude/latitude for the postal codes and use a spacial index to do proximity searches. Doesn't seem like you are looking for that though.</p> <p>If you want things really, really fast, go the route you were thinking of but use memcache or redis. You can use the zip/postal code as the lookup key. You would still need a persistant disk based data store to load the data from. I don't think memcache/redis is necessary, but it's an option.</p>