Best way to design / query multi-level relationship table
I would be tempted to deploy all of the techniques you've mentioned. Let me explain. The normalised Service/ City/ State/ Country is great for OLTP processing. So retain it for that part of the application and treat it as the actual data store.

As you mentioned, this is likely to make search complicated so denormalising would be advantageous. Unlike your proposal I would denormalise into a separate table which exists only to assist search. It is an explicit acknowledgement that a real DBMS on an actual computer does not have the performance characteristics the theoretical computer scientists would like to imagine. By putting it in a separate table one isolates the compromised physical necessity from the preferred, normalised design.

Finally I would combine all the search terms in a single column in this denormalised table. One way would be to together the Service Name, City Name, State Name and Country Name, space delimited, and place a full text index on that column.

Another would be to have three columns - id, name and source_table. The first two come from the data values listed in the question. source_table says which of the normalised tables this comes from. Sample data, taken from the question, would be:

  id     name      source_table
  -----  --------  ------------
  1      Service1  Service
  2      Service2  Service
  ...
  1      KL        City  
  3      JB        City
  ...
  2      Penang    State
  ..
  1      Malaysia  Country


The query would match the user's search term against this table's name column:

select
  id,
  source_table
from search_table
where name = &lt;user-provided value&gt;


The returned id and source_table can be used to determine which values to choose from the normalised tables. These can be joined to each other in the normal fashion. Since there are four layers in the hierarchy there can be only four possible queries (service, service/ city, service/ city/ state, service/ city/ state/ country). It would be simple to call the appropriate one like this:

if source_table = "Service"

  select
    &lt;columns&gt;
  from Service
  where id = &lt;search_table.id&gt;

if source_table = "City"

  select
    &lt;columns&gt;
  from Service
  inner join City
    on Service.cityid = City.id
  where City.id = &lt;search_table.id&gt;

... etc.


Be aware that names may be duplicated across these levels (Monaco, for example) and decide what you wish to do with these cases.

The process could be simplified somewhat if names could be guaranteed to be unique and natural keys were used rather than surrogate ones.

I wonder, though, if all this effort is worthwhile. How many rows will there be in these tables? How poor is performance of a query on the normalised tables, with indexes, that compares the user's search value to each name column with ORs between? By creating a representative amount of dummy data and measuring response time on production-like hardware you could save some development, and a lot of maintenance, work.