Optimizing an outer join operation using a bitmap index structure
US6957222B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Dec 31, 2001 |
| Grant date | Oct 18, 2005 |
| Priority date | — |
| Expiry date | Oct 11, 2023 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99942
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method, computer program and database system are disclosed for performing an outer join of at least a first table T1 and a second table T2. The join has join conditions. Each of the tables has an associated Star Map, S1 and S2, respectively. Each Star Map includes bitmap entries which have locations indexed by the hash of one or more values associated with one or more join key columns of its associated table. A bitmap entry in a Star Map, if set, indicates the presence of a row in its associated table that has entries in the one or more join key columns that together hash to the location of the bitmap entry. 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 set bitmap entries in a Star Map SJ where there is a corresponding set bitmap entry in S1 and a corresponding set bitmap entry in S2, b) selecting a row from table T1 and hashing the combined entries in the one or more join key columns of the selected T1 row to identify a bitmap entry in SJ, and c) if the identified bitmap entry in SJ is not set, projecting the selected T1 row with a NULL corresponding to data fro…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.