Estimating string intersections for database systems

A method comprising:

• receiving a query for data that includes an intersection operation on a first set of strings and a second set of strings;
• generating a plurality of candidate query execution plans based on the query;
• determining a plurality of execution costs associated with the plurality of candidate query execution plans, wherein the execution cost associated with a particular candidate query execution plan in the plurality of candidate query execution plans is based on a number of strings in the intersection of the first and second sets of strings, wherein determining the execution cost associated with the particular candidate query execution plan comprises:
• determining a number of strings in first set of strings;
• determining a number of strings in second set of strings;
• determining a first string interval for the first set of strings;
• determining a second string interval for the second set of strings;
• determining a third string interval for an intersection of the first and second sets of strings;
• determining a first relative interval length for the first string interval;
• determining a second relative interval length for the second string interval;
• determining a third relative string interval for the third string interval;
• determining a number of strings in the first set of strings that is included in the intersection of the first and second sets of strings based on the first and third relative interval lengths;
• determining a number of strings in the second set of strings that is included in the intersection of the first and second sets of strings based on the second and third relative interval lengths;
• and
• determining the number strings in the intersection of the first and second sets of strings based on the number of strings in the first set of strings that is included in the intersection of the first and second sets of strings based on the first and third relative interval lengths and the number of strings in the second set of strings that is included in the intersection of the first and second sets of strings based on the second and third relative interval lengths;
• selecting a query execution plan from the plurality of candidate query execution plans based on the plurality of execution costs;
• and
• executing the query execution plan to generate a set of query results for the query.

A system comprising:

• a set of processing units;
• and
• a non-transitory computer-readable medium storing instructions that when executed by at least one processing unit in the set of processing units cause the at least one processing unit to:
• receive a query for data that includes an intersection operation on a first set of strings and a second set of strings;
• generate a plurality of candidate query execution plans based on the query;
• determine a plurality of execution costs associated with the plurality of candidate query execution plans, wherein the execution cost associated with a particular candidate query execution plan in the plurality of candidate query execution plans is based on a number of strings in the intersection of the first and second sets of strings, wherein determining the execution cost associated with the particular candidate query execution plan comprises:
• determining a number of strings in first set of strings;
• determining a number of strings in second set of strings;
• determining a first string interval for the first set of strings;
• determining a second string interval for the second set of strings;
• determining a third string interval for an intersection of the first and second sets of strings;
• determining a first relative interval length for the first string interval;
• determining a second relative interval length for the second string interval;
• determining a third relative string interval for the third string interval;
• determining a number of strings in the first set of strings that is included in the intersection of the first and second sets of strings based on the first and third relative interval lengths;
• determining a number of strings in the second set of strings that is included in the intersection of the first and second sets of strings based on the second and third relative interval lengths;
• and
• determining the number strings in the intersection of the first and second sets of strings based on the number of strings in the first set of strings that is included in the intersection of the first and second sets of strings based on the first and third relative interval lengths and the number of strings in the second set of strings that is included in the intersection of the first and second sets of strings based on the second and third relative interval lengths;
• select a query execution plan from the plurality of candidate query execution plans based on the plurality of execution costs;
• and
• execute the query execution plan to generate a set of query results for the query.