In order for databases to find good query plans, they must have accurate statistics about the data. Some databases and setups offer a way to update statistics automatically (e.g. recent versions of postgresql have autovacuum), others may not.

There should be a feature in admincp to run analyze table/vacuum/etc. on all tables used by phpbb.

Support topic where lack of accurate statistics results in a poor query plan: http://www.phpbb.com/community/viewtopic.php?f=46&t=2065265