Cardinality-based join ordering
US6138111A · kind A · utility
Assignee
Inventor
Key dates
| Filing date | May 2, 1997 |
| Grant date | Oct 24, 2000 |
| Priority date | — |
| Expiry date | May 2, 2017 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99932
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.