It seemed odd to me too that a single API call could cause that much work. Granted, I have no idea how the actual app works. But one way to do this is to have clients belong to groups, then record if a group got a message (few writes).

Then for each client pull the groups the client belongs to and look for new messages (possibly more reads than storing the messages on a per-client basis).

It's an extra database table and layer of indirection, but that's one way.