I have to correct my statement, a query seems to be only linear when using OR.
This however is strange since some weeks ago, I could get good response times when using exclusively AND.
I will investigate on this..