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
