Equivalent of a composite index across multiple tables?

Oracle can use both indices. You just don't have the right two indices.

Consider: if the query plan uses your index on mail.sent_date first, what does it get from mail? It gets all the mail.ids where mail.sent_date is within the range you gave in your where clause, yes?

So it goes to mail_to with a list of mail.ids and the mail.name you gave in your where clause. At this point, Oracle decides that it's better to scan the table for matching mail_to.mail_ids rather than use the index on mail_to.name.

Indices on varchars are always problematic, and Oracle really prefers full table scans. But if we give Oracle an index containing the columns it really wants to use, and depending on total table rows and statistics, we can get it to use it. This is the index:

 create index mail_to_pid_name on mail_to( mail_id, name ) ; 

This works where an index just on name doesn't, because Oracle's not looking just for a name, but for a mail_id and a name.

Conversely, if the cost-based analyzer determines it's cheaper to go to table mail_to first, and uses your index on mail_to.name, what doe sit get? A bunch of mail_to_.mail_ids to look up in mail. It needs to find rows with those ids and certain sent_dates, so:

 create index mail_id_sentdate on mail( sent_date, id ) ; 

Note that in this case I've put sent_date first in the index, and id second. (This is more an intuitive thing.)

Again, the take home point is this: in creating indices, you have to consider not just the columns in your where clause, but also the columns in your join conditions.

---

Update

jthg: yes, it always depends on how the data is distributed. And on how many rows are in the table: if very many, Oracle will do a table scan and hash join, if very few it will do a table scan. You might reverse the order of either of the two indices. By putting sent_date first in the second index, we eliminate most needs for an index solely on sent_date.

A materialized view would allow you to index the values, assuming the stringent materialized view criteria is met.