Indexes that are based on bitmap values and that use summary bitmap values

• US 20070050381A1
• Filed: 08/29/2005
• Published: 03/01/2007
• Est. Priority Date: 08/26/2005
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Hu, Ying, Sundara, Seema, Srinivasan, Jagannathan, Chorma, Timothy
• Granted Patent: US 7,774,346 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices

Abstract

A database management system that has bitmap values in which set bits in a representation of a bitstring specify a set of objects whose definitions are built into the database management system. The database management system further includes user-accessible operations on the bitmap values. The bitmap values are represented by means of a mapping specifier that specifies a range of the set of objects and a representation of a string of bits that has been mapped onto the set of object specified by the range specifier. Objects containing bitmap values may be indexed by means of an index tree that includes summary bitmap values.

Claims

1. An index tree, the index tree being stored in a medium accessible to a processor and being manipulatable by the processor, the index tree comprising:

a plurality of first nodes at a level of the tree, each node containing a bitmap value; and

a second node at a next higher level of the tree, the second node being a parent of the plurality of first nodes and containing a summary bitmap value that equals the result of an aggregation operation on bits of the bitmap values contained in the plurality of first nodes.

2. The index tree set forth in claim 1, wherein:

the aggregation operation is the logical OR of corresponding bits of the bitmap values contained in the plurality of first nodes.

3. The index tree set forth in claim 1, wherein:

the aggregation operation is the logical AND of corresponding bits of the bitmap values contained in the plurality of first nodes.

4. The index tree set forth in claim 1 wherein:

the second node is the root node of the index tree.

5. The index tree set forth in claim 1 wherein:

the index tree indexes a set of objects that contain bitmap values;

the first nodes are leaf nodes of the index tree; and

each first node'"'"'s bitmap value is a copy of a bitmap value contained in an object of the set thereof; and

each first node further specifies the object that contains the bitmap value whose copy is in the first node.

6. The index tree set forth in claim 5 wherein:

the aggregation operation is a logical OR operation; and

a set bit in a parent node'"'"'s summary bit map indicates that there exists at least one bitmap in the parent'"'"'s descendant leaf nodes in which the bit corresponding to the set bit is set.

7. The index tree set forth in claim 5 wherein:

the aggregation operation is a logical AND operation; and

when a bit is not set in the parent node'"'"'s summary bit map, the unset bit indicates that there is at least one bitmap in the parent'"'"'s descendant leaf nodes in which the bit corresponding to the unset bit in the parent node'"'"'s summary bit map is unset.

8. The index tree set forth in claim 5, wherein:

each object contains a scalar value in addition to the bitmap value; and

the index tree indexes a subset of the objects wherein all of the objects have equal scalar values.

9. The index tree set forth in claim 5, wherein:

each object contains a scalar value in addition to the bitmap value; and

the index tree indexes a subset of the objects wherein all of the objects have scalar values belonging to a given range of the scalar values.

10. The index tree set forth in claim 5, wherein:

the set of objects is rows in a table in a relational database system.

11. The index tree set forth in claim 10, wherein:

the index tree is an index object for the table in a relational database system.

12. The index tree set forth in claim 1, wherein:

the index tree is an index object in a relational database system.

13. The index tree set forth in claim 1, wherein:

the first nodes are leaf nodes of the index tree;

there is a plurality of next higher levels in the index tree; and

the summary bitmap value of a given node at a given higher level of the index tree equals the result of the aggregation operation on the bitmap values contained in all of the nodes that are descendants of the given node.

14. The index tree set forth in claim 13, wherein:

the next higher levels of the tree include a highest level containing the root node of the index tree.

15. A storage medium that is readable by a processor, the storage medium being characterized in that:

the storage medium contains the index tree set forth in claim 1.

16. A method of making an index tree, the index tree being stored in a medium accessible to a processor, the method being performed by the processor and the method comprising the steps of:

making a plurality of first nodes at a level of the tree, each first node containing a bitmap value; and

making a second node at a next higher level of the tree, the second node being a parent of the nodes in the plurality of first nodes and containing a summary bitmap value that equals the result of an aggregation operation on bits of the bitmap values contained in the plurality of first level nodes.

17. The method set forth in claim 16, wherein:

the aggregation operation is the logical OR of corresponding bits of the bitmap values contained in the plurality of first nodes

18. The method set forth in claim 16, wherein:

the aggregation operation is the logical AND of corresponding bits of the bitmap values contained in the plurality of first nodes.

19. The method of making an index tree set forth in claim 16 further comprising the step of:

dividing the plurality of first nodes into one or more disjunct sets thereof; and

in the step of making a second node, making a second node for each of the disjunct sets, the second node corresponding to a disjunct set being a parent of the nodes in the corresponding disjunct set.

20. The method set forth in claim 19, wherein:

beginning with the index tree'"'"'s leaf nodes as the first nodes, the steps of the method are repeated at each next higher level of the index tree until the parent node is the root node.

21. The method set forth in claim 16, wherein:

the index tree indexes a set of objects that contain bitmap values;

the first nodes are leaf nodes of the index tree; and

each first node'"'"'s bitmap value is a copy of a bitmap value contained in an object of the set thereof; and

each first node further specifies the object that contains the bitmap value whose copy is in the first node.

22. The method set forth in claim 21, wherein:

the objects of the set of objects contain a scalar value in addition to the bitmap value; and

the index tree indexes a subset of the objects wherein all of the objects have equal scalar values.

23. The method set forth in claim 21, wherein:

each object contains a scalar value in addition to the bitmap value; and

the index tree indexes a subset of the objects wherein all of the objects have scalar values belonging to a given range of the scalar values.

24. The method set forth in claim 21 wherein:

the processor is executing code for a relational database management system;

the set of objects is rows in a table in the relational database system; and

the index tree is an index object for the table in the relational database management system.

25. The method set forth in claim 16 wherein:

the processor is executing code for a relational database management system; and

the index tree is an index object in the relational database management system.

26. A storage medium that is readable by a processor, the storage medium being characterized in that:

the storage medium includes a program which, when executed by the processor, causes the processor to perform the steps set forth in claim 16.

27. In an index tree that is stored in a medium accessible to a processor and that employs summary bitmaps in the index tree'"'"'s internal nodes, a method of traversing the index tree comprising the steps of:

(1) in a parent node of the index tree, determining whether a given bit of the parent node'"'"'s summary bitmap is set to a value that indicates further traversal of the index tree;

(2) if the given bit is so set and the child nodes are internal nodes, performing step (1) in each of the parent'"'"'s child nodes; and

continuing to perform steps (1) and (2) as long as the given bit in the child node'"'"'s summary bit map is set to the value that indicates further traversal.

28. The method set forth in claim 27 wherein

the index tree'"'"'s leaf nodes include bitmaps which have bits corresponding to the bits of the summary bit maps;

and

the method further comprises the step performed when the child node is a leaf node of;

determining the value of the bit in the leaf node'"'"'s bitmap that corresponds to the given bit.

29. The method set forth in claim 28 wherein:

the leaf node'"'"'s bitmap represents a set of objects; and

the value of the bit in the leaf node'"'"'s bitmap indicates whether a given object is present in the set.

30. The method set forth in claim 29 wherein

the leaf node further includes an identifier for another object;

and the method further includes the step of;

depending on whether the given object is present in the set, returning the identifier for the other object.

31. The method set forth in claim 30 wherein

the summary bitmaps are made using a logical OR aggregation operation;

and

the step of determining determines whether the bit in the leaf node'"'"'s bitmap that corresponds to the given bit is set to indicate the presence of the given object in the set; and

when the bit in the leaf node'"'"'s bitmap is so set, the step of returning the identifier returns the identifier for the other object.

32. The method set forth in claim 30 wherein:

the summary bitmaps are made using a logical AND aggregation operation; and

the step of determining determines whether the bit in the leaf node'"'"'s bitmap that corresponds to the given bit is set to indicate the non-presence of the given object in the set; and

when the bit in the leaf node'"'"'s map is so set, the step of returning the identifier returns the identifier for the other object.

33. The method set forth in claim 30 wherein:

the index tree is an index object in a relational database management system that indexes a table in the relational database management system;

the other object is a row in the table indexed by the index tree; and

the bitmap in the leaf node is a copy of a bitmap that is included in the row.

34. A storage medium that is readable by a processor, the storage medium being characterized in that:

the storage medium contains code which, when executed by the processor, causes the processor to perform the method set forth in claim 27.