Skip to main content

uqa_execution/
parallel.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Rayon-backed parallel split + recombine, plus a branch-level
8//! [`ParallelExecutor`] for independent plan fragments.
9//!
10//! Two parallelism shapes live here:
11//!
12//! * [`run_parallel`] — chunked Vec-in / Vec-out. Used by parallel-
13//!   aware operators (large hash joins, blocking sorts, hash
14//!   aggregates) to fan out per-partition work.
15//! * [`ParallelExecutor`] — runs N independent worker closures
16//!   concurrently and returns their results in input order, allowing the
17//!   operator-tree driver
18//!   can fork independent branches (`Intersect` / `Union` /
19//!   `BayesianEvidenceFusion` / `RobustPositiveEvidencePool` /
20//!   `ProbBoolFusion` children, deep-fusion
21//!   `SignalLayer` signals) without serialising them.
22
23// The browser (emscripten) target runs single-threaded, so the rayon
24// pool is native-only and every parallel site keeps a sequential twin.
25#[cfg(not(target_os = "emscripten"))]
26use rayon::prelude::*;
27use std::sync::atomic::{AtomicBool, Ordering};
28use std::sync::Arc;
29
30#[cfg(not(target_os = "emscripten"))]
31mod pool;
32
33/// Split `input` into `num_partitions` chunks, run `worker` over each
34/// chunk in parallel, and concatenate the results in the same order
35/// the chunks were emitted in.
36pub fn run_parallel<T, R, F>(input: Vec<T>, num_partitions: usize, worker: F) -> Vec<R>
37where
38    T: Send,
39    R: Send,
40    F: Fn(Vec<T>) -> Vec<R> + Sync + Send,
41{
42    let parts = if num_partitions == 0 {
43        1
44    } else {
45        num_partitions
46    };
47    let chunk_size = input.len().div_ceil(parts).max(1);
48    let chunks: Vec<Vec<T>> = input
49        .into_iter()
50        .fold(Vec::with_capacity(parts), |mut acc, x| {
51            if acc
52                .last()
53                .map(|c: &Vec<T>| c.len() >= chunk_size)
54                .unwrap_or(true)
55            {
56                acc.push(Vec::with_capacity(chunk_size));
57            }
58            if let Some(chunk) = acc.last_mut() {
59                chunk.push(x);
60            }
61            acc
62        });
63    #[cfg(not(target_os = "emscripten"))]
64    {
65        let context = crate::statement::thread_context::StatementThreadContext::current();
66        let work = || {
67            chunks
68                .into_par_iter()
69                .map(|chunk| under_statement_thread_context(&context, || worker(chunk)))
70                .reduce(Vec::new, |mut a, b| {
71                    a.extend(b);
72                    a
73                })
74        };
75        if rayon::current_thread_index().is_some() {
76            work()
77        } else {
78            ParallelExecutor::new(parts).pool().install(work)
79        }
80    }
81    #[cfg(target_os = "emscripten")]
82    {
83        chunks.into_iter().map(worker).fold(Vec::new(), |mut a, b| {
84            a.extend(b);
85            a
86        })
87    }
88}
89
90#[cfg(test)]
91mod tests {
92    use super::*;
93
94    #[test]
95    fn run_parallel_preserves_total_elements() {
96        let v: Vec<i32> = (0..100).collect();
97        let out = run_parallel(v.clone(), 4, |chunk| {
98            chunk.into_iter().map(|x| x * 2).collect()
99        });
100        assert_eq!(out.len(), v.len());
101        assert_eq!(
102            out.iter().sum::<i32>(),
103            v.iter().map(|x| x * 2).sum::<i32>()
104        );
105    }
106
107    #[test]
108    fn run_parallel_with_zero_partitions_is_safe() {
109        let out = run_parallel(vec![1, 2, 3], 0, |c| c);
110        assert_eq!(out, vec![1, 2, 3]);
111    }
112
113    #[test]
114    fn parallel_executor_returns_results_in_branch_order() {
115        let par = ParallelExecutor::new(4);
116        let workers: Vec<Box<dyn Fn() -> i32 + Send + Sync>> =
117            vec![Box::new(|| 1), Box::new(|| 2), Box::new(|| 3)];
118        let out = par.execute_branches(&workers);
119        assert_eq!(out, vec![1, 2, 3]);
120    }
121
122    #[test]
123    fn parallel_executor_disabled_falls_back_to_sequential() {
124        let par = ParallelExecutor::new(0);
125        assert!(!par.enabled());
126        let workers: Vec<Box<dyn Fn() -> i32 + Send + Sync>> =
127            vec![Box::new(|| 10), Box::new(|| 20)];
128        let out = par.execute_branches(&workers);
129        assert_eq!(out, vec![10, 20]);
130    }
131
132    #[test]
133    fn parallel_executor_below_threshold_skips_pool() {
134        let par = ParallelExecutor::new(4);
135        let workers: Vec<Box<dyn Fn() -> i32 + Send + Sync>> = vec![Box::new(|| 99)];
136        let out = par.execute_branches(&workers);
137        assert_eq!(out, vec![99]);
138    }
139}
140
141// ---------------------------------------------------------------
142// Branch-level parallel executor
143// ---------------------------------------------------------------
144
145/// Default thread-pool size. Setting the runtime value to `0` disables
146/// parallel execution.
147pub const DEFAULT_PARALLEL_WORKERS: usize = 4;
148
149/// Minimum number of branches before parallel dispatch kicks in. Below this,
150/// sequential execution wins on overhead.
151pub const MIN_PARALLEL_BRANCHES: usize = 2;
152
153/// Branch-level parallel executor.
154///
155/// Owns a lazily created pool with the configured worker count and a shutdown flag. Clones retain the same pool. The last external owner joins every worker; if a pool task releases the last owner, its return completes termination instead. Each call to [`Self::execute_branches`] runs the supplied workers in parallel (when enabled and above the branching threshold) and collects their results in input order.
156#[derive(Debug, Clone)]
157pub struct ParallelExecutor {
158    max_workers: usize,
159    shutdown: Arc<AtomicBool>,
160    #[cfg(not(target_os = "emscripten"))]
161    pool: Arc<std::sync::OnceLock<pool::OwnedPool>>,
162}
163
164impl ParallelExecutor {
165    /// Build an executor with at most `max_workers` concurrent
166    /// branches. `0` disables parallel dispatch (every branch runs
167    /// sequentially).
168    #[must_use]
169    pub fn new(max_workers: usize) -> Self {
170        Self {
171            max_workers,
172            shutdown: Arc::new(AtomicBool::new(false)),
173            #[cfg(not(target_os = "emscripten"))]
174            pool: Arc::new(std::sync::OnceLock::new()),
175        }
176    }
177
178    /// Whether the executor will dispatch concurrently.
179    #[must_use]
180    pub fn enabled(&self) -> bool {
181        self.max_workers > 0 && !self.shutdown.load(Ordering::Acquire)
182    }
183
184    /// Mark the executor as shut down. Subsequent
185    /// [`Self::execute_branches`] calls fall back to sequential
186    /// execution.
187    pub fn shutdown(&self) {
188        self.shutdown.store(true, Ordering::Release);
189    }
190
191    #[cfg(not(target_os = "emscripten"))]
192    fn pool(&self) -> &pool::OwnedPool {
193        self.pool
194            .get_or_init(|| pool::OwnedPool::start(self.max_workers))
195    }
196
197    /// Run each `worker` and collect results in the same order. Uses
198    /// rayon's work-stealing pool when [`Self::enabled`] is `true` and
199    /// the branch count is at least [`MIN_PARALLEL_BRANCHES`];
200    /// otherwise falls back to sequential execution.
201    pub fn execute_branches<R, F>(&self, workers: &[F]) -> Vec<R>
202    where
203        R: Send,
204        F: Fn() -> R + Sync + Send,
205    {
206        if !self.enabled() || workers.len() < MIN_PARALLEL_BRANCHES {
207            return workers.iter().map(|w| w()).collect();
208        }
209        #[cfg(not(target_os = "emscripten"))]
210        {
211            let context = crate::statement::thread_context::StatementThreadContext::current();
212            self.pool().install(|| {
213                workers
214                    .par_iter()
215                    .map(|w| under_statement_thread_context(&context, w))
216                    .collect()
217            })
218        }
219        #[cfg(target_os = "emscripten")]
220        {
221            workers.iter().map(|w| w()).collect()
222        }
223    }
224}
225
226/// Run a worker under the dispatching thread's transaction clock, date order, interval style and statement cancellation.
227#[cfg(not(target_os = "emscripten"))]
228fn under_statement_thread_context<R>(
229    context: &crate::statement::thread_context::StatementThreadContext,
230    work: impl FnOnce() -> R,
231) -> R {
232    let _scope = context.enter();
233    work()
234}
235
236impl Default for ParallelExecutor {
237    fn default() -> Self {
238        Self::new(DEFAULT_PARALLEL_WORKERS)
239    }
240}
241
242#[cfg(test)]
243mod temporal_tests {
244    #[test]
245    fn temporal_input_and_output_context_reaches_each_worker() {
246        let _input = uqa_sql::expr::TemporalInputContext {
247            transaction_clock_micros: Some(123),
248            date_order: uqa_core::TemporalDateOrder::DayMonthYear,
249            interval_style: uqa_core::TemporalIntervalStyle::SqlStandard,
250        }
251        .enter();
252        let check = || {
253            assert_eq!(uqa_sql::expr::transaction_clock_micros(), Some(123));
254            assert_eq!(
255                uqa_sql::expr::temporal_interval_style(),
256                uqa_core::TemporalIntervalStyle::SqlStandard
257            );
258            let uqa_core::Value::Temporal(date) =
259                uqa_sql::expr::cast_value(&uqa_core::Value::Str("02/03/2020".into()), "date")
260                    .unwrap()
261            else {
262                panic!("date")
263            };
264            assert_eq!(date.to_sql_string(), "2020-03-02");
265        };
266        super::run_parallel(vec![1, 2, 3, 4], 4, |chunk| {
267            check();
268            chunk
269        });
270        super::ParallelExecutor::new(4).execute_branches(&[check; 4]);
271    }
272}
273
274#[cfg(test)]
275mod cancellation_tests {
276    use uqa_core::{CancellationReason, CancellationToken, QueryCancelled};
277    use uqa_sql::expr::{
278        check_statement_cancellation, statement_cancellation, StatementCancellationScope,
279    };
280
281    #[test]
282    fn statement_cancellation_reaches_each_worker() {
283        let token = CancellationToken::new();
284        token.cancel_with(CancellationReason::StatementTimeout);
285        let _statement = StatementCancellationScope::enter(token.clone());
286        let check = || {
287            assert!(statement_cancellation().is_some_and(|current| current.shares_signal(&token)));
288            assert_eq!(
289                check_statement_cancellation(),
290                Err(QueryCancelled::new(CancellationReason::StatementTimeout))
291            );
292        };
293        super::run_parallel(vec![1, 2, 3, 4], 4, |chunk| {
294            check();
295            chunk
296        });
297        super::ParallelExecutor::new(4).execute_branches(&[check; 4]);
298    }
299
300    #[test]
301    fn work_dispatched_outside_a_statement_never_observes_another_statements_context() {
302        let token = CancellationToken::new();
303        token.cancel();
304        let statement = crate::statement::thread_context::StatementThreadContext {
305            retained_rows: crate::query::sources::retained_source::RetainedRowContext::default(),
306            io: uqa_core::io_usage::IOContext::default(),
307            regex_cache: None,
308            temporal_input: uqa_sql::expr::TemporalInputContext {
309                transaction_clock_micros: Some(123),
310                ..uqa_sql::expr::TemporalInputContext::current()
311            },
312            cancellation: Some(token),
313        };
314        let _statement = statement.enter();
315        let outside = || {
316            assert!(statement_cancellation().is_none());
317            assert_eq!(check_statement_cancellation(), Ok(()));
318            assert_eq!(uqa_sql::expr::transaction_clock_micros(), None);
319        };
320        let dispatch_outside = || {
321            let _detached = crate::statement::thread_context::StatementThreadContext {
322                retained_rows: crate::query::sources::retained_source::RetainedRowContext::default(
323                ),
324                io: uqa_core::io_usage::IOContext::default(),
325                regex_cache: None,
326                temporal_input: uqa_sql::expr::TemporalInputContext {
327                    transaction_clock_micros: None,
328                    ..uqa_sql::expr::TemporalInputContext::current()
329                },
330                cancellation: None,
331            }
332            .enter();
333            super::ParallelExecutor::new(4).execute_branches(&[outside; 4]);
334            super::run_parallel(vec![1, 2, 3, 4], 4, |chunk| {
335                outside();
336                chunk
337            });
338        };
339        super::ParallelExecutor::new(4).execute_branches(&[dispatch_outside; 4]);
340        assert_eq!(
341            check_statement_cancellation(),
342            Err(QueryCancelled::USER_REQUEST)
343        );
344        assert_eq!(uqa_sql::expr::transaction_clock_micros(), Some(123));
345    }
346}