Setting estimate percentage as DBMS_STATS.AUTO_SAMPLE_SIZE , Oracle determines the best sample size for good statistics (Recommended value 9i). Can we trust it? It depends on which version you use.
On 9.2.04(we experienced) and 9.2.05(Oracle confirmed), if you specify estimate_percent=>dbms_stats.auto_sample_size, it can be extremely slow.
It is bug# 3150750, and has been fixed in 220.127.116.11 as Note:283897.1