Optimizing an exclusion join operation using a bitmap index structure
US6957210B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Dec 31, 2001 |
| Grant date | Oct 18, 2005 |
| Priority date | — |
| Expiry date | Mar 6, 2023 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99932
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method, computer program and database system are disclosed for performing an exclusion join of at least a first table T1 and a second table T2, where each of the tables has an associated Star Map, S1 and S2, respectively. Each Star Map includes bitmap entries having locations indexed by the hash of one or more values associated with one or more join key columns of its associated table. The method, computer program, and database system include a) performing one or more Boolean operations using the bitmap entries of the Star Maps S1 and S2 to produce bitmap entries in a Star Map SJ where there is a corresponding set bitmap entry in S1 and no corresponding set bitmap entry in S2; b) using SJ to identify qualifying rows from the first table T1; and c) providing the qualifying rows as an exclusion join result.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.