Compaction can keep an index entry pointing at fragment 0 row 0 after that fragment is removed

[amunra]

Description

MissingAddrs (rust/lance/src/dataset/optimize/remapping.rs:92) walks a compaction rewrite group and yields the row addresses that were not rewritten. The caller maps each of those to None, meaning "this row is gone".

When its input iterator of rewritten addresses runs out, it substitutes 0:

// rust/lance/src/dataset/optimize/remapping.rs:129-132
// If we've exhausted row_addrs but we aren't done then use 0 which
// is guaranteed to not match because that would mean that row_addrs
// was empty and we check for that earlier.
self.row_addrs.next().unwrap_or(0)

Two things are wrong with that comment.

1. Nobody checks that row_addrs is non-empty. The assert! in the constructor (remapping.rs:105) checks that fragments is non-empty. The only non-test caller, transpose_row_ids_from_digest (remapping.rs:171, calling MissingAddrs::new at remapping.rs:196), passes row_addrs straight through, and so does its caller transpose_row_addrs (remapping.rs:161), reached from commit_compaction at rust/lance/src/dataset/optimize.rs:2874.

2. 0 is a real row address. RowAddress::new_from_parts is ((fragment_id as u64) << 32) | row_offset (rust/lance-core/src/utils/address.rs:37-38), so fragment 0 offset 0 is 0. The loop's expected_row_addr starts at first_frag.id * RowAddress::FRAGMENT_SIZE (remapping.rs:109), which is also 0 for fragment 0.

So on the first iteration for a group whose first old fragment is fragment 0 and which rewrote nothing, the sentinel's fragment id equals current_fragment.id and its value equals expected_row_addr. Both "report this address" branches are skipped and (0, 0) is consumed as if it had been rewritten. The remaining offsets are reported normally.

The map the indices then receive has no key 0. Per the documented semantics of RowAddrRemap::get (rust/lance-core/src/utils/row_addr_remap.rs:56-61), a missing key means "the address is not affected by this remap (keep it unchanged)" — not "deleted". Index remap code follows that: rust/lance-index/src/scalar/ngram.rs:377-381 keeps row_id on None, and rust/lance-index/src/scalar/label_list.rs:225 does mapping.get(addr).unwrap_or(Some(addr)). The index therefore keeps an entry addressing a fragment that the same commit removed. I verified the remap contents, not the query-level effect; what a stale entry does to results depends on the index type and I did not measure it.

Only IndexRemapMode::Direct is affected. IndexRemapMode::Compact reports (0, 0) as deleted for the same rewrite group. Direct is the default (optimize.rs:185-186 and optimize.rs:332), and the two modes are meant to be interchangeable — test_compact_matches_transpose (remapping.rs:448) asserts they agree, but only for a group that did rewrite rows.

Reachability: the input shape is a rewrite group whose rewritten-address set is empty and whose first old fragment is fragment 0 — in practice, a group in which every row was deleted. I reached it through the public distributed-compaction API: a RewriteResult (optimize.rs:2239, all fields public) with an empty serialized row_addrs, passed to commit_compaction. The second test below does exactly that and fails. Compact answers correctly for the same input, because it decides deletedness from fragment-range membership and so has no sentinel to collide with. RewriteResult and commit_compaction are also re-exported through the Python and Java bindings, so the shape is constructible from those too. Reading the code, the in-process Dataset::delete + compact_files path does not produce it: FileFragment::write_deletions returns None once the deletion vector covers every row (rust/lance/src/dataset/fragment.rs:2588-2593), so a fully deleted fragment is dropped rather than left for compaction. I did not test that path.

A one-line fix is to use a sentinel that cannot be a real address: self.row_addrs.next().unwrap_or(RowAddress::TOMBSTONE_ROW). TOMBSTONE_ROW (rust/lance-core/src/utils/address.rs:31) has TOMBSTONE_FRAG as its fragment half, and that is documented as a fragment id that will never be used (address.rs:29), so the sentinel's fragment id never matches the fragment being scanned and the existing frag != current_fragment.id branch reports every remaining address. With that change both tests below pass and cargo test -p lance --lib dataset::optimize (146 tests) and cargo test -p lance-core --lib row_addr_remap stay green.

Steps to reproduce

Add to `mod tests` in `rust/lance/src/dataset/optimize/remapping.rs`:


/// A rewrite group in which every row was deleted rewrites no rows, so
/// every address it covers must be reported as missing and mapped to
/// `None` (deleted). Fragment 0 offset 0 is not, because the sentinel that
/// `MissingAddrs` substitutes when `row_addrs` is exhausted is itself the
/// address (0, 0).
#[test]
fn test_missing_addrs_nothing_rewritten() {
    use lance_core::utils::row_addr_remap::GroupInput;

    let fmt = |addrs: &[u64]| {
        addrs
            .iter()
            .map(|a| RowAddress::new_from_u64(*a).to_string())
            .collect::<Vec<_>>()
    };
    let all_deleted = |id: u64| {
        vec![FragDigest {
            id,
            physical_rows: 3,
            num_deleted_rows: 3,
        }]
    };

    // Control: the same group, but with a first fragment id that is not 0.
    let frag1 = all_deleted(1);
    let missing1 = MissingAddrs::new(std::iter::empty(), &frag1).collect::<Vec<_>>();
    assert_eq!(fmt(&missing1), vec!["(1, 0)", "(1, 1)", "(1, 2)"]);

    let frag0 = all_deleted(0);
    let missing0 = MissingAddrs::new(std::iter::empty(), &frag0).collect::<Vec<_>>();
    assert_eq!(fmt(&missing0), vec!["(0, 0)", "(0, 1)", "(0, 2)"]);

    // What the caller ends up with: (0, 0) must map to "deleted", not be
    // absent (absent means "not affected by this remap, keep as-is").
    let map = transpose_row_ids_from_digest(RoaringTreemap::new(), &frag0, &[]);
    assert_eq!(map.get(&0), Some(&None));

    // The two remap modes must agree on the same rewrite group.
    let compact = RowAddrRemap::compact([GroupInput {
        rewritten_old_row_addrs: RoaringTreemap::new(),
        old_frag_ids: vec![0],
        new_frags: vec![],
    }])
    .unwrap();
    assert_eq!(compact.get(0), RowAddrRemap::direct(map).get(0));
}


`cargo test -p lance --lib test_missing_addrs_nothing_rewritten`:


running 1 test
test dataset::optimize::remapping::tests::test_missing_addrs_nothing_rewritten ... FAILED

failures:

---- dataset::optimize::remapping::tests::test_missing_addrs_nothing_rewritten stdout ----

thread 'dataset::optimize::remapping::tests::test_missing_addrs_nothing_rewritten' panicked at
rust/lance/src/dataset/optimize/remapping.rs:637:9:
assertion `left == right` failed
  left: ["(0, 1)", "(0, 2)"]
 right: ["(0, 0)", "(0, 1)", "(0, 2)"]

test result: FAILED. 0 passed; 1 failed; 0 ignored; 0 measured; 3431 filtered out; finished in 0.06s


The fragment-1 control on the line above passes: with a first fragment id other than 0 the sentinel's fragment id never matches, so every address is reported.

The same thing through the public API. Add to `mod tests` in `rust/lance/src/dataset/optimize.rs`:


/// Records the remap that compaction hands to the indices.
#[derive(Debug, Default, Clone)]
struct CaptureRemap {
    captured: Arc<std::sync::Mutex<Option<RowAddrRemap>>>,
}

#[async_trait]
impl IndexRemapper for CaptureRemap {
    async fn remap_indices(
        &self,
        remap: RowAddrRemap,
        _: &[u64],
    ) -> Result<Vec<RemappedIndex>> {
        *self.captured.lock().unwrap() = Some(remap);
        Ok(Vec::new())
    }
}

#[async_trait]
impl IndexRemapperOptions for CaptureRemap {
    async fn create_remapper(&self, _: &Dataset) -> Result<Option<Box<dyn IndexRemapper>>> {
        Ok(Some(Box::new(self.clone())))
    }
}

/// A rewrite group in which every row was deleted rewrites nothing, so the
/// remap compaction hands to the indices must report every address the
/// group covers as deleted (`Some(None)`). Under `IndexRemapMode::Direct`
/// the address (0, 0) is instead absent, which every index remap reads as
/// "not affected by this remap, keep the address unchanged".
#[rstest]
#[case::fragment_zero_direct(0, IndexRemapMode::Direct)]
#[case::fragment_zero_compact(0, IndexRemapMode::Compact)]
#[case::fragment_one_direct(1, IndexRemapMode::Direct)]
#[case::fragment_one_compact(1, IndexRemapMode::Compact)]
#[tokio::test]
async fn test_remap_of_fully_deleted_rewrite_group(
    #[case] compacted_fragment: u32,
    #[case] mode: IndexRemapMode,
) {
    const ROWS_PER_FRAG: u32 = 10;
    let mut dataset = lance_datagen::gen_batch()
        .col("id", lance_datagen::array::step::<Int32Type>())
        .into_ram_dataset(FragmentCount::from(2), FragmentRowCount::from(ROWS_PER_FRAG))
        .await
        .unwrap();

    let original = dataset
        .get_fragments()
        .into_iter()
        .find(|frag| frag.id() as u32 == compacted_fragment)
        .unwrap()
        .metadata;
    // Nothing was read, so no row addresses were rewritten and no new
    // fragment was produced.
    let mut nothing_rewritten = Vec::new();
    RoaringTreemap::new()
        .serialize_into(&mut nothing_rewritten)
        .unwrap();
    let task = RewriteResult {
        metrics: CompactionMetrics {
            fragments_removed: 1,
            ..Default::default()
        },
        new_fragments: vec![],
        read_version: dataset.manifest.version,
        original_fragments: vec![original],
        row_addrs: Some(nothing_rewritten),
    };

    let capture = CaptureRemap::default();
    commit_compaction(
        &mut dataset,
        vec![task],
        Arc::new(capture.clone()),
        &CompactionOptions {
            index_remap_mode: mode,
            ..Default::default()
        },
    )
    .await
    .unwrap();
    assert_eq!(
        dataset.count_rows(None).await.unwrap(),
        ROWS_PER_FRAG as usize
    );

    let remap = capture.captured.lock().unwrap().clone().unwrap();
    for offset in 0..ROWS_PER_FRAG {
        let addr = u64::from(RowAddress::new_from_parts(compacted_fragment, offset));
        assert_eq!(
            remap.get(addr),
            Some(None),
            "({compacted_fragment}, {offset}) was not reported as deleted, mode {mode:?}"
        );
    }
}


`cargo test -p lance --lib test_remap_of_fully_deleted_rewrite_group -- --test-threads 1`:


running 4 tests
test dataset::optimize::tests::test_remap_of_fully_deleted_rewrite_group::case_1_fragment_zero_direct ... FAILED
test dataset::optimize::tests::test_remap_of_fully_deleted_rewrite_group::case_2_fragment_zero_compact ... ok
test dataset::optimize::tests::test_remap_of_fully_deleted_rewrite_group::case_3_fragment_one_direct ... ok
test dataset::optimize::tests::test_remap_of_fully_deleted_rewrite_group::case_4_fragment_one_compact ... ok

failures:

---- dataset::optimize::tests::test_remap_of_fully_deleted_rewrite_group::case_1_fragment_zero_direct stdout ----

thread 'dataset::optimize::tests::test_remap_of_fully_deleted_rewrite_group::case_1_fragment_zero_direct' panicked at
rust/lance/src/dataset/optimize.rs:4217:13:
assertion `left == right` failed: (0, 0) was not reported as deleted, mode Direct
  left: None
 right: Some(None)

test result: FAILED. 3 passed; 1 failed; 0 ignored; 0 measured; 3428 filtered out; finished in 0.09s

Expected behavior

MissingAddrs reports every address in the rewrite group's old fragments that was not rewritten, including (0, 0), so the remap handed to index remapping maps it to None (deleted). IndexRemapMode::Direct and IndexRemapMode::Compact return the same answer for the same rewrite group.

Lance version

Reproduced on main at commit 8a145b348

Language binding

Rust

Environment

No response

Logs / traceback