But if they're getting the history via companies like Google, they'd link together your records just as easily.
I see VPNs often being touted as anonymity tools, when it's my understand not all VPNS have multiple users sharing one IP.
(Ex: it's my understanding that an Algo VPN might obscure your geographic location, it's an IP unique to you. Not clear on how a commercial service like Tunnelbear works - many services tout no logging but seem to stay mum on if IPs are shared)
If any of the above is incorrect, please feel free to jump in and reply but it looks to me like moving as much browsing over to Tor as possible is the best move if you're worried about anonymity and not simply someone owning the wifi you are connected to.