Laravel Eloquent - Search for record in child table

I'm trying to implement an efficient search on street names. A street has multiple residences (houses). The search I'm trying to build is street names LIKE %example% within the given city_id. The result must include the LIKE list of matching street name, and the name of the city it belongs to (with the given city_id in $request).

Some things that I have tried:

Search from the Residence table:

$residences = FrResidence::where('city_id', $request->city_id)->whereHas('street', function ($q) use ($request) {
    $q->where('name', 'LIKE', "$request->name%");
})->limit($limit)->get();

The issue with this approach is that I need unique street names. And as streets belong to multiple residences I get the same results multiple items.

The other thing I have tried is to search LIKE from street, and find the matching city afterward. This works. However, requests can take up to 15 seconds (as the Residences table has 20+ million records):

// Find matching street
$streets = FrStreet::where('name', 'LIKE', "$request->name%")->limit($limit)->get();
$response = [];
foreach ($streets as $street) {
    // Find matching residence
    $filter = [['street_id', $street->id]];

    // Add optional filters
    if ($request->has('city_id')) {
        array_push($filter, ['city_id', $request->city_id]);
    }

    $residence = FrResidence::where($filter)->first();
    if (!empty($residence)) {
        array_push(
            $response,
            $searchResponseController->createStreetResult($country, [
                'name' => $street->name,
                'street_id' => $street->id,
                'cityName' =>  $residence->city->name,
                'cityId' => $residence->city->id
            ])
        );
    }
}

What is the best and fastest way to do this?

The database setup I have is: Street has many Residences

Street model:

protected $fillable = [
    'id',
    'name',
    'externalIdentifier'
];

public function residences()
{
    return $this->hasMany('\App\Models\Addresses\fr\Residence', 'street_id', 'id');
}

City model:

protected $fillable = [
    'id',
    'name'
];

public function residences()
{
    return $this->hasMany('\App\Models\Addresses\fr\Residence', 'city_id', 'id');
}

Residence model

protected $fillable = [
    'id',
    'number',
    'postalcode_id',
    'street_id',
    'city_id',
];

public function street()
{
    return $this->belongsTo('\App\Models\Addresses\fr\Street', 'street_id', 'id');
}

public function city()
{
    return $this->belongsTo('\App\Models\Addresses\fr\City', 'city_id', 'id');
}