Skip to content

Commit 21f99d6

Browse files
alxmrsclaude
andcommitted
Address review: complete SQL statements, nanoGPT's model, introductions
- Attention: each spelling's forward pass and gradient is now one complete SQL statement. The gradient with respect to Q, K and V is a single query (grad of three columns of a join), as fast as three statements sharing a backward pass. - nanoGPT: match model.py. Layer norms have learned gains (ln_1, ln_2, ln_f), the MLP uses GELU (its tanh approximation; DataFusion has no erf), and the residual projections use GPT-2's scaled initialization. The hyperparameters name their GPTConfig counterparts, and the docstring lists what still differs: size, optimizer, dropout. - TODO(xqlsystems/ddx#142) on each window MAX wrapped in ddx_stop_gradient. - Introduce every project, paper and term before using it, in the demos, their README and xarray_sql.ad; record the rule, and the TODO exception to the no-issue-numbers rule, in AGENTS.md. - Drop the README's "Gradients in SQL" section until the feature is ready to announce, and the stale --lazy flag from benchmarks/ml/README.md. Co-Authored-By: Claude Opus 5.5 <[email protected]> Claude-Session: https://claude.ai/code/session_01NyN7idACeDMh94qrnFMu6h
1 parent 2767ea5 commit 21f99d6

9 files changed

Lines changed: 291 additions & 154 deletions

File tree

‎AGENTS.md‎

Lines changed: 10 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,16 @@ summarizes recurring maintainer review feedback so changes land clean.
88
- Keep docstrings and comments self-contained. Do **not** put GitHub issue or PR
99
numbers in docstrings or code comments; a reader should not need the issue
1010
tracker to understand the code. Issue references belong in the commit message
11-
and PR description (e.g. `Closes #189`), not in the source.
11+
and PR description (e.g. `Closes #189`), not in the source. The one exception
12+
is a workaround's `TODO`, which names the issue that would remove it:
13+
`TODO(#NN): <action item>`, or `TODO(owner/repo#NN): <action item>` for an
14+
issue in another repository. The comment still explains the workaround.
15+
- Introduce every reference before relying on it. The first time a document
16+
(a docstring, comment, README or docs page) mentions a project, paper,
17+
algorithm, dataset or term of art, such as einfold, FlashAttention or a
18+
section of another project's design, say in a few words what it is, and link
19+
it where there is a link. Don't assume the reader has the context of the
20+
conversation that produced the code.
1221
- Do not reference the review conversation, chat, or "the reporter" in comments.
1322
Describe the behavior, not how it came up.
1423

‎README.md‎

Lines changed: 0 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -237,30 +237,6 @@ Some highlights:
237237
* Dense tensor operations are slower in SQL than Xarray. It seems like the vanilla HashJoin implementation in standard DB engines are not as performant as array ops (they don't take advantage of contiguous array layouts), though this gives us some idea for how it could [one day be possible](https://github.com/xqlsystems/einfold).
238238
* Sparse tensor operations are just as fast (or faster!) than Xarray today. Specifically, SQL is an excellent way to perform regridding and reprojecting between different spatial scales (see also: we include a `proj` udf via the `xarray-sql[geo]` extra).
239239

240-
## Gradients in SQL
241-
242-
With the `ml` extra (`pip install "xarray-sql[ml]"`), a `Context` takes
243-
gradients of queries with [ddx](https://github.com/xqlsystems/ddx). In a
244-
select list, `grad(loss, column)` is, at each row, the derivative of the
245-
number the CTE `loss` computes with respect to that row's `column`. A
246-
gradient-descent step on a parameter table is then one statement:
247-
248-
```python
249-
ctx.sql("""
250-
WITH pred AS (
251-
SELECT x.sample, SUM(x.value * w.val) AS y
252-
FROM x JOIN w ON x.feature = w.feature GROUP BY x.sample),
253-
loss AS (
254-
SELECT AVG(power(pred.y - t.value, 2)) AS l
255-
FROM pred JOIN t ON pred.sample = t.sample)
256-
SELECT feature, val - 0.1 * grad(loss, val) AS val FROM w
257-
""")
258-
```
259-
260-
[`benchmarks/ml`](benchmarks/ml) trains a small GPT and runs attention and
261-
a GraphCast-shaped weather model this way, checked against JAX and timed on
262-
several engines.
263-
264240
## Why does this work?
265241

266242
Underneath Xarray, Dask, and Pandas, there are NumPy arrays. These are paged in

‎benchmarks/ml/01_attention.py‎

Lines changed: 117 additions & 47 deletions
Original file line numberDiff line numberDiff line change
@@ -8,28 +8,39 @@
88
# [tool.uv.sources]
99
# xarray-sql = { path = "../../", editable = true }
1010
# ///
11-
"""Demo 1: attention in SQL, the query einfold should turn into FlashAttention.
12-
13-
Attention, the core of a transformer, is ``softmax(Q·Kᵀ/√d)·V``. In the
14-
XQL model, ``Q``, ``K`` and ``V`` are tables of ``(t, d, x)`` (token,
15-
feature, value), and attention is two folds over joins: an einsum for the
16-
scores, and a weighted average of ``V`` with weights ``exp(score)``.
17-
18-
The SQL below is the naive plan, which stores every one of the N×N
19-
scores. FlashAttention never does: it streams tiles of keys past tiles of
20-
queries, with an online softmax. einfold's first target is to find that
21-
plan from this SQL, in both of its spellings, with no attention-specific
22-
rule (einfold's ``docs/demos.md``, Demo 1). This script is the baseline
23-
that plan must match and beat:
24-
25-
* **forward**: each spelling on each host, against a JAX reference;
26-
* **gradient**: ddx differentiates the same SQL with respect to Q, K
27-
and V, against ``jax.grad``;
11+
"""Demo 1: causal attention in SQL, on several engines, with its gradient.
12+
13+
Attention, the core of a transformer, is ``softmax(Q·Kᵀ/√d)·V``: each
14+
token's output is an average of the value vectors ``V``, weighted by how
15+
well the token's query in ``Q`` matches each earlier token's key in ``K``.
16+
Here ``Q``, ``K`` and ``V`` are tables of ``(t, d, x)`` (token, feature,
17+
value), registered from xarray Datasets, and attention is two sums over
18+
joins: the scores, a sum of ``Q`` times ``K`` over features, and the
19+
average of ``V`` weighted by ``exp(score)``.
20+
21+
This SQL is the naive plan: it stores every one of the N×N scores.
22+
FlashAttention (Dao et al., 2022, https://arxiv.org/abs/2205.14135)
23+
computes the same result without storing them, by streaming blocks of
24+
keys past blocks of queries and keeping a running softmax. einfold
25+
(https://github.com/xqlsystems/einfold), a query optimizer that rewrites
26+
SQL plans into array algorithms like this one, aims to find that plan
27+
from this SQL, in both of the spellings below, with no rule written for
28+
attention. It is the first of einfold's three target demos
29+
(``docs/demos.md`` in its repository). This script is the baseline that
30+
plan must match and then beat:
31+
32+
* **forward**: each spelling on each *host* (einfold's word for an engine
33+
that runs a plan; here DataFusion and DuckDB), checked against the same
34+
attention in JAX, Google's library for differentiable array programs;
35+
* **gradient**: the gradient of a loss with respect to every value of Q,
36+
K and V, as one SQL statement. ddx (https://github.com/xqlsystems/ddx),
37+
which differentiates SQL queries, computes it, and ``jax.grad`` checks
38+
it;
2839
* **masks are absent rows**: an infinity in V reaches only the queries
2940
allowed to see it, as SQL's semantics require of any faster plan;
3041
* **a control that is not attention**: the Nadaraya–Watson estimator, a
31-
Gaussian-kernel weighted average used in regridding. The rules that
32-
fuse attention must fuse it too.
42+
Gaussian-kernel weighted average used in regridding. Any rule that
43+
speeds up attention must speed up this query too.
3344
3445
Run ``uv run benchmarks/ml/01_attention.py --help`` for the options.
3546
"""
@@ -48,12 +59,14 @@
4859

4960
D = 64 # features per head; the scores are scaled by 1/√64 = 1/8.
5061

51-
# The scores, softmax and weighted average, in einfold's window spelling.
52-
# The causal mask is a join predicate: a masked (i, j) pair is a row that
53-
# does not exist. The max only keeps exp() from overflowing and cancels
54-
# out of the ratio, so it carries no gradient (ddx_stop_gradient).
62+
# Attention in einfold's window spelling. The causal mask is a join
63+
# predicate: a masked (i, j) pair is a row that does not exist. Subtracting
64+
# each row's max only keeps exp() from overflowing: it cancels out of the
65+
# ratio w / z, so it carries no gradient, which ddx_stop_gradient says.
66+
# TODO(xqlsystems/ddx#142): remove ddx_stop_gradient from the window MAX
67+
# once ddx can differentiate a window aggregate; it refuses one today.
5568
ATTENTION_WINDOW = """
56-
scores AS (
69+
WITH scores AS (
5770
SELECT q.t AS i, k.t AS j, SUM(q.x * k.x) / 8.0 AS s
5871
FROM q JOIN k ON q.d = k.d
5972
WHERE q.t >= k.t
@@ -69,12 +82,45 @@
6982
JOIN v ON w.j = v.t
7083
JOIN norm n ON w.i = n.i
7184
GROUP BY w.i, v.d)
85+
SELECT t, d, x FROM attention ORDER BY t, d
7286
"""
7387

74-
# The same attention as ddx spells it: the row max as a GROUP BY, joined
75-
# back to the scores.
88+
# The gradient of half the output's squared norm, with respect to every
89+
# value of Q, K and V: the same query, plus a loss and a different SELECT.
90+
ATTENTION_WINDOW_GRADIENT = """
91+
WITH scores AS (
92+
SELECT q.t AS i, k.t AS j, SUM(q.x * k.x) / 8.0 AS s
93+
FROM q JOIN k ON q.d = k.d
94+
WHERE q.t >= k.t
95+
GROUP BY q.t, k.t),
96+
weights AS (
97+
SELECT i, j, exp(s - ddx_stop_gradient(MAX(s) OVER (PARTITION BY i))) AS w
98+
FROM scores),
99+
norm AS (
100+
SELECT i, SUM(w) AS z FROM weights GROUP BY i),
101+
attention AS (
102+
SELECT w.i AS t, v.d, SUM(w.w / n.z * v.x) AS x
103+
FROM weights w
104+
JOIN v ON w.j = v.t
105+
JOIN norm n ON w.i = n.i
106+
GROUP BY w.i, v.d),
107+
loss AS (
108+
SELECT SUM(x * x) / 2 AS l FROM attention)
109+
SELECT q.t, q.d,
110+
grad(loss, q.x) AS dq,
111+
grad(loss, k.x) AS dk,
112+
grad(loss, v.x) AS dv
113+
FROM q
114+
JOIN k ON q.t = k.t AND q.d = k.d
115+
JOIN v ON q.t = v.t AND q.d = v.d
116+
ORDER BY q.t, q.d
117+
"""
118+
119+
# The same attention as ddx spells it: each row's max as a GROUP BY,
120+
# joined back to the scores. Here ddx_stop_gradient isn't needed, but it
121+
# is exact, and it spares ddx differentiating the max.
76122
ATTENTION_GROUP_BY = """
77-
scores AS (
123+
WITH scores AS (
78124
SELECT q.t AS i, k.t AS j, SUM(q.x * k.x) / 8.0 AS s
79125
FROM q JOIN k ON q.d = k.d
80126
WHERE q.t >= k.t
@@ -92,18 +138,51 @@
92138
JOIN v ON w.j = v.t
93139
JOIN norm n ON w.i = n.i
94140
GROUP BY w.i, v.d)
141+
SELECT t, d, x FROM attention ORDER BY t, d
95142
"""
96143

97-
SPELLINGS = {"window": ATTENTION_WINDOW, "group by": ATTENTION_GROUP_BY}
144+
ATTENTION_GROUP_BY_GRADIENT = """
145+
WITH scores AS (
146+
SELECT q.t AS i, k.t AS j, SUM(q.x * k.x) / 8.0 AS s
147+
FROM q JOIN k ON q.d = k.d
148+
WHERE q.t >= k.t
149+
GROUP BY q.t, k.t),
150+
row_max AS (
151+
SELECT i, ddx_stop_gradient(MAX(s)) AS m FROM scores GROUP BY i),
152+
weights AS (
153+
SELECT s.i, s.j, exp(s.s - r.m) AS w
154+
FROM scores s JOIN row_max r ON s.i = r.i),
155+
norm AS (
156+
SELECT i, SUM(w) AS z FROM weights GROUP BY i),
157+
attention AS (
158+
SELECT w.i AS t, v.d, SUM(w.w / n.z * v.x) AS x
159+
FROM weights w
160+
JOIN v ON w.j = v.t
161+
JOIN norm n ON w.i = n.i
162+
GROUP BY w.i, v.d),
163+
loss AS (
164+
SELECT SUM(x * x) / 2 AS l FROM attention)
165+
SELECT q.t, q.d,
166+
grad(loss, q.x) AS dq,
167+
grad(loss, k.x) AS dk,
168+
grad(loss, v.x) AS dv
169+
FROM q
170+
JOIN k ON q.t = k.t AND q.d = k.d
171+
JOIN v ON q.t = v.t AND q.d = v.d
172+
ORDER BY q.t, q.d
173+
"""
98174

99-
# A scalar of the output to differentiate: half its squared norm.
100-
LOSS = "loss AS (SELECT SUM(x * x) / 2 AS l FROM attention)"
175+
# Each spelling's forward query and gradient query.
176+
SPELLINGS = {
177+
"window": (ATTENTION_WINDOW, ATTENTION_WINDOW_GRADIENT),
178+
"group by": (ATTENTION_GROUP_BY, ATTENTION_GROUP_BY_GRADIENT),
179+
}
101180

102181
# Nadaraya–Watson: at each target point, the average of the sources' y
103182
# weighted by a Gaussian kernel of their distance (bandwidth h = 0.5).
104183
# Structurally attention: a weighted average with weights exp(score).
105184
NADARAYA_WATSON = """
106-
kernel AS (
185+
WITH kernel AS (
107186
SELECT t.p, s.q, exp(-(power(t.x - s.x, 2) + power(t.y - s.y, 2)) / 0.25) AS w
108187
FROM target t CROSS JOIN source s)
109188
SELECT k.p, SUM(k.w * s.v) / SUM(k.w) AS v
@@ -155,8 +234,7 @@ def main():
155234
for name, data in zip("qkv", (q, k, v)):
156235
host.load(name, table(data))
157236

158-
for spelling, ctes in SPELLINGS.items():
159-
forward = f"WITH {ctes} SELECT * FROM attention ORDER BY t, d"
237+
for spelling, (forward, gradient) in SPELLINGS.items():
160238
rows = report.time(
161239
f"forward ({spelling})", host, n, host.query, forward
162240
)
@@ -167,16 +245,10 @@ def main():
167245
if not host.differentiates:
168246
report.skip(step, host, n, "no ddx backend")
169247
continue
170-
# One statement per input, sharing one backward pass.
171-
gradients = [
172-
f"WITH {ctes}, {LOSS} "
173-
f"SELECT t, d, grad(loss, x) AS x FROM {name} ORDER BY t, d"
174-
for name in "qkv"
175-
]
176-
grads = report.time(step, host, n, host.query_all, gradients)
248+
rows = report.time(step, host, n, host.query, gradient)
177249
errors = [
178-
assert_close(f"d/d{name}", matrix(got), ref)
179-
for name, got, ref in zip("qkv", grads, want_grads)
250+
assert_close(f"d/d{name}", matrix(rows, f"d{name}"), ref)
251+
for name, ref in zip("qkv", want_grads)
180252
]
181253
report.check(max(errors))
182254

@@ -198,10 +270,8 @@ def check_masks_are_absent_rows(host_names):
198270
for host in hosts(host_names):
199271
for name, data in zip("qkv", (q, k, v)):
200272
host.load(name, table(data))
201-
for spelling, ctes in SPELLINGS.items():
202-
out = matrix(
203-
host.query(f"WITH {ctes} SELECT * FROM attention ORDER BY t, d")
204-
)
273+
for spelling, (forward, _) in SPELLINGS.items():
274+
out = matrix(host.query(forward))
205275
assert np.isfinite(out[:j]).all(), (host.name, spelling)
206276
assert np.isposinf(out[j:, 0]).all(), (host.name, spelling)
207277
assert np.isfinite(out[:, 1:]).all(), (host.name, spelling)
@@ -233,7 +303,7 @@ def check_nadaraya_watson(host_names, report):
233303
host,
234304
len(targets),
235305
host.query,
236-
f"WITH {NADARAYA_WATSON}",
306+
NADARAYA_WATSON,
237307
)
238308
got = xql.to_dataset(rows, dims=["p"])["v"].values
239309
report.check(assert_close("nadaraya-watson", got, want))

0 commit comments

Comments
 (0)