Handling large databases

In the scheme of things, a few million rows is not a particulary large Database.

Assuming we are talking about an OLTP database, denormalising without first identifying the root cause of your bottlenecks is a very, very bad idea.

The first thing you need to do is profile your query workload over a representative time period to identify where most of the work is being done (for instance, using SQL Profiler, if you are using SQL Server). Look at the number of logical reads a query performs multiplied by the number of times executed. Once you have identified the top ten worst performing queries, you need to examine the query execution plans in detail.

I'm going to go out on a limb here (because it is usually the case), but I would be surprised if your problem is not either

1. Absence of the 'right' covering indexes for the costly queries
2. Poorly configured or under specified disk subsystem

This SO answer describes how to profile to find the worst performing queries in a workload.

As the old saying goes "normalize till it hurts, denormalise till it works".

I love this one! This is typically the kind of thing that must not be accepted anymore. I can imagine that, back at DBASEIII times, where you could not open more than 4 tables at a time (unless changing some of your AUTOEXEC.BAT parameters AND rebooting your computer, ahah! ...), there was some interest in denormalisation.

But nowadays I see this solution similar to a gardener waiting for a tsunami to water his lawn. Please use the available watering can (SQL profiler).

And don't forget that each time you denormalize part of your database, your capacity to further adapt it decreases, as risks of bugs in code increases, making the whole system less and less sustainable.

2 million rows is normally not a Very Large Database, depending on what kind of information you store. Usualy when performance degrades you should verify your indexing strategy. The SQL Server Database Engine Tuning Advisor may be of help there.