Movable Type 4.21 publication slow

This is not my idea of good performance. This is 1400 entries. It used to take about 10-20 minutes. What's going on?

Update 2008-10-30: Here is just the entries. Yes, 144 minutes for the 1400 entries in this weblog. That's 10 per minute. I thought Movable Type 4.21 was supposed to be faster?

Update 2008-10-31: In an effort to assist my website host, webhosting4life.com, in isolating the problem< I republished my website this afternoon. It took a really long time: 251 minutes.

I've provided a number of ideas for them to explore:

It appears that the queries are all causing table scans. I've looked at the phpmyadmin system variables for MySQL and they are consistent with large numbers of table scans due to missing keys in searches.

If no activity was found on my database, then perhaps the MySQL activity is from another user. These MySQL settings are both database and global settings:

• Slow_queries
• Handler_read_rnd
• Handler_read_rnd_next
• Select_full_join
• Select_range_check

All of these values are exceptional and all suggest queries that are not properly hitting indexes, causing table scans. Again, I recommend looking at the slow queries log.

Right now, 10% of the queries to the database my website uses have taken more than long_query_time seconds. That seems a really high ratio.

Update 2008-10-31: Another personal best: 19 hours, 47 minutes.