1. Добавляете данные ОДНОВРЕМЕННО сразу в 2-е таблицы: в одну общую историческую таблицу (или можно создавать новую таблицу раз в месяц, пол-года, год) и в таблицу за последний короткий промежуток времени (например, за месяц).
2. Раз в сколько там хотите удаляйте устаревшие данные из таблицы короткого периода: "подрезайте хвост" после сортировки по timestamp-полю.
Таким образом, будет возможность оперативной работы со свежими данными и более длительной работы с архивными данными.
UPD: 100 млн. записей из них надо проверить заходил ли сегодня уже пользователь или нет. То есть эту задачу надо выполнить как можно быстрее, чтобы дальше определить, что делать с ним.
Банально: LastLogon (timestamp) в одном из полей таблицы пользователей.