I'm guessing that type inference doesn't know what K and V to use for your empty vec![]. It may seem like this doesn't matter, but the compiler still needs a concrete Vec<(K, V)> type in order to resolve the rest of your code.
You could use the explicit "turbofish" syntax on your call, like foo::<Vec<&str, &str>>(vec![]). Or if you can construct an empty Query directly, you can just use that like foo(Query::new()).
Or maybe just add an impl for [(); 0], and you can then call foo([]), which is a little less noisy. It's a good idea to not require unconditional allocation anyway.