You only need to index common where statements that are used often. Review the query log at the bottom of your pages and check for CB tables then see queries that are repeated or very large and add an index for them if possible.
If I recall correctly you're the user with millions of users on your site. There is no workaround to improving performance. You absolutely must profile your site. This is the only way to find bottlenecks and then fix them. Using xDebug Profiler for example can help profile on a page by page basis (run it on slow pages) to see what's taking forever and take you straight to the lines of code causing the slow down. This is a task that "scale-ability" teams normally handle so it's very possible you need to contact an expert team to help performance optimize your site.
Joomla and any Joomla extensions will require custom changes to fix your scale needs. They all have a "normal" range and you're outside of it and will require scale-ability changes to improve the performance. Even if you have just Joomla and nothing else you'd hit brick walls in performance due to not implementing scale-ability changes.
Simply changes like locking page limit to 25-50 entries only, disabling various Searches (often heavy), etc.. can improve on this performance greatly. You need to find what pages are slowing you down exactly and then profile them.
There's a good read on this for Joomla found below.
groups.google.com/forum/?fromgroups=#!topic/joomla-dev-general/vAvsSNhm8n8
At this time I've never simulated a website with millions of users so I don't really know what more to suggest.
krileon
