Bitmap Indices (Cont.) In its simplest form a bitmap index on an attribute has a bitmap for each value of the attribute Bitmap has as many bits as records In a bitmap for value v,the bit for a record is 1 if the record has the value v for the attribute,and is 0 otherwise Bitmaps for gender Bitmaps for record income level m 10010 number ID gender income level L1 10100 0 76766 m L1 01101 1 22222 f L2 L2 01000 12121 L1 L3 00001 3 15151 m L4 L4 00010 4 58583 f L3 L5 00000 Database System Concepts-7th Edition 24.12 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 24.12 ©Silberschatz, Korth and Sudarshan th Edition Bitmap Indices (Cont.) ▪ In its simplest form a bitmap index on an attribute has a bitmap for each value of the attribute • Bitmap has as many bits as records • In a bitmap for value v, the bit for a record is 1 if the record has the value v for the attribute, and is 0 otherwise
Bitmap Indices (Cont.) Bitmap indices are useful for queries on multiple attributes not particularly useful for single attribute queries Queries are answered using bitmap operations ·Intersection(and） ·Union(or) Complementation (not) Each operation takes two bitmaps of the same size and applies the operation on corresponding bits to get the result bitmap ·E.g,100110AND110011=100010 1001100R110011=110111 NOT100110=011001 Males with income level L1:10010AND 10100=10000 Can then retrieve required tuples. Counting number of matching tuples is even faster Database System Concepts-7th Edition 24.13 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 24.13 ©Silberschatz, Korth and Sudarshan th Edition Bitmap Indices (Cont.) ▪ Bitmap indices are useful for queries on multiple attributes • not particularly useful for single attribute queries ▪ Queries are answered using bitmap operations • Intersection (and) • Union (or) • Complementation (not) ▪ Each operation takes two bitmaps of the same size and applies the operation on corresponding bits to get the result bitmap • E.g., 100110 AND 110011 = 100010 100110 OR 110011 = 110111 NOT 100110 = 011001 • Males with income level L1: 10010 AND 10100 = 10000 ▪ Can then retrieve required tuples. ▪ Counting number of matching tuples is even faster
Bitmap Indices (Cont.) Bitmap indices generally very small compared with relation size .E.g.,if record is 100 bytes,space for a single bitmap is 1/800 of space used by relation. If number of distinct attribute values is 8,bitmap is only 1%of relation size Deletion needs to be handled properly Existence bitmap to note if there is a valid record at a record location Needed for complementation not(A=v):(NOT bitmap-A-v)AND ExistenceBitmap Should keep bitmaps for all values,even null value To correctly handle SQL null semantics for NOT(A=V): intersect above result with (NOT bitmap-A-Null) Database System Concepts-7th Edition 24.14 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 24.14 ©Silberschatz, Korth and Sudarshan th Edition Bitmap Indices (Cont.) ▪ Bitmap indices generally very small compared with relation size • E.g., if record is 100 bytes, space for a single bitmap is 1/800 of space used by relation. ▪ If number of distinct attribute values is 8, bitmap is only 1% of relation size ▪ Deletion needs to be handled properly • Existence bitmap to note if there is a valid record at a record location • Needed for complementation ▪ not(A=v): (NOT bitmap-A-v) AND ExistenceBitmap ▪ Should keep bitmaps for all values, even null value • To correctly handle SQL null semantics for NOT(A=v): ▪ intersect above result with (NOT bitmap-A-Null)
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 Sudarshan
Database 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 tupleid is 64 bits • Above technique merges benefits of bitmap and B+ -tree indices
Spatial and Temporal Indices Database System Concepts -7th Edition 24.16 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 24.16 ©Silberschatz, Korth and Sudarshan th Edition Spatial and Temporal Indices