Вы на правильном пути. Если вы расширите оператор count в вашем примере до полного подзапроса, вы получите:
SELECT *,
(SELECT COUNT(*) FROM message_received WHERE unread = 1 AND user_id = $uid) AS unread_count,
FROM message_recieved WHERE user_id = $uid;
Который будет иметь непрочитанное количество, которое вы ищете (в каждом ряду!). MySQL также должен быть достаточно умным, чтобы кэшировать результат этого запроса подсчета, поэтому вы фактически выполнили два запроса по одному соединению.
Наличие метки на каждой строке кажется немного чрезмерным ... Хотя, может быть, это место, где два запроса - лучшая ставка - и вы можете попытаться оптимизировать в другом месте с помощью объединений или чего-то еще, что MySQL Меньше неприятностей - счет боли в доминирующей ягодице.
Надеюсь, это поможет!
PS: Если это PHP, вы должны иметь возможность выполнять любое количество запросов через одно соединение - просто позвоните mysql_query(...)
связка раз перед звонком mysql_close(...)
.