Skip to main content

rypipe_core/
bounded.rs

1use std::ops::Range;
2use std::path::Path;
3use std::sync::Arc;
4
5use arrow::record_batch::RecordBatch;
6
7use crate::budget::{BudgetLedger, StreamStats};
8use crate::consumer::CollectingConsumer;
9use crate::decoder::{split_points_to_ranges, RecordParser, Splitter};
10use crate::engine::TableBuilder;
11use crate::input::InputBuffer;
12use crate::plan::ExecutionPlan;
13use crate::spill::SpillSink;
14use crate::Result;
15
16/// A memory budget expressed in bytes.
17#[derive(Clone, Copy, Debug)]
18pub struct MemoryBudget {
19    bytes: usize,
20    strict: bool,
21}
22
23impl MemoryBudget {
24    pub fn new(bytes: usize) -> Self {
25        Self {
26            bytes,
27            strict: false,
28        }
29    }
30
31    pub fn bytes(&self) -> usize {
32        self.bytes
33    }
34
35    /// Fail when an executor memory check exceeds its allocation allowance.
36    /// This does not impose an OS limit on process RSS or adapter-owned memory.
37    pub fn with_strict(mut self, strict: bool) -> Self {
38        self.strict = strict;
39        self
40    }
41
42    pub fn is_strict(&self) -> bool {
43        self.strict
44    }
45
46    pub(crate) fn share(self, count: usize) -> Self {
47        Self {
48            bytes: self.bytes / count.max(1),
49            ..self
50        }
51    }
52
53    pub(crate) fn check(self, used: usize) -> Result<()> {
54        if self.strict && used > self.bytes {
55            return Err(crate::Error::Memory {
56                used,
57                limit: self.bytes,
58            });
59        }
60        Ok(())
61    }
62}
63
64/// Internal safeguard: never request more than this many split points, so a
65/// pathological row-size estimate cannot explode per-chunk overhead. The
66/// batch count is otherwise derived from the budget, input size, and
67/// estimated bytes per row; batches may still exceed the budget when the
68/// required count exceeds this cap. Increased for 64KB streaming (50GB/64KB
69/// ≈ 800k batches); still bounded by file scan cost.
70pub const MAX_SPLIT_CHUNKS: usize = 100_000;
71
72/// Minimum rows per emitted batch when the memory budget cannot hold a
73/// single row. Batches are oversize in that regime regardless (ordinary
74/// mode permits this), and per-row batches would let batch count — and
75/// consumer cost — grow linearly with row count.
76pub const MIN_ROWS_OVERSIZE_BATCH: usize = 64;
77
78/// Parse an input in bounded batches to stay within a memory budget.
79pub struct BoundedExecutor {
80    budget: MemoryBudget,
81    split_cap: usize,
82}
83
84impl BoundedExecutor {
85    pub fn new(budget: MemoryBudget) -> Self {
86        Self {
87            budget,
88            split_cap: MAX_SPLIT_CHUNKS,
89        }
90    }
91
92    /// Override the split cap (default [`MAX_SPLIT_CHUNKS`]). Raising it may be
93    /// needed for very large files with small budgets, where capped batches
94    /// would otherwise overshoot the budget.
95    pub fn with_split_cap(mut self, cap: usize) -> Self {
96        self.split_cap = cap;
97        self
98    }
99
100    /// Payload bytes the executor targets per emitted batch. Exported
101    /// batches are exact-sized, so a single-record batch larger than this
102    /// is a flagged oversize batch (see [`StreamStats::oversize_batches`]).
103    fn batch_target_bytes(&self) -> usize {
104        (self.budget.bytes() / 64).max(1)
105    }
106
107    /// Derive chunk ranges and batch sizing from an in-memory sample of the
108    /// input. Returns `(chunk_ranges, rows_per_batch, bytes_per_row)`.
109    ///
110    /// Retained as a planning utility (and exercised by the split-cap test);
111    /// the single-pass `run_slice_spill` path no longer calls it.
112    #[allow(dead_code)]
113    fn plan_chunks(
114        &self,
115        bytes: &[u8],
116        splitter: &dyn Splitter,
117        min_chunk_bytes: usize,
118    ) -> (Vec<Range<usize>>, usize, usize, bool) {
119        let bytes_per_row = splitter
120            .estimate_bytes_per_row(&bytes[..bytes.len().min(65536)])
121            .max(1);
122        // Input, growing columns, merge buffers and Arrow output overlap.
123        let batch_bytes = self.batch_target_bytes();
124        let total_rows_est = bytes.len() / bytes_per_row;
125        // When the budget cannot hold even one row, every batch is oversize
126        // anyway (permitted in ordinary mode), so per-row batches only
127        // explode the batch count — consumers concatenating thousands of
128        // single-row batches degrade quadratically. Floor at a minimum
129        // batch size in that regime, and report the regime so consume_chunks
130        // does not adapt it back down (the capacity-based adaptive estimate
131        // is inflated by builder preallocation and collapses to 1).
132        let oversize = batch_bytes < bytes_per_row;
133        let min_rows = if oversize { MIN_ROWS_OVERSIZE_BATCH } else { 1 };
134        let rows_per_batch = (batch_bytes / bytes_per_row)
135            .max(min_rows)
136            .min(total_rows_est.max(1));
137
138        let num_batches = bytes.len().div_ceil(batch_bytes).max(1);
139        let capped = num_batches.min(self.split_cap);
140        let t = std::time::Instant::now();
141        let split_points = splitter.find_split_points_with(bytes, capped, min_chunk_bytes);
142        crate::profiling::add(crate::profiling::SPLIT, t.elapsed().as_nanos() as u64);
143        let chunks = split_points_to_ranges(&split_points, bytes.len());
144        (chunks, rows_per_batch, bytes_per_row, oversize)
145    }
146
147    /// Parse a whole byte slice in one pass through `SpillSink`, flushing
148    /// batches to `consumer` as they fill. Replaces the chunked
149    /// parse-each-chunk-then-`extend` path: no split points, no merge copy.
150    #[allow(clippy::too_many_arguments)]
151    fn run_slice_spill<P, C>(
152        &self,
153        bytes: &[u8],
154        splitter: &dyn Splitter,
155        parser: &P,
156        plan: Arc<ExecutionPlan>,
157        consumer: &mut C,
158        ledger: &mut BudgetLedger,
159        stats: &mut StreamStats,
160    ) -> Result<()>
161    where
162        P: RecordParser,
163        C: crate::consumer::BatchConsumer,
164    {
165        if bytes.is_empty() {
166            return Ok(());
167        }
168        let sample = &bytes[..bytes.len().min(65536)];
169        let bytes_per_row = splitter.estimate_bytes_per_row(sample).max(1);
170        let batch_target = self.batch_target_bytes();
171        // Budget cannot hold one row: batches are oversize regardless, so
172        // floor the batch size (per-row batches explode consumer cost) and do
173        // not flush early on capacity.
174        let oversize = batch_target < bytes_per_row;
175        let total_rows_est = bytes.len() / bytes_per_row;
176        let min_rows = if oversize {
177            MIN_ROWS_OVERSIZE_BATCH
178        } else {
179            1
180        };
181        let rows_per_batch = (batch_target / bytes_per_row)
182            .max(min_rows)
183            .min(total_rows_est.max(1));
184        let soft_cap = (self.budget.bytes() / 4).max(1);
185        let budget = self.budget.share(4);
186
187        // The engine never holds more than one batch before spilling, so size
188        // its preallocation off the batch, not the whole input. Sizing off the
189        // input would trip a strict budget at construction time.
190        let mut engine = TableBuilder::with_plan(rows_per_batch.max(64), plan);
191        engine.set_memory_budget(budget)?;
192        ledger.set_builders(engine.capacity_bytes());
193
194        let mut sink = SpillSink::new(
195            engine,
196            consumer,
197            rows_per_batch,
198            batch_target,
199            soft_cap,
200            oversize,
201            self.budget,
202            ledger,
203            stats,
204        );
205
206        std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
207            let t = std::time::Instant::now();
208            parser.validate(bytes)?;
209            crate::profiling::add(crate::profiling::VALIDATE, t.elapsed().as_nanos() as u64);
210            let t = std::time::Instant::now();
211            let result = parser.parse_chunk_generic(bytes, &mut sink);
212            crate::profiling::add(crate::profiling::PARSE, t.elapsed().as_nanos() as u64);
213            result
214        }))
215        .unwrap_or_else(|payload| {
216            let msg = if let Some(s) = payload.downcast_ref::<&str>() {
217                (*s).to_string()
218            } else if let Some(s) = payload.downcast_ref::<String>() {
219                s.clone()
220            } else {
221                "unknown panic".to_string()
222            };
223            Err(crate::Error::Parser(format!(
224                "worker panicked during bounded parse: {msg}"
225            )))
226        })?;
227
228        sink.finish_run()
229    }
230
231    /// Parse an in-memory byte slice in bounded batches, calling `consumer` per batch.
232    ///
233    /// Chunks are sliced directly from `bytes`; no file I/O occurs. This is
234    /// the streaming entry point for adapters holding decompressed data.
235    /// The budget controls batch sizing; allocator, parser, input, and Arrow
236    /// overhead can raise process RSS above this target.
237    pub fn run_bytes_stream<P, C>(
238        &self,
239        bytes: &[u8],
240        splitter: &dyn Splitter,
241        parser: P,
242        plan: Arc<ExecutionPlan>,
243        consumer: &mut C,
244    ) -> Result<()>
245    where
246        P: RecordParser + Clone + Send + Sync,
247        C: crate::consumer::BatchConsumer,
248    {
249        self.run_bytes_stream_with_stats(bytes, splitter, parser, plan, consumer)
250            .map(|_| ())
251    }
252
253    /// Like [`BoundedExecutor::run_bytes_stream`], but reports a
254    /// [`StreamStats`] summary including the peak tracked engine memory.
255    ///
256    /// The input slice is caller-owned, so it is not charged to the ledger;
257    /// `peak_tracked_bytes` covers builders and in-flight batches only.
258    pub fn run_bytes_stream_with_stats<P, C>(
259        &self,
260        bytes: &[u8],
261        splitter: &dyn Splitter,
262        parser: P,
263        plan: Arc<ExecutionPlan>,
264        consumer: &mut C,
265    ) -> Result<StreamStats>
266    where
267        P: RecordParser + Clone + Send + Sync,
268        C: crate::consumer::BatchConsumer,
269    {
270        let mut ledger = BudgetLedger::new(self.budget);
271        let mut stats = StreamStats::default();
272        self.run_bytes_stream_inner(
273            bytes,
274            splitter,
275            parser,
276            plan,
277            consumer,
278            &mut ledger,
279            &mut stats,
280        )?;
281        stats.peak_tracked_bytes = ledger.peak();
282        Ok(stats)
283    }
284
285    #[allow(clippy::too_many_arguments)]
286    fn run_bytes_stream_inner<P, C>(
287        &self,
288        bytes: &[u8],
289        splitter: &dyn Splitter,
290        parser: P,
291        plan: Arc<ExecutionPlan>,
292        consumer: &mut C,
293        ledger: &mut BudgetLedger,
294        stats: &mut StreamStats,
295    ) -> Result<()>
296    where
297        P: RecordParser + Clone + Send + Sync,
298        C: crate::consumer::BatchConsumer,
299    {
300        self.run_slice_spill(bytes, splitter, &parser, plan, consumer, ledger, stats)
301    }
302
303    /// Parse an in-memory byte slice in bounded batches, returning one
304    /// `RecordBatch` per batch.
305    ///
306    /// Chunks are sliced directly from `bytes`; no file I/O occurs. This is
307    /// the entry point for adapters holding decompressed or streamed-in data.
308    pub fn run_bytes<P>(
309        &self,
310        bytes: &[u8],
311        splitter: &dyn Splitter,
312        parser: P,
313        plan: Arc<ExecutionPlan>,
314    ) -> Result<Vec<RecordBatch>>
315    where
316        P: RecordParser + Clone + Send + Sync,
317    {
318        let batches = Vec::new();
319        let mut consumer = CollectingConsumer(batches);
320        self.run_bytes_stream(bytes, splitter, parser, plan, &mut consumer)?;
321        consumer.finish()
322    }
323
324    /// Parse `path` in batches, calling `consumer` per batch (streaming).
325    ///
326    /// Compressed inputs are decompressed up front and served via
327    /// `run_bytes_stream`. Uncompressed inputs with `mmap` use the seek-based
328    /// path with a reusable chunk buffer to keep RSS constant.
329    pub fn run_stream<P, C>(
330        &self,
331        path: &Path,
332        splitter: &dyn Splitter,
333        parser: P,
334        plan: Arc<ExecutionPlan>,
335        prefault: bool,
336        consumer: &mut C,
337    ) -> Result<()>
338    where
339        P: RecordParser + Clone + Send + Sync,
340        C: crate::consumer::BatchConsumer,
341    {
342        self.run_stream_with_stats(path, splitter, parser, plan, prefault, consumer)
343            .map(|_| ())
344    }
345
346    /// Like [`BoundedExecutor::run_stream`], but reports a [`StreamStats`]
347    /// summary including the peak tracked engine memory.
348    pub fn run_stream_with_stats<P, C>(
349        &self,
350        path: &Path,
351        splitter: &dyn Splitter,
352        parser: P,
353        plan: Arc<ExecutionPlan>,
354        prefault: bool,
355        consumer: &mut C,
356    ) -> Result<StreamStats>
357    where
358        P: RecordParser + Clone + Send + Sync,
359        C: crate::consumer::BatchConsumer,
360    {
361        let mut ledger = BudgetLedger::new(self.budget);
362        let mut stats = StreamStats::default();
363        let use_mmap = cfg!(feature = "mmap");
364        let input = InputBuffer::open(path, use_mmap, prefault)?;
365
366        #[cfg(feature = "mmap")]
367        if matches!(input, InputBuffer::Mmap(_)) {
368            self.run_mapped_stream(
369                input,
370                splitter,
371                parser,
372                plan,
373                consumer,
374                &mut ledger,
375                &mut stats,
376            )?;
377            stats.peak_tracked_bytes = ledger.peak();
378            return Ok(stats);
379        }
380
381        self.budget.share(4).check(input.len())?;
382        ledger.set_input(input.len());
383        self.run_bytes_stream_inner(
384            input.as_slice(),
385            splitter,
386            parser,
387            plan,
388            consumer,
389            &mut ledger,
390            &mut stats,
391        )?;
392        stats.peak_tracked_bytes = ledger.peak();
393        Ok(stats)
394    }
395
396    /// Parse `path` in batches, returning one `RecordBatch` per batch.
397    ///
398    /// The caller is responsible for concatenating the batches if a single
399    /// table is desired.
400    ///
401    /// Compressed inputs (see [`InputBuffer::open`]) are decompressed up
402    /// front and served from memory via [`BoundedExecutor::run_bytes`].
403    /// Uncompressed inputs on platforms with the `mmap` feature retain the
404    /// seek-based path: the mapping is dropped after planning and each chunk
405    /// is read from disk on demand, keeping resident memory low.
406    pub fn run<P>(
407        &self,
408        path: &Path,
409        splitter: &dyn Splitter,
410        parser: P,
411        plan: Arc<ExecutionPlan>,
412        prefault: bool,
413    ) -> Result<Vec<RecordBatch>>
414    where
415        P: RecordParser + Clone + Send + Sync,
416    {
417        let batches = Vec::new();
418        let mut consumer = CollectingConsumer(batches);
419        self.run_stream(path, splitter, parser, plan, prefault, &mut consumer)?;
420        consumer.finish()
421    }
422
423    /// Streaming path for mapped inputs: parse the mapping directly in one
424    /// pass. The mapping is retained (no drop-and-re-read copy); the operating
425    /// system can reclaim clean pages under pressure.
426    #[cfg(feature = "mmap")]
427    #[allow(clippy::too_many_arguments)]
428    fn run_mapped_stream<P, C>(
429        &self,
430        input: InputBuffer,
431        splitter: &dyn Splitter,
432        parser: P,
433        plan: Arc<ExecutionPlan>,
434        consumer: &mut C,
435        ledger: &mut BudgetLedger,
436        stats: &mut StreamStats,
437    ) -> Result<()>
438    where
439        P: RecordParser + Clone + Send + Sync,
440        C: crate::consumer::BatchConsumer,
441    {
442        let bytes = input.as_slice();
443        self.run_slice_spill(bytes, splitter, &parser, plan, consumer, ledger, stats)
444    }
445}
446
447#[cfg(test)]
448mod tests {
449    use super::*;
450    use crate::decoder::Splitter;
451    use crate::ExecutionPlan;
452
453    struct NewlineSplitter;
454
455    impl Splitter for NewlineSplitter {
456        fn next_record_start(&self, bytes: &[u8], from: usize) -> Option<usize> {
457            if from == 0 && !bytes.is_empty() {
458                return Some(0);
459            }
460            bytes[from.saturating_sub(1)..]
461                .iter()
462                .position(|&b| b == b'\n')
463                .map(|i| from + i + 1)
464                .filter(|&p| p < bytes.len())
465        }
466
467        fn estimate_bytes_per_row(&self, sample: &[u8]) -> usize {
468            let newlines = sample.iter().filter(|&&b| b == b'\n').count().max(1);
469            (sample.len() / newlines).max(1)
470        }
471    }
472
473    fn rows(n: usize) -> Vec<u8> {
474        "abcdefghij\n".repeat(n).into_bytes()
475    }
476
477    #[test]
478    fn test_split_cap_limits_chunk_count() {
479        let data = rows(10_000);
480        let budget = MemoryBudget::new(1024);
481
482        let default_chunks = BoundedExecutor::new(budget)
483            .plan_chunks(&data, &NewlineSplitter, crate::decoder::MIN_CHUNK_BYTES)
484            .0
485            .len();
486        assert!(
487            default_chunks > 2,
488            "uncapped run must split: {default_chunks}"
489        );
490
491        for cap in [1, 2, 3] {
492            let chunks = BoundedExecutor::new(budget)
493                .with_split_cap(cap)
494                .plan_chunks(&data, &NewlineSplitter, crate::decoder::MIN_CHUNK_BYTES)
495                .0;
496            assert!(
497                chunks.len() <= cap.max(1),
498                "cap {cap} must bound chunk count, got {}",
499                chunks.len()
500            );
501        }
502    }
503
504    /// Newline-delimited `key=value` rows, for bounded-path tests.
505    #[derive(Clone)]
506    struct KeyValueParser;
507
508    impl crate::decoder::RecordParser for KeyValueParser {
509        fn validate(&self, bytes: &[u8]) -> crate::Result<()> {
510            simdutf8::basic::from_utf8(bytes)?;
511            Ok(())
512        }
513
514        fn parse_chunk(
515            &self,
516            bytes: &[u8],
517            sink: &mut dyn crate::decoder::ColumnarSink,
518        ) -> crate::Result<()> {
519            let text = std::str::from_utf8(bytes).map_err(|e| crate::Error::Plan(e.to_string()))?;
520            for line in text.lines() {
521                if line.is_empty() {
522                    continue;
523                }
524                sink.begin_row();
525                for token in line.split_whitespace() {
526                    if let Some((k, v)) = token.split_once('=') {
527                        sink.put_field(k, crate::value::Value::Str(std::borrow::Cow::Borrowed(v)));
528                    }
529                }
530                sink.end_row();
531            }
532            Ok(())
533        }
534    }
535
536    /// Records start exactly at every multiple of 12, so chunk boundaries
537    /// never land mid-record (unlike NewlineSplitter, which is off-by-one
538    /// for this purpose).
539    struct AlignedSplitter;
540
541    impl Splitter for AlignedSplitter {
542        fn next_record_start(&self, bytes: &[u8], from: usize) -> Option<usize> {
543            let start = from.div_ceil(12) * 12;
544            (start < bytes.len()).then_some(start)
545        }
546
547        fn estimate_bytes_per_row(&self, _sample: &[u8]) -> usize {
548            12
549        }
550    }
551
552    #[test]
553    fn tiny_budget_below_row_size_keeps_batch_count_bounded() {
554        // Budget (8 bytes) smaller than a single row (~11 bytes): without the
555        // oversize floor this emits one batch per row (10_000 batches), which
556        // degrades quadratically for consumers concatenating batches.
557        // ~12 bytes/row; budget (8 bytes) cannot hold a single row. Without
558        // the oversize floor this emits one batch per row (100_000 batches),
559        // which degrades quadratically for consumers concatenating batches.
560        let data = "a=1 b=2 c=3\n".repeat(100_000).into_bytes();
561        let mut consumer = crate::consumer::CollectingConsumer(Vec::new());
562        let stats = BoundedExecutor::new(MemoryBudget::new(8))
563            .run_bytes_stream_with_stats(
564                &data,
565                &AlignedSplitter,
566                KeyValueParser,
567                std::sync::Arc::new(ExecutionPlan::new()),
568                &mut consumer,
569            )
570            .unwrap();
571        assert_eq!(stats.rows, 100_000, "all rows must be delivered");
572        assert!(
573            stats.batches <= 2048,
574            "batch count must stay far below row count for pathological              budgets, got {}",
575            stats.batches
576        );
577    }
578
579    #[test]
580    fn test_default_split_cap_is_max_split_chunks() {
581        assert_eq!(
582            BoundedExecutor::new(MemoryBudget::new(1)).split_cap,
583            MAX_SPLIT_CHUNKS
584        );
585        let plan = ExecutionPlan::new().with_max_split_chunks(7);
586        assert_eq!(plan.max_split_chunks, Some(7));
587        assert_eq!(ExecutionPlan::new().max_split_chunks, None);
588    }
589}