Join type for optimizing database queries

• US 10,102,248 B2
• Filed: 01/27/2015
• Issued: 10/16/2018
• Est. Priority Date: 10/10/2012
• Status: Active Grant

• Current Assignee: Tmaxtibero Company Limited
• Original Assignee: TmaxData Co., Ltd.
• Inventors: Kang, BongChae, Park, Sang Young, Yi, Sukwon, Choi, Youngjae
• Primary Examiner(s): Reyes, Mariela
• Assistant Examiner(s): Jacobs, Edward
• Application Number:
  US14/606,586
• Publication Number:
  US 20150142775A1
• Time in Patent Office: 1,358 Days
• 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;

wherein 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;

wherein 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;

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;

wherein the first aggregation join is created under a situation that when both the tables are joined, the columns belonging 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 belonging to the other table; and

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.

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 sub query 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 sub query 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 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 belonging 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.

11. 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.

12. The method of claim 11, 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.

13. 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.

14. A non-transitory computer readable medium comprising machine readable instructions executable by a processor, the instructions comprising a query compiler, the 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;

wherein 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;

wherein 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;

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;

wherein the first aggregation join is created under a situation that when both the tables are joined, the columns belonging 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 belonging to the other table; and

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.

15. The query compiler non-transitory computer readable medium of claim 14, 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 belonging 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.