Bitmap filter, a method of generating the same, and a method of using a bitmap filter to perform a join

A computer-implemented method of using an extended bit vector to filter a data source as part of a join operation, wherein the data source comprises a plurality of entries and each entry comprises an identifier and the extended bit vector comprises a) a bitmap filter corresponding to a filter parameter and configured to implement one-to-one mapping of an identifier of an entry of the data source to a bit location within the bitmap filter and b) a plurality of counters of bits set in the bitmap filter, wherein each bit location of the bitmap filter is associated with one of the plurality of counters, the method comprising:

• associating a set bit of the bitmap filter with an entry of thee data source that comprises an identifier that matches the filter parameter, wherein the set bit is located at a bit location within the bitmap filter;
• determining a row identifier of row in another data source that corresponds to the identifier based on a count of a counter associated with the bit location of the set bit, wherein the count of the counter is a sum of a number of set bits in bit locations in the bitmap filter that are between the bit location of the set bit associated with the entry of the data source and a bit location in the bitmap filter corresponding to a different, known, row identifier of a different row in the another data source;
• interrogating the row of the another data source corresponding to the determined row identifier to obtain information defining the identifier that matches the filter parameter;
• and
• importing the information from the associated row of the another data source into a result table.

A computer-implemented method of using an extended bit vector to filter a data source as part of a join operation using parallel processing, wherein the data source comprises a plurality of entries and each entry comprises an identifier and the extended bit vector comprises a) a bitmap filter corresponding to a filter parameter and configured to implement one-to-one mapping of an identifier of an entry of the data source to a bit location within the bitmap filter and b) a plurality of counters, C1-Cn, of bits set in the bitmap filter, wherein each bit location of the bitmap filter is associated with one of the plurality of counters, C1-Cn, the method comprising:

• storing the bitmap filter in a first register, Reg E;
• storing a plurality of identifiers of a corresponding plurality of entries of the data source in a second register, Reg B1, wherein each identifier has a numerical value and the numerical values of the plurality of identifiers are shifted based on a minimum identifier value defined by the bitmap filter;
• applying a first single instruction multiple data, SIMD, instruction to the second register, Reg B1, wherein the first SIMD instruction is applied in parallel to all the identifiers stored by the second register;
• generating, based on the application of the first SIMD instruction, a third register, Reg B2, wherein the third register, Reg B2, comprises a plurality of byte addresses of the bitmap filter corresponding to the second register, Reg B1;
• applying, a second SIMD instruction to the first register, Reg E, and the third register, Reg B2, wherein the second SIMD instruction is applied in parallel to all the identifiers stored by the first the third register;
• generating, based on the second SIMD instruction, a fourth register, Reg C, wherein the fourth register, Reg C, comprises a version of the first register, Reg E, corresponding to the byte addresses of Reg B2;
• applying, a third SIMD instruction to the second register, Reg B1, and the fourth register, Reg C, wherein the third SIMD instruction is applied in parallel to all the identifiers stored by the fourth register;
• generating, based on the third SIMD instruction, a fifth register, Reg D, wherein the fifth register, Reg D, identifies those identifiers of the second register, Reg B1, that are a match to the bitmap filter.