any sample of more than 5% would be better and histograms for columns which are frequently joined.. ( which would mostly likely be indexed columns .. which otherwise i dont see why would an index be present
on that col/cols )

For partitions.. i would think stats for new partitions created would be sufficeint, as a general rule, where in application would have increasing amount of data on latest partitions which are mostly on date columns..

Abhay.