помоему нужно проектировать не базу, а логику работы. У вас одновременно будет выполняться "обновление" всех 1мил. пользователей? Для нормального сервера базы данных 1мил. записей это мелочь, обработает достаточно быстро. Тем более выполнит агрегатные операции, как подсчет количества записей вообще на лету. Поэтому самый удачный будет способ обычного листа.
@Cyapa вам хороший совет дал: используйте суррогатные ключи. Скорость работы на них значительная, запросы по размерам уменьшаются, а логика работы становится ясной и понятной.