Skip to main content

slatedb_estimates/
lib.rs

1//! Approximate range statistics built on top of SlateDB metadata APIs.
2
3mod range_stats;
4
5pub use crate::range_stats::RangeStats;
6
7/// Controls which storage sources and refinement strategy are used for size estimates.
8#[derive(Debug, Clone)]
9pub struct SizeApproximationOptions {
10    /// Whether to include mutable and immutable memtables.
11    ///
12    /// Memtable estimation is currently unsupported, so setting this to `true`
13    /// causes size estimation to return an invalid-argument error.
14    pub include_memtables: bool,
15    /// Whether to include on-disk SST files.
16    ///
17    /// This must currently be `true` because memtable estimation is unsupported.
18    pub include_files: bool,
19    /// Maximum tolerated coarse-estimate contribution before refining a partial SST.
20    ///
21    /// Values must be finite and in `0.0..=1.0`. A partial SST whose coarse
22    /// contribution is smaller than this fraction of the total coarse estimate
23    /// may be counted without block-level refinement. Use `0.0` to refine every
24    /// partial SST.
25    pub error_margin: f64,
26}
27
28impl Default for SizeApproximationOptions {
29    fn default() -> Self {
30        Self {
31            include_memtables: false,
32            include_files: true,
33            error_margin: 0.10,
34        }
35    }
36}
37
38#[cfg(test)]
39mod tests {
40    use std::sync::Arc;
41    use std::time::Duration;
42
43    use slatedb::bytes::Bytes;
44    use slatedb::compactor::{
45        CompactionScheduler, CompactionSchedulerSupplier, CompactionSpec, CompactorBuilder,
46        CompactorStateView, SourceId,
47    };
48    use slatedb::config::{CompactorOptions, FlushOptions, FlushType, Settings, SstBlockSize};
49    use slatedb::object_store::memory::InMemory;
50    use slatedb::{ByteRangeBounds, Db, ErrorKind, SstReader};
51
52    use super::{RangeStats, SizeApproximationOptions};
53
54    #[tokio::test]
55    async fn approximate_size_returns_zero_for_missing_range() {
56        let (range_stats, _, _) = seeded_stats("/size-zero", 16, 1).await;
57
58        let size = range_stats
59            .get_approximate_size(
60                Bytes::from_static(b"z00")..Bytes::from_static(b"z99"),
61                &SizeApproximationOptions::default(),
62            )
63            .await
64            .unwrap();
65
66        assert_eq!(size, 0);
67    }
68
69    #[tokio::test]
70    async fn approximate_size_requires_a_source() {
71        let (range_stats, _, _) = seeded_stats("/size-sources", 16, 1).await;
72        let opts = SizeApproximationOptions {
73            include_memtables: false,
74            include_files: false,
75            error_margin: 0.0,
76        };
77
78        let err = range_stats
79            .get_approximate_size(
80                Bytes::from_static(b"k00")..Bytes::from_static(b"k10"),
81                &opts,
82            )
83            .await
84            .unwrap_err();
85
86        assert_eq!(err.kind(), ErrorKind::Invalid);
87        assert!(err.to_string().contains("at least one"));
88    }
89
90    #[tokio::test]
91    async fn approximate_size_rejects_memtables_for_now() {
92        let (range_stats, _, _) = seeded_stats("/size-memtables", 16, 1).await;
93        let opts = SizeApproximationOptions {
94            include_memtables: true,
95            include_files: true,
96            error_margin: 0.0,
97        };
98
99        let err = range_stats
100            .get_approximate_size(
101                Bytes::from_static(b"k00")..Bytes::from_static(b"k10"),
102                &opts,
103            )
104            .await
105            .unwrap_err();
106
107        assert_eq!(err.kind(), ErrorKind::Invalid);
108        assert!(err.to_string().contains("include_memtables"));
109    }
110
111    #[tokio::test]
112    async fn approximate_size_validates_error_margin() {
113        let (range_stats, _, _) = seeded_stats("/size-margin", 16, 1).await;
114        let opts = SizeApproximationOptions {
115            include_memtables: false,
116            include_files: true,
117            error_margin: 1.5,
118        };
119
120        let err = range_stats
121            .get_approximate_size(
122                Bytes::from_static(b"k00")..Bytes::from_static(b"k10"),
123                &opts,
124            )
125            .await
126            .unwrap_err();
127
128        assert_eq!(err.kind(), ErrorKind::Invalid);
129        assert!(err.to_string().contains("1.5"));
130    }
131
132    #[tokio::test]
133    async fn approximate_size_refines_partial_ranges() {
134        let (range_stats, _, _) = seeded_stats("/size-refined", 20, 2).await;
135        let full = range_stats
136            .get_approximate_size(
137                Bytes::from_static(b"k00")..Bytes::from_static(b"k20"),
138                &SizeApproximationOptions::default(),
139            )
140            .await
141            .unwrap();
142        let refined = range_stats
143            .get_approximate_size(
144                Bytes::from_static(b"k03")..Bytes::from_static(b"k17"),
145                &SizeApproximationOptions::default(),
146            )
147            .await
148            .unwrap();
149
150        assert!(refined < full);
151    }
152
153    #[tokio::test]
154    async fn larger_error_margin_can_skip_refinement() {
155        let (range_stats, _, _) = seeded_stats("/size-skip", 20, 2).await;
156        let refined = range_stats
157            .get_approximate_size(
158                Bytes::from_static(b"k03")..Bytes::from_static(b"k17"),
159                &SizeApproximationOptions {
160                    include_memtables: false,
161                    include_files: true,
162                    error_margin: 0.0,
163                },
164            )
165            .await
166            .unwrap();
167        let coarse = range_stats
168            .get_approximate_size(
169                Bytes::from_static(b"k03")..Bytes::from_static(b"k17"),
170                &SizeApproximationOptions {
171                    include_memtables: false,
172                    include_files: true,
173                    error_margin: 0.75,
174                },
175            )
176            .await
177            .unwrap();
178
179        assert!(coarse >= refined);
180    }
181
182    #[tokio::test]
183    async fn estimate_key_count_matches_full_scan_for_put_only_data() {
184        let (range_stats, _, expected_full) = seeded_stats("/keycount-full", 12, 1).await;
185
186        let count = range_stats
187            .estimate_key_count(Bytes::from_static(b"k00")..Bytes::from_static(b"k12"))
188            .await
189            .unwrap();
190
191        assert_eq!(count, expected_full);
192    }
193
194    #[tokio::test]
195    async fn estimate_key_count_for_block_aligned_range_matches_scan() {
196        let path = "/keycount-aligned";
197        let object_store: Arc<dyn slatedb::object_store::ObjectStore> = Arc::new(InMemory::new());
198        let db = build_seeded_db(path, Arc::clone(&object_store), 18, 1).await;
199
200        let reader = SstReader::new(path, Arc::clone(&object_store), None, None);
201        let manifest = db.manifest();
202        let view = manifest.l0().front().unwrap();
203        let sst_file = reader.open_with_handle(view.sst.clone()).unwrap();
204        let index = sst_file.index().await.unwrap();
205        assert!(index.len() > 2, "test data should span multiple blocks");
206
207        let start = Bytes::copy_from_slice(index.get(1).unwrap().1);
208        let end = Bytes::copy_from_slice(index.get(2).unwrap().1);
209
210        let expected = scan_count(&db, start.clone()..end.clone()).await;
211        let range_stats = RangeStats::new(Arc::new(db), path, object_store, None, None);
212
213        let count = range_stats.estimate_key_count(start..end).await.unwrap();
214        assert_eq!(count, expected);
215    }
216
217    #[tokio::test]
218    async fn estimate_key_count_is_monotonic_for_put_only_data() {
219        let (range_stats, _, _) = seeded_stats("/keycount-monotonic", 18, 1).await;
220        let full = range_stats
221            .estimate_key_count(Bytes::from_static(b"k00")..Bytes::from_static(b"k18"))
222            .await
223            .unwrap();
224        let partial = range_stats
225            .estimate_key_count(Bytes::from_static(b"k03")..Bytes::from_static(b"k10"))
226            .await
227            .unwrap();
228
229        assert!(partial <= full);
230    }
231
232    #[tokio::test]
233    async fn estimate_key_count_is_a_storage_level_estimate_for_overlapping_l0() {
234        let path = "/keycount-overlapping-l0";
235        let object_store: Arc<dyn slatedb::object_store::ObjectStore> = Arc::new(InMemory::new());
236        let db = Db::builder(path, Arc::clone(&object_store))
237            .with_sst_block_size(SstBlockSize::Block1Kib)
238            .build()
239            .await
240            .unwrap();
241
242        db.put(b"k", b"value-0").await.unwrap();
243        flush_memtable(&db).await;
244        db.put(b"k", b"value-1").await.unwrap();
245        flush_memtable(&db).await;
246        db.delete(b"k").await.unwrap();
247        flush_memtable(&db).await;
248
249        let scan_count = scan_count(&db, Bytes::from_static(b"k")..Bytes::from_static(b"l")).await;
250        let range_stats = RangeStats::new(Arc::new(db), path, object_store, None, None);
251        let estimated = range_stats
252            .estimate_key_count(Bytes::from_static(b"k")..Bytes::from_static(b"l"))
253            .await
254            .unwrap();
255
256        assert_eq!(scan_count, 0);
257        assert_eq!(estimated, 2);
258    }
259
260    #[tokio::test(flavor = "multi_thread", worker_threads = 2)]
261    async fn estimate_key_count_matches_scan_for_compacted_put_only_data() {
262        let path = "/keycount-compacted";
263        let object_store: Arc<dyn slatedb::object_store::ObjectStore> = Arc::new(InMemory::new());
264        let db = Db::builder(path, Arc::clone(&object_store))
265            .with_settings(compacting_settings())
266            .with_compactor_builder(
267                CompactorBuilder::new(path, Arc::clone(&object_store))
268                    .with_options(compactor_options())
269                    .with_scheduler_supplier(Arc::new(CompactL0AfterTwoSchedulerSupplier)),
270            )
271            .with_sst_block_size(SstBlockSize::Block1Kib)
272            .build()
273            .await
274            .unwrap();
275
276        for i in 0..24 {
277            let key = format!("k{i:02}");
278            let value = format!("value-{i:02}-{}", "x".repeat(192));
279            db.put(key.as_bytes(), value.as_bytes()).await.unwrap();
280
281            if i == 11 {
282                flush_memtable(&db).await;
283            }
284        }
285        flush_memtable(&db).await;
286        wait_for_compaction(&db).await;
287
288        let manifest = db.manifest();
289        assert!(manifest.l0().is_empty());
290        assert!(!manifest.compacted().is_empty());
291
292        let range = Bytes::from_static(b"k00")..Bytes::from_static(b"k24");
293        let expected = scan_count(&db, range.clone()).await;
294        let range_stats = RangeStats::new(Arc::new(db), path, object_store, None, None);
295
296        let estimated = range_stats.estimate_key_count(range).await.unwrap();
297        assert_eq!(estimated, expected);
298    }
299
300    #[tokio::test]
301    async fn constructors_produce_identical_results() {
302        let path_one = "/constructors-one";
303        let path_two = "/constructors-two";
304        let store_one: Arc<dyn slatedb::object_store::ObjectStore> = Arc::new(InMemory::new());
305        let store_two: Arc<dyn slatedb::object_store::ObjectStore> = Arc::new(InMemory::new());
306        let db_one = build_seeded_db(path_one, Arc::clone(&store_one), 18, 2).await;
307        let db_two = build_seeded_db(path_two, Arc::clone(&store_two), 18, 2).await;
308
309        let with_new = RangeStats::new(
310            Arc::new(db_one),
311            path_one,
312            Arc::clone(&store_one),
313            None,
314            None,
315        );
316        let reader = SstReader::new(path_two, Arc::clone(&store_two), None, None);
317        let with_parts = RangeStats::from_db_parts(Arc::new(db_two), reader);
318
319        let range = Bytes::from_static(b"k03")..Bytes::from_static(b"k17");
320        let opts = SizeApproximationOptions::default();
321
322        let size_one = with_new
323            .get_approximate_size(range.clone(), &opts)
324            .await
325            .unwrap();
326        let size_two = with_parts
327            .get_approximate_size(range.clone(), &opts)
328            .await
329            .unwrap();
330        let count_one = with_new.estimate_key_count(range.clone()).await.unwrap();
331        let count_two = with_parts.estimate_key_count(range).await.unwrap();
332
333        assert_eq!(size_one, size_two);
334        assert_eq!(count_one, count_two);
335    }
336
337    #[tokio::test]
338    async fn approximate_size_with_prefix_matches_range_equivalent() {
339        let (range_stats, _, _) = seeded_stats("/size-prefix", 20, 2).await;
340        let opts = SizeApproximationOptions::default();
341
342        let prefix_result = range_stats
343            .get_approximate_size_with_prefix(b"k0", &opts)
344            .await
345            .unwrap();
346        let range_result = range_stats
347            .get_approximate_size(Bytes::from_static(b"k0")..Bytes::from_static(b"k1"), &opts)
348            .await
349            .unwrap();
350
351        assert_eq!(prefix_result, range_result);
352    }
353
354    #[tokio::test]
355    async fn estimate_key_count_with_prefix_matches_range_equivalent() {
356        let (range_stats, _, _) = seeded_stats("/keycount-prefix", 20, 2).await;
357
358        let prefix_result = range_stats
359            .estimate_key_count_with_prefix(b"k0")
360            .await
361            .unwrap();
362        let range_result = range_stats
363            .estimate_key_count(Bytes::from_static(b"k0")..Bytes::from_static(b"k1"))
364            .await
365            .unwrap();
366
367        assert_eq!(prefix_result, range_result);
368    }
369
370    #[tokio::test]
371    async fn prefix_methods_handle_empty_prefix() {
372        let (range_stats, _, expected_full) = seeded_stats("/prefix-empty", 12, 1).await;
373
374        let count = range_stats
375            .estimate_key_count_with_prefix(b"")
376            .await
377            .unwrap();
378
379        assert_eq!(count, expected_full);
380    }
381
382    async fn seeded_stats(
383        path: &'static str,
384        key_count: usize,
385        flushes: usize,
386    ) -> (RangeStats, Arc<dyn slatedb::object_store::ObjectStore>, u64) {
387        let object_store: Arc<dyn slatedb::object_store::ObjectStore> = Arc::new(InMemory::new());
388        let db = build_seeded_db(path, Arc::clone(&object_store), key_count, flushes).await;
389        let expected_full =
390            scan_count(&db, Bytes::from_static(b"k00")..Bytes::from_static(b"zzz")).await;
391        let range_stats =
392            RangeStats::new(Arc::new(db), path, Arc::clone(&object_store), None, None);
393        (range_stats, object_store, expected_full)
394    }
395
396    async fn build_seeded_db(
397        path: &'static str,
398        object_store: Arc<dyn slatedb::object_store::ObjectStore>,
399        key_count: usize,
400        flushes: usize,
401    ) -> Db {
402        let db = Db::builder(path, object_store)
403            .with_sst_block_size(SstBlockSize::Block1Kib)
404            .build()
405            .await
406            .unwrap();
407
408        let chunk = key_count.div_ceil(flushes.max(1));
409        for i in 0..key_count {
410            let key = format!("k{i:02}");
411            let value = format!("value-{i:02}-{}", "x".repeat(192));
412            db.put(key.as_bytes(), value.as_bytes()).await.unwrap();
413
414            if (i + 1) % chunk == 0 {
415                flush_memtable(&db).await;
416            }
417        }
418
419        if chunk == 0 || !key_count.is_multiple_of(chunk) {
420            flush_memtable(&db).await;
421        }
422
423        db
424    }
425
426    async fn flush_memtable(db: &Db) {
427        db.flush_with_options(FlushOptions {
428            flush_type: FlushType::MemTable,
429        })
430        .await
431        .unwrap();
432    }
433
434    fn compacting_settings() -> Settings {
435        Settings {
436            flush_interval: Some(Duration::from_millis(10)),
437            compactor_options: None,
438            garbage_collector_options: None,
439            ..Settings::default()
440        }
441    }
442
443    fn compactor_options() -> CompactorOptions {
444        CompactorOptions {
445            poll_interval: Duration::from_millis(10),
446            max_concurrent_compactions: 1,
447            ..CompactorOptions::default()
448        }
449    }
450
451    async fn wait_for_compaction(db: &Db) {
452        tokio::time::timeout(Duration::from_secs(10), async {
453            loop {
454                let manifest = db.manifest();
455                if manifest.l0().is_empty() && !manifest.compacted().is_empty() {
456                    return;
457                }
458                tokio::time::sleep(Duration::from_millis(10)).await;
459            }
460        })
461        .await
462        .expect("timed out waiting for compaction");
463    }
464
465    struct CompactL0AfterTwoSchedulerSupplier;
466
467    impl CompactionSchedulerSupplier for CompactL0AfterTwoSchedulerSupplier {
468        fn compaction_scheduler(
469            &self,
470            _options: &CompactorOptions,
471        ) -> Box<dyn CompactionScheduler + Send + Sync> {
472            Box::new(CompactL0AfterTwoScheduler)
473        }
474    }
475
476    struct CompactL0AfterTwoScheduler;
477
478    impl CompactionScheduler for CompactL0AfterTwoScheduler {
479        fn propose(&self, state: &CompactorStateView) -> Vec<CompactionSpec> {
480            let manifest = state.manifest();
481            if manifest.l0().len() < 2 {
482                return Vec::new();
483            }
484
485            let sources = manifest
486                .l0()
487                .iter()
488                .map(|view| SourceId::SstView(view.id))
489                .collect();
490            let destination = manifest.compacted().first().map_or(0, |run| run.id + 1);
491
492            vec![CompactionSpec::new(sources, destination)]
493        }
494    }
495
496    async fn scan_count<T>(db: &Db, range: T) -> u64
497    where
498        T: ByteRangeBounds + Send,
499    {
500        let mut iter = db.scan(range).await.unwrap();
501        let mut count = 0u64;
502        while iter.next().await.unwrap().is_some() {
503            count += 1;
504        }
505        count
506    }
507}