spacedb_query/planner.rs
1//! The partition-aware planner: map-reduce across shards, with **honest coverage**.
2//!
3//! A query is a `map` function run on **each shard, next to its data** (only the
4//! partial result travels back), and a `reduce` function that combines partials.
5//! Because `reduce` is associative and commutative, partials from a
6//! partition-degraded set still compose — and when some shards are unreachable,
7//! the result is returned **flagged with coverage** ("computed over 4/5 shards"),
8//! never silently under-reported.
9//!
10//! Each map runs on the verifiable [`FunctionRuntime`](crate::FunctionRuntime), so
11//! its [`FunctionRun`](crate::FunctionRun) attestation comes back for corroboration
12//! / audit. Fanning a map across *redundant* hosts and comparing their
13//! attestations is the MATA seam; this planner is the single-coordinator core.
14
15use crate::corroborate::FunctionRun;
16use crate::error::QueryResult;
17use crate::runtime::{FunctionRuntime, RunLimits};
18use crate::snapshot::Snapshot;
19
20/// One shard of a query's data: a pinned snapshot, on a host that may be down.
21#[derive(Clone, Debug)]
22pub struct Shard {
23 pub id: String,
24 pub snapshot: Snapshot,
25 pub reachable: bool,
26}
27
28impl Shard {
29 /// A reachable shard.
30 pub fn new(id: impl Into<String>, snapshot: Snapshot) -> Self {
31 Self {
32 id: id.into(),
33 snapshot,
34 reachable: true,
35 }
36 }
37
38 /// Mark the shard's host as down (its data won't contribute).
39 pub fn unreachable(mut self) -> Self {
40 self.reachable = false;
41 self
42 }
43}
44
45/// The query: a `map` over each shard's snapshot and an associative/commutative
46/// `reduce` over the partials, both deployed as deterministic WASM.
47pub struct QueryPlan<'a> {
48 pub map_wasm: &'a [u8],
49 pub reduce_wasm: &'a [u8],
50 pub limits: RunLimits,
51}
52
53/// How much of the dataset the result actually covers — the honesty contract.
54#[derive(Clone, Copy, Debug, PartialEq, Eq)]
55pub struct Coverage {
56 pub shards_total: usize,
57 pub shards_computed: usize,
58}
59
60impl Coverage {
61 /// Whether every shard contributed (no partition gaps).
62 pub fn is_complete(&self) -> bool {
63 self.shards_total > 0 && self.shards_computed == self.shards_total
64 }
65
66 /// How many shards were unreachable.
67 pub fn missing(&self) -> usize {
68 self.shards_total - self.shards_computed
69 }
70}
71
72/// The result of a query: the reduced output (if any shard contributed), the
73/// coverage, and the per-shard map attestations.
74#[derive(Clone, Debug)]
75pub struct QueryOutcome {
76 pub output: Option<Vec<u8>>,
77 pub coverage: Coverage,
78 pub map_runs: Vec<FunctionRun>,
79}
80
81/// Frame two partials for the `reduce` ABI: `len(a) ‖ a ‖ b`.
82fn frame_pair_into(framed: &mut Vec<u8>, a: &[u8], b: &[u8]) {
83 framed.clear();
84 framed.extend_from_slice(&(a.len() as u32).to_le_bytes());
85 framed.extend_from_slice(a);
86 framed.extend_from_slice(b);
87}
88
89/// Run `plan` over `shards`: map each reachable shard's snapshot, then reduce the
90/// partials. Unreachable shards are skipped (lowering coverage, never failing the
91/// query); a map/reduce error on a *reachable* shard propagates (it signals a
92/// systemic deploy/ABI bug, since the same WASM runs everywhere).
93pub fn run_query(
94 runtime: &FunctionRuntime,
95 plan: &QueryPlan,
96 shards: &[Shard],
97) -> QueryResult<QueryOutcome> {
98 // Each module is hashed once for the whole query, and a shard's snapshot
99 // already carries the digest of its bytes: nothing is hashed per shard.
100 let map_hash = *blake3::hash(plan.map_wasm).as_bytes();
101 let reduce_hash = *blake3::hash(plan.reduce_wasm).as_bytes();
102
103 // Map phase: run the query next to each reachable shard's data.
104 let mut partials: Vec<Vec<u8>> = Vec::new();
105 let mut map_runs: Vec<FunctionRun> = Vec::new();
106 for shard in shards {
107 if !shard.reachable {
108 continue;
109 }
110 let exec = runtime.run_prehashed(
111 &map_hash,
112 plan.map_wasm,
113 shard.snapshot.bytes(),
114 Some(shard.snapshot.hash()),
115 &plan.limits,
116 )?;
117 partials.push(exec.output);
118 map_runs.push(exec.run);
119 }
120
121 let coverage = Coverage {
122 shards_total: shards.len(),
123 shards_computed: partials.len(),
124 };
125
126 // Reduce phase: fold the partials. Order-independent (reduce is commutative).
127 let output = if partials.is_empty() {
128 None
129 } else {
130 // Moved, not cloned; and one framing buffer serves every reduce step.
131 let mut partials = partials.into_iter();
132 let mut acc = partials.next().expect("partials is non-empty");
133 let mut framed = Vec::new();
134 for partial in partials {
135 frame_pair_into(&mut framed, &acc, &partial);
136 acc = runtime
137 .run_prehashed(&reduce_hash, plan.reduce_wasm, &framed, None, &plan.limits)?
138 .output;
139 }
140 Some(acc)
141 };
142
143 Ok(QueryOutcome {
144 output,
145 coverage,
146 map_runs,
147 })
148}