Optimizing an equi-join operation using a bitmap index structure
US7092954B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Dec 31, 2001 |
| Grant date | Aug 15, 2006 |
| Priority date | — |
| Expiry date | May 26, 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 joining a plurality of tables T1 through TN, where each of the tables has an associated Star Map, S1 through SN, 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. 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 includes a) performing a Boolean operation using the bitmap entries of the Star Maps S1 through SN to produce a join Star Map SJ, b) using SJ to select rows from the tables T1 through TN, and c) joining the resulting rows to produce a join result.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.