Granted Patent B2

US 12,287,788 · App. 18/339,284 · Granted Apr 29, 2025

Inventors: Seyed Mohammad Amin Kamali (Orleans, CA); Vincent Corvinelli (Mississauga, CA); Calisto Zuzarte (Pickering, CA)

Assignee: International Business Machines Corporation

G06F16/24544G06F16/2456

Abstract

Claims (96)

1. A computer-implemented method comprising:

building a join cardinality estimation model by:

generating a training query having a known join cardinality;

generating an adjacency matrix encoding a join graph of the training query, wherein, for a given query that joins a set of n tables, the respective adjacency matrix can be defined as an n×n matrix, where a value in the matrix at a position (i, j) is 1 if the table i is joined with table j and 0 otherwise;

encoding one side of a diagonal axis of the adjacency matrix; and

training the join cardinality estimation model using the encoded adjacency matrix and the known join cardinality;

performing an inference using the join cardinality estimation model, the inference comprising a predicted join cardinality for a query; and

executing a query execution plan for the query using the predicted join cardinality.

2. The computer-implemented method of claim 1 , wherein performing the inference comprises:

generating an adjacency matrix encoding a join graph of the query;

encoding one side of a diagonal axis of the adjacency matrix;

inputting the encoded adjacency matrix into the join cardinality estimation model; and

receiving, as output, the predicted join cardinality.

3. The computer-implemented method of claim 1 , wherein encoding the adjacency matrix includes condensing the adjacency matrix to a one dimensional vector for machine learning algorithms requiring a vector input.

4. The computer-implemented method of claim 1 , wherein building the join cardinality estimation model further comprises:

generating an additional adjacency matrix encoding a join type of the training query;

encoding one side of a diagonal axis of the additional adjacency matrix into a join type adjacency matrix; and

concatenating the encoded join type adjacency matrix with the encoded join graph prior to training the join cardinality estimation model.

5. The computer-implemented method of claim 1 , wherein building the join cardinality estimation model further comprises:

generating an additional adjacency matrix encoding a join operator of the training query;

encoding one side of a diagonal axis of the additional adjacency matrix into a join operator adjacency matrix; and

concatenating the encoded join operator adjacency matrix with the encoded join graph prior to training the join cardinality estimation model.

6. The computer-implemented method of claim 1 , wherein building the join cardinality estimation model further comprises:

generating an additional adjacency matrix encoding a ratio of the cardinality of join columns to table cardinality on each side of a join of the training query;

encoding one side of a diagonal axis of the additional adjacency matrix into a column-to-table adjacency matrix; and

concatenating the encoded column-to-table adjacency matrix with the encoded join graph prior to training the join cardinality estimation model.

7. The computer-implemented method of claim 1 , wherein building the join cardinality estimation model further comprises:

generating an additional adjacency matrix encoding a ratio of the cardinality of left and right tables of a join of the training query;

encoding one side of a diagonal axis of the additional adjacency matrix into a table cardinalities adjacency matrix; and

concatenating the encoded table cardinalities adjacency matrix with the encoded join graph prior to training the join cardinality estimation model.

8. The computer-implemented method of claim 1 , wherein building the join cardinality estimation model further comprises:

generating an additional adjacency matrix encoding a measure of skewness for each join column of a join of the training query;

encoding one side of a diagonal axis of the additional adjacency matrix into a skewness adjacency matrix; and

concatenating the encoded skewness adjacency matrix with the encoded join graph prior to training the join cardinality estimation model.

9. The computer-implemented method of claim 1 , wherein building the join cardinality estimation model further comprises:

generating an additional adjacency matrix encoding a measure of a join selectivity of a join without local predicates of the training query;

encoding one side of a diagonal axis of the additional adjacency matrix into a join factor adjacency matrix; and

concatenating the encoded join factor adjacency matrix with the encoded join graph prior to training the join cardinality estimation model.

10. The computer-implemented method of claim 1 , wherein building the join cardinality estimation model further comprises:

generating an additional adjacency matrix encoding an inclusion measure of one side of a join column values in the other side of the join column values of the training query;

encoding one side of a diagonal axis of the additional adjacency matrix into an inclusion factor adjacency matrix; and

concatenating the encoded inclusion factor adjacency matrix with the encoded join graph prior to training the join cardinality estimation model.

11. The computer-implemented method of claim 1 , wherein building the join cardinality estimation model further comprises:

generating an additional adjacency matrix encoding a cardinality of respective base tables and a selectivity of local predicates on the base tables of a join of the training query;

encoding one side of a diagonal axis of the additional adjacency matrix into a node coordinates adjacency matrix; and

concatenating the encoded node coordinates adjacency matrix with the encoded join graph prior to training the join cardinality estimation model.

12. A system having a memory, computer readable instructions, and one or more processors for executing the computer readable instructions, the computer readable instructions controlling the one or more processors to perform operations comprising:

building a join cardinality estimation model by:

generating a training query having a known join cardinality;

generating an adjacency matrix encoding a join graph of the training query, wherein, for a given query that joins a set of n tables, the respective adjacency matrix can be defined as an n×n matrix, where a value in the matrix at a position (i, i) is 1 if the table i is joined with table j and 0 otherwise;

encoding one side of a diagonal axis of the adjacency matrix; and

training the join cardinality estimation model using the encoded adjacency matrix and the known join cardinality;

performing an inference using the join cardinality estimation model, the inference comprising a predicted join cardinality for a query; and

executing a query execution plan for the query using the predicted join cardinality.

13. The system of claim 12 , wherein performing the inference comprises:

generating an adjacency matrix encoding a join graph of the query;

encoding one side of a diagonal axis of the adjacency matrix;

inputting the encoded adjacency matrix into the join cardinality estimation model; and

receiving, as output, the predicted join cardinality.

14. The system of claim 12 , wherein encoding the adjacency matrix includes condensing the adjacency matrix to a one dimensional vector for machine learning algorithms requiring a vector input.

15. The system of claim 12 , wherein building the join cardinality estimation model further comprises:

generating an additional adjacency matrix encoding a join type of the training query;

encoding one side of a diagonal axis of the additional adjacency matrix into a join type adjacency matrix; and

concatenating the encoded join type adjacency matrix with the encoded join graph prior to training the join cardinality estimation model.

16. A computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by one or more processors to cause the one or more processors to perform operations comprising:

building a join cardinality estimation model by:

generating a training query having a known join cardinality;

generating an adjacency matrix encoding a join graph of the training query, wherein, for a given query that joins a set of n tables, the respective adjacency matrix can be defined as an n×n matrix, where a value in the matrix at a position (i, j) is 1 if the table i is joined with table j and 0 otherwise;

encoding one side of a diagonal axis of the adjacency matrix; and

training the join cardinality estimation model using the encoded adjacency matrix and the known join cardinality;

performing an inference using the join cardinality estimation model, the inference comprising a predicted join cardinality for a query; and

executing a query execution plan for the query using the predicted join cardinality.

17. The computer program product of claim 16 , wherein performing the inference comprises:

generating an adjacency matrix encoding a join graph of the query;

encoding one side of a diagonal axis of the adjacency matrix;

inputting the encoded adjacency matrix into the join cardinality estimation model; and

receiving, as output, the predicted join cardinality.

18. The computer program product of claim 16 , wherein encoding the adjacency matrix includes condensing the adjacency matrix to a one dimensional vector for machine learning algorithms requiring a vector input.

19. The computer program product of claim 16 , wherein building the join cardinality estimation model further comprises:

generating an additional adjacency matrix encoding a join type of the training query;

encoding one side of a diagonal axis of the additional adjacency matrix into a join type adjacency matrix; and

concatenating the encoded join type adjacency matrix with the encoded join graph prior to training the join cardinality estimation model.

20. A computer-implemented method comprising:

generating a training query having a known join cardinality;

generating an adjacency matrix encoding a join graph of the training query, wherein, for a given query that joins a set of n tables, the respective adjacency matrix can be defined as an n×n matrix, where a value in the matrix at a position (i, j) is 1 if the table i is joined with table j and 0 otherwise;

encoding one side of a diagonal axis of the adjacency matrix; and

training the join cardinality estimation model using the encoded adjacency matrix and the known join cardinality.

21. The computer-implemented method of claim 20 , wherein encoding the adjacency matrix includes condensing the adjacency matrix to a one dimensional vector for machine learning algorithms requiring a vector input.

22. A computer-implemented method comprising:

performing an inference using a trained join cardinality estimation model, the inference comprising a predicted join cardinality for a query, wherein performing the inference comprises:

generating an adjacency matrix encoding a join graph of the query;

encoding one side of a diagonal axis of the adjacency matrix;

inputting the encoded adjacency matrix into the join cardinality estimation model; and

receiving, as output, the predicted join cardinality; and

executing a query execution plan for the query using the predicted join cardinality;

wherein, when the query joins a set of n tables, the adjacency matrix can be defined as an n×n matrix, where a value in the matrix at a position (i, j) is 1 if the table i is joined with table j and 0 otherwise.

Assignments (1)

Continuity (1)

References Cited (26)