BI performance has a lot to do with what OLAP and presentation layer
tools you might be using. You haven't specified those. Is it Analysis
Services? 2000 or 2005?
Billions of rows is not an unusual size for a fact table but even a few
thousand rows can be "unwieldy" if you don't have the right model and
architecture.