Mysql – Best way to design / query multi-level relationship table

My company is going to develop a mobile app selling services across different regions. We are expecting users are going to hugely depend on the Search function. Thus, I need to make sure the database design is good enough to handle the searches.

The main concern I have is, not only should the user be able to search the services by name or description, but also by service location.

Let me first show you what I designed:

Solution 1
Table: Service
+------+----------+--------------+--------+----------+----------+
| id   | name     | description  | cityid | address1 | address2 |
+------+----------+--------------+--------+----------+----------+
|     1| Service1 | Description1 |       1| Address1 |          |
|     2| Service2 | Description2 |       2| Address2 |          |
|     3| Service3 | Description3 |       3| Address3 |          |
+------+----------+--------------+--------+----------+----------+

Table: City
+------+-----------+---------+
| id   | name      | stateid |
+------+-----------+---------+
|     1| KL        |       1 |
|     2| Georgetown|       2 |
|     3| JB        |       3 |
+------+-----------+---------+

Table: State
+------+---------------------+-----------+
| id   | name                | countryid |
+------+---------------------+-----------+
|     1| Wilayah Persekutuan |         1 |
|     2| Penang              |         2 |
|     3| Johor               |         3 |
+------+---------------------+-----------+

Table: Country
+------+-----------+
| id   | name      |
+------+-----------+
|     1| Malaysia  |
|     2| Singapore |
+------+-----------+

Above are my tables with some sample data. The requirement is to allow the user to enter a keyword to start searching in the Service table – if the keyword matches a service name, then return that result from Service. If not, then search for the keyword in the City table – if the keyword matches a particular City row, then get all the Service rows that match that city by the cityid. If no row is found, then go on searching in the State table, up until the Country table.

So here is a problem with my solution. If the user enters a Country name, I will get a match result from the Country table, then I use the result's countryid to get all the related states in the State table, then I use those results' stateids to get all related cities in the City table – and only then I use the last results' cityid to search for the related services in the Service table. Which I think is not a good approach as it needs to use a lot of recursive IN searches to filter the results, which is not good for performance.

My colleague then came up with another solution, which put all the search related references into the Service table – something like this:

Solution 2
Table: Service
+------+----------+--------------+--------+----------+-----------+----------+----------+
| id   | name     | description  | cityid | stateid  | countryid | address1 | address2 |
+------+----------+--------------+--------+----------+-----------+----------+----------+
|     1| Service1 | Description1 |      1 |        1 |         1 | Address1 |          |
|     2| Service2 | Description2 |      2 |        2 |         2 | Address2 |          |
|     3| Service3 | Description3 |      3 |        3 |         3 | Address3 |          |
+------+----------+--------------+--------+----------+-----------+----------+----------+

So, if Country matched the search, then use the result's countryid to perform search straight in the Service table, otherwise, if State matched the search, then use the result's stateid to perform the search in Service and so on. This method is more efficient as it doesn't have so much recursive searches, but the downside is it violates the Normalisation practices: the Service table has redundant info, which is countryid and stateid. And logically speaking, I can find those two IDs with only cityid, even though I need to perform multiple look-ups/joins.

So which solution should I go for? Or do you have a better suggestion? Please advise.