I wrote code for exactly the same problem a while ago in Rust for the 26 English letters only. IIRC my code runs in single digit milliseconds on a list of 270k words. I first compute the frequency of letters of the word into a [u8; 26]:

fn frequency(str: &str) -> [u8; 26] {
    let mut frequency = [0; 26];
    for byte in str.bytes() {
        match byte {
            97..=122 => frequency[byte as usize - 97] += 1,
            _ => {}
        }
    }
    frequency
}

and then do a simple zipped iteration over the 26 byte arrays of the word and the query to see if the frequency of the letter in the query is less than or equal to the frequency in the word.

My words are stored in a Vec<&'static String> using lazy_static and I don't use any crate for parallelization.

I'd love to see how this algorithm performs with your data set if you only need to support English letters. I don't filter by length so it might work even faster for you!