As far as I can see, I would prefer shared queue or limited queue instead of having per client individual queues. This strategy can be used for anything which got data which is shared with multiple users and require synchronization.I'm also very happy to receive any feedback, you'll find my contact info from home page.
First optimization things I usually take a look are:
Goal of these things is to minimize the load caused on server. I've often seen that some applications with large queues generate significant load on server, even if everything is on idle. Load is being generated by repeated checks to large tables without indexes or with too large indexes. In these cases data should be partitioned better or whole strategy of queueing should be changed.
How we can reduce amount of data? Deduplication aka normalize data. In some rare cases this is bad idea, because the joins required could be even worse for the server than just scanning huge tables. But usually it's an good idea, especially if we can separate "small queue" and large data it's referring to.
Some queue systems do store same data for every client in data structures without deduplication. If queues are memory based, this can cause system to run out of memory or memory page swapping aka excessive swapping aka disk trashing.
After these changes, the queue system became virtually free to run. Now it consumes 1000x less disk space, server doesn't basically need to know even about all clients because implementation is fully RESTful no state needs to be kept on server side. And all frequent polls hit check the same portion of the queue table instead of triggering separate disk access to fetch "per client data" as well as minimizes the amount of data that needs to be cached in ram all the time for performance reasons.
Depending from database server and it's data structures this method can be also written so that the queue table is circular log structure by rewriting older records with newer ones. This prevents data fragmentation very efficiently because the queue is always clean continuous queue on disk as well. But this is complex topic and requires detailed knowledge about the database system internals being used. In this case, the circular logging worked beautifully. But as example, SQLite3 uses dynamic record size and replacing older record with slightly larger record could lead to fragmentation. Some databases also provide special Queue type tables, but you can also abuse those to get bad results if you don't consider these matters when designing the solution.