In-memory bitmap for column store operations

Patent metadata

Field	Value
Publication number	US-9268807-B2
Application number	US-201313944196-A
Country	US
Kind code	B2
Filing date	Jul 17, 2013
Priority date	Jul 17, 2013
Publication date	Feb 23, 2016
Grant date	Feb 23, 2016

Abstract

Disclosed herein are system, method, and computer program product embodiments for implementing a bitmap for a column store database. An embodiment operates by creating, by at least one processor, a bitmap identifying rows in a column store database. The bitmap may include a list of bit chunks, a bit chunk including an offset being a natural number indicating a chunk size, and a bit specification including one of an ordered row id list, a contiguous row id sequence, and a bit vector. In addition, the embodiment includes performing database operations using the bitmap.

First claim

What is claimed is:

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.

Assignees

• Blanco Rolando
• Goel Anil Kumar
• Andrei Mihnea
• Sybase Inc

Inventors

• Blanco Rolando
• Goel Anil Kumar
• Andrei Mihnea

Classifications

• G06F16/2237 Primary

  Vectors, bitmaps or matrices · CPC title

• G06F16/254

  Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses · CPC title

• G06F16/2228

  Indexing structures · CPC title

• G06F16/10

  File systems; File servers · CPC title

• G06F16/9027

  Trees · CPC title