Yeah, it has got to be a bug. The database server has gone absolutely haywire since upgrading to 3.1, patch or no patch.
I have the exact same problem. Large site, ~200k posts.
Patching query.php seemed to help a lot up until 3.0.4, but since upgrading to 3.1 we’re having big problems with mysql performance – even with a patched query.php (from http://core.trac.ww.wp.xz.cn/ticket/10964).
Like for k-factor above, cached pages are delivered fine, but the CPU often is maxing out for a single query.
I’m at a loss.
