COUNT(id) or MAX(id) - which is faster?

In MySQL InnoDB, SELECT COUNT(id) WHERE secondary_index = ? is an expensive operation and when the user has a lot of messages, this query might take a long time. Even when using an index, the engine still needs to count all matching records. The performance will degrade with growing total message count.

On the other hand, SELECT MAX(id) WHERE secondary_index = ? can deliver the highest id in that index in almost constant time by doing a simple drilldown in the B-Tree structure of the index.

If you want to understand why, consider looking up how the B+Tree data structure works, which is used by InnoDB to structure the rows of your tables and indexes.

I suggest you go with SELECT MAX(id), if the requirement is only to check if there are new messages (and not the count of them).

Also, if you rely on the message count you might open a gap for race conditions. What if the user deletes a message and receives a new one between two polling intervals?

To have the information that someone has new messages - do exactly that. Update the field in users table (I'm assuming that's the name) when a new message is recorded in the system. You have the recipient's ID, that's all you need. You can create an after insert trigger (assumption: there's users2messages table) that updates users table with a boolean flag indicating there's a message.

This approach is by far faster than counting indexes, be the index primary or secondary. When the user performs an action, you can update the users table with has_messages = 0, when a new message arrives - you update the table with has_messages = 1. It's simple, it works, it scales and using triggers to maintain it makes it easy and seamless. I'm sure there will be nay-sayers who don't like triggers, you can do it manually at the point of associating a user with a new message.