Query processing using compressed bitmaps

Details Query processing using compressed bitmaps Query processing using compressed bitmaps

1997-02-28

2000-10-31

Amsbury, Wayne

Data processing: database and file management or data structures

Database design

Data structure types

707 4, 707 10, 707100, 707101, G06F 1730

Patent

active

061416568

ABSTRACT:
A method for performing logical operations on bitmap streams from segmented bitmaps. The logical operations include the AND, OR, and Set Minus operations. One embodiment of the invention performs the logical AND operation on a plurality of bitmap streams by searching for a set of overlapping bitmap segments. The ranges corresponding to the overlap among the overlapping bitmap segments are scanned to generate non-gap results. One embodiment of the invention performs the logical OR operation on a plurality of bitmap streams. To generate a result for a given range, only the bitmap segments overlapping the given range are ORed together. One embodiment of the invention performs a Set Minus between bitmap streams. A set minus is the ANDing of a first condition with the negation of another condition. To generate a set minus result, the ranges corresponding to the gaps in the bitmap associated with the negated condition are ignored.

REFERENCES:
patent: 4606002 (1986-08-01), Waisman et al.
patent: 4817036 (1989-03-01), Millett et al.
patent: 5430869 (1995-07-01), Ishak et al.
patent: 5475837 (1995-12-01), Ishak et al.
patent: 5495608 (1996-02-01), Antoshenkov
patent: 5504889 (1996-04-01), Burgess
patent: 5560007 (1996-09-01), Thai
patent: 5649181 (1997-07-01), French et al.
patent: 5664172 (1997-09-01), Antoshenkov
Antoshenkov, G., "Random Sampling from Pseudo-Ranked B + Trees", Proceeding of the 18th VLDB Conference, Vancouver, BC Canada, Aug. 1992, pp. 375-382.
Antoshenkov, G. et al., "Byte-Aligned Bitmap Compression", Date Compression Conference, 1995 DCC 1995 Proceedings Mar. 1995, p. 476.
Antonshenkov, G., "Dynamic Query Optimization in Rdb/VMS", Proceedings of Ninth International Conference on Data Engineering, Apr. 1993, pp. 42-52.
Eshel M. et al., "CMs File-Level Commit" IBM Technical Disclosure Bulletin, vol. 32, No. 1, Jun. 1989 pp. 266-268.
O'Neil, P. et al., "Multi-Table Joins Through Bitmapped Join Indices", SIGMOD Record, vol. 24, No. 3, Sep. 1995, pp. 8-11.
Pronk, V. et al., "A Performance Analysis Of The Bit-Map Access Protocol For Shared-Medium Networks", Proceedings of International Zurich Seminar on Broadband Communications, 1998 Accessing, Transmission, Networking., Feb. 1998.
Wu, Ming-Chuan et al., "Encoded Bitmap Indexing For Data Warehouses", Proceedings of 14th International Conference on Data Engineering, Feb. 1998.
Mano, Moris, "Digital Design", 1991 Prentice-Hall, Inc., ISBN 0-13-212937-X (TK7888.3.M343 1991) p. 1017.
"Oracle TextServer3 Concepts, Version 3," Oracle Corporation (Part No. A24984-1, 1995, pp. 3-1 to 3-23).
"Oracle Textserver3 Concepts, Release 3.1," Oracle Corporation (Part No. A41697-2), 1996, pp. 3-1 to 3-29.
"SQL TextRetrieval Administrator's Guide", Version 2.0, Oracle Corporation, Rev. Jul., 1992 (Part No. 0365-20-0792).
IOUW wrap-up (vendors introduce database tools at International Oracle Users Week conference) (Client/server Connection) (Industry Trend or Event) DBMS, v8 n13, p. 112(1), Dec. 1995.
"Oracle 7.3 Focuses on Data Warehousing", Dan Richman, Computerworld, Inc., Sep. 25, 1995.
"Model 204 Architecture and Performance", Presented at 2.sup.nd International Workshop on High Performance Transaction Systems, Patrick O'Neil, Sep. 1987.
"Faster Data Warehouses", Infoweek, Sec. "OpenLabs".
Oracle Press Releases, "Oracle 7 Release 7.3 extends Oracle's lead in Data warehousing Market", http://www.oracle.com/corporate/press/html/73w.html.; Oracle to host first developer conference; Preview new products, Jan. 30, 1996, http://www.oracle.com/corporate/press/html/odc2.html, DBMS vol. 8, n13, p. 112/OUW wrap-up.
Rennhackhamp, Martin DBMS, v9, n12, p. S12(3)Nov. 1996, DBMS Server Comparision Supplement Software Review Evaluation Oracle, Oracle7 7.3 and Universal Server.
"Communication", by Robert Sachs, for U.S. Application #08/808,429, entitled Query Processing Using Compressed Bitmaps.
"Declaration of Mark Kremer", for U.S. Application #08/808,429, entitled Query Processing using Compressed Bitmaps.
"Oracle: Oracle, HP And EMC Combines Forces To Create World's Largest Data Warehouse", by M2 Presswire, Sep. 19, 1995.
"Technology Analysis-Faster Data Warehouse-New Tools Provide High-Performance Querying Through Advanced Indexing", by H. Edelstein, Information Week, Dec. 4, 1995.

Affiliated with

Also associated with

Rating

Query processing using compressed bitmaps does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2064739