Draconian

Всё зависит от архитектуры самой БД и производительности сервера, начните с MySql.

СУБД не указали.

В общем случае, по-моему, будет примерно так:
Таблица пользователей (с id активного сейчас тарифа). По умолчанию все пользователи бесплатные.
Таблица тарифов.
Поскольку у одного юзера может быть много тарифов, связь N-M, нужна таблица связи:
юзер_тариф (id юзера, id тарифа, датавремя начала действия, датавремя окончания действия, признак is_active)

Джобами проверяем пользователей на активные тарифы, если время вышло - меняем тариф на тот, у которого осталось время, ставим признак is_active в 0, меняем активный тариф в таблице пользователей. Тут же можно вести лог, какого пользователя, когда, с какого на какой тариф перевели.

По-моему, это не корректный запрос, согласно стандарта SQL.
Почему бы id и name не фильтровать отдельно?
Т.е.:

SELECT * 
FROM table
WHERE id in (...) AND name in (...);

В чем у вас необходимость именно такие пары использовать?

Второй вариант с реляционной структурой вполне жизнеспособен. Хорошо индексированная таблица будет работать без проблем и на больших объемах. Вы можете и заранее это проверить, создав структуру и наполнив её большим количеством тестовых данных.
Насчет NoSQL решайте сами, материалов полно, например, вот и вот.

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

Есть подозрение, что нужно либо добавить индексы, либо проверить существующие, потому что выборки по индексированным полям должны выполняться очень быстро при таких размерах.

В остальном, Walt Disney дал правильные советы: разделить эту таблицу на две - архивную (в идеале - партицированную) и оперативную, в которой хранить данные за определенный период, джобами по истечении срока перекидывать эти данные в архив.
Можно еще дополнительно иметь "супер-оперативную" таблицу, в которой хранить необходимые вам уже агрегированные данные, которые обновлять триггерами после вставки информации в оперативную таблицу. Таким образом, после обновления оперативной таблицы, у вас уже будет вся аналитика за текущий период (день\неделю и т.д.).

Что касается аналитики по архиву, из моего опыта, заказчик всегда просит оперативные, быстро работающие отчеты, и агрегированные отчеты по месяцам\годам из архива, которые лишь бы построились. :-)