The only time I've ever noticed a performance increase in de-normalizing was for aggregate-type queries. It is hard to, on the fly, take a 4+ million row and SUM( * ) or COUNT or AVG etc. WHERE some_composite_key = XYZ AND other_things
So we store the de-normalized version in a table with the counts and update them when a new row is inserted. The UPDATE cost is far less than the SELECT since we're updating a single row in a small table (< 40,000 rows).
The other problem situation I've noticed is on JOIN type queries
For example, this forum software stores forums and moderators in separate tables. If you were to JOIN the moderators and forum to each other in order to grab the mods of all the forums and the forum info in one query you will have a LOT of I/O. Why? Because the join will pull back lots of duplicate forum information, e.g.:
SELECT f.*,
u.username,
u.userid
FROM forum f
INNER JOIN forum_moderator fm ON fm.forumid = f.forumid
INNER JOIN user u ON u.userid = fm.userid
So if you have 10 moderators you're going to have all the forum info duplicated, like this:
forumid, forum_title, etc. ... username, userid
-----------------------------------------------
1, 'Forum title', ... 'MattR', 1
1, 'Forum title', ... 'Joebob', 2
1, 'Forum title', ... 'Hippy', 23
1, 'Forum title', ... 'Admin', 234
1, 'Forum title', ... 'UserA', 3461
1, 'Forum title', ... 'UserB', 331
1, 'Forum title', ... 'Happy Gilmore', 97121
Which leads to a LOT of I/O back to your client application.
It's not necessarily a good candidate for de-normilization but if you say stored the forum moderators in a single row (horribly denormalized by forum_moderator( username1, userid1, username2, userid2, ... )) you could bring back the mods in a single result set.