Optimizing table join ordering using graph theory prior to query optimization
US5758335A · kind A · utility
Assignee
Inventor
Key dates
| Filing date | Sep 27, 1996 |
| Grant date | May 26, 1998 |
| Priority date | — |
| Expiry date | Sep 27, 2016 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99942
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method for improving the efficiency of queries in relational database management systems that use the exhaustive method of query optimization. The join structure of the query is examined prior to query optimization and tables are ordered according to graph theory. The tables in the FROM clause of the query are then reordered before query optimization. The access plan is thus developed from an already near-optimal table ordering. As a result, the number of table permutations examined during query optimization is pruned, the time to examining large numbers of table order permutations is avoided, and the optimization cost is reduced.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.