Context
Removals are ColumnFrame's worst structural disadvantage vs RowFrame (~10x slower; row store just rebuilds a slice of map pointers, column store rebuilds every column). This is root cause 3 of the column-vs-row parity investigation and was not addressed by PR #155 (which fixed access-path costs, not structural ones).
Micro data (1000 items × 10 fields, Apple M5 Pro): Removals row 15μs vs column 49-54μs; recall/filter/sort e2e shapes still favor row by 10-20% after PR #155, removals being a main contributor.
Proposal
Deferred (tombstone) deletion:
- RemoveItems only flips presence/tombstone bits + bumps a deleted counter — O(removed) instead of O(rows × cols)
- Read paths (Item / ItemColumn / ToResult / BuildInput validation) skip tombstoned rows via an index mapping
- Real compaction happens only when dead ratio crosses a threshold (e.g. 50%) or at ToResult time
Costs / risks
- Invasive: every read path must be tombstone-aware; the zero-copy ItemColumn view either compacts on read (copy) or exposes a mapping
- Index semantics: operator-visible indices must stay dense (0..n-1 post-removal) for cross-engine parity — the mapping layer must be airtight, and first-error priority in validation must remain byte-identical
- Cross-engine: go/java/cpp must adopt the same observable semantics (internal representation may differ); cross-validate + differential fuzz gate
Alternative considered
Reorder indirection (permutation vector instead of moving data) was evaluated and rejected: it breaks contiguity for the zero-copy batch view and reorder is already in-place cycle-following. Removals are the better target.
References
- llmdoc/memory/reflections/column-vs-row-parity-investigation.md (root cause 3)
Context
Removals are ColumnFrame's worst structural disadvantage vs RowFrame (~10x slower; row store just rebuilds a slice of map pointers, column store rebuilds every column). This is root cause 3 of the column-vs-row parity investigation and was not addressed by PR #155 (which fixed access-path costs, not structural ones).
Micro data (1000 items × 10 fields, Apple M5 Pro): Removals row 15μs vs column 49-54μs; recall/filter/sort e2e shapes still favor row by 10-20% after PR #155, removals being a main contributor.
Proposal
Deferred (tombstone) deletion:
Costs / risks
Alternative considered
Reorder indirection (permutation vector instead of moving data) was evaluated and rejected: it breaks contiguity for the zero-copy batch view and reorder is already in-place cycle-following. Removals are the better target.
References