adityamukho · Oct 14, 2026 · Oct 14, 2026 · Oct 14, 2026 · Oct 14, 2026
@@ -22,6 +22,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 - **An unknown aggregate or window function is an error whatever the data** (#414). Aggregate and window function names in `:find` are now resolved before the query runs: an unknown aggregate fails with the new `QRY-010` and an unknown window function with the new `QRY-011`, even on an empty database or when no row matches. Before, such a query returned no results until a row matched and then failed with `INT-029`/`INT-030`, which stay registered for internal inconsistencies only.
 - **One current valid-time window per fact** (#435). At any transaction time, each `(entity, attribute, value)` now has exactly one current valid-time window: the one from its latest `transact`. A later assertion of the same fact replaces the earlier window, which stays visible through `:as-of` of the earlier transaction. Before, every window ever asserted stayed live until a `retract`, so closing an open window with `(transact {:valid-from vf :valid-to D} ...)` left the open one live and `:valid-at` after `D` still found the fact. Closing, extending or reopening a window is now a plain `transact` with the new bounds; `retract` still withdraws the fact. **This changes query results for existing data:** a fact asserted in several transactions with different windows is now valid only in its latest window at the current transaction time. A fact that was true over two separate periods can no longer have both windows live at once; model each period as its own entity, or read earlier periods with `:as-of`. Asserting one fact with two different windows in one `transact` is rejected with the new `API-011`, and nothing is written. Data written before this check with two windows in one transaction keeps both.
 - **The `uuid` dependency no longer enables `v4`** (#439). The library only makes v5 UUIDs, so the `v4` feature and, on browser wasm, `js` are gone from its `uuid` dependency, and with them `getrandom`. A crate that called `Uuid::new_v4` only because Cargo feature unification turned `v4` on through minigraf must now enable `uuid/v4` itself. The release binary shrinks by 48 bytes.
+- **Join answers no longer depend on the query plan** (#545). Two cases changed. A join on a float value now pairs `0.0` with `-0.0`, as a shared variable compared after the join key already did; before, `Value`'s hash told them apart, so the join key never paired them. NaN still equals nothing. Float constants in a pattern still match within `f64::EPSILON`. And a variable bound to a keyword by one pattern and to the ref of the entity the keyword names by another, which already joined, now returns the kind from the first of those patterns in the `:where` text. Before, it returned the kind from the pattern the planner ran first, so the answer could change with the selectivity of the other patterns, and differed under the `wasm` feature, which does not reorder. For example, with `[:alice :friend :bob]` stored as a keyword, `[:find ?b :where [?a :friend ?b] [?b :name "Bob"]]` returned the ref of `:bob`, because the planner runs the pattern with two constants first, and now returns the keyword `:bob`. An expression that binds a variable still sets its value where it runs, and later patterns keep that value. The rule covers the top-level `:where` of queries with and without rules; inside `or`, `not` and rule bodies the kinds are unchanged.
 
 ### Added
 

@@ -204,7 +204,7 @@ Auto-migrates v7 → v8 on open (spec §9, with a backup meta page). v1–v6 are
 
 ## Test Coverage
 
-**1489 tests** (1479 passing, 10 ignored; unit + integration + doc).
+**1500 tests** (1490 passing, 10 ignored; unit + integration + doc).
 See `docs/TEST_COVERAGE.md` for the full per-file breakdown.
 
 **Testing conventions** — see the Testing Conventions section below before writing any tests.

@@ -131,7 +131,7 @@ let r2 = pq.execute(&[("tx", BindValue::TxCount(2)), ("entity", BindValue::Entit
 
 ```bash
 cargo run          # interactive Datalog REPL
-cargo test         # run 1489 tests
+cargo test         # run 1500 tests
 cargo run < demos/demo_recursive.txt   # recursive rules demo
 ```


@@ -0,0 +1,218 @@
+# Joins (#545) — Plan
+
+Spec: `docs/superpowers/specs/2026-10-11-streaming-engine-design.md` §5.4, §6.1, §6.2,
+§6.3 (#473, part 3 of 9). PRs target `v3`; no closing keyword for #473. #545 closes by
+hand (`gh issue close`) when the last PR merges.
+
+| PR | Steps | Branch |
+|---|---|---|
+| 1 | 1–3: the executor's join rules settled (floats, keyword or ref), `CHANGELOG.md` | `feat/545-join-rules` |
+| 2 | 4–9: join keys, `IndexNestedLoopJoin`, `HashJoin`, planner v2, oracle tests | `feat/545-joins` |
+| 3 | 10–13: pseudo-attributes across joins, `:db/valid-at`, measurement, docs | `feat/545-pseudo-joins` |
+
+Each PR leaves `v3` with no unused code, and updates the test counts and `CHANGELOG.md`
+for what it ships.
+
+## Today's join rules
+
+`PatternMatcher::join_with_pattern` (`src/query/datalog/matcher.rs`) joins the rows so far
+with the next pattern in `optimizer::plan` order, in one of two ways:
+
+- **Hash path.** Taken when the pattern's entity, or else its value, is a variable the
+  rows already bind (the join variable). The pattern is matched against every fact
+  without the rows, and the matches are hashed on `normalize_join_value` of the join
+  variable (a keyword becomes the ref of the entity it names, `edn_to_entity_id`). Other
+  shared variables are compared after the same normalisation. A merged row keeps the
+  row's value for every variable the row binds.
+- **Nested-loop path.** Taken otherwise: no shared variable, or one in the attribute
+  position only, and for pseudo-attribute patterns. Bound variables are substituted into
+  the pattern as constants (`apply_binding_to_component`) and matched with the constant
+  rules of `match_component`: a keyword constant matches the keyword or the ref of the
+  entity it names, a UUID constant a ref or a keyword naming it, a float constant any
+  float within `f64::EPSILON`. A substituted variable is not rebound, so the row's value
+  is kept.
+
+Both paths compare `norm(a) == norm(b)`, with `norm` the keyword-to-ref normalisation.
+The nested-loop path never compares a bound float: a bound entity or value variable
+always takes the hash path, and the attribute position holds keywords only. Two answers
+still depend on the plan (which differs under the `wasm` feature, where patterns are not
+reordered):
+
+- **Floats.** `Value`'s `Hash` hashes `-0.0` and `0.0` differently although `==` holds
+  for them, so a hash join on a float key never pairs them, while the same pair as a
+  non-key shared variable (compared with `==`) does. Elsewhere bound floats are compared
+  within `f64::EPSILON` only where a `not` / `not-join` body substitutes them as
+  constants (`substitute_pattern`), which is #546's anti-join.
+- **Keyword or ref.** A variable bound to a keyword by one pattern and to the ref of the
+  same entity by another returns the kind of whichever pattern ran first. In the
+  nested-loop path this happens through the attribute position: a variable bound to a
+  ref matches the attribute whose keyword names that entity.
+
+## Design decisions not fixed by the spec
+
+Settled with the maintainer on 2026-10-14.
+
+1. **Float joins use IEEE `==`** (§5.4). Two bound floats are join-equal when `==` holds:
+   `0.0` equals `-0.0`, and NaN equals nothing, NaN included. A float *constant* in a
+   pattern keeps the `f64::EPSILON` match (spec §5.4, unchanged). In the executor this
+   is a fix to `Value`'s `Hash`, which breaks the `Hash`/`Eq` contract for `-0.0` today:
+   it now hashes `-0.0` as `0.0`. That covers every hash-keyed comparison of values: the
+   pattern hash join, and the `not`, `not-join` and `or` keys. The epsilon comparison
+   of bound floats substituted into `not` / `not-join` bodies is #546's to settle with
+   the same rule (comment on #546).
+2. **Keyword or ref: the first pattern in `:where` text order** (§5.4). When a variable
+   is bound by several patterns, its value comes from the first of them in the query
+   text. An expression binding (`[(f …) ?v]`) still overwrites the variable where
+   `optimizer::plan` places it, and later joins keep the expression's value. The rule
+   applies to the top-level `:where` of a query (the plan loops of
+   `execute_query_on_executor` and `execute_query_with_rules`). `or` branches, `not`
+   bodies and rule bodies keep today's rule; #546 and #548 decide theirs when they move
+   to the engine.
+   Pseudo-attribute patterns never replace a value: they read metadata of an entity
+   the query has bound, and bind their entity variable only when nothing has.
+3. **`IndexNestedLoopJoin` probes the entity position only.** The join is an
+   `IndexNestedLoopJoin` when the inner pattern's entity is a variable the outer rows
+   bind: one EAVT range per outer row, committed and pending. Every other join, including
+   a join on the value or attribute position and a join with no shared variable (a cross
+   product), is a `HashJoin`. Deviation from spec §6.3, which probes any position an
+   index covers. Two reasons: the pending store has EAVT and AEVT indexes but no AVET,
+   so a value probe reads the attribute's whole pending range once per outer row (every
+   fact of an in-memory database); and a ref probe into the value position must also
+   find the keyword values that name the entity, which no index holds.
+4. **Pseudo-attributes keep today's plan-dependent rule, and a follow-up issue tracks
+   it.** `:db/valid-from`, `:db/valid-to`, `:db/tx-count` and `:db/tx-id` read the fact
+   of the last real pattern, in `optimizer::plan` order, that matched the same entity
+   (the matcher's hidden `__f*_<uuid>` keys, overwritten by each match). The engine
+   reproduces that. `:db/valid-at` joins with every visible fact of the entity, one row
+   per fact. The issue is filed with PR 3.
+5. **Join keys** (§5.4). Two cells are join-equal when:
+   - both are `Eid`, or both `Iid`: the same id;
+   - one is `Iid(k)` and the other `Eid(e)`: `e` is the id of `edn_to_entity_id(k)`
+     (`IdSpace::keyword_eid`, a DICT id or a provisional one, cached like other DICT
+     lookups);
+   - both are `Val`: the same scalar, floats by decision 1. Long strings are one form:
+     `Scan` turns a pending string over 64 bytes into `Long(vref)` when the committed
+     value pages hold it (`KeySource::long_value_ref`), so equal long strings are equal
+     cells (the #544 plan, decision 2, left this to #545).
+   The planner normalises a slot's `Iid` cells only where the two sides can hold
+   different kinds: an entity position holds `Eid`, an attribute position `Iid`, a value
+   position or an expression binding either.
+6. **Which cell a join keeps** (decision 2). The planner records, for each slot, the
+   `:where` index of the pattern that bound it (or "expression"). When a pattern earlier
+   in the text joins on that slot, the output row takes the pattern's cell; otherwise
+   the outer row's. Static per join, no per-row cost.
+7. **`HashJoin` build side.** The side with the smaller estimate: `optimizer`'s
+   `pattern_cost` for the inner pattern against the smallest `pattern_cost` of the outer
+   patterns (`branch_cost`). Ties build on the inner pattern. A key cell that contains a
+   NaN never matches, so such rows are dropped on both sides. Bytes held are counted
+   with #549.
+8. **Join order** stays `optimizer::plan`'s (selectivity order; source order under
+   `wasm`, spec §6.3). With decisions 1 and 2 the answer no longer depends on it, except
+   for pseudo-attributes (decision 4).
+9. **`PreparedQuery` plans per execution**, as in #544 (decision 10 there). Planning is
+   a walk over the clauses; caching the operator tree with bind values as parameters
+   waits for a measurement that shows planning matters. Deviation from spec §6.3's last
+   paragraph, recorded on the issue.
+
+## Steps
+
+### 1. Float joins in the executor (PR 1)
+- `Value`'s `Hash`: `-0.0` hashes as `0.0` (decision 1).
+- Unit test in `types.rs`: equal values hash equally, `-0.0` and `0.0` included.
+- Integration tests (`tests/join_rules_test.rs`): a join on a float value pairs `0.0`
+  with `-0.0`, as the join key and as a shared variable after an entity key; a float
+  constant still matches within epsilon. (A NaN cannot be stored: the parser has no
+  NaN literal.)
+- Comment on #546: the substituted-float epsilon in `not` bodies.
+
+### 2. Keyword or ref by `:where` order in the executor (PR 1)
+- `PatternMatcher::match_with_hint_seeded` takes the set of variables the pattern
+  rebinds (decision 2). The hash path inserts the pattern's value for them; the
+  nested-loop path takes the fact's value at the variable's first position (entity,
+  attribute, value).
+- The two executor plan loops track, per variable, the `:where` index of its binding
+  pattern (expressions mark it as fixed) and pass the set.
+- Integration tests: `[?a :friend ?b] [?b :name "Bob"]` (keyword-valued `:friend`)
+  returns the keyword whatever the plan, and the reversed text the ref; the same through
+  the attribute position and with a rule call; an expression's value is kept by a later,
+  text-earlier pattern. They also pass with `--features wasm` (no reordering).
+
+### 3. PR 1 checks
+- `CHANGELOG.md` (v3.0.0, Breaking changes): the two rules and the queries whose answers
+  change.
+- `cargo fmt`, clippy (native, `wasm`, `browser`/wasm32), `cargo test`,
+  `cargo test --features test-oracle`.
+
+### 4. Join keys (PR 2)
+- `IdSpace::keyword_eid`; `Scan` canonicalises pending long strings (decision 5).
+- `cell::join_eq` and a hashable `JoinKey` (decisions 1, 5).
+- Unit tests: keyword vs ref of the same entity (DICT and provisional), long strings
+  committed vs pending, floats.
+
+### 5. `IndexNestedLoopJoin` (PR 2)
+- `src/query/engine/join.rs`. `Scan` takes a seed row: its `Term::Eq` positions compare
+  with the seed's cells by `join_eq` (a new `Term::Join(slot)`, keeping `Term::Eq` for a
+  variable repeated inside one pattern, which compares exactly as `match_fact_against_pattern`
+  does), its entity range is the probe, and it keeps or replaces each joined cell by
+  decision 6. A provisional entity id has only pending facts.
+- Per outer batch: probes in row order; an outer row with many matches resumes the inner
+  scan across output batches. `close` closes the outer side and the current probe.
+- Counters: outer rows in, inner keys and facts read, rows out.
+
+### 6. `HashJoin` (PR 2)
+- Builds on one side (decision 7), streams the other, emits rows in the streamed side's
+  order. An empty key is a cross product.
+
+### 7. Planner v2 (PR 2)
+- Eligible: every clause is a pattern with a real attribute, an expression, or a
+  pseudo-attribute pattern on the first pattern's entity (#544's shapes); `:find` plain
+  variables; as #544 otherwise. Pseudo-attribute patterns anywhere else wait for PR 3.
+- Clauses in `optimizer::plan` order; the first pattern is a `Scan`, each later pattern an
+  `IndexNestedLoopJoin` or a `HashJoin` (decision 3), each expression a `Filter`/`Bind`.
+
+### 8. Oracle tests (PR 2)
+- `tests/engine_oracle_test.rs`: two- and three-pattern joins on entity, value and
+  attribute positions; cross products; keyword vs ref in both text orders; floats
+  `0.0`/`-0.0`/NaN; long strings committed vs pending; pending shadowing committed in
+  the inner pattern; in-memory and file-backed, before and after a checkpoint and a
+  reopen; `:as-of` and `:valid-at` on joins.
+- `cargo test --features test-oracle` over the whole suite: most multi-pattern queries in
+  the existing suites now run on the engine.
+
+### 9. PR 2 checks
+- As step 3, plus binary size (`binary-size.yml`) and the #394 envelope at 100K/1M on the
+  bench machine for the three join shapes and the #379 point queries.
+
+### 10. Pseudo-attributes across joins (PR 3)
+- Each real pattern's scan fills metadata columns only when a pseudo-attribute pattern
+  may read it. A pseudo-attribute pattern reads, per row, the metadata of the last real
+  pattern before it in plan order whose entity cell is join-equal to its entity
+  (decision 4).
+- Eligible when its entity term is the entity term of a real pattern planned before it
+  (the matcher's fast path then always applies), or when no real pattern is planned
+  before it (it then matches every visible fact of the entity: a `Scan` of `[e _ _]`
+  with the metadata column). Other shapes stay on the executor.
+- `:db/valid-at`: a join with `[e _ _]` and a constant column (the query's valid time,
+  `Null` under `:any-valid-time`).
+
+### 11. Follow-up issue (PR 3)
+- Pseudo-attribute metadata depends on plan order (decision 4); milestone v3.0.0, label
+  `query`.
+
+### 12. Measurement (PR 3)
+- #394 envelope at 100K, 1M and 10M on the bench machine, idle: the join shapes
+  (`follows_name`, `manager_peers`, `group_members`), point queries, peak RSS.
+  `docs/BENCHMARKS.md` rows.
+
+### 13. Docs (PR 3)
+- `CHANGELOG.md`: multi-pattern queries stream.
+- `CLAUDE.md` module list (`join.rs`), test count; `ROADMAP.md`; `docs/TEST_COVERAGE.md`;
+  `README.md` count.
+- Docs site (`../minigraf-docs`): `content/architecture.md` query-engine section, and
+  `content/datalog-reference.md` for the join rules (decisions 1, 2), under
+  `@since v3.0.0`.
+- Comment on #545 for decisions 3 and 9.
+
+## Bindings
+
+No public API change and no new error code, so no binding cascade.
@@ -96,6 +96,10 @@ impl std::hash::Hash for Value {
             Value::Float(f) => {
                 if f.is_nan() {
                     0_u8.hash(state);
+                } else if *f == 0.0 {
+                    // `-0.0 == 0.0`, so both must hash alike (#545).
+                    2_u8.hash(state);
+                    0_u64.hash(state);
                 } else if f.is_sign_negative() {
                     1_u8.hash(state);
                     (-f).to_bits().hash(state);
@@ -728,4 +732,21 @@ mod tests {
             }
         }
     }
+
+    /// Equal values hash alike (#545): `-0.0 == 0.0`.
+    #[test]
+    fn equal_floats_hash_alike() {
+        use std::hash::{BuildHasher, RandomState};
+        let h = RandomState::new();
+        assert_eq!(
+            h.hash_one(Value::Float(-0.0)),
+            h.hash_one(Value::Float(0.0)),
+            "-0.0 and 0.0"
+        );
+        assert_ne!(
+            h.hash_one(Value::Float(-1.0)),
+            h.hash_one(Value::Float(1.0)),
+            "-1.0 and 1.0"
+        );
+    }
 }
@@ -858,6 +858,8 @@ impl StratifiedEvaluator {
                                 &p,
                                 hint.as_ref()
                                     .unwrap_or(&crate::query::datalog::optimizer::IndexHint::Eavt),
+                                // Rule bodies keep today's rule until #548.
+                                &[],
                             );
                         }
                         WhereClause::Expr { expr, binding: out } => {