Dynamic temporary index creation

Both, but mostly proactive

It's important to test during development against realistic volumes and quality of data. It's unbelievably common to have a query running on a developers 100 or 1000 rows then fall flat with 10 million production rows.

It allows you to make notes too about "index may help here". Or "revisit me". Or "will fix with new feature xxx in next DB version".

However, a few queries won't stand the test of time. Data distribution changes or it goes exponential because the optimiser decides to use a different join type. In this case, you can only react.

Saying that, for SQL Server at least, the various "missing index" and "longest query" DMV queries can indicate problem areas before the phone call

Edit: to clarify...

Proactive doesn't mean tune every query now. It means tune what you need to (frequently run) to a reasonable response time. Mostly ignore the weekly 3am Sunday report queries.

If I were you I would run a trace specific to hits on that table. It shouldn't be overly intensive since you are restricting it to just queries against that table, from your application. Run just the minimum needed by the DTA (Database Tuning Advisor). Run it for a day here, a day there, make sure you get some end of week days and some end of month days. Then run the whole lot through the DTA.

Here is why, I'm willing to bet that you have specific combinations of columns that are going to come up more often than not. You can create more complex indexes based on that information. You might also find that you can create some correlated statistics. Basically statistics that have more than one column. For example creating a statistic on City and State together may improve queries against those two columns.

However make sure you don't create to many indexes. On a table that large I'm guessing you do a fair number of writes and every additional index added will slow them down. Of course you may do most of your writes during a batch process.

Also make sure that you put an automatic process to update your statistics periodically. With that many rows the statistics aren't going to update on their own very often. Only once 500+20% of the rows have changed, in at 500 mil rows that's a LOT.