Repository navigation
Commit fdb5ed4
Detect fold pipelines in DataFusion's plans: demo 1's attention (#72)
🪭 Claude (einfold)
Fourth of M2's stack, on #70's `PipelineNode`. `DetectFolds` now finds
demo 1's causal attention, written in plain SQL, in DataFusion's
optimized plans, and replaces it with a `PipelineNode`, keeping the plan
it replaced as the fallback. That makes demo 1's "found, not told"
criterion testable. The rule mentions no attention-specific operator. It
matches the parts of a softmax-weighted average of a fold's results
(`detect_pipelines.rs`):
- **the scores:** a fold, as the rule's first shape, under a projection
of its group keys and its sum, scaled by `* c`, `/ c`, or neither. Its
join may carry **conditions** comparing two of its group keys, such as
`q.t >= k.t`, which become the fold's mask (#59). Any other join
condition declines;
- **the weights:** `exp(s - m)`, with `m` the largest score per kept
key, in either spelling:
- a window, `MAX(s) OVER (PARTITION BY i)`, over the whole partition,
with no `ORDER BY` or filter;
- `MAX(s) … GROUP BY i` joined back on `i`, which is ddx's spelling.
Or `exp(s)`, with no shift;
- **the average:** `SUM(w * v.x)`, grouped by the kept key and the
values' other columns, over the weights joined with a values relation on
the summed key, divided by either:
- `norm.z`: the same weights summed per kept key, joined on it and
grouped by too. This is demo 1's spelling, and `Normalizer::KeptGroups`;
- `SUM(w)` in the same aggregate: `Normalizer::JoinedRows`, as a kernel
smoother or recommender writes it.
**What must hold, or it declines:**
- DataFusion copies each CTE into every place it's read, so the scores
and weights appear two to four times. Every copy must be the same fold,
with the same scale and shift. Otherwise the shift wouldn't cancel
between the numerator and the normalizer.
- The maximum must be taken per the kept key, not the summed one.
- The joins must be plain inner equi-joins on `=`.
**Order.** Pipelines are found from the top down, before folds: a
pipeline's scores are themselves a fold, which the rule's bottom-up pass
would replace first. `DetectFolds::detect` runs both passes, and
`EinFoldQueryPlanner` calls it. As an `OptimizerRule`, `DetectFolds`
still finds folds only.
**Refactor.** Fold analysis (`analyze`) is split out of the first shape,
so pipelines can reuse it, and so it can take a join's comparisons as
conditions. A fold with conditions on its own is still left alone, since
the fold kernels don't compute masks yet.
**Invariants** (`tests/detect_pipelines.rs`, 1,500 cases searched), for
random `q`, `k`, `v`, complete or with a hole, and queries drawn from:
- both spellings;
- three scales;
- four masks: either way round, strict or not, or none;
- the `SUM(w) / SUM(w)` form with no shift;
- five look-alikes: a maximum partitioned by the summed key; one with
`ORDER BY`; a normalizer of `exp(2w)`; a normalizer of weights over the
same fold scaled differently; and an unmasked fold, which the M1 tests
already cover.
The invariants:
1. The same rows as DataFusion, values within `1e-9`.
2. A pipeline found exactly when the query is one.
3. The fused algorithm run whenever the tables are complete.
The first draft accepted a maximum partitioned by the summed key, which
the look-alikes caught. A mutant that skips the normalizer's same-scores
check survived until the different-scale look-alike went in. One mutant
is equivalent: a scores relation's only bare `DOUBLE` column is the
score. `detect_vs_host.rs` still passes.
**Not yet.** One spelling waits for a later PR: a projection that reads
`norm.z`. ddx's attention program, which normalizes inside the sum, is
this PR's second commit (#76). The Gaussian-kernel average, whose
producer isn't a sum of products, is #99 to #102, which add row
expressions.
**Size.** About 810 lines that aren't tests, 620 of them the new
matcher. It is one rule: each part (scores, weights, maximum,
normalizer, consumer) is checked against the others, so splitting it
would leave pieces that can't be tested on their own.
<!--
- [x] cargo fmt / clippy -D warnings / test / doc -D warnings / reuse
lint
-->
It also finds attention normalized inside the sum, `SUM(w / norm.z *
v.x)`, the spelling ddx (an XQL Systems project for differentiating SQL
queries) can differentiate, since it groups by no key that depends on a
differentiated column. Fixes #76.
## After CodeRabbit's review
- **Detection declines three more look-alikes:** a projection with two
score columns, one that shows a group key twice (and so hides another),
and a join of the scores to their maximum that matches NULL keys.
- **The property test damages its tables in more ways.** One of `q`, `k`
and `v` sometimes has a row missing or repeated, a NULL value, a NaN or
infinite value, a NULL key, or no rows at all. With NaN and infinite
values the tables are still complete, so the fused algorithm must still
run and agree. 1,500 cases 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]>1 parent 7ac28a8 commit fdb5ed4
5 files changed
Lines changed: 1268 additions & 31 deletions
File tree
- crates/einfold-datafusion
- src
- tests
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
49 | 49 | | |
50 | 50 | | |
51 | 51 | | |
52 | | - | |
53 | | - | |
| 52 | + | |
| 53 | + | |
54 | 54 | | |
55 | 55 | | |
| 56 | + | |
56 | 57 | | |
57 | 58 | | |
58 | 59 | | |
| |||
99 | 100 | | |
100 | 101 | | |
101 | 102 | | |
| 103 | + | |
| 104 | + | |
| 105 | + | |
| 106 | + | |
| 107 | + | |
| 108 | + | |
| 109 | + | |
| 110 | + | |
| 111 | + | |
| 112 | + | |
| 113 | + | |
| 114 | + | |
| 115 | + | |
| 116 | + | |
| 117 | + | |
| 118 | + | |
| 119 | + | |
| 120 | + | |
| 121 | + | |
| 122 | + | |
| 123 | + | |
| 124 | + | |
| 125 | + | |
| 126 | + | |
| 127 | + | |
| 128 | + | |
102 | 129 | | |
103 | 130 | | |
104 | 131 | | |
| |||
253 | 280 | | |
254 | 281 | | |
255 | 282 | | |
256 | | - | |
257 | | - | |
258 | | - | |
| 283 | + | |
| 284 | + | |
| 285 | + | |
| 286 | + | |
| 287 | + | |
| 288 | + | |
| 289 | + | |
| 290 | + | |
| 291 | + | |
259 | 292 | | |
260 | 293 | | |
261 | 294 | | |
| |||
267 | 300 | | |
268 | 301 | | |
269 | 302 | | |
| 303 | + | |
| 304 | + | |
| 305 | + | |
| 306 | + | |
| 307 | + | |
| 308 | + | |
270 | 309 | | |
271 | | - | |
| 310 | + | |
| 311 | + | |
272 | 312 | | |
| 313 | + | |
| 314 | + | |
| 315 | + | |
| 316 | + | |
| 317 | + | |
| 318 | + | |
| 319 | + | |
| 320 | + | |
| 321 | + | |
| 322 | + | |
| 323 | + | |
| 324 | + | |
| 325 | + | |
| 326 | + | |
| 327 | + | |
| 328 | + | |
| 329 | + | |
| 330 | + | |
| 331 | + | |
| 332 | + | |
| 333 | + | |
| 334 | + | |
| 335 | + | |
| 336 | + | |
| 337 | + | |
| 338 | + | |
| 339 | + | |
| 340 | + | |
| 341 | + | |
| 342 | + | |
| 343 | + | |
| 344 | + | |
| 345 | + | |
273 | 346 | | |
274 | 347 | | |
275 | 348 | | |
| |||
291 | 364 | | |
292 | 365 | | |
293 | 366 | | |
294 | | - | |
| 367 | + | |
295 | 368 | | |
296 | 369 | | |
297 | 370 | | |
| |||
374 | 447 | | |
375 | 448 | | |
376 | 449 | | |
| 450 | + | |
| 451 | + | |
| 452 | + | |
| 453 | + | |
| 454 | + | |
| 455 | + | |
| 456 | + | |
| 457 | + | |
| 458 | + | |
| 459 | + | |
377 | 460 | | |
378 | 461 | | |
379 | 462 | | |
| |||
393 | 476 | | |
394 | 477 | | |
395 | 478 | | |
| 479 | + | |
396 | 480 | | |
397 | 481 | | |
398 | | - | |
| 482 | + | |
399 | 483 | | |
400 | 484 | | |
401 | 485 | | |
402 | 486 | | |
403 | 487 | | |
404 | 488 | | |
405 | 489 | | |
406 | | - | |
407 | | - | |
408 | | - | |
409 | | - | |
410 | | - | |
411 | | - | |
412 | | - | |
| 490 | + | |
413 | 491 | | |
414 | 492 | | |
415 | | - | |
416 | | - | |
417 | | - | |
418 | | - | |
419 | | - | |
420 | | - | |
421 | | - | |
422 | | - | |
| 493 | + | |
| 494 | + | |
| 495 | + | |
| 496 | + | |
| 497 | + | |
| 498 | + | |
| 499 | + | |
| 500 | + | |
| 501 | + | |
| 502 | + | |
| 503 | + | |
| 504 | + | |
| 505 | + | |
| 506 | + | |
| 507 | + | |
| 508 | + | |
| 509 | + | |
| 510 | + | |
| 511 | + | |
| 512 | + | |
| 513 | + | |
| 514 | + | |
| 515 | + | |
| 516 | + | |
| 517 | + | |
| 518 | + | |
| 519 | + | |
| 520 | + | |
| 521 | + | |
| 522 | + | |
| 523 | + | |
| 524 | + | |
| 525 | + | |
| 526 | + | |
| 527 | + | |
| 528 | + | |
| 529 | + | |
| 530 | + | |
423 | 531 | | |
424 | 532 | | |
425 | 533 | | |
| |||
0 commit comments