EP0875838A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Cardinality-based join ordering
Assignee: International Business Machines Corp
•
Filing: 1998-05-05
•
Granted: —
•
Expires: 2018-05-05
Abstract
Abstract Method and apparatus for optimizing the processing of join queries based on join cardinality. Embodiments implement the methods in query optimizers in relational database management systems. A good join order for a multiple join query is found with a metric that compares the relative merits of candidate join orders as a whole. Embodiments estimate the join selectivity of foreign key - foreign key joins, where both participating tables are foreign keys with respect to a primary or unique key of one primary table. A graph representation of a query is processed to estimate the join cardinality of an arbitrarily large number of filters and joins, including any combination of primary key - foreign key joins and foreign key - foreign key joins.
Inventors
- 👤 Murali M. Krishna
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-11-06 05:06
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24542; G06F16/24544; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932
Claims Analysis
Total Claims: 35
Claim 1
Independent Claim
54 words
A computer-implemented method for selecting a join order
for a query having two or more join operations, the
method comprising: computing a value of a Sigma metric for each join order
of a set of possible join orders; and selecting a join order for the query using the computed
values of the Sigma metric.
Claim 2
Dependent Claim
58 words
The method of claim 1, wherein the value of Sigma for a
join order is the sum over all joins in the join order of
an estimate of the cardinality of each join as it is
performed in the join order, where the cardinality of a
join is the number of tuples that will result from the
join.
Claim 3
Dependent Claim
47 words
The method of claim 1, further comprising: selecting a join order from among the set of possible
join orders; obtaining an estimate of the cardinality of each
component join in the selected join order; and calculating a value for Sigma by summing each of the
cardinality estimates.
Claim 4
Dependent Claim
22 words
The method of claim 3, wherein obtaining the cardinality
of each component join comprises: estimating the cardinality using a graph representation
method.
Claim 5
Dependent Claim
27 words
The method of claim 3, wherein obtaining the
cardinality of each component join comprises: retrieving a pre-computed value as the cardinality of one
of the component joins.
Claim 6
Independent Claim
80 words
The method of any preceding claim, further
comprising: identifying a component join as a foreign key - foreign
key join, being a join where the join predicate is in
substance S.fk = T.fk, where both S.fk and T.fk are
foreign keys with respect to one primary or alternative
key of one primary table R; and estimating the cardinality of the foreign key - foreign
key join as |S| . |T| / |R|, where |R| denotes the cardinality of table R.
Claim 7
Independent Claim
79 words
The method of any preceding claim, further
comprising: identifying a component join as a foreign key - foreign
key join, being a join where the join predicate is in
substance S.fk = T.fk, where both S.fk and T.fk are
foreign keys with respect to one primary or alternative
key of one primary table R; and estimating the join selectivity of the foreign key -
foreign key join as 1 / |R|, where |R| denotes the cardinality of table R.
Claim 8
Independent Claim
44 words
A method as claimed in any preceding claim, wherein the
step of computing a value of Sigma for a join order of
the set of possible join orders comprises the step of
selecting all possible join orders as the set of possible
join orders.
Claim 9
Independent Claim
41 words
A method as claimed in any preceding claim, wherein the
step of selecting a join order for the query using the
computed values of the Sigma metric comprises the step of
selecting the join order having a minimum value of Sigma.
Claim 10
Independent Claim
79 words
A method of estimating the join selectivity of a
foreign key - foreign key join, being a join where
the join predicate is in substance S.fk = T.fk,
where both S.fk and T.fk are foreign keys with
respect to one primary or alternative key of one
primary table R, the method comprising: calculating an estimate of the join selectivity of the
foreign key - foreign key join as 1 / |R|, where |R| denotes the cardinality of table R.
Claim 11
Independent Claim
57 words
A system for selecting a join order for a query
having two or more join operations, the system
comprising: means for computing a value of a Sigma metric for each
join order of a set of possible join orders; and means for selecting a join order for the query using the
computed values of the Sigma metric.
Claim 12
Dependent Claim
58 words
The system of claim 11, wherein the value of Sigma
for a join order is the sum over all joins in the
join order of an estimate of the cardinality of each
join as it is performed in the join order, where the
cardinality of a join is the number of tuples that
will result from the join.
Claim 13
Dependent Claim
53 words
The system of claim 11, further comprising: means for selecting a join order from among the set of
possible join orders; means for obtaining an estimate of the cardinality of
each component join in the selected join order; and means for calculating a value for Sigma by summing each
of the cardinality estimates.
Claim 14
Dependent Claim
27 words
The system of claim 13, wherein the means for
obtaining the cardinality of each component join
comprise: means for estimating the cardinality using a graph
representation method.
Claim 15
Dependent Claim
32 words
The system of claim 13, wherein the means for
obtaining the cardinality of each component join
comprise: means for retrieving a pre-computed value as the
cardinality of one of the component joins.
Claim 16
Independent Claim
88 words
The system of any of claims 11 to 15 , further
comprising: means for identifying a component join as a foreign key -
foreign key join, being a join where the join predicate
is in substance S.fk = T.fk, where both S.fk and T.fk are
foreign keys with respect to one primary or alternative
key of one primary table R; and means for estimating the cardinality of the foreign key -
foreign key join as |S| . |T| / |R|, where |R| denotes the cardinality of table R.
Claim 17
Independent Claim
84 words
The system of any of claims 11 to 16, further
comprising: means for identifying a component join as a foreign key -
foreign key join, being a join where the join predicate
is in substance S.fk = T.fk, where both S.fk and T.fk are
foreign keys with respect to one primary or alternative
key of one primary table R; and estimating the join selectivity of the foreign key -
foreign key join as 1 / |R| where |R| denotes the cardinality of table R.
Claim 18
Independent Claim
46 words
A system as claimed in any of claims 11 to 17, wherein
the means for computing a value of Sigma for each join
order of the set of possible join orders comprises means
for
selecting all possible join orders as the set of possible
join orders.
Claim 19
Independent Claim
42 words
A system as claimed in any of claims 11 to 18, the means
for selecting a join order for the query using the
computed values of the Sigma metric comprises means for
selecting the join order having a minimum value of Sigma.
Claim 20
Independent Claim
88 words
A system for estimating the join selectivity of a
foreign key - foreign key join, being a join where
the join predicate is in substance S.fk = T.fk,
where both S.fk and T.fk are foreign keys with
respect to one primary or alternate key of table R,
the system comprising: means for identifying a predicate as an Fk-Fk join; and
means for calculating an estimate of the join selectivity
of the foreign key - foreign key as 1 / |R|, where |R| denotes the cardinality of table R.
Claim 21
Dependent Claim
89 words
A computer-implemented method for estimating the
cardinality of a multiple-join query of relational
database tables, the method comprising the steps of: calculating data representing a join graph of the
multiple-join query, the join graph having a set of
vertices and a set of edges, the set of vertices
corresponding one-to-one with the tables in the multiple-join
query, the set of edges corresponding one-to-one
with the join predicates expressed and implied in the
query; and using the data representing the join graph to estimate
the cardinality of the multiple-join query.
Claim 22
Dependent Claim
35 words
The method of claim 21, further comprising: identifying all expressed and implied join predicates in
the multiple-join query; and providing a pair of vertices and a connecting edge in the
graph for each join predicate.
Claim 23
Independent Claim
70 words
The method of either of claims 21 to 22, wherein if
the predicate is parent key - foreign key, the
corresponding connecting edge is directed from the
primary table towards the foreign table, and
otherwise the edge is undirected, the method further
comprising: eliminating tail vertices from the graph to form a
reduced graph; and using the data representing the reduced graph to estimate
the cardinality of the multiple-join query.
Claim 24
Dependent Claim
60 words
The method of claim 23, wherein eliminating tail
vertices comprises: examining each vertex in a pass through the graph, and if
the vertex is a tail vertex, deleting the vertex and all
edges adjacent to the vertex; and if any tail vertices were deleted during a pass through
the graph, making another pass through the graph to
delete tail vertices.
Claim 25
Independent Claim
48 words
The method of any of claims 21 to 24, wherein
estimating the cardinality of the multiple-join
query comprises multiplying the selectivity of the
join represented by each edge, the cardinality of
the table represented by each vertex, and the
individual selectivity of the table represented by
each vertex.
Claim 26
Independent Claim
87 words
A system for estimating the cardinality of a
multiple-join query of relational database tables,
comprising: means for calculating data representing a join graph of
the multiple-join query, the join graph having a set of
vertices and a set of edges, the set of vertices
corresponding one-to-one with the tables in the multiple-join
query, the set of edges corresponding one-to-one
with the join predicates expressed and implied in the
query; and means for using the data representing the join graph to
estimate the cardinality of the multiple-join query.
Claim 27
Dependent Claim
39 words
The system of claim 26, further comprising: means for identifying all expressed and implied join
predicates in the multiple-join query; and means for providing a pair of vertices and a connecting
edge in the graph for each join predicate.
Claim 28
Independent Claim
75 words
The system of claim either of claims 26 or 27,
wherein if the predicate is parent key - foreign
key, the corresponding connecting edge is directed
from the primary table towards the foreign table,
and otherwise the edge is undirected, the system
further comprising: means for eliminating tail vertices from the graph to
form a reduced graph; and means for using the data representing the reduced graph
to estimate the cardinality of the multiple-join query.
Claim 29
Dependent Claim
39 words
The system of claim 28, wherein the means for
eliminating tail vertices comprises: means for examining each vertex in the graph, and if the
vertex is a tail vertex, deleting the vertex and all
edges adjacent to the vertex.
Claim 30
Independent Claim
54 words
The system of claim any of claims 26 to 29, wherein
the means for estimating the cardinality of the
multiple-join query comprise means for multiplying
the selectivity of the join represented by each
edge, the cardinality of the table represented by
each vertex, and the individual selectivity of the
table represented by each vertex.
Claim 31
Dependent Claim
48 words
A data processing method for processing a join query
comprising the steps of selecting a join order for
processing said query according to a method as
claimed in any of claims 1 to 10 or 21 to 25; and
processing said join query according to the selected
order.
Claim 32
Dependent Claim
42 words
A data processing system for processing a join query
comprising a system for selecting a join query as
claimed in any of claims 11 to 20 or 26 to 30; and
means for processing said join query according to
the selected order.
Claim 33
Dependent Claim
56 words
A computer program product for processing a join
query, said product comprising a storage medium
having embodied thereon computer program code means
for implementing a method as claimed in any of
claims 1 to 10, 21 to 25 or for implementing a
system as claimed in any of claims 11 to 20 or 26 to
30.
Claim 34
Dependent Claim
29 words
A method of processing a join query comprising the steps
of estimating a join selectivity according to claim 10; and
processing the join query using the estimated join
selectivity.
Claim 35
Dependent Claim
20 words
A data proccesing system for processing a join query
comprising means for implementing a method as claimed in
claim 34.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.