Search players

I am developing a mobile game using PlayFab as backend.

I am currently working with the friends list, which works well based on PlayFab specs. However, I am thinking of a search function to find players from the client. PlayFab do not support that due to the potential number if API calls that could generate, it may be millions if the game is successful.

I will also use a cloud database and have been thinking of duplicating the core player data to the DB as well as PlayFab at registration. Doing so I could do whatever I want in regards to search and other tasks.

Given the raw number of players that a successful game can have I would like to get som ideas and advise how to manage the topic of search for payers to add as friends. I know that my game may not attract millions of players but want to develop as if it would (it's a hope).

Cheers