Find products whose factors read three or more relations, as folds of regrouped operands - #131

Co-Authored-By: Claude Opus 5.5 <[email protected]>
Claude-Session: https://claude.ai/code/session_01M96xSez6PZwTmfaGh2eJgS

🪭 Claude (einfold)

This sets einfold for Python's version to `0.2.0rc1`. Once it merges and
`python-v0.2.0rc1` is tagged on it, the release candidate goes to PyPI.
Users then get it with `pip install --upgrade --pre
"einfold[datafusion]"`, and the plain install keeps 0.1.0. It's for
xarray-sql's acceptance testing. xarray-sql is an XQL Systems project
that queries Xarray datasets with SQL.

It holds the first part of M3, from [spike
S31](docs/spikes/s31-ddx-gradient-steps/README.md):
- #129 reads ddx's fill as a domain's default. ddx is an XQL Systems
project for automatic differentiation of SQL queries.
- #131 finds products whose factors read three or more relations.
- #132 runs DataFusion's own functions in einfold's library rather than
through the FFI.

On xarray-sql's demos, from a local build of these changes on an
i7-8700, in medians of 3 runs:

| | 0.1.0 | 0.2.0rc1 | DataFusion | DuckDB |
|---|---:|---:|---:|---:|
| attention gradient, 1,024 tokens, window | 2.30 s | 0.90 s | 4.03 s |
5.42 s |
| attention gradient, 1,024 tokens, `GROUP BY` | 1.89 s | 0.59 s | 4.67
s | 7.60 s |
| GPT training step, nanoGPT's CPU size | 4.03 s | 2.61 s | 12.05 s | |

That's 4.5× and 7.9× DataFusion on attention's gradient, and 4.6× on the
GPT step, past M3's gate of 4× (design v20).

Two of the gate's items aren't met yet, and stay open for M3:
- A flat chain of three matrix products is faster than both hosts at 64
and 96, but ties DataFusion at 32 × 32. Choosing the contraction order
would fix that.
- einfold changes none of TPC-H's 22 plans, but from Python each query
pays the FFI's fixed cost: 1.06× DataFusion's time at scale factor 1.

## Decisions to review

- **A release candidate now,** before M3 is done, so that xarray-sql
tests the gradient work while the rest of M3 continues: the contraction
order, the FFI's per-query cost (#81, #58), and the fused backward pass,
which waits on xqlsystems/ddx#243.

🤖 Generated with [Claude Code](https://claude.com/claude-code)

https://claude.ai/code/session_01M96xSez6PZwTmfaGh2eJgS

Co-authored-by: Claude Opus 5.5 <[email protected]>

🪤 Claude (fuzz adversary)

The simulation, einfold's random differential test against plain
DataFusion, now generates the three shapes that #129 and #131 taught
detection to find. Each run before this one reached none of them.
Nothing changes for users. These are the generators for the soak of
0.2.0rc1.

## Decisions to review

- **Fills with other constants**
([`fill`](https://github.com/xqlsystems/einfold/blob/8ec90e5/crates/einfold-datafusion/tests/simulation/queries.rs#L430)).
A fold from a domain, or joined back to one, now reads its sum through
`COALESCE`, ddx's `CASE`, and the `IS NOT NULL` form DataFusion writes
for `COALESCE`. ddx is an XQL Systems project for automatic
differentiation of SQL queries. The constant is `0.0`, `-0.0`, `1.0`,
`-2.5`, NaN or `-inf`. Some fills sit inside an expression or inside
another fill. The look-alikes are:
  - the bare sum;
  - the sum filled with a column;
  - two fills of one sum.

The two fills test the sum with `IS NULL` and with `IS NOT NULL`. If
both tested it the same way, DataFusion would compute the shared test in
a projection below, and no fill would reach detection. I first wrote
them alike, and a planted bug went unseen.
- **Finite values in some cases**
([`data.rs`](https://github.com/xqlsystems/einfold/blob/8ec90e5/crates/einfold-datafusion/tests/simulation/data.rs#L203)).
With values that are all finite or NULL, in 30% of cases, the dense
algorithm can take operands with missing rows, which is #129's purpose.
A NaN or an infinity anywhere kept it from doing so before. The tally
counts these cases, and a run of 10,000 cases or more asserts that one
happened (4 in 2,000 here).
- **Products over three relations**
([`three_relations`](https://github.com/xqlsystems/einfold/blob/8ec90e5/crates/einfold-datafusion/tests/simulation/queries.rs#L598)).
The third relation is `d` as `m`. It joins `l`, `r` or both, and the
factor on its side reads it, or neither factor does. The join order is
drawn, or the joins are written as a comma join. Factors use `*`, `-`,
`%`, or (with inexact values) `/`, and groups may be `m`'s keys. The
look-alikes are both factors reading `m`, and `m` joining both sides
with neither factor reading it. `d` and the operands get NULL keys more
often
([here](https://github.com/xqlsystems/einfold/blob/8ec90e5/crates/einfold-datafusion/tests/simulation.rs#L271)),
since a NULL key in the regrouped join must join nothing.
- **Float `/` and `%` in factors**
([`factor`](https://github.com/xqlsystems/einfold/blob/8ec90e5/crates/einfold-datafusion/tests/simulation/queries.rs#L114)).
With exact values these are `v / v`, `1.5 % v` and `v / 2.0`, all exact.
With inexact values it is `1.0 / v`, whose magnitude the bound's twin
tables still give.
- **Integer `/` and `%` that fail only on dropped rows**
([here](https://github.com/xqlsystems/einfold/blob/8ec90e5/crates/einfold-datafusion/tests/simulation/queries.rs#L131)).
The divisor is 0 exactly where the join key is NULL. The existing
fallible factor casts `v` to `BIGINT`, and that cast already keeps the
factor above the join, so no factor before this one tested whether
integer division moves.

## How it is tested

The invariants are unchanged: the same rows as the host, bit for bit
with exact values; the same errors; and the rest listed at the top of
`simulation.rs`. To check that the new generators reach the new code, I
planted bugs in it. Each ran for 2,000 cases from seed 777000.

| Planted bug | Caught |
|---|---|
| `fill_default` accepts two fills of different constants | 6 `[rows]`
and `[kernels]` failures |
| Integer `%` counts as movable | 10 `[error]` failures |
| The regrouped join makes NULL equal NULL | 3 in 500 cases forced to
three relations with einfold's kernels; about 1 in 10,000 in the normal
mix |
| `join_back.rs` keeps a `-0.0` default | not seen |

Bug 4 can't change a result. With a `-0.0` default, the dense algorithm
doesn't take missing rows, so the node runs the host's plan
(`host_plans=1`). The filter is a second guard that no output shows.

On main, 2,000 cases from seed 777000 pass.

## Not in this pull request

- A soak of 0.2.0rc1 with these generators, dispatched in CI once this
is up. Findings will go to issues.
- An invariant for #132: that relinking DataFusion's functions in the
Python bridge changes no function's answer, under session settings such
as a time zone. It belongs in Python tests.

🤖 Generated with [Claude Code](https://claude.com/claude-code)

https://claude.ai/code/session_01SCMAk87qC9VKCk22P7HDH1

---------

Co-authored-by: Claude Opus 5.5 <[email protected]>

… guard (#143)

🪭 Claude (einfold)

A `SUM` of a product of three factors, each from one of three
inner-joined tables, now runs as one fold of three operands, which
einfold computes as two dense matrix products in the cheaper order. A
chain of matrix products, `SUM(a.v * b.v * c.v)` over `a JOIN b ON a.j =
b.j JOIN c ON b.k = c.k`, no longer builds the join's `n³` rows.
`EXPLAIN` shows it as `Fold: a,b * b,c * c,d -> a,d`. This closes M3's
chain item, and the design moves to v21.

Through the Python package (an i7-8700, best of 3–7 runs), against
DataFusion and DuckDB 1.5.6:

| `n` | matrices: einfold | DataFusion | DuckDB | matrix·matrix·vector:
einfold | DataFusion | DuckDB |
|---:|---:|---:|---:|---:|---:|---:|
| 32 | 4.0 ms | 12.3 ms | 37.5 ms | 4.1 ms | 3.2 ms | 4.3 ms |
| 64 | 4.8 ms | 104 ms | 333 ms | 4.1 ms | 4.6 ms | 10.7 ms |
| 96 | 6.4 ms | 1,506 ms | 1,583 ms | 4.4 ms | 15.2 ms | 29.6 ms |
| 128 | 6.2 ms | 2,808 ms | 5,093 ms | 4.7 ms | 21.5 ms | 49.6 ms |

The flat chain used to tie DataFusion at `n = 32` (12 ms). The
matrix–vector chain at `n = 32` is still 0.8× DataFusion: einfold's 4 ms
there is the Python bridge's fixed cost per query (#81, #58), the same
at every size.

## Decisions to review

- **One operator, not a rewrite of the plan**
([`chain.rs`](https://github.com/xqlsystems/einfold/blob/0b67e4b/crates/einfold-kernels/src/chain.rs)).
The kernel runs the dense algorithm twice through an intermediate of the
kept dimensions, choosing the pair to contract first by its cost in
multiplications from the extents, when it runs. The design's relational
form (nested `GROUP BY`s) moves to M5: its guard needs a `SUM(abs(…))`
beside each intermediate sum, and einfold detects one aggregate per
query until M5.
- **The float guard, checked on the factors**
([`guarded`](https://github.com/xqlsystems/einfold/blob/0b67e4b/crates/einfold-kernels/src/chain.rs#L162)).
Reordering changes which floats are added, so the chain runs only where
every factor is finite and the product over the operands of their
largest magnitude times their row count is at most 2¹⁰⁰⁰. That bounds
every partial sum in either order, so neither overflows. Otherwise it
runs the host's plan, as it does wherever the dense algorithm declines.
The bound is coarse, so data that is merely large but safe runs the
host's plan. A tighter one would need the intermediates' sums of
magnitudes, as above.
- **The widened bound** ([design
8.6](https://github.com/xqlsystems/einfold/blob/0b67e4b/docs/design.md#86-numerics-determinism-and-precision)).
Multiplying an intermediate sum, rather than each term, rounds each term
differently, so the bound widens by `2·u·Σ|terms|`, as the online
softmax's `exp` roundings widen it.
- **Detection prefers a chain, and keeps #131's fold behind it**
([`fold`](https://github.com/xqlsystems/einfold/blob/m3/chain-order/crates/einfold-datafusion/src/detect_folds.rs#L323)).
The two-operand fold of the same product, whose join operand repeats
each key tuple, never ran dense, but by default it ran the
discrimination algorithm. Where the chain declines (text, negative or
NULL keys, duplicates, special values, or the guard), it runs that fold,
by einfold's kernels, rather than the host's plan. Without one, it runs
the host's. A product where a factor reads two tables, such as
attention's `exp(s − m) / z · v`, is still #131's alone. A chain takes
no domain yet, so it isn't joined back to one.

## How it is tested

`chains_answer_as_the_host_does`
([`chains_vs_host.rs`](https://github.com/xqlsystems/einfold/blob/0b67e4b/crates/einfold-datafusion/tests/chains_vs_host.rs))
draws five shapes (chains, matrix–vector, batched, a star sharing one
key, and a chain also grouped by a joined key), with joins and products
in random orders. The tables are complete, or have missing rows,
duplicates, NULL or negative keys, NULLs, NaN, infinities and values
near overflow. It checks:
- the same groups, NULLs, NaNs, infinities and signed zeros as the host;
- the same bits for small integers;
- otherwise agreement within `2·(n + 2)·u·Σ|terms|`, with `Σ|terms|`
from the host;
- coverage: the chain ran dense in some cases and the host's plan in
others.

Half its cases run einfold's default rule, under which a declined chain
runs that fold. It passed 4,000 cases. It caught a disabled guard (inf
against NaN), the swapped fold reading unswapped operands, and the
intermediate's keys reversed. The rest of the workspace, 6,000
simulation cases and the Python tests pass.

🤖 Generated with [Claude Code](https://claude.com/claude-code)

https://claude.ai/code/session_01M96xSez6PZwTmfaGh2eJgS

---------

Co-authored-by: Claude Opus 5.5 <[email protected]>

🪭 Claude (einfold)

This sets einfold for Python's version to `0.2.0rc2`. Once it merges and
`python-v0.2.0rc2` is tagged on it, the release candidate goes to PyPI.
Users then get it with `pip install --upgrade --pre
"einfold[datafusion]"`, and the plain install keeps 0.1.0. It's for
xarray-sql's acceptance testing. xarray-sql is an XQL Systems project
that queries Xarray datasets with SQL. xarray-sql passed 0.2.0rc1
(xqlsystems/xarray-sql#285).

Since rc1:
- #143 computes a chain of three products, such as `SUM(a.v * b.v *
c.v)` over three joined tables, as two dense products in the cheaper
order. It reorders only where a float guard shows no sum can overflow,
and otherwise runs #131's fold or the host's plan. A chain of matrix
products is now 3× DataFusion at `n = 32` (it tied in rc1), 22× at 64,
and 450× at 128. DuckDB is slower than DataFusion at every size
measured.
- #140 fixes #136: from Python, functions now run with the session's
configuration, so `to_unixtime` reads text in the session's time zone.
0.1.0 and rc1 read it in UTC.
- #141 checks that einfold changes no built-in function's answer from
Python, under two time zones.
- #134 and #142 extend the simulation, einfold's random comparison
against DataFusion, to rc1's new shapes, and fix its pairing of rows
that differ only in a zero's sign (#138).

Still open for M3: a chain whose last factor is a vector is 0.8×
DataFusion at `n = 32` (4.1 ms against 3.2 ms), and TPC-H is 1.06×
DataFusion's time. Both are the Python bridge's fixed cost per query
(#81, #58). The fused backward pass waits on xqlsystems/ddx#243.

🤖 Generated with [Claude Code](https://claude.com/claude-code)

https://claude.ai/code/session_01M96xSez6PZwTmfaGh2eJgS

Co-authored-by: Claude Opus 5.5 <[email protected]>

🪭 Claude (einfold)

Sets einfold for Python's version to `0.2.0`. Once this merges, the tag
`python-v0.2.0` publishes it to PyPI, and `pip install --upgrade
"einfold[datafusion]"` gets it without `--pre`. It's the same code as
0.2.0rc2, which xarray-sql acceptance-tested. xarray-sql is an XQL
Systems project that queries Xarray datasets with SQL. The maintainer
approved the release.

Since 0.1.0:
- #129, #131 and #143 add folds with a fill as the domain's default,
regrouped operands, and chains of three products in the cheaper order,
under a float guard. A chain of matrix products is 3× DataFusion at `n =
32`, 22× at 64, and 450× at 128.
- #132 and #140 run DataFusion's default functions in einfold's library,
with the session's configuration. `to_unixtime` reads text in the
session's time zone (#136).
- #141 checks that einfold changes no built-in function's answer from
Python. #134 and #142 extend the simulation to the new shapes.

Known issues, for later releases:
- #145 and #146: a `DataFrame` that reads an in-memory table fails once
its `SessionContext` is dropped. The cause is in datafusion-python; the
workaround is to keep the context alive.
- The Python bridge's fixed cost per query (#81, #58): a chain whose
last factor is a vector is 0.8× DataFusion at `n = 32`, and TPC-H is
1.06× DataFusion's time.

## Decisions to review

None.

🤖 Generated with [Claude Code](https://claude.com/claude-code)

https://claude.ai/code/session_01M96xSez6PZwTmfaGh2eJgS

Co-authored-by: Claude Opus 5.5 <[email protected]>