The problem is most likely that you have wrong index or doesn't use them at all.

It depends on how you're using Laravel's pagination. If you're using it directly as a query builder / Eloquent method, it should LIMIT no problem. If you're inserting the data manually into a Paginator object, you need to modify the query yourself.

Show us your code if you want specific help.

If you have a ORDER BY (or sth like) clause it fetches all rows and slices them via php. Look in souce to find out whats going on ;)

Well my query look like this :) I tried to remove the orderBy() part, but it still slice pages with php.

$feed = $query->where('trip_date', '!=', '0000-00-00')->where('trip_date', '>=', $curDate);
        $feed->join('feed_routes', 'feed.id', '=', 'feed_routes.feed_id');
        if( !empty($from) ){
            $feed = $feed->where('feed_routes.from', '=', $from);
        }
        if( !empty($to) ){
            $feed = $feed->where('feed_routes.to', '=', $to);
        }
        if( !empty($trip_date) ) {
            $feed = $feed->where('feed.trip_date', '=', $trip_date);
        }
        if( !empty($trip_types) ) {
            $feed = $feed->where(function($query) use ($trip_types){
                foreach( $trip_types as $type ) {
                    $query->orWhere('feed.type', '=', $type);
                }
            });
        }
        $feed = $feed->groupBy('feed.message_id')
            ->orderBy('posted_at', 'DESC')
            ->paginate()
            ->toArray();

Thanks guys, the problem was groupBy() :) I replaced it with ->select(DB::raw('DISTINCT(feed.message_id)')

The performance gain with 50k rows is ~4x :)