Efficient Implementation of Bitmap Operations Bitmaps are packed into words;a single word and (a basic CPU instruction)computes and of 32 or 64 bits at once E.g.,1-million-bit maps can be and-ed with just 31,250 instruction Counting number of 1s can be done fast by a trick: Use each byte to index into a precomputed array of 256 elements each storing the count of 1s in the binary representation Can use pairs of bytes to speed up further at a higher memory cost Add up the retrieved counts ■ Bitmaps can be used instead of Tuple-ID lists at leaf levels of B*-trees,for values that have a large number of matching records Worthwhile if 1/64 of the records have that value,assuming a tuple- id is 64 bits Above technique merges benefits of bitmap and B*-tree indices Database System Concepts-7th Edition 24.15 ©Silberscha乜，Korth and SudarshanDatabase System Concepts - 7 24.15 ©Silberschatz, Korth and Sudarshan th Edition Efficient Implementation of Bitmap Operations ▪ Bitmaps are packed into words; a single word and (a basic CPU instruction) computes and of 32 or 64 bits at once • E.g., 1-million-bit maps can be and-ed with just 31,250 instruction ▪ Counting number of 1s can be done fast by a trick: • Use each byte to index into a precomputed array of 256 elements each storing the count of 1s in the binary representation ▪ Can use pairs of bytes to speed up further at a higher memory cost • Add up the retrieved counts ▪ Bitmaps can be used instead of Tuple-ID lists at leaf levels of B+ -trees, for values that have a large number of matching records • Worthwhile if > 1/64 of the records have that value, assuming a tuple￾id is 64 bits • Above technique merges benefits of bitmap and B+ -tree indices