JOIN TYPE FOR OPTIMIZING DATABASE QUERIES

• US 20150142775A1
• Filed: 01/27/2015
• Published: 05/21/2015
• Est. Priority Date: 10/10/2012
• Status: Active Grant

• Current Assignee: Tmaxtibero Company Limited
• Original Assignee: Tibero Company Limited
• Inventors: KANG, BongChae, PARK, Sang Young, YI, Sukwon, CHOI, Youngjae
• Granted Patent: US 10,102,248 B2
• Time in Patent Office: Days
• US Class Current: 707/714
• CPC Class Codes: G06F 16/24526 Internal representations for queries
• CPC Class Codes: G06F 16/24535 of sub-queries or views
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination

Abstract

A query complier analyzes a query to identify a correlated scalar subquery. The query complier transforms the query having the correlated scalar subquery into a query of AGGREGATION INNER/OUTER JOIN or MAX1ROW INNER/OUTER JOIN depending on a result type of the correlated scalar subquery. The AGGREGATION INNER/OUTER JOIN performs JOIN on the rows of the correlated scalar subquery with the rows of a main query and AGGREGATE on the joined rows and returns a result of the joined rows of the main query and aggregation value thereof. The MAX1ROW INNER/OUTER JOIN performs JOIN on the rows of the correlated scalar subquery with the rows of a main query, raises Error when the number of joined rows of the subquery is two or more and returns a result of the row of the main query and the joined row of the subquery.

Claims

1. A method for optimizing database queries in a query compiler, comprising:

searching a subquery within a query;

analyzing the searched subquery to identify a candidate of a scalar subquery;

analyzing the candidate scalar subquery to identify a candidate of a correlated scalar subquery; and

transforming the query having the candidate correlated scalar subquery into a query of a quasi-JOIN depending on a result type of the candidate correlated scalar subquery,

wherein the quasi-JOIN is a join to process grouping and aggregation, in which Group by Aggregation and Join that is a lower node of the Group by Aggregation are merged together and the quasi-JOIN includes a first aggregation join in which join keys and group keys do not match each other and a second aggregation join in which join keys and group keys match each other; and

the first aggregation join creates a result in which the group keys are partially grouped and subjected to Aggregation when the join keys and the groups have a matching condition, wherein the results for the rows with the group keys that are duplicated are grouped at a Group by Aggregation that is an upper node;

the second aggregation join returns a result in which the group keys are grouped and subjected to Aggregation when the join keys and the groups have a matching condition.

2. The method of claim 1, wherein said analyzing the searched subquery comprises:

analyzing whether the searched subquery is written along with a comparison operator while being included in WHERE clause to identify the searched subquery as the candidate scalar subquery.

3. The method of claim 1, wherein said analyzing the searched subquery includes:

analyzing whether the searched subquery is included in SELECT clause to identify the searched subquery as the candidate scalar subquery.

4. The method of claim 1, wherein said analyzing the candidate scalar subquery comprises:

analyzing whether the candidate scalar subquery uses a column included in a table of the main query to identify the candidate scalar subquery as the candidate correlated scalar subquery.

5. The method of claim 1, wherein said transforming the query having the candidate correlated scalar subquery into a query of a quasi-JOIN includes:

performing UNNEST on the query having the candidate correlated scalar subquery to create a query of AGGREGATION INNER/OUTER JOIN when the candidate correlated scalar subquery takes a type of returning a result of AGGREGATION.

6. The method of claim 1, wherein said transforming the query having the candidate correlated scalar subquery into a query of a quasi-JOIN includes:

performing UNNEST on the query having the candidate correlated scalar subquery to create a query of MAX1ROW INNER/OUTER JOIN when the candidate correlated scalar subquery takes a type of returning one column value.

7. The method of claim 5, wherein the AGGREGATION INNER/OUTER JOIN functions to perform JOIN on the rows of the correlated scalar subquery with the rows of the main query and AGGREGATE on the joined rows and returns a result of the joined rows of the main query and aggregation value thereof.

8. The method of claim 6, wherein the MAX1ROW INNER/OUTER JOIN functions to perform JOIN on the row of the correlated scalar subquery with the rows of the main query, raises Error when the number of the joined rows of the subquery is two or more and returns a result of the row of the main query and the joined row of the subquery.

9. The method of claim 1, wherein the quasi-JOIN is implemented by join algorithms having HASH JOIN, MERGE JOIN and Nested Loop Join.

10. The method of claim 1, wherein a table to which the group keys belong is a group table and a table to which the columns used in performing the aggregation belong is an aggregation table;

and

wherein the first aggregation join is created under a situation that when both the tables are joined, the columns belonged to any one of the tables are selected as the group keys, and the group keys and the join keys do not match each other when the aggregation is performed with the columns belonged to the other table.

11. The method of claim 10, wherein the first aggregation join is configured to:

designate the rows having the same join key as one group to produce each structure to store the aggregation for each designated group; and

calculate an aggregation value for the aggregation structure of the join key group relevant to the join key while searching the aggregation table in a way of calculating each join key group once only even though each join key group has several rows.

12. The method of claim 11, wherein when there is a shortage of storage space in the memories in the course of performing the join;

and

wherein the first aggregation join is further configured to;

transfer the group keys for the rows belonged to the join key group and the structures capable of merging the aggregation results to the Group by Aggregation that is an upper node, wherein the Group by Aggregation merges the aggregation structures for each same group to return the result thereof.

13. The method of claim 1, wherein the second aggregation join is configured to:

designate the rows having the same join key in the group table as one group; and

produce each structure to store aggregation for each designated group and variables to count the rows having the same join key in the group table.

14. The method of claim 13, wherein the second aggregation join is configured to:

return the result of performing the aggregation with the group key substituted for the join key by self-merging the aggregations as many as the number of the rows counted for each join key.

15. The method of claim 5, wherein the MAX1ROW JOIN generates an error when at least two rows are joined among the rows in the driving table.

16. A query compiler, comprising:

a parser configured to parse a query provided to the query compiler;

a query rewriter configured to analyze the parsed query to identify a correlated scalar subquery, and transform the query having the identified correlated scalar subquery into a query of a quasi-JOIN according to a result type of the identified correlated scalar subquery; and

a query optimizer configured to make a plurality of execution plans from the transformed query of a quasi-JOIN using statistical information, and select a query execution plan having a minimum cost among the plurality of execution plans,

wherein the quasi-JOIN is a join to process grouping and aggregation, in which Group by Aggregation and Join that is a lower node of the Group by Aggregation are merged together and the quasi-JOIN includes a first aggregation join in which join keys and group keys do not match each other and a second aggregation join in which join keys and group keys match each other; and

the first aggregation join creates a result in which the group keys are partially grouped and subjected to Aggregation when the join keys and the groups have a matching condition, wherein the results for the rows with the group keys that are duplicated are grouped at a Group by Aggregation that is an upper node; and

the second aggregation join returns a result in which the group keys are grouped and subjected to Aggregation when the join keys and the groups have a matching condition.

17. The query compiler of claim 16, wherein a table to which the group keys belong is a group table and a table to which the columns used in performing the aggregation belong is an aggregation table;

the first aggregation join is created under a situation that when both the tables are joined, the columns belonged to any one of the tables are selected as the group keys, and the group keys and the join keys do not match each other when the aggregation is performed with the columns belonged to the other table; and

the first aggregation join is configured to;

designate the rows having the same join key as one group to produce each structure to store the aggregation for each designated group; and

calculate an aggregation value for the aggregation structure of the join key group relevant to the join key while searching the aggregation table in a way of calculating each join key group once only even though each join key group has several rows.

18. The query compiler of claim 17, wherein when there is a shortage of storage space in the memories in the course of performing the join;

and

the first aggregation join is further configured to;

transfer the group keys for the rows belonged to the aggregation group and the structures capable of merging the aggregation results to the Group by Aggregation that is an upper node, wherein the Group by Aggregation merges the aggregation structures for each same group to return the result thereof.