# US 11,907,221 B2 · Scheduling parallel execution of query sub-plans > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,907,221 B2 - Document ID: US11907221B2 - Status: Granted - Kind: B2 - Application number: 17/804,770 - Filed: 2022-05-31 - Published: 2023-06-22 - Granted: 2024-02-20 - Earliest claimed: 2021-12-17 - Assignees: Snowflake Inc. - Applicants: Snowflake Inc. - Inventors: Sebastian Breß; Moritz Eyssen; Max Heimel - Web page: https://patentgrep.com/patent/US11907221B2 ## CPC - G06F 16/24545: {Selectivity estimation or determination} - G06F 16/24532: {of parallel queries} - G06F 16/24537: {of operators} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Sub-plans are executed in parallel using a plurality of execution nodes, which can be part of a data platform. In particular, various embodiments identify sub-plans (e.g., fragments or portions of one or more child operators) of a root operator in a query plan such that the identified sub-plans that are candidates for execution on a single execution node, determine a cost estimate for causing the candidate sub-plans to be executed in parallel using multiple execution nodes, and cause the candidate sub-plans to be executed in parallel based on the cost estimate. ## Claims ### Claim 1 A system comprising: at least one hardware processor; and at least one memory storing instructions that cause the at least one hardware processor to perform operations comprising: accessing a query plan that comprises at least one root operator, the at least one root operator being associated with a plurality of sub-plans; identifying, from the plurality of sub-plans, a sub-plurality of sub-plans that each involves processing a data set that satisfies a set of criteria; estimating a first cost for executing individual sub-plans of the sub-plurality of sub-plans successively using a plurality of execution nodes; estimating a second cost for executing the sub-plurality of sub-plans in parallel using the plurality of execution nodes; comparing the first cost to the second cost; determining, based on the comparing, whether the sub-plurality of sub-plans is to be executed in parallel using the plurality of execution nodes; and in response to determining that the sub-plurality of sub-plans is to be executed in parallel using the plurality of execution nodes, causing the sub-plurality of sub-plans to be executed in parallel using the plurality of execution nodes by performing, for each single sub-plan in the sub-plurality of sub-plans, a single scheduling operation to assign execution of an entire portion of the single sub-plan to a single execution node of the plurality of execution nodes, the single execution node being configured to generate a local schedule queue to process the single sub-plan assigned to the single execution node. ### Claim 2 (depends on 1) The system of claim 1, wherein the determining, based on the comparing, whether the sub-plurality of sub-plans is to be executed in parallel using the plurality of execution nodes comprises: based on the comparing, determining whether the first cost is greater than the second cost; and in response to determining that the first cost is greater than the second cost, determining to execute the sub-plurality of sub-plans in parallel using the plurality of execution nodes. ### Claim 3 (depends on 1) The system of claim 1, wherein the determining, based on the comparing, whether the sub-plurality of sub-plans is to be executed in parallel using the plurality of execution nodes comprises: based on the comparing, determining whether the first cost is at least greater than the second cost by a threshold value; and in response to determining that the first cost is at least greater than the second cost by the threshold value, determining to execute the sub-plurality of sub-plans in parallel using the plurality of execution nodes. ### Claim 4 (depends on 3) The system of claim 3, wherein the threshold value comprises a ratio of the first cost and the second cost. ### Claim 5 (depends on 1) The system of claim 1, wherein the data set comprises one or more files. ### Claim 6 (depends on 1) The system of claim 1, wherein the at least one root operator comprising a join operator. ### Claim 7 (depends on 1) The system of claim 1, wherein the at least one root operator comprising a union all operator. ### Claim 8 (depends on 1) The system of claim 1, wherein sub-plans in the sub-plurality of sub-plans have a same set of dependencies. ### Claim 9 (depends on 8) The system of claim 8, wherein the operations comprise: maintaining a dependency map that describes one or more dependencies between individual operators to be executed, the dependency map being initialized based on the query plan, and the identifying the sub-plurality of sub-plans being based on the dependency map. ### Claim 10 (depends on 1) The system of claim 1, wherein the operations comprise: selecting the at least one root operator from a global scheduling queue. ### Claim 11 (depends on 1) The system of claim 1, wherein the set of criteria includes one or more criteria for identifying the data set that is capable of being executed by a single execution node. ### Claim 12 A method comprising: accessing a query plan that comprises at least one root operator, the at least one root operator being associated with a plurality of sub-plans; identifying, from the plurality of sub-plans, a sub-plurality of sub-plans that each involves processing a data set that satisfies a set of criteria; estimating a first cost for executing individual sub-plans of the sub-plurality of sub-plans successively using a plurality of execution nodes; estimating a second cost for executing the sub-plurality of sub-plans in parallel using the plurality of execution nodes; comparing the first cost to the second cost; determining, based on the comparing, whether the sub-plurality of sub-plans is to be executed in parallel using the plurality of execution nodes; and in response to determining that the sub-plurality of sub-plans is to be executed in parallel using the plurality of execution nodes, causing the sub-plurality of sub-plans to be executed in parallel using the plurality of execution nodes by performing, for each single sub-plan in the sub-plurality of sub-plans, a single scheduling operation to assign execution of an entire portion of the single sub-plan to a single execution node of the plurality of execution nodes, the single execution node being configured to generate a local schedule queue to process the single sub-plan assigned to the single execution node. ### Claim 13 (depends on 12) The method of claim 12, wherein the determining, based on the comparing, whether the sub-plurality of sub-plans is to be executed in parallel using the plurality of execution nodes comprises: based on the comparing, determining whether the first cost is greater than the second cost; and in response to determining that the first cost is greater than the second cost, determining to execute the sub-plurality of sub-plans in parallel using the plurality of execution nodes. ### Claim 14 (depends on 12) The method of claim 12, wherein the determining, based on the comparing, whether the sub-plurality of sub-plans is to be executed in parallel using the plurality of execution nodes comprises: based on the comparing, determining whether the first cost is at least greater than the second cost by a threshold value; and in response to determining that the first cost is at least greater than the second cost by the threshold value, determining to execute the sub-plurality of sub-plans in parallel using the plurality of execution nodes. ### Claim 15 (depends on 14) The method of claim 14, wherein the threshold value comprises a ratio of the first cost and the second cost. ### Claim 16 (depends on 12) The method of claim 12, wherein the data set comprises one or more files. ### Claim 17 (depends on 12) The method of claim 12, wherein the at least one root operator comprising a join operator. ### Claim 18 (depends on 12) The method of claim 12, wherein the at least one root operator comprising a union all operator. ### Claim 19 (depends on 12) The method of claim 12, wherein sub-plans in the sub-plurality of sub-plans have a same set of dependencies. ### Claim 20 (depends on 19) The method of claim 19, comprising: maintaining a dependency map that describes one or more dependencies between individual operators to be executed, the dependency map being initialized based on the query plan, and the identifying the sub-plurality of sub-plans being based on the dependency map. ### Claim 21 (depends on 12) The method of claim 12, comprising: selecting the at least one root operator from a global scheduling queue. ### Claim 22 (depends on 12) The method of claim 12, wherein the set of criteria includes one or more criteria for identifying the data set that is capable of being executed by a single execution node. ### Claim 23 A non-transitory computer-readable medium comprising instructions that, when executed by one or more processors of a machine, configure the machine to perform operations comprising: accessing a query plan that comprises at least one root operator, the at least one root operator being associated with a plurality of sub-plans; identifying, from the plurality of sub-plans, a sub-plurality of sub-plans that each involves processing a data set that satisfies a set of criteria; estimating a first cost for executing individual sub-plans of the sub-plurality of sub-plans successively using a plurality of execution nodes; estimating a second cost for executing the sub-plurality of sub-plans in parallel using the plurality of execution nodes; comparing the first cost to the second cost; determining, based on the comparing, whether the sub-plurality of sub-plans is to be executed in parallel using the plurality of execution nodes; and in response to determining that the sub-plurality of sub-plans is to be executed in parallel using the plurality of execution nodes, causing the sub-plurality of sub-plans to be executed in parallel using the plurality of execution nodes by performing, for each single sub-plan in the sub-plurality of sub-plans, a single scheduling operation to assign execution of an entire portion of the single sub-plan to a single execution node of the plurality of execution nodes, the single execution node being configured to generate a local schedule queue to process the single sub-plan assigned to the single execution node. ### Claim 24 (depends on 23) The non-transitory computer-readable medium of claim 23, wherein the determining, based on the comparing, whether the sub-plurality of sub-plans is to be executed in parallel using the plurality of execution nodes comprises: based on the comparing, determining whether the first cost is greater than the second cost; and in response to determining that the first cost is greater than the second cost, determining to execute the sub-plurality of sub-plans in parallel using the plurality of execution nodes. ### Claim 25 (depends on 23) The non-transitory computer-readable medium of claim 23, wherein the determining, based on the comparing, whether the sub-plurality of sub-plans is to be executed in parallel using the plurality of execution nodes comprises: based on the comparing, determining whether the first cost is at least greater than the second cost by a threshold value; and in response to determining that the first cost is at least greater than the second cost by the threshold value, determining to execute the sub-plurality of sub-plans in parallel using the plurality of execution nodes. ### Claim 26 (depends on 25) The non-transitory computer-readable medium of claim 25, wherein the threshold value comprises a ratio of the first cost and the second cost. ### Claim 27 (depends on 23) The non-transitory computer-readable medium of claim 23, wherein the data set comprises one or more files. ### Claim 28 (depends on 23) The non-transitory computer-readable medium of claim 23, wherein the at least one root operator comprising a join operator. ### Claim 29 (depends on 23) The non-transitory computer-readable medium of claim 23, wherein the at least one root operator comprising a union all operator. ### Claim 30 (depends on 23) The non-transitory computer-readable medium of claim 23, wherein sub-plans in the sub-plurality of sub-plans have a same set of dependencies.