Bloom Filters A bloom filter is a probabilistic data structure used to check membership of a value in a set May return true(with low probability)even if an element is not present But never returns false if an element is present Used to filter out irrelevant sets Key data structure is a single bitmap For a set with n elements,typical bitmap size is 10n Uses multiple independent hash functions With a single hash function h()with range=number of bits in bitmap: For each element s in set S compute h(s)and set bit h(s) To query an element v compute h(v),and check if bit h(v)is set Problem with single hash function:significant chance of false positive due to hash collision 10%chance with 10n bits Database System Concepts-7th Edition 24.2 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 24.2 ©Silberschatz, Korth and Sudarshan th Edition Bloom Filters ▪ A bloom filteris a probabilistic data structure used to check membership of a value in a set • May return true (with low probability) even if an element is not present • But never returns false if an element is present • Used to filter out irrelevant sets ▪ Key data structure is a single bitmap • For a set with n elements, typical bitmap size is 10n ▪ Uses multiple independent hash functions ▪ With a single hash function h() with range=number of bits in bitmap: • For each element s in set S compute h(s) and set bit h(s) • To query an element v compute h(v), and check if bit h(v) is set ▪ Problem with single hash function: significant chance of false positive due to hash collision • 10% chance with 10n bits
Bloom Filters (Cont.) Key idea of Bloom filter:reduce false positives by use multiple hash functions h()for i=1..k For each element s in set S for each i compute hi(s)and set bit hi(s) To query an element v for each i compute hi(v),and check if bit hi(v)is set If bit hi(v)is set for every i then report v as present in set Else report v as absent With 10n bits,and k =7,false positive rate reduces to 1%instead of 10%with k=1 Database System Concepts-7th Edition 24.3 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 24.3 ©Silberschatz, Korth and Sudarshan th Edition Bloom Filters (Cont.) ▪ Key idea of Bloom filter: reduce false positives by use multiple hash functions hi () for i = 1..k • For each element s in set S for each i compute hi (s) and set bit hi (s) • To query an element v for each i compute hi (v), and check if bit hi (v) is set ▪ If bit hi (v) is set for every i then report v as present in set ▪ Else report v as absent • With 10n bits, and k = 7, false positive rate reduces to 1% instead of 10% with k = 1
Write Optimized Indices Performance of B+-trees can be poor for write-intensive workloads One 1/O per leaf,assuming all internal nodes are in memory With magnetic disks,100 inserts per second per disk With flash memory,one page overwrite per insert Two approaches to reducing cost of writes Log-structured merge tree ·Buffer tree Database System Concepts-7th Edition 24.4 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 24.4 ©Silberschatz, Korth and Sudarshan th Edition Write Optimized Indices ▪ Performance of ▪ B + -trees can be poor for write-intensive workloads • One I/O per leaf, assuming all internal nodes are in memory • With magnetic disks, < 100 inserts per second per disk • With flash memory, one page overwrite per insert ▪ Two approaches to reducing cost of writes • Log-structured merge tree • Buffer tree
Log Structured Merge (LSM)Tree Consider only inserts/queries for now Lo Records inserted first into in- Memory memory tree (Lo tree) When in-memory tree is full Disk records moved to disk(L1 tree) B+-tree constructed using bottom-up build by merging existing L1 tree with records from Lo tree When L1 tree exceeds some threshold,merge into L2 tree And so on for more levels 。 Size threshold for Li+1 tree is k times size threshold for Li tree Merge creates a new B+-tree using bottom-up build Database System Concepts-7th Edition 24.5 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 24.5 ©Silberschatz, Korth and Sudarshan th Edition Log Structured Merge (LSM) Tree ▪ Consider only inserts/queries for now ▪ Records inserted first into inmemory tree (L0 tree) ▪ When in-memory tree is full, records moved to disk (L1 tree) • B + -tree constructed using bottom-up build by merging existing L1 tree with records from L0 tree ▪ When L1 tree exceeds some threshold, merge into L2 tree • And so on for more levels • Size threshold for Li+1 tree is k times size threshold for Li tree • Merge creates a new B+ -tree using bottom-up build
LSM Tree (Cont.) Benefits of LSM approach Inserts are done using only sequential l/O operations Leaves are full,avoiding space wastage Reduced number of I/O operations per record inserted as compared to normal B*-tree(up to some size) If each leaf has m entries,m/kentries merged in using 1 IO Total l/O operations:k/m logk(M/M)where /total number of entries,and Mis the size of Lo tree. Drawback of LSM approach Queries have to search multiple trees Entire content of each level copied multiple times Database System Concepts-7th Edition 24.6 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 24.6 ©Silberschatz, Korth and Sudarshan th Edition LSM Tree (Cont.) ▪ Benefits of LSM approach • Inserts are done using only sequential I/O operations • Leaves are full, avoiding space wastage • Reduced number of I/O operations per record inserted as compared to normal B+ -tree (up to some size) ▪ If each leaf has m entries, m/k entries merged in using 1 IO ▪ Total I/O operations: k/m logk (I/M) where I = total number of entries, and M is the size of L0 tree. ▪ Drawback of LSM approach • Queries have to search multiple trees • Entire content of each level copied multiple times
Optimizations of LSM ■Rolling merge LSM/Stepped Merge often implemented on a partitioned relation Each partition size set to some max,split if over-sized Spread partitions over multiple machines Database System Concepts-7th Edition 24.7 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 24.7 ©Silberschatz, Korth and Sudarshan th Edition ▪ Rolling merge ▪ LSM/Stepped Merge often implemented on a partitioned relation • Each partition size set to some max, split if over-sized • Spread partitions over multiple machines Optimizations of LSM
Stepped Merge Index Stepped-merge index:variant of LSM tree with k trees at each level on disk Memory When all k indices exist at a level,merge them into one Disk index of next level. ·Reduces write cost compared to LSM tree But queries are even more expensive since many trees need to be queries Optimization for point lookups Compute Bloom filter for each tree and store in- memory Query a tree only if Bloom filter returns a positive result Database System Concepts-7th Edition 24.8 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 24.8 ©Silberschatz, Korth and Sudarshan th Edition Stepped Merge Index ▪ Stepped-merge index: variant of LSM tree with k trees at each level on disk • When all k indices exist at a level, merge them into one index of next level. • Reduces write cost compared to LSM tree ▪ But queries are even more expensive since many trees need to be queries ▪ Optimization for point lookups • Compute Bloom filter for each tree and store inmemory • Query a tree only if Bloom filter returns a positive result
LSM Trees (Cont.) Deletion handled by adding special "delete"entries Lookups will find both original entry and the delete entry,and must return only those entries that do not have matching delete entry When trees are merged,if we find a delete entry matching an original entry,both are dropped. Update handled using insert delete LSM trees were introduced for disk-based indices But useful to minimize erases with flash-based indices The stepped-merge variant of LSM trees is used in many BigData storage systems Google BigTable,Apache Cassandra,MongoDB And more recently in SQLite4,LevelDB,and MyRocks storage engine of MySQL Database System Concepts-7th Edition 24.9 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 24.9 ©Silberschatz, Korth and Sudarshan th Edition LSM Trees (Cont.) ▪ Deletion handled by adding special “delete” entries • Lookups will find both original entry and the delete entry, and must return only those entries that do not have matching delete entry • When trees are merged, if we find a delete entry matching an original entry, both are dropped. ▪ Update handled using insert + delete ▪ LSM trees were introduced for disk-based indices • But useful to minimize erases with flash-based indices • The stepped-merge variant of LSM trees is used in many BigData storage systems ▪ Google BigTable, Apache Cassandra, MongoDB ▪ And more recently in SQLite4, LevelDB, and MyRocks storage engine of MySQL
Buffer Tree Alternative to LSM tree Key idea:each internal node of B+-tree has a buffer to store inserts Inserts are moved to lower levels when buffer is full With a large buffer,many records are moved to lower level each time Per record I/O decreases correspondingly ■Benefits Less overhead on queries Can be used with any tree index structure Used in PostgreSQL Generalized Search Tree(GiST)indices Drawback:more random l/O than LSM tree Internal node Buffer Database System Concepts-7th Edition 24.10 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 24.10 ©Silberschatz, Korth and Sudarshan th Edition Buffer Tree ▪ Alternative to LSM tree ▪ Key idea: each internal node of B+ -tree has a buffer to store inserts • Inserts are moved to lower levels when buffer is full • With a large buffer, many records are moved to lower level each time • Per record I/O decreases correspondingly ▪ Benefits • Less overhead on queries • Can be used with any tree index structure • Used in PostgreSQL Generalized Search Tree (GiST) indices ▪ Drawback: more random I/O than LSM tree
Bitmap Indices Bitmap indices are a special type of index designed for efficient querying on multiple keys Records in a relation are assumed to be numbered sequentially from,say,0 Given a number n it must be easy to retrieve record n Particularly easy if records are of fixed size Applicable on attributes that take on a relatively small number of distinct values E.g.,gender,country,state,... 。 E.g.,income-level (income broken up into a small number of levels such as0-9999,10000-19999,20000-50000,50000-infinity) A bitmap is simply an array of bits Database System Concepts-7th Edition 24.11 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 24.11 ©Silberschatz, Korth and Sudarshan th Edition Bitmap Indices ▪ Bitmap indices are a special type of index designed for efficient querying on multiple keys ▪ Records in a relation are assumed to be numbered sequentially from, say, 0 • Given a number n it must be easy to retrieve record n ▪ Particularly easy if records are of fixed size ▪ Applicable on attributes that take on a relatively small number of distinct values • E.g., gender, country, state, … • E.g., income-level (income broken up into a small number of levels such as 0-9999, 10000-19999, 20000-50000, 50000- infinity) ▪ A bitmap is simply an array of bits