Multiplication-based method for stitching results of predicate evaluation in column stores

A method comprising:

• querying a plurality of column values with a predicate;
• generating an indicator bit for each of the plurality of column values based on the predicate and joining a result of querying each of the plurality of column values with the respective indicator bit;
• generating a column-major linear bitmap from the result of querying each of the plurality of column values and respective indicator bits;
• determining an offset between adjacent indicator bits in the column-major linear bitmap;
• multiplying, via a processor, the column-major linear bitmap with a multiplier to shift the indicator bits into consecutive positions in the linear bitmap;
• and
• performing a bitwise AND operation on the multiplied linear bitmap and a second multiplied linear bitmap to combine predicate evaluations from the plurality of column values and a second plurality of column values.

The method claim of 8, for a value of the offset k that is greater than or equal to 4 and less than 8, further comprising:

• multiplying the linear bitmap with the multiplier M1=1+2j+22j+ . . . 2(k−1)j;
• performing the bitwise AND of the linear bitmap with the mask S1=264−264−k+264−n−264−n−k+264−2n−264−2n−k+264−3n−264−3n−k+ . . . (until exponents are less than 0);
• multiplying the linear bitmap with a second multiplier M2=1+2m+22m+ . . . 2(ceil(64/n−1)m;
• performing a bitwise AND of the linear bitmap with a second mask S2=264−2(floor(64/k));
• and
• where j=k−1, m=k2−k, and n=k2.

The method claim of 8, for a value of the offset k that is equal to 3, further comprising:

• multiplying the linear bitmap with the multiplier M1=1+2j+22j+ . . . 2(k−1)j;
• performing the bitwise AND of the linear bitmap with the mask S1=264−264−k+264−n−264−n−k+264−2n−264−2n−k+264−3n−264−3n−k+ . . . (until exponents are less than 0);
• multiplying the linear bitmap with a second multiplier M2=1+2m+22m+ . . . 2(ceil(64/n−1)m;
• performing a bitwise AND of the linear bitmap with a second mask S2=264−2(floor(64/k));
• performing a bitwise AND of the linear bitmap with a third mask S3=264−264−9+264−27−264−36+264−54−264−63;
• multiplying the linear bitmap with a third multiplier M3=1+218+236;
• and
• where j=k−1, m=k2−k, and n=k2.

The method claim of 8, for a value of the offset k that is equal to 2, further comprising:

• multiplying the linear bitmap with the multiplier M1=1+2j+22j+ . . . 2(k−1)j;
• performing the bitwise AND of the linear bitmap with the mask S1=264−264−k+264−n−264−n−k+264−2n−264−2n−k+264−3n−264−3n−k+ . . . (until exponents are less than 0);
• multiplying the linear bitmap with a second multiplier M2=1+2m+22m+ . . . 2(ceil(64/n−1)m;
• performing a bitwise AND of the linear bitmap with a second mask S2=264−2(floor(64/k));
• performing the operation (((((linear bitmap & S3)*M3) & S4)*M4) & S5)*M5);
• and
• where S3=0xF0F0F0F0F0F0F0F0, M3=17, S4=0xFF00FF00FF00FF00, M4=257, S5=0xFFFF0000FFFF0000ull, M5=65537, j=k−1, m=k2−k, and n=k2.

A system comprising:

• a processor;
• a column unifier configured via the processor to query a plurality of column values with a predicate, and generate an indicator bit for each of the plurality of column values based on the predicate and joining a result of querying each of the plurality of column values with the respective indicator bit;
• a bitmap generator configured to generate a column-major linear bitmap from the result of querying each of the plurality of column values and respective indicator bits;
• wherein the column unifier is further configured to determine an offset between adjacent indicator bits in the column-major linear bitmap;
• a converter configured to multiply the column-major linear bitmap with a multiplier to shift the indicator bits into consecutive positions in the linear bitmap;
• and
• a bitwise operator to perform a bitwise AND operation on the multiplied linear bitmap and a second multiplied linear bitmap to combine predicate evaluations from the plurality of column values and a second plurality of column values.