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}