There are MANY cases where the government legitimately possesses personal information that could potentially cause harm if revealed, for operational as well as public safety purposes. Vehicle registration and drivers license records, for example.
This personal information is typically exempt from FOIA laws. I can't go FOIA vehicle registration records to look up where a certain driver lives, but the state and police officers do have access to that information.
A search involves access without consent. Police don't need a search warrant to perform a search with the consent of the owner. In the case of cell phone data the search is without the consent of the data owner (the phone company). In this case the municipality is collecting public-view data themselves, not without the consent of the collector, so there's no search warrant issue.