I cannot fully agree with previous answer, though the main idea is the same.
Last read timestamp
First of all you have to store last pull timestamp for every user if there is only personal messages, or / and last pull timestamp for every user-channel (chat, stream, room, topic, etc. whatever) pair to keep track of unread messages separately.
Storing flag for every user-notification pair may be a solution too, but often it becomes harder to catch the event of "reading" for each notification in UI (in case this is not emails box) and generally leads to bad user experience.
Query over interval
Every time you get all total unread notifications count (not the difference)
Imaging you have website where people see such counter and you update it with some interval, let's say 30 seconds, and there are 10_000 of visitors reading some articles simultaneously. Then you get 20k rmp or 333 rps only for counter. For 10 second updates you get 60k rmp 1k rps respectively.
The only situation when it' ok is when you are an administer of the website and you have the only table called "notifications" or "news" that are addressed to all its users. It is not supposed to be a lot of rows here.
Keep unread messages count for each user-room pair
So in addition to keeping last pull timestamp you often have to cache unread messages count somewhere, otherwise indices won't help you. Count is quite expensive operation (e.g. in postgres). Depending on messages / posts / notifications table size quite soon it will become a problem.
You may cache counters in memory or in database as well.
In general you can say to whom a message is addressed (if a user authenticated), so at the moment of creating a message you can increment your counters for the user (say, in chat application).
Your cache should be invalided (or set to zero) each time after user reads messages.
Caching messages (capped lists)
Cache last N messages for each room along with last read timestamp
What is the maximum amount of messages you would like to be shown as unread? Suppose your counter has limit, then you can keep track of last N (e.g. 10) messages in each room in memory (Aerospike, Redis, Memcached), then complexity of finding messages created at later than last read timestamp will be CONST (O(N) actually, but N is const) and not depending on database size / indices at all. Make sure you gave enough memory to your cache. Everything exceeding N is flushed.
You get total at the first time, and then difference on updates
You can subscribe your client using pub/sub mechanism via websocket or another protocol. Then when opening page user should get count of unread notifications and then you push these notifications to a client, increment counters, and your client implementation should increase counter on the page.
Using message brokers such as Kafka you can also connect and grab all unread messages automatically (with some restrictions, of course)
- It won't work unless you web app is SPA, in case it's classic page navigation it's almost equal to caching count.*
Hide the count just show label
Don't underestimate what is written on label. It may be 1 unread or 500 unread, but it doesn't really matter. Think first whether blank label (or just with 1), label 10 or label 100 make any difference. Instead of counting them you may use
EXISTS clause in Postgres and just show that there are some of messages. So by developing good UI you can significantly reduce load on database.