I hope courts require both that the requested search data is very specific to the crime (which you are right, a specific address is specific), and I also think that such requests should be by court order/search warrant. The specificity requirement is most important, but I think law enforcement should not get a blank check to do these sorts of queries. It's a lot harder to convince a judge/jury that a query was too broad after it turned up good evidence compared to rejecting the query before it is run and collected.
That's all from a legal perspective. From a policy perspective, I think our search histories should not be collected in the first place as much as practically possible. In meatspace, libraries are actually very protective of what books you look up/checkout. Seattle City Library actually requires you to opt-in for tracking of your checkout history because they know this sort of data is sensitive.