Outerjoin and antijoin reordering using extended eligibility lists
US6665663B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Mar 15, 2001 |
| Grant date | Dec 16, 2003 |
| Priority date | — |
| Expiry date | May 9, 2022 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99934
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
An optimization technique that reorders outerjoins and antijoins with inner joins in a bottom-up optimizer of a relational database management system (RDBMS).Each join predicate is associated with a normal eligibility list (NEL) that includes tables that are referenced in the join predicate and an extended eligibility list (EEL) that includes additional tables that are referenced in conflicting join predicates. An EEL includes all the tables needed by a predicate to preserve the semantics of the original query. During join enumeration, the optimizer determines whether a join predicate's EEL is a subset of all the tables in two subplans to be merged, i.e., whose EEL is covered. If so, the two subplans are combined using the join predicate. Otherwise, the two subplans cannot be joined. Two approaches are used to reordering: without compensation and with compensation. The “without compensation” approach only allows join reorderings that are valid under associative rules. Thus, the optimizer will not combine subplans using a join predicate whose EEL is not covered. The “with compensation” approach allows two subplans to be combined using the join predicate, when…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.