ailake_query/
dv.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2// Iceberg V3 Deletion Vector support — Phase B (read only).
3//
4// A Deletion Vector (DV) is a Roaring Bitmap stored inside a Puffin `.dvd` file.
5// The manifest entry carries `(path, offset, length)` that address the bitmap blob
6// bytes directly, so no full Puffin footer parse is needed for read support.
7//
8// Phase C will add write support (producing DVs on row delete operations).
9
10use ailake_catalog::provider::DeletionVector;
11use ailake_core::{AilakeError, AilakeResult};
12use ailake_store::Store;
13use roaring::RoaringBitmap;
14use std::sync::Arc;
15
16/// Fetch and deserialize a Deletion Vector bitmap from a Puffin `.dvd` file.
17///
18/// Uses a range GET (`offset..offset+length`) so only the bitmap bytes are
19/// transferred from S3 — no full file download required.
20///
21/// The returned bitmap contains the row positions (0-based within the data file)
22/// that have been deleted. Callers must filter HNSW results against this bitmap:
23/// ```ignore
24/// results.retain(|(row_id, _)| !bitmap.contains(row_id.as_u64() as u32));
25/// ```
26pub async fn load_deletion_vector(
27    store: &Arc<dyn Store>,
28    dv: &DeletionVector,
29) -> AilakeResult<RoaringBitmap> {
30    let bytes = store
31        .get_range(&dv.path, dv.offset..dv.offset + dv.length)
32        .await?;
33
34    RoaringBitmap::deserialize_from(bytes.as_ref()).map_err(|e| {
35        AilakeError::Io(std::io::Error::other(format!(
36            "ailake: failed to deserialize Deletion Vector bitmap from '{}' \
37             (offset={}, length={}): {e}",
38            dv.path, dv.offset, dv.length
39        )))
40    })
41}
42
43/// Returns true when any row in `row_ids` is deleted according to `bitmap`.
44/// Used for early-exit pruning: if zero deletions touch the candidate set, skip
45/// the per-row check.
46#[inline]
47pub fn has_deletions(bitmap: &RoaringBitmap, row_ids: &[u64]) -> bool {
48    row_ids.iter().any(|&id| bitmap.contains(id as u32))
49}
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54    use ailake_store::LocalStore;
55    use bytes::Bytes;
56    use roaring::RoaringBitmap;
57
58    fn make_bitmap_bytes(deleted: &[u32]) -> Vec<u8> {
59        let mut bm = RoaringBitmap::new();
60        for &r in deleted {
61            bm.insert(r);
62        }
63        let mut buf = Vec::new();
64        bm.serialize_into(&mut buf).unwrap();
65        buf
66    }
67
68    #[tokio::test]
69    async fn load_dv_roundtrip() {
70        let dir = tempfile::tempdir().unwrap();
71        let bitmap_bytes = make_bitmap_bytes(&[0, 5, 42, 1000]);
72
73        // Write a minimal Puffin-like file: just the bitmap bytes at a known offset.
74        // In real Puffin files there is a header and footer; the DV manifest entry
75        // gives us the exact offset+length so we only fetch those bytes.
76        let offset: u64 = 16; // simulate a 16-byte Puffin header before the blob
77        let mut file_bytes = vec![0u8; offset as usize]; // fake puffin header
78        file_bytes.extend_from_slice(&bitmap_bytes);
79
80        let dvd_path = "data/dv-0001.dvd";
81        let store: Arc<dyn Store> = Arc::new(LocalStore::new(dir.path()));
82        store.put(dvd_path, Bytes::from(file_bytes)).await.unwrap();
83
84        let dv = DeletionVector {
85            path: dvd_path.to_string(),
86            offset,
87            length: bitmap_bytes.len() as u64,
88            cardinality: 4,
89        };
90
91        let bm = load_deletion_vector(&store, &dv).await.unwrap();
92        assert!(bm.contains(0));
93        assert!(bm.contains(5));
94        assert!(bm.contains(42));
95        assert!(bm.contains(1000));
96        assert!(!bm.contains(1)); // not deleted
97        assert_eq!(bm.len(), 4);
98    }
99
100    #[test]
101    fn has_deletions_detects_overlap() {
102        let mut bm = RoaringBitmap::new();
103        bm.insert(10);
104        bm.insert(20);
105
106        assert!(has_deletions(&bm, &[5, 10, 15])); // 10 is deleted
107        assert!(!has_deletions(&bm, &[1, 2, 3])); // none deleted
108    }
109}
ailake_query/dv.rs

ailake_query/
dv.rs
