Assuming a message is 200 bytes or so, searching millions of messages is trivially doable on your phone (200 MB full text index). Billions is pushing it a bit, but you can work around on the app level (e.g. only index the last month in high traffic groups).