How much time will a vacuum/autovacuum operation take?

Question

I manage a big (some hundreds of gigs) database containing tables with various roles, some of them holding millions of records. Some tables only receive large number of inserts and deletes, some other few inserts and large number of updates.

Database runs on PostgreSQL 8.4 on a Debian 6.0 amd64 system with 16 gigabytes of RAM.

The question is sometimes autovacuum process on a table, takes a very long time (days) to complete. I want to be able to roughly tell how much time a particular vacuum command will take, to be able to decide whether to cancel it or not. Also if there were a progress indicator for postgres vacuum operations, it would be really helpful.

Edit:

I'm not looking for a bullet-proof solution. Just a rough hint on the number of dead tuples or necessary I/O bytes is enough to decide. It is really annoying to have no clue when VACUUM will finish, whatsoever.

I've seen that pg_catalog.pg_stat_all_tables has a column for number of dead tuples. So it is possible to have an estimation, even if it means one has to ANALYZE the table before. On the other hand, autovacuum_vacuum_threshold and autovacuum_vacuum_scale_factor settings alone prove that postgres itself knows something about the amount of change on the tables and probably puts it in the hands of the DBA too.

I'm not sure what query to run, because when I run VACUUM VERBOSE, I see that not only tables, but indexes on them are being processed too.