I'd simply like to emphasize the bitmap index option. With a billion rows, I can only assume that this is at least a reporting database if not an actual warehouse. If it is a warehouse, it should absolutely use bitmaps. If it is a reporting database, it should probably use bitmaps.
I'm glad you recommend bitmaps because I've gone that way on my database.
The only problem I've found is that Oracle seems a bit reluctant to use them if you only query on a single column. Sometimes, you have a column with badly distributed data e.g. one value might have a million records, another might have only 1. It would be nice if the optimizer was smart enough to work out that the bitmap index should be used for the row with only 1 value.
It will do this with B*tree indexes but with bitmaps it never does. It doesn't help if you do "alter table estimate/compute statistics for indexed columns". This is despite the fact that it is often clearly more efficient to use the bitmap than do a full table scan. I've done tests where I've used a hint to tell the optimizer to use the bitmap and it is definitely much quicker.