# US 12,111,829 B2 · Instruction level parallelism in a declarative graph query language > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,111,829 B2 - Document ID: US12111829B2 - Status: Granted - Kind: B2 - Application number: 17/822,429 - Filed: 2022-08-25 - Published: 2023-11-02 - Granted: 2024-10-08 - Earliest claimed: 2022-04-29 - Assignees: Microsoft Technology Licensing, LLC - Applicants: Microsoft Technology Licensing, LLC - Inventors: Anders Tungeland Gjerdrum; Tor Kreutzer; Jan-Ove Almli Karlberg - Web page: https://patentgrep.com/patent/US12111829B2 ## CPC - G06F 16/24532: {of parallel queries} - G06F 16/24537: {of operators} - G06F 16/24545: {Selectivity estimation or determination} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Example solutions for executing a query in a declarative graph query language include receiving the query for data in a database and determining if one or both of i) a pattern in the query, and ii) the data in the database render the query suitable for being executed, at least in part, in parallel. If either condition indicates that the query is suitable for being executed, at least in part, in parallel, one or more fork operations and join operations are injected into a query plan, and the query is executed according to the query plan. Some examples further determine whether executing the query in parallel is computing resource-efficient, and only executes computing resource-efficient queries in parallel. ## Claims ### Claim 1 A system for executing a query, the system comprising: a hardware processor; and a computer-readable medium storing instructions that are operative upon execution by the hardware processor to: receive the query in a declarative graph query language for data stored in a graph database; select data parallelizable optimization based on the data in the graph database or pattern parallelizable optimization based on patterns in the query, wherein the data parallelizable optimization and the pattern parallelizable optimization are different types of parallelizable optimization algorithms; determine that executing the query in parallel passes a computing resource efficiency test based on one or more of: traffic shaping inside an execution environment of the query, and load shaping inside the execution environment of the query; inject a fork operation and a join operation into a query plan of the query based on selection of the data parallelizable optimization or the pattern parallelizable optimization, and based on the determination; and execute the query according to the query plan. ### Claim 2 (depends on 1) The system of claim 1, wherein the instructions are further operative to: select both data parallelizable optimization and pattern parallelizable optimization; and inject the fork operation and the join operation into the query plan based on selection of both the data parallelizable optimization and the pattern parallelizable optimization. ### Claim 3 (depends on 1) The system of claim 1, wherein the instructions are further operative to: measure time and an expended resource for executing the query in parallel; and train a machine learning model to determine whether executing the query in parallel passes the computing resource efficiency test based on at least the measured time and the expended resource. ### Claim 4 (depends on 1) The system of claim 1, wherein the pattern parallelizable optimization is selected based on a determination that the query queries two or more non-overlapping subgraphs. ### Claim 5 (depends on 1) The system of claim 1, wherein the data parallelizable optimization is selected based on a determination that the data does not contain a cyclic relationship. ### Claim 6 (depends on 1) The system of claim 1, wherein a statistical model determines that the data in the graph database renders the query suitable for being executed, at least in part, in parallel. ### Claim 7 (depends on 1) The system of claim 1, wherein the data parallelizable optimization is selected based on the data in the graph database being suitable for parallel execution. ### Claim 8 (depends on 1) The system of claim 1, wherein the pattern parallelizable optimization is selected based on the patterns in the query being suitable for parallel execution. ### Claim 9 A method for executing a query, the method comprising: receiving the query in a declarative graph query language for data stored in a graph database; selecting data parallelizable optimization based on the data in the graph database or pattern parallelizable optimization based on patterns in the query, wherein the data parallelizable optimization and the pattern parallelizable optimization are different types of parallelizable optimization algorithms; determining that executing the query in parallel passes a computing resource efficiency test based on one or more of: traffic shaping inside an execution environment of the query, and load shaping inside the execution environment of the query; injecting a fork operation and a join operation into a query plan of the query based on selection of the data parallelizable optimization or the pattern parallelizable optimization, and based on the determination; and executing the query according to the query plan. ### Claim 10 (depends on 9) The method of claim 9, further comprising: selecting both data parallelizable optimization and pattern parallelizable optimization; and injecting the fork operation and the join operation into the query plan based on selection of both the data parallelizable optimization and the pattern parallelizable optimization. ### Claim 11 (depends on 9) The method of claim 9, further comprising: measuring time and an expended resource for executing the query in parallel; and training a machine learning model to determine whether executing the query in parallel passes the computing resource efficiency test based on at least the measured time and the expended resource. ### Claim 12 (depends on 9) The method of claim 9, wherein the pattern parallelizable optimization is selected based on a determination that the query queries two or more non-overlapping subgraphs. ### Claim 13 (depends on 9) The method of claim 9, wherein the data parallelizable optimization is selected based on a determination that the data does not contain a cyclic relationship. ### Claim 14 (depends on 9) The method of claim 9, wherein the data parallelizable optimization is selected based on the data in the graph database being suitable for parallel execution. ### Claim 15 (depends on 9) The method of claim 9, wherein the pattern parallelizable optimization is selected based on the patterns in the query being suitable for parallel execution. ### Claim 16 One or more hardware computer storage devices having computer-executable instructions stored thereon, which, on execution by a computer, cause the computer to perform operations comprising: receiving a query in a declarative graph query language for data stored in a graph database; selecting data parallelizable optimization based on the data in the graph database or pattern parallelizable optimization based on patterns in the query, wherein the data parallelizable optimization and the pattern parallelizable optimization are different types of parallelizable optimization algorithms; determining that executing the query in parallel passes a computing resource efficiency test based on one or more of: traffic shaping inside an execution environment of the query, and load shaping inside the execution environment of the query; injecting a fork operation and a join operation into a query plan of the query based on selection of the data parallelizable optimization or the pattern parallelizable optimization, and based on the determination; and executing the query according to the query plan. ### Claim 17 (depends on 16) The one or more hardware computer storage devices of claim 16, wherein the operations further comprise: selecting both data parallelizable optimization and pattern parallelizable optimization; and injecting the fork operation and the join operation into the query plan based on selection of both the data parallelizable optimization and the pattern parallelizable optimization. ### Claim 18 (depends on 16) The one or more hardware computer storage devices of claim 16, wherein the operations further comprise: measure time and an expended resource for executing the query in parallel; and train a machine learning model to determine whether executing the query in parallel passes the computing resource efficiency test based on at least the measured time and the expended resource. ### Claim 19 (depends on 16) The one or more hardware computer storage devices of claim 16, wherein the pattern parallelizable optimization is selected based on a determination that the query queries two or more non-overlapping subgraphs. ### Claim 20 (depends on 16) The one or more hardware computer storage devices of claim 16, wherein the data parallelizable optimization is selected based on a determination that the data does not contain a cyclic relationship.