Feature request: multi_get() for batch key lookups

[lveillard]

Use Case

I'm building an embedded graph database (BlitzStore) on top of fjall. A common operation is fetching multiple units by ID after an index scan:

// Current: N individual gets
let mut units = Vec::with_capacity(ids.len());
for &id in ids {
    if let Some(unit) = partition.get(id.to_be_bytes())? {
        units.push(unit);
    }
}

Proposed API

// Batch lookup
let results: Vec<Option<Slice>> = partition.multi_get(&[key1, key2, key3])?;

Expected Benefits

Based on RocksDB benchmarks, batch lookups can be 2-3x faster than individual gets due to:

• Shared bloom filter checks across keys
• Better cache locality
• Reduced per-call overhead

Workaround

For contiguous IDs we use range scans, but for non-contiguous IDs (common after filtering) we fall back to N individual gets.

Priority

This is the only missing feature we identified after reviewing fjall 3.0 - everything else we needed (contains_key, .rev(), approximate_len, OCC transactions) is already there. Great work on 3.0! 🎉

[marvin-j97]

There is an open WIP implementation using io_uring (fjall-rs/lsm-tree#226), however I'm not really ready to put io_uring and async I/O into the core library. So for now using a non-async implementation would be fine.

[lveillard]

Sync implementation would be perfect for our use case! We're fully sync in the embedded path anyway.

If it helps, here's our current workaround pattern:

// We detect contiguous IDs for range scan, else fall back to N gets
pub fn batch_get(&self, ids: &[UnitId]) -> Result<Vec<Unit>> {
    if Self::is_contiguous(ids) {
        return self.scan_id_range(min, max);  // O(1) range scan
    }
    // Fallback: N individual gets
    ids.iter().filter_map(|id| self.get(*id).ok().flatten()).collect()
}

A native multi_get that batches bloom filter checks would eliminate the N individual lookups for non-contiguous IDs. Happy to test a PR if you want early feedback!

[marvin-j97]

Blocked by fjall-rs/lsm-tree#96

[plugd-in]

It would be helpful if you could "toggle" locality/caching on a transaction. Then, rather than the API being, for example, multi_get<I, K>(&self, iter: I) -> Iter where I: IntoIter<K>, K: AsRef<[u8]>, we could get a Snapshot, call cached_lookup(&mut self, cache: bool) and expect our calls to benefit from the same performance gain as a multi_get. I'm considering configurable caching because there might be some overhead if we expect our data to not be local to other keys.

For my use-case, I have keys that are close together, where I don't want to necessarily do a range/prefix scan, but don't want to need to keep looking for the key/data if I know they are close by.

[marvin-j97]

It would be helpful if you could "toggle" locality/caching on a transaction. Then, rather than the API being, for example, multi_get<I, K>(&self, iter: I) -> Iter where I: IntoIter<K>, K: AsRef<[u8]>, we could get a Snapshot, call cached_lookup(&mut self, cache: bool) and expect our calls to benefit from the same performance gain as a multi_get. I'm considering configurable caching because there might be some overhead if we expect our data to not be local to other keys.

For my use-case, I have keys that are close together, where I don't want to necessarily do a range/prefix scan, but don't want to need to keep looking for the key/data if I know they are close by.

I honestly don't quite understand how that would really work. The entire idea of multi_get is to batch cache & file descriptor lookups, and not going through the SuperVersion lock for each key. When you don't know all the keys in advance, it doesn't really work.

[plugd-in]

I honestly don't quite understand how that would really work. The entire idea of multi_get is to batch cache & file descriptor lookups, and not going through the SuperVersion lock for each key. When you don't know all the keys in advance, it doesn't really work.

I guess it depends on how the file descriptors and the keys and whatnot are cached. My thought was to cache wherever prior keys have been found (e.g. in the transaction struct), and then when you do another lookup, check the caches first. It does seem like knowing all the keys in advance would make this batch lookup more efficient, though. For my use-case, I don't really know what keys I need in advance, just that they are close together (in terms of ordering and general access patterns), so I wouldn't really benefit as much from a multi_get.

I guess, another way to put it is: If we can do some of the caching within the transaction, such that get could also benefit, while multi_get would still benefit from knowing the keys ahead of time, that would be nice. If it's not feasible to implement this in this fashion, then get is still perfectly fine for me, and my comment was irrelevant to the design of multi_get.