Skip to content

Latest commit

 

History

History
309 lines (251 loc) · 26.5 KB

physical-compile-coverage.md

File metadata and controls

309 lines (251 loc) · 26.5 KB

Physical compile coverage for deployment computation

Audience: developers moving computation from ASAPQuery-backend into asap_executor::physical_planner.

Contract

Logical selection decides what to compute. A PhysicalPropertiesAssignment sets node timing (Stage 2 materialization chooses it per physical candidate). physical_planner::compile turns a timed PhysicalASAPDAG into physical operator DAGs. The backend owns ingestion, tumbling windows, storage, stored-state evaluation, external exact engines, pricing/selection, and execution scheduling.

A backend lowering is covered when compile accepts the corresponding PhysicalASAPDAG node and produces operators with the same result. The backend should then pass the timed DAG and its input slot nodes to compile. It should not rebuild operator choices from PromQL text or construct operators itself.

Inventory

Surveyed backend: ASAPQuery-backend branch perf/788-startup-search. Planner base: split/462-f-physical-planner (#475).

Fallback below names the legacy wrapper node of that base. #543 removed it: those shapes are ordinary operator nodes now, and the Planner has no execution fallback.

Status values:

  • Supported: compile or compile_node already covers this computation.
  • Partial: some shapes are covered. The Notes column lists the gap.
  • Missing: compile rejects this computation.
  • Backend: not computation, or owned by the backend.
# Backend site Computation Planner node Status at #475 Notes
1 query_time.rs Lower::lower, compile_logical PromQL AST → QueryTimeOperator DAG for a native query Fallback { QueryExpr } sub-DAGs plus value payloads Missing compile lowers Fallback only as a raw Scan source.
2 QueryTimeOperator::Aggregate (sum/min/max/avg/count) Grouped value aggregation Value::Exact(Aggregate); SummaryAgg{ExactAggregate, Reduce} over finalized values Supported Also promql_values::compile_aggregate.
3 QueryTimeOperator::Sort, Limit (topk, sort, sort_desc) Ordering and per-group limits Value::Sort, Value::Limit Supported
4 QueryTimeOperator::Binary, QueryPlanNode::Binary (vector ⊗ scalar) Arithmetic with a scalar operand Binary whose operand is Fallback{PromqlScalarBridge(Literal)} Missing Query-time Binary accepts only label-map vector schemas. The literal node has no native binding.
5 QueryTimeOperator::Binary (vector ⊗ vector) One-to-one label matching and arithmetic Binary over grouped value rows Missing Only the ingestion-time aligned_binary and label-map vector_binary exist.
6 binary_operator CheckedDiv / FiniteDiv Guarded division BinaryOperator checked flags Partial Flags are evaluated, but only where rows 4/5 are covered.
7 QueryTimeOperator::Binary comparisons, bool Filter or 0/1 comparison Binary{Compare} Missing Payload::Binary does not carry return_bool.
8 QueryTimeOperator::UnaryNegate Negation Binary{Mul} by literal -1 Missing The frontend emits * -1; same gap as row 4.
9 QueryTimeOperator::VectorToScalar scalar() Fallback{PromqlScalarFromVector} Missing Only promql_values::compile_vector_to_scalar.
10 QueryTimeOperator::HistogramQuantile Bucket interpolation Fallback / AggIntent::HistogramQuantile Missing Only promql_values::compile_histogram_quantile.
11 QueryTimeOperator::Temporal (rate, increase, *_over_time) Per-series window functions SummaryAgg{PerEntity} over TimeRange(Scan) Partial Supported with closed series identity. Not supported over Fallback matrices (compile_temporal only).
12 logical_dag.rs Subquery, subquery_grid, expanded_inputs Re-evaluate the child on a step grid and assemble a matrix Fallback{PromqlSubquery} Missing No Planner operator.
13 QueryPlanNode::Scalar, DAGCompiler::lower scalar literal Scalar constant Fallback{PromqlScalarBridge(Literal)} Missing Only promql_values::compile_scalar.
14 DAGCompiler::lower ReduceSum; physical_values.rs PerEntity projection Sum over finalized values; per-entity identity SummaryAgg{ExactAggregate(Sum)} Supported The backend builds an identity Operator::project itself for PerEntity.
15 DAGCompiler::lower ExactReadout; post_asap_readout.rs ExactReadout Finalize exact state (sum/count/min/max/rate/increase) Value::FinalizeExactAccumulator Partial Count yields Int64 against a declared Float64 PromQL value. compile rejects it.
16 post_asap_readout.rs SummaryEstimate (readout_bound, expand_item_rows) Sketch estimate per group; TopK item expansion SummaryEstimate Partial The backend's label-map state layout and MetricsQL __name__ rules have no Planner equivalent. compile_exact_evaluation has no sketch counterpart.
17 post_asap_readout.rs SummaryMerge (merge_bound_states) Merge states by group SummaryMerge Supported Union plus summary_merge.
18 post_asap_readout.rs counter range parameters Counter lookback for rate/increase TimeRange ancestor of finalization Supported Applied through with_counter_lookback.
19 post_asap_readout.rs execute_value_fragment Per-timestamp binding of a value fragment n/a Backend Evaluation scheduling.
20 DAGCompiler::lower SummaryJoin / Subtract / Delete Summary algebra SummaryJoin, SummarySubtract, SummaryDelete Missing The backend also rejects these (ExactFallback).
21 current_series.rs Snapshot + TopK Current-series ranking EvaluatePopulation{TopK} Supported
22 current_series.rs Sum / Count / Average Current-series aggregates EvaluatePopulation{Sum,Count,Average} Missing compile accepts only TopK.
23 current_series.rs Quantile Current-series quantile EvaluatePopulation{Quantile} Missing No exact quantile reduction.
24 raw_dag.rs weight Column Summary update from a sample/projected value SummaryAgg Supported
25 raw_dag.rs weight Constant Unit/constant-weight update SummaryAgg Missing compile_node requires a column weight.
26 raw_dag.rs item Column / Tuple Keyed update item SummaryAgg{item} Supported keyed_summary_build.
27 raw_dag.rs item EntityIdentity Series-identity item SummaryAgg{item} Missing Needs the series-identity column.
28 physical_values.rs compile, combine Translate QueryTimeOperator to promql_values::*; compose fragments n/a Supported Exists only because of row 1. The Planner no longer composes fragments: CompiledPhysicalDAG::compose was removed, and a plan reads its inputs only at Scans and materialized views.
29 query_plan.rs compile_native_fragment (Semi join, Exact aggregate, Sort, Limit, Filter) Relational value ops RelationalJoin, Value::* Supported Already calls compile.
30 query_time.rs selected_query_time_nodes, selected_native_expression, selected_aggregate_operator Recover operator identity from original PromQL text Payload variants (ExactKind::Min/Max, AggIntent) Supported Payloads already carry the identity. These witnesses are needed only while row 1 remains.
31 Scan, ExactSubquery, CandidateExactSubquery, CurrentSeries ingest, ReadMaterialization, ExternalExact Storage reads and external engines Input slots Backend

Totals at #475: 11 Supported, 4 Partial, 14 Missing, 2 Backend.

Covered after this change

Row Change
4, 8, 13 Query-time Binary folds a scalar-literal operand into a projection over grouped value rows.
5 Query-time Binary over grouped value rows performs an inner equi-join on equal label columns, then applies the operator. Per-series rows remain Partial.
15 Count finalization converts exactly to the declared Float64 value.
22, 23 EvaluatePopulation Sum/Count/Average/Quantile compile to grouped aggregation. Reduction::Quantile implements PromQL interpolation.

Totals after this change: 17 Supported, 4 Partial, 8 Missing, 2 Backend.

Covered by PromQL fallback compilation

compile lowers each PromQL operator node (selector, range function, subquery, binary operator) natively, realized with promql_rows::with_series_identity. The deployment supplies the raw rows of each selector as the input of its Scan node, by that node's ID and with its schema. Each selector has its own Scan, even when two selectors read the same metric. A node's own ID still names its output, so a deployment may instead supply that whole result, for example from an external exact engine. A node that reads no selector, such as vector(1), needs no input. The Planner has no execution fallback: a node compile cannot lower fails compilation.

Operator::series_window evaluates each series at the query time, or at each subquery step, over the left-open window (t - offset - range, t - offset]. Instant selection takes the latest sample and omits the series if that sample is a stale marker. Range functions ignore stale markers. The raw rows must cover every window the node evaluates; raw_series documents the subquery extent. A subquery has at most 100000 steps. Output rows keep the full series identity; the query adapter still applies PromQL's metric-name rules. A bare selector consumed by another node, such as a per-entity summary, remains raw range rows and is not compiled as instant selection.

Row Change
1 Supported shapes: selectors with offset; rate, increase, delta, and sum/avg/min/max/count_over_time; by aggregation; sort; topk/limit; scalar(); vector(literal); arithmetic with one literal. Now Partial.
9 scalar() compiles to VectorToScalar. (Since the relational section below, scalar(v) is a read of another operator, bound as a column; see there.)
11 Range functions over the raw selector rows.
12 f(sel[R:S]) and f(g(sel[r])[R:S]), with subquery offset, evaluate on the aligned step grid. The frontend now retains subquery offset/@ as a TimeShift; it previously dropped them. Now Partial.

Totals after this change: 19 Supported, 5 Partial, 5 Missing, 2 Backend.

Covered by multi-selector fallback compilation

Row Change
1 Vector-vector arithmetic with one-to-one matching, on, and ignoring. Each side is reduced to its matching labels, then matched on equal label sets. A duplicate match group is an error, as in Prometheus. The result drops __name__. irate, idelta, changes, resets, last_over_time, and exact quantile_over_time. @ <timestamp> on selectors. Still Partial.
11 The range functions above, over raw selector rows.
12 @ <timestamp> on subqueries anchors the step grid. An inner selector's @ pins every step. Still Partial.

@ fixes the instant a window ends at, before offset; the output keeps the query's evaluation time. The raw rows must cover the window at that instant. Vector matching rewrites the series identity, so its results already lack __name__. (This section once listed without aggregation too, but compile refused it with "grouping without requires resolved label columns"; it is covered in the reduce aggregates section below.) Other results keep it; the query adapter still drops it. (Range functions drop it too since the comparison change below.)

Totals are unchanged: 19 Supported, 5 Partial, 5 Missing, 2 Backend.

Covered by per-series arithmetic

Row Change
5 Query-time Binary over rows with a series identity, such as per-series evaluations of stored state, uses the Fallback's series_labels and series_binary. Examples: avg_over_time as stored sum/count, and rate(a) / rate(b). Matching drops __name__ and honors on/ignoring when the payload carries them. Only one-to-one arithmetic is covered; group_left/group_right stay rejected and comparisons are row 7. Now Supported.
4, 8 A literal operand also applies to per-series rows and drops __name__, in the Fallback too. Series whose label sets become equal are an error, as in Prometheus.

Grouped sum/avg, current-series Sum/Average evaluations, and sum_over_time/avg_over_time use Prometheus' Kahan-Neumaier summation. An average switches to an incremental mean once the running sum would overflow. The grouped path also serves SQL SUM/AVG over Float64, which are now compensated the same way. Stored exact Sum now retains a Kahan-Neumaier compensation term through updates, tumbling-window merges, and persistence. A truly overflowing sum remains infinite; the checked avg_over_time division still rejects that case.

Totals after this change: 20 Supported, 4 Partial, 5 Missing, 2 Backend.

Covered by comparisons and set operators

The IR now distinguishes bool comparisons: BinaryOpKind::CompareBool(op) beside the filtering BinaryOpKind::Compare(op). The PromQL frontend emits it for bool; it previously dropped the modifier.

Operator::series_binary evaluates every PromQL binary operator, in the Fallback and in query-time Binary nodes, following Prometheus' VectorBinop, VectorAnd, VectorOr, and VectorUnless:

  • Arithmetic drops __name__. A comparison filter keeps the matched left series with its value and name; with a scalar on the left it keeps the vector's value. bool yields 1 or 0 and drops the name. NaN compares unequal to everything.
  • Operands may be vectors, literals, scalar(), or scalar-valued binary expressions such as -scalar(x). Two scalars yield a scalar. The label-map vector_binary also treats CompareBool as its bool mode.
  • One-to-one matching and group_left/group_right with included labels. The "one" side must not repeat a match group; many-to-one results must be unique. A left duplicate is an error only if more than one match is kept.
  • and, or, and unless match label sets many-to-many, with on or ignoring, and return the original series.
  • Range functions other than last_over_time and first_over_time now drop __name__ in the Fallback. Series whose label sets become equal are an error, as in Prometheus. Vector-scalar results are checked the same way. Inside a subquery the inner function also drops the name and checks identities separately at each evaluation timestamp.

Binary result schemas now include labels contributed by or, group_right, and group_left, including a right-side series identity when needed. Thus sum by (job) (a) * on(job) group_left(team) info retains team, and sum by(job)(a) or info retains every right-side label.

Row Change
1 Comparisons, bool, set operators, group_left/group_right, scalar() operands, and literals over aggregates whose value has another name, such as sum by (job) (a) * 2. Still Partial.
5 Grouped Binary rows use the same operator instead of a relational join. A duplicate match group is now an error instead of a cross product.
7 Fallback, grouped Binary, and per-series comparisons and sets. Temporal stored evaluations drop __name__ before matching, including exact Count conversion, and reject duplicate output identities.

Totals after this change: 20 Supported, 5 Partial, 4 Missing, 2 Backend.

Covered by classic histogram_quantile

Row Change
10 A classic-bucket histogram_quantile(q, v) lowers to Aggregate{Reduce(without([le])), [HistogramQuantile{q, le}]}, where le is the argument's le column. The frontend seeds le into the selector's schema. compile binds that Aggregate (and only that grouping) to one operator, Operator::series_histogram_quantile, that groups rows by every label except le and applies Prometheus bucketQuantile: buckets sorted by bound, equal bounds summed, counts made monotonic, NaN without a +Inf bucket or with no observations, and the largest finite bound for a rank past every finite bucket. The output labels are the input labels without le and __name__; result label sets that become equal are an error, as in Prometheus. Covers histogram_quantile(q, rate(x_bucket[5m])), histogram_quantile(q, sum by (le, job) (…)), and bare bucket selectors. Now Supported.

An argument whose output provably lacks le, such as sum by (job) (rate(x_bucket[5m])), is rejected at lowering. Prometheus returns an empty vector for it. Candidate search keeps the classic form as one retained exact ordinary sub-DAG for every accuracy target; it has no sketch candidate. histogram_quantiles lowers each branch the same way, and compile binds its Concat of relabeled branches (see the relational section below): histogram_quantiles(x_bucket, "q", 0.5, 0.9) answers one series per φ, {q="0.5"} and {q="0.9"}. Nested aggregation, such as sum(histogram_quantile(…)), does not compile: the outer aggregate looks for a value column named value, while the quantile's is named histogram_quantile. It is tracked in issue #911.

Totals after this change: 21 Supported, 5 Partial, 3 Missing, 2 Backend.

Covered by exact reduce aggregates

Row Change
1 PromQL stddev, stdvar, group and count_values, with by or without. stddev/stdvar use Welford's update, as Prometheus does: stddev by (job) (m) over job a's 1, 2 and 4 is the square root of 14/9. group is 1 per group. count_values("v", m) writes each value as Go's FormatFloat(v, 'f', -1, 64) does (0.30000000000000004, 1000000000000000000000, NaN, +Inf), and its label replaces a grouping or kept label of that name, as in Prometheus. A label the without list also names is removed again, so count_values("zone", m) without (instance, zone) counts per kept group with no zone label. Still Partial.
2 without grouping over the series identity: sum without (instance) (m) groups by every label but instance and __name__, so {job=a, instance=1, zone=z} answers as {job=a, zone=z}. The IR marks that kept identity as computed, not copied. count without (instance) (m) answers its count as Int64, as count by does: the label rewrite that drops __name__ carries any numeric sample, while an operator that computes on the sample (a binary operator between vectors, histogram_quantile, label_replace) requires Float64. A ranking (topk, Sort, Limit) partitioned without over the identity is refused, since it keeps each row's labels.
3 An exact topk, Aggregate{Reduce, [TopK]}, lowers to a Sort that keeps the first k rows per partition (value descending, NULLs and NaN last; fetch: Some(k), a bounded heap of k rows per partition) and a Project of the ranked rows. The current-series top-k (row 21) lowers to the same sort. topk(2, sum by (job) (rate(c[5m]))) answers the two largest job sums with their jobs; topk by (job) (1, m) keeps each series' full labels, __name__ included.
29 SQL STDDEV, STDDEV_SAMP, STDDEV_POP, VAR_SAMP, VAR_POP and corr over Float64 or Int64 columns: NULL for fewer than two values (sample forms) or none (population forms), corr NULL for a constant input.

Totals are unchanged: 21 Supported, 5 Partial, 3 Missing, 2 Backend.

Covered by per-series time functions

Row Change
1 An exact per-series range function over raw samples lowers to a per-entity Aggregate over the window's TimeRange, which compile binds natively. A row reduction (sum/avg/min/max/count/quantile/stddev/stdvar_over_time, distinct, l2 and entropy) runs on the aggregate operator; a function of each series' time-ordered samples (rate, increase, irate, delta, idelta, deriv, predict_linear, changes, resets, last/first_over_time, mad_over_time, ts_of_min/max/first/last_over_time, double_exponential_smoothing, present_over_time) runs on the range function kernel, whose window ends a fixed offset before the evaluation time. timestamp(v) over an instant selector runs the same way. rate and increase extrapolate as Prometheus 3.x extrapolatedRate, in this kernel and in the exact counter state alike. The result drops __name__, except last_over_time and first_over_time, which keep it as Prometheus does. Still Partial.

The range function kernel reads the window of a TimeRange whose TimeShifts carry no @ anchor: rate(x[5m] @ 300) does not compile yet, since its window is not a fixed offset back from the evaluation time. Any other per-entity aggregate, such as absent_over_time(x[5m]), fails to compile.

Totals are unchanged: 21 Supported, 5 Partial, 3 Missing, 2 Backend.

Covered by relational operators, window functions, series operators and scalar reads

Shapes the SQL and PromQL frontends emit for ordinary queries. A node one native operator implements lowers in bind_operation, so compile_node compiles it too; a node that lowers to several operators (helpers, then its own) lowers only in compile.

Shape IR node Lowering
SQL SELECT DISTINCT Dedup One Limit of 1 row per distinct value (compile_node too).
SQL INTERSECT / EXCEPT [ALL] SetOp Intersect / Except One set_operation (compile_node too). The SQL frontend lowers these to semi / anti joins today, so only an IR built directly reaches it.
SQL UNION ALL, GROUP BY ROLLUP / GROUPING SETS levels SetOp Union all, Concat A union of the branches, each projected to the output schema when its names or nullability differ. UNION lowers to a Dedup over a UNION ALL; a SetOp Union without ALL adds a distinct Limit.
SQL window functions (row_number, rank, dense_rank, lag / lead, first_value / last_value / nth_value, sum / avg / count / min / max) with ROWS / RANGE frames SQLWindowFunc Expression arguments and order keys projected first, then sql_window. Aggregates slide their frame (rows enter at the end and leave at the start): O(n) per partition for frames whose bounds only grow, MIN / MAX by a monotonic queue. They reduce a frame's rows as the Aggregate reduces a group's: MAX over {1, NaN} is 1, an Int64 sum fails only when its result leaves Int64. RANGE offsets read one numeric or timestamp order key; NULL and NaN keys sort before or after every number.
SQL ORDER BY an expression Sort with an expression key The keys projected after the input's columns, the sort, then a projection back.
SQL scalar subquery, IN / EXISTS (uncorrelated, kept as a scalar read, for example inside OR); PromQL scalar(v) ScalarRef edges of a Filter, Project or PromqlVectorFromScalar One bind_scalar_ref per distinct read, chained over the input, each appending the read's value as a column, then the node over the widened rows. IN follows SQL's three-valued logic; scalar(v) reads v's one sample (Float64, or count's Int64), NaN unless exactly one. m / scalar(count(m)), vector(scalar(n)).
SQL LIKE / ILIKE, CASE x WHEN, casts between Int64, Float64, Utf8 and Bool scalar expressions LIKE against a literal pattern runs Arrow's like kernels over the batch; casts follow DataFusion (a float truncates to an integer).
PromQL vector(s), time(), hour() PromqlVectorFromScalar, EvalTimestamp The evaluation time (one row), s projected over it, then the sample's timestamp.
PromQL label_replace, label_join PromqlRelabel One series_relabel (compile_node too). Two series that end with one label set at one time are an error, as in Prometheus.
PromQL limitk, limit_ratio PromqlSeriesSample One series_sample (compile_node too): limitk keeps each group's first k series in label-set order, per step; limit_ratio keeps the series Prometheus keeps (its label hash).

info(m) (PromqlInfoEnrich) still fails to compile: the IR does not carry the info metric as an input.

Remaining

In order of backend usage:

  1. Rows 1 and 12, the remaining PromQL shapes:
    • Other scalar functions as operands.
    • Subquery operands other than one per-series function; implicit subquery resolution, which is a deployment default.
    • Other functions, such as absent_over_time, range functions under an @ anchor, and math functions. absent(v) is covered: it lowers to an Aggregate by no key with an Absent measure carrying the labels of v's equality matchers, and compiles to the executor's Absent operator, which emits one sample of value 1 with those labels when its input has no row and nothing otherwise. After these shapes are covered, the backend can delete rows 28 and 30.
  2. Rows 25 and 27: constant weights and EntityIdentity items for precompute SummaryAgg.
  3. Row 16: a label-map sketch-state evaluation, the counterpart of compile_exact_evaluation, and MetricsQL __name__ retention rules.
  4. Row 20: summary join, subtract, and delete.

fill, fill_left, and fill_right matching modifiers are rejected by the frontend (#494); they are never silently ignored.

Additional scalar and persistence coverage

deriv and predict_linear use per-series linear regression. Prediction uses the evaluation instant even when an offset selects older samples. As in Prometheus, an @-pinned call is step-invariant: it is evaluated once, at the first instant of the query or of its subquery grid, and reused at every step. Inner subquery functions validate label-set uniqueness per step.

time() reads the run's evaluation timestamp in seconds and composes with scalar and vector operands, including vector(time()). Logical literals, floating intent parameters, and physical values encode NaN and infinities as explicit JSON strings instead of losing them as null; finite values remain numbers. Deployments continue to own document versioning.

label_replace compiles to a native label rewrite with anchored regular expressions, capture expansion, non-match preservation, empty-label removal, and duplicate-label-set rejection. Multi-quantile branches use the same label rewrite for their constant quantile labels. These operators perform computation only; the backend still supplies raw selectors and stored inputs.

@ start() and @ end() remain dynamic anchors in the compiled program, including selector offsets and subquery grids. The deployment supplies the outer query bounds with RunContext::with_query_range(start_ms, end_ms); for an instant query both bounds equal its evaluation time. Executing an @ start()/@ end() program without those bounds fails before reading inputs. A literal @ pin does not require bounds, but a range query must still supply them: without them each step runs as its own instant query, so a pinned call is re-evaluated per step. Query output timestamps still use the current evaluation instant.