Q:

Will adding a NONCLUSTERED INDEX as suggested by DTA improve performance?

I have the following tables defined in the database
Shop Table

ShopId 
ShopName 
Owner
Banner
Header
CityId
ShopImageId
Active

City Table

CityId
CityName
CountryId
RegionId

Country Table

CountryId
CountryName
RegionId

REGION

RegionId
RegionName

ShopImages

Id
Image
ShopId

Here is my select query
SELECT ShopName, Owner, CityName, CountryName,RegionName
FROM Shop S 
INNER JOIN City CT ON CT.CityId=S.CityId
INNER JOIN Country CO ON CO.CountryId=CT.CountryId
INNER JOIN Region R ON CT.RegionId=R.RegionId
LEFT OUTER JOIN ShopImages SI ON S.ShopImageId=SI.Id

WHERE S.Banner like '%restaurant%' OR S.Description like '%restaurant%'
AND S.CityId=10 AND S.Active=1

As of now city table has around 3,000,000 records & Shop has
  40,000,000 + records.

It takes time to fetch records. All the clustered indexes(primary key) were already defined.

I am trying to optimize with the help of DTA(Database Tuning Advisor).
  It suggest me to add the below index

CREATE NONCLUSTERED INDEX 
  [_dta_index_CITY_9_2098106515__K9_K20_K1_K2] ON [dbo].[CITY] 
(
    [COUNTRYID] ASC,
    [REGIONID] ASC,
    [CITYID] ASC,
    [CITYNAME] ASC
)WITH (SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF) 
  ON [PRIMARY]

Is it worth to add this Index? Can i take all the suggesstion from DTA? It suggesting adding some statistics also.
How better how can improve my above query ?

A:

It's hard to say that DTA is wrong when analyzing the indexes, since I do't know the data distribution and it does, but the first indexes I'd add beyond the primary keys is a (possibly composite) index on SHOP.CityID and SHOP.Active.
I can't give you any absolutes without testing, but this is the reasoning.
Since you're basically doing the filtering on SHOP and have no filters on any other table, the heavy lifting of the query would most likely be on filtering the 50M rows in SHOP. 
If the database started joining from any other table, the unfiltered join would result in 3M rows against CITY, and starting with filtering SHOP would most likely result in quite a bit fewer. The compiler likes "fewer" for good reason.
This is the filter on SHOP;
WHERE S.Banner like '%restaurant%' OR S.Description like '%restaurant%'
  AND S.CityId=10 AND S.Active=1

Since LIKE queries starting with % basically can't use indexes at all, you'll want as narrow and quick filtering as possible done by S.CityId=10 AND S.Active=1. If you index those, the other two conditions won't need to scan more than a few rows found using the indexes instead of scanning - possibly - 50M rows.
The only reason I can see that the index suggested would make more than a minor impact is if the CITY table has a large amount of fields, and the index would allow the database to read less data from disk to get to the fields. Not saying it's the case, but only trying it will tell for sure.

