SIGMOD'22 Submission

[geoffxy]

Paper writing (first draft, section checklist)

• [x] Abstract
  • Andreas
• [x] Introduction
  • Andreas
• [x] Design
  • Markos
• [x] Evaluation
  • Geoffrey (+ experiments)
• [x] Background
• [x] Related Work
• [x] Discussion
• [x] Conclusion

Experiments Must Have

• [x] Lean store bindings for comparison
• [x] YCSB synthetic
• [x] YCSB Bourbon datasets
  • NOTE: These YCSB experiments need to be re-run after #12 is addressed
• [x] Test experiments with LeanStore

Experiments nice to have

• [ ] Kvell bindings finished and comparison
• [ ] SOSD bindings for LeanStore too so we can compare against LLSM
• [ ] SOSD benchmark run for comparison (LLSM / RocksDB)
• [x] #18

Required code changes

• [x] #12
• [x] #10
• [x] Adapt experiments to LeanStore (cannot "reopen" a database)

Features (nice to have)

• ALEX page table improvements
  • [ ] Optimistic lock coupling to remove model-wide mutex
  • [ ] Compression for adjacent physical pages

[geoffxy]

Notes from meeting on 8/31

Opportunities for model-based inserts Precondition: Know about "all the keys" or have a sample

• Lazily reorganizing a chain (know all keys in the chain)
• Bulk loading data

Key differences compared to LeanStore

• Lazy reorganization instead of splitting nodes directly (chain reorg) - more write optimizied
• Page grouping lets us leave out extra separator keys (interpolation among grouped pages)
• Learned index inner nodes may be smaller than the B+Tree inner nodes
• CDF forecasting to leave "gaps" based on the insert distribution
• Use of a write buffer like RocksDB
  • Could always load the page while checking the memtable
  • Pros:
  • Exploit concurrent I/O
  • Cons:
  • Need to always check the memtable for reads

LeanStore experiment

• Hotspot insert - show benefit of write buffering in LLSM vs. LeanStore - vary hotspot size

Idea for leaving gaps

• Sample memtables to determine what the insert CDF looks like (how many memtable generations?)
• Trigger reorganization and leave gaps based on the empirical insert CDF

Comparison with Bourbon

• Qualitative comparison only b/c not open source
• Fundamentally still an LSM
• Key idea is very similar to a subsection in the RadixSpline paper - replace block index with a CDF index (learned index)
  • Index per SSTable

One strategy for grouping

• Use existing RadixSpline code to do the spline fitting
• Can store the spline points in ALEX or a B+Tree (to handle inserts)
• Need to store additional metadata in the record "value" to allow us to use the spline points
  • Number of pages in the segment
  • Where the page is located on disk (physical location)
  • Model data
  • Overflow page chain
• This strategy might degenerate because we don't consider neighboring segments - will need some kind of global reorg
  • Need a cost model to know when to trigger a global reorganization
  • Size of the index - number of physical pages, compute B+Tree size, if exceeds B+Tree size then trigger reorg
• Could do local fixing - look at neighboring segments and use a cost model to figure out if we should merge them