How Readyset Rewrites Your SQL: Subqueries in HAVING, ORDER BY, JOIN ON

This post extends Readyset's query rewrite pipeline — the machinery that turns arbitrary SQL into a form the dataflow engine can compile — to a family of query shapes it used to reject outright. It follows an earlier post, How Readyset Rewrites Your SQL, that walked through the pipeline in depth, but it stands on its own; here is the one-paragraph recap you need.

Readyset caches a query by compiling it into a dataflow graph that maintains the query's result incrementally as the upstream data changes — a read becomes a lookup into a materialized result, not a re-execution. That graph is stricter than SQL in two ways that matter here: every join connects exactly two inputs on a column-equality predicate (a.id = b.id), and there is no per-outer-row execution, so a correlated subquery — which conceptually runs once per outer row — must be rewritten into an ordinary join before it can be compiled at all. That rewrite is decorrelation, and the pipeline already applies it to subqueries in WHERE and in the SELECT list, including the three-valued-logic bookkeeping that keeps IN / NOT IN correct when a subquery can produce NULL — but only in those two positions.

A subquery can appear in other places, though. It can sit in a HAVING clause, filtering aggregated groups. It can drive an ORDER BY. It can be a condition inside a JOIN ... ON. SQL allows all of these; Readyset's dataflow engine, until recently, allowed none of them. A query like this:

SELECT u.id
FROM users u
JOIN orders o ON o.user_id = u.id
             AND EXISTS (SELECT 1 FROM premium p WHERE p.user_id = u.id)

was hard-rejected before it ever reached decorrelation. Readyset returned an error and the query fell back to the upstream database — no cache, no incremental maintenance. And these shapes are not exotic: BI tools and hand-written reporting SQL routinely put existence conditions in a HAVING or a join, and put "order by a computed count" in an ORDER BY.

This post is about closing that gap — extending the pipeline to decorrelate subqueries in four new positions: HAVING, ORDER BY, INNER JOIN ON, and LEFT OUTER JOIN ON. All four rest on one idea. For three of them it's near-mechanical; the fourth — LEFT OUTER JOIN ON — takes real care, because the obvious version of the move silently returns wrong answers, in a way that is a nice illustration of what the dataflow model does and doesn't allow.

One idea: move the subquery to a position decorrelation already handles

The decorrelation machinery is powerful, but it only fires on subqueries in WHERE and in SELECT lists. So rather than teach it four new positions, the pipeline does the opposite: it rewrites each new position into one of the two it already handles, then lets the existing decorrelation run unchanged.

The trick, in every case, is to do that move without changing what the query means — including for the subtle rows (empty groups, ties, NULL-extended left-join rows) where a careless move would quietly return the wrong answer. That soundness argument is the real content; the mechanical rewrite is small.

A single pre-decorrelation position-normalization pass handles all four, reshaping each into a WHERE clause or a SELECT-list projection before decorrelation runs. Let's take them in order of difficulty.

HAVING: lift the whole SELECT into a wrapper

HAVING filters after grouping — it's a WHERE that runs on aggregated rows. So a subquery predicate in HAVING is conceptually a filter applied to the grouped result. The pipeline makes that literal: it wraps the aggregating query in an outer SELECT, and moves the HAVING-subquery predicate up into the wrapper's WHERE.

-- Before: correlated subquery in HAVING
SELECT region, SUM(amount) AS total
FROM orders
GROUP BY region
HAVING SUM(amount) > (SELECT AVG(budget) FROM targets t WHERE t.region = orders.region)

-- After: wrap the aggregation; the HAVING-subquery predicate becomes a WHERE on the wrapper
SELECT agg.region, agg.total
FROM (
    SELECT region, SUM(amount) AS total
    FROM orders
    GROUP BY region
) AS agg
WHERE agg.total > (SELECT AVG(budget) FROM targets t WHERE t.region = agg.region)

The grouping and aggregation stay in the inner query; the subquery predicate now lives in the wrapper's WHERE, correlated to the projected agg.region, exactly where decorrelation knows how to turn it into a join. Ordinary HAVING predicates that don't contain a subquery stay put on the inner query — only the subquery-bearing conjunct is lifted.

ORDER BY: project the subquery into the SELECT list

An ORDER BY that sorts by a subquery is really asking for a computed value per row, then a sort on that value. So the pipeline projects the subquery into the inner SELECT list under a synthetic alias, and points the wrapper's ORDER BY at that alias:

-- Before: ORDER BY a correlated subquery, with a LIMIT
SELECT p.id, p.name
FROM products p
ORDER BY (SELECT COUNT(*) FROM sales s WHERE s.product_id = p.id) DESC
LIMIT 10

-- After: the subquery becomes a projected column; the wrapper orders by it
SELECT sub.id, sub.name
FROM (
    SELECT p.id, p.name,
           (SELECT COUNT(*) FROM sales s WHERE s.product_id = p.id) AS sales_count
    FROM products p
) AS sub
ORDER BY sub.sales_count DESC
LIMIT 10

Now the subquery is a scalar in a SELECT list — decorrelated by Readyset's scalar-subquery machinery, which lowers a per-row correlated COUNT to a GNL LEFT JOIN with COALESCE so a product with zero sales sorts as 0, not NULL.

The one subtlety is the tail. HAVING, ORDER BY, LIMIT, and OFFSET form a causally-chained sequence: filter groups, then sort, then clamp to N rows. When the wrap fires, that whole tail has to migrate to the wrapper together. Leaving LIMIT on the inner query would clamp rows before the wrapper's sort and filter applied — a different result set. So LIMIT/OFFSET move up with the ORDER BY, keeping the post-grouping pipeline coherent.

INNER JOIN ON: just move it to WHERE

Now the join positions. Recall the core structural constraint: every join in the dataflow graph connects exactly two inputs via column-equality predicates. a.id = b.id is fine; a subquery is not something a join operator can evaluate. So a subquery in an ON clause has to move out, leaving a clean two-relation equality join behind.

For an inner join, that move is easy, because the ON and WHERE clauses are interchangeable for such a predicate. An inner join emits a row only when the join condition holds; a WHERE filter discards rows where its condition fails. Applying the subquery predicate as a post-join filter produces exactly the same rows.

-- Before: subquery in an INNER JOIN ON
SELECT u.id
FROM users u
JOIN orders o ON o.user_id = u.id
             AND EXISTS (SELECT 1 FROM premium p WHERE p.user_id = u.id)

-- After: equality stays in ON, the subquery moves to WHERE
SELECT u.id
FROM users u
JOIN orders o ON o.user_id = u.id
WHERE EXISTS (SELECT 1 FROM premium p WHERE p.user_id = u.id)

The ON is back to a clean equality join, and the EXISTS sits in WHERE, where decorrelation turns it into a semi-join. Correlated or uncorrelated, EXISTS / NOT EXISTS / IN / NOT IN / scalar — they all move uniformly, because the transformation is about position, not the subquery's shape. This is sound because the engine's plan-level predicate pushdown already commutes filters freely past inner joins; the rewrite just does explicitly, at the SQL level, what the compiler would have done anyway.

LEFT OUTER JOIN ON: the move-to-WHERE trap

The inner-join trick doesn't transfer. Moving a subquery predicate from a LEFT JOIN's ON to its WHERE filters out the very rows the join is meant to preserve — a NULL-extended left row can't satisfy the predicate, so WHERE drops it, silently collapsing the LEFT JOIN into an INNER JOIN. Predicate pushdown commutes filters past inner joins but not past a left join's null-extending edge, so the subquery has to leave the ON without moving to WHERE.

The computed-column wrap

The insight is to keep the subquery on the preserved side of the null-extension, not the filtered side. Instead of moving the predicate out of the ON, the pipeline wraps the operand the subquery correlates to in a derived table that pre-computes the subquery's value as an ordinary column, and rewrites the ON to reference that column.

-- Before: correlated scalar subquery in a LEFT JOIN ON
SELECT s.id, o.id
FROM suppliers s
LEFT JOIN orders o ON o.supplier_id = s.id
                  AND s.rating = (SELECT MAX(score) FROM reviews r WHERE r.supplier_id = s.id)

-- After: wrap the preserved side; the ON references a projected column
SELECT sub.id, o.id
FROM (
    SELECT s.id, s.rating,
           (SELECT MAX(score) FROM reviews r WHERE r.supplier_id = s.id) AS top_score
    FROM suppliers s
) AS sub
LEFT JOIN orders o ON o.supplier_id = sub.id
                  AND sub.rating = sub.top_score

Two things happened. First, the ON is back to a two-relation equality-plus-comparison over {sub, orders} — no subquery. Second, the correlated subquery now lives in a SELECT list, which decorrelation already handles (lowering it to a GNL LEFT JOIN that maintains the per-supplier top score incrementally). We didn't invent a new decorrelation; we moved the subquery into a position an existing pass understands — the same move as HAVING and ORDER BY — while leaving the outer join two-relation.

Crucially, null-extension is preserved. The wrap is on the left (preserved) side, so every supplier row still flows into the left join whether or not it matches an order. A supplier whose computed top_score makes the ON false is NULL-extended, exactly as in the original — not filtered away.

Which operand gets wrapped depends on where the correlation points:

• Uncorrelated subquery: it's a query constant, so it can be pre-evaluated and wrapped onto the join partner.
• Correlated to the preserved (left) side: wrap the left side, as above.
• Correlated to the non-preserved (right) side: symmetric — wrap the right side instead.
• Correlated to both sides: there's no single operand to host the computation without spanning both relations, which would violate the two-relation join constraint. This case is declined — the query safely falls back to upstream — though we'll come back to a way to rescue an important slice of it.

One edge is worth calling out, because it takes the idea to its logical end: when the subquery comparison is the only thing in the ON, with no ordinary equality to key the join on at all — say, attaching the current (highest-version) config to every event.

-- Before: the ON is only a scalar-subquery equality — there is no join key
SELECT e.id, c.value
FROM events e
LEFT JOIN config c ON c.version = (SELECT MAX(version) FROM config)

-- After: the subquery is materialized as a column on the opposite side,
-- and the comparison becomes a real join key
SELECT sub.id, c.value
FROM (SELECT e.id, (SELECT MAX(version) FROM config) AS cur_version FROM events e) AS sub
LEFT JOIN config c ON c.version = sub.cur_version

The wrap manufactures the key: c.version = sub.cur_version is a column-equality the dataflow join can compile where a moment ago there was none. The only new twist is choosing which operand to project onto, so a null-extended row can't blank out the synthesized key — the same null-extension discipline as everywhere else.

RIGHT OUTER JOIN is canonicalized to LEFT earlier in the pipeline, so it comes along for free. FULL OUTER JOIN — where both sides are preserved — stays out of scope.

IN and NOT IN: keep the whole subquery

IN and NOT IN in a LEFT JOIN ON need one extra bit of care, because a membership subquery can carry an ORDER BY ... LIMIT, a GROUP BY, or an aggregate that changes which rows are in the set. x IN (SELECT id FROM t ORDER BY score DESC LIMIT 3) means "one of the three highest-scoring ids" — the ordering and the limit define the set, they don't decorate it. So the rewrite has to move the membership test to a supported position while keeping it whole.

It does exactly that, with the same computed-column wrap: it projects the IN node verbatim as a boolean flag onto the wrapped side, and references the flag in the ON.

-- Before: IN-subquery in a LEFT JOIN ON, with a LIMIT that matters
SELECT s.id, o.id
FROM suppliers s
LEFT JOIN orders o ON o.supplier_id = s.id
                  AND s.id IN (SELECT supplier_id FROM shipments ORDER BY qty DESC LIMIT 3)

-- After: the IN is preserved intact inside a CASE, projected onto the wrapped side
SELECT sub.id, o.id
FROM (
    SELECT s.id,
           CASE WHEN s.id IN (SELECT supplier_id FROM shipments ORDER BY qty DESC LIMIT 3)
                THEN 1 ELSE 0 END AS in_flag
    FROM suppliers s
) AS sub
LEFT JOIN orders o ON o.supplier_id = sub.id AND sub.in_flag = 1

The ORDER BY ... LIMIT rides along untouched, so the membership set is exactly what SQL says it is. And because the IN node is preserved, it flows into the pipeline's existing three-valued-logic machinery — the null-present / existence probe joins — which reproduce IN / NOT IN semantics exactly, including the awkward case where the subquery set contains a NULL.

That last point is what makes NOT IN fall out for free. x NOT IN S is only TRUE when x is definitely absent from S; if S contains a NULL and x isn't otherwise found, the answer is unknown, and in a join, unknown is not a match. Keeping the NOT IN node verbatim — with the negation inside the membership test rather than flipped into the CASE — lets the existing probes distinguish "definitely absent" from "unknown," so no special-case NULL handling was needed in the new code at all. The general 3VL infrastructure that already existed for WHERE and SELECT positions simply applies. Reusing it, rather than reinventing a bespoke NOT IN rewrite, is what kept this change small.

A bonus: promoting spuriously-outer joins

The both-side-correlated left-join case we declined above isn't always a genuine left join. Consider:

SELECT p.id, z.qty
FROM parts p
LEFT JOIN shipments z ON p.id = z.part_id
                     AND EXISTS (SELECT 1 FROM jobs j WHERE j.part_id = p.id AND j.id = z.job_id)
WHERE z.qty > 100

The ON subquery correlates to both p and z — the case with no single operand to wrap. But look at the WHERE: z.qty > 100. A NULL-extended z row has z.qty = NULL, which can never satisfy z.qty > 100, so those rows are filtered out anyway. This left join is only spuriously outer — it's equivalent to an INNER JOIN. Once we recognize that, we can promote it to INNER before decorrelation, and then the simple move-to-WHERE mechanism applies and the both-side correlation decorrelates cleanly.

The promotion fires only when a downstream predicate genuinely null-rejects the right side. A NULL-preserving predicate — z.qty > 100 OR z.qty IS NULL, or a NOT IN (subquery) that can be true for a null value — must not trigger it, or we'd wrongly drop the very rows a left join exists to keep. That soundness boundary is the whole game, and it's guarded by the same nullability analysis the pipeline already uses elsewhere.

The result

Queries that previously failed at validation now cache and maintain incrementally, across all four new positions:

• Subqueries in HAVING and ORDER BY, with the post-grouping LIMIT/OFFSET tail migrated coherently
• EXISTS / NOT EXISTS in INNER JOIN ON and LEFT OUTER JOIN ON
• IN / NOT IN in the join positions, with ORDER BY / LIMIT / GROUP BY / aggregates preserved and full three-valued logic
• Scalar-comparison subqueries in join conditions
• Correlated (to either side) and uncorrelated variants
• RIGHT JOIN forms, via canonicalization to LEFT

Everything that can't yet be expressed as a two-relation equality join — both-side correlation that isn't rescued by promotion, FULL OUTER JOIN conditions — is declined, not mis-compiled: the query falls back to the upstream database and returns correct results, just without a cache.

This is the natural continuation of that pipeline: the general decorrelation machinery was already there; the work was recognizing specific positions it didn't yet reach, moving the subquery into a form that machinery already understands, and proving at each step that the rewrite preserves the query's meaning — including for the empty groups, the ties under a LIMIT, and the rows a left join is careful to keep. Each new position is another pass composed into the pipeline, tested against the full regression suite, and held to the same standard: the cached result must equal what the database would have returned, for every possible state of the data