Pagination: Filtering Filters

We have an E-Commerce Platform that has a "product catalog" page with 1000's of results. This catalog is paginated (offset pagination). There are filters which, when activated, filter the results. Our problem is that our filters are not limited to the result set, and are therefore nonsensical.

Example:

Result Set:
Blue Car
Red Car
Blue Book
Yellow Book

Filters:
Colors: [Blue, Red, Yellow]
Items: [Car, Book]

Companies like Amazon, etc. limit the filters shown, so when someone filters on "Book", the only colors available are [Blue, Yellow].

My question is: how is it possible to filter the filters unless the entire queryset is evaluated? And, if the entire queryset is evaluated, why do companies like Amazon use pagination?

Note: My team is using Django with DRF and GraphQl backends, but this should not make a difference.