More efficient ways to do a select count(*)

I see often times applications run such query on a high frequency basis and 
this seemingly harmless query becomes a top cpu consumer.
For whatever reason applications need to do this, how else such query can 
written to avoid the FTS it often does.
In a quick test, I saw doing  count(primary key) is much faster and xplan shows 
index vs. FTS access path.
For this particular issue, there is no PK on the table and using a UK does 
guarantee a not-null value.
Any other ideas (parallel exec is not an option).

Thanks  
--
http://www.freelists.org/webpage/oracle-l

Other related posts: