Skip to main content

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}