Support nested query functions for PromQL and SQL (testing + implementation)

[zzylol]

Summary

The ASAPQuery query engine should support nested query functions — applying a function on top of a subquery — for both PromQL and SQL. This issue tracks the testing and implementation of general nested-query support.

What the architecture already supports (grounding)

Nesting is structural at L3: intent_algebra::QueryExpr is a recursive, box-owned tree, and every operator already accepts an arbitrary child. The pieces that consume it are recursive too, so most of the "nesting" plumbing is already in place:

• L3 IR (crates/core/src/intent_algebra/query_expr.rs) — Aggregate { child }, Sort { child }, Limit { child }, Subquery { child }, BinaryOp { lhs, rhs }, etc. all box an arbitrary subtree. Schema derivation (output_schema_in) recurses and already handles a cross-series aggregate freezing an open schema to closed, per-series (label-preserving) reductions under TimeRange, etc.
• L2→L3 converter (crates/core/src/intent_algebra/lower.rs) — convert recurses through every node, including an outer Aggregate over an arbitrary child, Sort/Limit over arbitrary children, PromQLSubquery, and BinaryOp.
• Binder (crates/core/src/intent_algebra/binder.rs) — walks the whole tree to seed the usage-derived schema, so nested group keys / matchers resolve positionally.
• SQL front end (crates/lower/src/sql/mod.rs) — lower_plan recurses through the DataFusion LogicalPlan, so a nested aggregate / filter / projection chain already lowers. (Gaps below.)

So the binary form Q1 <op> Q2 was never the real ceiling — BinaryOp already nests both sides arbitrarily (see crates/e2e/tests/nested.rs::q25_div_over_complex_subtrees).

The actual gap (PromQL)

The ceiling was in the PromQL L1→L2 front end (crates/lower/src/promql.rs). walk_aggregate lowered an aggregate's argument through a flat two-level template (Inner + Outer enums): an outer aggregator over exactly one inner selector or range-vector function. Any composite argument was rejected:

• max(sum by (job) (rate(m[5m]))) — outer aggregate over a nested aggregate
• topk(3, sum by (instance) (rate(m[5m]))) — topk over a nested aggregate (was pinned as topk_over_aggregate_arg_is_rejected__GAP)
• sum(rate(a[5m]) + rate(b[5m])) — aggregate over a binary op
• sum(histogram_quantile(0.9, sum by (le) (rate(h_bucket[5m])))) — aggregate over a function lowered on a separate path

Done in this issue (PromQL) — PR linked below

• walk_aggregate now tries the flat fast path first (keeping heavy-hitter topk(k, count_over_time(...)) recognition intact), then falls back to recursing through the same walk used at top level and wrapping the result in the outer aggregation (outer_kind + build_over_subtree). This lifts the two-level limit to arbitrary function nesting.
• Genuinely unsupported inner expressions (e.g. unary negation) still surface their error — nothing is silently mislowered.
• ColumnRef::SampleValue resolution (crates/core/src/intent_algebra/column_resolution.rs) now also resolves to the sole numeric non-timestamp column, so an outer ranking over a cross-series aggregate (topk(k, sum by (job) (…)), value column renamed sum) finds its sort key.
• Tests: gap test flipped to a passing conformance test; added nested-aggregate / aggregate-over-binary-op / outer-over-nested-aggregate conformance tests, an exact-tree e2e test (q27_max_over_sum_by_job_over_rate), and SampleValue resolution unit tests.

Remaining implementation plan (tasks)

PromQL

• Generalize walk_aggregate to recurse over composite arguments (this PR).
• Range-vector function over a sub-query — max_over_time(rate(m[5m])[1h:]). extract_matrix only accepts a (parenthesised) matrix selector; teach the InnerFunc path to accept a PromQLSubquery child so *_over_time/rate can wrap a sub-query. Pinned today as over_time_of_subquery_is_rejected__GAP (crates/lower/tests/promql_conformance.rs).
• topk(k, <bare instant selector>) by (labels) — e.g. topk(3, http_requests_total) by (job). The non-heavy-hitter path defaults a bare selector to an implicit cross-series Sum, which destroys the by labels before Sort.partition_by resolves them (and is semantically wrong — PromQL ranks the raw samples). Rank the selector's own value, keep labels, route by to Sort.partition_by. (Surfaced reviewing PR feat(core)!: collapse L3 grouping — remove Partition node, unify on GroupKeys (#12, #13) #18.)
• Unary negation / scalar-literal operands inside nesting — sum(-m), v > 10*1024*1024. Needs a negate/scalar node in the L2 PromQL path (separate from this issue; tracked by the __GAP tests in section G).

SQL

• Derived tables / inline views — SELECT … FROM (SELECT … ) t. lower_plan rejects LogicalPlan::SubqueryAlias over a non-TableScan input and bare LogicalPlan::Subquery (crates/lower/src/sql/mod.rs). Lower the inner plan recursively and re-qualify its output columns with the alias so t.col resolves. This is the SQL counterpart of PromQL function nesting.
• Scalar / IN / EXISTS subqueries in predicates — decide representation (correlated vs uncorrelated) or reject cleanly with a pinned gap test.
• Conformance + e2e tests mirroring the PromQL nested cases (outer aggregate over a derived-table aggregate; ranking over a subquery).

Cross-cutting

• Boundary decision per node (sketch vs exact) is an L4 concern, not L3: L3 carries intent only. No engine change needed for nesting itself; confirm L4 rules fire per node over nested trees once the L4 framework lands.
• Document the nesting contract (which composite arguments lower vs. are rejected) in docs/promql-lowering.md.

Open questions

• Full set of nested patterns query authors need (gather more concrete examples).
• For SQL, how far to go on correlated subqueries vs. rejecting them cleanly in v1.

[zzylol]

Progress update (verified against latest main)

Keeping this tracking issue open, but the checklist is stale — two items landed since it was written:

• topk(k, <bare instant selector>) by (labels) — done in PR fix(lower): topk over a bare selector preserves by-labels (#30) #31. topk by (job) (3, m) now ranks the raw samples label-preservingly and routes by to Sort.partition_by. (This also closed the related standalone issues PromQL: topk/bottomk over bare instant vector produces unexpected Aggregate(Sum) #21 / PromQL: topk with 'by' clause over bare instant vector fails with column resolution error #22.)
• SQL derived tables / inline views (SELECT … FROM (SELECT …) t) — done in PR feat(lower): nested SQL query functions via derived tables (#27) #29. Covered by derived_table_aggregate_over_aggregate_nests and derived_table_outer_avg_over_inner_percentile in crates/lower/tests/sql_lowering.rs.

Also note the topk(k, sum by (…)) nested-aggregate case (standalone issue #23) is now fixed via #28/#29.

Genuinely remaining (still pinned as __GAP):

• Range-vector function over a sub-query — max_over_time(rate(m[5m])[1h:]). Still rejected: over_time_of_subquery_is_rejected__GAP (crates/lower/tests/promql_conformance.rs:651).
• Unary negation / scalar-literal operands — sum(-m), v > 10*1024*1024. Still rejected: unary_negation_is_rejected__GAP (:486) and scalar_literal_operand_is_rejected__GAP (:534). These are now tracked by dedicated issues Unary negation rejected in PromQL lowering (no scalar/negate node) #36 (unary negation) and QueryExpr::BinaryOp has no scalar/literal operand — vector-op-scalar PromQL rejected #35 (BinaryOp scalar operand) — the single biggest real-world lowering blocker (~822/949 of the awesome-prometheus-alerts corpus).
• SQL scalar / IN / EXISTS subqueries in predicates — represent or reject cleanly.
• Document the nesting contract in docs/promql-lowering.md.

[zzylol]

Corpus-derived function-coverage backlog

Ran a rejection scan over the full PromQL corpora (2,821 queries: awesome_prometheus_alerts + promql_corpus_docs + promql_corpus_testdata) — 1,933 parsed-but-rejected. The dominant blocker is the scalar/literal operand (#35, ~1021 / 52.8%, already tracked). The rest is a function/operator coverage tail, now enumerated as dedicated issues (all labeled promql):

PromQL front-end (L2):

• PromQL: native-histogram accessor functions (histogram_*) unsupported #43 — native-histogram accessors histogram_* — 282 (14.6%)
• PromQL: counter-derivative range functions (changes/delta/deriv/resets/predict_linear/idelta) unsupported #44 — counter-derivative range fns (changes/delta/deriv/resets/predict_linear/idelta) — 108 (5.6%)
• PromQL: math/trig scalar-transform functions (abs/ceil/floor/clamp/ln/…) unsupported #45 — math/trig scalar transforms (abs/ceil/clamp/ln/…) — 81 (4.2%)
• PromQL: time/calendar functions (time/timestamp/day_of_week/…) unsupported #46 — time/calendar fns (time/timestamp/day_of_week/…) — 76 (3.9%)
• PromQL: presence functions (absent/absent_over_time/present_over_time) unsupported #47 — presence fns (absent/absent_over_time/present_over_time) — 65 (3.4%)
• PromQL: vector()/scalar()/info() type-conversion functions unsupported #48 — vector()/scalar()/info() — 44 (2.3%)
• PromQL: extended aggregation operators (limitk/limit_ratio/count_values/group) unsupported #49 — extended aggregate ops (limitk/limit_ratio/count_values/group) — 40 (2.1%)
• PromQL: label_replace/label_join unsupported #50 — label_replace/label_join — 28 (1.4%)
• PromQL: long-tail functions (extra *_over_time reducers, sort family, min_of/max_of) unsupported #51 — long-tail fns (extra *_over_time reducers, sort family, min_of/max_of) — ~51 (2.6%)

L2→L3 converter (L3):

• L3: sum by (__name__) fails column resolution (metric-name label not in usage-derived schema) #52 — sum by (__name__) column resolution — 4
• L3: nested aggregate drops outer group key (sum(sum by (k)(...)) by (j)) — decide WAI vs fix #53 — nested aggregate drops outer group key (overlaps this issue + Aggregate output-schema derivation is duplicated by hand between query_expr.rs and column_resolution.rs #41) — 1

Relationship to this issue: these enumerate the function/operator coverage surface. The nesting mechanics tracked here (#27) are the plumbing that lets a supported function wrap an arbitrary child; #43–#51 are about which leaf functions are supported in the first place. #53 is the one true overlap — a nested-aggregate schema-threading case surfaced here.

Checklist status on this issue:

• Generalize walk_aggregate over composite arguments (feat(lower): arbitrary PromQL function nesting in aggregates (#27) #28/feat(lower): nested SQL query functions via derived tables (#27) #29)
• topk(k, <bare selector>) by (labels) (fix(lower): topk over a bare selector preserves by-labels (#30) #31)
• SQL derived tables / inline views (feat(lower): nested SQL query functions via derived tables (#27) #29)
• Range-vector function over a sub-query — PR feat(lower): support *_over_time over a sub-query (#27) #42 (flips over_time_of_subquery_is_rejected__GAP → 3 passing conformance tests)
• Unary negation / scalar-literal operands — tracked by Unary negation rejected in PromQL lowering (no scalar/negate node) #36 / QueryExpr::BinaryOp has no scalar/literal operand — vector-op-scalar PromQL rejected #35
• SQL scalar / IN / EXISTS subqueries in predicates
• Document the nesting contract in docs/promql-lowering.md

[zzylol]

Checklist status after PR #101

• Generalize walk_aggregate over composite arguments (feat(lower): arbitrary PromQL function nesting in aggregates (#27) #28/feat(lower): nested SQL query functions via derived tables (#27) #29)
• topk(k, <bare selector>) by (labels) (fix(lower): topk over a bare selector preserves by-labels (#30) #31)
• SQL derived tables / inline views (feat(lower): nested SQL query functions via derived tables (#27) #29)
• Range-vector function over a sub-query (feat(lower): support *_over_time over a sub-query (#27) #42)
• SQL scalar / IN / EXISTS subqueries in predicates — decided + pinned in PR fix(l2): drop provably-absent outer group keys (#53); pin + document the #27 nesting contract #101: reject cleanly in v1, whole family (scalar, IN, correlated EXISTS, NOT EXISTS, NOT IN). Representing them needs an L2 expression-IR subquery node + a correlated-vs-uncorrelated choice; derived tables in FROM remain the supported SQL nesting shape.
• Document the nesting contract — PR fix(l2): drop provably-absent outer group keys (#53); pin + document the #27 nesting contract #101 adds "The nesting contract (issue Support nested query functions for PromQL and SQL (testing + implementation) #27)" to docs/promql-lowering.md: a lowers-vs-rejected table of composite argument shapes, each row citing the pinning test.
• Unary negation / scalar-literal operands — QueryExpr::BinaryOp has no scalar/literal operand — vector-op-scalar PromQL rejected #35 landed (QueryExpr::Scalar); unary negation stays tracked by dedicated issue Unary negation rejected in PromQL lowering (no scalar/negate node) #36.

PR #101 also fixes the one true overlap with this issue, #53 (outer group key provably absent from a nested aggregate's output → dropped per PromQL's absent-label grouping semantics).

Once #101 merges, everything tracked here is either done or owned by a dedicated issue (#36) — this tracking issue can be closed.

[zzylol]

Closing this tracking issue — everything scoped here is done or owned by a dedicated issue.

Landed (all merged to main):

• Generalized walk_aggregate over composite arguments (feat(lower): arbitrary PromQL function nesting in aggregates (#27) #28/feat(lower): nested SQL query functions via derived tables (#27) #29)
• topk(k, <bare selector>) by (labels) (fix(lower): topk over a bare selector preserves by-labels (#30) #31)
• SQL derived tables / inline views (feat(lower): nested SQL query functions via derived tables (#27) #29)
• Range-vector function over a sub-query (feat(lower): support *_over_time over a sub-query (#27) #42)
• SQL scalar / IN / EXISTS predicate subqueries — decided (reject cleanly in v1) + pinned (fix(l2): drop provably-absent outer group keys (#53); pin + document the #27 nesting contract #101)
• Nesting contract documented in docs/promql-lowering.md (fix(l2): drop provably-absent outer group keys (#53); pin + document the #27 nesting contract #101), incl. the nested-subquery docs example max_over_time(deriv(rate(m[5s])[30s:5s])[10m:])
• The one true overlap, L3: nested aggregate drops outer group key (sum(sum by (k)(...)) by (j)) — decide WAI vs fix #53 (outer group key provably absent from a nested aggregate's output), fixed (fix(l2): drop provably-absent outer group keys (#53); pin + document the #27 nesting contract #101)

Remaining tail, tracked elsewhere: unary negation / scalar-literal operands → #36 (its blocker #35 has landed).