# US 10,372,709 B2 · Estimating string intersections for database systems > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,372,709 B2 - Document ID: US10372709B2 - Status: Granted - Kind: B2 - Application number: 15/349,825 - Filed: 2016-11-11 - Published: 2018-05-17 - Granted: 2019-08-06 - Earliest claimed: 2016-11-11 - Assignees: Sap SE - Applicants: Sap SE - Inventors: Gerhard Hill - Web page: https://patentgrep.com/patent/US10372709B2 ## CPC - G06F 16/24545: {Selectivity estimation or determination} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Some embodiments provide a non-transitory machine-readable medium stores a program. The program receives a query for data that includes an intersection operation on a first set of strings and a second set of strings. The program further generates a plurality of candidate query execution plans based on the query. The program also determines a plurality of execution costs associated with the plurality of candidate query execution plans. The program further selects a query execution plan from the plurality of candidate query execution plans based on the plurality of execution costs. The program also executes the query execution plan to generate a set of query results for the query. ## Claims ### Claim 1 A non-transitory machine-readable medium storing a program executable by at least one processing unit of a computing device, the program comprising sets of instructions for: 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. ### Claim 2 (depends on 1) The non-transitory machine-readable medium of claim 1, wherein the program further comprises a set of instructions for sending the set of query results to a requestor from which the query is received. ### Claim 3 (depends on 1) The non-transitory machine-readable medium of claim 1, wherein the first string interval for the first set of strings represents a range of the first set of strings based on an alphabetical order of the first set of strings, wherein the second string interval for the second set of strings represents a range of the second set of strings based on an alphabetical order of the second set of strings, wherein the third string interval for the intersection of the first and second sets of strings represents a range of the intersection of the first and second sets of strings based on an alphabetical order of the intersection of the first and second sets of strings. ### Claim 4 (depends on 1) The non-transitory machine-readable medium of claim 1, wherein determining the first relative interval length for the first string interval comprises generating numerical representations of endpoints of the first string interval, wherein determining the second relative interval length for the second string interval comprises generating numerical representations of endpoints of the second string interval, wherein determining the third relative interval length for the third string interval comprises generating numerical representations of endpoints of the third string interval. ### Claim 5 (depends on 4) The non-transitory machine-readable medium of claim 4, wherein generating the numerical representations of the endpoints of the first string interval comprises converting characters of strings at the endpoints of the first string interval using an American Standard Code for Information Interchange (ASCII)-based character encoding, wherein generating the numerical representations of the endpoints of the second string interval comprises converting characters of strings at the endpoints of the second string interval using the ASCII-based character encoding, wherein generating the numerical representations of the endpoints of the third string interval comprises converting characters of strings at the endpoints of the third string interval using the ASCII-based character encoding. ### Claim 6 (depends on 5) The non-transitory machine-readable medium of claim 5, wherein determining the execution cost associated with the particular candidate query execution plan further comprises determining a string length of a longest string in the endpoints of the first string interval and the second string interval. ### Claim 7 (depends on 6) The non-transitory machine-readable medium of claim 6, wherein determining the execution cost associated with the particular candidate query execution plan further comprises padding strings in the endpoints of the first string interval and the second string interval other than the longest string with a non-existent character. ### Claim 8 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. ### Claim 9 (depends on 8) The method of claim 8 further comprising sending the set of query results to a requestor from which the query is received. ### Claim 10 (depends on 8) The method of claim 8, wherein the first string interval for the first set of strings represents a range of the first set of strings based on an alphabetical order of the first set of strings, wherein the second string interval for the second set of strings represents a range of the second set of strings based on an alphabetical order of the second set of strings, wherein the third string interval for the intersection of the first and second sets of strings represents a range of the intersection of the first and second sets of strings based on an alphabetical order of the intersection of the first and second sets of strings. ### Claim 11 (depends on 8) The method of claim 8, wherein determining the first relative interval length for the first string interval comprises generating numerical representations of endpoints of the first string interval, wherein determining the second relative interval length for the second string interval comprises generating numerical representations of endpoints of the second string interval, wherein determining the third relative interval length for the third string interval comprises generating numerical representations of endpoints of the third string interval. ### Claim 12 (depends on 11) The method of claim 11, wherein generating the numerical representations of the endpoints of the first string interval comprises converting characters of strings at the endpoints of the first string interval using an American Standard Code for Information Interchange (ASCII)-based character encoding, wherein generating the numerical representations of the endpoints of the second string interval comprises converting characters of strings at the endpoints of the second string interval using the ASCII-based character encoding, wherein generating the numerical representations of the endpoints of the third string interval comprises converting characters of strings at the endpoints of the third string interval using the ASCII-based character encoding. ### Claim 13 (depends on 12) The method of claim 12, wherein determining the execution cost associated with the particular candidate query execution plan further comprises determining a string length of a longest string in the endpoints of the first string interval and the second string interval. ### Claim 14 (depends on 13) The method of claim 13, wherein determining the execution cost associated with the particular candidate query execution plan further comprises padding strings in the endpoints of the first string interval and the second string interval other than the longest string with a non-existent character. ### Claim 15 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. ### Claim 16 (depends on 15) The system of claim 15, wherein the instructions further cause the at least one processing unit to send the set of query results to a requestor from which the query is received. ### Claim 17 (depends on 15) The system of claim 15, wherein the first string interval for the first set of strings represents a range of the first set of strings based on an alphabetical order of the first set of strings, wherein the second string interval for the second set of strings represents a range of the second set of strings based on an alphabetical order of the second set of strings, wherein the third string interval for the intersection of the first and second sets of strings represents a range of the intersection of the first and second sets of strings based on an alphabetical order of the intersection of the first and second sets of strings. ### Claim 18 (depends on 15) The system of claim 15, wherein determining the first relative interval length for the first string interval comprises generating numerical representations of endpoints of the first string interval, wherein determining the second relative interval length for the second string interval comprises generating numerical representations of endpoints of the second string interval, wherein determining the third relative interval length for the third string interval comprises generating numerical representations of endpoints of the third string interval. ### Claim 19 (depends on 18) The system of claim 18, wherein generating the numerical representations of the endpoints of the first string interval comprises converting characters of strings at the endpoints of the first string interval using an American Standard Code for Information Interchange (ASCII)-based character encoding, wherein generating the numerical representations of the endpoints of the second string interval comprises converting characters of strings at the endpoints of the second string interval using the ASCII-based character encoding, wherein generating the numerical representations of the endpoints of the third string interval comprises converting characters of strings at the endpoints of the third string interval using the ASCII-based character encoding. ### Claim 20 (depends on 19) The system of claim 19, wherein determining the execution cost associated with the particular candidate query execution plan further comprises: determining a string length of a longest string in the endpoints of the first string interval and the second string interval; and padding strings in the endpoints of the first string interval and the second string interval other than the longest string with a non-existent character.