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/// Split `input` into `num_partitions` chunks, run `worker` over each
31/// chunk in parallel, and concatenate the results in the same order
32/// the chunks were emitted in.
33pub fn run_parallel<T, R, F>(input: Vec<T>, num_partitions: usize, worker: F) -> Vec<R>
34where
35    T: Send,
36    R: Send,
37    F: Fn(Vec<T>) -> Vec<R> + Sync + Send,
38{
39    let parts = if num_partitions == 0 {
40        1
41    } else {
42        num_partitions
43    };
44    let chunk_size = input.len().div_ceil(parts).max(1);
45    let chunks: Vec<Vec<T>> = input
46        .into_iter()
47        .fold(Vec::with_capacity(parts), |mut acc, x| {
48            if acc
49                .last()
50                .map(|c: &Vec<T>| c.len() >= chunk_size)
51                .unwrap_or(true)
52            {
53                acc.push(Vec::with_capacity(chunk_size));
54            }
55            if let Some(chunk) = acc.last_mut() {
56                chunk.push(x);
57            }
58            acc
59        });
60    #[cfg(not(target_os = "emscripten"))]
61    {
62        let context = crate::statement::thread_context::StatementThreadContext::current();
63        chunks
64            .into_par_iter()
65            .map(|chunk| under_statement_thread_context(&context, || worker(chunk)))
66            .reduce(Vec::new, |mut a, b| {
67                a.extend(b);
68                a
69            })
70    }
71    #[cfg(target_os = "emscripten")]
72    {
73        chunks.into_iter().map(worker).fold(Vec::new(), |mut a, b| {
74            a.extend(b);
75            a
76        })
77    }
78}
79
80#[cfg(test)]
81mod tests {
82    use super::*;
83
84    #[test]
85    fn run_parallel_preserves_total_elements() {
86        let v: Vec<i32> = (0..100).collect();
87        let out = run_parallel(v.clone(), 4, |chunk| {
88            chunk.into_iter().map(|x| x * 2).collect()
89        });
90        assert_eq!(out.len(), v.len());
91        assert_eq!(
92            out.iter().sum::<i32>(),
93            v.iter().map(|x| x * 2).sum::<i32>()
94        );
95    }
96
97    #[test]
98    fn run_parallel_with_zero_partitions_is_safe() {
99        let out = run_parallel(vec![1, 2, 3], 0, |c| c);
100        assert_eq!(out, vec![1, 2, 3]);
101    }
102
103    #[test]
104    fn parallel_executor_returns_results_in_branch_order() {
105        let par = ParallelExecutor::new(4);
106        let workers: Vec<Box<dyn Fn() -> i32 + Send + Sync>> =
107            vec![Box::new(|| 1), Box::new(|| 2), Box::new(|| 3)];
108        let out = par.execute_branches(&workers);
109        assert_eq!(out, vec![1, 2, 3]);
110    }
111
112    #[test]
113    fn parallel_executor_disabled_falls_back_to_sequential() {
114        let par = ParallelExecutor::new(0);
115        assert!(!par.enabled());
116        let workers: Vec<Box<dyn Fn() -> i32 + Send + Sync>> =
117            vec![Box::new(|| 10), Box::new(|| 20)];
118        let out = par.execute_branches(&workers);
119        assert_eq!(out, vec![10, 20]);
120    }
121
122    #[test]
123    fn parallel_executor_below_threshold_skips_pool() {
124        let par = ParallelExecutor::new(4);
125        let workers: Vec<Box<dyn Fn() -> i32 + Send + Sync>> = vec![Box::new(|| 99)];
126        let out = par.execute_branches(&workers);
127        assert_eq!(out, vec![99]);
128    }
129}
130
131// ---------------------------------------------------------------
132// Branch-level parallel executor
133// ---------------------------------------------------------------
134
135/// Default thread-pool size. Setting the runtime value to `0` disables
136/// parallel execution.
137pub const DEFAULT_PARALLEL_WORKERS: usize = 4;
138
139/// Minimum number of branches before parallel dispatch kicks in. Below this,
140/// sequential execution wins on overhead.
141pub const MIN_PARALLEL_BRANCHES: usize = 2;
142
143/// Branch-level parallel executor.
144///
145/// Holds the configured worker count and a "shutdown" flag. Each call
146/// to [`Self::execute_branches`] runs the supplied workers in parallel
147/// (when enabled and above the branching threshold) and collects
148/// their results in input order.
149#[derive(Debug, Clone)]
150pub struct ParallelExecutor {
151    max_workers: usize,
152    shutdown: Arc<AtomicBool>,
153}
154
155impl ParallelExecutor {
156    /// Build an executor with at most `max_workers` concurrent
157    /// branches. `0` disables parallel dispatch (every branch runs
158    /// sequentially).
159    #[must_use]
160    pub fn new(max_workers: usize) -> Self {
161        Self {
162            max_workers,
163            shutdown: Arc::new(AtomicBool::new(false)),
164        }
165    }
166
167    /// Whether the executor will dispatch concurrently.
168    #[must_use]
169    pub fn enabled(&self) -> bool {
170        self.max_workers > 0 && !self.shutdown.load(Ordering::Acquire)
171    }
172
173    /// Mark the executor as shut down. Subsequent
174    /// [`Self::execute_branches`] calls fall back to sequential
175    /// execution.
176    pub fn shutdown(&self) {
177        self.shutdown.store(true, Ordering::Release);
178    }
179
180    /// Run each `worker` and collect results in the same order. Uses
181    /// rayon's work-stealing pool when [`Self::enabled`] is `true` and
182    /// the branch count is at least [`MIN_PARALLEL_BRANCHES`];
183    /// otherwise falls back to sequential execution.
184    pub fn execute_branches<R, F>(&self, workers: &[F]) -> Vec<R>
185    where
186        R: Send,
187        F: Fn() -> R + Sync + Send,
188    {
189        if !self.enabled() || workers.len() < MIN_PARALLEL_BRANCHES {
190            return workers.iter().map(|w| w()).collect();
191        }
192        #[cfg(not(target_os = "emscripten"))]
193        {
194            let context = crate::statement::thread_context::StatementThreadContext::current();
195            workers
196                .par_iter()
197                .map(|w| under_statement_thread_context(&context, w))
198                .collect()
199        }
200        #[cfg(target_os = "emscripten")]
201        {
202            workers.iter().map(|w| w()).collect()
203        }
204    }
205}
206
207/// Run a worker under the dispatching thread's transaction clock, date order, interval style and statement cancellation.
208#[cfg(not(target_os = "emscripten"))]
209fn under_statement_thread_context<R>(
210    context: &crate::statement::thread_context::StatementThreadContext,
211    work: impl FnOnce() -> R,
212) -> R {
213    let _scope = context.enter();
214    work()
215}
216
217impl Default for ParallelExecutor {
218    fn default() -> Self {
219        Self::new(DEFAULT_PARALLEL_WORKERS)
220    }
221}
222
223#[cfg(test)]
224mod temporal_tests {
225    #[test]
226    fn temporal_input_and_output_context_reaches_each_worker() {
227        let _input = uqa_sql::expr::TemporalInputContext {
228            transaction_clock_micros: Some(123),
229            date_order: uqa_core::TemporalDateOrder::DayMonthYear,
230            interval_style: uqa_core::TemporalIntervalStyle::SqlStandard,
231        }
232        .enter();
233        let check = || {
234            assert_eq!(uqa_sql::expr::transaction_clock_micros(), Some(123));
235            assert_eq!(
236                uqa_sql::expr::temporal_interval_style(),
237                uqa_core::TemporalIntervalStyle::SqlStandard
238            );
239            let uqa_core::Value::Temporal(date) =
240                uqa_sql::expr::cast_value(&uqa_core::Value::Str("02/03/2020".into()), "date")
241                    .unwrap()
242            else {
243                panic!("date")
244            };
245            assert_eq!(date.to_sql_string(), "2020-03-02");
246        };
247        super::run_parallel(vec![1, 2, 3, 4], 4, |chunk| {
248            check();
249            chunk
250        });
251        super::ParallelExecutor::new(4).execute_branches(&[check; 4]);
252    }
253}
254
255#[cfg(test)]
256mod cancellation_tests {
257    use uqa_core::{CancellationReason, CancellationToken, QueryCancelled};
258    use uqa_sql::expr::{
259        check_statement_cancellation, statement_cancellation, StatementCancellationScope,
260    };
261
262    #[test]
263    fn statement_cancellation_reaches_each_worker() {
264        let token = CancellationToken::new();
265        token.cancel_with(CancellationReason::StatementTimeout);
266        let _statement = StatementCancellationScope::enter(token.clone());
267        let check = || {
268            assert!(statement_cancellation().is_some_and(|current| current.shares_signal(&token)));
269            assert_eq!(
270                check_statement_cancellation(),
271                Err(QueryCancelled::new(CancellationReason::StatementTimeout))
272            );
273        };
274        super::run_parallel(vec![1, 2, 3, 4], 4, |chunk| {
275            check();
276            chunk
277        });
278        super::ParallelExecutor::new(4).execute_branches(&[check; 4]);
279    }
280
281    #[test]
282    fn work_dispatched_outside_a_statement_never_observes_another_statements_context() {
283        let token = CancellationToken::new();
284        token.cancel();
285        let statement = crate::statement::thread_context::StatementThreadContext {
286            temporal_input: uqa_sql::expr::TemporalInputContext {
287                transaction_clock_micros: Some(123),
288                ..uqa_sql::expr::TemporalInputContext::current()
289            },
290            cancellation: Some(token),
291        };
292        let _statement = statement.enter();
293        let outside = || {
294            assert!(statement_cancellation().is_none());
295            assert_eq!(check_statement_cancellation(), Ok(()));
296            assert_eq!(uqa_sql::expr::transaction_clock_micros(), None);
297        };
298        let dispatch_outside = || {
299            let _detached = crate::statement::thread_context::StatementThreadContext {
300                temporal_input: uqa_sql::expr::TemporalInputContext {
301                    transaction_clock_micros: None,
302                    ..uqa_sql::expr::TemporalInputContext::current()
303                },
304                cancellation: None,
305            }
306            .enter();
307            super::ParallelExecutor::new(4).execute_branches(&[outside; 4]);
308            super::run_parallel(vec![1, 2, 3, 4], 4, |chunk| {
309                outside();
310                chunk
311            });
312        };
313        super::ParallelExecutor::new(4).execute_branches(&[dispatch_outside; 4]);
314        assert_eq!(
315            check_statement_cancellation(),
316            Err(QueryCancelled::USER_REQUEST)
317        );
318        assert_eq!(uqa_sql::expr::transaction_clock_micros(), Some(123));
319    }
320}