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 { MIN_ROWS_OVERSIZE_BATCH } else { 1 };
177        let rows_per_batch = (batch_target / bytes_per_row)
178            .max(min_rows)
179            .min(total_rows_est.max(1));
180        let soft_cap = (self.budget.bytes() / 4).max(1);
181        let budget = self.budget.share(4);
182
183        // The engine never holds more than one batch before spilling, so size
184        // its preallocation off the batch, not the whole input. Sizing off the
185        // input would trip a strict budget at construction time.
186        let mut engine = TableBuilder::with_plan(rows_per_batch.max(64), plan);
187        engine.set_memory_budget(budget)?;
188        ledger.set_builders(engine.capacity_bytes());
189
190        let mut sink = SpillSink::new(
191            engine,
192            consumer,
193            rows_per_batch,
194            batch_target,
195            soft_cap,
196            oversize,
197            self.budget,
198            ledger,
199            stats,
200        );
201
202        std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
203            let t = std::time::Instant::now();
204            parser.validate(bytes)?;
205            crate::profiling::add(crate::profiling::VALIDATE, t.elapsed().as_nanos() as u64);
206            let t = std::time::Instant::now();
207            let result = parser.parse_chunk_generic(bytes, &mut sink);
208            crate::profiling::add(crate::profiling::PARSE, t.elapsed().as_nanos() as u64);
209            result
210        }))
211        .unwrap_or_else(|payload| {
212            let msg = if let Some(s) = payload.downcast_ref::<&str>() {
213                (*s).to_string()
214            } else if let Some(s) = payload.downcast_ref::<String>() {
215                s.clone()
216            } else {
217                "unknown panic".to_string()
218            };
219            Err(crate::Error::Parser(format!(
220                "worker panicked during bounded parse: {msg}"
221            )))
222        })?;
223
224        sink.finish_run()
225    }
226
227    /// Parse an in-memory byte slice in bounded batches, calling `consumer` per batch.
228    ///
229    /// Chunks are sliced directly from `bytes`; no file I/O occurs. This is
230    /// the streaming entry point for adapters holding decompressed data.
231    /// The budget controls batch sizing; allocator, parser, input, and Arrow
232    /// overhead can raise process RSS above this target.
233    pub fn run_bytes_stream<P, C>(
234        &self,
235        bytes: &[u8],
236        splitter: &dyn Splitter,
237        parser: P,
238        plan: Arc<ExecutionPlan>,
239        consumer: &mut C,
240    ) -> Result<()>
241    where
242        P: RecordParser + Clone + Send + Sync,
243        C: crate::consumer::BatchConsumer,
244    {
245        self.run_bytes_stream_with_stats(bytes, splitter, parser, plan, consumer)
246            .map(|_| ())
247    }
248
249    /// Like [`BoundedExecutor::run_bytes_stream`], but reports a
250    /// [`StreamStats`] summary including the peak tracked engine memory.
251    ///
252    /// The input slice is caller-owned, so it is not charged to the ledger;
253    /// `peak_tracked_bytes` covers builders and in-flight batches only.
254    pub fn run_bytes_stream_with_stats<P, C>(
255        &self,
256        bytes: &[u8],
257        splitter: &dyn Splitter,
258        parser: P,
259        plan: Arc<ExecutionPlan>,
260        consumer: &mut C,
261    ) -> Result<StreamStats>
262    where
263        P: RecordParser + Clone + Send + Sync,
264        C: crate::consumer::BatchConsumer,
265    {
266        let mut ledger = BudgetLedger::new(self.budget);
267        let mut stats = StreamStats::default();
268        self.run_bytes_stream_inner(
269            bytes,
270            splitter,
271            parser,
272            plan,
273            consumer,
274            &mut ledger,
275            &mut stats,
276        )?;
277        stats.peak_tracked_bytes = ledger.peak();
278        Ok(stats)
279    }
280
281    #[allow(clippy::too_many_arguments)]
282    fn run_bytes_stream_inner<P, C>(
283        &self,
284        bytes: &[u8],
285        splitter: &dyn Splitter,
286        parser: P,
287        plan: Arc<ExecutionPlan>,
288        consumer: &mut C,
289        ledger: &mut BudgetLedger,
290        stats: &mut StreamStats,
291    ) -> Result<()>
292    where
293        P: RecordParser + Clone + Send + Sync,
294        C: crate::consumer::BatchConsumer,
295    {
296        self.run_slice_spill(bytes, splitter, &parser, plan, consumer, ledger, stats)
297    }
298
299    /// Parse an in-memory byte slice in bounded batches, returning one
300    /// `RecordBatch` per batch.
301    ///
302    /// Chunks are sliced directly from `bytes`; no file I/O occurs. This is
303    /// the entry point for adapters holding decompressed or streamed-in data.
304    pub fn run_bytes<P>(
305        &self,
306        bytes: &[u8],
307        splitter: &dyn Splitter,
308        parser: P,
309        plan: Arc<ExecutionPlan>,
310    ) -> Result<Vec<RecordBatch>>
311    where
312        P: RecordParser + Clone + Send + Sync,
313    {
314        let batches = Vec::new();
315        let mut consumer = CollectingConsumer(batches);
316        self.run_bytes_stream(bytes, splitter, parser, plan, &mut consumer)?;
317        consumer.finish()
318    }
319
320    /// Parse `path` in batches, calling `consumer` per batch (streaming).
321    ///
322    /// Compressed inputs are decompressed up front and served via
323    /// `run_bytes_stream`. Uncompressed inputs with `mmap` use the seek-based
324    /// path with a reusable chunk buffer to keep RSS constant.
325    pub fn run_stream<P, C>(
326        &self,
327        path: &Path,
328        splitter: &dyn Splitter,
329        parser: P,
330        plan: Arc<ExecutionPlan>,
331        prefault: bool,
332        consumer: &mut C,
333    ) -> Result<()>
334    where
335        P: RecordParser + Clone + Send + Sync,
336        C: crate::consumer::BatchConsumer,
337    {
338        self.run_stream_with_stats(path, splitter, parser, plan, prefault, consumer)
339            .map(|_| ())
340    }
341
342    /// Like [`BoundedExecutor::run_stream`], but reports a [`StreamStats`]
343    /// summary including the peak tracked engine memory.
344    pub fn run_stream_with_stats<P, C>(
345        &self,
346        path: &Path,
347        splitter: &dyn Splitter,
348        parser: P,
349        plan: Arc<ExecutionPlan>,
350        prefault: bool,
351        consumer: &mut C,
352    ) -> Result<StreamStats>
353    where
354        P: RecordParser + Clone + Send + Sync,
355        C: crate::consumer::BatchConsumer,
356    {
357        let mut ledger = BudgetLedger::new(self.budget);
358        let mut stats = StreamStats::default();
359        let use_mmap = cfg!(feature = "mmap");
360        let input = InputBuffer::open(path, use_mmap, prefault)?;
361
362        #[cfg(feature = "mmap")]
363        if matches!(input, InputBuffer::Mmap(_)) {
364            self.run_mapped_stream(
365                input,
366                splitter,
367                parser,
368                plan,
369                consumer,
370                &mut ledger,
371                &mut stats,
372            )?;
373            stats.peak_tracked_bytes = ledger.peak();
374            return Ok(stats);
375        }
376
377        self.budget.share(4).check(input.len())?;
378        ledger.set_input(input.len());
379        self.run_bytes_stream_inner(
380            input.as_slice(),
381            splitter,
382            parser,
383            plan,
384            consumer,
385            &mut ledger,
386            &mut stats,
387        )?;
388        stats.peak_tracked_bytes = ledger.peak();
389        Ok(stats)
390    }
391
392    /// Parse `path` in batches, returning one `RecordBatch` per batch.
393    ///
394    /// The caller is responsible for concatenating the batches if a single
395    /// table is desired.
396    ///
397    /// Compressed inputs (see [`InputBuffer::open`]) are decompressed up
398    /// front and served from memory via [`BoundedExecutor::run_bytes`].
399    /// Uncompressed inputs on platforms with the `mmap` feature retain the
400    /// seek-based path: the mapping is dropped after planning and each chunk
401    /// is read from disk on demand, keeping resident memory low.
402    pub fn run<P>(
403        &self,
404        path: &Path,
405        splitter: &dyn Splitter,
406        parser: P,
407        plan: Arc<ExecutionPlan>,
408        prefault: bool,
409    ) -> Result<Vec<RecordBatch>>
410    where
411        P: RecordParser + Clone + Send + Sync,
412    {
413        let batches = Vec::new();
414        let mut consumer = CollectingConsumer(batches);
415        self.run_stream(path, splitter, parser, plan, prefault, &mut consumer)?;
416        consumer.finish()
417    }
418
419    /// Streaming path for mapped inputs: parse the mapping directly in one
420    /// pass. The mapping is retained (no drop-and-re-read copy); the operating
421    /// system can reclaim clean pages under pressure.
422    #[cfg(feature = "mmap")]
423    #[allow(clippy::too_many_arguments)]
424    fn run_mapped_stream<P, C>(
425        &self,
426        input: InputBuffer,
427        splitter: &dyn Splitter,
428        parser: P,
429        plan: Arc<ExecutionPlan>,
430        consumer: &mut C,
431        ledger: &mut BudgetLedger,
432        stats: &mut StreamStats,
433    ) -> Result<()>
434    where
435        P: RecordParser + Clone + Send + Sync,
436        C: crate::consumer::BatchConsumer,
437    {
438        let bytes = input.as_slice();
439        self.run_slice_spill(bytes, splitter, &parser, plan, consumer, ledger, stats)
440    }
441}
442
443#[cfg(test)]
444mod tests {
445    use super::*;
446    use crate::decoder::Splitter;
447    use crate::ExecutionPlan;
448
449    struct NewlineSplitter;
450
451    impl Splitter for NewlineSplitter {
452        fn next_record_start(&self, bytes: &[u8], from: usize) -> Option<usize> {
453            if from == 0 && !bytes.is_empty() {
454                return Some(0);
455            }
456            bytes[from.saturating_sub(1)..]
457                .iter()
458                .position(|&b| b == b'\n')
459                .map(|i| from + i + 1)
460                .filter(|&p| p < bytes.len())
461        }
462
463        fn estimate_bytes_per_row(&self, sample: &[u8]) -> usize {
464            let newlines = sample.iter().filter(|&&b| b == b'\n').count().max(1);
465            (sample.len() / newlines).max(1)
466        }
467    }
468
469    fn rows(n: usize) -> Vec<u8> {
470        "abcdefghij\n".repeat(n).into_bytes()
471    }
472
473    #[test]
474    fn test_split_cap_limits_chunk_count() {
475        let data = rows(10_000);
476        let budget = MemoryBudget::new(1024);
477
478        let default_chunks = BoundedExecutor::new(budget)
479            .plan_chunks(&data, &NewlineSplitter, crate::decoder::MIN_CHUNK_BYTES)
480            .0
481            .len();
482        assert!(
483            default_chunks > 2,
484            "uncapped run must split: {default_chunks}"
485        );
486
487        for cap in [1, 2, 3] {
488            let chunks = BoundedExecutor::new(budget)
489                .with_split_cap(cap)
490                .plan_chunks(&data, &NewlineSplitter, crate::decoder::MIN_CHUNK_BYTES)
491                .0;
492            assert!(
493                chunks.len() <= cap.max(1),
494                "cap {cap} must bound chunk count, got {}",
495                chunks.len()
496            );
497        }
498    }
499
500    /// Newline-delimited `key=value` rows, for bounded-path tests.
501    #[derive(Clone)]
502    struct KeyValueParser;
503
504    impl crate::decoder::RecordParser for KeyValueParser {
505        fn validate(&self, bytes: &[u8]) -> crate::Result<()> {
506            simdutf8::basic::from_utf8(bytes)?;
507            Ok(())
508        }
509
510        fn parse_chunk(
511            &self,
512            bytes: &[u8],
513            sink: &mut dyn crate::decoder::ColumnarSink,
514        ) -> crate::Result<()> {
515            let text = std::str::from_utf8(bytes).map_err(|e| crate::Error::Plan(e.to_string()))?;
516            for line in text.lines() {
517                if line.is_empty() {
518                    continue;
519                }
520                sink.begin_row();
521                for token in line.split_whitespace() {
522                    if let Some((k, v)) = token.split_once('=') {
523                        sink.put_field(k, crate::value::Value::Str(std::borrow::Cow::Borrowed(v)));
524                    }
525                }
526                sink.end_row();
527            }
528            Ok(())
529        }
530    }
531
532    /// Records start exactly at every multiple of 12, so chunk boundaries
533    /// never land mid-record (unlike NewlineSplitter, which is off-by-one
534    /// for this purpose).
535    struct AlignedSplitter;
536
537    impl Splitter for AlignedSplitter {
538        fn next_record_start(&self, bytes: &[u8], from: usize) -> Option<usize> {
539            let start = from.div_ceil(12) * 12;
540            (start < bytes.len()).then_some(start)
541        }
542
543        fn estimate_bytes_per_row(&self, _sample: &[u8]) -> usize {
544            12
545        }
546    }
547
548    #[test]
549    fn tiny_budget_below_row_size_keeps_batch_count_bounded() {
550        // Budget (8 bytes) smaller than a single row (~11 bytes): without the
551        // oversize floor this emits one batch per row (10_000 batches), which
552        // degrades quadratically for consumers concatenating batches.
553        // ~12 bytes/row; budget (8 bytes) cannot hold a single row. Without
554        // the oversize floor this emits one batch per row (100_000 batches),
555        // which degrades quadratically for consumers concatenating batches.
556        let data = "a=1 b=2 c=3\n".repeat(100_000).into_bytes();
557        let mut consumer = crate::consumer::CollectingConsumer(Vec::new());
558        let stats = BoundedExecutor::new(MemoryBudget::new(8))
559            .run_bytes_stream_with_stats(
560                &data,
561                &AlignedSplitter,
562                KeyValueParser,
563                std::sync::Arc::new(ExecutionPlan::new()),
564                &mut consumer,
565            )
566            .unwrap();
567        assert_eq!(stats.rows, 100_000, "all rows must be delivered");
568        assert!(
569            stats.batches <= 2048,
570            "batch count must stay far below row count for pathological              budgets, got {}",
571            stats.batches
572        );
573    }
574
575    #[test]
576    fn test_default_split_cap_is_max_split_chunks() {
577        assert_eq!(
578            BoundedExecutor::new(MemoryBudget::new(1)).split_cap,
579            MAX_SPLIT_CHUNKS
580        );
581        let plan = ExecutionPlan::new().with_max_split_chunks(7);
582        assert_eq!(plan.max_split_chunks, Some(7));
583        assert_eq!(ExecutionPlan::new().max_split_chunks, None);
584    }
585}