Query with pagination slow performance when LESS than 10 records

I am facing slow performance on a paginated query. When it has to fetch less than 10 records, it takes one minute. When its more than 10, it takes half a minute. If it is more than a thousand it takes 5 seconds!!!

Yes, the more data it has to fetch, the faster it is!!!!!!

The query:

$facilities = auth()->user()->facilities;
        $notSentStatusId = PlacementOpportunityStatus::where('StatusName', 'Not Sent')->first()->id;

        $caseFacilities = QueryBuilder::for(PlacementOpportunity::class)
            ->whereIn('facilityId', $facilities->pluck('facilityId'))
            ->whereNotNull('datePoEmailSent')
            ->where('active', 1)
            ->where('caseId', '>', 0)
            ->where('statusId', '>', 0)
            ->where('statusId', '!=', $notSentStatusId)
            ->with('case.client', 'case.resident', 'status', 'facility')
            ->allowedFilters([
                AllowedFilter::custom('query', new FilterProviderCaseFacilities),
                AllowedFilter::custom('facility', new FilterProviderCaseFacilities),
                AllowedFilter::custom('typeOfAdmission', new FilterProviderCaseFacilities),
                AllowedFilter::custom('caseStatus', new FilterProviderCaseFacilities),
                AllowedFilter::custom('placementStatus', new FilterProviderCaseFacilities),
                AllowedFilter::custom('dates', new FilterProviderCaseFacilities),
                AllowedFilter::custom('tourDates', new FilterProviderCaseFacilities),
            ])
            ->defaultSort('-datePoEmailSent');

        if ($request->has('dashboard') && $request->dashboard) {
            $caseFacilities->whereIn('statusId', explode(',', $request->dashboard));
            $caseFacilities->whereHas('case', function ($query) {
                $query
                    ->where('archived', 0)
                    ->whereNotIn('caseStatus', ['Won', 'Lost']);
            });
        }

        if ($request->has('sort')) {
            $caseFacilities->allowedSorts([
                AllowedSort::field('statusId'),
                AllowedSort::field('datePoEmailSent'),
                AllowedSort::custom('placementStatusName', new SortByRelationship, 'status.StatusName'),
                AllowedSort::custom('facility.facilityName', new SortByRelationship, 'facility.facilityName'),
                AllowedSort::custom('case.placementType', new SortByRelationship, 'case.placementType'),
                AllowedSort::custom('case.caseStatus', new SortByRelationship, 'case.caseStatus'),
                AllowedSort::custom('case.caseReference', new SortByRelationship, 'case.caseReference'),
                AllowedSort::custom('case.resident.firstName', new SortByThirdLevelRelationship, 'case.resident.firstName'),
            ]);
        }

        return PlacementOpportunityResource::collection($request->has('perPage') ? $caseFacilities->paginate($request->perPage) : $caseFacilities->paginate(config('pagination.per_page')));

This query is used to load columns in a Kanban. The Kanban has 6 columns. One separate api call for each column. Depending on the statusId is how I identify which data has to be fetched.

StatusId that has 3000 records or more to be fetched are loaded in 5 seconds.

StatusId that has 15 records are loaded in 30 seconds.

StatusId that has only 1 record are loaded in more than a minute.

Also, since the data is paginated, when i go to the second page of the statusId with 3000 records, it loads the data in less than 3 seconds. BUT if i go to the second page of the statusId with 15 records, it takes more than 30 seconds to load! Hence the title of this issue 'slow performance when LESS than 10 records'!

I already isolated so that ONLY the column with one record is api called, and the issue persists. It takes more than a minute. I though maybe the columns with thousands of records were interfering in the performance, but this proofs this is not the case

Honestly, it is really weird! Has anybody seen something like this? Any suggestions?

Thank you!