We had a similar conundrum at LayerVault a few months ago. It can be quite costly to rebuild file histories in a quick manner. We offloaded the tasks and denormalized the data a bit and now our pages scream.