> Yes it is a multi-key index, and the matches are exact.
>
> Someone else asked why I have separated these fields out from the
> mail_date.
>
> If I didn't, and I wanted to see the messages for this month, I'd have
> to regex and that would overwhelm the database.
As I said in that mail you could use a between first and last day of month
which can use an index and do the order by with that index.
Unfortunately a datepart(mail_date, year to month) is probably not
understood as indexable by the optimizer.
Andreas