Three Papers on ML & Databases — Concise Summaries

Core Idea

• View an index as a model that maps a key to its position (approximate the key’s cumulative distribution function, CDF).
• Replace hand-crafted data structures (B-tree, hash, Bloom) with learned models specialized to the key distribution.

Techniques

• Recursive Model Index (RMI): a hierarchy of small models narrowing to a final predictor, then a short local search.
• Learned Bloom filters: a classifier to reject non-members, with a small backup filter to bound false positives.
• Distribution-aware layouts: models inform page/segment placement to reduce search ranges and cache misses.

Findings

• On static or slowly changing data with skew, learned indexes can reduce memory and improve lookup latency vs. B-trees/BFs.
• Best when keys follow stable, learnable distributions (e.g., monotone numeric keys, structured strings).

Limitations & Care

• Updates & distribution shift require retraining or online adaptation; worst-case latency tails must be controlled.
• Hybrid designs (model + bounded search / fallback structure) are important for robustness.

Where ML Fits

• Cardinality estimation: supervised & deep models beat heuristics/histograms, especially on correlated predicates.
• Cost models & plan selection: learned cost surrogates guide optimizers; bandits/DRL explore join orders.
• Knob tuning & configuration: black-box optimization (Bayesian, RL) for indexes, memory, and concurrency.
• Admission control & scheduling: predict runtimes/queues; allocate CPU/IO fairly to meet SLOs.
• Storage & caching: learned eviction, prefetch and compression; tier placement via workload prediction.
• Monitoring & anomaly detection: time-series/autoencoders to spot regressions and noisy neighbors.

Design Patterns

• In-the-loop vs. on-the-side: models either directly decide (e.g., choose plan) or advise heuristics.
• Offline warm-start + online learning: bootstrap from logs, adapt with drift detection and rollback.
• Safety rails: confidence thresholds, fallback plans, and guardrails against catastrophic choices.

Challenges

• Label scarcity, workload drift, interpretability, and integrating uncertainty into deterministic components.
• Evaluation realism: need long-running, mixed workloads and end-to-end metrics, not only microbenchmarks.

Scope

• Systematic review of places where deep learning is embedded during execution (beyond planning/optimization).

Use Cases

• Predicate / UDF acceleration: learned surrogates to skip rows early (with calibrations to bound false negatives).
• Learned filters & sketches: neural Bloom-like gates and learned sampling to cut tuples before joins.
• Operator adaptivity: DL classifiers to pick join algorithms or radix partition sizes under skew.
• Approximate query processing (AQP): generative/embedding models to estimate aggregates with error bars.
• Compression & encodings: autoencoder/sequence models to compress columns and accelerate scans.
• Hardware-aware execution: DL to schedule GPU/CPU kernels, pick vector widths, and batch sizes.

Benefits & Caveats

• Big wins come from early tuple elimination and reducing random IO on skewed/structured data.
• Correctness requires safe fallbacks or calibrated thresholds; worst-case guarantees matter (esp. for joins).
• Deployment must consider model latency, batching, and cache behavior to avoid slowing hot loops.

Evaluation Themes

• Microbenchmarks for single operators plus end-to-end queries; ablations for model overhead vs. savings.
• Stress tests for drift and update churn; reporting tail latencies, not only averages.