@mariusor as VK shows, some people just add everyone as a friend. VK has a limit of 10000 friends per account.
Also, are you sure about *arbitrary* fields? I store everything in a relational database, so I can only really query on fields that have indexes on them unless I'm okay with it going through the entire table row by row (I'm not).
Maybe you should specify a response for when the query client asked for isn't possible to easily satisfy.
@grishka I'm not sure I need to worry about that kind of optimization just yet. Whatever you might think, an individual server will never grow to the size of a VK. Worrying about it before you're 1% of the way there is not going to help you I believe.