Suppose I have a table with millions strings in it as keys. What data structure can I use in order to efficiently support only queries like that?

select *
from table
where key contains (('cat' and 'dog') or 'apple')

example of strings that should be selected:

cat loves dog
cat and dog
apple trees

The collection is static.

  • $\begingroup$ "should" is a matter of opinion. What are the criteria you plan to use for evaluating candidate solutions? Please be more explicit about the set of queries you must support. A single example is not enough to identify precisely exactly which operations it must support. Also, please include all information in the question (you can edit your question) - don't leave clarifications in the comments. We want questions to stand on their own for people who encounter them for the first time, without requiring people to read the comments to understand your requirements. $\endgroup$
    – D.W.
    Dec 17, 2021 at 4:18
  • $\begingroup$ @D.W. Changed "should" to "can". $\endgroup$
    – indigo153
    Dec 17, 2021 at 8:32
  • $\begingroup$ My other comments about criteria and queries remain unaddressed. You can use any data structure you like, though some might be really slow. We require you to state your requirements and the criteria you want to use to evaluate answers. $\endgroup$
    – D.W.
    Dec 17, 2021 at 8:35
  • $\begingroup$ @D.W. I want to eliminate some really slow, and choose between fast (I don;t know how fast it can be solved that is why I didnt specify any constrains on search) $\endgroup$
    – indigo153
    Dec 17, 2021 at 10:14
  • $\begingroup$ What research have you done? What approaches have you already considered? Which ones have you rejected? Why did you reject them? Please show us in the question. Also, I encourage you to use that to help you articulate your requirements or evaluation metrics. See meta.stackoverflow.com/q/261592/781723. Again, if we don't know the set of queries you want to support, I don't know how we can possibly suggest a data structure. $\endgroup$
    – D.W.
    Dec 17, 2021 at 19:09


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.