ICEBERG QUERY EVALUATION IMPLEMENTING A COMPRESSED BITMAP INDEX

• US 20110270871A1
• Filed: 05/03/2010
• Published: 11/03/2011
• Est. Priority Date: 05/03/2010
• Status: Active Grant

• Current Assignee: ServiceNow Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Hsiao, Hui-l, He, Bin
• Granted Patent: US 8,626,770 B2
• Time in Patent Office: Days
• US Class Current: 707/769
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases

Abstract

Exemplary embodiments include an iceberg query method, including processing the iceberg query using a bitmap index having a plurality of bitmap vectors in a database, eliminating any of the plurality of bitmap vectors in the bitmap index that fails to meet a given condition thereby forming a subset of the plurality of bitmap vectors and aligning the vectors in the subset of the plurality of bitmap vectors in the bitmap index according to respective positions of the bitmap vectors in the subset of the plurality of bitmap vectors.

Claims

1. An iceberg query method, comprising:

processing the iceberg query using a bitmap index having a plurality of bitmap vectors in a database;

eliminating any of the plurality of bitmap vectors in the bitmap index that fails to meet a given condition thereby forming a subset of the plurality of bitmap vectors; and

aligning the vectors in the subset of the plurality of bitmap vectors in the bitmap index according to respective positions of the bitmap vectors in the subset of the plurality of bitmap vectors.

2. The method as claimed in claim 1 wherein the iceberg query is a GROUP BY query operation on a set of grouping attributes with a selection condition.

3. The method as claimed in claim 1 wherein the bitmap index vertically organizes a column in the database with the plurality of the bitmap vectors.

4. The method as claimed in claim 1 wherein the bitmap index is compressed.

5. The method as claimed in claim 1 wherein any vector of the plurality of bitmap vectors in the bitmap index that fails to meet a given condition is eliminated by dynamic pruning.

6. The method as claimed in claim 5 wherein the iceberg query is processed by a bitwise And operation.

7. The method as claimed in claim 6 further comprising in response to aligning the vectors in the subset of the plurality of bitmap vectors in the bitmap index, building a priority queue with the subset of the plurality of bitmap vectors, wherein each of the vectors of the subset of the plurality of bitmap vectors includes a priority based on a position of a first 1-bit of the vectors in the subset of the plurality of bitmap vectors.

8. The method as claimed in claim 7 further comprising shortening bitmap vector operations with a tracking pointer that points to respective locations of the 1-bit of each of the vectors in the subset of the plurality of bitmap vectors, wherein the tracking pointer is passed to the bitwise And operation.

9. The method as claimed in claim 7 further comprising reducing futile queue pushing via a global filter vector, the global filter vector recording 1-bit positions for bitmap vectors that have been eliminated, such that in response to finding a first 1-bit of a vector, determining if a corresponding aligned bitmap vector has been eliminated.

10. A computer program product for performing an iceberg query, the computer program product including instructions for causing a computer to implement a method, the method comprising:

processing the iceberg query using a bitmap index having a plurality of bitmap vectors in a database;

eliminating any of the plurality of bitmap vectors in the bitmap index that fails to meet a given condition thereby forming a subset of the plurality of bitmap vectors; and

aligning the vectors in the subset of the plurality of bitmap vectors in the bitmap index according to respective positions of the bitmap vectors in the subset of the plurality of bitmap vectors.

11. The computer program product as claimed in claim 10 wherein the iceberg query is a GROUP BY query operation on a set of grouping attributes with a selection condition.

12. The computer program product as claimed in claim 10 wherein the bitmap index vertically organizes a column in the database by the plurality of the bitmap vectors.

13. The computer program product as claimed in claim 10 wherein the bitmap index is compressed.

14. The computer program product as claimed in claim 10 wherein any vector in the bitmap index that fails to meet a given condition is eliminated by dynamic pruning.

15. The computer program product as claimed in claim 14 wherein the iceberg query is processed by a bitwise And operation.

16. The computer program product as claimed in claim 15 wherein the method further comprises in response to aligning the vectors in the subset of the plurality of bitmap vectors in the bitmap index, building a priority queue with the subset of the plurality of bitmap vectors, wherein each of the vectors of the subset of the plurality of bitmap vectors includes a priority based on a position of a first 1-bit of said each of the vectors in the subset of the plurality of bitmap vectors.

17. The computer program product as claimed in claim 16 wherein the method further comprises shortening bitmap vector operations with a tracking pointer that points to respective locations of the 1-bit of each of the vectors in the subset of the plurality of bitmap vectors, wherein the tracking pointer is passed to the bitwise And operation.

18. The computer program product as claimed in claim 16 wherein the method further comprises reducing futile queue pushing via a global filter vector, the global filter vector recording 1-bit positions for bitmap vectors that have been eliminated, such that in response to finding a first 1-bit of a vector, determining if a corresponding aligned bitmap vector has been eliminated.

19. An iceberg query method in a database, the method comprising:

processing a plurality of bitmap vectors vertically organized in a bitmap index by eliminating, by dynamic pruning, any of the bitmap vectors that fail to meet a given condition, leaving a subset of the plurality of bitmap vectors,

wherein the bitmap vectors are aligned according to a respective position of each of the bitmap vectors.

20. The method as claimed in claim 19, further comprising building a priority queue including the subset of the plurality of bitmap vectors, each of the vectors in the subset of the plurality of bitmap vectors including a priority based on a position of a 1-bit of each of the vectors in the subset of the plurality of bitmap vectors.

21. The method as claimed in claim 20 further comprising shortening bitmap vector operations by a tracking pointer that points to respective locations of the first 1-bit of each of the vectors in the subset of the plurality of bitmap vectors in the database.

22. The method as claimed in claim 20 further comprising reducing futile queue pushing by a global filter vector, which records 1-bit positions for bitmap vectors that have been eliminated.

23. A computer system configured to process an iceberg query in a database, the system comprising:

a memory element including the database that includes a plurality of bitmap vectors vertically organized in a bitmap index;

a processor communicatively coupled to the memory element and configured to;

eliminate, by dynamic pruning, any of the plurality of bitmap vectors in the bitmap index that fails to meet a given condition thereby forming a subset of the plurality of bitmap vectors; and

align the vectors in the subset of the plurality of bitmap vectors in the bitmap index according to a respective position of each of the bitmap vectors in the subset of the plurality of bitmap vectors.

24. The system as claimed in claim 23 wherein the processor is further configured to, in response to aligning the vectors in the subset of the plurality of bitmap vectors in the bitmap index, build a priority queue in the memory element with the subset of the plurality of bitmap vectors, wherein each of the vectors in the subset of the plurality of bitmap vectors includes a priority based on a position of a first 1-bit of each of the vectors in the subset of the plurality of bitmap vectors.

25. The system as claimed in claim 23 wherein the processor is further configured to perform at least one of the following:

i) shorten bitmap vector operations via a tracking pointer that points to a memory location in the memory element of the first 1-bit in the memory element of each of the vectors in the subset of the plurality of bitmap vectors, and ii) reduce futile queue pushing via a global filter vector, which records 1-bit positions for bitmap vectors that have been eliminated.