Patent Description:
Instead of the traditional columns and rows of a relational database table, graph databases store data in form of nodes and edges. A node represents a distinct data value or set of related values, and edges connect the nodes and thereby represent relationships therebetween. Edges may likewise have one or more related values (e.g., a duration of the relationship. For example, data related to company employees may be represented by a node for each employee, and edges may connect employees that work with one another thereby representing the relationships of co-workers. In another example, an edge connecting a buyer and product may represent a product purchase, and may have attributes such as sale price, quantity, date, etc. A complete picture of all the nodes with all interconnecting edges is referred to as a graph.

Storing information in the form of a graph (as opposed to a native relational database table) and performing graph queries can be desirable under certain circumstances. For example, graph storage can be desirable where a business application or its underlying data involve complex many-to-many relationships, or anytime there is a need to analyze the relationships that underlie the data (i.e., where the relationships between data points matter as much or more than the data points themselves). In these situations, graph storage and query capabilities can be useful since a graph database system typically allows one to more easily express certain types of queries. For example, pattern matching, multi-hop navigation, transitive closure and polymorphic queries are typically easier to express with a graph query.

Increasingly, relational database systems are being leveraged to perform the functions of a graph database system. In particular, the nodes and edges that comprise a graph may be stored in ordinary relational tables referred to as node and edge tables. Node tables store information or references relevant to a particular node (e.g., employee), and an edge table reflects the relationship (e.g., co-worker) between nodes in the node table. Such use of a relational database system can, however, uncover certain problems.

For example, executing a shortest path graph query on a relational database requires recursively joining multiple tables repeatedly, where each sequence of joins represents one path expansion. Relational database systems are often not natively capable of performing such a query. To perform such a query, a user may be forced to custom craft a query using conditional branching and temporary storage that can come with significant performance problems. Likewise, writing such conditional logic is error prone and requires new code for each new query. Alternatively, recursive common table expressions ("CTEs") may be employed to handle at least the recursive portions of a custom query, though these suffer from performance issues. Moreover, the recursive member of a CTE will typically recurse until no rows are returned meaning early termination may be difficult. <CIT> describes techniques to generate and to execute a query execution plan using static data buffering. After receiving a query with a clause that requires multiple iterations to execute, a database management system (DBMS) generates a plurality of plans that vary the order in which the database operations are executed. Within each plan, the DBMS identifies sets of rows within that plan that contain static data during execution of the query. Then, an additional step is added to each plan that includes loading the static set of rows in a database buffer cache. One or more database operations, from an iteration other than the first iteration, may be performed against the cached static set of rows. For each plan generated in this manner, a cost analysis model is applied, and the plan with the lowest estimated computational cost is selected for use as the query execution plan.

It is the object of the present invention to provide enhanced query processing.

Methods, systems, and computer-readable memory devices are provided that address issues related to efficient execution of graph queries, and other types of queries, in a relational database system by providing a multi-step sequence query plan operator. In one aspect, a database application is configured to accept and process a query to generate a query plan including a multi-step sequence, wherein the multi-step sequence includes at least an initial step configured to execute and pass execution control to another step, at least an intermediate step configured to execute and pass execution control to another step, and a final step configured to execute to provide a sub-query result based on the execution results of the aforementioned steps of the multi-step sequence. In an aspect, the sub-query result forms at least a partial basis of the results of the received query. The intermediate step may comprise a recursive step configured to generate recursive step results and pass such results back to itself via recursion unless or until an early termination condition is satisfied.

In an aspect, the relational database application may further generate one or more additional multi-step sequences for the query plan, and determine which multi-step sequence to execute. The relational database application may determine which multi-step sequence to execute based at least in part on: a step result of another step of the query plan, an intermediate query result of any other multi-step sequence in the query plan, and/or the inclusion of an optional parameter included in the query.

In another aspect, a multi-step sequence of a query plan may include steps configured to communicate arbitrary data to one or more other execution steps in the same, or a different, multi-step sequence of the query plan. A multi-step sequence in a query plan may also include multiple sub-plans that when executed, each generate respective sub-plan results, and wherein a sub-plan result for a first sub-plan may be incorporated into another sub-plan, and at least in part form the basis of the sub-plan result of that sub-plan. Furthermore, the sub-plan result for the first sub-plan may be re-used by other sub-plans or steps without requiring re-execution of the first sub-plan.

Further features and advantages of embodiments, as well as the structure and operation of various embodiments, are described in detail below with reference to the accompanying drawings. It is noted that the embodiments are not limited to the specific embodiments described herein. Such embodiments are presented herein for illustrative purposes only. Additional embodiments will be apparent to persons skilled in the relevant art(s) based on the teachings contained herein.

The present specification and accompanying drawings disclose one or more embodiments that incorporate the features of the disclosed embodiments. The scope of the embodiments is not limited only to the aspects disclosed herein. The disclosed embodiments merely exemplify the intended scope, and modified versions of the disclosed embodiments are also encompassed. Embodiments are defined by the claims appended hereto.

Embodiments will now be generally described with respect to performing a type of graph query against graph data stored as node and edge tables in a relational database. In particular, embodiments will be described in terms of generating a query plan to perform recursive shortest path traversal of graph. It should be understood, however, that embodiments are not limited to performing graph queries or recursive queries as will be discussed in more detail below. Embodiments are now described with reference to <FIG>.

<FIG> shows an example graph <NUM> reflecting co-worker relationships (edges) between workers (nodes). Graph <NUM> of <FIG> includes nodes N1-N4 enumerated with reference numerals <NUM>-<NUM>, respectively. Graph <NUM> also includes edge1-edged enumerated with reference numerals <NUM>-<NUM>, respectively. As described briefly above, nodes N1 <NUM> through N4 <NUM> represent workers at a company. Edge1 <NUM> through edge4 <NUM>, on the other hand, represent relationships between the workers. In this example, edges represent a "working with" relationship. That is, nodes connected by edges are workers that have a co-worker relationship (i.e., they work with one another). Graph <NUM> of <FIG> is merely a conceptual visualization tool. Data that embodies graph <NUM> must be stored differently than what is illustrated in graph <NUM> of <FIG>.

For example, <FIG> illustrates an example relational database node table <NUM> that describes properties associated with the nodes shown in the graph of <FIG>. Node table <NUM> is stored in a relational database as a table, and in this example is named "Employees. " Node table <NUM> includes three columns that store information related to each node. In particular, each row of node table <NUM> includes a NodeID, Employee Name and Role. The EmployeeName for at each node simply reflects the name of that employee. In graph <NUM> of <FIG>, the EmployeeName included in each node (i.e., row of the table) is merely shorthand. In an actual graph that reflects actual production data, one may expect to see the actual names of people.

Each node of node table <NUM> also includes a Role for that particular employee. For example, the employees illustrated by nodes in graph <NUM>, and embodied in node table <NUM>, may be an Architect as shown at node N1 <NUM> or N3 <NUM>, a receptionist as shown at node N2 <NUM>, or a PM (i.e., "Program Manager") as shown at node N4 <NUM>. Each node included in node table <NUM> also includes a NodeID that uniquely identifies each node and, as described below, also serves to identify the nodes connected by the edges of edge table <NUM> of <FIG>.

Edge table <NUM> of <FIG> may likewise be stored in the relational database along with node table <NUM>. In this example, edge table <NUM> is named "WorkingWith. " Edge table <NUM> includes three columns to define each edge. The columns are: Edge ID, FromNode and ToNode. Each row corresponds to an edge of graph <NUM>. The edgeID in each row uniquely identifies each edge. The FromNode of each row includes the NodeID of one of the nodes connected by that edge, and the ToNode includes the NodeID of the other node connected by the edge. Note, in this example, the node table reflects a "to" and "from" relationship (i.e. a directed graph). It should be understood, however, that embodiments are enabled to function with any type of graph, directed or otherwise.

Taking node table <NUM> and edge table <NUM> together, and with reference to <FIG>, one can see that these tables reflect the nodes of graph <NUM>, and the edges serving to interconnect such nodes. In embodiments, after node table <NUM> and edge table <NUM> have been created and persisted to the relational database system, a user may seek to execute graph queries against the data.

For example, <FIG> shows an example graph query <NUM> that may be submitted to, and processed by, example embodiments. <FIG> is described as follows with respect to <FIG> shows a table <NUM> illustrating possible traversal paths through the nodes of graph of <FIG> according to various constraints. The discussion immediately below of <FIG> serve to generally describe query <NUM> and the type of data such a query may return, in embodiments. Details of other embodiments describing processing of query <NUM> to generate a physical query plan will be discussed in greater detail further below.

Query <NUM> of <FIG> is an example Transact-SQL ("T-SQL") graph query, according to an embodiment. Query <NUM> comprises one statement including three clauses: SELECT clause <NUM>, FROM clause <NUM> and WHERE clause <NUM>. Query <NUM> operates as an implicit JOIN of the Employees table, the WorkingWith table, and again the Employees table, with the results filtered by WHERE clause <NUM>. Note, since the query is computing a recursive result, embodiments must take FROM clause <NUM> and WHERE clause <NUM> (including the recursive MATCH predicate <NUM> discussed below) together to compute the results rather than strictly computing a cartesian product.

WHERE clause <NUM> includes <NUM> conditions or predicates <NUM>, <NUM>, and <NUM>. Predicate <NUM> specifies a recursive MATCH condition that will include only the shortest path between starting node n1 and ending node n2, wherein nodes n1 and n2 satisfy predicates <NUM> and <NUM>, respectively. Predicate <NUM> requires that the Role of each matching start node be equal to 'Architect. ' Similarly, Predicate <NUM> requires that the Role of each matching ending node be equal to 'PM. ' The query result of query <NUM> is then generated by applying the conditions of WHERE clause <NUM> to the results of SELECT statement <NUM>. In particular, the query result will return the shortest path between every Architect and every Program Manager as shown in graph <NUM> of <FIG>, and as embodied by node table <NUM> and edge table <NUM>.

The query result of query <NUM> may be better understood by considering <FIG>. Table <NUM> of <FIG> illustrates the possible traversals paths through the nodes of graph <NUM> of <FIG> according to various constraints. Table <NUM> includes three columns including: all paths <NUM>, all paths between Architects and Program Managers <NUM> and shortest path between all Architects and Program Managers <NUM>. The paths illustrated in table <NUM> of <FIG> assume that no node can be traversed more than once. It should be understood, however, that no particular traversal restrictions or rules are required nor assumed. For instance, one could create a similar table of traversals assuming that no edge may be traversed more than once, or where loops/cycles are allowed up to some maximum path length.

The first column of table <NUM> illustrates all possible traversal paths through graph <NUM> from each node to all other nodes through all paths. For example, consider the upper left quadrant of column <NUM>, with reference to graph <NUM> of <FIG>, in which <NUM> paths are illustrated starting at node N1 <NUM> of graph <NUM>, and ending at each of the other nodes N2-N4. In particular, paths include: N1 to N2, N1 to N2 to N3, N1 to N2 to N3 to N4, N1 to N2 to N4, and N1 to N2 to N4 to N3. It can be shown that this is an exhaustive list of possible traversal paths from N1 to the other nodes N2-N4 (and where cycles or loops where a node is traversed more than once are not permitted in any path). The paths from N2, N3 and N4 to all of the other nodes are illustrated in the upper-right, lower-left and lower-right quadrants, respectively, of the column <NUM> of table <NUM>. This exhaustive list of traversal paths is provided only for the sake of context and completeness since, for example, the traversal of graph <NUM> required to evaluate query <NUM> would typically not start on any nodes other than architects (i.e., N1 and N3). In embodiments, however, bidirectional traversal may be performed whereby graph <NUM> is traversed in both directions starting with both architects and Program Managers (but no other nodes), and working until the traversals meet in the middle.

Now consider column <NUM> of table <NUM>, wherein constraints are placed on traversal paths. In particular, column <NUM> illustrates traversal paths of graph <NUM> of <FIG> where start nodes are restricted to Architects, and end nodes are restricted to Program Managers. As shown in node table <NUM> of <FIG>, only one employee has the Role of PM corresponding to node N4 <NUM>. Accordingly, all paths in column <NUM> must end on N4. Similarly, only N1 and N3 of graph <NUM> correspond to employees with the Role of Architect, which then requires that the paths of column <NUM> must always start on either nodes N1 or N3. As is apparent, the paths of column <NUM> are an exhaustive list of such paths.

Finally, consider column <NUM> of table <NUM> wherein an additional constraint is imposed on otherwise valid traversal paths shown in column <NUM>. In particular, the paths shown in column <NUM> satisfy not only the conditions required to produce the paths in column <NUM>, but also constitute the shortest paths (as measured by the number of hops since the edges in this case all have equal weights) between all architects and all program managers. Thus, there is only one path between N1 and N4, and between N3 and N4, and these paths are the shortest paths between the respective endpoints. The paths shown in column <NUM> are based on the rows returned by query <NUM> of <FIG>.

Although it may be noted that the ordering of the paths as shown in table <NUM> of <FIG> implies a depth-first traversal of graph <NUM>, it should be understood that embodiments are not restricted to any particular traversal algorithm. Indeed, as understood in the art, the algorithm employed to perform traversal may vary depending on the type of graph (e.g. weighted edges, negative edge weights) and/or particular type of shortest path problem being solved. In embodiments, shortest path algorithms may include Dijkstra's, Bellman-Ford, A* search, Floyd-Warshall, Johnson's, Vitterbi, and other algorithms as known in the art. Embodiments may implement recursive versions of one or more of these algorithms to perform the shortest path traversal necessary to perform query <NUM>, and may do so in various ways. For instance, <FIG> shows an example multi-step sequence <NUM> that may be included in a physical query plan for performing graph queries, and other types of queries, according to an example embodiment. Other structural and operational embodiments will be apparent to persons skilled in the relevant art(s) based on the following discussion regarding multi-step sequence <NUM>.

In an embodiment, multi-step sequence <NUM> is a type of logical and physical sequence operator that is included in a query plan. Multi-step sequence <NUM> as depicted in <FIG> includes an initial step <NUM>, an intermediate step <NUM>, and a final step <NUM>. Although multi-step sequence <NUM> is depicted in <FIG> as having three steps, such a configuration is illustrated as a typical example, and other embodiments of a multi-step sequence may include greater numbers of execution steps. Moreover, a multi-step sequence may include more than one final step, with the particular final step to execute being left as a runtime decision. Each of step <NUM> and <NUM> is configured to pass execution control to one or more other steps of multi-step sequence <NUM> via one or more execution paths <NUM>-<NUM>. Final step <NUM> is configured to pass execution control and query sub-result <NUM> back to a query execution component such as multi-step query plan executor <NUM> of query execution engine <NUM> as depicted in <FIG>, and as will be discussed in greater detail herein below. Embodiments of multi-step sequence <NUM>, including functional aspects enabled by multi-step sequence <NUM>, will now generally be described. Such embodiments will be described in terms of steps <NUM>, <NUM> and <NUM>. It should be understood, however, that embodiments of multi-step sequence <NUM> are not limited to multi-step sequences containing only these particular steps or types of steps. Embodiments are now described with reference to <FIG>.

In embodiments, multi-step sequence <NUM> of <FIG> may be understood by regarding instances of multi-step sequence <NUM> as an ordinary sequence operator, but with relaxed execution constraints and expanded inter-step communication capabilities. An ordinary sequence operator typically drives wide update plans, and executes each child of the sequence in a purely sequential order, first to last. Each child of such a sequence typically updates a different object, and returns only those rows generated by the last child of the sequence.

A multi-step sequence such as multi-step sequence <NUM>, on the other hand, is a more flexible sequence operator with a number of different capabilities. For example, embodiments of multi-step sequence <NUM>, when included in an executable physical query plan, may enable one or more of the following capabilities depending on the particulars of the generated multi-step sequence:.

In an embodiment, initial step <NUM>, intermediate step <NUM> and final step <NUM> of multi-step sequence <NUM> may each comprise a single physical or logical SQL query operator. In other embodiments, however, steps of multi-step sequence <NUM> may comprise one or more physical or logical SQL query operators. In an embodiment, physical operators may include any type of physical operator, such as for example, hash match, table insert, merge join, nested loops, index insert, non-clustered index update, parallelism, sort, split, stream aggregate, table scan and other types of SQL physical operators as may be known in the art. In embodiments, logical query operators may include, for example, branch and segment repartition, various join operators, distinct and distinct sort, partial aggregate, union and other types of SQL logical operators as known in the art.

When a query plan that includes an instance of multi-step sequence <NUM> is executed, initial step <NUM> of multi-step sequence <NUM> is the first step of the multi-step sequence to be executed. In an embodiment, initial step <NUM> is configured to execute to generate initial step results, and then pass execution control to a different step. Depending on the step results generated by initial step <NUM>, execution control passes to any other step including intermediate step <NUM> by passing execution control via execution path <NUM>. Alternatively, initial step <NUM> may pass execution control to any other steps that may be included in multi-step sequence <NUM> and as represented by the sets of vertical ellipses depicted in <FIG> (execution paths not shown). For the purposes of describing embodiments of multi-step sequence <NUM>, we herein assume that initial step <NUM> passes execution control to intermediate step <NUM> via execution path <NUM>.

In embodiments, intermediate step <NUM> of multi-step sequence <NUM> in <FIG> is configured to receive execution control from a previously executed step of multi-step sequence <NUM>. After receiving execution control, embodiments that include intermediate step <NUM> may be configured to execute to generate intermediate step results, and thereafter pass execution control to any other step in multi-step sequence <NUM>, including intermediate step <NUM> itself. Embodiments may include a number of useful features that are enabled by permitting multi-step sequence steps such as intermediate step <NUM> to execute itself. For example, recursive queries such a recursive shortest path graph queries, as discussed above, may be implemented in a simple manner without requiring the user to custom craft recursive queries or recursive CTEs, and also thereby avoid the performance problems associated with those solutions, in embodiments. Additionally, by permitting intermediate step <NUM> (as well as other instances of intermediate steps like intermediate step <NUM>) to pass execution control to any other step in multi-step sequence <NUM>, multi-step sequence <NUM> is enabled in embodiments to execute steps in arbitrary order, to execute alternative sub-plans according to actual step results determined at runtime, to adapt to the memory or performance needs of the query depending on cardinality estimates computed at run time, and to enable other features as discussed above.

After executing to generate intermediate step results, intermediate step <NUM> may pass execution control to any other step of multi-step sequence <NUM>. Intermediate step <NUM> may run only a single time to generate intermediate step results, and thereafter pass execution control to another step. Likewise, even where intermediate step <NUM> is being executed recursively (i.e., by repeatedly executing itself to operate on results generated by the previous iteration), typically a termination condition or recursion depth limit will eventually be reached, and intermediate step <NUM> will pass execution control to some other step. Note, in other embodiments, a step could execute repeatedly without terminating (i.e. an infinite loop). For the purposes of describing embodiments of multi-step sequence <NUM>, we herein assume that intermediate step <NUM> passes execution control to final step <NUM> via execution path <NUM>.

In embodiments, final step <NUM> of multi-step sequence <NUM> in <FIG> is configured to receive execution control from any previously executed step of multi-step sequence <NUM>, including from intermediate step <NUM> via execution path <NUM>. Final step <NUM> of multi-step sequence <NUM> is configured to be the final execution step in multi-step sequence <NUM>. In embodiments, final step <NUM> is configured to generate query sub-result <NUM> comprising the results for the entire execution of multi-step sequence <NUM>. In embodiments, query sub-result <NUM> may be based in part on any prior step results generated by steps of multi-step sequence <NUM>. After receiving execution control and generating query sub-result <NUM>, embodiments of multi-step sequence <NUM> are enabled to pass query sub-result <NUM> and execution control to any other query operator, step, step sequence or multi-step sequence, or back to query execution engine (e.g., multi-step query plan executor <NUM> of query execution engine <NUM> of <FIG>, as will be discussed in further detail below). Embodiments may generate and incorporate instances of multi-step sequence <NUM> in a query plan for performing query <NUM>, and may do so in various ways.

For instance, <FIG> shows a block diagram of an example relational database system <NUM> that includes a multi-step query plan generator <NUM> configured to generate a query including a multi-step sequence <NUM>, according to an example embodiment. Other structural and operational embodiments will be apparent to persons skilled in the relevant art(s) based on the following discussion regarding relational database system <NUM>.

Relational database system <NUM> includes query pre-processor <NUM>, query optimizer <NUM>, query execution engine <NUM> and relational data store(s) <NUM>. Query optimizer <NUM> includes multi-step query plan generator <NUM>. Query execution engine <NUM> includes multi-step query plan executor <NUM>. Query pre-processor <NUM> is coupled to query generating entity <NUM>. These features of relational database system <NUM> are described as follows.

In embodiments, query pre-processor <NUM> of relational database system <NUM> as shown in <FIG> is configured to accept query <NUM> from query generating entity <NUM>. Relational database system <NUM> is described as follows for illustrative purposes with respect to a received query being query <NUM> of <FIG>, but other queries may be received and processed by system <NUM> in embodiments. Query generating entity <NUM> may provide query <NUM> local to relational database system <NUM> (e.g., from a terminal or Microsoft SQL Server Management Studio), or remotely via a network such as, for example, the Internet. A network may, however, comprise one or more networks such as local area networks (LANs), wide area networks (WANs), enterprise networks, and may include one or more of wired and/or wireless portions. Examples of computing devices that may be used to provide queries to relational database system <NUM> include, for example and without limitation, desktop computers, laptop computers, tablet computers, netbooks, smartphones, wearable computing devices, etc..

Although relational database system <NUM> is depicted as a monolithic component, relational database system <NUM> may be implemented as any number of computing devices including servers, and may include any type and number of other resources, including resources that facilitate communications with and between computing devices connected via networks as described above. In embodiments, servers implementing relational database system <NUM> may be organized in any manner, including being grouped in server racks (e.g., <NUM>-<NUM> servers per rack, referred to as nodes or "blade servers"), server clusters (e.g., <NUM>-<NUM> servers, <NUM>-<NUM> racks, etc.), or datacenters (e.g., thousands of servers, hundreds of racks, dozens of clusters, etc.). In an embodiment, servers that comprise relational database system <NUM> may be co-located (e.g., housed in one or more nearby buildings with associated components such as backup power supplies, redundant data communications, environmental controls, etc.) to form a datacenter, or may be arranged in other manners. Accordingly, in an embodiment, relational database system <NUM> may comprise a datacenter in a distributed collection of datacenters.

As shown in <FIG>, query pre-processor <NUM> is configured to receive query <NUM> submitted by query-generating entity <NUM> and to perform certain operations thereon to generate a representation of the query that is suitable for further processing by query optimizer <NUM>. Such operations may include, but are not limited to, parser and algebrizer operations performed by parser and algebrizer components (not shown for ease of illustration). In an embodiment, query pre-processor <NUM> outputs query processor tree <NUM> that is a logical representation of query <NUM>. In an embodiment, query processor tree <NUM> may be obtained by translating the original text of query <NUM> into a tree structure with leaf nodes representing table accesses and internal nodes representing relational operators such as relational join. Query optimizer <NUM> is configured to receive query processor tree <NUM> output by query pre-processor <NUM>, and to process query processor tree <NUM> to generate query plan <NUM> for the query. Embodiments of relational database system <NUM>, and multi-step query plan generator <NUM> of query optimizer <NUM> in particular, will now generally be described. Such embodiments will be described in terms of processing query <NUM> of <FIG> to generate query plan <NUM> including an instance of multi-step sequence <NUM> of <FIG> for performing query <NUM>. It should be understood, however, that embodiments of relational database system <NUM> are not strictly limited to multi-step sequences as illustrated in <FIG>. Embodiments are now described with reference to <FIG> and <FIG>.

For convenience, query <NUM> is reproduced herein below:
<IMG>.

Generating query plan <NUM> to perform query <NUM> begins in query pre-processor <NUM>, wherein the text of T-SQL query <NUM> is parsed to determine, in part, whether query <NUM> includes a repeated MATCH expression. For example, query <NUM> includes a repeated MATCH expression as follows: <MAT> In embodiments, when the parser encounters the repeated MATCH expression in the query, the query is marked to indicate a recursive multi-step sequence should be used to generate query plan <NUM>.

When an incoming query requires a recursive multi-step sequence, such as with query <NUM>, query pre-processor <NUM> of relational database system <NUM> is configured to perform the initial transformations of query <NUM> into the query sections necessary to generate the recursive multi-step sequence incorporated into query plan <NUM>, in one embodiment. In particular, each repeated MATCH expression must be mapped onto an anchor member, a recursive member, and the outer SELECT query that expressly references the recursive member in a manner analogous to a recursive CTE.

Embodiments of query pre-processor <NUM> may also be configured to expand a repeated MATCH expression in both the left-to-right and right-to-left directions where embodiments allow queries to execute repeated MATCH expressions in either direction, e.g.: <MAT> In embodiments, the abovementioned transformations and expansions may be performed by query pre-processor <NUM> of relational database system <NUM> in part to produce query processor tree <NUM> as provided to query optimizer <NUM>. Embodiments of query optimizer <NUM> may be configured to generate query plan <NUM> using multi-step query plan generator <NUM> when query optimizer <NUM> determines that query plan <NUM> ought to include an instance of multi-step sequence <NUM>. For example, and as discussed above, parser functionality of query pre-processor <NUM> may include a flag in query processor tree <NUM> as provided to query optimizer <NUM>, and that indicates particular processing is required for evaluating query <NUM>. Query optimizer <NUM> may thereafter detect the flag in query processor tree <NUM>, and direct multi-step query plan generator <NUM> to create a recursive multi-step sequence for inclusion in query plan <NUM>, in an embodiment.

As discussed above, embodiments of query pre-processor <NUM> may be configured to perform the initial transformations of, for example, query <NUM> to expand the repeated MATCH section of query <NUM> into at least an anchor member, recursive member and outer select query. For example, consider <FIG> shows a query <NUM> including a repeated MATCH expression, and a conceptual effective query generated by transformation of the query, according to an embodiment. Query <NUM> of <FIG> is reproduced for convenience herein below:
<IMG>.

Effective query <NUM> of <FIG> shows a conceptual expansion of query <NUM> and its repeated match predicate (i.e., "match(shortest_path(n1(-(e1)->n2-(e2)->n3)+)) into an equivalent anchor member <NUM>, recursive member <NUM> and outer select query <NUM>. It should be understood that effective query <NUM> represents a non-physical, conceptual transformation, and does not represent the query from which query plan <NUM> is generated.

In embodiments, relational database system <NUM> of <FIG> may use query pre-processor, query optimizer <NUM>, multi-step query plan generator <NUM>, query execution engine <NUM>, and multi-step query plan executor <NUM> in various ways to generate a query plan that includes a multi-step sequence, and such sequences may likewise comprise various logical and physical plan operators, as discussed above. For instance, <FIG> shows a portion of the SHOWPLAN output <NUM> of a query plan that includes a multi-step sequence <NUM>, as generated for an example graph query by an embodiment. Multi-step sequence <NUM> as shown in SHOWPLAN output <NUM> is excerpted from a physical query plan generated by an embodiment of relational database system <NUM>, and comprises various logical and physical plan operators. SHOWPLAN output <NUM> of <FIG> is now described with reference to query <NUM> of <FIG>, and multi-step sequence <NUM> of <FIG>.

Graph query <NUM> is virtually identical to query <NUM> of <FIG>, except that graph query <NUM> includes FOR PATH expressions. In an embodiment, the FOR PATH option operates to mark the associated alias for later validation. In particular, any alias proceeded by the FOR PATH option must be used in a repeated MATCH expression in the query. Accordingly, the respective query plans created for these queries will be the same, and all discussion of query <NUM> herein applies equally to graph query <NUM> of <FIG>, and all further discussion of SHOWPLAN output <NUM> with instead reference query <NUM> and <FIG>.

Multi-step sequence <NUM> is one example of multi-step sequence <NUM> of <FIG> as discussed in detail above. In SHOWPLAN output <NUM>, multi-step sequence <NUM> is represented by Sequence SHOWPLAN operator <NUM>. As discussed above, a multi-step sequence may be regarded as a special type of sequence, and although sequence SHOWPLAN operator <NUM> is labeled "Sequence", it nevertheless operates as a multi-step sequence as detailed in more detail below.

As detailed above, and shown in <FIG>, embodiments of a multi-step sequence include at least an initial step, an intermediate step, and a final step. Multi-step sequence <NUM> includes five steps: predicate step <NUM>, predicate step <NUM>, recursion setup step <NUM>, recursive step <NUM> and final step <NUM>. In multi-step sequence <NUM>, predicate step <NUM> serves as the first step. Each of predicate step <NUM>, recursion setup step <NUM> and recursive step <NUM> is an intermediate step. Final step <NUM> comprises the final step of multi-step sequence <NUM>. Each of these steps will be discussed with reference to <FIG> and query <NUM> as reproduced herein below for convenience:
<IMG>.

Predicate step <NUM> and predicate step <NUM> of <FIG> perform query operations related to predicate <NUM> and predicate <NUM>, respectively. Predicate step <NUM> finds all the start nodes for the shortest path traversal of graph <NUM>. More specifically, predicate step <NUM> finds all rows in the Employee table where 'Role' equals 'Architect', and stores those rows in a temporary table. Similarly, predicate step <NUM> finds all the ending nodes for the shortest path traversal graph <NUM>. More specifically, predicate step <NUM> finds all rows in the Employee table where 'Role' equals 'PM', and stores those rows in a temporary table. Although predicate step <NUM> is the first step of multi-step sequence <NUM>, predicate step <NUM> could just as easily serve as the initial step since these operations are independent of one another. Likewise, and for the same reason, predicate step <NUM> and predicate step <NUM> could execute simultaneously, in embodiments. In any event, which ever of predicate step <NUM> and predicate step <NUM> executes second, that step would be regarded as an intermediate step.

Recursion setup step <NUM> is likewise an intermediate step. Recursion setup step <NUM> is the start of the path traversal. Recursion setup step <NUM> finds all of the nodes one hop away from each of starting nodes. More specifically, recursion setup step <NUM> retrieves the results stored in the temporary table by predicate step <NUM>, determines which rows are one hop away from each of those nodes, and stores those results in a temporary table. Referring to graph <NUM> of <FIG>, and node table <NUM> of <FIG>, it can be seen that nodes N1 and N3 are the start nodes as determined by predicate step <NUM>, and recursion setup step <NUM> will determine that node N2 as the only node one hop away from node N1 and nodes N2 and N4 as the nodes one hop away from N3. After recursion setup step <NUM> stores these results in the temporary table, and execution control is passed to a recursive step <NUM>.

Recursive step <NUM> is configured to recursively traverse the nodes of graph <NUM>, to determine the shortest paths between every architect and every PM. More specifically, recursive step <NUM> starts with the results of recursion setup step <NUM> (i.e., the nodes that are one hop away from the start nodes), and determines the nodes that are one hop away from those nodes, and proceeds by executing recursive step <NUM> recursively to find all the nodes at the next level, until no more nodes are found. Alternatively, and when traversing in a breadth first manner, it is possible to terminate recursion when a path is discovered and/or where all possible results have been found. During each iteration of recursive step <NUM>, the nodes found are stored in a temporary table, and at the end of the recursion, the temporary table will contain the entire result set.

Final step <NUM> retrieves the result set from the temporary table used by recursive step <NUM>, and bubbles those results up through the remainder of the query plan (not shown).

In embodiments, relational database system <NUM> of <FIG> may be used in various ways to execute graph queries or other types of queries using a multi-step sequence. For instance, <FIG> shows a flowchart <NUM> of a method for processing a query to generate and execute a physical query plan that includes a first multi-step sequence, according to an example embodiment of relational database system <NUM>. Flowchart <NUM> is described with continued reference to <FIG>. However, other structural and operational embodiments will be apparent to persons skilled in the relevant art(s) based on the following discussion regarding flowchart <NUM> and relational database system <NUM> of <FIG>.

Flowchart <NUM> begins with step <NUM>. In step <NUM>, a query is received in a database application. For example, in relational database system <NUM> of <FIG>, query pre-processor <NUM> receives query <NUM> from query generating entity <NUM>. As described above, query <NUM> may comprise, for example, a T-SQL query.

In step <NUM>, the query is processed to generate a query plan comprising at least a first set of execution steps configured to be executed to generate first query sub result, and wherein the first set of execution steps comprises a number of other steps as follows:.

For example, in relational database system <NUM> of <FIG>, query preprocessor <NUM> may be configured to pre-process query <NUM> to generate query processor tree <NUM>, which is received by query optimizer <NUM>. Query optimizer <NUM>, in conjunction with multi-step query plan generator <NUM>, is configured to generate query plan <NUM> that includes an instance of multi-step sequence <NUM>, all of which is described in detail above.

Flowchart <NUM> continues at step <NUM>. At step <NUM>, the query plan is executed to generate a final query result based at least in part on the first query sub-result by passing execution control to the initial step of the set of execution steps of the query plan. For example, and as discussed above, query optimizer <NUM> of relational database system <NUM> is configured to pass query plan <NUM> to query execution engine <NUM>. Query plan <NUM> includes an instance of multi-step sequence <NUM>. For example, query plan <NUM> could include a multi-step sequence similar to multi-step sequence <NUM> of <FIG>. In an embodiment, multi-step query plan executor <NUM> of query execution engine <NUM> may be configured to execute the query plan <NUM> by passing execution control to the first step in the query plan. The first step in the query plan may comprise, for example, initial step <NUM> of multi-step sequence <NUM> as shown in <FIG>. Where, for example, multi-step sequence <NUM> operates like multi-step sequence <NUM> of <FIG>, multi-step query plan executor <NUM> of query execution engine <NUM> would pass execution control to predicate step <NUM> of multi-step sequence <NUM> which serves as the initial step discussed above at step <NUM>.

Multi-step sequence <NUM> is executed to determine the starting nodes of graph traversal required to compute graph query <NUM>, as discussed above in some detail. Such starting nodes are stored in a temporary table and comprise the first step results discussed above in relation to step <NUM>. After executing predicate step <NUM> of multi-step sequence <NUM>, multi-step query plan executor <NUM> of query execution engine <NUM> is configured to pass execution control to an intermediate step as discussed above in relation to step <NUM>.

For example, multi-step query plan executor <NUM> of query execution engine <NUM> may pass execution control to predicate step <NUM> of multi-step sequence <NUM>. After execution of predicate step <NUM> completes, multi-step query plan executor <NUM> of query execution engine <NUM> may and pass execution control to the next step of multi-step sequence <NUM>, in this case, recursive setup step <NUM>. Once execution of recursive setup step <NUM> has completed, execution control may be passed to recursive step <NUM>.

As discussed above, recursive step <NUM> is configured to recursively traverse the underlying graph in the manner dictated by the specifics of query <NUM>, and store the results in a temporary table. Final step <NUM> of multi-step sequence <NUM> is configured to generate the first query sub-result as discussed above in relation to step <NUM>. More specifically, final step <NUM> shall retrieve the final results determined at recursive step <NUM>, and return such results as the first query sub-result. Through the foregoing description, the first query sub-result is based at least in part on the initial step results (i.e., the starting nodes of the traversal), and the intermediate step results (i.e., the results of the graph traversal).

After execution of multi-step sequence <NUM> has completed, query execution engine <NUM> may pass execution control to the next step in query plan <NUM>, if any. It can be appreciated through this description, as well as the detailed description of at least <FIG> and <FIG> above, that the final query result generated at step <NUM> must be based at least in part on the first query sub-result generated by, for example multi-step sequence <NUM>.

In the foregoing discussion of steps <NUM>-<NUM> of flowchart <NUM>, it should also be understood that at times, such steps may be performed in a different order or even contemporaneously with other steps. For example, in embodiments, processing the query in step <NUM> to generate execution steps of the query plan may proceed with different portions of such generation being performed in parallel.

As noted above, relational database system <NUM> of relational database system <NUM> of <FIG> may operate in various ways to process queries. For example, in an embodiment, query preprocessor <NUM>, query optimizer <NUM>, and multi-step query plan generator <NUM> may operate according to flowchart <NUM>, and optionally perform additional steps. For example, embodiments of relational database system <NUM> may operate according to any of <FIG> while or after performing the method steps of flowchart <NUM> as shown in <FIG>.

<FIG> depicts a flowchart <NUM> showing an example method for processing a query by generating a query plan that includes a second multi-step sequence, and determining which of the first and second multi-step sequences to execute, according to an example embodiment. Flowchart <NUM> is described with reference to relational database system <NUM> of <FIG>, although the method is not limited to that implementation. Other structural and operational embodiments will be apparent to persons skilled in the relevant art(s) based on the following discussion regarding flowchart <NUM>.

In step <NUM> of flowchart <NUM>, the query plan is generated to include a second set of execution steps, each of the first and second sets of execution steps to be executed in the alternative to generate the first query sub-result, and processing the query includes determining which of the sets of execution steps to execute. For example, relational database system <NUM> of <FIG> may receive a query <NUM>, that requires a query plan <NUM> with an additional multi-step sequence <NUM>, and where each of the multi-step sequences may execute in the alternative. For example, it can be difficult to determine prior to runtime whether a given query ought to execute as a serial plan, or parallel plan. Multi-step query plan generator <NUM> of query optimizer <NUM> may be configured to detect such ambiguities, and generate query plan <NUM> to include both serial and parallel plans. Further, query plan <NUM> may be configured to further include steps that may determine at runtime which of the plans to execute.

<FIG> shows a flowchart <NUM> of a method for determining which of the first and second sets of execution steps discussed in relation to <FIG> immediately above, should be executed. Flowchart <NUM> begins at step <NUM>. At step <NUM>, it is determined which of the first and second sets of execution steps to execute at least in part on a step result of any other execution step of the query plan, or an intermediate query result of any other set of execution steps of the query plan. For example, query plan <NUM> generated by query optimizer <NUM> in conjunction with multi-step query plan generator <NUM> may include additional execution steps, or additional sets of execution steps (e.g., multi-step sequences), the results of which are used to determine which of the first and second multi-step sequences ought to be executed. Such steps or sets of execution steps may be configured, for example, to more precisely estimate or determine the cardinality of some portion of the query, and thereafter select the more performant set of execution steps. Embodiments may determine which of the first and second sets of execution steps should be executed in other ways. For example, consider flowchart <NUM> of <FIG>.

<FIG> shows a flowchart <NUM> of an alternative method for determining which of the first and second sets of execution steps to execute, according to an example embodiment. Flowchart <NUM> begins at step <NUM>. In step <NUM>, it is determined which of the first and second sets of execution steps to execute based at least in part on an optional parameter included in the query. For example, as may be known to persons skilled in the relevant art(s), parameters may be passed to a query through, for example, a stored procedure. In an embodiment of relational database system <NUM>, query optimizer <NUM> and multi-step query plan generator <NUM> may work in conjunction to generate a query plan <NUM> including first and second sets of execution steps based at least in part on which parameters may be passed to the query via a stored procedure, and cache query plan <NUM> for later use. During the subsequent execution of the stored procedure, embodiments of relational database system <NUM> may use the parameter included in the invocation of the stored procedure to decide which of the first and second sets of execution steps should be executed.

Turning now to <FIG> shows a flowchart <NUM> of a method for processing a query by generating a physical query plan that includes a multi-step sequence including steps configured to communicate data to one or more other steps of the query plan, according to an example embodiment. As discussed above, embodiments of relational database system <NUM> may be configured to generate query plans using query optimizer <NUM> in conjunction with multi-step query plan generator <NUM> that include multi-step sequence such as, for example, multi-step sequence <NUM>. As discussed above in conjunction with the discussion of <FIG>, the results of predicate step <NUM> are stored in a temporary table, and thereafter used by recursion setup step <NUM> that, when executed, retrieves the results stored in that temporary table. In this manner, data may be communicated from one step of multi-step sequence to another step of multi-step sequence. In addition to temporary tables, however, embodiments of multi-step query plan generator <NUM> may generate multi-step sequences wherein step is enabled to pass discrete scalar values to other steps.

Embodiments of relational database system <NUM>, may also operate according to <FIG> shows a flowchart <NUM> of a method for processing a query to generate a query plan that includes first and second sub-plans, each configured to generate sub-plan results, and wherein the second sub-plan re-uses the sub-plan results of the first sub-plan during subsequent executions. Flowchart <NUM> begins at step <NUM>.

At step <NUM>, a first sub-plan comprising at least one execution step is generated. For example, in embodiments, query optimizer <NUM> may operate in conjunction with multi-step query plan generator <NUM> to generate query plan <NUM> to include an execution step or set of execution steps (i.e., multi-step sequence). Operation of flowchart <NUM> continues at step <NUM>.

At step <NUM>, the first sub-plan is executed to generate a first sub-plan result. For example, and as discussed above in conjunction with the discussion of at least <FIG>, <FIG> and <FIG>, an instance of multi-step sequence <NUM> may be executed by multi-step query plan executor <NUM> of query execution engine <NUM> to generate a query sub- result.

At step <NUM>, a second sub-plan comprising at least one execution step is generated based at least in part on the first sub-plan result, the second sub-plan configured to generate a second sub-plan result when executed by the query execution engine, and wherein any subsequent execution of the second sub-plan will reuse the first sub-plan result. In an embodiment, query optimizer <NUM> and multi-step query generator <NUM> of relational database system <NUM> may be configured to generate multi-step sequence <NUM> that depends at least in part on a query sub-result. Such a multi-step sequence may comprise the second sub-plan of step <NUM>. Of course, execution of the second sub-plan (which may be a multi-step sequence) will itself generate a second sub-plan result. Embodiments of query optimizer <NUM> may be configured to cache the second sub-plan for reuse for subsequent executions of that plan, and without requiring rerunning the first sub-plan to obtain first sub-plan result.

According to the invention, embodiments function according to flowchart <NUM> of <FIG> showing a method for processing a query by regenerating a portion of the query plan during execution of the query plan. Flowchart <NUM> begins at step <NUM>. At step <NUM>, a portion of a query plan is regenerated during execution of the query plan. Embodiments of relational database system <NUM> in conjunction query optimizer <NUM> and multi-step query plan generator <NUM> generate a query plan <NUM> including first and second multi-step sequences <NUM>. During execution of query plan <NUM>, the embodiment of the invention causes the portion of query plan <NUM> corresponding to the second multi-step sequence to be recompiled where query optimizer <NUM> made incorrect assumptions during optimization of the query to produce query plan <NUM>, and such incorrect assumptions are or discovered by executing the first multi-step sequence.

Note that foregoing general description of the operation of relational database system <NUM> is provided for example, and embodiments of relational database system <NUM> may operate in manners different than described above. Furthermore, not all steps of flowcharts <NUM>-<NUM> of <FIG> need to be performed in all embodiments. Furthermore, the steps of flowcharts <NUM> and <NUM> may be performed in orders different than shown in some embodiments.

Relational database system <NUM>, flowchart <NUM>, flowchart <NUM>, flowchart <NUM>, flowchart <NUM>, and/or flowchart <NUM>, flowchart <NUM>, and/or flowchart <NUM> may be implemented in hardware, or hardware combined with software and/or firmware. For example, relational database system <NUM>, flowchart <NUM>, flowchart <NUM>, flowchart <NUM>, flowchart <NUM>, flowchart <NUM>, flowchart <NUM>, and/or flowchart <NUM> may be implemented as computer program code/instructions configured to be executed in one or more processors and stored in a computer readable storage medium. Alternatively, relational database system <NUM>, flowchart <NUM>, flowchart <NUM>, flowchart <NUM>, flowchart <NUM>, flowchart <NUM>, flowchart <NUM>, and/or flowchart <NUM> may be implemented as hardware logic/electrical circuitry.

For instance, in an embodiment, one or more, in any combination, of relational database system <NUM>, flowchart <NUM>, flowchart <NUM>, flowchart <NUM>, flowchart <NUM>, flowchart <NUM>, flowchart <NUM>, and/or flowchart <NUM> may be implemented together in a SoC. The SoC may include an integrated circuit chip that includes one or more of a processor (e.g., a central processing unit (CPU), microcontroller, microprocessor, digital signal processor (DSP), etc.), memory, one or more communication interfaces, and/or further circuits, and may optionally execute received program code and/or include embedded firmware to perform functions.

<FIG> depicts an exemplary implementation of a computing device <NUM> in which embodiments may be implemented. For example, relational database system <NUM> may be implemented using one or more computing devices similar to computing device <NUM> in stationary or mobile computer embodiments, including one or more features of computing device <NUM> and/or alternative features. The description of computing device <NUM> provided herein is provided for purposes of illustration, and is not intended to be limiting. Embodiments may be implemented in further types of computer systems, as would be known to persons skilled in the relevant art(s).

A number of program modules may be stored on the hard disk, magnetic disk, optical disk, ROM, or RAM. These programs include operating system <NUM>, one or more application programs <NUM>, other programs <NUM>, and program data <NUM>. Application programs <NUM> or other programs <NUM> may include, for example, computer program logic (e.g., computer program code or instructions) for implementing relational database system <NUM>, flowchart <NUM>, flowchart <NUM>, flowchart <NUM>, flowchart <NUM>, flowchart <NUM>, flowchart <NUM>, and/or flowchart <NUM>, and/or further embodiments described herein.

Such computer programs, when executed or loaded by an application, enable computing device <NUM> to implement features of embodiments described herein.

In one embodiment, a system is provided. The system comprises: a query pre-processor configured to receive a query and construct a query tree of logical operators; a query optimizer configured to generate an executable query plan based at least in part on the query tree of logical operators, the executable query plan comprising at least a set of execution steps configured to be executed to generate a first query sub-result, the set of execution steps comprising: an initial step configured to be executed to generate first step results after receiving execution control, and pass execution control to a step different than the initial step, at least one intermediate step configured to generate second step results after receiving execution control, and pass execution control to any step of the set of execution steps, and a final step configured to, after receiving execution control, generate the first query sub-result based at least in part on the initial step results and the intermediate step results; and a query execution engine configured to execute the query to generate a final query result based at least in part on the first query sub-result by passing execution control to the initial step of the set of execution steps of the executable query plan.

In an embodiment of the foregoing system, the executable query plan further comprises: a second set of execution steps configured to generate a second query sub-result; and the query execution is configured to execute the query to generate the final query result further based at least in part on the second query sub-result.

In another embodiment of the foregoing system, the at least one intermediate step is further configured to pass execution control to any execution step in the executable query plan.

In an embodiment of the foregoing system, the query optimizer is configured to generate the executable query plan to include an execution step configured to communicate data to one or more other execution steps of the executable query plan.

In another embodiment of the foregoing system, the query optimizer is further configured to generate the executable query plan by including third and fourth sets of executions steps, each of the third and fourth sets of executions steps configured to be executed in the alternative; and the query execution engine is further configured to determine which of the third and fourth sets of execution steps to execute while the executable query plan is being executed.

In an embodiment of the foregoing system, the query execution engine is configured to determine which of the third and fourth sets of execution steps to execute based at least in part on at least one of a step result of any execution step of the executable query plan, or an intermediate query result of any other set of execution steps of the executable query plan.

In another embodiment of the foregoing system, the query execution engine is configured to determine which of the third and fourth sets of execution steps to execute based at least in part on whether an optional parameter is included in the query.

In an embodiment of the foregoing system, wherein, to generate the executable query plan, the query optimizer is further configured to: generate a first sub-plan comprising at least one execution step configured to generate a first sub-plan result; execute the first sub-plan to generate the first sub-plan result; and generate a second sub-plan comprising at least one execution step based at least in part on the first sub-plan result, the second sub-plan configured to generate a second sub-plan result when executed by the query execution engine, and wherein any subsequent execution of the second sub-plan will re-use the first sub-plan result.

In another embodiment of the foregoing system, the query optimizer is configured to re-generate at least a portion of the executable query plan during execution of the executable query plan.

A computer-implemented method of executing a query to generate a query result is provided. In an embodiment, the computer-implemented method comprises: receiving a query in a database application; processing the query, wherein said processing the query comprises: generating a query plan for the query, the query plan comprising at least a set of execution steps configured to be executed to generate a first query sub-result, the set of execution steps comprising: an initial step configured to be executed to generate first step results after receiving execution control, and pass execution control to a step different than the initial step, at least one intermediate step configured to generate second step results after receiving execution control, and pass execution control to any step of the set of execution steps, and a final step configured to, after receiving execution control, generate the first query sub-result based at least in part on the initial step results and the intermediate step results; and executing the query to generate a final query result based at least in part on the first query sub-result by passing execution control to the initial step of the set of execution steps of the query plan.

In an embodiment of the foregoing method, the query plan further comprises: a second set of execution steps configured to generate a second query sub-result; and wherein said executing the query to generate the final query result further comprises: executing the query to generate the final query result further based at least in part on the second query sub-result.

In an embodiment of the foregoing method, the at least one intermediate step comprises a recursive step configured to generate recursive step results and pass execution control to itself unless the recursive step results satisfy a pre-defined condition.

In another embodiment of the foregoing method, generating a query plan for the query comprises: generating the query plan to include an execution step configured to communicate data to one or more other execution steps of the query plan.

In an embodiment of the foregoing method, said generating a query plan for the query comprises: generating the query plan to include third and fourth sets of executions steps, each of the third and fourth sets of executions steps configured to be executed in the alternative; and wherein said processing the query further comprises: determining which of the third and fourth sets of execution steps to execute.

In another embodiment of the foregoing method, said determining which of the third and fourth sets of execution steps to execute comprises: determining which of the third and fourth sets of execution steps to execute based at least in part on at least one of a step result of any other execution step of the query plan, or an intermediate query result of any other set of execution steps of the query plan.

In an embodiment of the foregoing method, said determining which of the third and fourth sets of execution steps to execute comprises: determining which of the third and fourth sets of execution steps to execute based at least in part on an optional parameter included in the query.

In another embodiment of the foregoing method, generating a query plan for the query further comprises: generating a first sub-plan comprising at least one execution step configured to generate a first sub-plan result; executing the first sub-plan to generate the first sub-plan result; and generating a second sub-plan comprising at least one execution step based at least in part on the first sub-plan result, the second sub-plan configured to generate a second sub-plan result when executed by the query execution engine, and wherein any subsequent execution of the second sub-plan will re-use the first sub-plan result.

In an embodiment of the foregoing method, said processing the query further comprises: re-generating at least a portion of the query plan during execution of the query plan.

In still another embodiment, a computer-readable memory device having computer program code recorded thereon that when executed by at least one processor of a computing device causes the at least one processor to perform operations is provided.

In an embodiment of the foregoing computer-readable memory device, the operations comprise: receiving a query in a database application; processing the query, wherein said processing the query comprises: generate a query plan for the query, the query plan comprising at least a set of execution steps configured to be executed to generate a first query sub-result, the set of execution steps comprising: an initial step configured to be executed to generate first step results after receiving execution control, and pass execution control to a step different than the initial step, at least one intermediate step configured to generate second step results after receiving execution control, and pass execution control to any step of the set of execution steps, and a final step configured to, after receiving execution control, generate the first query sub-result based at least in part on the initial step results and the intermediate step results; and executing the query to generate a final query result based at least in part on the first query sub-result by passing execution control to the initial step of the set of execution steps of the query plan.

In another embodiment of the foregoing computer-readable memory device, the at least one intermediate step comprises a recursive step configured to generate recursive step results and pass execution control to itself unless the recursive step results satisfy a pre-defined condition.

Claim 1:
A computer-implemented method to execute a query to generate a query result (<NUM>), the method comprising:
receiving (<NUM>) a query (<NUM>) in a database application;
processing the query, wherein said processing the query comprises:
generating (<NUM>) a query plan for the query, the query plan comprising at least a first set of execution steps configured to be executed to generate a first query sub-result (<NUM>), the first set of execution steps comprising:
an initial step (<NUM>) configured to be executed to generate first step results after receiving execution control, and pass execution control to a step different than the initial step,
at least one intermediate step (<NUM>) configured to generate second step results after receiving execution control, and pass execution control to any step of the first set of execution steps, and
a final step (<NUM>) configured to, after receiving execution control, generate the first query sub-result based at least in part on the initial step results and the intermediate step results; and
executing (<NUM>) the query plan to generate a final query result based on the first query sub-result by passing execution control to the initial step of the first set of execution steps of the query plan,
wherein the method is characterized in that it further includes:
generate the executable query plan to include a second set of execution steps; and
re-generate a portion of the executable query plan during execution of the executable query plan, wherein the regenerating includes re-compiling a portion of the query plan corresponding to the second set of execution steps based on a discovery of incorrect assumptions made during generation of the executable query plan, where the discovery is made by executing the first set of execution steps.