Query optimization using join cardinality

Patent metadata

Field	Value
Publication number	US-10133778-B2
Application number	US-201514947252-A
Country	US
Kind code	B2
Filing date	Nov 20, 2015
Priority date	Nov 20, 2015
Publication date	Nov 20, 2018
Grant date	Nov 20, 2018

Abstract

Disclosed herein are system, method, and computer program product embodiments for utilizing join cardinality to improve the performance of query processing. An embodiment operates by a database engine receiving a query including a join operation on a first and a second table using a join predicate, and a tag for the join operation indicating a cardinality relationship between the first and the second table when satisfying the join predicate. Then, the database engine generates a query processing plan for performing the query. For the join operation, the database engine selects one of the first or the second tables to remove from the join operation based on a type of the join operation and the tag. Based on the selecting, the database engine may remove may the join operation and the selected table from the query processing plan.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
receiving a query including a join operation on a first and a second table using a join predicate, and a tag for the join operation indicating a cardinality relationship between the first and the second table when satisfying the join predicate;
generating a query processing plan for performing the query;
selecting, based on a type of the join operation and the tag, one of the first or the second tables to remove from the join operation; and
removing, based on the selecting, the join operation and the selected table from the query processing plan,
wherein at least one of the receiving, generating, removing, and verifying are performed by one or more computers.

2. The method of claim 1 , wherein the first table is representative of one of a table stored in a database, a joined table created from joining the first table with a second table in the database, or a second joined table created from joining the first joined table with a third table in the database.

3. The method of claim 1 , herein the tag includes a first part and a second part, wherein the first part indicates a cardinality of the first table with respect to the second table, and wherein the second part indicates a cardinality of the second table with respect to the first table.

4. The method of claim 1 , wherein the selecting comprises:
comparing the type of the join operation and the tag with programmed optimization criteria to determine the selected table.

5. The method of claim 4 , wherein the selecting further comprises:
using a projection of the query processing plan to verify that the selected table can be removed without affecting a result produced by the query processing plan.

6. The method of claim 1 , wherein the query processing plan is represented as a relational binary tree having a projection in a root node and the join operation in an internal node that is parent to a first and a second child node respectively corresponding to the first and second table, and wherein the removing comprises:
pruning, from the query processing plan, the internal node and a third child node corresponding to the selected table, wherein the third child node is one of the first and the second child nodes.

7. The method of claim 6 , wherein the verifying comprises:
traversing from a parent of the internal node to the root node to check that no ancestor node of the internal node accesses data from the third child node to produce the result of the query.

8. The method of claim 1 , wherein the query includes a plurality of join operations, wherein the query processing plan is represented as a relational binary tree having a root node containing a projection of the query and having a plurality of internal nodes, each internal node corresponding to a respective join operation of the query, and wherein the method further comprises:
determining whether each join operation and a corresponding internal node can be pruned from the binary tree without affecting a result produced by the query processing plan; and
prioritizing the determining for join operations that are closer to the root node.

9. A system, comprising:
a memory; and
at least one processor coupled to the memory and configured to:
receive a query including a join operation on a first and a second table using a join predicate, and a tag for the join operation indicating a cardinality relationship between the first and the second table when satisfying the join predicate;
generate a query processing plan for performing the query;
select, based on a type of the join operation and the tag, one of the first or the second tables to remove from the join operation, and
remove, based on the selecting, the join operation and the selected table from the query processing plan.

10. The system of claim 9 , wherein the first table is representative of one of a table stored in a database, a joined table created from joining the first table with a second table in the database, or a second joined table created from joining the first joined table h a third table in the database.

11. The system of claim 9 , wherein the tag includes a first part and a second part, wherein the first part indicates a cardinality of the first table with respect to the second table, and wherein the second part indicates a cardinality of the second table with respect to the first table.

12. The system of claim 9 , wherein to select the at least one processor is further configured to:
compare the type of the join operation and the tag with programmed optimization criteria to determine the selected table.

13. The system of claim 12 , wherein to select the at least one processor is further configured to:
using a projection of the query processing plan to verify that the selected table can be removed without affecting a result produced by the query processing plan.

14. The system of claim 9 , wherein the query processing plan is represented as a relational binary tree having a projection in a root node and the join operation in an internal node that is parent to a first and a second child node respectively corresponding to the first and second table, and wherein to remove the at least one processor is further configured to:
prune, from the query processing plan, the internal node and a third child node corresponding to the selected table, wherein the third child node is one of the first and the second child nodes.

15. The system of claim 14 , wherein to verify the at least one processor is further configured to:
traverse from a parent of the internal node to the root node to check that no ancestor node of the internal node accesses data from the third child node to produce the result of the query.

16. The system of claim 9 , wherein the query includes a plurality of join operations, wherein the query processing plan is represented as a relational binary tree having a root node containing a projection of the query and having a plurality of internal nodes, each internal node corresponding to a respective join operation of the query, and wherein the at least one processor is further configured to:
determine whether each join operation and a corresponding internal node can be pruned from the binary tree without affecting a result produced by the query processing plan; and
prioritize the determining for join operations that are closer to the root node.

17. A tangible computer-readable device having instructions stored thereon that, when executed by at least one computing device, causes the at least one computing device to perform operations comprising:
receiving a query including a join operation on a first and a second table using a join predicate, and a tag for the join operation indicating a cardinality relationship between the first and the second table when satisfying the join predicate;
generating a query processing plan for performing the query;
selecting, based on a type of the join operation and the tag, one of the first or the second tables to remove from the join operation; and
removing, based on the selecting, the join operation and the selected table from the query processing plan,
wherein at least one of the receiving, generating, removing, and verifying are performed by one or more computers.

18. The computer-readable device of claim 15 , wherein the selecting comprises:
comparing the type of the join operation and the tag with programmed optimization criteria to determine the selected table; and
using a projection of the query processing plan to verify that the selected table can be

Assignees

• Sap Se

Inventors

• Lee Taehyung
• Yoon Joo Young
• Song Sang Il
• Yoon Yongsik
• Wi Sung Heun
• Woo Junhee

Classifications

• G06F16/24544 Primary

  Join order optimisation · CPC title

• G06F16/00

  Information retrieval; Database structures therefor; File system structures therefor · CPC title

• G06F17/30

  Physics · mapped topic

• G06F17/30466 Primary

  Physics · mapped topic