1mod range_stats;
4
5pub use crate::range_stats::RangeStats;
6
7#[derive(Debug, Clone)]
9pub struct SizeApproximationOptions {
10 pub include_memtables: bool,
15 pub include_files: bool,
19 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}