Memory structure and method for tuning a database statement using a join-tree data structure representation, including selectivity factors, of a master table and detail table
First Claim
1. A machine-executed method of creating a data structure in a memory device, for use in selecting an execution plan for a data access statement that specifies (i) a plurality of tables and (ii) a plurality of join conditions, each of said join conditions specifying a relationship between (x) a table that uses a key as a primary key, referred to as a master table, and (y) a table that uses a corresponding key as a foreign key, referred to as a detail table, said method comprising:
- (a) defining a set of nodes respectively representing the tables;
(b) defining a set of directional links between pairs of nodes each of which represents a master-detail relationship between a detail table and a corresponding master table;
(c) defining, in a memory device, a data structure, referred to as a join tree, comprising a representation of the nodes and their directional links;
(d) associating with the join tree a representation of a set of properties of the nodes and links, comprising;
(1) for each node, a set of zero or more selectivity factors, each selectivity factor indicating the expected fraction of rows in the table represented by the node that satisfy one or more logical conditions set forth in the data access statement;
(2) for each directional link associated with a detail table and a master table, (A) the ratio of (i) the number of distinct rows satisfying the join statement in the detail table A to (ii) the number of distinct rows satisfying the join statement in the master table, and (B) the probability that a row in the detail table will have a corresponding row in the master table.
2 Assignments
0 Petitions
Accused Products
Abstract
A method of constructing an aid to tuning of database statements comprises a data structure (stored in a memory on a computer system) which compactly represents that information which is needed about a database statement to determine the optimal series of operations (e.g., table data fetches) needed to execute the statement. The information includes the relationships between tables joined in the statement and the selectivities of logical conditions applied to rows in those tables.
-
Citations
15 Claims
-
1. A machine-executed method of creating a data structure in a memory device, for use in selecting an execution plan for a data access statement that specifies (i) a plurality of tables and (ii) a plurality of join conditions, each of said join conditions specifying a relationship between (x) a table that uses a key as a primary key, referred to as a master table, and (y) a table that uses a corresponding key as a foreign key, referred to as a detail table, said method comprising:
-
(a) defining a set of nodes respectively representing the tables; (b) defining a set of directional links between pairs of nodes each of which represents a master-detail relationship between a detail table and a corresponding master table; (c) defining, in a memory device, a data structure, referred to as a join tree, comprising a representation of the nodes and their directional links; (d) associating with the join tree a representation of a set of properties of the nodes and links, comprising; (1) for each node, a set of zero or more selectivity factors, each selectivity factor indicating the expected fraction of rows in the table represented by the node that satisfy one or more logical conditions set forth in the data access statement; (2) for each directional link associated with a detail table and a master table, (A) the ratio of (i) the number of distinct rows satisfying the join statement in the detail table A to (ii) the number of distinct rows satisfying the join statement in the master table, and (B) the probability that a row in the detail table will have a corresponding row in the master table. - View Dependent Claims (2, 3, 5, 6)
-
-
4. A machine-executed method of creating a data structure in a memory device for use in selecting an execution plan for an SQL statement that specifies (i) a plurality of tables and (ii) a plurality of join conditions each of which specifies a relationship between (x) a table that uses a key as a primary key, referred to as a master table, and (y) a table that uses a corresponding key as a foreign key, referred to as a detail table, said method comprising:
-
(a) defining a set of nodes respectively representing the tables; (b) defining a set of directional links between pairs of nodes each of which represents a master-detail relationship between a detail table and a corresponding master table; (c) defining, in said memory device, a data structure, referred to as a join tree, comprising a representation of the nodes and their directional links; (d) associating with the join tree a representation of a set of properties of the nodes and links, comprising; (1) for each node, a set of zero or more filters, each filter indicating the expected fraction of rows in the table represented by the node that satisfy one or more logical conditions set forth in the SQL statement; (2) for each directional link associated with a detail table and a master table, (A) the ratio of (i) the number of distinct rows satisfying the join statement in the detail table A to (ii) the number of distinct rows satisfying the join statement in the master table, and (B) the probability that a row in the detail table will have a corresponding row in the master table.
-
-
7. A machine-readable memory device encoding a map of a data access statement, said data access statement specifying (i) a plurality of tables and (ii) a plurality of join conditions, each of said join conditions specifying a relationship between (x) a table that uses a key as a primary key, referred to as a master table, and (y) a table that uses a corresponding key as a foreign key, referred to as a detail table, said map comprising respective representations of:
-
(a) a set of nodes respectively representing the tables; (b) a set of directional links between pairs of nodes, each directional link representing a master-detail relationship between a detail table and a corresponding master table; (c) a set of properties of the nodes and links, comprising; (1) for each node, a set of zero or more selectivity factors, each selectivity factor indicating the expected fraction of rows in the table represented by the node that satisfy one or more logical conditions set forth in the data access statement; (2) for each directional link associated with a detail table and a master table, (A) the ratio of (i) the number of distinct rows satisfying the join statement in the detail table A to (ii) the number of distinct rows satisfying the join statement in the master table, and (B) the probability that a row in the detail table will have a corresponding row in the master table. - View Dependent Claims (8, 9, 11, 12, 13, 14)
-
-
10. A machine-readable memory device encoding a map of an SQL statement, said SQL statement specifying (i) a plurality of tables and (ii) a plurality of join conditions, each of said join conditions specifying a relationship between (x) a table that uses a key as a primary key, referred to as a master table, and (y) a table that uses a corresponding key as a foreign key, referred to as a detail table, said map comprising respective representations of:
-
(a) a set of nodes respectively representing the tables; (b) a set of directional links between pairs of nodes, each directional link representing a master-detail relationship between a detail table and a corresponding master table; (d) a set of properties of the nodes and links, comprising; (1) for each node, a set of zero or more filters, each filter indicating the expected fraction of rows in the table represented by the node that satisfy one or more logical conditions set forth in the SQL statement; (2) for each directional link associated with a detail table and a master table, (A) the ratio of (i) the number of distinct rows satisfying the join statement in the detail table A to (ii) the number of distinct rows satisfying the join statement in the master table, and (B) the probability that a row in the detail table will have a corresponding row in the master table. - View Dependent Claims (15)
-
Specification