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 from table T2. If d) the identified bitmap entry in SJ is set, performing the following: d1) if no row in T2 satisfies the join conditions and has entries in its one or more join key columns that together hash to the location of the identified set bitmap entry in SJ, projecting the selected T1 row and a NULL corresponding to data from table T2, d2) otherwise, for each row from T2 that satisfies the join condition and has entries in its one or more join key columns that together hash to the location of the identified set bitmap entry in SJ, projecting the selected T1 row with data from the row from T2, and e) repeating b)-d) for all rows in T1.