Also, on a technical level, let's not equate a government apparatus that both controls and records anything and everything you do online, with a government asking a private company to identify people who searched the name of a girl who was murdered.
Cops can search your car if they have a reason to believe you've committed a crime, but if they just start rifling through every car in a public lot someone is getting sued.