query/promql/native_compile.rs
1// Copyright 2023 Greptime Team
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Compiles a PromQL AST into a [`NativeTree`].
16//!
17//! This is the front half of the native evaluation model: it reads the parsed statement and writes
18//! down what it means as bound nodes. The native planner uses this compiler to build a tree for
19//! standalone execution. Its accepted expressions are described by the recursive rule below:
20//!
21//! ```text
22//! <expression> one of, recursively:
23//! <selector> e.g. x, x offset -5m
24//! <range function>(<matrix>) e.g. rate(x[5m]), rate(x[5m:1m] @ 1234)
25//! quantile_over_time(<constant>, <matrix>) e.g. quantile_over_time(0.9, x[5m])
26//! predict_linear(<matrix>, <constant>) e.g. predict_linear(x[5m], 300)
27//! double_exponential_smoothing(<matrix>, <constant>, <constant>)
28//! e.g. double_exponential_smoothing(x[5m], .5, .1)
29//! <math function>(<expression>[, <constant>]*) e.g. abs(rate(x[5m])), clamp_min(x, 0)
30//! <round or clamp>(<expression>, <scalar>+) e.g. round(x, time() / 10), clamp(x, 0, time())
31//! <histogram function>(<expression>) e.g. histogram_count(x)
32//! <sort>(<expression>[, <string>]*) e.g. sort_desc(x), sort_by_label(x, "job")
33//! absent(<expression>) e.g. absent(x{job="a"})
34//! absent_over_time(<matrix>) e.g. absent_over_time(x{job="a"}[5m])
35//! <histogram>(<constant>+, <expression>) e.g. histogram_quantile(0.9, rate(x[5m]))
36//! <label function>(<expression>, <string>*) e.g. label_replace(x, "a", "$1", "b", "(.*)")
37//! <expression> <operator> <scalar> e.g. x * 100, x > bool time()
38//! <scalar> <operator> <expression> e.g. 1 / x, time() - timestamp(x)
39//! <scalar> <operator> <scalar> e.g. time() - 60, time() > bool 1
40//! time(), pi(), vector(<scalar>) e.g. vector(time()), pi() * x
41//! <date function>() e.g. hour(), which is `hour(vector(time()))`
42//! -<expression> e.g. -x
43//! <expression> <set operator> <expression> e.g. x and on(job) y, x unless y
44//! info(<expression>[, {<matchers>}]) e.g. info(rate(x[5m]), {version=~".+"})
45//! <aggregator> [(by|without)(<labels>)] (<expression>)
46//! e.g. avg by(job)(rate(x[5m]) * 100)
47//! <aggregator> (<expression>) [(by|without)(<labels>)]
48//! e.g. count (x) by(job)
49//! quantile(<constant>, <expression>) [(by|without)(<labels>)]
50//! e.g. quantile(0.9, x) by(job)
51//! <selector aggregator>(<constant>, <expression>) [(by|without)(<labels>)]
52//! e.g. topk(3, x) by(job), limit_ratio(0.5, x)
53//! count_values(<string>, <expression>) [(by|without)(<labels>)]
54//! e.g. count_values("v", x)
55//!
56//! <matrix> <selector>[<range>]<modifiers> a range selector: raw samples
57//! | <expression>[<range>:<step>]<modifiers>
58//! a subquery: <expression> evaluated on a grid;
59//! the step may be omitted as `[<range>:]`
60//! <scalar> <constant> | time() | <scalar> <operator> <scalar>
61//! <modifiers> nothing, `offset <duration>`, `@ <anchor>`, or
62//! both, in either order — e.g. `x[5m] @ 1234
63//! offset 1m`
64//! ```
65//!
66//! where `<set operator>` is `and`, `or` or `unless`, optionally with `on(...)` or `ignoring(...)`,
67//! `<aggregator>` is `sum`, `avg`, `count`, `min`, `max`, `group`, `stddev`, `stdvar` or
68//! `quantile`, `<selector aggregator>` is `topk`, `bottomk`, `limitk` or `limit_ratio`, the
69//! function names are [`range_signature`]'s and [`math_signature`]'s, and which side
70//! of the matrix a range function's constants go on is [`RangeSignature`]'s: before it for
71//! `quantile_over_time`, after it for `predict_linear` and `double_exponential_smoothing`. A math
72//! function's constants always follow its vector.
73//!
74//! Parentheses are transparent wherever they appear — `rate((x[5m]))` is `rate(x[5m])` — because
75//! they say how a statement was typed rather than what it asks for.
76//!
77//! A subquery's `<expression>` is any shape above, so a subquery nests inside a subquery on a grid
78//! of its own, as in `rate(rate(x[5m:1m])[10m:30s])`; a `<step>` left out means Prometheus's default
79//! evaluation interval, one minute. Its `offset` and its `@` anchor are its own, not the inner
80//! expression's, so `rate(x[5m:1m] @ end() offset 1m)` reads one fixed interval. A `<selector>`
81//! outside a `<matrix>` takes an `offset` and an optional `@` anchor; `x @ 100` selects at one
82//! fixed instant across the evaluation grid, as does `rate(x[5m] @ 100)` for its window.
83//!
84//! Those shapes become `Input` (raw samples) → `Instant` (the last sample within the statement's
85//! lookback), `Input` (raw samples) → `Window` (the range function over the statement's grid),
86//! `<expression>` → `Window` whose input is evaluated (the subquery, whose input grid is its own),
87//! `<expression>` → `Map` (a pointwise math, native histogram or label function over what its
88//! argument evaluates to) and, over
89//! any of those, `Binary` (an arithmetic or comparison operation between vectors or with a
90//! constant on one side), `Scalar` (that constant), `Set` (`and`, `or` or `unless` between two
91//! vectors), `Info` (the expression and an `Instant` of the info metric reporting sample times),
92//! `Aggregate` (one of the nine aggregators that
93//! fold a group's values into one value per grid point, optionally grouped) and `Vector` (an
94//! operation over the whole vector at each point: a sort, `absent`, a classic histogram function, a
95//! selecting aggregator or `count_values`). Everything else is a
96//! [`DataFusionError::NotImplemented`] that names what was found and quotes the shapes above,
97//! because rejecting a query the compiler does not understand is the only honest alternative to
98//! compiling it into something else.
99//!
100//! The compiler binds a subquery's child grid and `RangeWindow` independently of runtime execution:
101//! compilation describes the anchored interval, while runtime support determines how that bound
102//! plan is consumed.
103//!
104//! Two decisions keep the recursion from growing a branch per query. A constant argument — a
105//! quantile, a rounding step, a clamp bound — is folded out of the statement by [`constant_value`],
106//! so `quantile_over_time(1 - 0.1, x[5m])` binds the number it means rather than the expression it
107//! was written as. A math function is bound by [`math_op`] from a list of names, so
108//! `clamp_min(abs(rate(x[5m])), 0)` is two maps over one window because the arguments nest, not
109//! because the compiler knows the query. Arithmetic inside a fold is the kernel operation
110//! [`BinaryOp::kind`] names, so the number this compiler binds and the number the kernel computes
111//! cannot disagree about `%`, `^` or `atan2`.
112//!
113//! Two more are about what a node means rather than about which node to build. A binary operation
114//! keeps its operands in the order they were written, because most operators are not commutative:
115//! `1 / x` is not `x / 1`, and which side the constant is on is the only thing that tells them
116//! apart. `return_bool` is carried as its own field, so `x > 0` (which filters) and `x > bool 0`
117//! (which reports zero or one) are one node with one field changed. A negation then needs no node of
118//! its own: `-x` binds as the multiplication by `-1` that it is, which the multiplication kernel
119//! already computes.
120//!
121//! Vector matching is bound with each selector's own input, including the labels and cardinality
122//! written on a vector–vector operation. A scalar has no input of its own: it is bound next to the
123//! vector that gives it something to broadcast over, while a statement whose value is only a
124//! constant is bound by [`compile_statement`] as that constant on the statement's grid.
125//!
126//! An aggregate is bound as [`AggregateStage::Complete`], which is a claim about the whole execution
127//! rather than about the node: it says that every contribution to every group is in this execution's
128//! input. The caller has to keep that claim. One tree per partition does not: handing every
129//! partition the same `Complete` tree sums each partition's part and reports it as the group's
130//! whole, so a partitioned caller has to feed whole groups to one execution or split the aggregation
131//! into `Partial` and `Final` instead. What a `Complete` node guarantees here is only the arithmetic
132//! — that the values it folded are all the values it was given.
133//!
134//! The statement's grid, the selector's lookback, window, offset and anchor are the only numbers
135//! derived here; the legality of the tree is not checked here. [`NativeTree::try_new`] is the
136//! single authority on that, so a node added later cannot be legal in one place and illegal in
137//! another. What is refused before a tree exists is the scan's shape: no shape below can consume
138//! chunks of different series that interleave, so an `Interleaved` ordering is refused once, at the
139//! entry, and [`NativeNode::validate`] refuses the same ordering for a tree built some other way.
140
141use std::cell::RefCell;
142use std::sync::Arc;
143use std::time::Duration;
144
145use datafusion::error::{DataFusionError, Result};
146use datatypes::series::samples::{FieldSpec, SeriesSchema};
147use datatypes::series::time::{EvalGrid, GridSpec};
148use datatypes::series::{SeriesLabels, SeriesOrdering};
149use promql::extension_plan::FieldKind;
150use promql::histogram_eval::{HistogramFunction, NativeHistogramFunction};
151use promql::info::InfoSelector;
152use promql::map::MathOp;
153use promql::map_label::LabelRewrite;
154use promql::map_time::DateFunction;
155use promql::native::plan::{
156 AggregateKind, AggregateStage, BoundAggregate, BoundInput, BoundInstant, BoundMap, BoundScalar,
157 BoundSetOp, BoundVectorOp, BoundWindow, Grouping, InstantValue, MapOp, NativeExpr, NativeNode,
158 NativeTree, NativeType, ParameterizedOp,
159};
160use promql::range_eval::{RangeFunction, RangeWindow, subquery_grid};
161use promql::select::{LabelMatcher, MatchOp, SortOrder, absent_labels};
162use promql::vector_match::{
163 BinaryKind, BinaryMatching, BinaryOp, Cardinality, FillValues, MatchingLabels, SetOp,
164 binary_output_schema,
165};
166use promql_parser::label::{MatchOp as ParserMatchOp, Matcher, Matchers};
167use promql_parser::parser::token::TokenType;
168use promql_parser::parser::value::ValueType;
169use promql_parser::parser::{
170 AggregateExpr, AtModifier, BinModifier, BinaryExpr, Call, EvalStmt, Expr as PromExpr,
171 LabelModifier, MatrixSelector, NumberLiteral, Offset, StringLiteral, SubqueryExpr,
172 VectorMatchCardinality, VectorMatchFillValues, VectorSelector, token,
173};
174
175use crate::promql::label_values::signed_millis_since_epoch;
176
177#[derive(Clone, Copy, Debug, PartialEq, Eq)]
178pub enum SelectorTiming {
179 Instant { lookback_ms: i64 },
180 Window { range_ms: i64 },
181}
182
183#[derive(Clone, Debug)]
184pub struct SelectorRequirement {
185 pub metric: Option<String>,
186 pub matchers: Matchers,
187 pub offset_ms: i64,
188 pub at_ms: Option<i64>,
189 pub grid_start_ms: i64,
190 pub grid_end_ms: i64,
191 pub timing: SelectorTiming,
192}
193
194impl SelectorRequirement {
195 /// Returns `(start_ms, end_ms, include_start)` for the scan hull covering this selector.
196 ///
197 /// The upper endpoint is inclusive. The hull can include timestamps unused by a sparse
198 /// evaluation grid; `grid_end_ms` is its actual last point, not the statement's end. The lower
199 /// endpoint is inclusive only for a zero-lookback instant selector.
200 pub fn raw_scan_bounds(&self) -> Result<(i64, i64, bool)> {
201 let end = self
202 .at_ms
203 .unwrap_or(self.grid_end_ms)
204 .checked_sub(self.offset_ms)
205 .ok_or_else(|| DataFusionError::Plan("selector scan end overflows".into()))?;
206 let lower = self
207 .at_ms
208 .unwrap_or(self.grid_start_ms)
209 .checked_sub(self.offset_ms)
210 .ok_or_else(|| DataFusionError::Plan("selector scan start overflows".into()))?;
211 let (duration, inclusive) = match self.timing {
212 SelectorTiming::Instant { lookback_ms } => (lookback_ms, lookback_ms == 0),
213 SelectorTiming::Window { range_ms } => (range_ms, false),
214 };
215 let start = lower
216 .checked_sub(duration)
217 .ok_or_else(|| DataFusionError::Plan("selector scan start overflows".into()))?;
218 Ok((start, end, inclusive))
219 }
220}
221
222/// One compiled selector occurrence and the scan layout bound for it.
223#[derive(Clone, Debug)]
224pub struct CompiledInput {
225 /// Occurrence number assigned in compiler traversal order, starting at zero. The caller maps this
226 /// occurrence to the appropriate scan; different occurrences may map to a shared scan child.
227 pub source_index: usize,
228 pub requirement: SelectorRequirement,
229 pub schema: Arc<SeriesSchema>,
230 pub ordering: SeriesOrdering,
231}
232
233#[derive(Clone, Debug)]
234pub struct CompiledTree {
235 pub tree: NativeTree,
236 pub inputs: Arc<[CompiledInput]>,
237}
238
239/// The shapes this compiler accepts, quoted in every rejection.
240///
241/// It is one sentence of grammar rather than a list of examples, because it is what a refused query
242/// reads: the shapes have to be true of every query the compiler binds, and the examples only show
243/// them. The two matrix shapes and the recursion through them are stated first, because that
244/// recursion is what a reader is most likely to get wrong.
245const SUPPORTED: &str = "a selector — `x`, optionally with an `offset` — a range function over \
246 a matrix, where a matrix is `<selector>[<range>]` as in `rate(x[5m])` or \
247 `<expression>[<range>:<step>]` as in `rate(x[5m:1m])`, with the step \
248 optionally omitted as `[<range>:]`, where the subquery's `<expression>` \
249 is any shape here, so a subquery nests on a grid of its own as in \
250 `rate(rate(x[5m:1m])[10m:30s])`, and where either matrix shape carries the \
251 `offset` and `@` anchor written on it as in `rate(x[5m] @ 1234)`; a math \
252 function over any of them (`abs(rate(x[5m]))`, `clamp_min(x, 0)`), with \
253 `round` and the `clamp` functions also taking scalars \
254 (`round(x, time() / 10)`), a native \
255 histogram function over any of them (`histogram_count(x)`), a label \
256 function over any of them \
257 (`label_replace(x, \"a\", \"$1\", \"b\", \"(.*)\")`), a binary \
258 operation between one of them and a scalar (`2 / (x + 1)`, \
259 `x > bool time()`, `time() - timestamp(x)`), a scalar — a constant, \
260 `time()` or a binary operation between scalars — \
261 `vector(<scalar>)`, a date function without an argument (`hour()`), a \
262 negation of one of them (`-x`), a set operation between two of them \
263 (`x and on(job) y`, `x or y`, `x unless y`), `info` over any of them with \
264 one info metric (`info(x, {version=~\".+\"})`), or one of the \
265 aggregators that folds a group's values into one value per grid point — \
266 `sum`, `avg`, `count`, `min`, `max`, `group`, `stddev`, `stdvar` and \
267 `quantile(<constant>, <expression>)` — over any of them, optionally \
268 grouped by `by` or `without` as in `avg by(job)(rate(x[5m]) * 100)`; \
269 `topk`, `bottomk`, `limitk`, `limit_ratio` or `count_values` over any of \
270 them, as in `topk(3, x) by(job)` and `count_values(\"v\", x)`; a \
271 sort, `absent`, `absent_over_time` or `histogram_quantile` / \
272 `histogram_fraction` over any of them (`sort_desc(x)`, \
273 `absent(x{job=\"a\"})`, `absent_over_time(x{job=\"a\"}[5m])`, \
274 `histogram_quantile(0.9, rate(x[5m]))`); a range function's own \
275 constants sit where that function takes them, before \
276 the matrix for `quantile_over_time(0.9, x[5m])` and after it for \
277 `predict_linear(x[5m], 300)` and \
278 `double_exponential_smoothing(x[5m], 0.5, 0.1)`";
279
280/// Compiles `stmt` into a tree that reads `input` and evaluates the statement's expression over it.
281///
282/// `input` is the raw series schema the caller bound from the table, and the caller has to apply the
283/// selector's matchers before binding it: `__field__`, `__schema__` and `__database__` select rows
284/// and fields the same way they do in the existing planner, and the AST cannot restate that
285/// afterwards. `input.fields` is therefore the post-`__field__` field set, not the table's; a caller
286/// that binds every field of the table instead compiles a different, wrong window, because
287/// `rate(x{__field__="a"}[5m])` over fields `[a, b]` would fold two fields where the planner folds
288/// one.
289///
290/// `ordering` is what the caller's scan guarantees, and the tree records it rather than assuming
291/// one. Only `Contiguous` and `KeyThenTime` are accepted: every shape this compiler accepts reads
292/// one series to its last chunk before the next, so an `Interleaved` declaration is refused at the
293/// entry, before any shape is built — the bare selector included, which returns before a window
294/// exists — and a shape added later inherits the refusal instead of restating it.
295/// [`NativeNode::validate`] refuses the same ordering in its `Instant` and `Window` branches, as a
296/// backstop for a tree built some other way.
297///
298/// This compatibility entry accepts exactly one selector. Call [`compile_selectors`] to retain
299/// each selector's requirement and binding when compiling more than one input.
300pub fn compile(
301 stmt: &EvalStmt,
302 input: Arc<SeriesSchema>,
303 ordering: SeriesOrdering,
304) -> Result<NativeTree> {
305 // This entry describes one float input: it has no way to be told that a field carries native
306 // histograms, so an aggregate whose state would depend on that is bound as the float aggregate it
307 // would be. A caller that does know - the planner, from the table's own fields - binds through
308 // [`compile_selectors`] and passes the kind with it.
309 let compiled = compile_selectors(
310 stmt,
311 &|_| Ok(Arc::clone(&input)),
312 ordering,
313 Some(FieldKind::Float),
314 )?;
315 if compiled.inputs.len() != 1 {
316 return Err(not_implemented(&format!(
317 "`compile` with {} selector inputs; use `compile_selectors` to bind each input",
318 compiled.inputs.len()
319 )));
320 }
321 Ok(compiled.tree)
322}
323
324fn data_free_value_field(stmt: &EvalStmt) -> Arc<str> {
325 fn visit(expr: &PromExpr, targets: &mut Vec<String>) {
326 match expr {
327 PromExpr::Aggregate(aggregate) => {
328 if aggregate.op.id() == token::T_COUNT_VALUES
329 && let Some(param) = &aggregate.param
330 && let PromExpr::StringLiteral(value) = unparen(param)
331 {
332 targets.push(value.val.clone());
333 }
334 if let Some(modifier) = &aggregate.modifier {
335 match modifier {
336 LabelModifier::Include(labels) | LabelModifier::Exclude(labels) => {
337 targets.extend(labels.labels.iter().cloned());
338 }
339 }
340 }
341 // An aggregate's parameter is an expression since `topk` and friends take one, and
342 // the grouping labels it binds are names the value field must not collide with:
343 // an aggregate refuses to group by the field it folds.
344 if let Some(param) = &aggregate.param {
345 visit(param, targets);
346 }
347 visit(&aggregate.expr, targets);
348 }
349 PromExpr::Unary(unary) => visit(&unary.expr, targets),
350 PromExpr::Binary(binary) => {
351 if let Some(modifier) = &binary.modifier {
352 if let Some(matching) = &modifier.matching {
353 targets.extend(matching.labels().labels.iter().cloned());
354 }
355 match &modifier.card {
356 VectorMatchCardinality::OneToMany(labels)
357 | VectorMatchCardinality::ManyToOne(labels) => {
358 targets.extend(labels.labels.iter().cloned());
359 }
360 _ => {}
361 }
362 }
363 visit(&binary.lhs, targets);
364 visit(&binary.rhs, targets);
365 }
366 PromExpr::Paren(paren) => visit(&paren.expr, targets),
367 PromExpr::Subquery(subquery) => visit(&subquery.expr, targets),
368 PromExpr::Call(call) => call.args.args.iter().for_each(|arg| visit(arg, targets)),
369 _ => {}
370 }
371 }
372 let mut targets = Vec::new();
373 visit(&stmt.expr, &mut targets);
374 if !targets.iter().any(|name| name == VECTOR_FIELD) {
375 return Arc::from(VECTOR_FIELD);
376 }
377 (0usize..)
378 .map(|index| format!("native_value_{index}"))
379 .find(|candidate| !targets.iter().any(|name| name == candidate))
380 .map(Arc::from)
381 .expect("the value field candidate sequence is unbounded")
382}
383
384/// Compiles a statement that reads no data — a constant, `time()`, `vector(time())`, `hour()` —
385/// to a tree without inputs, on the statement's grid.
386///
387/// A statement that reads a selector is refused: its scan is the caller's to bind, through
388/// [`compile_selectors`].
389pub fn compile_statement(stmt: &EvalStmt) -> Result<NativeTree> {
390 let output_field = data_free_value_field(stmt);
391 let compiled = compile_selectors_with_value_field(
392 stmt,
393 &|_| {
394 Err(not_implemented(&format!(
395 "a selector in `{}`, which is compiled as a statement that reads no data",
396 stmt.expr
397 )))
398 },
399 SeriesOrdering::Contiguous,
400 output_field,
401 // A statement that reads no data has no source to take a kind from. An aggregate over it
402 // still binds: the walk only reads the source kind at an input node, and there is none.
403 None,
404 )?;
405 Ok(compiled.tree)
406}
407
408/// Compiles `stmt` with an explicit evaluation grid, instead of the one its bounds derive.
409///
410/// A subquery root's inner expression is evaluated on the subquery's child grid, while the
411/// statement's own bounds stay where `@ start()` and `@ end()` resolve against them.
412pub(crate) fn compile_statement_with_grid(
413 stmt: &EvalStmt,
414 grid: Arc<EvalGrid>,
415) -> Result<NativeTree> {
416 let output_field = data_free_value_field(stmt);
417 let compiled = compile_selectors_with_grid_and_value_field(
418 stmt,
419 &|_| {
420 Err(not_implemented(&format!(
421 "a selector in `{}`, which is compiled as a statement that reads no data",
422 stmt.expr
423 )))
424 },
425 SeriesOrdering::Contiguous,
426 output_field,
427 Some(grid),
428 None,
429 )?;
430 Ok(compiled.tree)
431}
432
433/// Compiles `stmt` into a tree and returns a binding record for each selector occurrence.
434///
435/// `bindings` is called once per selector with its requirements. The resulting source indices are
436/// occurrence numbers in compiler traversal order; the caller maps them to scan children.
437pub fn compile_selectors(
438 stmt: &EvalStmt,
439 bindings: &dyn Fn(&SelectorRequirement) -> Result<Arc<SeriesSchema>>,
440 ordering: SeriesOrdering,
441 source_kind: Option<FieldKind>,
442) -> Result<CompiledTree> {
443 compile_selectors_with_value_field(
444 stmt,
445 bindings,
446 ordering,
447 Arc::from(VECTOR_FIELD),
448 source_kind,
449 )
450}
451
452/// Compiles `stmt` with an explicit evaluation grid. See [`compile_statement_with_grid`].
453pub(crate) fn compile_selectors_with_grid(
454 stmt: &EvalStmt,
455 bindings: &dyn Fn(&SelectorRequirement) -> Result<Arc<SeriesSchema>>,
456 ordering: SeriesOrdering,
457 grid: Arc<EvalGrid>,
458 source_kind: Option<FieldKind>,
459) -> Result<CompiledTree> {
460 compile_selectors_with_grid_and_value_field(
461 stmt,
462 bindings,
463 ordering,
464 Arc::from(VECTOR_FIELD),
465 Some(grid),
466 source_kind,
467 )
468}
469
470fn compile_selectors_with_value_field(
471 stmt: &EvalStmt,
472 bindings: &dyn Fn(&SelectorRequirement) -> Result<Arc<SeriesSchema>>,
473 ordering: SeriesOrdering,
474 value_field: Arc<str>,
475 source_kind: Option<FieldKind>,
476) -> Result<CompiledTree> {
477 compile_selectors_with_grid_and_value_field(
478 stmt,
479 bindings,
480 ordering,
481 value_field,
482 None,
483 source_kind,
484 )
485}
486
487fn compile_selectors_with_grid_and_value_field(
488 stmt: &EvalStmt,
489 bindings: &dyn Fn(&SelectorRequirement) -> Result<Arc<SeriesSchema>>,
490 ordering: SeriesOrdering,
491 value_field: Arc<str>,
492 grid: Option<Arc<EvalGrid>>,
493 source_kind: Option<FieldKind>,
494) -> Result<CompiledTree> {
495 if ordering == SeriesOrdering::Interleaved {
496 return Err(not_implemented(
497 "raw samples whose series interleave, which this compiler cannot consume: a native \
498 evaluation reads one series to its last chunk before the next, so chunks of different \
499 series may not interleave",
500 ));
501 }
502 // A tree reports evaluated samples or a scalar on the statement's grid; a range vector or a
503 // string has no grid of its own.
504 if !matches!(
505 stmt.expr.value_type(),
506 ValueType::Vector | ValueType::Scalar
507 ) {
508 return Err(not_implemented(&format!(
509 "the expression `{}`, which is a {} where a tree reports evaluated samples or a \
510 scalar",
511 stmt.expr,
512 stmt.expr.value_type()
513 )));
514 }
515 let inputs = RefCell::new(Vec::new());
516 let context = Context {
517 stmt,
518 bindings,
519 ordering,
520 inputs: &inputs,
521 // The grid is derived only once the statement is a shape this compiler answers, so an
522 // unsupported statement reports the reason it has no tree rather than a grid complaint.
523 grid: match grid {
524 Some(grid) => grid,
525 None => statement_grid(stmt)?,
526 },
527 value_field,
528 source_kind,
529 };
530 let tree = NativeTree::try_new(compile_expr(&context, &stmt.expr)?)?;
531 let inputs = inputs.into_inner();
532 validate_inputs(tree.root(), &inputs)?;
533 Ok(CompiledTree {
534 tree,
535 inputs: inputs.into(),
536 })
537}
538
539fn validate_inputs(root: &NativeNode, inputs: &[CompiledInput]) -> Result<()> {
540 let bound = root.inputs();
541 if bound.len() == inputs.len()
542 && bound
543 .iter()
544 .zip(inputs)
545 .enumerate()
546 .all(|(index, (bound, input))| {
547 input.source_index == index
548 && bound.source_index == input.source_index
549 && bound.ordering == input.ordering
550 && bound
551 .output
552 .samples()
553 .is_some_and(|schema| Arc::ptr_eq(schema, &input.schema))
554 })
555 {
556 return Ok(());
557 }
558 Err(DataFusionError::Internal(
559 "a compiled tree's recorded inputs do not match its input nodes".into(),
560 ))
561}
562
563/// Shared statement, per-selector binding callback, occurrence records, ordering and current grid.
564///
565/// A subquery substitutes its own grid while reusing the statement-level bindings and input list.
566struct Context<'a> {
567 stmt: &'a EvalStmt,
568 bindings: &'a dyn Fn(&SelectorRequirement) -> Result<Arc<SeriesSchema>>,
569 ordering: SeriesOrdering,
570 inputs: &'a RefCell<Vec<CompiledInput>>,
571 grid: Arc<EvalGrid>,
572 value_field: Arc<str>,
573 /// The kind the statement's sources carry, when the caller knows it.
574 ///
575 /// A binding whose state depends on it is refused rather than bound from a guess when it is
576 /// unknown: `source_kind` is `None` only for a statement the caller could not describe, and a
577 /// tree with no source never needs it.
578 source_kind: Option<FieldKind>,
579}
580
581/// Compiles `expr` into the node it denotes, recursing into whatever it is made of.
582///
583/// One rule per kind of expression and nothing per query: a math function is compiled by compiling
584/// its argument, so a query nests as deeply as it was written. A kind this compiler has no node for
585/// is refused with what was found, which is why the rejection is useful without a coverage list.
586fn compile_expr(context: &Context, expr: &PromExpr) -> Result<NativeNode> {
587 // A constant is a value rather than a computation, so it binds as the number it folds to, by the
588 // same fold a call's parameters use: `x * (1 + 2)` carries `3` rather than an addition the tree
589 // would have to know how to run. The fold is checked first so that no shape below has to say
590 // what it does with a constant operand.
591 if let Some(value) = constant_value(expr) {
592 return Ok(scalar_node(context, value));
593 }
594 match expr {
595 // Parentheses group, so they change how a statement was typed rather than what it asks for:
596 // the expression inside them is the one that compiles.
597 PromExpr::Paren(paren) => compile_expr(context, &paren.expr),
598 PromExpr::Call(call) => compile_call(context, call),
599 PromExpr::VectorSelector(selector) => instant_selection(context, selector),
600 PromExpr::Unary(unary) => negate(context, &unary.expr),
601 PromExpr::Binary(binary) => binary_operation(context, binary),
602 PromExpr::Aggregate(aggregate) => aggregate_expr(context, aggregate),
603 found => Err(not_implemented(&format!("the expression `{found}`"))),
604 }
605}
606
607/// Binds `value` as a constant scalar on the grid of the expression being compiled.
608///
609/// The grid is the context's rather than the constant's own: a constant has no timestamps, so the
610/// only positions it can be broadcast over are the ones the expression it sits next to is evaluated
611/// at — the statement's grid, or a subquery's inside one. [`NativeTree::validate`] compares a binary
612/// operation's two grids by spec rather than by allocation.
613///
614/// Nothing here can fail: the grid is the one [`Context`] already carries, so a caller needs no `?`.
615fn scalar_node(context: &Context, value: f64) -> NativeNode {
616 NativeNode {
617 expr: NativeExpr::Scalar(BoundScalar { value }),
618 output: NativeType::Scalar(Arc::clone(&context.grid)),
619 }
620}
621
622/// Compiles a negation as the multiplication it is: `-x` is `-1 * x`.
623///
624/// The tree has no negate node and needs none: broadcasting a constant over the expression's value
625/// is the same arithmetic, and the multiplication kernel is the one that already computes it. A
626/// dedicated negate kernel would be an optimization of this node's work rather than a different
627/// meaning, so binding the multiplication does not bind anything the query did not ask for.
628fn negate(context: &Context, operand: &PromExpr) -> Result<NativeNode> {
629 // The constant goes on the left, where the minus was: `-x` subtracts nothing, but a reader of
630 // the tree should see the same order the query was written in.
631 Ok(broadcast(
632 scalar_node(context, -1.0),
633 compile_expr(context, operand)?,
634 BinaryOp::Mul,
635 false,
636 ))
637}
638
639/// Compiles a binary operation, preserving written operand order and vector matching modifiers.
640///
641/// A scalar carries no labels, so broadcasting it over a vector is unambiguous. Vector operands
642/// retain their own input bindings and matching, including a fill on either side.
643fn binary_operation(context: &Context, binary: &BinaryExpr) -> Result<NativeNode> {
644 if let Some(op) = set_op(&binary.op) {
645 return set_operation(context, binary, op);
646 }
647 let Some(op) = binary_op(&binary.op) else {
648 return Err(not_implemented(&format!(
649 "the binary operator `{}` in `{binary}`",
650 binary.op
651 )));
652 };
653 // Two vectors are matched by their labels, so the node carries the modifiers the query wrote and
654 // each operand is compiled from its own selector.
655 if binary.lhs.value_type() == ValueType::Vector && binary.rhs.value_type() == ValueType::Vector
656 {
657 let left = compile_expr(context, &binary.lhs)?;
658 let right = compile_expr(context, &binary.rhs)?;
659 return bind_vector_binary(binary, left, right, op);
660 }
661 // What is left has a constant on one side, and a modifier is refused rather than dropped. This
662 // is deliberately narrower than Prometheus, which drops an `on` or `ignoring` written on a
663 // scalar rather than refusing it; refusing is the conservative choice here, because the tree's
664 // matching has no field that could carry the modifier, so binding the operation would compute
665 // something the query did not ask for. A fill value is refused for the same reason: the tree's
666 // matching has no field for one, and dropping it would compute the operation without the fill
667 // the query asked for.
668 if refuses_modifier(binary.modifier.as_ref()) {
669 return Err(not_implemented(&format!(
670 "the vector matching in `{binary}`, which a constant operand has nothing to match: \
671 `on`, `ignoring`, `group_left` and `group_right` name labels of a vector, and a fill \
672 value fills in a match group that could miss"
673 )));
674 }
675 // A comparison of two scalars reports a value only when written with `bool`; Prometheus
676 // refuses to parse one without it. Binding it would produce a node that only fails when it is
677 // run, so it is refused here with what was found. Two constants never reach here: they folded.
678 if binary.lhs.value_type() == ValueType::Scalar
679 && binary.rhs.value_type() == ValueType::Scalar
680 && matches!(op.kind(), BinaryKind::Comparison(_))
681 && !binary.return_bool()
682 {
683 return Err(not_implemented(&format!(
684 "the binary operation `{binary}` between two scalars, which reports no value: a \
685 comparison of two scalars is written with `bool` to say whether it holds"
686 )));
687 }
688 // Both operands are compiled before the node is built, so `2 / (x + 1)` nests. The constant side
689 // is bound by [`compile_expr`]'s fold, which is what makes it a scalar node rather than an
690 // expression the tree would have to run.
691 Ok(broadcast(
692 compile_expr(context, &binary.lhs)?,
693 compile_expr(context, &binary.rhs)?,
694 op,
695 binary.return_bool(),
696 ))
697}
698
699/// Binds the same vector operation over compiled or already evaluated operands.
700fn bind_vector_binary(
701 binary: &BinaryExpr,
702 left: NativeNode,
703 right: NativeNode,
704 op: BinaryOp,
705) -> Result<NativeNode> {
706 let (Some(lhs), Some(rhs)) = (left.output.samples(), right.output.samples()) else {
707 return Err(DataFusionError::Internal(format!(
708 "the binary operation `{binary}` compiled a vector operand to something other than samples"
709 )));
710 };
711 let output = NativeType::Samples(binary_output_schema(lhs, rhs)?);
712 Ok(NativeNode {
713 expr: NativeExpr::Binary {
714 left: Box::new(left),
715 right: Box::new(right),
716 matching: vector_matching(binary, op)?,
717 },
718 output,
719 })
720}
721
722/// Uses the ordinary binary binder for two evaluated frame inputs.
723pub(crate) fn bind_evaluated_binary(
724 binary: &BinaryExpr,
725 left: NativeNode,
726 right: NativeNode,
727) -> Result<NativeTree> {
728 let op = binary_op(&binary.op).ok_or_else(|| {
729 not_implemented(&format!(
730 "the binary operator `{}` in `{binary}`",
731 binary.op
732 ))
733 })?;
734 NativeTree::try_new(bind_vector_binary(binary, left, right, op)?)
735}
736
737/// Compiles `and`, `or` or `unless` between two vectors, matched by the labels the query wrote.
738///
739/// The parser already refuses a scalar operand, `bool` and `group_left` / `group_right` on a set
740/// operator. It does not refuse a fill value, which Prometheus does ("filling in missing series not
741/// allowed for set operators"), so that is refused here along with any cardinality other than the
742/// many-to-many the parser assigns.
743fn set_operation(context: &Context, binary: &BinaryExpr, op: SetOp) -> Result<NativeNode> {
744 let modifier = binary.modifier.as_ref();
745 if modifier.is_some_and(|modifier| {
746 modifier.card != VectorMatchCardinality::ManyToMany
747 || modifier.fill_values != VectorMatchFillValues::default()
748 }) {
749 return Err(not_implemented(&format!(
750 "the modifiers in `{binary}`: a set operator matches many-to-many and takes no fill \
751 value"
752 )));
753 }
754 let labels = matching_labels(modifier);
755 let left = compile_expr(context, &binary.lhs)?;
756 let right = compile_expr(context, &binary.rhs)?;
757 let (Some(lhs), Some(rhs)) = (left.output.samples(), right.output.samples()) else {
758 return Err(DataFusionError::Internal(format!(
759 "the set operation `{binary}` compiled an operand to something other than samples: the \
760 parser only accepts a set operator between two vectors"
761 )));
762 };
763 // Prometheus has one value per sample, and the existing planner refuses a set operator over
764 // several fields, so per-field presence has no reference semantics to follow.
765 if lhs.fields.len() != 1 || rhs.fields.len() != 1 {
766 return Err(not_implemented(&format!(
767 "the set operation `{binary}` between vectors of {} and {} fields: a set operator is \
768 compiled over one field on each side",
769 lhs.fields.len(),
770 rhs.fields.len()
771 )));
772 }
773 // A set operation hands on the samples it keeps unchanged, so it reports the left side's fields
774 // on the grid both sides share.
775 let output = left.output.clone();
776 Ok(NativeNode {
777 expr: NativeExpr::Set {
778 left: Box::new(left),
779 right: Box::new(right),
780 op: BoundSetOp { op, labels },
781 },
782 output,
783 })
784}
785
786/// Wraps two compiled operands in the binary node that applies `op` to them.
787///
788/// The output is the vector side's own binding, because a scalar carries no fields: a broadcast keeps
789/// the vector's fields and the grid it is evaluated on, which is the statement's grid on both sides.
790/// Two scalars are possible as a nested operand — a pair that [`constant_value`] refuses to fold, such
791/// as a comparison between two constants — and the node reports the left one's grid, which is the
792/// statement's too. The operands keep the order they were written in, because a non-commutative
793/// operator means what that order says.
794fn broadcast(left: NativeNode, right: NativeNode, op: BinaryOp, return_bool: bool) -> NativeNode {
795 // `compile_expr` binds a constant to a scalar node and a selection or a function to a vector, so
796 // this is where the side the operation reports is decided.
797 let output = if matches!(left.output, NativeType::Scalar(_)) {
798 right.output.clone()
799 } else {
800 left.output.clone()
801 };
802 NativeNode {
803 expr: NativeExpr::Binary {
804 left: Box::new(left),
805 right: Box::new(right),
806 matching: scalar_matching(op, return_bool),
807 },
808 output,
809 }
810}
811
812/// The matching a vector-and-constant operation records.
813///
814/// Nothing is matched: a scalar carries no labels, so [`NativeTree::validate`] broadcasts it and
815/// reads neither `labels` nor `cardinality`. They carry the default a vector–vector operation of the
816/// same operator would have, which is also the only matching PromQL allows here — it rejects
817/// `on`, `ignoring`, `group_left` and `group_right` on a scalar–vector operation. `return_bool` is
818/// the one modifier that changes what this operation computes: `x > 0` filters the vector and
819/// `x > bool 0` reports zero or one for each of its values.
820fn scalar_matching(op: BinaryOp, return_bool: bool) -> BinaryMatching {
821 BinaryMatching {
822 op,
823 return_bool,
824 labels: MatchingLabels::Ignoring(Vec::new()),
825 cardinality: Cardinality::OneToOne,
826 // A fill value fills in a match group that could miss, which a broadcast over a constant never
827 // does: the constant exists at every grid point, so there is no missing side to fill.
828 fill: FillValues::default(),
829 }
830}
831
832/// The matching a vector–vector operation records.
833///
834/// Each part is read from the modifier the query wrote, and a modifier it did not write is the
835/// default PromQL applies: every label but `__name__` matches (`ignoring` nothing), and the
836/// cardinality is one-to-one. Fill fields retain the parser's left/right values, which name the
837/// sides as written: the kernel swaps them together with the operands under `group_right`.
838///
839/// `ManyToMany` is the cardinality of a set operator, which [`binary_operation`] compiles before
840/// asking for a matching, so reaching it means the two disagree; it is reported as a shape with no
841/// node rather than panicking on a path a query cannot take today.
842fn vector_matching(binary: &BinaryExpr, op: BinaryOp) -> Result<BinaryMatching> {
843 let modifier = binary.modifier.as_ref();
844 let labels = matching_labels(modifier);
845 let cardinality = match modifier.map(|modifier| &modifier.card) {
846 None | Some(VectorMatchCardinality::OneToOne) => Cardinality::OneToOne,
847 Some(VectorMatchCardinality::ManyToOne(labels)) => {
848 Cardinality::ManyToOne(label_names(&labels.labels))
849 }
850 Some(VectorMatchCardinality::OneToMany(labels)) => {
851 Cardinality::OneToMany(label_names(&labels.labels))
852 }
853 Some(VectorMatchCardinality::ManyToMany) => {
854 return Err(not_implemented(&format!(
855 "the many-to-many matching in `{binary}`, which is the cardinality of a set \
856 operator: it combines two vectors' series, and this node is an arithmetic or \
857 comparison operation over values"
858 )));
859 }
860 };
861 let fill = modifier.map_or_else(FillValues::default, |modifier| FillValues {
862 lhs: modifier.fill_values.lhs,
863 rhs: modifier.fill_values.rhs,
864 });
865 Ok(BinaryMatching {
866 op,
867 return_bool: binary.return_bool(),
868 labels,
869 cardinality,
870 fill,
871 })
872}
873
874/// The set operator a PromQL token denotes, or `None` when it is not one.
875fn set_op(op: &TokenType) -> Option<SetOp> {
876 match op.id() {
877 token::T_LAND => Some(SetOp::And),
878 token::T_LOR => Some(SetOp::Or),
879 token::T_LUNLESS => Some(SetOp::Unless),
880 _ => None,
881 }
882}
883
884/// The labels `on(...)` or `ignoring(...)` names; with neither, every label but `__name__`.
885fn matching_labels(modifier: Option<&BinModifier>) -> MatchingLabels {
886 match modifier.and_then(|modifier| modifier.matching.as_ref()) {
887 None => MatchingLabels::Ignoring(Vec::new()),
888 Some(LabelModifier::Include(labels)) => MatchingLabels::On(label_names(&labels.labels)),
889 Some(LabelModifier::Exclude(labels)) => {
890 MatchingLabels::Ignoring(label_names(&labels.labels))
891 }
892 }
893}
894
895fn label_names(labels: &[String]) -> Vec<Arc<str>> {
896 labels.iter().map(|name| Arc::from(name.as_str())).collect()
897}
898
899/// The binary operator a PromQL token denotes, or `None` when there is no node for it.
900///
901/// A comparison carries `return_bool` separately, so `x > 0` and `x > bool 0` use the same
902/// operator. The node the runtime executes and the constant fold both read the operator here.
903fn binary_op(op: &TokenType) -> Option<BinaryOp> {
904 match op.id() {
905 token::T_ADD => Some(BinaryOp::Add),
906 token::T_SUB => Some(BinaryOp::Sub),
907 token::T_MUL => Some(BinaryOp::Mul),
908 token::T_DIV => Some(BinaryOp::Div),
909 token::T_MOD => Some(BinaryOp::Mod),
910 token::T_POW => Some(BinaryOp::Pow),
911 token::T_ATAN2 => Some(BinaryOp::Atan2),
912 token::T_EQLC => Some(BinaryOp::Eq),
913 token::T_NEQ => Some(BinaryOp::Ne),
914 token::T_GTR => Some(BinaryOp::Gt),
915 token::T_LSS => Some(BinaryOp::Lt),
916 token::T_GTE => Some(BinaryOp::Ge),
917 token::T_LTE => Some(BinaryOp::Le),
918 _ => None,
919 }
920}
921
922/// Compiles an aggregation into an aggregate node over the expression it groups.
923///
924/// The aggregators that fold a group's values into one value per grid point bind to an aggregate
925/// node: `sum`, `avg`, `count`, `min`, `max`, `group`, `stddev`, `stdvar` and `quantile`. The
926/// runtime validates whether the resulting tree can execute.
927///
928/// The rest of the parser's aggregates are a different shape and bind as a vector operation
929/// ([`vector_aggregate`]) rather than as a kind that would compute something else: `topk`,
930/// `bottomk`, `limitk` and `limit_ratio` select some of the input's series, so they do not report
931/// one value per group per grid point, and `count_values` writes one output label per distinct value
932/// rather than folding a group's values at all.
933///
934/// The grouping is bound in the tree's own terms, because `by` and `without` are not each other's
935/// inverse: `by(job)` keeps `job` and drops every other label, while `without(instance)` keeps every
936/// label it does not name and drops `__name__` as well, so a list of the surviving labels could not
937/// say the same thing. A bare `sum(x)` groups by no label at all, which is Prometheus's reading of
938/// "no modifier": every label is dropped, `__name__` included, and every series of the input falls
939/// into one group.
940///
941/// The stage is [`AggregateStage::Complete`], which says that every contribution to each group is in
942/// this execution's input. The module documentation says what keeping that claim costs a caller.
943fn aggregate_expr(context: &Context, aggregate: &AggregateExpr) -> Result<NativeNode> {
944 let AggregateExpr {
945 op,
946 expr,
947 param,
948 modifier,
949 } = aggregate;
950 let kind = match op.id() {
951 token::T_SUM => AggregateKind::Sum,
952 token::T_AVG => AggregateKind::Avg,
953 token::T_COUNT => AggregateKind::Count,
954 token::T_MIN => AggregateKind::Min,
955 token::T_MAX => AggregateKind::Max,
956 token::T_GROUP => AggregateKind::Group,
957 token::T_STDDEV => AggregateKind::Stddev,
958 token::T_STDVAR => AggregateKind::Stdvar,
959 token::T_QUANTILE => {
960 // `quantile` is the only one of the nine with a parameter, and the parser always gives
961 // it one: a `quantile` with no quantile written is refused before the compiler sees it.
962 // The quantile is the call's first argument, so a parameter that is not a constant is
963 // refused under that name rather than answered from a number bound too early.
964 let param = param.as_ref().ok_or_else(|| {
965 not_implemented(&format!(
966 "the aggregate `{op}` in `{aggregate}`, which takes its quantile as its first \
967 argument"
968 ))
969 })?;
970 AggregateKind::Quantile {
971 quantile: constant_argument(&op.to_string(), param, 0)?,
972 }
973 }
974 // A ranking aggregate keeps some of the input's series, and `count_values` writes one
975 // output label per distinct value: neither folds a group into one value per grid point, so
976 // both read the whole vector in a `Vector` node instead.
977 token::T_TOPK
978 | token::T_BOTTOMK
979 | token::T_LIMITK
980 | token::T_LIMIT_RATIO
981 | token::T_COUNT_VALUES => {
982 return vector_aggregate(context, aggregate);
983 }
984 // The parser's `aggregate_op` rule lists exactly the fourteen names above, so this arm is
985 // an operator this compiler was not taught rather than one it means to fold.
986 _ => {
987 return Err(not_implemented(&format!(
988 "the aggregate `{op}` in `{aggregate}`"
989 )));
990 }
991 };
992 let input = compile_expr(context, expr)?;
993 // What the aggregate's state carries is what its direct input answers with, so the binding is
994 // decided here, from the input's own walk, rather than from the statement's sources: an
995 // operator between the two can change the kind (`sum(count_over_time(h[5m]))` folds a float
996 // built from histograms).
997 //
998 // A kind this walk cannot name is not a float by default: the state a `sum` or `avg` keeps over
999 // a histogram is a different layout, so binding one from a guess would compute the wrong thing
1000 // for a statement whose sources carry histograms. Such a shape keeps the existing plan (the
1001 // refusal is `NotImplemented`).
1002 //
1003 // With float sources - or with no source at all - an unnameable input is still a float, and the
1004 // aggregate binds the numeric state it always did. What makes that a proof rather than a default
1005 // is that a native histogram sample can only enter a tree from a source that carries one: every
1006 // operator here passes a histogram through, reduces it to a float, or declines the shape. A
1007 // shape whose samples this walk does not describe (`clamp`, `topk`, `vector()` of a scalar) can
1008 // therefore not be holding one.
1009 let field_kind = match input.output_field_kind(context.source_kind) {
1010 Some(kind) => kind,
1011 None if context.source_kind == Some(FieldKind::Histogram) => {
1012 return Err(not_implemented(&format!(
1013 "the aggregate `{op}` in `{aggregate}`, whose input's field kind this compile cannot \
1014 name while its sources carry native histograms: the aggregate's state depends on \
1015 whether the input carries floats or histograms"
1016 )));
1017 }
1018 None => FieldKind::Float,
1019 };
1020 // A complete aggregate folds each group's values and reports them on its input's grid, one value
1021 // per input field, so its layout is its input's.
1022 let output = input.output.clone();
1023 Ok(NativeNode {
1024 expr: NativeExpr::Aggregate {
1025 input: Box::new(input),
1026 op: BoundAggregate {
1027 kind,
1028 group: grouping(modifier.as_ref()),
1029 stage: AggregateStage::Complete,
1030 field_kind,
1031 },
1032 },
1033 output,
1034 })
1035}
1036
1037/// Binds `topk`, `bottomk`, `limitk`, `limit_ratio` or `count_values` as a vector operation over
1038/// the expression it aggregates.
1039///
1040/// The parser gives each of them its parameter: a number for the first four, folded to the constant
1041/// it means like a `quantile`, and a string for `count_values`, the label it writes the value to.
1042fn vector_aggregate(context: &Context, aggregate: &AggregateExpr) -> Result<NativeNode> {
1043 let AggregateExpr {
1044 op,
1045 expr,
1046 param,
1047 modifier,
1048 } = aggregate;
1049 let name = op.to_string();
1050 let param = param.as_ref().ok_or_else(|| {
1051 not_implemented(&format!(
1052 "the aggregate `{op}` in `{aggregate}`, which takes a parameter as its first argument"
1053 ))
1054 })?;
1055 let group = grouping(modifier.as_ref());
1056 if matches!(op.id(), token::T_TOPK | token::T_BOTTOMK) && constant_value(param).is_none() {
1057 let input = compile_expr(context, expr)?;
1058 let output = input.output.clone();
1059 let parameter = compile_expr(context, param)?;
1060 return Ok(NativeNode {
1061 expr: NativeExpr::ParameterizedTopK {
1062 input: Box::new(input),
1063 op: BoundVectorOp::TopK {
1064 k: 0.0,
1065 top: op.id() == token::T_TOPK,
1066 group,
1067 },
1068 parameter: Box::new(parameter),
1069 },
1070 output,
1071 });
1072 }
1073 let bound = match op.id() {
1074 token::T_TOPK | token::T_BOTTOMK => BoundVectorOp::TopK {
1075 k: constant_argument(&name, param, 0)?,
1076 top: op.id() == token::T_TOPK,
1077 group,
1078 },
1079 token::T_LIMITK => BoundVectorOp::LimitK {
1080 k: constant_argument(&name, param, 0)?,
1081 group,
1082 },
1083 // `limit_ratio` keeps whole series by their label hash, so a grouping changes nothing.
1084 token::T_LIMIT_RATIO => BoundVectorOp::LimitRatio {
1085 ratio: constant_argument(&name, param, 0)?,
1086 },
1087 _ => {
1088 let PromExpr::StringLiteral(StringLiteral { val }) = unparen(param) else {
1089 return Err(not_implemented(&format!(
1090 "the aggregate `{op}` in `{aggregate}`, whose label `{param}` is not a string \
1091 literal"
1092 )));
1093 };
1094 BoundVectorOp::CountValues {
1095 label: Arc::from(val.as_str()),
1096 group,
1097 }
1098 }
1099 };
1100 vector_call(context, &name, bound, expr)
1101}
1102
1103/// How a `by` or `without` modifier identifies a group, in the tree's own terms.
1104///
1105/// The labels keep the order they were written in: a grouping is a set, and the tree records the
1106/// query rather than a key it derived from one.
1107fn grouping(modifier: Option<&LabelModifier>) -> Grouping {
1108 /// The written labels, as the tree stores them.
1109 fn labels(labels: &[String]) -> Arc<[Arc<str>]> {
1110 labels
1111 .iter()
1112 .map(|label| Arc::<str>::from(label.as_str()))
1113 .collect()
1114 }
1115 match modifier {
1116 // No modifier and `by()` ask for the same grouping: no label is kept, so every series of the
1117 // input falls into one group.
1118 None => Grouping::By(Arc::new([])),
1119 Some(LabelModifier::Include(by)) => Grouping::By(labels(&by.labels)),
1120 Some(LabelModifier::Exclude(without)) => Grouping::Without(labels(&without.labels)),
1121 }
1122}
1123
1124/// Compiles `timestamp`, projecting selected source times for a selector and evaluation times for
1125/// an already evaluated vector.
1126fn timestamp_call(context: &Context, args: &[Box<PromExpr>]) -> Result<NativeNode> {
1127 if args.len() != 1 {
1128 return Err(not_implemented("timestamp expects one argument"));
1129 }
1130 let argument = unparen(&args[0]);
1131 if argument.value_type() != ValueType::Vector {
1132 return Err(not_implemented("timestamp argument is not a vector"));
1133 }
1134 if let PromExpr::VectorSelector(selector) = argument {
1135 return instant_selection_of(context, selector, InstantValue::Timestamp);
1136 }
1137 let input = compile_expr(context, argument)?;
1138 let NativeType::Samples(schema) = &input.output else {
1139 return Err(not_implemented("timestamp argument is not a vector"));
1140 };
1141 if schema.fields.len() != 1 {
1142 return Err(not_implemented(
1143 "timestamp() over a multi-value input is not supported natively",
1144 ));
1145 }
1146 let output = input.output.clone();
1147 Ok(NativeNode {
1148 expr: NativeExpr::Timestamp {
1149 input: Box::new(input),
1150 },
1151 output,
1152 })
1153}
1154
1155/// Compiles `info(v[, {selector}])` as its base `v` and the instant selection of the info series it
1156/// reads.
1157///
1158/// The info series are selected the way Prometheus' `fetchInfoSeries` and `evalSeries` select
1159/// them: by the info metric's name and the data matchers, at the reference time the selectors of
1160/// `v` share ([`info_input`]), with the statement's lookback. Which of them a base series matches by
1161/// its identifying labels is the kernel's.
1162fn info_call(context: &Context, args: &[Box<PromExpr>]) -> Result<NativeNode> {
1163 let InfoInput { selector, kernel } = info_input(context.stmt, args)?;
1164 let base = compile_expr(context, &args[0])?;
1165 if base
1166 .output
1167 .samples()
1168 .is_none_or(|schema| schema.eval_grid.is_none())
1169 {
1170 return Err(DataFusionError::Internal(format!(
1171 "info's first argument `{}` compiled to something other than an evaluated vector: the \
1172 parser only accepts a vector there",
1173 args[0]
1174 )));
1175 }
1176 let info = instant_selection_of(context, &selector, InstantValue::InfoTimestamp)?;
1177 let fields = info
1178 .output
1179 .samples()
1180 .map_or(0, |schema| schema.fields.len());
1181 // Prometheus reads one sample per info series and point, and the existing planner has no
1182 // `info` to follow for several fields.
1183 if fields != 1 {
1184 return Err(not_implemented(&format!(
1185 "info over the info metric `{selector}` with {fields} fields: an info series is read as \
1186 one field"
1187 )));
1188 }
1189 let output = base.output.clone();
1190 Ok(NativeNode {
1191 expr: NativeExpr::Info {
1192 base: Box::new(base),
1193 info: Box::new(info),
1194 selector: kernel,
1195 },
1196 output,
1197 })
1198}
1199
1200/// The info series `info(v[, {selector}])` reads, as a selector, and the selector its kernel
1201/// combines by.
1202pub(crate) struct InfoInput {
1203 /// The info metric with the data matchers, at the reference time the selectors of `v` share.
1204 pub selector: VectorSelector,
1205 pub kernel: InfoSelector,
1206}
1207
1208/// Splits the arguments of `info` into the selector of its info series and the kernel's selector.
1209///
1210/// The compiler binds the selector as the call's last input and the planner prepares a scan for it
1211/// at the same position, so both read it here. One info metric is one table, so the name has to be
1212/// `target_info` (no name matcher) or one `__name__="..."`: a regular expression or a negative
1213/// matcher can select several tables. `__field__`, `__schema__` and `__database__` choose what a
1214/// selector reads rather than match a label, which Prometheus would read them as, so they are
1215/// refused too.
1216pub(crate) fn info_input(stmt: &EvalStmt, args: &[Box<PromExpr>]) -> Result<InfoInput> {
1217 let (base, labels) = match args {
1218 [base] => (base, None),
1219 [base, labels] => (base, Some(labels)),
1220 _ => {
1221 return Err(not_implemented(&format!(
1222 "a call to `info` with {} argument(s)",
1223 args.len()
1224 )));
1225 }
1226 };
1227 let matchers: &[Matcher] = match labels.map(|labels| labels.as_ref()) {
1228 None => &[],
1229 Some(PromExpr::VectorSelector(VectorSelector {
1230 name: None,
1231 matchers,
1232 offset: None,
1233 at: None,
1234 })) if matchers.or_matchers.is_empty() => &matchers.matchers,
1235 Some(other) => {
1236 return Err(not_implemented(&format!(
1237 "`info` whose second argument `{other}` is not one label selector without a name \
1238 or modifiers"
1239 )));
1240 }
1241 };
1242 let (names, data): (Vec<&Matcher>, Vec<&Matcher>) = matchers
1243 .iter()
1244 .partition(|matcher| matcher.name == "__name__");
1245 let metric = match names.as_slice() {
1246 [] => "target_info".to_string(),
1247 [name] if name.op == ParserMatchOp::Equal => name.value.clone(),
1248 _ => {
1249 return Err(not_implemented(
1250 "`info` over the info metrics a regular expression, a negative matcher or several \
1251 `__name__` matchers select, which can be several tables",
1252 ));
1253 }
1254 };
1255 if data.iter().any(|matcher| {
1256 matches!(
1257 matcher.name.as_str(),
1258 "__field__" | "__schema__" | "__database__"
1259 )
1260 }) {
1261 return Err(not_implemented(
1262 "`info` with a `__field__`, `__schema__` or `__database__` matcher, which selects \
1263 what is read rather than a data label",
1264 ));
1265 }
1266 let (at, offset_ms) = info_reference(stmt, base)?;
1267 let offset = match offset_ms {
1268 0 => None,
1269 ms if ms > 0 => Some(Offset::Pos(Duration::from_millis(ms.unsigned_abs()))),
1270 ms => Some(Offset::Neg(Duration::from_millis(ms.unsigned_abs()))),
1271 };
1272 let kernel = InfoSelector {
1273 name_matchers: names
1274 .iter()
1275 .map(|matcher| (match_op(&matcher.op), Arc::from(matcher.value.as_str())))
1276 .collect(),
1277 data_labels: data
1278 .iter()
1279 .map(|matcher| Arc::from(matcher.name.as_str()))
1280 .collect(),
1281 keep_unmatched: data.iter().all(|matcher| matcher.is_match("")),
1282 };
1283 Ok(InfoInput {
1284 selector: VectorSelector {
1285 name: Some(metric),
1286 matchers: Matchers::new(data.into_iter().cloned().collect()),
1287 offset,
1288 at,
1289 },
1290 kernel,
1291 })
1292}
1293
1294/// The `@` anchor and offset the info series are selected at: those of the first selector of
1295/// `expr` when every vector-producing path of it reaches a selector with the same effective
1296/// reference time, and none otherwise, as Prometheus `infoSeriesSelectTimestampAndOffset` decides.
1297///
1298/// A selector inside subqueries adds their offsets until one of them anchors it with `@`. A path
1299/// that produces a vector without a selector, such as `vector(1)`, is evaluated at the step itself,
1300/// so it leaves no shared reference.
1301fn info_reference(stmt: &EvalStmt, expr: &PromExpr) -> Result<(Option<AtModifier>, i64)> {
1302 #[derive(Default)]
1303 struct Walk {
1304 /// The first selector's anchor, its resolved time and its offset.
1305 first: Option<(Option<AtModifier>, Option<i64>, i64)>,
1306 uniform: bool,
1307 reference_free: bool,
1308 }
1309
1310 fn inspect<'a>(
1311 stmt: &EvalStmt,
1312 expr: &'a PromExpr,
1313 subqueries: &mut Vec<&'a SubqueryExpr>,
1314 walk: &mut Walk,
1315 ) -> Result<bool> {
1316 if !matches!(expr.value_type(), ValueType::Vector | ValueType::Matrix) {
1317 return Ok(false);
1318 }
1319 let selector = match expr {
1320 PromExpr::VectorSelector(selector) => Some(selector),
1321 PromExpr::MatrixSelector(MatrixSelector { vs, .. }) => Some(vs),
1322 _ => None,
1323 };
1324 if let Some(selector) = selector {
1325 let mut at = selector.at.clone();
1326 let mut offset = selector_offset_ms(&selector.offset)?;
1327 for subquery in subqueries.iter().rev() {
1328 if at.is_some() {
1329 break;
1330 }
1331 offset = offset
1332 .checked_add(selector_offset_ms(&subquery.offset)?)
1333 .ok_or_else(|| DataFusionError::Plan("selector offset overflows".into()))?;
1334 at = subquery.at.clone();
1335 }
1336 let at_ms = selector_anchor_ms(&at, stmt)?;
1337 match &walk.first {
1338 None => walk.first = Some((at, at_ms, offset)),
1339 Some((_, first_at, first_offset)) => {
1340 let same = match (first_at, at_ms) {
1341 (None, None) => *first_offset == offset,
1342 (Some(first_at), Some(at)) => {
1343 i128::from(*first_at) - i128::from(*first_offset)
1344 == i128::from(at) - i128::from(offset)
1345 }
1346 _ => false,
1347 };
1348 walk.uniform &= same;
1349 }
1350 }
1351 return Ok(true);
1352 }
1353 let children: Vec<&PromExpr> = match expr {
1354 PromExpr::Paren(paren) => vec![&paren.expr],
1355 PromExpr::Unary(unary) => vec![&unary.expr],
1356 PromExpr::Binary(binary) => vec![&binary.lhs, &binary.rhs],
1357 PromExpr::Aggregate(aggregate) => aggregate
1358 .param
1359 .iter()
1360 .chain([&aggregate.expr])
1361 .map(|child| child.as_ref())
1362 .collect(),
1363 // The second argument of a nested `info` is selector syntax, not a vector it evaluates.
1364 PromExpr::Call(call) if call.func.name == "info" => call
1365 .args
1366 .args
1367 .iter()
1368 .take(1)
1369 .map(|arg| arg.as_ref())
1370 .collect(),
1371 PromExpr::Call(call) => call.args.args.iter().map(|arg| arg.as_ref()).collect(),
1372 PromExpr::Subquery(subquery) => {
1373 subqueries.push(subquery);
1374 let found = inspect(stmt, &subquery.expr, subqueries, walk);
1375 subqueries.pop();
1376 let found = found?;
1377 walk.reference_free |= !found;
1378 return Ok(found);
1379 }
1380 other => {
1381 return Err(not_implemented(&format!(
1382 "`info` over `{other}`, whose reference time is not derived here"
1383 )));
1384 }
1385 };
1386 let mut found = false;
1387 for child in children {
1388 found |= inspect(stmt, child, subqueries, walk)?;
1389 }
1390 walk.reference_free |= !found;
1391 Ok(found)
1392 }
1393
1394 let mut walk = Walk {
1395 uniform: true,
1396 ..Default::default()
1397 };
1398 inspect(stmt, expr, &mut Vec::new(), &mut walk)?;
1399 match walk.first {
1400 Some((at, _, offset)) if walk.uniform && !walk.reference_free => Ok((at, offset)),
1401 _ => Ok((None, 0)),
1402 }
1403}
1404
1405fn match_op(op: &ParserMatchOp) -> MatchOp {
1406 match op {
1407 ParserMatchOp::Equal => MatchOp::Equal,
1408 ParserMatchOp::NotEqual => MatchOp::NotEqual,
1409 ParserMatchOp::Re(_) => MatchOp::Regex,
1410 ParserMatchOp::NotRe(_) => MatchOp::NotRegex,
1411 }
1412}
1413
1414/// Compiles a range, pointwise, histogram or label function call.
1415///
1416/// The name lists are disjoint, and a range function is decided first because it binds its own
1417/// window rather than its argument's value. A name in neither list is refused here, which is where
1418/// the difference between "this compiler cannot fold this function" and "this name means nothing"
1419/// is still visible.
1420fn compile_call(context: &Context, call: &Call) -> Result<NativeNode> {
1421 if call.func.name == "timestamp" {
1422 return timestamp_call(context, &call.args.args);
1423 }
1424 if call.func.name == "info" {
1425 return info_call(context, &call.args.args);
1426 }
1427 // `absent_over_time` reads a matrix where `absent` reads a vector, so it cannot ride the vector
1428 // path below: the operation it binds is `absent`'s own, over a presence read of the window.
1429 if call.func.name == ABSENT_OVER_TIME {
1430 return absent_over_time_call(context, &call.args.args);
1431 }
1432 let Call { func, args } = call;
1433 if let Some(node) = scalar_call(context, func.name, &args.args)? {
1434 return Ok(node);
1435 }
1436 if let Some(signature) = range_signature(func.name) {
1437 return window_call(context, func.name, signature, &args.args);
1438 }
1439 if let Some(node) = parameterized_histogram_call(context, func.name, &args.args)? {
1440 return Ok(node);
1441 }
1442 if let Some((op, vector)) = vector_op(func.name, &args.args)? {
1443 return vector_call(context, func.name, op, vector);
1444 }
1445 if let Some(node) = scalar_function_call(context, func.name, &args.args)? {
1446 return Ok(node);
1447 }
1448 // The name is looked up before the call's arguments are read, so a name this compiler has no
1449 // kernel for is refused as such whichever arguments it was given, and the rejection names the
1450 // name rather than describing a vector it never wrote. `pi()` does not reach here: it is a
1451 // constant the statement itself decides, so it already folded in `compile_expr`.
1452 if let Some(node) = parameterized_call(context, func.name, &args.args)? {
1453 return Ok(node);
1454 }
1455 if let Some((op, vector)) = math_op(func.name, &args.args)? {
1456 return map_call(context, func.name, MapOp::Math(op), vector);
1457 }
1458 if let Some(function) = histogram_function(func.name) {
1459 let [vector] = args.args.as_slice() else {
1460 return Err(not_implemented(&format!(
1461 "a call to `{}` with {} argument(s), where it takes its vector",
1462 func.name,
1463 args.args.len()
1464 )));
1465 };
1466 return map_call(context, func.name, MapOp::Histogram(function), vector);
1467 }
1468 if let Some((rewrite, vector)) = label_rewrite(func.name, &args.args)? {
1469 return map_call(context, func.name, MapOp::Label(Arc::new(rewrite)), vector);
1470 }
1471 Err(not_implemented(&format!(
1472 "a call to `{}`, which has no native kernel",
1473 func.name
1474 )))
1475}
1476
1477/// Binds `time()`, `vector(s)` and a date function called without an argument, or
1478/// returns `None` when the call is none of them.
1479///
1480/// A date function without an argument is `f(vector(time()))` in Prometheus, but it reads the
1481/// evaluation timestamp truncated to whole seconds rather than the float `time()` reports, so it is
1482/// bound as the evaluation time's own date and then handed on as a vector.
1483fn scalar_call(
1484 context: &Context,
1485 name: &str,
1486 args: &[Box<PromExpr>],
1487) -> Result<Option<NativeNode>> {
1488 let grid = || Arc::clone(&context.grid);
1489 let eval_time = |date| NativeNode {
1490 expr: NativeExpr::EvalTime { date },
1491 output: NativeType::Scalar(grid()),
1492 };
1493 let node = match (name, args) {
1494 ("time", []) => eval_time(None),
1495 ("vector", [scalar]) => vector_of(
1496 compile_expr(context, scalar)?,
1497 &grid(),
1498 &context.value_field,
1499 ),
1500 ("scalar", [vector]) => {
1501 if vector.value_type() != ValueType::Vector {
1502 return Err(not_implemented("scalar() requires a vector argument"));
1503 }
1504 let input = compile_expr(context, vector)?;
1505 let NativeType::Samples(schema) = &input.output else {
1506 return Err(not_implemented("scalar() requires an evaluated vector"));
1507 };
1508 let Some(input_grid) = schema.eval_grid.clone() else {
1509 return Err(not_implemented("scalar() requires an evaluated vector"));
1510 };
1511 NativeNode {
1512 expr: NativeExpr::ScalarOf {
1513 input: Box::new(input),
1514 },
1515 output: NativeType::Scalar(input_grid),
1516 }
1517 }
1518 (name, []) => match math_signature(name) {
1519 Some(MathSignature::Unary(MathOp::Date(date))) => {
1520 vector_of(eval_time(Some(date)), &grid(), &context.value_field)
1521 }
1522 _ => return Ok(None),
1523 },
1524 _ => return Ok(None),
1525 };
1526 Ok(Some(node))
1527}
1528
1529/// Binds `max_of(a, b)` or `min_of(a, b)`, whose arguments are both scalars, or returns `None` for
1530/// any other call.
1531///
1532/// Prometheus types both as `(scalar, scalar) -> scalar`, so what the call wrote is two scalar
1533/// expressions rather than a vector and its parameters: the first argument is the map's input and
1534/// the second is its one parameter, and the answer is a scalar on the grid they are evaluated on. A
1535/// constant argument is bound as the number it folds to ([`compile_expr`]); as the input, that
1536/// number is the one chunk the map materializes, so a call of two constants reads no input at all.
1537/// A vector argument is refused here: it is not a shape the kernel could compute, and a function of
1538/// two scalars has no vector form to fold.
1539fn scalar_function_call(
1540 context: &Context,
1541 name: &str,
1542 args: &[Box<PromExpr>],
1543) -> Result<Option<NativeNode>> {
1544 let op = match name {
1545 "max_of" => ParameterizedOp::MaxOf,
1546 "min_of" => ParameterizedOp::MinOf,
1547 _ => return Ok(None),
1548 };
1549 let [left, right] = args else {
1550 return Err(not_implemented(&format!(
1551 "a call to `{name}` with {} argument(s), where it takes two scalars",
1552 args.len()
1553 )));
1554 };
1555 for argument in [left, right] {
1556 if argument.value_type() != ValueType::Scalar {
1557 return Err(not_implemented(&format!(
1558 "a call to `{name}` whose argument `{argument}` is a {}, where the function takes \
1559 scalars",
1560 argument.value_type()
1561 )));
1562 }
1563 }
1564 let input = compile_expr(context, left)?;
1565 let output_grid = match &input.output {
1566 NativeType::Scalar(grid) => Arc::clone(grid),
1567 // A scalar expression compiles to a scalar, so this is a backstop rather than a shape a
1568 // statement reaches.
1569 _ => {
1570 return Err(not_implemented(&format!(
1571 "a call to `{name}` whose argument `{left}` does not evaluate to a scalar"
1572 )));
1573 }
1574 };
1575 let parameter = compile_expr(context, right)?;
1576 match ¶meter.output {
1577 NativeType::Scalar(grid) if grid.spec() == output_grid.spec() => {}
1578 NativeType::Scalar(_) => {
1579 return Err(not_implemented(&format!(
1580 "a call to `{name}` whose arguments are evaluated on grids that differ"
1581 )));
1582 }
1583 _ => {
1584 return Err(not_implemented(&format!(
1585 "a call to `{name}` whose argument `{right}` does not evaluate to a scalar"
1586 )));
1587 }
1588 }
1589 Ok(Some(NativeNode {
1590 expr: NativeExpr::ParameterizedMap {
1591 input: Box::new(input),
1592 op,
1593 parameters: vec![parameter],
1594 },
1595 output: NativeType::Scalar(output_grid),
1596 }))
1597}
1598
1599/// Binds `round`, `clamp`, `clamp_min` or `clamp_max` whose parameters are not all constants, or
1600/// returns `None` for any other call. Prometheus reads each parameter at every step, so each one is
1601/// bound as the scalar node it compiles to; with constant parameters the call is a [`MathOp`].
1602fn parameterized_call(
1603 context: &Context,
1604 name: &str,
1605 args: &[Box<PromExpr>],
1606) -> Result<Option<NativeNode>> {
1607 let op = match name {
1608 "round" => ParameterizedOp::Round,
1609 "clamp" => ParameterizedOp::Clamp,
1610 "clamp_min" => ParameterizedOp::ClampMin,
1611 "clamp_max" => ParameterizedOp::ClampMax,
1612 _ => return Ok(None),
1613 };
1614 let Some((vector, parameters)) = args.split_first() else {
1615 return Ok(None);
1616 };
1617 if parameters.len() != op.arity()
1618 || parameters
1619 .iter()
1620 .all(|parameter| constant_value(parameter).is_some())
1621 {
1622 return Ok(None);
1623 }
1624 if vector.value_type() != ValueType::Vector {
1625 return Err(not_implemented(&format!(
1626 "a call to `{name}` whose first argument is `{vector}`, which is a {}, where the \
1627 function takes a vector",
1628 vector.value_type()
1629 )));
1630 }
1631 let input = compile_expr(context, vector)?;
1632 let parameters = parameters
1633 .iter()
1634 .map(|parameter| compile_expr(context, parameter))
1635 .collect::<Result<Vec<_>>>()?;
1636 let output = input.output.clone();
1637 Ok(Some(NativeNode {
1638 expr: NativeExpr::ParameterizedMap {
1639 input: Box::new(input),
1640 op,
1641 parameters,
1642 },
1643 output,
1644 }))
1645}
1646
1647/// `vector(s)`: the scalar `input` as one series without labels, under one value field.
1648fn vector_of(input: NativeNode, grid: &Arc<EvalGrid>, value_field: &str) -> NativeNode {
1649 NativeNode {
1650 expr: NativeExpr::VectorOf {
1651 input: Box::new(input),
1652 },
1653 output: NativeType::Samples(Arc::new(SeriesSchema {
1654 fields: Arc::from([FieldSpec {
1655 name: Arc::from(value_field),
1656 }]),
1657 eval_grid: Some(Arc::clone(grid)),
1658 })),
1659 }
1660}
1661
1662/// The field `vector(s)` reports its value under: a scalar names no column, so it is the planner's
1663/// default value column.
1664const VECTOR_FIELD: &str = "value";
1665
1666/// Binds a range function over the matrix it is given, and the window that matrix opens.
1667///
1668/// Where the matrix sits is the signature's, not a convention: `quantile_over_time(0.9, x[5m])` writes
1669/// its constant before the matrix, while `predict_linear(x[5m], 300)` and
1670/// `double_exponential_smoothing(x[5m], 0.5, 0.1)` write theirs after it, and a function with no
1671/// constants at all reads the matrix first. [`RangeSignature::selector_index`] is that position, and
1672/// everything else the call wrote is a constant — which keeps the position it was written at, so a
1673/// rejection names the argument the query wrote rather than the constant's offset among the constants.
1674///
1675/// The matrix is either shape: a range selector, which reads raw samples, or a subquery, which
1676/// evaluates its own expression on a grid of its own.
1677fn window_call(
1678 context: &Context,
1679 name: &str,
1680 signature: RangeSignature,
1681 args: &[Box<PromExpr>],
1682) -> Result<NativeNode> {
1683 // The count is the signature's, so the rejection names what this function takes rather than
1684 // what one argument happens to be.
1685 let expected = signature.arity();
1686 if args.len() != expected {
1687 return Err(not_implemented(&format!(
1688 "a call to `{name}` with {} argument(s), where it takes {expected}: {}",
1689 args.len(),
1690 signature.arguments()
1691 )));
1692 }
1693 // The matrix sits where the signature says it does, and everything else is a constant. Reading it
1694 // by position rather than by "the last argument" is what lets `predict_linear(x[5m], 300)` and
1695 // `quantile_over_time(0.9, x[5m])` share one path.
1696 let selector_index = signature.selector_index();
1697 // The selector stays in its original argument position for signature binding, while either
1698 // matrix form can provide the samples folded by the range function.
1699 let argument = &args[selector_index];
1700 let function = signature.bind(name, args)?;
1701 match unparen(argument) {
1702 PromExpr::MatrixSelector(MatrixSelector { vs, range }) => {
1703 window_selection(context, function, vs, range)
1704 }
1705 PromExpr::Subquery(subquery) => subquery_window(context, name, function, subquery),
1706 other => Err(not_implemented(&format!(
1707 "a call to `{name}` whose matrix is `{other}`, where it has to be a range \
1708 selector like `x[5m]` or a subquery like `x[5m:1m]`"
1709 ))),
1710 }
1711}
1712
1713/// Wraps `op` over the value of `vector`, which is the first argument of a math, native histogram
1714/// or label function.
1715///
1716/// The output is the input's own type: a pointwise function moves no value to another grid point
1717/// and reports one value per field it was given, so the map's schema is the input's allocation
1718/// rather than a copy that merely agrees with it. [`NativeTree::validate`] does not require that
1719/// sharing: it compares the map's grid with its input's by [`EvalGrid::spec`] and its field count
1720/// with its input's, so a map that allocated an equal grid of its own would validate the same way.
1721/// The only comparison by identity is an input node's, whose output has to be the very binding it
1722/// was bound to.
1723fn map_call(context: &Context, name: &str, op: MapOp, vector: &PromExpr) -> Result<NativeNode> {
1724 // A map is pointwise over a vector, so the function's first argument has to be one. The parser
1725 // checks the same thing and the tree's validation checks the compiled input's type again, but
1726 // neither can name the argument the client wrote: this is the check that can.
1727 if vector.value_type() != ValueType::Vector {
1728 return Err(not_implemented(&format!(
1729 "a call to `{name}` whose first argument is `{vector}`, which is a {}, where the \
1730 function takes a vector",
1731 vector.value_type()
1732 )));
1733 }
1734 let input = compile_expr(context, vector)?;
1735 let output = input.output.clone();
1736 Ok(NativeNode {
1737 expr: NativeExpr::Map {
1738 input: Box::new(input),
1739 op: BoundMap {
1740 ops: Arc::from([op]),
1741 },
1742 },
1743 output,
1744 })
1745}
1746
1747/// Wraps the vector operation `op` over the value of `vector`, which keeps its type as a map does.
1748fn vector_call(
1749 context: &Context,
1750 name: &str,
1751 op: BoundVectorOp,
1752 vector: &PromExpr,
1753) -> Result<NativeNode> {
1754 if vector.value_type() != ValueType::Vector {
1755 return Err(not_implemented(&format!(
1756 "a call to `{name}` whose vector argument is `{vector}`, which is a {}, where the \
1757 function takes a vector",
1758 vector.value_type()
1759 )));
1760 }
1761 let input = compile_expr(context, vector)?;
1762 let output = input.output.clone();
1763 Ok(NativeNode {
1764 expr: NativeExpr::Vector {
1765 input: Box::new(input),
1766 op,
1767 },
1768 output,
1769 })
1770}
1771
1772/// Compiles a classic histogram call with at least one varying scalar argument.
1773fn parameterized_histogram_call(
1774 context: &Context,
1775 name: &str,
1776 arguments: &[Box<PromExpr>],
1777) -> Result<Option<NativeNode>> {
1778 if !matches!(name, "histogram_quantile" | "histogram_fraction") {
1779 return Ok(None);
1780 }
1781 let Some((vector, args)) = arguments.split_last() else {
1782 return Ok(None);
1783 };
1784 let expected = if name == "histogram_quantile" { 1 } else { 2 };
1785 if args.len() != expected || args.iter().all(|arg| constant_value(arg).is_some()) {
1786 return Ok(None);
1787 }
1788 if vector.value_type() != ValueType::Vector {
1789 return Err(not_implemented(&format!(
1790 "a call to `{name}` whose vector argument is `{vector}` is not a vector"
1791 )));
1792 }
1793 let function = if name == "histogram_quantile" {
1794 HistogramFunction::Quantile(
1795 args.first()
1796 .and_then(|arg| constant_value(arg))
1797 .unwrap_or(0.0),
1798 )
1799 } else {
1800 HistogramFunction::Fraction {
1801 lower: args
1802 .first()
1803 .and_then(|arg| constant_value(arg))
1804 .unwrap_or(0.0),
1805 upper: args
1806 .get(1)
1807 .and_then(|arg| constant_value(arg))
1808 .unwrap_or(0.0),
1809 }
1810 };
1811 let input = compile_expr(context, vector)?;
1812 let output = input.output.clone();
1813 let parameters = args
1814 .iter()
1815 .map(|arg| compile_expr(context, arg))
1816 .collect::<Result<Vec<_>>>()?;
1817 Ok(Some(NativeNode {
1818 expr: NativeExpr::ParameterizedHistogram {
1819 input: Box::new(input),
1820 op: BoundVectorOp::Histogram(function),
1821 parameters,
1822 },
1823 output,
1824 }))
1825}
1826
1827/// The PromQL name of `absent_over_time`, which is not a range function here: it reads a matrix but
1828/// answers with `absent`'s vector operation rather than with one value per series.
1829const ABSENT_OVER_TIME: &str = "absent_over_time";
1830
1831/// The range function `absent_over_time` folds a window with, to learn whether a series has a sample
1832/// in it.
1833///
1834/// `absent` answers at every point its input holds no series at, so the matrix has to become one
1835/// series per series holding a sample: a range function at all, rather than a value no series
1836/// states. Which range function is therefore a question of which points a window reports, and
1837/// `present_over_time` and `last_over_time` report the same ones — a window with at least one
1838/// sample. The name is what separates them: `present_over_time` drops the metric name, and a
1839/// selector written without one is discovered as one source per metric, so two metrics carrying the
1840/// same ordinary labels would arrive at the fold as one label set. The window refuses two values of
1841/// one label set at one point, because everything above it reads them as one series: the query
1842/// would fail where Prometheus answers with the empty vector. Keeping the name keeps those two
1843/// series apart, and `absent` reads presence alone, so the value this fold computes is not part of
1844/// the answer.
1845const PRESENCE_FOLD: RangeFunction = RangeFunction::LastOverTime;
1846
1847/// Binds `absent_over_time(m[d])` into `absent`'s own vector operation, over a presence read of the
1848/// window.
1849///
1850/// Both halves are `absent`'s: the labels come from the matrix selector's matchers exactly as
1851/// `absent` derives them from a vector selector's, and the operation tests whether its input holds
1852/// a series at each grid point. What differs is only where that input comes from — a matrix folds a
1853/// window rather than selecting an instant — which is why the call is bound here and not by
1854/// [`vector_call`]: `absent_over_time` reads a matrix, and nothing in it is a vector expression the
1855/// recursion could compile.
1856///
1857/// The existing plan answers this call per series with a UDF, which needs a metric name to read a
1858/// table from; a selector written without one names its metrics only by the labels that pick them,
1859/// which is exactly the shape `absent_over_time` is asked for when nothing matches.
1860fn absent_over_time_call(context: &Context, arguments: &[Box<PromExpr>]) -> Result<NativeNode> {
1861 let [matrix] = arguments else {
1862 return Err(not_implemented(&format!(
1863 "a call to `{ABSENT_OVER_TIME}` with {} argument(s), where it takes one matrix",
1864 arguments.len()
1865 )));
1866 };
1867 let labels = absent_labels_of(matrix)?;
1868 let input = match unparen(matrix) {
1869 PromExpr::MatrixSelector(MatrixSelector { vs, range }) => {
1870 window_selection(context, PRESENCE_FOLD, vs, range)?
1871 }
1872 PromExpr::Subquery(subquery) => {
1873 subquery_window(context, ABSENT_OVER_TIME, PRESENCE_FOLD, subquery)?
1874 }
1875 other => {
1876 return Err(not_implemented(&format!(
1877 "a call to `{ABSENT_OVER_TIME}` whose matrix is `{other}`, where it has to be a \
1878 range selector like `x[5m]` or a subquery like `x[5m:1m]`"
1879 )));
1880 }
1881 };
1882 let output = input.output.clone();
1883 Ok(NativeNode {
1884 expr: NativeExpr::Vector {
1885 input: Box::new(input),
1886 op: BoundVectorOp::Absent { labels },
1887 },
1888 output,
1889 })
1890}
1891
1892/// The vector operation a sort, `absent` or a classic histogram function binds, and the vector it reads,
1893/// or `None` when `name` is none of them.
1894fn vector_op<'a>(
1895 name: &str,
1896 arguments: &'a [Box<PromExpr>],
1897) -> Result<Option<(BoundVectorOp, &'a PromExpr)>> {
1898 let order = match name {
1899 "sort" => Some(SortOrder::Asc),
1900 "sort_desc" => Some(SortOrder::Desc),
1901 "sort_by_label" | "sort_by_label_desc" => None,
1902 "histogram_quantile" | "histogram_fraction" => {
1903 let Some((vector, constants)) = arguments.split_last() else {
1904 return Err(not_implemented(&format!(
1905 "a call to `{name}` with no argument"
1906 )));
1907 };
1908 let function = match constants {
1909 [quantile] if name == "histogram_quantile" => {
1910 HistogramFunction::Quantile(constant_argument(name, quantile, 0)?)
1911 }
1912 [lower, upper] if name == "histogram_fraction" => HistogramFunction::Fraction {
1913 lower: constant_argument(name, lower, 0)?,
1914 upper: constant_argument(name, upper, 1)?,
1915 },
1916 _ => {
1917 return Err(not_implemented(&format!(
1918 "a call to `{name}` with {} argument(s)",
1919 arguments.len()
1920 )));
1921 }
1922 };
1923 return Ok(Some((BoundVectorOp::Histogram(function), vector)));
1924 }
1925 "absent" => {
1926 let [vector] = arguments else {
1927 return Err(not_implemented(&format!(
1928 "a call to `absent` with {} argument(s)",
1929 arguments.len()
1930 )));
1931 };
1932 let labels = absent_labels_of(vector)?;
1933 return Ok(Some((BoundVectorOp::Absent { labels }, vector)));
1934 }
1935 _ => return Ok(None),
1936 };
1937 let Some((vector, strings)) = arguments.split_first() else {
1938 return Err(not_implemented(&format!(
1939 "a call to `{name}` with no argument"
1940 )));
1941 };
1942 let order = match order {
1943 Some(order) if strings.is_empty() => order,
1944 Some(_) => {
1945 return Err(not_implemented(&format!(
1946 "a call to `{name}` with {} argument(s)",
1947 arguments.len()
1948 )));
1949 }
1950 None => {
1951 let labels = strings
1952 .iter()
1953 .map(|argument| match unparen(argument) {
1954 PromExpr::StringLiteral(StringLiteral { val }) => Ok(Arc::from(val.as_str())),
1955 other => Err(not_implemented(&format!(
1956 "a call to `{name}` whose argument `{other}` is not a string literal"
1957 ))),
1958 })
1959 .collect::<Result<Vec<_>>>()?;
1960 if name == "sort_by_label" {
1961 SortOrder::ByLabel(labels)
1962 } else {
1963 SortOrder::ByLabelDesc(labels)
1964 }
1965 }
1966 };
1967 Ok(Some((BoundVectorOp::Sort(order), vector)))
1968}
1969
1970/// The labels `absent(expr)` and `absent_over_time(m[d])` answer with, as Prometheus
1971/// `createLabelsForAbsentFunction` derives them: from the matchers of a vector or range selector,
1972/// and none for any other expression.
1973///
1974/// Both selectors carry the same matchers, and Prometheus derives the labels from them the same way
1975/// in either position, so the range selector of `absent_over_time` reads exactly as the vector
1976/// selector of `absent` does.
1977///
1978/// `__field__`, `__schema__` and `__database__` choose what is read rather than match a label, so
1979/// they are not labels of the answer, as in the existing planner.
1980fn absent_labels_of(expr: &PromExpr) -> Result<SeriesLabels> {
1981 let (selector, alternatives) = match unparen(expr) {
1982 PromExpr::VectorSelector(selector) => (&selector.matchers, &selector.matchers.or_matchers),
1983 PromExpr::MatrixSelector(MatrixSelector { vs, .. }) => {
1984 (&vs.matchers, &vs.matchers.or_matchers)
1985 }
1986 _ => return absent_labels(&[]),
1987 };
1988 if !alternatives.is_empty() {
1989 return Err(not_implemented(&format!(
1990 "`absent` or `absent_over_time` over `{expr}`, whose matchers are alternatives"
1991 )));
1992 }
1993 let matchers = selector
1994 .matchers
1995 .iter()
1996 .filter(|matcher| {
1997 !matches!(
1998 matcher.name.as_str(),
1999 "__field__" | "__schema__" | "__database__"
2000 )
2001 })
2002 .map(|matcher| LabelMatcher {
2003 name: Arc::from(matcher.name.as_str()),
2004 op: match_op(&matcher.op),
2005 value: Arc::from(matcher.value.as_str()),
2006 matches_empty: matcher.is_match(""),
2007 })
2008 .collect::<Vec<_>>();
2009 absent_labels(&matchers)
2010}
2011
2012/// Binds `function` over the range selector `vs[range]` into a window over the raw input.
2013///
2014/// Both shapes reach this: the range, the offset, the anchor, the grid and the output are the same
2015/// whichever function reads them, so a parameterised function only decides *what* folds the window,
2016/// never *which* window is folded.
2017fn window_selection(
2018 context: &Context,
2019 function: RangeFunction,
2020 vs: &VectorSelector,
2021 range: &Duration,
2022) -> Result<NativeNode> {
2023 // An `@` anchor is step-invariant: every step folds the same samples, which the window's
2024 // `anchor_ms` tells `RangeEvaluator` to replay over the grid.
2025 let range_ms = range_millis(range.as_millis())?;
2026 let offset_ms = selector_offset_ms(&vs.offset)?;
2027 let anchor_ms = selector_anchor_ms(&vs.at, context.stmt)?;
2028 // The grid is the last thing built: a query refused above, or a window that cannot exist,
2029 // never pays for a grid nothing would read.
2030 let output_grid = Arc::clone(&context.grid);
2031
2032 let (grid_start_ms, grid_end_ms) = grid_endpoints(&output_grid)?;
2033 let (source_index, schema) = bind_selector(
2034 context,
2035 SelectorRequirement {
2036 metric: vs.name.clone(),
2037 matchers: vs.matchers.clone(),
2038 offset_ms,
2039 at_ms: anchor_ms,
2040 grid_start_ms,
2041 grid_end_ms,
2042 timing: SelectorTiming::Window { range_ms },
2043 },
2044 )?;
2045 let output = NativeType::Samples(Arc::new(SeriesSchema {
2046 fields: Arc::clone(&schema.fields),
2047 eval_grid: Some(Arc::clone(&output_grid)),
2048 }));
2049 let raw = NativeType::Samples(Arc::clone(&schema));
2050
2051 Ok(NativeNode {
2052 expr: NativeExpr::Window {
2053 input: Box::new(NativeNode {
2054 expr: NativeExpr::Input(BoundInput {
2055 output: raw.clone(),
2056 source_index,
2057 ordering: context.ordering,
2058 }),
2059 output: raw,
2060 }),
2061 op: BoundWindow {
2062 function,
2063 window: RangeWindow {
2064 range_ms,
2065 offset_ms,
2066 anchor_ms,
2067 modifier: None,
2068 },
2069 // The input is raw samples, so it has no grid of its own.
2070 input_grid: None,
2071 output_grid,
2072 },
2073 },
2074 output,
2075 })
2076}
2077
2078/// The step a subquery names when it names none, as in `x[5m:]`.
2079///
2080/// Prometheus falls back to the global evaluation interval, whose default is a minute, rather than to
2081/// the statement's own step. The existing planner folds the same default; the constant is restated
2082/// here because that one is private to the planner, and it is a Prometheus protocol constant rather
2083/// than a number either caller may choose.
2084const DEFAULT_SUBQUERY_STEP_MS: i64 = 60_000;
2085
2086/// The grid a subquery's inner expression is evaluated on, and the window that reads it.
2087///
2088/// Both halves of the native route need the same answer: the compiler binds the grid into the node,
2089/// where it tells the window which points its input was evaluated at, and the planner binds the tree
2090/// it compiles to the grid its rows carry. A second derivation would let the two disagree about the
2091/// default step or the conversion of the range, and a tree bound to a grid it was not compiled on
2092/// cannot be planned, so the numbers are derived here once.
2093pub(crate) struct SubqueryGrid {
2094 /// The interval the range function folds, and how far back from the anchor it reads.
2095 pub(crate) window: RangeWindow,
2096 /// The grid `subquery.expr` is evaluated on.
2097 pub(crate) grid: Arc<EvalGrid>,
2098}
2099
2100/// Derives the [`SubqueryGrid`] of `subquery`, whose outer statement is evaluated on `outer`.
2101///
2102/// The child grid is one point per `step` over the interval the subquery's window reads, which its
2103/// `@` anchor, offset and range decide; without an anchor it is the statement's own range. Every
2104/// number is converted checked, so a range or a step too large to name a millisecond is reported as
2105/// itself rather than wrapped into a different interval.
2106///
2107/// `None` when the anchored interval contains no step boundary, which names no evaluation point at
2108/// all. Declining is the caller's decision: the compiler reports the shape it cannot fold, while the
2109/// planner keeps the plan the existing path builds.
2110pub(crate) fn subquery_child_grid(
2111 stmt: &EvalStmt,
2112 outer: &EvalGrid,
2113 subquery: &SubqueryExpr,
2114) -> Result<Option<SubqueryGrid>> {
2115 // The anchor is resolved by the same function a range selector's is, so `start()`, `end()` and a
2116 // literal — including a negative one — mean the same thing in both shapes.
2117 let anchor_ms = selector_anchor_ms(&subquery.at, stmt)?;
2118 let range_ms = range_millis(subquery.range.as_millis())?;
2119 // A subquery step of zero names no evaluation point at all, so it is reported as its own value
2120 // rather than as an empty grid.
2121 let step_ms = match subquery.step {
2122 Some(step) => millis(step.as_millis()).ok_or_else(|| {
2123 DataFusionError::Plan(format!(
2124 "the subquery's step of {}ms is out of range",
2125 step.as_millis()
2126 ))
2127 })?,
2128 None => DEFAULT_SUBQUERY_STEP_MS,
2129 };
2130 if step_ms <= 0 {
2131 return Err(DataFusionError::Plan(format!(
2132 "the subquery's step is {step_ms}ms, and a step has to be longer than zero"
2133 )));
2134 }
2135 let offset_ms = selector_offset_ms(&subquery.offset)?;
2136 let window = RangeWindow {
2137 range_ms,
2138 offset_ms,
2139 anchor_ms,
2140 modifier: None,
2141 };
2142 let Some(spec) = subquery_grid(outer.spec(), window, step_ms)? else {
2143 return Ok(None);
2144 };
2145 // Keep subquery grids deferred: selector binding needs only their spec endpoints, not a
2146 // materialized timestamp vector proportional to the range.
2147 let grid = Arc::new(EvalGrid::try_deferred(spec).map_err(grid_error)?);
2148 Ok(Some(SubqueryGrid { window, grid }))
2149}
2150
2151/// Binds `function` over `subquery`, whose inner expression is evaluated on a grid of its own.
2152///
2153/// A range function folds a matrix, and PromQL writes a matrix two ways. A range selector reads raw
2154/// samples from the scan; a subquery builds one by evaluating an expression. That is why this node
2155/// declares `input_grid`: `rate(x[5m:1m])` samples `x` at one-minute steps over the five-minute
2156/// lookback, and the window folds those points rather than raw samples. The inner expression is
2157/// compiled against the subquery's grid for the same reason — a selector inside it has to land where
2158/// the window will read it.
2159///
2160/// An `@` anchor makes the subquery step-invariant: every output point reads the same interval,
2161/// `(anchor - offset - range, anchor - offset]`. The child grid is built for that interval, while
2162/// the output grid remains the statement's grid; the anchor, range and offset are bound together in
2163/// the window.
2164fn subquery_window(
2165 context: &Context,
2166 name: &str,
2167 function: RangeFunction,
2168 subquery: &SubqueryExpr,
2169) -> Result<NativeNode> {
2170 let SubqueryExpr { expr, .. } = subquery;
2171 // A subquery evaluates an expression and hands the window one value per grid point per field, so
2172 // the expression inside it has to be a vector: a scalar has no fields for the window to fold.
2173 if expr.value_type() != ValueType::Vector {
2174 return Err(not_implemented(&format!(
2175 "a call to `{name}` over the subquery `{subquery}`, whose expression is a {}, where a \
2176 subquery has to evaluate a vector",
2177 expr.value_type()
2178 )));
2179 }
2180 let Some(SubqueryGrid {
2181 window,
2182 grid: child_grid,
2183 }) = subquery_child_grid(context.stmt, &context.grid, subquery)?
2184 else {
2185 return Err(not_implemented(&format!(
2186 "the subquery `{subquery}`, which names no evaluation point in its anchored interval or \
2187 the statement's range"
2188 )));
2189 };
2190 let inner = compile_expr(
2191 &Context {
2192 stmt: context.stmt,
2193 bindings: context.bindings,
2194 inputs: context.inputs,
2195 ordering: context.ordering,
2196 grid: Arc::clone(&child_grid),
2197 value_field: Arc::clone(&context.value_field),
2198 source_kind: context.source_kind,
2199 },
2200 expr,
2201 )?;
2202
2203 let inner_schema = inner
2204 .output
2205 .samples()
2206 .ok_or_else(|| DataFusionError::Internal("subquery body did not produce samples".into()))?;
2207 let output = NativeType::Samples(Arc::new(SeriesSchema {
2208 fields: Arc::clone(&inner_schema.fields),
2209 eval_grid: Some(Arc::clone(&context.grid)),
2210 }));
2211
2212 Ok(NativeNode {
2213 expr: NativeExpr::Window {
2214 input: Box::new(inner),
2215 op: BoundWindow {
2216 function,
2217 window,
2218 // The one field that tells this window from a raw one: its input was evaluated on the
2219 // subquery's grid rather than read from the scan.
2220 input_grid: Some(child_grid),
2221 output_grid: Arc::clone(&context.grid),
2222 },
2223 },
2224 output,
2225 })
2226}
2227
2228/// Compiles a bare selector into an instant selection over the raw input.
2229///
2230/// The lookback, the offset and the grid are the whole of an instant selection: it reports the last
2231/// sample at or before each grid point, within the statement's lookback.
2232fn instant_selection(context: &Context, selector: &VectorSelector) -> Result<NativeNode> {
2233 instant_selection_of(context, selector, InstantValue::Sample)
2234}
2235
2236fn instant_selection_of(
2237 context: &Context,
2238 selector: &VectorSelector,
2239 value: InstantValue,
2240) -> Result<NativeNode> {
2241 let lookback_ms = lookback_millis(context.stmt.lookback_delta.as_millis())?;
2242 let offset_ms = selector_offset_ms(&selector.offset)?;
2243 let at_ms = selector_anchor_ms(&selector.at, context.stmt)?;
2244 let output_grid = Arc::clone(&context.grid);
2245 let (grid_start_ms, grid_end_ms) = grid_endpoints(&output_grid)?;
2246 let (source_index, schema) = bind_selector(
2247 context,
2248 SelectorRequirement {
2249 metric: selector.name.clone(),
2250 matchers: selector.matchers.clone(),
2251 offset_ms,
2252 at_ms,
2253 grid_start_ms,
2254 grid_end_ms,
2255 timing: SelectorTiming::Instant { lookback_ms },
2256 },
2257 )?;
2258 if value == InstantValue::Timestamp && schema.fields.len() != 1 {
2259 return Err(not_implemented(
2260 "timestamp() over a multi-value input is not supported natively",
2261 ));
2262 }
2263 let output = NativeType::Samples(Arc::new(SeriesSchema {
2264 fields: Arc::clone(&schema.fields),
2265 eval_grid: Some(Arc::clone(&output_grid)),
2266 }));
2267 let raw = NativeType::Samples(Arc::clone(&schema));
2268 Ok(NativeNode {
2269 expr: NativeExpr::Instant {
2270 input: Box::new(NativeNode {
2271 expr: NativeExpr::Input(BoundInput {
2272 output: raw.clone(),
2273 source_index,
2274 ordering: context.ordering,
2275 }),
2276 output: raw,
2277 }),
2278 op: BoundInstant {
2279 lookback_ms,
2280 offset_ms,
2281 at_ms,
2282 value,
2283 output_grid,
2284 },
2285 },
2286 output,
2287 })
2288}
2289
2290fn bind_selector(
2291 context: &Context,
2292 requirement: SelectorRequirement,
2293) -> Result<(usize, Arc<SeriesSchema>)> {
2294 let schema = (context.bindings)(&requirement)?;
2295 let source_index = context.inputs.borrow().len();
2296 context.inputs.borrow_mut().push(CompiledInput {
2297 source_index,
2298 requirement,
2299 schema: Arc::clone(&schema),
2300 ordering: context.ordering,
2301 });
2302 Ok((source_index, schema))
2303}
2304
2305fn grid_endpoints(grid: &EvalGrid) -> Result<(i64, i64)> {
2306 let spec = grid.spec();
2307 let end = i128::from(spec.start_ms) + i128::from(spec.len - 1) * i128::from(spec.step_ms);
2308 let end = i64::try_from(end)
2309 .map_err(|_| DataFusionError::Internal("evaluation grid endpoint overflows".into()))?;
2310 Ok((spec.start_ms, end))
2311}
2312
2313/// The grid the statement is evaluated on: `(end - start) / step + 1` points, the last of which
2314/// does not pass `end`.
2315///
2316/// Visible to the planner because the binding a [`NativeTree`] is planned against has to name the
2317/// same grid the tree itself was compiled on, and [`compile`]'s callers therefore read it here
2318/// rather than deriving the grid a second time.
2319pub(crate) fn statement_grid(stmt: &EvalStmt) -> Result<Arc<EvalGrid>> {
2320 let start_ms = signed_millis_since_epoch(stmt.start)?;
2321 let end_ms = signed_millis_since_epoch(stmt.end)?;
2322 // The step is narrowed before [`GridSpec`] sees it, so an interval to which no millisecond
2323 // step corresponds is reported as its own value rather than as a step of zero.
2324 let step_ms = millis(stmt.interval.as_millis()).ok_or_else(|| {
2325 DataFusionError::Plan(format!(
2326 "the statement's evaluation step of {}ms is out of range",
2327 stmt.interval.as_millis()
2328 ))
2329 })?;
2330 // A positive step, ordered endpoints and an inclusive length that fits are the grid's contract,
2331 // so [`GridSpec`] owns them; re-deriving any of them here would be a second copy of it.
2332 let spec = GridSpec::try_from_range(start_ms, end_ms, step_ms).map_err(|error| {
2333 DataFusionError::Plan(format!(
2334 "the statement's grid of {start_ms}ms..{end_ms}ms at {step_ms}ms per step is invalid: \
2335 {error}"
2336 ))
2337 })?;
2338 Ok(Arc::new(EvalGrid::try_deferred(spec).map_err(grid_error)?))
2339}
2340
2341/// The window length of a range selector, which has to be longer than zero to select anything.
2342fn range_millis(range: u128) -> Result<i64> {
2343 let range_ms = millis(range).ok_or_else(|| {
2344 DataFusionError::Plan(format!(
2345 "the range selector's window of {range}ms is out of range"
2346 ))
2347 })?;
2348 if range_ms <= 0 {
2349 return Err(DataFusionError::Plan(format!(
2350 "the range selector's window is {range_ms}ms, and a window has to be longer than zero"
2351 )));
2352 }
2353 Ok(range_ms)
2354}
2355
2356/// The statement's lookback in milliseconds, which is how far back an instant selection reads.
2357fn lookback_millis(lookback: u128) -> Result<i64> {
2358 millis(lookback).ok_or_else(|| {
2359 DataFusionError::Plan(format!(
2360 "the statement's lookback of {lookback}ms is out of range"
2361 ))
2362 })
2363}
2364
2365/// The selector's `@` anchor in milliseconds since the Unix epoch, or `None` when it has none.
2366///
2367/// `start()` and `end()` stay symbolic in the AST, because only the statement knows which evaluation
2368/// range they name, so they are resolved against `stmt.start` and `stmt.end` here. The offset is not
2369/// folded in: [`RangeWindow`] keeps anchor and offset apart and ends the window at
2370/// `anchor_ms - offset_ms` at run time.
2371///
2372/// An anchor decouples the window's read range from the statement's: it reads
2373/// `(anchor_ms - offset_ms - range_ms, anchor_ms - offset_ms]`, which for an anchor like `@ 1234` can
2374/// lie entirely outside `[stmt.start - range_ms, stmt.end]`. Whoever binds the scan therefore has to
2375/// derive its range from the window's anchor, offset and range rather than from `stmt.start` and
2376/// `stmt.end`; a scan bound to the statement alone leaves such a window with no samples, and the
2377/// query silently returns empty instead of failing.
2378fn selector_anchor_ms(at: &Option<AtModifier>, stmt: &EvalStmt) -> Result<Option<i64>> {
2379 match at {
2380 None => Ok(None),
2381 Some(AtModifier::Start) => Ok(Some(signed_millis_since_epoch(stmt.start)?)),
2382 Some(AtModifier::End) => Ok(Some(signed_millis_since_epoch(stmt.end)?)),
2383 Some(AtModifier::At(time)) => Ok(Some(signed_millis_since_epoch(*time)?)),
2384 }
2385}
2386
2387/// The selector's offset in milliseconds; positive reads earlier samples.
2388fn selector_offset_ms(offset: &Option<Offset>) -> Result<i64> {
2389 let Some(offset) = offset else {
2390 return Ok(0);
2391 };
2392 let (magnitude, sign) = match offset {
2393 Offset::Pos(duration) => (duration.as_millis(), 1),
2394 Offset::Neg(duration) => (duration.as_millis(), -1),
2395 };
2396 millis(magnitude)
2397 .and_then(|magnitude| magnitude.checked_mul(sign))
2398 .ok_or_else(|| {
2399 DataFusionError::Plan(format!(
2400 "the selector's offset of {magnitude}ms is out of range"
2401 ))
2402 })
2403}
2404
2405/// A millisecond magnitude as an `i64`, or `None` when it does not fit.
2406fn millis(millis: u128) -> Option<i64> {
2407 i64::try_from(millis).ok()
2408}
2409
2410fn grid_error(error: datatypes::error::Error) -> DataFusionError {
2411 DataFusionError::Plan(format!("the statement's grid is invalid: {error}"))
2412}
2413
2414/// What a call to a range function has to be: where its range selector sits, how many constants it
2415/// reads, and how they bind.
2416///
2417/// The selector's position is a variant rather than a convention because PromQL does not put it in
2418/// one place: `quantile_over_time(0.9, x[5m])` writes its quantile before the selector, while
2419/// `predict_linear(x[5m], 300)` and `double_exponential_smoothing(x[5m], 0.5, 0.1)` write theirs
2420/// after it. A single "parameters come first" rule would read the selector as a constant in the
2421/// second group and reject an ordinary query, so each shape states its own layout.
2422#[derive(Clone, Copy)]
2423enum RangeSignature {
2424 /// A function that reads only its range selector, as in `rate(x[5m])`.
2425 Selector(RangeFunction),
2426 /// One constant, then the range selector, as in `quantile_over_time(0.9, x[5m])`.
2427 ConstantBeforeSelector(fn(f64) -> RangeFunction),
2428 /// The range selector, then one constant, as in `predict_linear(x[5m], 300)`.
2429 ConstantAfterSelector(fn(f64) -> RangeFunction),
2430 /// The range selector, then two constants, as in
2431 /// `double_exponential_smoothing(x[5m], 0.5, 0.1)`.
2432 TwoConstantsAfterSelector(fn(f64, f64) -> RangeFunction),
2433}
2434
2435impl RangeSignature {
2436 /// The position of the range selector among the call's arguments.
2437 fn selector_index(self) -> usize {
2438 match self {
2439 Self::Selector(_)
2440 | Self::ConstantAfterSelector(_)
2441 | Self::TwoConstantsAfterSelector(_) => 0,
2442 Self::ConstantBeforeSelector(_) => 1,
2443 }
2444 }
2445
2446 /// How many constants the function reads.
2447 fn constants(self) -> usize {
2448 match self {
2449 Self::Selector(_) => 0,
2450 Self::ConstantBeforeSelector(_) | Self::ConstantAfterSelector(_) => 1,
2451 Self::TwoConstantsAfterSelector(_) => 2,
2452 }
2453 }
2454
2455 /// How many arguments the call writes, its range selector counted in.
2456 fn arity(self) -> usize {
2457 self.constants() + 1
2458 }
2459
2460 /// What the call's arguments are, for the arity rejection to name them.
2461 fn arguments(self) -> &'static str {
2462 match self {
2463 Self::Selector(_) => "its range selector",
2464 Self::ConstantBeforeSelector(_) => "a number and its range selector",
2465 Self::ConstantAfterSelector(_) => "its range selector and a number",
2466 Self::TwoConstantsAfterSelector(_) => "its range selector and two numbers",
2467 }
2468 }
2469
2470 /// Binds the function from the call's arguments, which have already passed the arity check.
2471 fn bind(self, name: &str, args: &[Box<PromExpr>]) -> Result<RangeFunction> {
2472 Ok(match self {
2473 Self::Selector(function) => function,
2474 Self::ConstantBeforeSelector(bind) => bind(constant_argument(name, &args[0], 0)?),
2475 Self::ConstantAfterSelector(bind) => bind(constant_argument(name, &args[1], 1)?),
2476 Self::TwoConstantsAfterSelector(bind) => bind(
2477 constant_argument(name, &args[1], 1)?,
2478 constant_argument(name, &args[2], 2)?,
2479 ),
2480 })
2481 }
2482}
2483
2484/// The signature the PromQL name calls, or `None` when this compiler has no range kernel for it.
2485///
2486/// The map is explicit on purpose, as in [`range_function`]: a name that is not listed is rejected,
2487/// so supporting one more function is a decision made in one place rather than a consequence of a
2488/// name looking familiar. A parameterised function is named here rather than in the map, because
2489/// its name alone cannot produce the variant the tree binds.
2490fn range_signature(name: &str) -> Option<RangeSignature> {
2491 match name {
2492 "quantile_over_time" => Some(RangeSignature::ConstantBeforeSelector(
2493 RangeFunction::QuantileOverTime,
2494 )),
2495 // These two write their constants after the selector, which is the opposite order to
2496 // `quantile_over_time`.
2497 "predict_linear" => Some(RangeSignature::ConstantAfterSelector(
2498 RangeFunction::PredictLinear,
2499 )),
2500 "double_exponential_smoothing" => Some(RangeSignature::TwoConstantsAfterSelector(
2501 |smoothing, trend| RangeFunction::DoubleExponentialSmoothing { smoothing, trend },
2502 )),
2503 _ => range_function(name).map(RangeSignature::Selector),
2504 }
2505}
2506
2507/// What a call to a math function has to be: the constants it reads after its vector, and how to
2508/// bind them.
2509///
2510/// The shapes are separated by how many constants the function reads, because that is the only
2511/// thing the variants differ in: a name maps to one kernel, and the constants are bound from the
2512/// call. `round` is the one function whose constant may be left out, so it is its own shape: the
2513/// default is a decision about the function rather than about the constant.
2514#[derive(Clone, Copy)]
2515enum MathSignature {
2516 /// A function of its vector alone, as in `abs`.
2517 Unary(MathOp),
2518 /// A function of its vector and one constant, as in `clamp_min`.
2519 OneConstant(fn(f64) -> MathOp),
2520 /// A function of its vector and one constant it may be called without, as in `round`.
2521 DefaultedConstant {
2522 default: f64,
2523 bind: fn(f64) -> MathOp,
2524 },
2525 /// A function of its vector and two constants, as in `clamp`.
2526 TwoConstants(fn(f64, f64) -> MathOp),
2527}
2528
2529impl MathSignature {
2530 /// How many constants the function reads when every one of them is written.
2531 fn parameters(self) -> usize {
2532 match self {
2533 Self::Unary(_) => 0,
2534 Self::OneConstant(_) | Self::DefaultedConstant { .. } => 1,
2535 Self::TwoConstants(_) => 2,
2536 }
2537 }
2538
2539 /// How many constants the function has to be given.
2540 fn required(self) -> usize {
2541 match self {
2542 Self::DefaultedConstant { .. } => 0,
2543 _ => self.parameters(),
2544 }
2545 }
2546
2547 /// What the call's arguments are, for the arity rejection to name them.
2548 fn arguments(self) -> &'static str {
2549 match self {
2550 Self::Unary(_) => "its vector",
2551 Self::OneConstant(_) => "its vector and one constant",
2552 Self::DefaultedConstant { .. } => "its vector and one optional constant",
2553 Self::TwoConstants(_) => "its vector and two constants",
2554 }
2555 }
2556}
2557
2558/// The signature the PromQL name calls, or `None` when this compiler has no math kernel for it.
2559///
2560/// The map is explicit on purpose, as in [`range_function`]: a name that is not listed is refused
2561/// rather than treated as math because it looks mathematical, so adding one more function is a
2562/// decision made in one place. A name in this list is a promise that its kernel exists, which is why
2563/// arity is a property of the variant rather than of the caller.
2564fn math_signature(name: &str) -> Option<MathSignature> {
2565 match name {
2566 "abs" => Some(MathSignature::Unary(MathOp::Abs)),
2567 "ceil" => Some(MathSignature::Unary(MathOp::Ceil)),
2568 "floor" => Some(MathSignature::Unary(MathOp::Floor)),
2569 "sqrt" => Some(MathSignature::Unary(MathOp::Sqrt)),
2570 "exp" => Some(MathSignature::Unary(MathOp::Exp)),
2571 "ln" => Some(MathSignature::Unary(MathOp::Ln)),
2572 "log2" => Some(MathSignature::Unary(MathOp::Log2)),
2573 "log10" => Some(MathSignature::Unary(MathOp::Log10)),
2574 "sin" => Some(MathSignature::Unary(MathOp::Sin)),
2575 "cos" => Some(MathSignature::Unary(MathOp::Cos)),
2576 "tan" => Some(MathSignature::Unary(MathOp::Tan)),
2577 "asin" => Some(MathSignature::Unary(MathOp::Asin)),
2578 "acos" => Some(MathSignature::Unary(MathOp::Acos)),
2579 "atan" => Some(MathSignature::Unary(MathOp::Atan)),
2580 "sinh" => Some(MathSignature::Unary(MathOp::Sinh)),
2581 "cosh" => Some(MathSignature::Unary(MathOp::Cosh)),
2582 "tanh" => Some(MathSignature::Unary(MathOp::Tanh)),
2583 "asinh" => Some(MathSignature::Unary(MathOp::Asinh)),
2584 "acosh" => Some(MathSignature::Unary(MathOp::Acosh)),
2585 "atanh" => Some(MathSignature::Unary(MathOp::Atanh)),
2586 "deg" => Some(MathSignature::Unary(MathOp::Deg)),
2587 "rad" => Some(MathSignature::Unary(MathOp::Rad)),
2588 "sgn" => Some(MathSignature::Unary(MathOp::Sgn)),
2589 // A date function takes the vector its values are read from; without one it reads the
2590 // evaluation time, which has no input to map and is refused by `math_op`.
2591 "day_of_month" => Some(MathSignature::Unary(MathOp::Date(DateFunction::DayOfMonth))),
2592 "day_of_week" => Some(MathSignature::Unary(MathOp::Date(DateFunction::DayOfWeek))),
2593 "day_of_year" => Some(MathSignature::Unary(MathOp::Date(DateFunction::DayOfYear))),
2594 "days_in_month" => Some(MathSignature::Unary(MathOp::Date(
2595 DateFunction::DaysInMonth,
2596 ))),
2597 "hour" => Some(MathSignature::Unary(MathOp::Date(DateFunction::Hour))),
2598 "minute" => Some(MathSignature::Unary(MathOp::Date(DateFunction::Minute))),
2599 "month" => Some(MathSignature::Unary(MathOp::Date(DateFunction::Month))),
2600 "year" => Some(MathSignature::Unary(MathOp::Date(DateFunction::Year))),
2601 // `round`'s nearest defaults to one, so `round(x)` is `round(x, 1)` and its variant always
2602 // carries the number it rounds to.
2603 "round" => Some(MathSignature::DefaultedConstant {
2604 default: 1.0,
2605 bind: |nearest| MathOp::Round { nearest },
2606 }),
2607 "clamp" => Some(MathSignature::TwoConstants(|min, max| MathOp::Clamp {
2608 min,
2609 max,
2610 })),
2611 "clamp_min" => Some(MathSignature::OneConstant(|min| MathOp::ClampMin { min })),
2612 "clamp_max" => Some(MathSignature::OneConstant(|max| MathOp::ClampMax { max })),
2613 _ => None,
2614 }
2615}
2616
2617/// The pointwise kernel `name` denotes over its vector, and that vector, or `None` when this
2618/// compiler has no math kernel for that name.
2619///
2620/// A name that is not in [`math_signature`] is not math: the caller reports that it has no kernel
2621/// instead of compiling it into a kernel that would compute something else. `arguments` is the
2622/// call's whole argument list, because the vector is its first argument: the arity is the
2623/// signature's and counts the vector in, so a call with no argument at all is refused as a call
2624/// that wrote none rather than as a shape this compiler cannot bind. The arguments after the vector
2625/// are the call's constants, in the order they were written, and each is folded to the number it
2626/// means by [`constant_value`], because the tree binds a kernel's constants and has no field for an
2627/// expression.
2628fn math_op<'a>(
2629 name: &str,
2630 arguments: &'a [Box<PromExpr>],
2631) -> Result<Option<(MathOp, &'a PromExpr)>> {
2632 let Some(signature) = math_signature(name) else {
2633 return Ok(None);
2634 };
2635 // The vector is the function's first argument, so a call that wrote no argument at all is
2636 // refused by the same arity check as one that wrote too few constants.
2637 let Some((vector, parameters)) = arguments.split_first() else {
2638 return Err(arity_error(name, signature, 0));
2639 };
2640 let given = parameters.len() + 1;
2641 if given < signature.required() + 1 || given > signature.parameters() + 1 {
2642 return Err(arity_error(name, signature, given));
2643 }
2644 // The vector is the first argument, so the constants are read from the second onwards.
2645 let op = match signature {
2646 MathSignature::Unary(op) => op,
2647 MathSignature::OneConstant(bind) => bind(constant_argument(name, ¶meters[0], 1)?),
2648 MathSignature::DefaultedConstant { default, bind } => bind(match parameters.first() {
2649 Some(parameter) => constant_argument(name, parameter, 1)?,
2650 None => default,
2651 }),
2652 MathSignature::TwoConstants(bind) => bind(
2653 constant_argument(name, ¶meters[0], 1)?,
2654 constant_argument(name, ¶meters[1], 2)?,
2655 ),
2656 };
2657 Ok(Some((op, vector)))
2658}
2659
2660/// The native histogram function `name` denotes, or `None` when it is not one.
2661///
2662/// These read only native histogram samples and drop the float ones, as Prometheus'
2663/// `simpleHistogramFunc` does; `histogram_quantile` and `histogram_fraction` also read classic
2664/// bucket series and are not listed.
2665fn histogram_function(name: &str) -> Option<NativeHistogramFunction> {
2666 match name {
2667 "histogram_count" => Some(NativeHistogramFunction::Count),
2668 "histogram_sum" => Some(NativeHistogramFunction::Sum),
2669 "histogram_avg" => Some(NativeHistogramFunction::Avg),
2670 "histogram_stddev" => Some(NativeHistogramFunction::StdDev),
2671 "histogram_stdvar" => Some(NativeHistogramFunction::StdVar),
2672 _ => None,
2673 }
2674}
2675
2676/// The label change `label_replace` or `label_join` makes, and the vector it is made to, or `None`
2677/// when `name` is neither.
2678///
2679/// The parser checks the argument types and counts; what is left to check is the arguments'
2680/// content, which [`LabelRewrite`] does as Prometheus does at evaluation, so an invalid regular
2681/// expression or an empty label name fails the statement here as it would there.
2682fn label_rewrite<'a>(
2683 name: &str,
2684 arguments: &'a [Box<PromExpr>],
2685) -> Result<Option<(LabelRewrite, &'a PromExpr)>> {
2686 if !matches!(name, "label_replace" | "label_join") {
2687 return Ok(None);
2688 }
2689 let Some((vector, strings)) = arguments.split_first() else {
2690 return Err(not_implemented(&format!(
2691 "a call to `{name}` with no argument"
2692 )));
2693 };
2694 let strings = strings
2695 .iter()
2696 .map(|argument| match unparen(argument) {
2697 PromExpr::StringLiteral(StringLiteral { val }) => Ok(val.as_str()),
2698 other => Err(not_implemented(&format!(
2699 "a call to `{name}` whose argument `{other}` is not a string literal"
2700 ))),
2701 })
2702 .collect::<Result<Vec<_>>>()?;
2703 let rewrite = match (name, strings.as_slice()) {
2704 ("label_replace", [dst, replacement, src, regex]) => {
2705 LabelRewrite::replace(dst, replacement, src, regex)?
2706 }
2707 ("label_join", [dst, separator, src @ ..]) => LabelRewrite::join(dst, separator, src)?,
2708 _ => {
2709 return Err(not_implemented(&format!(
2710 "a call to `{name}` with {} argument(s)",
2711 arguments.len()
2712 )));
2713 }
2714 };
2715 Ok(Some((rewrite, vector)))
2716}
2717
2718/// The rejection of a math call that wrote `given` arguments where `signature` takes another count.
2719///
2720/// The count is the signature's, so the message says what this function takes rather than what one
2721/// argument happens to be. The vector is counted in: it is the function's first argument, and a
2722/// reader counting the call's arguments should not have to add it themselves.
2723fn arity_error(name: &str, signature: MathSignature, given: usize) -> DataFusionError {
2724 not_implemented(&format!(
2725 "a call to `{name}` with {given} argument(s), where it takes {}",
2726 signature.arguments()
2727 ))
2728}
2729
2730/// The constant `argument` folds to, or a rejection naming the argument and where it was read.
2731///
2732/// A parameter is a constant of the statement: a quantile, a rounding step or a clamp bound is a
2733/// field of the tree, so a parameter whose value is only known at run time — `time()` being the real
2734/// case — has nowhere to go. It is refused rather than answered from the wrong number, and the
2735/// rejection names the expression, because that is what the query has to change.
2736///
2737/// `name` is whoever reads the argument: a call's function name, or an aggregator's, since
2738/// `quantile(0.9, x)` reads a constant too. The rejection therefore names that and the position
2739/// rather than calling everything a call, which would be false for an aggregate.
2740///
2741/// A quantile outside `[0, 1]` is not refused here: Prometheus binds it and the kernel reports
2742/// `-Infinity` below zero and `+Infinity` above one, so refusing it would be this compiler inventing
2743/// a rule the query engine does not have.
2744fn constant_argument(name: &str, argument: &PromExpr, position: usize) -> Result<f64> {
2745 constant_value(argument).ok_or_else(|| {
2746 not_implemented(&format!(
2747 "`{name}`, whose {} is `{argument}`, where it has to be a constant expression this \
2748 compiler folds to a number literal",
2749 argument_position(position)
2750 ))
2751 })
2752}
2753
2754/// How a rejection names the argument a parameter was read from.
2755///
2756/// The three positions are the ones a supported call can write: a math function's vector and the two
2757/// constants behind it, or a range function's selector and the constants on either side of it. Every
2758/// caller passes the literal position it read, so there is no fourth position to name and no default
2759/// to invent one for.
2760fn argument_position(position: usize) -> &'static str {
2761 const POSITIONS: [&str; 3] = ["first argument", "second argument", "third argument"];
2762 POSITIONS[position]
2763}
2764
2765/// Whether a binary operation carries a modifier this compiler refuses to bind.
2766///
2767/// A scalar carries no labels, so there is nothing to match or name, and the tree's matching has no
2768/// field for a fill value: binding the operation would compute it without the modifier the query
2769/// asked for. The fold and [`binary_operation`] share this test rather than restating it, because a
2770/// fold that computed a constant without reading its modifier would answer a query the dispatch
2771/// below refuses.
2772fn refuses_modifier(modifier: Option<&BinModifier>) -> bool {
2773 modifier.is_some_and(|modifier| {
2774 modifier.matching.is_some()
2775 || modifier.card != VectorMatchCardinality::OneToOne
2776 || modifier.fill_values != VectorMatchFillValues::default()
2777 })
2778}
2779
2780/// The number `expr` folds to, or `None` when its value is not the statement's to know.
2781///
2782/// Only what the statement itself decides is folded: a number literal, a group around one, a negated
2783/// one, `pi()`, and arithmetic whose two operands both fold. Any other call, a selector, a range
2784/// selector, an aggregate and a subquery are `None`, because their value comes from the data or from
2785/// the evaluation time, and a kernel's constant is a field of the tree rather than something bound
2786/// while it runs. Returning `None` rather than an error is what lets the caller report where the
2787/// expression was found, which is the useful half of the refusal.
2788///
2789/// `pi()` belongs on the folding side because the statement itself decides it: it is one number, not
2790/// a value read from the data. Folding it is what makes `pi() * x` the multiplication by
2791/// [`std::f64::consts::PI`] it means, `clamp_max(x, pi())` a kernel constant like `clamp_max(x, 3)`,
2792/// and `quantile(pi() / 4, x)` a parameter this compiler can bind. The number is the one the promql
2793/// crate's `map_pi` answers the previous route with — both are `std::f64::consts::PI` — so the two
2794/// routes cannot disagree about what `pi()` is.
2795///
2796/// Arithmetic uses the kernel operation named by [`BinaryOp::kind`], including
2797/// [`ArithmeticOp::calculate`]'s platform math behavior; defining `%`, `^` or `atan2` again here
2798/// would be a second answer for the two to disagree over. Set operators do not fold.
2799/// Visible to the planner, which asks whether a statement's value is a constant before binding it.
2800pub(crate) fn constant_value(expr: &PromExpr) -> Option<f64> {
2801 match expr {
2802 PromExpr::NumberLiteral(NumberLiteral { val }) => Some(*val),
2803 PromExpr::Paren(paren) => constant_value(&paren.expr),
2804 PromExpr::Unary(unary) => constant_value(&unary.expr).map(|value| -value),
2805 PromExpr::Binary(binary) => {
2806 // A modifier is read before the operands are folded: `x * (1 + fill(0) 2)` asks for a
2807 // fill, and folding the inner addition would answer `x * 3` with the fill gone. The
2808 // expression is left unfolded so the dispatch below refuses it with the reason it
2809 // writes, which is also why this is a `None` rather than an error here.
2810 if refuses_modifier(binary.modifier.as_ref()) {
2811 return None;
2812 }
2813 let left = constant_value(&binary.lhs)?;
2814 let right = constant_value(&binary.rhs)?;
2815 match binary_op(&binary.op)?.kind() {
2816 BinaryKind::Arithmetic(op) => Some(op.calculate(left, right)),
2817 // A comparison of two constants is the number it reports when it is written with
2818 // `bool`: Prometheus reads `1 > bool 2` as `0`, which is the kernel's own
2819 // comparison. Without `bool` there is no number to report -- `1 > 2` is a parse
2820 // error in Prometheus -- so it is left unfolded and the dispatch refuses it.
2821 BinaryKind::Comparison(op) => binary
2822 .return_bool()
2823 .then(|| f64::from(op.apply(left, right))),
2824 }
2825 }
2826 // A selector, a range selector, an aggregate and a subquery read data; `time()`,
2827 // `scalar(v)` and the rest of the calls read something this compiler cannot know before the
2828 // query runs. `pi()` is not one of them: it is the one call whose value the statement itself
2829 // fixes, so it folds here as a literal does.
2830 PromExpr::Call(call) if call.func.name == "pi" && call.args.args.is_empty() => {
2831 Some(std::f64::consts::PI)
2832 }
2833 _ => None,
2834 }
2835}
2836
2837/// The range function a PromQL name denotes, or `None` when this compiler has no kernel for it.
2838///
2839/// The map is explicit on purpose: a name that is not listed here is rejected, so supporting one
2840/// more function is a decision made in one place rather than a consequence of a name looking
2841/// familiar.
2842fn range_function(name: &str) -> Option<RangeFunction> {
2843 match name {
2844 "rate" => Some(RangeFunction::Rate),
2845 "increase" => Some(RangeFunction::Increase),
2846 "delta" => Some(RangeFunction::Delta),
2847 "irate" => Some(RangeFunction::Irate),
2848 "idelta" => Some(RangeFunction::Idelta),
2849 "avg_over_time" => Some(RangeFunction::AvgOverTime),
2850 "min_over_time" => Some(RangeFunction::MinOverTime),
2851 "max_over_time" => Some(RangeFunction::MaxOverTime),
2852 "sum_over_time" => Some(RangeFunction::SumOverTime),
2853 "count_over_time" => Some(RangeFunction::CountOverTime),
2854 "last_over_time" => Some(RangeFunction::LastOverTime),
2855 "present_over_time" => Some(RangeFunction::PresentOverTime),
2856 "stddev_over_time" => Some(RangeFunction::StddevOverTime),
2857 "stdvar_over_time" => Some(RangeFunction::StdvarOverTime),
2858 "resets" => Some(RangeFunction::Resets),
2859 "changes" => Some(RangeFunction::Changes),
2860 "deriv" => Some(RangeFunction::Deriv),
2861 // These functions are supported unconditionally by this native compiler.
2862 "first_over_time" => Some(RangeFunction::FirstOverTime),
2863 "mad_over_time" => Some(RangeFunction::MadOverTime),
2864 "ts_of_first_over_time" => Some(RangeFunction::TsOfFirstOverTime),
2865 "ts_of_last_over_time" => Some(RangeFunction::TsOfLastOverTime),
2866 "ts_of_min_over_time" => Some(RangeFunction::TsOfMinOverTime),
2867 "ts_of_max_over_time" => Some(RangeFunction::TsOfMaxOverTime),
2868 _ => None,
2869 }
2870}
2871
2872/// The expression a parenthesised one wraps, however many parentheses were written.
2873///
2874/// Parentheses group, so they say nothing about the expression inside them: `rate((x[5m]))` asks
2875/// for exactly what `rate(x[5m])` asks for. Refusing it would reject a statement on the way it was
2876/// typed rather than on what it means. A range selector is not an expression this compiler
2877/// compiles on its own, so the call that reads one looks through the grouping itself.
2878fn unparen(mut expr: &PromExpr) -> &PromExpr {
2879 while let PromExpr::Paren(paren) = expr {
2880 expr = &paren.expr;
2881 }
2882 expr
2883}
2884
2885/// A rejection of a shape outside [`SUPPORTED`].
2886fn not_implemented(found: &str) -> DataFusionError {
2887 DataFusionError::NotImplemented(format!(
2888 "the native PromQL compiler supports only {SUPPORTED} for now, but found {found}"
2889 ))
2890}
2891
2892#[cfg(test)]
2893mod tests;