The problem goes like this, with a story.
You have an application that contains a search field. When you search some input, there's an auto-complete component that pops up showing up similar results to your input.
Each result is a location in the database and this is the structure of
id | name | lat | lon ----------------------------------------- 0 | New york street test 51 |34.123| 38.245
Every location has
Your system has a function that knows how to receive 2 locations and return the distance in km.
You also have a table called
stores which contains id, name, lat, lon of the shop.
When you select a place, your application finds 20 closest stores to the location that you have selected.
Everything works fine for a start, but now the application has grown and filled up with new stores in many locations and you have over one 500 million stores registered in the database. Every search is heavy and overloading the system and it takes a few seconds to a minute to get a result.
How can you make it better, efficient?
Spoiler - My idea to answer the question
My idea is to split the world map into regions matrix of size
Constantwhere constant is set to 10km x 10km. Each region will have its
IDand every shop you add through your platform will get the region id of where you add it to. When you search for lat and lon, the system will go through all regions searching what region contains that coordinate and return the region id, and then you can grab all shops of that region id. But wait, you have a problem, what if there's a closer store in the neighbor regions? Simple, you have 4 points of your region's corners, you can look up for all neighbor regions and compare if there's a closer store. And if you don't have enough stores and you must get 10 stores out of all regions, use the 4 coordinates of the corners as-well and go recursive on all regions until you reach 10 closest.
I am open and happy to hear everyone's thoughts. Note this is not a real story, it was asked in some interview and I took it very interesting to see if there are better and more interesting solutions.