The source material on page 9 and 10 claims a subpoena is necessary:

https://archive.nytimes.com/www.nytimes.com/interactive/2013...

Therefore, I am confused whether or not a warrant is needed. If the phone networks were straight up selling call records, then surely no law enforcement agency would bother with warrants.

Buying the records could cause issues potentially in court. The selling of 'evidence' can cause various conflicts of interest.

That said I would be completely unsurprised if they were used for 'parallel discovery' purposes.

Call records have never needed a warrant (lookup "pen registers"). Call contents (i.e. wiretaps) have in principle always needed a warrant, modulo many exceptions. These days though, call records seem to be for sale to anyone who wants them, whether or not that is legal.

A private investigator could fill us in, but if you look at the different personal data services you'll see a lot of "check this box to agree that you have a valid legal reason to pay us $75 for your ex's info" type setups. Pirate Code law.

Subscriber data: court order.

Communications: warrant.

Metadata: it depends.

(Not a general rule but a useful heuristic).