MAX performance degrades

[Paul Smith]

The length of time my MAX query takes to execute gets longer with the amount of data I have in my table. That may seem like a very obvious statement (well it is), but I cannot have my application's performance degrading over time. I need constant performance.

I have a table T1 with columns C1, C2, C3, and C4. C1 is the primary key. I have a multi-part index on C2 and C3. C4 has low cardinality (if that is teh correct terminology for it not having many distinct values).

My query is:
SELECT MAX(C2) FROM T1 WHERE C3='<value>' AND C4='<value>' AND C2<='<value>'

If I double the number of rows in the table then the time to execute the query pretty much doubles too. Is there anything I can do to get constant performance? I know that by doubling the number of rows in the table I am doubling the number of rows that have to be processed by MAX, so I don't suppose indexes are really going to help. I am using version 4.0.20 of MySQL (which, although probably not relevant, I am told can only use one index per query).

Thanks,
Paul