Skip to main content

rete_core/sparql/
par_agg.rs

1//! A grouped query on several threads.
2//!
3//! `SELECT … (COUNT(*) AS ?n) WHERE { … } GROUP BY …` over ten million rows
4//! spends its time per row: decoding a term, a string function, a lookup in
5//! the row's graph, a probe of a join. None of it depends on any other row,
6//! and the evaluator ran all of it on one thread.
7//!
8//! Here the scan that drives the pattern is cut into slices. Each worker
9//! thread takes slices in order and evaluates the *same* plan over one slice
10//! at a time, in its own context (its own term memos). What the slices have
11//! in common is made once, by the calling thread, and read by all of them:
12//! rows are `Send + Sync`, so a hash join's table, a basic graph pattern's
13//! prefix, or the list of graphs a block visits is one copy behind an `Arc`
14//! ([`crate::row::Shard::shared`]).
15//!
16//! **Two ways to aggregate.**
17//!
18//! - *Merged groups.* Each worker folds its slices into partial aggregates
19//!   and the calling thread merges them in slice order, which is scan order,
20//!   so every aggregate sees its rows in the order the single fold does (see
21//!   the partial aggregation notes in `aggregate`). The slices are fixed by
22//!   the file ([`SHARDS`]), not by the machine.
23//! - *One fold.* When an aggregate keeps a set of the values it saw
24//!   (`COUNT(DISTINCT …)`, `GROUP_CONCAT(DISTINCT …)`), or a slice holds more
25//!   groups than may wait for a merge ([`MAX_SHARD_GROUPS`]), the workers do
26//!   the per-row work and send their rows, cut down to the slots the fold
27//!   reads, to the calling thread, which folds them slice after slice exactly
28//!   as it folds the one scan. Memory is the single fold's, plus the rows in
29//!   flight ([`ROWS_AHEAD`]).
30//!
31//! **Which queries.** The driving scan has to sit where the algebra
32//! distributes over a union of its rows. The path from the top of the pattern
33//! to it goes through FILTER and BIND, UNION (each branch split, or run in
34//! slice 0 alone when it cannot be), a sub-select that only projects, and
35//! the left side of a join, an OPTIONAL or a MINUS. An EXISTS in a FILTER
36//! has its solutions evaluated once, by the first slice that needs them
37//! (`ExistsCell`); a MINUS has its right side indexed once, as a join has.
38//! The right side of that join is either what the single
39//! thread looks up once per left row (`GRAPH ?g { … }` with `?g` bound on the
40//! left, a path from a bound endpoint, a BGP whose cheapest pattern is a fat
41//! scan), or it is built once into the hash table every slice probes. The
42//! scan itself is:
43//!
44//! - a basic graph pattern: its one pattern's tiles; or, with several
45//!   patterns, the tiles of the pattern `BgpSolutions` streams, the prefix
46//!   rows that look the last pattern up, or a range of subjects when two
47//!   large patterns are merge-joined on theirs (`bgp::shard_bgp_rows`);
48//! - a block under `GRAPH ?g`: a one-pattern scan over the quad orders, the
49//!   subjects of a class probe, the graphs its required pattern is found in,
50//!   or every graph.
51//!
52//! **Checked, not assumed.** The plan nodes are named by address and every one
53//! of them must be reached exactly once per slice ([`crate::row::Shard`]). A
54//! pushdown that evaluates a node some other way would hand its rows to every
55//! slice; this is checked on a dry run before any thread starts and again on
56//! every slice, and a miss means the query runs on one thread as before. The
57//! dry run measures first and builds second: a query whose scan is too short
58//! to split never pays for a table the single thread would not build.
59//!
60//! **Over a network.** A slice reads its tiles ahead in one batch (a cut scan
61//! starts at the largest window; a restricted quad scan faults its own
62//! tiles), so a remote file is cut into fewer, larger slices
63//! ([`REMOTE_SHARDS`], each at least [`REMOTE_MIN_TILES`] tiles) and a short
64//! scan stays one scan. A join that looks something up per row is not split
65//! there: lookups from several threads read half as many bytes again as one
66//! thread's in order. Nor is a walk of every graph, which fetches its section
67//! in bulk.
68//!
69//! **Memory.** Workers run at most `2 × workers` slices ahead of the calling
70//! thread. Each worker's term memos are capped at its share of one
71//! context's. A table built for all slices is the table the single thread's
72//! hash join builds.
73//!
74//! Native builds with the `parallel` feature only. `RETE_QUERY_THREADS=1` (or
75//! [`set_query_threads`]) turns it off.
76
77use std::sync::atomic::{AtomicUsize, Ordering};
78
79/// How many worker threads a grouped query may use; 0 = not set.
80static THREADS: AtomicUsize = AtomicUsize::new(0);
81
82/// Grouped queries answered on several threads so far, process-wide.
83static SHARDED: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(0);
84
85/// How many grouped queries (subqueries included) have been answered on
86/// several threads so far, in this process. A counter for tests and
87/// diagnostics: whether a query took that path is the difference around it.
88pub fn sharded_queries() -> u64 {
89    SHARDED.load(Ordering::Relaxed)
90}
91
92/// The most threads used when nothing says otherwise.
93const DEFAULT_MAX_THREADS: usize = 16;
94
95/// Set how many threads a grouped query may run on (`1`: always one thread;
96/// `0`: the default, the machine's cores up to 16, or `RETE_QUERY_THREADS`).
97/// Process-wide. The rows a query returns do not depend on it.
98pub fn set_query_threads(n: usize) {
99    THREADS.store(n, Ordering::Relaxed);
100}
101
102/// How many threads a grouped query may run on: see [`set_query_threads`].
103pub fn query_threads() -> usize {
104    match THREADS.load(Ordering::Relaxed) {
105        0 => default_threads(),
106        n => n,
107    }
108}
109
110fn default_threads() -> usize {
111    static DEFAULT: std::sync::OnceLock<usize> = std::sync::OnceLock::new();
112    *DEFAULT.get_or_init(|| {
113        if let Some(n) = std::env::var("RETE_QUERY_THREADS")
114            .ok()
115            .and_then(|v| v.trim().parse::<usize>().ok())
116            .filter(|&n| n > 0)
117        {
118            return n;
119        }
120        std::thread::available_parallelism()
121            .map(|n| n.get())
122            .unwrap_or(1)
123            .min(DEFAULT_MAX_THREADS)
124    })
125}
126
127/// The group rows of `sel` (as `aggregate` returns them), computed on several
128/// threads; `None` when the query is not one this can split, or the attempt
129/// was given up: the caller then aggregates as it always did.
130#[cfg(not(feature = "parallel"))]
131pub(super) fn aggregate_shards<'q>(
132    _ctx: &'q crate::row::Ctx<'q>,
133    _sel: &'q super::Select,
134    _active: &'q crate::index::GraphIndex,
135    _nf: Option<&'q [String]>,
136    _g: &'q super::GroupSpec,
137) -> Option<Vec<crate::row::Row>> {
138    None
139}
140
141#[cfg(feature = "parallel")]
142pub(super) use threaded::aggregate_shards;
143
144#[cfg(feature = "parallel")]
145mod threaded {
146    use std::cell::Cell;
147    use std::collections::BTreeMap;
148    use std::sync::atomic::{AtomicBool, Ordering};
149    use std::sync::{mpsc, Condvar, Mutex};
150
151    use super::super::aggregate::{
152        aggregate_folded, aggregate_partial, apply_pre, fold_slots, mergeable, Merger,
153        PartialGroups,
154    };
155    use super::super::eval::{
156        certain_bound, eval_plan_iter, expr_has_exists, only_projects, path_endpoint_bound,
157        possible_bound, query_ctx, shares_certain_var,
158    };
159    use super::super::{diag, ExistsCell, FExpr, GraphTarget, GroupSpec, Plan, Select};
160    use super::query_threads;
161    use crate::index::GraphIndex;
162    use crate::row::{Ctx, Row, SharedState, MEMO_CAP_BYTES};
163
164    /// How many slices the driving scan is cut into (fewer when it has fewer
165    /// tiles). Fixed, so the slices, and with them the order in which a
166    /// floating-point SUM adds up, do not depend on the machine's core count.
167    const SHARDS: usize = 64;
168
169    /// The slices of a file read over a network: as many as the most workers,
170    /// each at least [`REMOTE_MIN_TILES`] tiles of the driving scan.
171    const REMOTE_SHARDS: usize = 16;
172
173    /// The fewest tiles a slice of a remote file's scan holds (about half a
174    /// megabyte): below it the requests would outnumber the single scan's.
175    const REMOTE_MIN_TILES: usize = 8;
176
177    /// The most groups one slice may hold when the slices' groups are merged:
178    /// see the module notes on memory.
179    const MAX_SHARD_GROUPS: usize = 100_000;
180
181    /// Rows per message when the workers send rows to the one fold.
182    const ROW_CHUNK: usize = 2048;
183
184    /// About how many rows may wait for the one fold, over all workers.
185    const ROWS_AHEAD: usize = 1 << 21;
186
187    /// How many slices the driving scan is cut into when the rows go to one
188    /// fold. The fold sees the scan's rows in the scan's order whatever the
189    /// slices are, so they can be small: a worker then finishes a slice
190    /// before its share of the waiting rows is full, and does not stop to
191    /// wait for the fold.
192    const ROW_SHARDS: usize = 1024;
193
194    /// A worker's stack: the main thread's usual 8 MiB, not a spawned
195    /// thread's 2 MiB, since a worker evaluates the same (possibly deeply
196    /// nested) plan the calling thread would.
197    const WORKER_STACK: usize = 8 << 20;
198
199    /// The floor of a worker's share of the term memos.
200    const MIN_MEMO_CAP: usize = 4 << 20;
201
202    thread_local! {
203        /// Set on a worker thread: a subquery it evaluates must not fan out again.
204        static IN_WORKER: Cell<bool> = const { Cell::new(false) };
205    }
206
207    /// The plan nodes a grouped query is split on, by address.
208    #[derive(Default)]
209    struct Split {
210        leaves: Vec<usize>,
211        only_first: Vec<usize>,
212        /// Joins and MINUSes whose right side is built once for all slices.
213        builds: Vec<usize>,
214        /// EXISTS sub-plans of the filters on the way to the scan: each is
215        /// evaluated once, by the first slice that needs it.
216        exists: Vec<usize>,
217    }
218
219    /// The EXISTS sub-plans of `e` (not the ones nested inside them, which
220    /// belong to their own evaluation).
221    fn exists_plans(e: &FExpr, out: &mut Vec<usize>) {
222        match e {
223            FExpr::Exists(plan) => out.push(plan.as_ref() as *const Plan as usize),
224            FExpr::Var(_) | FExpr::Const(_) | FExpr::Bound(_) => {}
225            FExpr::Not(a) => exists_plans(a, out),
226            FExpr::Arith(_, a, b)
227            | FExpr::SameTerm(a, b)
228            | FExpr::Compare(_, a, b)
229            | FExpr::And(a, b)
230            | FExpr::Or(a, b) => {
231                exists_plans(a, out);
232                exists_plans(b, out);
233            }
234            FExpr::If(c, t, f) => {
235                exists_plans(c, out);
236                exists_plans(t, out);
237                exists_plans(f, out);
238            }
239            FExpr::In(x, list) => {
240                exists_plans(x, out);
241                list.iter().for_each(|e| exists_plans(e, out));
242            }
243            FExpr::Func(_, args) | FExpr::Coalesce(args) => {
244                args.iter().for_each(|e| exists_plans(e, out));
245            }
246        }
247    }
248
249    /// May a condition (a FILTER, an OPTIONAL's) sit on the way to the scan?
250    /// Yes without EXISTS. With it, on a local file: its sub-plans are noted
251    /// and each is evaluated once for all slices. Over a network not: an
252    /// EXISTS probed per row would be one request per row from every thread.
253    fn condition(ctx: &Ctx, e: &FExpr, out: &mut Split) -> bool {
254        if !expr_has_exists(e) {
255            return true;
256        }
257        if ctx.rete.reads_are_remote() {
258            return false;
259        }
260        exists_plans(e, &mut out.exists);
261        true
262    }
263
264    /// Find the driving scans under `plan` (see the module notes); `index` is
265    /// the graph `plan` is evaluated on. `false`: this pattern cannot be
266    /// split, and `out` holds nothing to rely on.
267    fn split(
268        ctx: &Ctx,
269        plan: &Plan,
270        index: &GraphIndex,
271        from_named: bool,
272        out: &mut Split,
273    ) -> bool {
274        let node = plan as *const Plan as usize;
275        match plan {
276            Plan::Bgp(patterns) if !patterns.is_empty() => {
277                out.leaves.push(node);
278                true
279            }
280            // Any block under a graph variable: its one-pattern scan, the
281            // graphs its required pattern is found in, or every graph, sliced.
282            Plan::Graph(GraphTarget::Var(v), _) => {
283                if ctx.slots.slot(v).is_some() {
284                    out.leaves.push(node);
285                    true
286                } else {
287                    false
288                }
289            }
290            Plan::Graph(GraphTarget::Named(iri), inner) => match ctx.rete.graph_index(iri) {
291                Some(gi) => split(ctx, inner, gi, from_named, out),
292                None => false,
293            },
294            Plan::Filter(e, inner) => {
295                let mark = out.exists.len();
296                if condition(ctx, e, out) && split(ctx, inner, index, from_named, out) {
297                    true
298                } else {
299                    out.exists.truncate(mark);
300                    false
301                }
302            }
303            Plan::Extend(_, e, inner) => {
304                !expr_has_exists(e) && split(ctx, inner, index, from_named, out)
305            }
306            // A sub-select that only projects: the scan is in its pattern,
307            // which has its own variables' slots.
308            Plan::Subquery(sub) if only_projects(sub) => {
309                let sub_ctx = query_ctx(ctx.rete, sub);
310                split(&sub_ctx, &sub.plan, index, from_named, out)
311            }
312            // The left side holds the scan; the right side is probed per row
313            // where the single thread does that, else indexed once.
314            Plan::Minus(l, r) => {
315                let lcert = certain_bound(ctx, l, ctx.slots.len());
316                let probed = matches!(&**r, Plan::Bgp(patterns)
317                    if crate::bgp::CorrelatedProbe::new(ctx, index, patterns, &lcert).is_some());
318                if probed {
319                    return !ctx.rete.reads_are_remote() && split(ctx, l, index, from_named, out);
320                }
321                if !buildable(r) {
322                    return false;
323                }
324                let mark = out.builds.len();
325                out.builds.push(node);
326                if split(ctx, l, index, from_named, out) {
327                    true
328                } else {
329                    out.builds.truncate(mark);
330                    false
331                }
332            }
333            Plan::Union(l, r) => {
334                // A branch that cannot be split runs whole, in slice 0 alone.
335                let mut branch = |p: &Plan| {
336                    let mark = (
337                        out.leaves.len(),
338                        out.only_first.len(),
339                        out.builds.len(),
340                        out.exists.len(),
341                    );
342                    if split(ctx, p, index, from_named, out) {
343                        true
344                    } else {
345                        out.leaves.truncate(mark.0);
346                        out.only_first.truncate(mark.1);
347                        out.builds.truncate(mark.2);
348                        out.exists.truncate(mark.3);
349                        out.only_first.push(p as *const Plan as usize);
350                        false
351                    }
352                };
353                let l = branch(l);
354                let r = branch(r);
355                l || r
356            }
357            Plan::Join(l, r) => join(ctx, node, l, r, index, from_named, out),
358            Plan::LeftJoin(l, r, cond) => {
359                let mark = out.exists.len();
360                if cond.as_ref().is_none_or(|c| condition(ctx, c, out))
361                    && join(ctx, node, l, r, index, from_named, out)
362                {
363                    true
364                } else {
365                    out.exists.truncate(mark);
366                    false
367                }
368            }
369            _ => false,
370        }
371    }
372
373    /// `l ⋈ r` (or `l OPTIONAL r`) with the driving scan under `l`. The right
374    /// side is either looked up once per left row, as the single thread would
375    /// (nothing is built), or built once into a hash table every slice probes.
376    fn join(
377        ctx: &Ctx,
378        node: usize,
379        l: &Plan,
380        r: &Plan,
381        index: &GraphIndex,
382        from_named: bool,
383        out: &mut Split,
384    ) -> bool {
385        if looked_up_per_row(ctx, index, l, r) {
386            // Over a network every lookup is a request, and lookups from
387            // several threads at once read more than one thread's do in
388            // order (measured: half as many bytes again): not split.
389            return !ctx.rete.reads_are_remote() && split(ctx, l, index, from_named, out);
390        }
391        if !buildable(r) {
392            return false;
393        }
394        let mark = out.builds.len();
395        out.builds.push(node);
396        if split(ctx, l, index, from_named, out) {
397            true
398        } else {
399            out.builds.truncate(mark);
400            false
401        }
402    }
403
404    /// Is `r` joined to `l` by one lookup per left row, whatever the rows,
405    /// with nothing built from `r` as a whole? The three cases `join_iter`
406    /// decides before it sees a row: `GRAPH ?g { … }` with `?g` possibly
407    /// bound on the left, a property path with an endpoint bound on the left,
408    /// and a BGP that shares a certainly bound variable and whose cheapest
409    /// pattern is a fat scan.
410    fn looked_up_per_row(ctx: &Ctx, index: &GraphIndex, l: &Plan, r: &Plan) -> bool {
411        let lcert = certain_bound(ctx, l, ctx.slots.len());
412        match r {
413            // As `join_iter` decides it: possibly bound is enough. A row that
414            // leaves `?g` unbound joins with every graph, and that walk is
415            // then made, once, in the slice the row is in.
416            Plan::Graph(GraphTarget::Var(gv), _) => ctx
417                .slots
418                .slot(gv)
419                .is_some_and(|slot| possible_bound(ctx, l, ctx.slots.len())[slot]),
420            Plan::Path(s, _, o) => path_endpoint_bound(ctx, l, s, o),
421            Plan::Bgp(patterns) => {
422                !patterns.is_empty()
423                    && shares_certain_var(ctx, patterns, &lcert)
424                    && crate::bgp::bgp_min_estimate(ctx, index, patterns)
425                        .is_none_or(|n| n >= crate::bgp::FAT_SCAN_ROWS)
426            }
427            _ => false,
428        }
429    }
430
431    /// May the right side of a join be evaluated whole and built into a
432    /// table? The shapes the single thread hash-joins. Not the ones it would
433    /// rather push the left rows into (VALUES, a UNION of patterns, an
434    /// entailed atom), nor a path, which it drives from a bound endpoint.
435    fn buildable(r: &Plan) -> bool {
436        match r {
437            Plan::Bgp(_) | Plan::Subquery(_) => true,
438            Plan::Graph(_, inner) => buildable(inner),
439            Plan::Filter(e, inner) | Plan::Extend(_, e, inner) => {
440                !expr_has_exists(e) && buildable(inner)
441            }
442            Plan::Join(a, b) => buildable(a) && buildable(b),
443            Plan::LeftJoin(a, b, cond) => {
444                cond.as_ref().is_none_or(|c| !expr_has_exists(c)) && buildable(a) && buildable(b)
445            }
446            _ => false,
447        }
448    }
449
450    /// Runs its closure when dropped by a panic's unwinding.
451    struct OnPanic<F: Fn()>(F);
452
453    impl<F: Fn()> Drop for OnPanic<F> {
454        fn drop(&mut self) {
455            if std::thread::panicking() {
456                (self.0)();
457            }
458        }
459    }
460
461    /// Which slice a worker takes next, and how far the calling thread has
462    /// come (slices merged, or the slice whose rows it is folding).
463    struct Claims {
464        next: usize,
465        merged: usize,
466        stop: bool,
467    }
468
469    enum Msg {
470        /// Slice `i`'s groups; `None`: the attempt is given up.
471        Part(usize, Option<PartialGroups>),
472        /// The type errors a worker's expressions recorded.
473        Diag(diag::Taken),
474    }
475
476    /// How a run on several threads ended.
477    enum Outcome {
478        Done(Vec<Row>),
479        /// A slice held more groups than may wait for a merge.
480        TooManyGroups,
481        Failed,
482    }
483
484    /// What every run needs: the query, the split, and what was built for all
485    /// slices.
486    struct Job<'j, 'q> {
487        rete: &'q crate::file::Rete,
488        sel: &'q Select,
489        active: &'q GraphIndex,
490        nf: Option<&'q [String]>,
491        g: &'q GroupSpec,
492        sp: &'j Split,
493        shared: &'j SharedState,
494        /// The number of slices when their groups are merged.
495        n: usize,
496        /// The length of the longest driving scan, in tiles (or rows).
497        tiles: usize,
498        /// The file is read over a network.
499        remote: bool,
500        workers: usize,
501    }
502
503    impl Job<'_, '_> {
504        /// A worker's own context: its share of the memos, the split, and
505        /// what is shared.
506        fn worker_ctx(&self) -> Ctx<'_> {
507            let mut wctx = query_ctx(self.rete, self.sel);
508            let memo_cap = (MEMO_CAP_BYTES / self.workers).max(MIN_MEMO_CAP);
509            wctx.resolver.set_memo_cap(memo_cap);
510            wctx.exhaustive.set(true);
511            wctx.shard.set_plan(
512                self.sp.leaves.clone(),
513                self.sp.only_first.clone(),
514                self.sp.builds.clone(),
515                self.shared.clone(),
516            );
517            wctx
518        }
519    }
520
521    pub(in super::super) fn aggregate_shards<'q>(
522        ctx: &'q Ctx<'q>,
523        sel: &'q Select,
524        active: &'q GraphIndex,
525        nf: Option<&'q [String]>,
526        g: &'q GroupSpec,
527    ) -> Option<Vec<Row>> {
528        let threads = query_threads();
529        if threads < 2 || IN_WORKER.with(Cell::get) || crate::guard::armed_here() {
530            return None;
531        }
532        if g.pre.iter().any(|(_, e)| expr_has_exists(e)) {
533            return None;
534        }
535        let mut sp = Split::default();
536        if !split(ctx, &sel.plan, active, nf.is_some(), &mut sp) || sp.leaves.is_empty() {
537            return None;
538        }
539
540        // Dry runs: build slice 0's pipeline in this context, pull nothing.
541        // The first only measures: it must reach every split node once, and
542        // it tells how long the longest driving scan is. A scan too short to
543        // split ends here, before anything is built for it. The second
544        // builds what the slices share (a join's table).
545        ctx.shard.set_plan(
546            sp.leaves.clone(),
547            sp.only_first.clone(),
548            sp.builds.clone(),
549            SharedState::new(),
550        );
551        let dry = |measuring: bool| {
552            ctx.shard.set_measuring(measuring);
553            ctx.shard.begin(Some((0, SHARDS)));
554            drop(eval_plan_iter(ctx, active, nf, &sel.plan));
555            (ctx.shard.exact(), ctx.shard.tiles())
556        };
557        let (mut exact, tiles) = dry(true);
558        if exact && tiles >= 2 && !sp.builds.is_empty() {
559            exact = dry(false).0;
560        }
561        let mut shared = ctx.shard.shared_state();
562        ctx.shard.clear();
563        // An empty cell for each EXISTS on the way: the first slice whose row
564        // needs its solutions fills it, the others read it.
565        for &plan in &sp.exists {
566            shared
567                .entry((plan, 0))
568                .or_insert_with(|| std::sync::Arc::new(ExistsCell::default()));
569        }
570        // Over a network a slice is a request or two (it reads its tiles ahead
571        // in one batch), so there are fewer of them and none is small: a short
572        // scan stays one scan, with its few coalesced requests.
573        let remote = ctx.rete.reads_are_remote();
574        let n = if remote {
575            REMOTE_SHARDS.min(tiles / REMOTE_MIN_TILES)
576        } else {
577            SHARDS.min(tiles)
578        };
579        if !exact || n < 2 {
580            return None;
581        }
582        let job = Job {
583            rete: ctx.rete,
584            sel,
585            active,
586            nf,
587            g,
588            sp: &sp,
589            shared: &shared,
590            n,
591            tiles,
592            remote,
593            workers: threads.min(n),
594        };
595        // The slices' groups are merged when every aggregate can be; when one
596        // cannot (a set of distinct values), or a slice has too many groups
597        // to hold while it waits, the workers send their rows to one fold.
598        let outcome = if mergeable(g) {
599            match merge_groups(ctx, &job) {
600                Outcome::TooManyGroups => fold_rows(ctx, &job),
601                other => other,
602            }
603        } else {
604            fold_rows(ctx, &job)
605        };
606        match outcome {
607            Outcome::Done(rows) => {
608                super::SHARDED.fetch_add(1, Ordering::Relaxed);
609                Some(rows)
610            }
611            _ => None,
612        }
613    }
614
615    /// Each worker folds its slices into partial aggregates; the calling
616    /// thread merges them in slice order.
617    fn merge_groups(ctx: &Ctx, job: &Job) -> Outcome {
618        let (n, workers) = (job.n, job.workers);
619        let window = 2 * workers;
620        let claims = Mutex::new(Claims {
621            next: 0,
622            merged: 0,
623            stop: false,
624        });
625        let wake = Condvar::new();
626        let abort = AtomicBool::new(false);
627        let too_many = AtomicBool::new(false);
628        let give_up = || {
629            abort.store(true, Ordering::Relaxed);
630            if let Ok(mut c) = claims.lock() {
631                c.stop = true;
632            }
633            wake.notify_all();
634        };
635        let (tx, rx) = mpsc::channel::<Msg>();
636        let mut merger = Merger::default();
637        let mut failed = false;
638
639        std::thread::scope(|scope| {
640            for _ in 0..workers {
641                let tx = tx.clone();
642                let (claims, wake, abort, too_many, give_up) =
643                    (&claims, &wake, &abort, &too_many, &give_up);
644                let worker = move || {
645                    // A worker that panics never sends its slice: the others
646                    // must not wait for the merge to pass it.
647                    let _stop = OnPanic(give_up);
648                    IN_WORKER.with(|w| w.set(true));
649                    diag::begin();
650                    let wctx = job.worker_ctx();
651                    let wctx = &wctx;
652                    loop {
653                        let i = {
654                            let mut c = claims.lock().unwrap();
655                            loop {
656                                if c.stop || c.next >= n {
657                                    break None;
658                                }
659                                if c.next < c.merged + window {
660                                    c.next += 1;
661                                    break Some(c.next - 1);
662                                }
663                                c = wake.wait(c).unwrap();
664                            }
665                        };
666                        let Some(i) = i else { break };
667                        wctx.shard.begin(Some((i, n)));
668                        let mut seen = 0u32;
669                        let rows = eval_plan_iter(wctx, job.active, job.nf, &job.sel.plan)
670                            .take_while(|_| {
671                                seen = seen.wrapping_add(1);
672                                !seen.is_multiple_of(4096) || !abort.load(Ordering::Relaxed)
673                            });
674                        let folded = aggregate_partial(wctx, rows, job.g, MAX_SHARD_GROUPS);
675                        if folded.is_none() {
676                            too_many.store(true, Ordering::Relaxed);
677                        }
678                        let part =
679                            folded.filter(|_| wctx.shard.exact() && !abort.load(Ordering::Relaxed));
680                        let gone = part.is_none();
681                        if gone {
682                            give_up();
683                        }
684                        if tx.send(Msg::Part(i, part)).is_err() || gone {
685                            break;
686                        }
687                    }
688                    let _ = tx.send(Msg::Diag(diag::take()));
689                };
690                // A thread that cannot be started is one worker fewer; with
691                // none at all no slice arrives and the attempt fails.
692                if std::thread::Builder::new()
693                    .name("rete-query".into())
694                    .stack_size(WORKER_STACK)
695                    .spawn_scoped(scope, worker)
696                    .is_err()
697                {
698                    break;
699                }
700            }
701            drop(tx);
702
703            // Merge in slice order as the slices arrive.
704            let mut pending: BTreeMap<usize, PartialGroups> = BTreeMap::new();
705            let mut next = 0usize;
706            let mut diags = Vec::new();
707            for msg in rx {
708                match msg {
709                    Msg::Diag(taken) => diags.push(taken),
710                    Msg::Part(_, None) => {
711                        failed = true;
712                        pending.clear();
713                        give_up();
714                    }
715                    Msg::Part(i, Some(part)) => {
716                        if failed {
717                            continue;
718                        }
719                        pending.insert(i, part);
720                        while let Some(part) = pending.remove(&next) {
721                            merger.absorb(part);
722                            next += 1;
723                        }
724                        claims.lock().unwrap().merged = next;
725                        wake.notify_all();
726                    }
727                }
728            }
729            if next != n {
730                failed = true;
731            }
732            // Only a run that is kept reports what its workers recorded: a
733            // run given up is evaluated again, and records it all again.
734            if !failed {
735                diags.into_iter().for_each(diag::absorb);
736            }
737        });
738
739        if failed {
740            return if too_many.load(Ordering::Relaxed) {
741                Outcome::TooManyGroups
742            } else {
743                Outcome::Failed
744            };
745        }
746        Outcome::Done(merger.finish(ctx, job.g))
747    }
748
749    /// Each worker evaluates its slices and sends the rows; the calling
750    /// thread folds them, slice after slice, exactly as it folds the one
751    /// scan's rows. Whatever the aggregates keep (distinct sets, any number of
752    /// groups) is kept once, by the one fold. The workers do the per-row work
753    /// of the pattern and of the aggregated expressions.
754    fn fold_rows(ctx: &Ctx, job: &Job) -> Outcome {
755        // (A remote file keeps its few large slices: see `aggregate_shards`.)
756        let n = if job.remote {
757            job.n
758        } else {
759            ROW_SHARDS.min(job.tiles)
760        };
761        let workers = job.workers;
762        // The slots the fold reads: a row is cut down to them before it is
763        // sent, so what waits for the fold is a few values a row.
764        let keep = fold_slots(ctx, job.g);
765        let keep = &keep;
766        // A slice's rows wait in its own bounded channel, so a worker ahead
767        // of the fold stops when its share of the rows that may wait is full.
768        let chunks_ahead = (ROWS_AHEAD / workers / ROW_CHUNK).max(1);
769        let mut senders = Vec::with_capacity(n);
770        let mut receivers = Vec::with_capacity(n);
771        for _ in 0..n {
772            let (tx, rx) = mpsc::sync_channel::<Vec<Row>>(chunks_ahead);
773            senders.push(Some(tx));
774            receivers.push(rx);
775        }
776        let senders = Mutex::new(senders);
777        let claims = Mutex::new(Claims {
778            next: 0,
779            merged: 0,
780            stop: false,
781        });
782        let wake = Condvar::new();
783        let abort = AtomicBool::new(false);
784        let give_up = || {
785            abort.store(true, Ordering::Relaxed);
786            if let Ok(mut c) = claims.lock() {
787                c.stop = true;
788            }
789            // A slice nobody took has its sender here: dropped, so the fold
790            // does not wait for it.
791            if let Ok(mut s) = senders.lock() {
792                s.iter_mut().for_each(|tx| *tx = None);
793            }
794            wake.notify_all();
795        };
796        let (dtx, drx) = mpsc::channel::<diag::Taken>();
797        let mut out = Vec::new();
798
799        std::thread::scope(|scope| {
800            for _ in 0..workers {
801                let dtx = dtx.clone();
802                let (claims, wake, abort, give_up, senders) =
803                    (&claims, &wake, &abort, &give_up, &senders);
804                let worker = move || {
805                    let _stop = OnPanic(give_up);
806                    IN_WORKER.with(|w| w.set(true));
807                    diag::begin();
808                    let wctx = job.worker_ctx();
809                    let wctx = &wctx;
810                    loop {
811                        // At most `2 × workers` slices ahead of the one being
812                        // folded: what waits is bounded by slices in flight.
813                        let i = {
814                            let mut c = claims.lock().unwrap();
815                            loop {
816                                if c.stop || c.next >= n {
817                                    break None;
818                                }
819                                if c.next < c.merged + 2 * workers {
820                                    c.next += 1;
821                                    break Some(c.next - 1);
822                                }
823                                c = wake.wait(c).unwrap();
824                            }
825                        };
826                        let Some(i) = i else { break };
827                        let Some(tx) = senders.lock().unwrap()[i].take() else {
828                            break;
829                        };
830                        wctx.shard.begin(Some((i, n)));
831                        let mut chunk: Vec<Row> = Vec::with_capacity(ROW_CHUNK);
832                        let mut open = true;
833                        for mut row in eval_plan_iter(wctx, job.active, job.nf, &job.sel.plan) {
834                            apply_pre(wctx, &mut row, job.g);
835                            chunk.push(keep.iter().map(|&s| row[s].take()).collect());
836                            if chunk.len() == ROW_CHUNK {
837                                let full =
838                                    std::mem::replace(&mut chunk, Vec::with_capacity(ROW_CHUNK));
839                                if tx.send(full).is_err() || abort.load(Ordering::Relaxed) {
840                                    open = false;
841                                    break;
842                                }
843                            }
844                        }
845                        if open && !chunk.is_empty() {
846                            open = tx.send(chunk).is_ok();
847                        }
848                        if !wctx.shard.exact() {
849                            give_up();
850                        }
851                        if !open || abort.load(Ordering::Relaxed) {
852                            break;
853                        }
854                    }
855                    let _ = dtx.send(diag::take());
856                };
857                if std::thread::Builder::new()
858                    .name("rete-query".into())
859                    .stack_size(WORKER_STACK)
860                    .spawn_scoped(scope, worker)
861                    .is_err()
862                {
863                    // Fewer workers; with none, no slice would ever be taken.
864                    give_up();
865                    break;
866                }
867            }
868            drop(dtx);
869
870            // The one fold: slice after slice, each slice's rows in order.
871            let (claims, wake, abort) = (&claims, &wake, &abort);
872            let rows = receivers
873                .into_iter()
874                .enumerate()
875                .flat_map(move |(i, rx)| {
876                    if let Ok(mut c) = claims.lock() {
877                        c.merged = i;
878                    }
879                    wake.notify_all();
880                    rx.into_iter().flatten()
881                })
882                .take_while(|_| !abort.load(Ordering::Relaxed));
883            out = aggregate_folded(ctx, rows, job.g, keep);
884            if abort.load(Ordering::Relaxed) {
885                // Workers blocked on a full channel see it closed (the
886                // receivers went with the iterator) and stop.
887                give_up();
888            } else {
889                // Every slice was folded to its end; the workers are done or
890                // about to be. Their records come once they have all gone.
891                wake.notify_all();
892            }
893        });
894        if abort.load(Ordering::Relaxed) {
895            return Outcome::Failed;
896        }
897        drx.into_iter().for_each(diag::absorb);
898        Outcome::Done(out)
899    }
900}