The government is not getting access to (nor asking for) all queries. The government is getting access to information identifying who searched for a term. Google's query may include all search terms but Google obviously already has that data anyways.

This is equivalent to asking FedEx who in a given city was shipped something from a specific address. Sure when FedEx does a search it may technically search over all shipments from any address, but the government isn't getting access to that information. Hardly equivalent to door-to-door searches of every house.