What index strategy to use to improve multi-condition SELECT?
Privet Sergiy,

Index design and cost based query optimizers are complicated subjects, and this isn't the place to cover all aspects, so I will address your specific question.

To satisfy the WHERE clause, the 'optimal' index for your query example might be a composite index on (foo, baz). Why?

Think about a phone book directory, and foo and baz as last name and first name respectively. Let's say you are looking for all records in the phone book where the last name is 'doh', and the first name > 'John'. The composite index on last name, first name the phone directory uses allows you to quickly navigate to the 'doh' section, find the first 'John', and from there just follow the list one by one until you exhaust all 'Doh' last names. Could you do it with an index just on Last name? yes.. but you would need to scan all 'Doh' records. An index on First name only, means you have to scan all 'John's, and all following first names to find your 'Doh's.

If your table consists of just foo and baz, it's a no-brainer.
That said, the fact that your SELECT list uses a *, means that if the index doesn't contain all the data to satisfy the query, an additional 'lookup' will be needed for each row to get the rest of the columns. 
This would be similar to an index at the end of the book, that has a pointer to the relevant page. You could potentially include all columns of the table in the index, but that may cause challenges for data modifications and bloat database size.

The optimizer now needs to decide between using the index, and performing potentially many 'lookups', and if it assumes there will be many of those, it may decide to simply scan the whole table and avoid the lookups. 
This is why cost based optimizers require statistics on the columns to make the right decisions, some engines such as SQL Server also store complete histograms of value distribution for better accuracy.

Different RDBMS engines will handle this differently, so look for resources specific to the engine you are using.

HTH