Bit-Mapped Indexing Routines---Beta Testers Wanted

Bit-Mapped Indexing Routines---Beta Testers Wanted

Post by ddupl.. » Fri, 22 Nov 1996 04:00:00



Bit-mapped indexing is still a relatively new concept in the DB field.
It is with this in mind that I set out to produce a library of
functions for creating, managing and manipulating bit-maps. Although
the routines could be used for manipulating any form of bitmap, they
were specifically designed for bit-mapped indexing.

There are a number of factors that make these routines superior to
those currently used by Sysbase, Oracle, Redbrick and the other DB
vendors that have implemented this BM (bitmap) technology:

1) The ability store 100,000 bits in 14K. This is WORST case senario.
 At best, 100,000 bits can be stored in 34 bytes.

2) This is THE major advantage - ALL THE ROUTINES ACT UPON THE
COMPRESSED DATA,  therefore:
i)  No de-compression time.
ii) Extremely fast data manipulation because of the size of the
data set being manipulated.

3) This is another major advantage - THE ROUTINES OVERCOME THE
PROBLEMS ASSOCIATED WITH HIGH CARDINALITY DATA.
This is basically acheived by breaking the data into sections. If
there is no data in a particular section, a BM for that section is

not stored. E.g. A bit-map is divided into 10 sections, each
representing 10,000 bit positions, i.e. a 100,000 bit BM. If position
1, 10,000, and 100,000 is set, only 3 - 6 bytes at most would be
required to store the BM positions. (This excludes section header
information, which is about 8 bytes for every section, i.e. 24 bytes
in the example above)

The BM functions include functions for:

1)  ANDing
2)  ORing
3)  XORing
4)  NOTing
5)  ORXing (deleting)
6)  XNORing
7)  NANDing
8)  NORIng
9)  Finding
10) Search Next
11) Search Previous
12) Adding
13) Deleting
14) Appending..... and more.

I am able to perform various logical operations (1 - 8), on 2 source
data sets of 1,000,000 bits each, and produce a result data set in 0.2
seconds for any single operation. Once again this is WORST case
senario. Best case... I am unable to time them, as the timing function
returns 0.0000. My test have been conducted on a Compaq 90Mz Pentium
with 32MB memory.

A beta version of these routines will be available by 1 January 1997.
The routines will comprise of a 16-bit Windows library, a 32-bit
Windows library, a DOS library, and 16 & 32 Bit Windows DLL's and will
be shipped complete with on-line documentation and help.

If anybody is interested in testing the routines, please send me an
e-mail at:


The above e-mail address will be activated on 11/18/96 at 6:00PM EST.

 
 
 

Bit-Mapped Indexing Routines---Beta Testers Wanted

Post by ZOD » Sat, 30 Nov 1996 04:00:00


I thought it was "bitWISE" indexing not "bitmapped" indexing. Please
correct me on this.

Bill Gfroehrer...

 
 
 

Bit-Mapped Indexing Routines---Beta Testers Wanted

Post by Diana Ra » Sat, 07 Dec 1996 04:00:00


Bitmap indexes are used for high-performance query execution, such as in
a data warehouse environment.  They are best used on columns with a low
cardinality.  For example, if your data values for column "direction"
were "up", "down", "left", and "right", the bitmap index would look as
follows:

direction = "up"      0  1  0  0  0  0  0  0  1  0  1  0
direction = "down"    0  0  1  1  0  0  1  1  0  0  0  1
direction = "left"    1  0  0  0  0  1  0  0  0  0  0  0
direction = "right"   0  0  0  0  1  0  0  0  0  1  0  0

rather than mapping the full value.


> I thought it was "bitWISE" indexing not "bitmapped" indexing. Please
> correct me on this.

> Bill Gfroehrer...

 
 
 

Bit-Mapped Indexing Routines---Beta Testers Wanted

Post by David Walrat » Wed, 11 Dec 1996 04:00:00



> I thought it was "bitWISE" indexing not "bitmapped" indexing. Please
> correct me on this.

> Bill Gfroehrer...

Bitmap indexes are the generic term for the technology.

Sybase usues the term "bitwise" indexing to differentiate the
high-cardinality bitmap index technology in its Sybase IQ data
warehousing product from the more common low-cardinality bitmapping
indexes available in other products. (See www.sybase.com et al...)

Incidentally, I wonder what the original poster meant by bitmap indexes
being "relatively new" in databases. Low cardinality bitmap indexes
were in Model 204 well over 20 years ago, so maybe he/she meant
relative to punch-card databases ?

DEW

----------------------------------------------------------------------

Sybase IQ                       77 S. Bedford St, Burlington, MA 01803

Opinions are my own; my employer doesn't want them.

 
 
 

Bit-Mapped Indexing Routines---Beta Testers Wanted

Post by John Wo » Wed, 11 Dec 1996 04:00:00



>I thought it was "bitWISE" indexing not "bitmapped" indexing. Please
>correct me on this.

>Bill Gfroehrer...

I believe it is Sybase that has a patent and trademark on BitWise.
BitWise, I believe, is a combination of Bit-map indexing and querying
to address high-cardinality data problems when using just Bit-map
indexing.
--
John Wood

   "Nearly all men can stand adversity,
   but if you want to test a man's character, give him power."

 
 
 

Bit-Mapped Indexing Routines---Beta Testers Wanted

Post by Barry Johnso » Thu, 12 Dec 1996 04:00:00



> Incidentally, I wonder what the original poster meant by bitmap indexes
> being "relatively new" in databases. Low cardinality bitmap indexes
> were in Model 204 well over 20 years ago, so maybe he/she meant
> relative to punch-card databases ?
> ...
> Opinions are my own; my employer doesn't want them.

FWIW, Burroughs' DMSII also had them by the time I got to it in '77...

--

 
 
 

Bit-Mapped Indexing Routines---Beta Testers Wanted

Post by wendy whitm » Thu, 19 Dec 1996 04:00:00




Quote:>I believe it is Sybase that has a patent and trademark on BitWise.

Actually, no one "has" a trademark on BitWise.  My company is one of
many who use this name (either for the company, a product, a process,
etc.) and we've been in litagation over it for years.
 
 
 

Bit-Mapped Indexing Routines---Beta Testers Wanted

Post by Dave Bridge » Thu, 19 Dec 1996 04:00:00





> > Incidentally, I wonder what the original poster meant by bitmap indexes
> > being "relatively new" in databases. Low cardinality bitmap indexes
> > were in Model 204 well over 20 years ago, so maybe he/she meant
> > relative to punch-card databases ?
> > ...
> > Opinions are my own; my employer doesn't want them.

> FWIW, Burroughs' DMSII also had them by the time I got to it in '77...

> --


Actually bitmap indexes existed in the punch card era. They were called (I
believe) "Keysort" a trade name of (I believe) Royal-McBee. Holes were
punched around the edges of a card upon which was written the information.
The "bits" were turned from "zero" to "one" by notching the edge of the
card to the hole. A query was made by running a sorting needle through the
stack of cards and shaking the deck. All cards which matched the query
attribute would fall out. The process would then be repeated on the fallen
cards to refine the query. The final results of the query could then be
read from the remaining "dropped" cards. This is the origin of the term
"false drop" for a query match that should not have occurred or occurred by
accident.

Needless to say these were not Hollerith (IBM) punched cards.

--Dave

 
 
 

Bit-Mapped Indexing Routines---Beta Testers Wanted

Post by Anthony Mandi » Fri, 20 Dec 1996 04:00:00



> Actually bitmap indexes existed in the punch card era.

        Yeah, they were the holes!

Quote:> They were called (I
> believe) "Keysort" a trade name of (I believe) Royal-McBee. Holes were
> punched around the edges of a card upon which was written the information.
> The "bits" were turned from "zero" to "one" by notching the edge of the
> card to the hole. A query was made by running a sorting needle through the
> stack of cards and shaking the deck.

        And the whole process was known as a quick sort! ;-)

-am

 
 
 

Bit-Mapped Indexing Routines---Beta Testers Wanted

Post by Felix Kasza [MV » Fri, 20 Dec 1996 04:00:00


Dave,

 > A query was made by running a sorting needle through the
 > stack of cards and shaking the deck.

Those were the days ... nothing faster than an analog sort.  (The
setup time is a bit of a hindrance, though!)

Cheers,
Felix.

Looking for MS Knowledgebase articles?  Go to http://www.microsoft.com/kb/ ...

 
 
 

1. Bit-Mapped Indexing Routines - Beta Testers Wanted

Bit-Mapped Indexing Routines  -  Beta Testers Wanted
--------------------------------------------------------------------------------------

Bit-mapped indexing is still a relatively new concept in the DB field.
It is with this in mind that I set out to produce a library of
functions for creating, managing and manipulating bit-maps. Although
the routines could be used for manipulating any form of bitmap, they
were specifically designed for bit-mapped indexing.

There are a number of factors that make these routines superior to
those currently used by Sysbase, Oracle, Redbrick and the other DB
vendors that have implemented this BM (bitmap) technology:

1) The ability store 100,000 bits in 14K. This is WORST case senario.
 At best, 100,000 bits can be stored in 34 bytes.

2) This is THE major advantage - ALL THE ROUTINES ACT UPON THE
COMPRESSED DATA,  therefore:
i)  No de-compression time.
ii) Extremely fast data manipulation because of the size of the
data set being manipulated.

3) This is another major advantage - THE ROUTINES OVERCOME THE
PROBLEMS ASSOCIATED WITH HIGH CARDINALITY DATA.
This is basically acheived by breaking the data into sections. If
there is no data in a particular section, a BM for that section is

not stored. E.g. A bit-map is divided into 10 sections, each
representing 10,000 bit positions, i.e. a 100,000 bit BM. If position
1, 10,000, and 100,000 is set, only 3 - 6 bytes at most would be
required to store the BM positions. (This excludes section header
information, which is about 8 bytes for every section, i.e. 24 bytes
in the example above)

The BM functions include functions for:

1)  ANDing
2)  ORing
3)  XORing
4)  NOTing
5)  ORXing (deleting)
6)  XNORing
7)  NANDing
8)  NORIng
9)  Finding
10) Search Next
11) Search Previous
12) Adding
13) Deleting
14) Appending..... and more.

I am able to perform various logical operations (1 - 8), on 2 source
data sets of 1,000,000 bits each, and produce a result data set in 0.2
seconds for any single operation. Once again this is WORST case
senario. Best case... I am unable to time them, as the timing function
returns 0.0000. My test have been conducted on a Compaq 90Mz Pentium
with 32MB memory.

A beta version of these routines will be available by 1 January 1997.
The routines will comprise of a 16-bit Windows library, a 32-bit
Windows library, a DOS library, and 16 & 32 Bit Windows DLL's and will
be shipped complete with on-line documentation and help.

If anybody is interested in testing the routines, please send me an
e-mail at:


The above e-mail address will be activated on 11/18/96 at 6:00PM EST.

2. How you transfer diagrams from one db to another?

3. Bit-Mapped Indexing Routines----Beta Testers Wanted

4. ***FREE MOBILE CALLS*** This works! 9183

5. multiselection

6. Bit-Mapped Indexing Routines - Beta Testers Wanted

7. Seeking Oracle developer

8. Bit-Mapped Indexing Routines----Beta Testers Wanted

9. ***Bit-Mapped Indexing Routines (Beta Testers Wanted)***

10. Bit-Mapped Indexing Routines - Beta Testers Wanted

11. ***Bit-Mapped Indexing Routines (Beta Testers Wanted)***