How does size affect this query?

[Dan Bress]

I have a table with about 120 million records in it
each record has a state column, and a date column

I am executing the query

select distinct(thingid) from table where state=1 order by datecolumn asc limit 150;

i have an index of state,datecolumn

if the number of items in a state of 1 is small(less than 10,000) this query very very quickly. However, right now there are several million records in a state of 1, and this is causing the query to slow down to take a second or two per call.


It seems like having more records in a state of 1 slows things down.
Is this expected? Is there anything we can do to improve this?