I was working for a company about 2-3 years ago, we ran into the same issue. I forgot how many docs the db had but I know it was 1m+, it may have been over 2m. I worked with IBM for over 6 months on it trying every suggestion they had. In the end we decided to split the database so that all open/active records and closed records under 1 year old were in 1 database and everything else went into the secod database. We used an archive agent to copy closed records over 1 yr to the second db. In the end it kept the doc counts about the same in each database. We also purged the deletion stubs and lowered the purge interval.