Hi Shawn,
Thanks for raising your concerns!
The main reason is that we're optimizing for *fast and predictable
single-key lookups*. With non-overlapping ranges, once index metadata is
cached, a key can be resolved with *a single region-file lookup* (a single
small file read).
Most alternatives improve write amplification, but they introduce overlap.
That means readers must consult *multiple files*, handle updates/deletes,
and reconcile results. On object storage, reading every additional file *adds
latency,* making lookup time dependent on the maintenance state of the
index.
We considered several alternatives before settling on non-overlapping
ranges:
1. Table-like layout: flexible ranges, delete vectors, and unbounded
update files.
- Benefit: minimal write amplification.
- Trade-off: lookup latency becomes heavily dependent on maintenance
quality, file counts, and compaction state, with no predictable
resolution
time.
2. Bounded overlay files (mini-LSM style): fixed ranges with one or more
update files.
- Benefit: avoids rewrite of base regions.
- Trade-off: same number of update files, lookups must consult
multiple files, increasing and making resolution time less predictable.
3. Global update file: immutable range files plus a shared update layer.
- Benefit: low number of extra files.
- Trade-off: updates become non-parallel and lookups still require
consulting multiple files, increasing resolution time.
About your concerns:
1. *Write amplification:* some alternatives may reduce it (2nd solution
typically does not), but at the cost of slower and less predictable reads.
2. *Maintenance complexity:* the design does not require a full rewrite.
New data can be merged into affected ranges, and oversized ranges can be
split independently.
3. *Future evolution:* the non-overlap invariant enables a fast-path
lookup. A future version could relax this, but would likely need a way to
distinguish indexes that support the fast path from those that don't.
Our experience with small files and equality deletes suggests that
recommendations alone are often not enough. A poorly maintained index can
easily become slower than a table scan, which is something we'd like
readers and optimizers to be able to rule out.
I hope this helps,
Thanks,
Peter
Shawn Chang <[email protected]> ezt írta (időpont: 2026. szept. 30.,
Sze, 9:01):
> Hi all,
>
> During the last index sync, Talat brought up a question about the
> non-overlapping invariant in the current index spec. I was thinking about
> this again today, but couldn't remember all the details from the
> discussion, and I also couldn't find the rationale clearly documented
> anywhere, so I'm shamelessly asking the same question here :)
>
> Requiring region files to be globally ordered and non-overlapping seems to
> come with a few tolls:
>
> 1.
>
> *Write amplification.* Incremental updates may require rewriting
> affected regions, especially for hot key ranges.
> 2.
>
> *Maintenance complexity.* Maintaining this invariant requires the
> index maintainer to globally repartition/sort data and rewrite affected
> regions, which makes the index maintenance implementation a bit demanding.
> 3.
>
> *Future evolution.* If readers rely on non-overlap to identify a
> single region file and early-exit, allowing overlap later will be a
> breaking change rather than simply relaxing a validation rule.
>
> I understand that the current design favors write-once-read-many workloads
> and a simpler read path. What I'm still missing is a clear description of
> the alternatives we considered, what complexity each alternative
> introduces, and why we think the current trade-off is worth making.
>
> For example, overlapping regions could lead to unbounded read
> amplification and complicated reconciliation semantics. But there also seem
> to be middle grounds, such as the bounded model Ryan mentioned in the last
> meeting: one base region file plus at most one overlay file.
>
> I think it would be useful to document this trade-off explicitly. Right
> now the non-overlap invariant is clear, but the reasoning seems less clear
> to me for: 1) choosing it over the potential alternatives like mini LSM,
> and 2) making it a format-level invariant rather than a recommended writer
> behavior.
>
>
> Thanks,
>
> Shawn
>
