Bitmap segmentation

Details Bitmap segmentation Bitmap segmentation

1999-05-13

2001-02-27

Alam, Hosain T. (Department: 2771)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000, C707S793000, C707S793000

Reexamination Certificate

active

06195656

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to databases, and more particularly, to the maintenance and storage of bitmap indexes used to access data stored in databases.
BACKGROUND OF THE INVENTION
A bitmap index is an index that includes a set of bitmaps that can be used to efficiently process queries on a body of data associated with the bitmap index. In the context of bitmap indexes, a bitmap is a series of bits that indicate which of the records stored in the body of data satisfy a particular criteria. Each record in the body of data has a corresponding bit in the bitmap. Each bit in the bitmap serves as a flag to indicate whether the record that corresponds to the bit satisfies the criteria associated with the bitmap.
Typically, the criteria associated with a bitmap is whether the corresponding records contain a particular key value. In the bitmap for a given key value, all records that contain the key value will have their corresponding bits set to 1 while all other bits are set to 0. A collection of bitmaps for the key values that occur in the data records can be used to index the data records. In order to retrieve the data records with a given key value, the bitmap for that key value is retrieved from the index and, for each bit set to 1 in the bitmap, the corresponding data record is retrieved. The records that correspond to bits are located based on a mapping function between bit positions and data records.
For example,
FIG. 1
illustrates a table
100
that contains ten rows, where each row contains a name and a gender indicator. Rows
2
,
3
,
4
,
5
,
6
,
8
,
9
and
10
contain male gender indictors. Rows
1
and
7
contain female gender indicators. Therefore, the bitmap of table
100
for the criteria “GENDER=MALE” would be 0111110111, where the “1”s in positions
2
-
6
and
8
-
10
indicate that the second through sixth and eighth through tenth rows of table
100
satisfy the “GENDER=MALE” criteria, and the zeros in the first and seventh positions indicate that first and seventh rows in table
100
do not satisfy the “GENDER=MALE” criteria.
When retrieving data using a bitmap index, several logical retrieval conditions may be combined using Boolean operations on the appropriate bitmaps. For example, if the data that is to be retrieved is subject to the conditions that key
1
=<val
1
> and key
2
=<val
2
>, a bitwise AND of the bitmaps for key values <val
1
> and <val
2
> can be performed to generate a bitmap that indicates the data items that match both conditions.
Database systems that support bitmap indexes treat, store and maintain each bitmap as an atomic contiguous data item. Thus, all locking, logging and manipulating of a bitmap is performed for the bitmap as a unit. Unfortunately, this conventional use of bitmap indexes has some significant drawbacks.
For example, when a change needs to be made to a bit in a bitmap, a lock on the bitmap is obtained before updating the bitmap so that other processes cannot concurrently update the bitmap in an inconsistent manner. In a system where concurrent inserts, deletes and/or updates of the data are taking place and some form of locking mechanism is used to ensure consistency, locking an entire bitmap prevents concurrent execution of transactions that are affecting different bits within the same logical bitmap.
Many databases employ a consistency model that requires changes to the data to be logged to disk. When logging is used with bitmap indexes, the entire bitmap is recorded in the log as an atomic unit for each change made to the bitmap. Such logging involves considerable processing time and disk-I/O, especially when large bitmaps are involved.
Further, treating a bitmap as an atomic unit may require significant disk-I/O and memory usage. If an entire bitmap has to be retrieved as an atomic unit from the bitmap index, the cost in terms of disk-I/O and memory can be substantial even when information from only a small part of the bitmap is actually be needed.
During information retrieval operations, the information in large portions of a bitmap may not be relevant. For example, if an AND operation is being performed between two bitmaps and the first bitmap contains a long sequence of zeros, the information contained in the portion of the second bitmap that corresponds to those zeros is irrelevant, since the result of an AND operation with a zero will always be zero. However, because bitmaps are stored and treated as atomic data items, all bits within both bitmaps will be loaded and processed.
Based on the foregoing, it is clearly desirable to provide a database system in which bitmap indexes may be used with less resource consumption than is currently experienced. It is further desirable to reduce the overhead involved in logging changes made to bitmaps within a bitmap index. It is further desirable to increase the concurrency of systems in which multiple transactions perform operations which affect or use the same bitmap.
SUMMARY OF THE INVENTION
A method and apparatus are provided for segmenting the bitmaps stored in a bitmap index.
According to one aspect of the invention, a bitmap is represented by a plurality of bitmap segments. Each bitmap segment corresponds to a range of records within the body of data associated with the bitmap index. Rather than treating each bitmap as an atomic unit, the database system is able to manipulate each bitmap segment independently relative to the other bitmap segments.
There may be gaps that exist between the ranges represented by a set of bitmap segments. Thus, if the body of data associated with the bitmap index does not contain records that fall into a particular range, the bitmap index does not store bitmap segments to cover that range of non-existent records. Similarly, the bitmap index does not have to store bitmap segments to cover ranges of records that would all be represented by the same bit value.
According to one aspect of the invention, each bitmap segment is protected by its own lock, thereby allowing multiple bitmap segments associated with the same criteria to be accessed and updated simultaneously. In addition, when a bitmap segment is updated, a log is generated that indicates only the new version of that bitmap segment, rather than the entire bitmap.


REFERENCES:
patent: 5442715 (1995-08-01), Gaborski et al.
patent: 5465322 (1995-11-01), Hsu et al.
patent: 5495608 (1996-02-01), Antoshenkov
patent: 5502804 (1996-03-01), Butterfield et al.
patent: 5504411 (1996-04-01), Banton et al.
patent: 5552898 (1996-09-01), Deschuytere
patent: 5604850 (1997-02-01), Whitmer
patent: 5642473 (1997-06-01), Klotz, Jr.
patent: 5649181 (1997-07-01), French et al.
patent: 5664172 (1997-09-01), Antotoshenkov
patent: 5706495 (1998-01-01), Chandha et al.
patent: 5742816 (1998-04-01), Barr et al.
patent: 5751921 (1998-05-01), Fujimoto
patent: 5845276 (1998-12-01), Emerson et al.
patent: 5870764 (1999-02-01), Lo et al.
patent: 5884307 (1999-03-01), Depledge et al.
patent: 5893087 (1999-04-01), Wlaschin et al.
patent: 5899988 (1999-05-01), Depledge et al.
patent: 5963935 (1999-05-01), Ozbutun et al.
patent: 0 606 137 A2 (1994-07-01), None
Sun-Teck Tan, “Multimedia based PC assembly learning tool”, IEEE International Conference on Multi Media Engineering Education, 1996., Jul. 3-5, 1996, pp. 167-174.
Kung-Lung Wu, “Range-based bitmap indexing for high cardinality attributes with skew”, COMPSAC '98., Proceedings. The Twenty-Second Annual International Computer Software and Applications Conference, 1998, Aug. 19-21, 1998, pp. 61-66.
Ming-Chuan Wu, “Encoded Bitmap indexing for data warehouses”, Proceedings, 14th International Conference on Data Engineering, 1998., Feb. 23-27, 1998, pp. 220-230.
“Communication”, by Robert Sachs, for U.S. Application #08/807,344, entitled Creating Bitmaps from Multi-Level Identifiers.
“Declaration of Mark Kremer”, for U.S. Application #08,807,344, entitled “Creating Bitmaps from Multi-Level Identifiers”.
“Oracle 7.3 Focuses on Data Warehousing”, by Dan Richman, Sep. 25

Affiliated with

Also associated with

Rating

Bitmap segmentation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Bitmap segmentation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bitmap segmentation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2561455