Finding the top K most similar sets
Do you have any information about your data set? Is it sparse, will most similarities be zero? Is the total dictionary small? You could consider a inverted index. For example

word  query_id
W1    [1, 3, 6]
W2    [2, 5]
W3    [1, 3, 4]
W4    [2, 3, 4]
W5    [2, 3, 6]

query_id  query
1         W1 W3
2         W2 W4 W4
3         W1 W3 W4 W5
4         W3 W4
5         W2
6         W1 W5


Here W_i is a word, e.g. birthday and query_id is the id of the query in the database. e.g. {how, are, you} might have id 22. Now you get a query {W1 W3 W5}. Aggregate counts on the inverted index. W1 was seen in queries 1, 3, and 6. W3 in 1, 3, and 4, etc.

query_id  count
1         2
2         1
3         3
4         1
6         2


The count will the number of words in common with the incoming query, this is the numerator of the jaccard similarity. So, to find the top k you can start with the queries with the highest count. query_id 3 has the highest count and its similarity is 3/4.

If you have a massive database there are techniques like locality sensitive hashing which will basically reduce the search space into a small bucket. The incoming query gets hashed and lands in a bucket. You can then do a linear search with all the queries in this bucket to find the nearest k.