Design patterns: Making code implementation-agnostic

I want my code to be implementation-agnostic. In this particular case, I want to abstract data storage.
I created IDatasource interface that could be implemented later by SqlStorage, MongoStorage, etc. I noticed that I had to define in interface every method that could be possibly needed. For example, I can have getUser(String name), but if I want getAllUsers(), I could not implement it using getUser(String name) because I don't know in advance all the user's names. So I must add getAllUsers() to IDatasource.
If I'd do this for every new method (e.g. getting only some users that match certain criteria), it would soon become a mess.
I thought of always getting all the users and do a filtering in code, but that doesn't make much sense.
Is there a simpler solution to this or I'm left with huge interface?