admin/settings/search is slow with many nodes

I've been looking into using Drupal with millions of nodes. One problem is that the admin/settings/search page is very slow. This tends to cause CPU quota errors on shared hosting.

The query causing the problem is this one:

SELECT COUNT(*) FROM node n LEFT JOIN search_dataset d ON d.type = 'node' AND d.sid = n.nid WHERE n.status = 1 AND (d.sid IS NULL OR d.reindex <> 0)

which has roughly the same problems as the query in node_update_index(), and could be fixed with a similar approach.