Join index bitmap for non-equality query conditions

1. A data store system comprising:

an array of persistent storage devices configured to store a plurality of data store tables;

a processor in communication with the array of persistent storage devices, the processor configured to;

receive a query containing a non-equality join condition on a first column, from a first data store table and a second column on a second data store fable; and

generate a bitmap based on the non-equality join condition, wherein the bitmap indicates respective matches match or non-match between the first column and second column in accordance with the non-equality join condition, wherein each bit represents a result of the non-equality join condition applied to the first column and the second column;

compress each column of the bitmap to generate a compressed bit string, wherein, to compress each column of the bitmap, the processor is further configured to:

select each column of the bitmap;

segment bits in each selected column of the bitmap into segments of a predetermined size;

determine of content of each segment;

compare each segment to a next segment;

in response to content of a segment being different than content of the next segment compress the segment separately from the next segment; and

in response to determination, of two or more contiguous segments contain same content, compress the two or more contiguous segments together;

generate at least one data structure, wherein the at least one data structure comprises a row identifier of the first column associated with bit string and the compressed bit string; and

store said each compressed column of the bitmap, wherein the stored compressed column of the bitmap is used when the non-equality join condition is present in another received query.

2. The data store system of claim 1 , wherein the processor is further configured to

generate at least one data structure, wherein the at least one data structure comprises a row identifier of the first column associated with the bit string and the compressed bit string.

3. The data store system of claim 2 , wherein the processor is further configured to generate an index table, wherein the index table comprises:

an index indicative of a row position of each column value of the second table in the bitmap; and

a corresponding row identifier of each row of the second column corresponding to a respective index.

4. The data store system of claim 3 , wherein the processor is further configured to:

determine a row of the second table has been deleted; and

set the row identifier to an invalid value to indicate the row of the second table has been deleted.

5. The data store system of claim 2 , wherein the processor is further configured to:

determine a row of the first table has been deleted; and

delete a compressed bit string and row identifier in an associated data structure that corresponds to the row of the first table.

6. The data store system of claim 1 , wherein the processor is further configured to generate a plurality of pad bits associated with each bit string, wherein the pad bits allow the compressed bit string to be expanded, and wherein the pad bits are stored in a data structure corresponding to the associated bit string.

7. The data store system of claim 2 , wherein the processor is further configured to:

determine that a row as been inserted into the first table;

identify respective matches between the inserted row of the first column and second column in accordance with the non-equality join condition; and

generate a bit string indicative of any matches identified between the inserted row of the first column and the second column in accordance with the non-equality join condition.

8. A method comprising;

receiving, by a processor, a query containing a non-equality join condition on a first column from a first data store table and a second column on a second data store table; and

generating, by the processor, a bitmap based on the non-equality join condition, wherein the bitmap indicates respective matches between the first column and second column in accordance with the non-equality join condition, wherein the bitmap is implemented when the non-equality join condition is present in another received query;

compressing, by the processor, each column of the bitmap to generate a compressed bit string, wherein the compressing comprises:

selecting each column of the bitmap;

segmenting bits in each selected column of the bitmap into segments of a predetermined size;

determining of content of each segment;

comparing each segment to a next segment;

in response to content of a segment being different than content of the next segment, compressing the segment separately from the next segment; and

in response to determination of two or more contiguous segments contain same content, compressing the two or more contiguous segments together; and

storing said each compressed column of the bitmap, wherein the stored compressed column of the bitmap is used when the non-equality join condition is present in another received query.

9. The method of claim 8 , further comprising

generating at least one data structure, wherein the at least one data structure comprises a row identifier of the first column associated with the bit string and the compressed bit string.

10. The method of claim 9 , further comprising generating an index table, wherein the index table comprises an index indicative of a row position of each column value of the second table in the bitmap and a corresponding row identifier of each row of the second column corresponding to a respective index.

11. The method of claim 10 , further comprising:

determining a row of the second table has been deleted; and

setting the row identifier in the index table associated with the row to an invalid value to indicate the row of the second table has been deleted.

12. The method of claim 9 , further comprising:

determining that a row as been inserted into the first table;

identifying respective matches between the inserted row of the first column and second column in accordance with the non-equality join condition; and

generating a bit string indicative of any matches identified between the inserted row of the first column and the second column in accordance with the non-equality join condition.

13. The method of claim 8 , further comprising generating a plurality of pad bits associated with each bit string, wherein the pad bits allow the compressed bit string to be expanded, and wherein the pad bits are stored in a data structure corresponding to the associated bit string.

14. The method of claim 8 , further comprising:

determining a row of the first table has been deleted; and

deleting a compressed bit string and row identifier in an associated data structure that corresponds to the row of the first table.

15. A non-transitory computer-readable medium encoded with a plurality of instructions executable by a processor, the plurality of instructions comprising:

instructions to receive a query containing a non-equality join condition on a first column from a first data store table and a second column on a second data store table; and

instructions to generate a bitmap based on the non-equality join condition, wherein the bitmap indicates respective matches between the first column and second column in accordance with the non-equality join condition, wherein the bitmap maybe is used each time the non-equality join condition is present in another received query;

instructions to compress each column of the bitmap to generate a compressed bit string, wherein the instructions to compress comprise:

instructions to select each column of the bitmap;

instructions to segment bits in each selected column of the bitmap into segments of a predetermined size;

instructions to determine of content of each segment;

instructions to compare each segment to a next segment;

in response to content of a segment being different than content of the next segment, instructions to compress the segment separately from the next segment; and

in response to determination of two or more contiguous segments contain same content, instructions to compress the two or more continuous segments together; and

instructions to store said each compressed column of the bitmap, wherein the stored compressed column of the bitmap is used when the non-equality join condition is present in another received query.

16. The non-transitory computer-readable medium of claim 15 , wherein the plurality of instructions further comprises instructions to generate at least one data structure, wherein the at least one data structure comprises a row identifier of the first column associated with the bit siring and the compressed bit string.

17. The non-transitory computer-readable medium of claim 16 , wherein the plurality of instructions further comprises instructions to generate an index table, wherein the index table comprises an index indicative of a row position of each column value of the second table in the bitmap and a corresponding row identifier of each row of the second column corresponding to a respective index.

18. The non-transitory computer-readable medium of claim 15 , wherein the plurality of instructions further comprises: instructions to determine a row of the second table has been deleted: and instructions to set the row identifier in the index table to an invalid value to indicate the row of the second table has been deleted.

19. The non-transitory computer-readable medium of claim 15 , wherein the plurality of instructions further comprises instructions to generate a plurality of pad bits associated with each bit string, wherein the pad bits allow the compressed bit string to be expanded, and wherein the pad bits are stored in a data structure corresponding to the associated bit string.

20. The non-transitory computer-readable medium of claim 15 , wherein the plurality of instructions further comprises:

instructions to determine a row of the first table has been deleted; and

instructions to delete a compressed bit string and row identifier in an associated data structure that corresponds to the row of the first table.