Yes it is different, because in the convenience store case, the offended party is supplying evidence it collected itself.
In this case, a third party would be provided evidence.
In this case, a third party would be provided evidence.
It's a pretty common thing for a completely unrelated store's surveillance cameras to have footage of a robbery of another store. That's why police ask every store in the area when one is robbed.
There is a difference between shop owners volunteering camera information and this case. This is closer to all shop owners in town being ordered to turn over the personal information of everyone who bought a shovel, because they found a body that had been buried.
Isn't that literally what is happening here? The police are asking Google who looked for this very specific thing in this very specific area at this very specific time period.