Не.. ну надо же... индексы сильно фрагментируются...
. А я то все думал - почему после вставки "millions of records" система прямо жуть как хочет как минимум пересчитать статистику или индексы перестроить для таблиц, из которых впоследствии планируются много выборок.
Не удержался от сарказма в связи с тем, что автор не поленился узнать процент фрагментированности индексов, хотя в общем-то и так понятно - что после вставки такого количества записей - базе данных явно полагается чего-нибудь там перестроить для того, чтобы активно делать выборки по таблице.