Generally, the DB engine will also optimize when AND/OR is involved. The index should make a difference.
Adding an index does add to the cost of inserting a record (create an object). However, having a few well placed indices should be no issue. Several dozens of indices will probably cause performance issues. There is a grey area inbetween.
Use your commen sense in determining your index strategy.
Also, try to avoid 'contains' search elements, because an index will not help there. Searching using starts with, greater or less than can be optimized using an index. Don't overdo it by setting an index for every search field.
Some considerations:
Test your scenario using a production (-like) copy in a test environment. Make sure that the test environment has sufficient resources. Quite often you can run some tests without restoring the file document contents.
If you really want to understand how the database is using your indexes, it's best to have a local database and look at the explain plan of the queries executed. You can find some info here: http://mxblog.eu/link/post/sql-is-about-what-data-you-want-not-how-to-get-it
Hi Ralph, I didn't know about the order of the index, so thanks for pointing that one out. For me a rule of thumb is that an index performs best when it contains unique values like the persons last name or a timestamp. Having that said, I'm not sure if it's better to create an index on the enumerator, but your test should verify this.