To inquire about the query complexity of the following query in SQL

I would like to inquire about the complexity of the following example query in SQL:

SELECT id
from DB
where Country = "India"
    AND Size = "Large"

That is, taking the AND of rows matching the filters for any two columns out of **m>>2** columns. I want to return the first column which contain the ids. Can it be done in time sublinear in the number of rows? Thank you.