Rui Santos Costa

Cloud-native OLAP systems like Snowflake, BigQuery, and Athena hit a problem I call Pruning Lag. Queries must full-scan during the window between data ingestion and index availability. I designed MARS, a logarithmic-bucket routing scheme that achieves immediate pruning from the first ingested row with zero blocking, and proved it near-optimal (Theorem 4): its pruning effectiveness stays within a constant factor of an offline oracle. Along the way I argue for a Rebuild Barrier, the design principle that any distribution-aware scheme needs Ω(N) work before effective pruning, leaving a tight lower bound to future work. On cold Athena/S3 it scans up to ~30× fewer bytes (1795× in the extreme fare ≥ 500 case), which at Athena's $5/TB translates to a material, if data-dependent, cut in query cost (est.).

• 4.6×Wall-clock speedup (in-memory, 10.6M rows)
• 5–9×Speedup on cold object storage (Athena/S3)
• 99.5%Bytes skipped (NYC taxi dataset)

Single-server multi-user Oblivious-RAM constructions have historically been stuck on a mutable position map. EPOCH-ORAM replaces per-access random leaf assignment with a PRF-based deterministic formula ℓ(b,e) = PRF(K, b, e) mod L, enabling coordination-free multi-user access via a shared key. The empirical result reframes the problem. Multi-user ORAM is a coordination problem, not a security problem.

• 3.5×Overhead vs. single-user Path ORAM
• 10⁶Blocks evaluated
• fullObliviousness on single untrusted server