Estimating number of iterations or self joins required to evaluate iterative or recursive database queries

Patent metadata

Field	Value
Publication number	US-9152670-B2
Application number	US-201213722133-A
Country	US
Kind code	B2
Filing date	Dec 20, 2012
Priority date	Dec 20, 2012
Publication date	Oct 6, 2015
Grant date	Oct 6, 2015

Abstract

The number of iterations or self joins required to execute a recursive database query can be estimated. It will be appreciated that this estimation can be used to plan the execution of the recursive query and can be made in various ways and for various applications. By way of example, an estimated number of iterations or self joins required to execute a recursive database query (e.g., 12) can be used as a basis to determine or plan an optimal execution plan. For example, given an estimated twelve (12) iterations, an execution plan can be determined for executing at least the first three (3) iterations or for executing every three (3) iterations, whereas for an estimated twenty (21) iterations required to complete a recursive database query, an execution plan can be determined for the first five (5) or six (6) iterations, and so on.

First claim

What is claimed is:

1. A method, implemented at least partly by a device, for facilitating execution of a database query of a database, wherein the database query requires multiple sub-queries to be executed as multiple iterations such that a result of a first one of the sub-queries is needed to be determined in a first iteration of the iterations in order to determine a result of a second one of the sub-queries in a second iteration of the iterations to be performed after the first iteration, and wherein the method comprises:
estimating a projected number of iterations required to execute the database query including the first and second iterations at least partly by determining the projected number of iterations at least partly based on the following: (i) an estimated number of all nodes in one or more recursion trees (I) that represent the organization of data involved in the database query, (ii) the number of nodes in the one or more recursion trees that originate at a seed (S) provided as input of the database query, and (iii) an estimated average of the outgoing edges of the nodes of the one or more recursion trees (Avg_outDegree); and
determining at least one execution plan for executing one or more of the iterations, at least partly based on the projected number of iterations required to execute the database query.

2. The method of claim 1 , wherein the determining of the at least one execution plan for executing the one or more of the iterations comprises:
determining the projected number of iterations and/or self joins planned by the at least one execution.

3. The method of claim 1 , wherein the estimating of the projected number of iterations further comprises:
determining the projected number of iterations at least partly based on the ratio of the estimated number of all nodes and a product of the seed and the Avg_outDegree(I/(S*Avg_outDegree)).

4. The method of claim 3 , wherein the estimating number of all nodes in one or more recursion trees (I) that represent the organization of data involved in the database query is determined at least partly based on one or more of the following: (i) the number of the distinct nodes, including origination nodes and destination nodes, in the one or more recursion trees (NUV(C1∩C2)) that represent an intersection of two or more columns involved in at least one join operation of the database query, and (ii) an average number of incoming edges of the nodes of the one or more recursion trees (Avg_inDegree).

5. The method of claim 4 , wherein the estimated average of the incoming edges of the nodes of the one or more recursion trees (Avg_inDegree) is determined at least partly based one or more of the following: (i) a number of total rows (R) representing number of rows in one or more graph tables corresponding to the one or more recursion trees that represent the organization of data involved in the database query, and (ii) number of unique values of destination nodes of the one or more recursion trees that represent the organization of data involved in the database query (NUV(C1)).

6. The method of claim 4 , wherein the estimated average of the incoming edges of the nodes of the one or more recursion trees (Avg_inDegree) is determined at least partly based on division of total number of rows R by NUV(C1).

7. The method of claim 1 , wherein the estimated average of the outgoing edges of the nodes of the one or more recursion trees (Avg_outDegree) is determined at least partly based one or more of the following: (i) a number of total rows (R) representing number of rows in one or more graph tables corresponding to the one or more recursion trees that represent the organization of data involved in the database query, and (ii) the number of unique values of one or more of source nodes of the one or more recursion trees that represent the organization of data involved in the database query (NUV(C2)).

8. The method of claim 1 , wherein the estimated average of the outgoing edges of the nodes of the one or more recursion trees (Avg_outDegree) is determined at least partly based on (R/NUV(C2)).

9. A device that includes one or more processors configured to:
estimate a projected number of iterations required to execute a database query that requires multiple sub-queries to be executed as multiple iterations such that a result of a first one of the sub-queries is needed to be determined in a first iteration of the iterations in order to determine a result of a second one of the sub-queries in a second iteration of the iterations to be performed after the first iteration; wherein the estimating comprises determining the projected number of iterations at least partly based on: (i) an estimated number of all nodes in one or more recursion trees (I) that represent the organization of data involved in the database query, (ii) the number of nodes in the one or more recursion trees that originate at a seed (S) provided as input of the database query, and (iii) an estimated average of the outgoing edges of the nodes of the one or more recursion trees (Avg_outDegree); and
determine at least one execution plan for executing one or more of the iterations, at least partly based on the projected number of iterations required to execute the database query.

10. A non-transitory computer readable storage medium storing at least executable code for facilitating execution of a database query of a database, wherein the database query requires multiple sub-queries to be executed as multiple iterations such that a result of a first one of the sub-queries is needed to be determined in a first iteration of the iterations in order to determine a result of a second one of the sub-queries in a second iteration of the iterations to be performed after the first iteration, and wherein the executable code includes:
executable code for estimating a projected number of iterations required to execute the database query including the first and second iterations at least partly by determining the projected number of iterations at least partly based on: (i) an estimated number of all nodes in one or more recursion trees (I) that represent the organization of data involved in the database query, (ii) the number of nodes in the one or more recursion trees that originate at a seed (S) provided as input of the database query, and (iii) an estimated average of the outgoing edges of the nodes of the one or more recursion trees (Avg_outDegree); and
executable code for determining at least one execution plan for executing one or more of the iterations, at least partly based on the projected number of iterations required to execute the database query.

Assignees

• Teradata Corp
• Teradata Us Inc

Inventors

• Ghazal Ahmad Said
• Seid Dawit

Classifications

• G06F16/24542 Primary

  Plan optimisation · CPC title

• G06F17/30463 Primary

  Physics · mapped topic