In-memory bitmap for column store operations

1. A method, comprising:

creating, by at least one processor, a bitmap identifying rows in an in-memory column-store database, the bitmap comprising a list of bit chunks, a bit chunk comprising an offset comprising a natural number indicating a chunk size, and a bit specification comprising one of an ordered row id list, a contiguous row id sequence, and a bit vector;

modifying a row id of the bitmap;

determining a bit specification of a bit chunk in the list of bit chunks;

converting the bit specification of the bit chunk from a first type to a second type to reduce memory used to represent the bitmap, wherein the first type is different than the second type and the conversion is based on the determined bit specification and the modified row id; and

performing database operations using the bitmap on the in-memory column-store database.

2. The method of claim 1 , the bitmap further comprising:

a first chunk reference indicating a first bit chunk in the list of bit chunks; and

a last chunk reference indicating a last bit chunk in the list of bit chunks.

3. The method of claim 1 , the bit specification further comprising:

a first row id indicating a first bit in the bit specification; and

a last row id indicating a last bit in the bit specification.

4. The method of claim 1 , the bit chunk further comprising:

a next chunk reference indicating a next bit chunk in the list of bit chunks; and

a previous chunk reference indicating a previous chunk in the list of bit chunks.

5. The method of claim 1 , wherein the modifying comprises:

adding a new row id to the bitmap.

6. The method of claim 1 , wherein the modifying comprises:

removing an existing row id from the bitmap.

7. The method of claim 1 , wherein the modifying comprises:

appending a new row id to the bitmap by adding the new row id to a last bit chunk in the bitmap.

8. The method of claim 1 , the modifying further comprising:

appending a new row id to the bitmap by adding the new row id to a new bit chunk added after a last bit chunk of the bitmap; and

coalescing the new bit chunk and the last bit chunk of the bitmap into a single new last bit chunk.

9. The method of claim 1 , wherein the chunk size is divisible by a number of bits in a machine word.

10. The method of claim 1 , the database operations comprising insertion of rows, deletion of rows, updating of rows, selection of rows, and determination of rows visible to a transaction.

11. A system, comprising:

a memory; and

at least one processor coupled to the memory and configured to:

create a bitmap identifying rows in an in-memory column-store database, the bitmap comprising a list of bit chunks, a bit chunk comprising an offset comprising a natural number indicating a chunk size, and a bit specification comprising one of an ordered row id list, a contiguous row id sequence, and a bit vector;

modify a row id of the bitmap;

determine a bit specification of a bit chunk in the list of bit chunks;

convert the bit specification of the bit chunk from a first type to a second type to reduce memory used to represent the bitmap, wherein the first type is different than the second type and the conversion is based on the determined bit specification and the modified row id; and

perform database operations using the bitmap on the in-memory column-store database.

12. The system of claim 11 , the bitmap further comprising:

a first chunk reference indicating a first bit chunk in the list of bit chunks; and

a last chunk reference indicating a last bit chunk in the list of bit chunks.

13. The system of claim 11 , the bit specification further comprising:

a first row id indicating a first bit in the bit specification; and

a last row id indicating a last bit in the bit specification.

14. The system of claim 11 , the bit chunk further comprising:

a next chunk reference indicating a next bit chunk in the list of bit chunks; and

a previous chunk reference indicating a previous chunk in the list of bit chunks.

15. The system of claim 11 , the at least one processor further configured to:

add a new row id to the bitmap.

16. The system of claim 11 , the at least one processor further configured to:

remove an existing row id from the bitmap.

17. The system of claim 11 , the at least one processor further configured to:

append a new row id to the bitmap by adding the new row id to a last bit chunk in the bitmap.

18. The system of claim 11 , the at least one processor further configured to:

append a new row id to the bitmap by adding the new row id to a new bit chunk added after a last bit chunk of the bitmap; and

coalesce the new bit chunk and the last bit chunk of the bitmap into a single new last bit chunk.

19. The system of claim 11 , wherein the chunk size is divisible by a number of bits in a machine word.

20. A tangible computer-readable device having instructions stored thereon that, when executed by at least one computing device, causes the at least one computing device to perform operations comprising:

creating a bitmap identifying rows in an in-memory column-store database, the bitmap comprising a list of bit chunks, a bit chunk comprising an offset comprising a natural number indicating a chunk size, and a bit specification comprising one of an ordered row id list, a contiguous row id sequence, and a bit vector;

modifying a row id of the bitmap;

determining a bit specification of a bit chunk in the list of bit chunks;

converting the bit specification of the bit chunk from a first type to a second type to reduce memory used to represent the bitmap, wherein the first type is different than the second type and the conversion is based on the determined bit specification and the modified row id; and

performing database operations using the bitmap on the in-memory column-store database.