Laravel / MYSQL (Eloquent) - Querying large table

I am making an online directory, this directory contains businesses, this is how the current table structure is set out:

1) "Business"

• Name
• Phone_Number
• Email

2) Tags

• id
• tag

3) Business_tags

• id
• business_id
• tag_id

There are over 9k rows inside of the business table, and over 84,269 rows and there are over 29k rows inside the ("Business_tags") table (As a business can have multiple tags).

Inside the business model, is the following:

public function tags()
{
   return $this->belongsToMany('App\Tags');
}

The issue is when I am trying to do a search, so for example, let's say that someone wants to search for a "Chinese" then it's takes more time than it probably should to return a value. For example, I am using:

$business = Business::where(function ($business) use ($request) {

    $business->whereHas('tags', function ($tag) use ($request) {

    }); 

})->paginate(20);

Searching takes on average: 35 seconds to display the results.

Here is the raw sql:

select * from `businesses` where (exists (select * from `tags` inner join `business_tags` on `tags`.`id` = `business_tags`.`tags_id` where `business_tags`.`business_id` = `businesses`.`id` and `name` in ('chinese')))

This takes on average: 52.4s to run inside Sequel pro (Using the raw SQL statement)

Any ideas how I can improve the performance of this query so that it's a lot faster? I want to have this functionality, but the user is not going to wait this long for a response!

via Chebli Mohamed