PCM for main memory PCM-friendly algorithms Rethinking Database algorithms for Phase Change memory cidr2011 Motivation Choosing PCM-friendly database algorithms and data structures to reduce the number of writes
PCM for main memory PCM-friendly algorithms • Motivation Choosing PCM-friendly database algorithms and data structures to reduce the number of writes Rethinking Database Algorithms for Phase Change Memory(CIDR2011)
PCM for main memory PCM-friendly DB algorithms Prior design goals for DRAM Low computation complexity Good CPU cache performance Power efficiency( more recently New goal for PCM minimizing pcm writes Low wear, energy and latency Finer-grained access granularity: bits, words, cache line Two core database techniques B+-Tree Index Hash joins
PCM for main memory PCM-friendly DB algorithms • Prior design goals for DRAM − Low computation complexity − Good CPU cache performance − Power efficiency (more recently) • New goal for PCM − minimizing PCM writes − Low wear , energy and latency − Finer-grained access granularity:bits,words,cache line • Two core database techniques − B + -Tree Index − Hash Joins
PCM-friendly db algorithms B+-Tree Index B+-Tree Records at leaf nodes High fan out Suitable for file systems 7 · For PCm Insertion/deletion incur a lot of write operations num eys Insert 3 num keys 524789 789 incurs 11 writes pointers pointers K keys and K pointers in a node: 2 (K/2)+1=K+1
PCM-friendly DB algorithms B + -Tree Index • B + -Tree – Records at leaf nodes – High fan out – Suitable for file systems • For PCM – Insertion/deletion incur a lot of write operations – K keys and K pointers in a node: 2(K/2)+1=K+1 num keys 5 2 4 7 8 9 pointers num keys 6 2 3 4 7 8 9 pointers Insert 3 incurs 11 writes
PCM-friendly dB algorithms B+-Tree Index PCM-friendly b*Tree Unsorted all the non-leaf and leaf nodes unsorted Unsorted leaf sorted non -eaf and unsorted leaf Unsorted leaf with bitmap sorted non-leaf and unsorted leaf with bitmaps num eys num keys 5|8 2|94|7 101182947 1010 pointers pointers Unsorted leaf node Unsorted leaf node with bitmap
• PCM-friendly B+ -Tree – Unsorted: all the non-leaf and leaf nodes unsorted – Unsorted leaf: sorted non-leaf and unsorted leaf – Unsorted leaf with bitmap :sorted non-leaf and unsorted leaf with bitmaps PCM-friendly DB algorithms B + -Tree Index num keys 5 8 2 9 4 7 pointers num keys 1011 1010 8 2 9 4 7 pointers Unsorted leaf node Unsorted leaf node with bitmap
PCM-friendly db algorithms B+-Tree Index Unsorted leaf Insert/delete incurs 3 writes num num keys Delete 2 eys 582|94 48|794 pointers pointers Unsorted leaf with bitmap Insert incurs 3 writes delete incurs 1 write num keys num eys 10118 Delete 2 2|947 1018 1010 1010 pointers pointers
• Unsorted leaf – Insert/delete incurs 3 writes PCM-friendly DB algorithms B + -Tree Index num keys 5 8 2 9 4 7 pointers num keys 4 8 7 9 4 pointers Delete 2 • Unsorted leaf with bitmap – Insert incurs 3 writes; delete incurs 1 write num keys 1011 1010 8 2 9 4 7 pointers Delete 2 num keys 1001 1010 8 2 9 4 7 pointers