# US 11,341,132 B2 · Generating a producer-driven execution plan from a consumer-driven iterator-based execution plan > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,341,132 B2 - Document ID: US11341132B2 - Status: Granted - Kind: B2 - Application number: 14/841,713 - Filed: 2015-09-01 - Published: 2017-03-02 - Granted: 2022-05-24 - Earliest claimed: 2015-09-01 - Assignees: Sybase, Inc. - Applicants: Sybase, Inc - Inventors: Xiaobin Ma; Xun Cheng; Prabhas Kumar Samanta - Web page: https://patentgrep.com/patent/US11341132B2 ## CPC - G06F 16/24542: {Plan optimisation} - G06F 16/2246: {Trees, e.g. B+trees} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract An original query execution plan of a database query is received. The original query execution plan represents a tree of operators. Source code for the original query execution plan is generated by a single traversal of the tree of operators. The generated source code is compiled into native machine code. The native machine code represents a simplified native access plan (SNAP). ## Claims ### Claim 1 A computer implemented method to generate a simplified native access plan (SNAP) from an original query execution plan, the method comprising: receiving an original query execution plan of a database query of a database system, wherein the original query execution plan represents a tree of operators; determining whether the database system is configured to permit processing of the SNAP; wherein in response to determining that the database system is configured to permit the processing of the SNAP, at runtime, generating source code for the original query execution plan by a single traversal of the tree of operators; during generating the source code, converting a nested loop join in the original query execution plan from an iterator-based model to a single function consisting of a doubled loop; including in the doubled loop a function to send a respective row to a client process after the doubled loop generates each respective row; the single traversal traversing the tree of operators beginning at a root node and generating the source code from a bottom of the tree of operators upward; and at runtime, compiling the generated source code into native machine code, wherein the native machine code represents the SNAP. ### Claim 2 (depends on 1) The method of claim 1 further comprising: storing the SNAP for subsequent execution of the database query, wherein upon receiving a subsequent request to execute the database query, the SNAP is invoked to produce a result for the database query. ### Claim 3 (depends on 1) The method of claim 1, wherein generating the source code for the original query execution plan further comprises: generating source code for a child operator to produce a tuple for a parent of the child operator from the tree of operators; and generating source code for the parent operator to consume the produced tuple of the child operator from the tree of operators. ### Claim 4 (depends on 1) The method of claim 1, wherein the single traversal of the tree of operators further comprises: traversing the tree of operators from leaf nodes of the tree of operators to the root node of the tree of operators. ### Claim 5 (depends on 1) The method of claim 1 further comprising: initializing a SNAP code generator by generating a vector structure that includes a plurality of function blocks each representing a corresponding operator from the tree of operators, wherein each function block includes one or more basic block each representing a function of the corresponding operator. ### Claim 6 (depends on 1) The method of claim 1, wherein execution flow of the original query execution plan is consumer driven and execution flow of the SNAP is transformed to be producer driven. ### Claim 7 (depends on 1) The method of claim 1, wherein compiling the generated source code into the SNAP is performed by a low level virtual machine (LLVM) compilation framework. ### Claim 8 A computer system configured to generate a simplified native access plan from an original query execution plan (SNAP), the computer system including: a memory to store computer executable instructions; at least one computer processor coupled to the memory to execute the instructions, to perform operations comprising: receiving an original query execution plan of a database query of a database system, wherein the original query execution plan represents a tree of operators; determining whether the database system is configured to permit processing of the SNAP; wherein in response to determining that the database system is configured to permit the processing of the SNAP, at runtime, generating source code for the original query execution plan by a single traversal of the tree of operators; during generating the source code, converting a nested loop join in the original query execution plan from an iterator-based model to a single function consisting of a doubled loop; including in the doubled loop a function to send a respective row to a client process after the doubled loop generates each respective row; the single traversal traversing the tree of operators beginning at a root node and generating the source code from a bottom of the tree of operators upward; and at runtime, compiling the generated source code into native machine code, wherein the native machine code represents the SNAP. ### Claim 9 (depends on 8) The computer of claim 8, wherein the operations further comprise: storing the SNAP for subsequent execution of the database query, wherein upon receiving a subsequent request to execute the database query, the SNAP is invoked to produce a result for the database query. ### Claim 10 (depends on 8) The computer of claim 8, wherein the operations further comprise: generating source code for a child operator to produce a tuple for a parent of the child operator from the tree of operators; and generating source code for the parent operator to consume the produced tuple of the child operator from the tree of operators. ### Claim 11 (depends on 8) The computer system of claim 8 wherein the operations further comprise: traversing the tree of operators from leaf nodes of the tree of operators to the root node of the tree of operators. ### Claim 12 (depends on 8) The computer system of claim 8, wherein the operations further comprise: initializing a SNAP code generator by generating a vector structure that includes a plurality of function blocks each representing a corresponding operator from the tree of operators, wherein each function block includes one or more basic block each representing a function of the corresponding operator. ### Claim 13 (depends on 8) The computer system of claim 8, wherein the first component configured to be run in a first runtime and the second component configured to be run in a second runtime separate from the first runtime. ### Claim 14 (depends on 8) The computer system of claim 8, wherein execution flow of the original query execution plan is consumer driven and execution flow of the SNAP is transformed to be producer driven. ### Claim 15 A non-transitory computer readable medium storing instructions thereon, which when executed by a processor cause a computer system to: receive an original query execution plan of a database query of a database system, wherein the original query execution plan represents a tree of operators; determine whether the database system is configured to permit processing of a simplified native access plan (SNAP); wherein in response to determining that the database system is configured to permit the processing of the SNAP, at runtime, generate source code for the original query execution plan by a single traversal of the tree of operators; during generating the source code, convert a nested loop join in the original query execution plan from an iterator-based model to a single function consisting of a doubled loop; including in the doubled loop a function to send a respective row to a client process after the doubled loop generates each respective row; the single traversal traversing the tree of operators beginning at a root node and generating the source code from a bottom of the tree of operators upward; and at runtime, compile the generated source code into native machine code, the native machine code represents a SNAP. ### Claim 16 (depends on 15) The computer readable medium of claim 15, wherein the instructions when executed by the processor cause the computer system further to: storing the SNAP for subsequent execution of the database query, wherein upon receiving a subsequent request to execute the database query, the SNAP is invoked to produce a result for the database query. ### Claim 17 (depends on 15) The computer readable medium of claim 15, wherein the instructions when executed by the processor cause the computer system further to: generating source code for a child operator to produce a tuple for a parent of the child operator from the tree of operators; and generating source code for the parent operator to consume the produced tuple of the child operator from the tree of operators. ### Claim 18 (depends on 15) The computer readable medium of claim 15, wherein the instructions when executed by the processor cause the computer system further to: traversing the tree of operators from leaf nodes of the tree of operators to the root node of the tree of operators. ### Claim 19 (depends on 15) The computer readable medium of claim 15, wherein the instructions when executed by the processor cause the computer system further to: initializing a SNAP code generator by generating a vector structure that includes a plurality of function blocks each representing a corresponding operator from the tree of operators, wherein each function block includes one or more basic block each representing a function of the corresponding operator. ### Claim 20 (depends on 15) The computer readable medium of claim 15, wherein execution flow of the original query execution plan is consumer driven and execution flow of the SNAP is transformed to be producer driven.