use std::sync::atomic::{AtomicUsize, Ordering};
static THREADS: AtomicUsize = AtomicUsize::new(0);
static SHARDED: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(0);
pub fn sharded_queries() -> u64 {
SHARDED.load(Ordering::Relaxed)
}
const DEFAULT_MAX_THREADS: usize = 16;
pub fn set_query_threads(n: usize) {
THREADS.store(n, Ordering::Relaxed);
}
pub fn query_threads() -> usize {
match THREADS.load(Ordering::Relaxed) {
0 => default_threads(),
n => n,
}
}
fn default_threads() -> usize {
static DEFAULT: std::sync::OnceLock<usize> = std::sync::OnceLock::new();
*DEFAULT.get_or_init(|| {
if let Some(n) = std::env::var("RETE_QUERY_THREADS")
.ok()
.and_then(|v| v.trim().parse::<usize>().ok())
.filter(|&n| n > 0)
{
return n;
}
std::thread::available_parallelism()
.map(|n| n.get())
.unwrap_or(1)
.min(DEFAULT_MAX_THREADS)
})
}
#[cfg(not(feature = "parallel"))]
pub(super) fn aggregate_shards<'q>(
_ctx: &'q crate::row::Ctx<'q>,
_sel: &'q super::Select,
_active: &'q crate::index::GraphIndex,
_nf: Option<&'q [String]>,
_g: &'q super::GroupSpec,
) -> Option<Vec<crate::row::Row>> {
None
}
#[cfg(feature = "parallel")]
pub(super) use threaded::aggregate_shards;
#[cfg(feature = "parallel")]
mod threaded {
use std::cell::Cell;
use std::collections::BTreeMap;
use std::sync::atomic::{AtomicBool, Ordering};
use std::sync::{mpsc, Condvar, Mutex};
use super::super::aggregate::{
aggregate_folded, aggregate_partial, apply_pre, fold_slots, mergeable, Merger,
PartialGroups,
};
use super::super::eval::{
certain_bound, eval_plan_iter, expr_has_exists, only_projects, path_endpoint_bound,
possible_bound, query_ctx, shares_certain_var,
};
use super::super::{diag, ExistsCell, FExpr, GraphTarget, GroupSpec, Plan, Select};
use super::query_threads;
use crate::index::GraphIndex;
use crate::row::{Ctx, Row, SharedState, MEMO_CAP_BYTES};
const SHARDS: usize = 64;
const REMOTE_SHARDS: usize = 16;
const REMOTE_MIN_TILES: usize = 8;
const MAX_SHARD_GROUPS: usize = 100_000;
const ROW_CHUNK: usize = 2048;
const ROWS_AHEAD: usize = 1 << 21;
const ROW_SHARDS: usize = 1024;
const WORKER_STACK: usize = 8 << 20;
const MIN_MEMO_CAP: usize = 4 << 20;
thread_local! {
static IN_WORKER: Cell<bool> = const { Cell::new(false) };
}
#[derive(Default)]
struct Split {
leaves: Vec<usize>,
only_first: Vec<usize>,
builds: Vec<usize>,
exists: Vec<usize>,
}
fn exists_plans(e: &FExpr, out: &mut Vec<usize>) {
match e {
FExpr::Exists(plan) => out.push(plan.as_ref() as *const Plan as usize),
FExpr::Var(_) | FExpr::Const(_) | FExpr::Bound(_) => {}
FExpr::Not(a) => exists_plans(a, out),
FExpr::Arith(_, a, b)
| FExpr::SameTerm(a, b)
| FExpr::Compare(_, a, b)
| FExpr::And(a, b)
| FExpr::Or(a, b) => {
exists_plans(a, out);
exists_plans(b, out);
}
FExpr::If(c, t, f) => {
exists_plans(c, out);
exists_plans(t, out);
exists_plans(f, out);
}
FExpr::In(x, list) => {
exists_plans(x, out);
list.iter().for_each(|e| exists_plans(e, out));
}
FExpr::Func(_, args) | FExpr::Coalesce(args) => {
args.iter().for_each(|e| exists_plans(e, out));
}
}
}
fn condition(ctx: &Ctx, e: &FExpr, out: &mut Split) -> bool {
if !expr_has_exists(e) {
return true;
}
if ctx.rete.reads_are_remote() {
return false;
}
exists_plans(e, &mut out.exists);
true
}
fn split(
ctx: &Ctx,
plan: &Plan,
index: &GraphIndex,
from_named: bool,
out: &mut Split,
) -> bool {
let node = plan as *const Plan as usize;
match plan {
Plan::Bgp(patterns) if !patterns.is_empty() => {
out.leaves.push(node);
true
}
Plan::Graph(GraphTarget::Var(v), _) => {
if ctx.slots.slot(v).is_some() {
out.leaves.push(node);
true
} else {
false
}
}
Plan::Graph(GraphTarget::Named(iri), inner) => match ctx.rete.graph_index(iri) {
Some(gi) => split(ctx, inner, gi, from_named, out),
None => false,
},
Plan::Filter(e, inner) => {
let mark = out.exists.len();
if condition(ctx, e, out) && split(ctx, inner, index, from_named, out) {
true
} else {
out.exists.truncate(mark);
false
}
}
Plan::Extend(_, e, inner) => {
!expr_has_exists(e) && split(ctx, inner, index, from_named, out)
}
Plan::Subquery(sub) if only_projects(sub) => {
let sub_ctx = query_ctx(ctx.rete, sub);
split(&sub_ctx, &sub.plan, index, from_named, out)
}
Plan::Minus(l, r) => {
let lcert = certain_bound(ctx, l, ctx.slots.len());
let probed = matches!(&**r, Plan::Bgp(patterns)
if crate::bgp::CorrelatedProbe::new(ctx, index, patterns, &lcert).is_some());
if probed {
return !ctx.rete.reads_are_remote() && split(ctx, l, index, from_named, out);
}
if !buildable(r) {
return false;
}
let mark = out.builds.len();
out.builds.push(node);
if split(ctx, l, index, from_named, out) {
true
} else {
out.builds.truncate(mark);
false
}
}
Plan::Union(l, r) => {
let mut branch = |p: &Plan| {
let mark = (
out.leaves.len(),
out.only_first.len(),
out.builds.len(),
out.exists.len(),
);
if split(ctx, p, index, from_named, out) {
true
} else {
out.leaves.truncate(mark.0);
out.only_first.truncate(mark.1);
out.builds.truncate(mark.2);
out.exists.truncate(mark.3);
out.only_first.push(p as *const Plan as usize);
false
}
};
let l = branch(l);
let r = branch(r);
l || r
}
Plan::Join(l, r) => join(ctx, node, l, r, index, from_named, out),
Plan::LeftJoin(l, r, cond) => {
let mark = out.exists.len();
if cond.as_ref().is_none_or(|c| condition(ctx, c, out))
&& join(ctx, node, l, r, index, from_named, out)
{
true
} else {
out.exists.truncate(mark);
false
}
}
_ => false,
}
}
fn join(
ctx: &Ctx,
node: usize,
l: &Plan,
r: &Plan,
index: &GraphIndex,
from_named: bool,
out: &mut Split,
) -> bool {
if looked_up_per_row(ctx, index, l, r) {
return !ctx.rete.reads_are_remote() && split(ctx, l, index, from_named, out);
}
if !buildable(r) {
return false;
}
let mark = out.builds.len();
out.builds.push(node);
if split(ctx, l, index, from_named, out) {
true
} else {
out.builds.truncate(mark);
false
}
}
fn looked_up_per_row(ctx: &Ctx, index: &GraphIndex, l: &Plan, r: &Plan) -> bool {
let lcert = certain_bound(ctx, l, ctx.slots.len());
match r {
Plan::Graph(GraphTarget::Var(gv), _) => ctx
.slots
.slot(gv)
.is_some_and(|slot| possible_bound(ctx, l, ctx.slots.len())[slot]),
Plan::Path(s, _, o) => path_endpoint_bound(ctx, l, s, o),
Plan::Bgp(patterns) => {
!patterns.is_empty()
&& shares_certain_var(ctx, patterns, &lcert)
&& crate::bgp::bgp_min_estimate(ctx, index, patterns)
.is_none_or(|n| n >= crate::bgp::FAT_SCAN_ROWS)
}
_ => false,
}
}
fn buildable(r: &Plan) -> bool {
match r {
Plan::Bgp(_) | Plan::Subquery(_) => true,
Plan::Graph(_, inner) => buildable(inner),
Plan::Filter(e, inner) | Plan::Extend(_, e, inner) => {
!expr_has_exists(e) && buildable(inner)
}
Plan::Join(a, b) => buildable(a) && buildable(b),
Plan::LeftJoin(a, b, cond) => {
cond.as_ref().is_none_or(|c| !expr_has_exists(c)) && buildable(a) && buildable(b)
}
_ => false,
}
}
struct OnPanic<F: Fn()>(F);
impl<F: Fn()> Drop for OnPanic<F> {
fn drop(&mut self) {
if std::thread::panicking() {
(self.0)();
}
}
}
struct Claims {
next: usize,
merged: usize,
stop: bool,
}
enum Msg {
Part(usize, Option<PartialGroups>),
Diag(diag::Taken),
}
enum Outcome {
Done(Vec<Row>),
TooManyGroups,
Failed,
}
struct Job<'j, 'q> {
rete: &'q crate::file::Rete,
sel: &'q Select,
active: &'q GraphIndex,
nf: Option<&'q [String]>,
g: &'q GroupSpec,
sp: &'j Split,
shared: &'j SharedState,
n: usize,
tiles: usize,
remote: bool,
workers: usize,
}
impl Job<'_, '_> {
fn worker_ctx(&self) -> Ctx<'_> {
let mut wctx = query_ctx(self.rete, self.sel);
let memo_cap = (MEMO_CAP_BYTES / self.workers).max(MIN_MEMO_CAP);
wctx.resolver.set_memo_cap(memo_cap);
wctx.exhaustive.set(true);
wctx.shard.set_plan(
self.sp.leaves.clone(),
self.sp.only_first.clone(),
self.sp.builds.clone(),
self.shared.clone(),
);
wctx
}
}
pub(in super::super) fn aggregate_shards<'q>(
ctx: &'q Ctx<'q>,
sel: &'q Select,
active: &'q GraphIndex,
nf: Option<&'q [String]>,
g: &'q GroupSpec,
) -> Option<Vec<Row>> {
let threads = query_threads();
if threads < 2 || IN_WORKER.with(Cell::get) || crate::guard::armed_here() {
return None;
}
if g.pre.iter().any(|(_, e)| expr_has_exists(e)) {
return None;
}
let mut sp = Split::default();
if !split(ctx, &sel.plan, active, nf.is_some(), &mut sp) || sp.leaves.is_empty() {
return None;
}
ctx.shard.set_plan(
sp.leaves.clone(),
sp.only_first.clone(),
sp.builds.clone(),
SharedState::new(),
);
let dry = |measuring: bool| {
ctx.shard.set_measuring(measuring);
ctx.shard.begin(Some((0, SHARDS)));
drop(eval_plan_iter(ctx, active, nf, &sel.plan));
(ctx.shard.exact(), ctx.shard.tiles())
};
let (mut exact, tiles) = dry(true);
if exact && tiles >= 2 && !sp.builds.is_empty() {
exact = dry(false).0;
}
let mut shared = ctx.shard.shared_state();
ctx.shard.clear();
for &plan in &sp.exists {
shared
.entry((plan, 0))
.or_insert_with(|| std::sync::Arc::new(ExistsCell::default()));
}
let remote = ctx.rete.reads_are_remote();
let n = if remote {
REMOTE_SHARDS.min(tiles / REMOTE_MIN_TILES)
} else {
SHARDS.min(tiles)
};
if !exact || n < 2 {
return None;
}
let job = Job {
rete: ctx.rete,
sel,
active,
nf,
g,
sp: &sp,
shared: &shared,
n,
tiles,
remote,
workers: threads.min(n),
};
let outcome = if mergeable(g) {
match merge_groups(ctx, &job) {
Outcome::TooManyGroups => fold_rows(ctx, &job),
other => other,
}
} else {
fold_rows(ctx, &job)
};
match outcome {
Outcome::Done(rows) => {
super::SHARDED.fetch_add(1, Ordering::Relaxed);
Some(rows)
}
_ => None,
}
}
fn merge_groups(ctx: &Ctx, job: &Job) -> Outcome {
let (n, workers) = (job.n, job.workers);
let window = 2 * workers;
let claims = Mutex::new(Claims {
next: 0,
merged: 0,
stop: false,
});
let wake = Condvar::new();
let abort = AtomicBool::new(false);
let too_many = AtomicBool::new(false);
let give_up = || {
abort.store(true, Ordering::Relaxed);
if let Ok(mut c) = claims.lock() {
c.stop = true;
}
wake.notify_all();
};
let (tx, rx) = mpsc::channel::<Msg>();
let mut merger = Merger::default();
let mut failed = false;
std::thread::scope(|scope| {
for _ in 0..workers {
let tx = tx.clone();
let (claims, wake, abort, too_many, give_up) =
(&claims, &wake, &abort, &too_many, &give_up);
let worker = move || {
let _stop = OnPanic(give_up);
IN_WORKER.with(|w| w.set(true));
diag::begin();
let wctx = job.worker_ctx();
let wctx = &wctx;
loop {
let i = {
let mut c = claims.lock().unwrap();
loop {
if c.stop || c.next >= n {
break None;
}
if c.next < c.merged + window {
c.next += 1;
break Some(c.next - 1);
}
c = wake.wait(c).unwrap();
}
};
let Some(i) = i else { break };
wctx.shard.begin(Some((i, n)));
let mut seen = 0u32;
let rows = eval_plan_iter(wctx, job.active, job.nf, &job.sel.plan)
.take_while(|_| {
seen = seen.wrapping_add(1);
!seen.is_multiple_of(4096) || !abort.load(Ordering::Relaxed)
});
let folded =
aggregate_partial(wctx, job.active, rows, job.g, MAX_SHARD_GROUPS);
if folded.is_none() {
too_many.store(true, Ordering::Relaxed);
}
let part =
folded.filter(|_| wctx.shard.exact() && !abort.load(Ordering::Relaxed));
let gone = part.is_none();
if gone {
give_up();
}
if tx.send(Msg::Part(i, part)).is_err() || gone {
break;
}
}
let _ = tx.send(Msg::Diag(diag::take()));
};
if std::thread::Builder::new()
.name("rete-query".into())
.stack_size(WORKER_STACK)
.spawn_scoped(scope, worker)
.is_err()
{
break;
}
}
drop(tx);
let mut pending: BTreeMap<usize, PartialGroups> = BTreeMap::new();
let mut next = 0usize;
let mut diags = Vec::new();
for msg in rx {
match msg {
Msg::Diag(taken) => diags.push(taken),
Msg::Part(_, None) => {
failed = true;
pending.clear();
give_up();
}
Msg::Part(i, Some(part)) => {
if failed {
continue;
}
pending.insert(i, part);
while let Some(part) = pending.remove(&next) {
merger.absorb(part);
next += 1;
}
claims.lock().unwrap().merged = next;
wake.notify_all();
}
}
}
if next != n {
failed = true;
}
if !failed {
diags.into_iter().for_each(diag::absorb);
}
});
if failed {
return if too_many.load(Ordering::Relaxed) {
Outcome::TooManyGroups
} else {
Outcome::Failed
};
}
Outcome::Done(merger.finish(ctx, job.g))
}
fn fold_rows(ctx: &Ctx, job: &Job) -> Outcome {
let n = if job.remote {
job.n
} else {
ROW_SHARDS.min(job.tiles)
};
let workers = job.workers;
let keep = fold_slots(ctx, job.g);
let keep = &keep;
let chunks_ahead = (ROWS_AHEAD / workers / ROW_CHUNK).max(1);
let mut senders = Vec::with_capacity(n);
let mut receivers = Vec::with_capacity(n);
for _ in 0..n {
let (tx, rx) = mpsc::sync_channel::<Vec<Row>>(chunks_ahead);
senders.push(Some(tx));
receivers.push(rx);
}
let senders = Mutex::new(senders);
let claims = Mutex::new(Claims {
next: 0,
merged: 0,
stop: false,
});
let wake = Condvar::new();
let abort = AtomicBool::new(false);
let give_up = || {
abort.store(true, Ordering::Relaxed);
if let Ok(mut c) = claims.lock() {
c.stop = true;
}
if let Ok(mut s) = senders.lock() {
s.iter_mut().for_each(|tx| *tx = None);
}
wake.notify_all();
};
let (dtx, drx) = mpsc::channel::<diag::Taken>();
let mut out = Vec::new();
std::thread::scope(|scope| {
for _ in 0..workers {
let dtx = dtx.clone();
let (claims, wake, abort, give_up, senders) =
(&claims, &wake, &abort, &give_up, &senders);
let worker = move || {
let _stop = OnPanic(give_up);
IN_WORKER.with(|w| w.set(true));
diag::begin();
let wctx = job.worker_ctx();
let wctx = &wctx;
loop {
let i = {
let mut c = claims.lock().unwrap();
loop {
if c.stop || c.next >= n {
break None;
}
if c.next < c.merged + 2 * workers {
c.next += 1;
break Some(c.next - 1);
}
c = wake.wait(c).unwrap();
}
};
let Some(i) = i else { break };
let Some(tx) = senders.lock().unwrap()[i].take() else {
break;
};
wctx.shard.begin(Some((i, n)));
let mut chunk: Vec<Row> = Vec::with_capacity(ROW_CHUNK);
let mut open = true;
let mut cache = super::super::ExistsCache::new();
for mut row in eval_plan_iter(wctx, job.active, job.nf, &job.sel.plan) {
apply_pre(wctx, job.active, &mut row, job.g, &mut cache);
chunk.push(keep.iter().map(|&s| row[s].take()).collect());
if chunk.len() == ROW_CHUNK {
let full =
std::mem::replace(&mut chunk, Vec::with_capacity(ROW_CHUNK));
if tx.send(full).is_err() || abort.load(Ordering::Relaxed) {
open = false;
break;
}
}
}
if open && !chunk.is_empty() {
open = tx.send(chunk).is_ok();
}
if !wctx.shard.exact() {
give_up();
}
if !open || abort.load(Ordering::Relaxed) {
break;
}
}
let _ = dtx.send(diag::take());
};
if std::thread::Builder::new()
.name("rete-query".into())
.stack_size(WORKER_STACK)
.spawn_scoped(scope, worker)
.is_err()
{
give_up();
break;
}
}
drop(dtx);
let (claims, wake, abort) = (&claims, &wake, &abort);
let rows = receivers
.into_iter()
.enumerate()
.flat_map(move |(i, rx)| {
if let Ok(mut c) = claims.lock() {
c.merged = i;
}
wake.notify_all();
rx.into_iter().flatten()
})
.take_while(|_| !abort.load(Ordering::Relaxed));
out = aggregate_folded(ctx, rows, job.g, keep);
if abort.load(Ordering::Relaxed) {
give_up();
} else {
wake.notify_all();
}
});
if abort.load(Ordering::Relaxed) {
return Outcome::Failed;
}
drx.into_iter().for_each(diag::absorb);
Outcome::Done(out)
}
}