Skip to main content

query/promql/planner/
native.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//! The native fused-series route of the PromQL planner.
16//!
17//! [`PromPlanner::try_plan_native_fused`] offers a whole statement expression to the native compiler and,
18//! when the compiler accepts it, replaces everything the existing path would plan below the root with one
19//! [`FusedSeries`] node over the selector's own table scan. A tree that folds across series, such as an
20//! aggregate, is split instead: its per-series prefix and a `Partial` aggregate run in a `FusedSeries`
21//! producer, a `SeriesRepartitionExec` routes that state, and a second `FusedSeries` runs the `Final`
22//! aggregate over it, because a region holds only part of a group. Declining is the normal answer: every
23//! shape the compiler does not accept, and every query this route cannot bind to a scan faithfully, keeps
24//! the plan the existing planner builds.
25//!
26//! The node is built from the raw series schema the tree's input was compiled against, the statement's
27//! evaluation grid, and output tag names derived from the native tree. The output schema has the shape the
28//! existing unary pipeline produces -- the time index, then the series fields, then the tags -- so a node
29//! planned here is consumed by the same code that consumes a `SeriesNormalize` output.
30//!
31//! A statement that reads no data - a constant, `time()`, `vector(time())` - is planned with no scan: one
32//! node, no child, the time index and value.
33
34use std::borrow::Cow;
35use std::sync::Arc;
36use std::time::{Duration, SystemTime, UNIX_EPOCH};
37
38use common_catalog::consts::{METRIC_ENGINE, MITO_ENGINE, MITO2_ENGINE};
39use common_query::native_histogram::native_histogram_value_type;
40use common_query::prelude::OTLP_AGGREGATION_TEMPORALITY_LABEL;
41use common_query::series_frame::raw_series_frame_schema_with_ordering;
42use datafusion::arrow::datatypes::DataType as ArrowDataType;
43use datafusion::common::{DFSchema, DFSchemaRef};
44use datafusion::error::DataFusionError;
45use datafusion::logical_expr::UserDefinedLogicalNode;
46use datafusion::logical_expr::{EmptyRelation, Extension, LogicalPlan, TableScanBuilder, Union};
47use datafusion::physical_plan::ExecutionPlan;
48use datafusion::prelude::Expr as DfExpr;
49use datafusion_expr::Expr;
50use datatypes::data_type::DataType as _;
51use datatypes::series::SeriesOrdering;
52use datatypes::series::samples::{FieldSpec, SeriesSchema};
53use datatypes::series::time::EvalGrid;
54use futures::future::BoxFuture;
55use promql::extension_plan::{
56    FieldKind, FusedOutputFormat, FusedSeries, FusedSeriesBinding, FusedSeriesExec, InputLocality,
57    RawSeriesSource, input_locality, matching_operands_drop_key,
58};
59use promql::native::plan::{
60    AggregateKind, BoundAggregate, BoundInput, BoundVectorOp, NativeExpr, NativeNode, NativeTree,
61    NativeType, aggregate_state_binding, binary_output_field_kind, fused_output_tags,
62    native_tree_supported, uniform_field_kind,
63};
64use promql::native::segment::{
65    self, NATIVE_ORDERING, canonical_boundary_stages, canonical_local_prefix,
66    contains_canonical_merge, contains_global_consumer, groups_by_metric_name,
67    merge_answers_histogram, region_local_segment, segment_tree, with_row_name_column,
68};
69// Kept reachable here because this crate reads them through this module's own path: the dist
70// planner's commutativity check asks whether a fused node is per-series work, and this crate's
71// planner and tests read a discovered input's shape.
72pub(crate) use promql::native::segment::{
73    independent_scan_pair, is_empty_discovered_input, pointwise_operand,
74};
75use promql_parser::label::{METRIC_NAME, MatchOp, Matchers};
76use promql_parser::parser::value::ValueType;
77use promql_parser::parser::{
78    EvalStmt, Expr as PromExpr, MatrixSelector, ParenExpr, SubqueryExpr, VectorSelector,
79};
80use session::context::{MetricDiscoveryScope, QueryContextRef};
81use snafu::{ResultExt, ensure};
82use store_api::metric_engine_consts::{DATA_SCHEMA_TABLE_ID_COLUMN_NAME, METRIC_ENGINE_NAME};
83use store_api::region_engine::RawLabelSource;
84
85use crate::promql::error::{DataFusionPlanningSnafu, DuplicateOutputColumnsSnafu, Result};
86use crate::promql::native_compile::{
87    InfoInput, bind_evaluated_binary, compile_selectors_with_grid, compile_statement_with_grid,
88    info_input, statement_grid, subquery_child_grid,
89};
90use crate::promql::planner::{DEFAULT_FIELD_COLUMN, DEFAULT_TIME_INDEX_COLUMN, PromPlanner};
91use crate::query_engine::QueryEngineState;
92
93/// The query option that turns the native fused-series route on for one query.
94///
95/// Named after the engine-wide option it mirrors ([`QueryOptions::experimental_native_promql`]), it
96/// is a query option like the others in this crate: a client states it per request (the HTTP hints
97/// header, a gRPC context key) or per session (`SET query.experimental_native_promql = ...`), and
98/// the engine-wide option is the default. The three resolve in that order where the query options
99/// snapshot is applied, and the planner reads the resulting
100/// [`NativePromqlExtension`](crate::options::NativePromqlExtension) rather than this key.
101///
102/// [`QueryOptions::experimental_native_promql`]: crate::options::QueryOptions::experimental_native_promql
103pub const NATIVE_PROMQL_EXTENSION_KEY: &str = "query.experimental_native_promql";
104
105/// Whether the query options of one query ask for the native fused-series route.
106///
107/// Read from the query options snapshot the query is planned with, so a per-request value and a
108/// session `SET` arrive here alike, already normalized: this compares literally (`true` in any
109/// case) rather than parsing again, because a value that is not a boolean never reaches the
110/// snapshot.
111pub(crate) fn native_promql_requested(query_ctx: &QueryContextRef) -> bool {
112    query_ctx
113        .extension(NATIVE_PROMQL_EXTENSION_KEY)
114        .is_some_and(|value| value.eq_ignore_ascii_case("true"))
115}
116
117/// Whether one query asks for the native fused-series route, resolved the way planning resolves
118/// it: a stated value wins (`request over session `SET``), otherwise the engine default answers.
119///
120/// This exists for the callers that have to act *before* a plan is built - the frontend bounds
121/// metric discovery by the caller's grants only when this route will read it - and it resolves
122/// from the same two sources planning reads: [`QueryContext::query_option_snapshot`] for what the
123/// query states, and the engine-wide option for what it inherits. Nothing here re-derives the
124/// option from a third place, so the two readers cannot disagree.
125pub fn native_promql_resolved(
126    query_ctx: &QueryContextRef,
127    engine_default: bool,
128) -> crate::error::Result<bool> {
129    let snapshot = query_ctx.query_option_snapshot().map_err(|error| {
130        crate::error::InvalidQueryContextExtensionSnafu {
131            reason: error.to_string(),
132        }
133        .build()
134    })?;
135    Ok(
136        match snapshot.extensions().get(NATIVE_PROMQL_EXTENSION_KEY) {
137            Some(value) => value.eq_ignore_ascii_case("true"),
138            None => engine_default,
139        },
140    )
141}
142
143/// Whether this executable plan is the native raw PromQL topology, the one plan shape whose
144/// region reads one query-wide body budget cannot deadlock.
145///
146/// That topology is a chain of [`FusedSeriesExec`] nodes over region reads, and each fused node polls its
147/// input while that input is being drained, so a region body holding a permit keeps making progress.
148/// Admission stops there: a plan with any other multi-input node keeps its per-scan bounds only.
149pub(crate) fn native_raw_plan_bounds_region_reads(plan: &Arc<dyn ExecutionPlan>) -> bool {
150    fn walk(node: &dyn ExecutionPlan, fused: &mut usize) -> bool {
151        let is_fused = node.is::<FusedSeriesExec>();
152        if is_fused {
153            *fused += 1;
154        }
155        if node.children().len() > 1 && !is_fused {
156            return false;
157        }
158        node.children()
159            .iter()
160            .all(|child| walk(child.as_ref(), fused))
161    }
162
163    let mut fused = 0;
164    walk(plan.as_ref(), &mut fused) && fused > 0
165}
166
167/// What one discovered metric contributes: the shared schema, its time column, the tags the union
168/// reports, and the one metric name the single-source shape carries.
169type DiscoveredSelectorMetadata = (Arc<SeriesSchema>, String, Vec<String>, Arc<str>);
170
171/// One prepared occurrence of a selector: its scan, raw-series layout and reporting columns.
172///
173/// `partitioned` says whether the table behind that scan is split into regions along a partition column.
174/// Nothing in the scan carries this: it is a placement fact about the table.
175type PreparedInput = (
176    LogicalPlan,
177    Arc<SeriesSchema>,
178    Option<Arc<str>>,
179    String,
180    Vec<String>,
181    // `partitioned`: whether this input's table is split into regions along a partition column.
182    bool,
183    // `split_series`: whether that partition splits one series across regions, which a bare scan
184    // cannot reconcile. A partition on tags keeps every series whole in one region.
185    bool,
186);
187
188/// A fully placed native operand and the evaluated layout its frame carries.
189struct NativeFramePlan {
190    plan: LogicalPlan,
191    output: NativeType,
192    tags: Vec<String>,
193    kind: FieldKind,
194    time: String,
195    grid: Arc<EvalGrid>,
196}
197
198enum NativePlanned {
199    Rows(LogicalPlan),
200    Frame(NativeFramePlan),
201}
202
203fn native_planned(
204    plan: LogicalPlan,
205    metadata: Option<(NativeType, Vec<String>)>,
206    kind: FieldKind,
207    time: String,
208    grid: Arc<EvalGrid>,
209) -> NativePlanned {
210    match metadata {
211        Some((output, tags)) => NativePlanned::Frame(NativeFramePlan {
212            plan,
213            output,
214            tags,
215            kind,
216            time,
217            grid,
218        }),
219        None => NativePlanned::Rows(plan),
220    }
221}
222
223impl PromPlanner {
224    /// Builds the scan of the one logical table the current context is bound to. The caller has
225    /// already preprocessed this selector's matchers and set the context to its table.
226    #[allow(clippy::too_many_arguments)]
227    async fn prepare_one_scan(
228        &mut self,
229        matchers: Matchers,
230        under_rate_or_increase: bool,
231        logical_scan_id: &mut Option<u32>,
232        logical_ids_differ: &mut bool,
233        statement_kind: &mut Option<FieldKind>,
234    ) -> Result<Option<PreparedInput>> {
235        let (Some(metric), Some(time)) = (
236            self.ctx.table_name.clone(),
237            self.ctx.time_index_column.clone(),
238        ) else {
239            return Ok(None);
240        };
241        let tags = self.ctx.tag_columns.clone();
242        let fields = self.ctx.field_columns.clone();
243        // A `__field__` matcher narrows the field set in a projection the existing planner builds, and the
244        // raw series scan below this node has no equivalent: it reports every field the scan carries.
245        if self.ctx.field_column_matcher.is_some() || fields.is_empty() {
246            return Ok(None);
247        }
248        // Delta samples are increments: the existing planner sums them for `increase` and
249        // divides by the range for `rate`, while the native tree assumes cumulative samples.
250        // Decline only when this selector is read by one of those calls.
251        if tags
252            .iter()
253            .any(|tag| tag == OTLP_AGGREGATION_TEMPORALITY_LABEL)
254            && under_rate_or_increase
255        {
256            return Ok(None);
257        }
258        // The selector's own table scan, built by the same method the existing path uses:
259        // the physical planner turns it into the region scan the node reads, and building a
260        // scan here instead would let the two paths disagree about the columns they read.
261        let table_ref = self.table_ref()?;
262        let mut input = self.create_table_scan_plan(table_ref).await?;
263        let logical_scan = metric_scan_and_table_id(&input);
264        let has_verified_metric_rewrite = logical_scan.is_some();
265        // A metric logical table's id is part of the identity its own scan reads: two logical tables served
266        // through one physical table prepare two scans of that one table, and the ids are what says they are
267        // two metrics. A missing id on either side is not a difference.
268        if let Some((_, _, table_id)) = &logical_scan {
269            match *logical_scan_id {
270                None => *logical_scan_id = Some(*table_id),
271                Some(first) if first != *table_id => *logical_ids_differ = true,
272                Some(_) => {}
273            }
274        }
275        let scan = match logical_scan {
276            Some((mut scan, predicate, _)) => {
277                // Preserve logical field order and the table restriction on the direct
278                // physical scan.
279                let source_schema = scan.source.schema();
280                let Some(mut ordered_projection) = fields
281                    .iter()
282                    .map(|field| source_schema.index_of(field).ok())
283                    .collect::<Option<Vec<_>>>()
284                else {
285                    return Ok(None);
286                };
287                let original_projection = scan.projection.as_ref();
288                let selected_indices = original_projection
289                    .cloned()
290                    .unwrap_or_else(|| (0..source_schema.fields().len()).collect());
291                for index in selected_indices {
292                    let is_field = fields
293                        .iter()
294                        .any(|field| field == source_schema.field(index).name());
295                    if !is_field && !ordered_projection.contains(&index) {
296                        ordered_projection.push(index);
297                    }
298                }
299                scan.filters.push(predicate);
300                scan = TableScanBuilder::from(scan)
301                    .with_projection(Some(ordered_projection))
302                    .build()
303                    .context(DataFusionPlanningSnafu)?;
304                input = LogicalPlan::TableScan(scan.clone());
305                scan
306            }
307            None => match &input {
308                LogicalPlan::TableScan(scan) => scan.clone(),
309                _ => return Ok(None),
310            },
311        };
312        let table = self.table_from_source(&scan.source)?;
313        let table_meta = &table.table_info().meta;
314        // A table split along a partition column lives in more than one region. The canonical boundary's router
315        // only collects the pieces its own producer holds, so the caller needs this fact to tell a whole-query
316        // label-set answer from one region's share of it.
317        let partitioned = table_meta.partition_column_names().next().is_some();
318        // An engine without a raw-series scanner has no frame to give this node, and by the time the physical
319        // planner asks, the logical plan is already this node: the refusal there is a planning error, not a
320        // fallback. So the engine is checked here. A file-engine table is the concrete case, since its
321        // `SinglePartitionScanner` leaves `raw_series_schema` at the default `None`. A metric-engine selector is
322        // admitted through its verified logical rewrite.
323        if !supports_native_raw_series(&table_meta.engine)
324            || (table_meta.engine == METRIC_ENGINE_NAME && !has_verified_metric_rewrite)
325        {
326            return Ok(None);
327        }
328        // The region's raw-series preflight refuses these, and the physical layer turns that
329        // refusal into an error, so decline this route here instead.
330        let time_index_type = table_meta
331            .schema
332            .timestamp_column()
333            .map(|column| &column.data_type);
334        if time_index_type
335            != Some(&datatypes::prelude::ConcreteDataType::timestamp_millisecond_datatype())
336            || table_meta
337                .options
338                .extra_options
339                .get(store_api::mito_engine_options::APPEND_MODE_KEY)
340                .is_some_and(|value| value.eq_ignore_ascii_case("true"))
341        {
342            return Ok(None);
343        }
344        // A partition column that is not a tag splits one series across regions, and a bare scan cannot
345        // reconcile the fragments; a raw source can, so such a selector is admitted and its input is bound per
346        // source below.
347        let split_series = !table_meta
348            .partition_column_names()
349            .all(|column| tags.iter().any(|tag| tag == column));
350        // This route declares one output column per field, so every field it binds carries one kind:
351        // `Float64`, or the canonical native histogram struct. A field of any other type - an integer, a
352        // `Float32`, a decimal, a string - keeps the existing plan, and so does a statement whose fields
353        // disagree.
354        //
355        // `Float64` fields are answered by the columnar series-index reader when a region prepares one. A
356        // histogram field is not, since the logical plan cannot tell which reader a region will prepare, so
357        // such a selection falls back to the ordinary scan.
358        let Some(field_kind) = uniform_field_kind(
359            fields
360                .iter()
361                .map(|field| Self::field_column_type(input.schema(), field)),
362        ) else {
363            return Ok(None);
364        };
365        if statement_kind.is_some_and(|kind| kind != field_kind) {
366            return Ok(None);
367        }
368        *statement_kind = Some(field_kind);
369        let series_schema = Arc::new(SeriesSchema {
370            fields: fields
371                .iter()
372                .map(|name| FieldSpec {
373                    name: Arc::from(name.as_str()),
374                })
375                .collect::<Vec<_>>()
376                .into(),
377            eval_grid: None,
378        });
379        // The row filter is the selector's own: the time range is added after compiling,
380        // because only the compiler knows whether this occurrence reads a window or one
381        // instant.
382        let mut filters = Self::matchers_to_expr(matchers, input.schema())?;
383        if let LogicalPlan::TableScan(table_scan) = &mut input {
384            table_scan.filters.append(&mut filters);
385        } else {
386            return Ok(None);
387        }
388        Ok(Some((
389            input,
390            series_schema,
391            Some(Arc::from(metric)),
392            time,
393            tags,
394            partitioned,
395            split_series,
396        )))
397    }
398
399    pub(super) async fn try_plan_native_fused(
400        &mut self,
401        prom_expr: &PromExpr,
402        query_engine_state: &QueryEngineState,
403    ) -> Result<Option<LogicalPlan>> {
404        match self
405            .try_plan_native(prom_expr, query_engine_state, FusedOutputFormat::PlainRows)
406            .await?
407        {
408            // A whole statement answers a row table. A frame is what a composition reads from its
409            // operands, so the statement root is never one.
410            Some(NativePlanned::Rows(plan)) => Ok(Some(plan)),
411            _ => Ok(None),
412        }
413    }
414
415    /// The one native attempt at `prom_expr`, in the representation the caller needs from it.
416    ///
417    /// The whole expression is offered first: the compiler folds a range function and the math functions
418    /// over it into one node. What it cannot bind that way - two selectors carrying different field kinds,
419    /// or an operand that is itself a composition - is admitted as a composition of two frames instead.
420    ///
421    /// Both attempts write the planner's selector state, so this restores the context it was called with
422    /// before returning whatever the attempt answered, which lets a refused operand leave nothing behind.
423    ///
424    /// `Box::pin` is here only because a composition and this attempt call each other, which an anonymous
425    /// async future cannot be sized for.
426    fn try_plan_native<'a>(
427        &'a mut self,
428        prom_expr: &'a PromExpr,
429        query_engine_state: &'a QueryEngineState,
430        format: FusedOutputFormat,
431    ) -> BoxFuture<'a, Result<Option<NativePlanned>>> {
432        Box::pin(async move {
433            let saved = self.ctx.clone();
434            let whole = Box::pin(self.try_plan_native_fused_with_context(
435                prom_expr,
436                query_engine_state,
437                format,
438            ))
439            .await;
440            self.ctx = saved.clone();
441            match whole {
442                Ok(Some(planned)) => return Ok(Some(planned)),
443                Ok(None) => {}
444                Err(error) => return Err(error),
445            }
446            let composed = self
447                .try_plan_native_composed_binary(prom_expr, query_engine_state, format)
448                .await;
449            self.ctx = saved;
450            composed
451        })
452    }
453
454    /// Combines two native operands without a legacy join.
455    ///
456    /// Each operand is planned the way the whole expression is and bound as one evaluated series frame.
457    /// What admits the pair is the composition itself: the two grids must agree, and the matching, its
458    /// cardinality, its fill values and the output column's kind must all be ones the kernels answer. A
459    /// shape they refuse declines to the existing plan rather than to an error.
460    ///
461    /// Only a binary expression composes, and only its own two operands are offered below.
462    async fn try_plan_native_composed_binary(
463        &mut self,
464        expr: &PromExpr,
465        query_engine_state: &QueryEngineState,
466        format: FusedOutputFormat,
467    ) -> Result<Option<NativePlanned>> {
468        if !self.native_fused
469            || self.ctx.start != self.ctx.stmt_start
470            || self.ctx.end != self.ctx.stmt_end
471        {
472            return Ok(None);
473        }
474        // Parentheses are not a shape of their own: the operand inside them is the one that
475        // composes.
476        let mut inner = expr;
477        while let PromExpr::Paren(paren) = inner {
478            inner = &paren.expr;
479        }
480        let PromExpr::Binary(binary) = inner else {
481            return Ok(None);
482        };
483        // Each attempt restores context even when a scan or compiler fails, and the second operand
484        // starts from the same context the first one did.
485        let saved = self.ctx.clone();
486        let left = self
487            .try_plan_native(
488                &binary.lhs,
489                query_engine_state,
490                FusedOutputFormat::SeriesFrame,
491            )
492            .await;
493        self.ctx = saved.clone();
494        let Some(NativePlanned::Frame(left)) = left? else {
495            return Ok(None);
496        };
497        let right = self
498            .try_plan_native(
499                &binary.rhs,
500                query_engine_state,
501                FusedOutputFormat::SeriesFrame,
502            )
503            .await;
504        self.ctx = saved;
505        let Some(NativePlanned::Frame(right)) = right? else {
506            return Ok(None);
507        };
508        if left.grid.spec() != right.grid.spec() {
509            return Ok(None);
510        }
511        let NativeFramePlan {
512            plan: left_plan,
513            output: left_output,
514            tags: left_tags,
515            kind: left_kind,
516            time: left_time,
517            grid: left_grid,
518        } = left;
519        let NativeFramePlan {
520            plan: right_plan,
521            output: right_output,
522            tags: right_tags,
523            kind: right_kind,
524            ..
525        } = right;
526        let source_tags = [left_tags, right_tags];
527        let evaluated = |source_index, output: &NativeType| NativeNode {
528            expr: NativeExpr::Input(BoundInput {
529                source_index,
530                output: output.clone(),
531                ordering: SeriesOrdering::Contiguous,
532            }),
533            output: output.clone(),
534        };
535        let tree = match bind_evaluated_binary(
536            binary,
537            evaluated(0, &left_output),
538            evaluated(1, &right_output),
539        ) {
540            Ok(tree) => tree,
541            Err(DataFusionError::NotImplemented(_)) => return Ok(None),
542            Err(error) => return Err(error).context(DataFusionPlanningSnafu),
543        };
544        let NativeExpr::Binary { matching, .. } = &tree.root().expr else {
545            return Ok(None);
546        };
547        let Some(root_kind) = binary_output_field_kind(
548            left_kind,
549            right_kind,
550            matching.op,
551            matching.return_bool,
552            matching.fill,
553        ) else {
554            return Ok(None);
555        };
556        if !native_tree_supported(&tree) {
557            return Ok(None);
558        }
559        // The expression names the value columns, and it is the label the node reports.
560        let expression = expr.to_string();
561        // What a consumer of this composition reads, and the layout the node publishes. The row
562        // layout names one column per value; the frame layout is the evaluated frame this tree's
563        // own root declares, which is what a frame consumer decodes.
564        let metadata = match format {
565            FusedOutputFormat::PlainRows => None,
566            FusedOutputFormat::SeriesFrame => {
567                let Some(tags) = fused_output_tags(tree.root(), &source_tags) else {
568                    return Ok(None);
569                };
570                Some((tree.root().output.clone(), tags))
571            }
572        };
573        let output_schema = match format {
574            FusedOutputFormat::PlainRows => {
575                let Some(schema) = Self::fused_root_schema(
576                    &expression,
577                    &tree,
578                    &source_tags,
579                    &left_time,
580                    root_kind,
581                )?
582                else {
583                    return Ok(None);
584                };
585                schema
586            }
587            FusedOutputFormat::SeriesFrame => {
588                let frame = match FusedSeries::series_frame_schema(&tree) {
589                    Ok(frame) => frame,
590                    // A frame this composition cannot declare is a shape it does not answer.
591                    Err(DataFusionError::Plan(_)) => return Ok(None),
592                    Err(error) => return Err(error).context(DataFusionPlanningSnafu),
593                };
594                Arc::new(
595                    DFSchema::try_from(frame.as_ref().clone()).context(DataFusionPlanningSnafu)?,
596                )
597            }
598        };
599        let Ok(node) = FusedSeries::try_new_with_format(
600            Arc::from(expression.as_str()),
601            tree,
602            FusedSeriesBinding {
603                grid: Arc::clone(&left_grid),
604                time_index: left_time.clone(),
605                tags: Vec::new(),
606                metric_name: None,
607            },
608            vec![left_plan, right_plan],
609            output_schema,
610            format,
611        ) else {
612            return Ok(None);
613        };
614        let plan = LogicalPlan::Extension(Extension {
615            node: Arc::new(node),
616        });
617        Ok(Some(native_planned(
618            plan, metadata, root_kind, left_time, left_grid,
619        )))
620    }
621
622    /// Plans `prom_expr` as one native node, or returns `None` to keep the existing plan.
623    ///
624    /// The expression names the value columns; the compiler's bound tree and selector schemas
625    /// determine their values. The existing planner is not consulted for capability or schema approval.
626    ///
627    /// The route is offered a whole expression because the compiler folds a range function and the math
628    /// functions over it into one tree: offering a sub-expression would compile a tree that computes
629    /// something the reader did not write. The node's table, time index, tag and field columns come from
630    /// the planner's resolved selector context, which is the raw series schema the tree's input is
631    /// compiled against. Selectors with a `__field__` matcher keep legacy planning.
632    ///
633    /// `None` is not a failure: the caller plans the query with the existing planner as if this method did
634    /// not exist.
635    async fn try_plan_native_fused_with_context(
636        &mut self,
637        prom_expr: &PromExpr,
638        query_engine_state: &QueryEngineState,
639        format: FusedOutputFormat,
640    ) -> Result<Option<NativePlanned>> {
641        if !self.native_fused {
642            return Ok(None);
643        }
644        // The expression names the value columns of every rows layout this attempt publishes, and the
645        // node's own label follows the same text. It is the whole statement's expression even when a
646        // subquery root compiles its inner one, because that is the statement the reader wrote.
647        let expression = prom_expr.to_string();
648        // A range selector returns raw samples, which have no evaluation grid to bind. A subquery root
649        // instead returns its inner expression on the subquery's child grid, and a range query has no grid
650        // to bind a matrix root to.
651        let subquery_root = root_subquery(prom_expr);
652        if prom_expr.value_type() == ValueType::Matrix
653            && (subquery_root.is_none() || self.ctx.start != self.ctx.end)
654        {
655            return Ok(None);
656        }
657
658        let Some(stmt) = self.native_statement(prom_expr) else {
659            return Ok(None);
660        };
661        // The subquery root's inner expression is compiled on the child grid, with the statement left
662        // untouched: `@ start()` and `@ end()` inside it resolve against the statement's bounds. A statement
663        // whose grid cannot be built keeps the existing plan.
664        let child_grid = if let Some(subquery) = subquery_root {
665            let Ok(outer) = statement_grid(&stmt) else {
666                return Ok(None);
667            };
668            let Some(child) =
669                subquery_child_grid(&stmt, &outer, subquery).context(DataFusionPlanningSnafu)?
670            else {
671                return Ok(None);
672            };
673            Some(child.grid)
674        } else {
675            None
676        };
677        let effective_expr = match subquery_root {
678            Some(subquery) => subquery.expr.as_ref(),
679            None => &stmt.expr,
680        };
681        let mut selectors = Vec::new();
682        // The walk starts outside any `rate` or `increase`, and records that per selector as it
683        // descends: a selector is delta-temporality-sensitive only where one of those calls reads
684        // it, which is what keeps `rate(a) / b` admissible when only `b` carries the marker.
685        let mut set_operations = Vec::new();
686        if !collect_selectors_with_set_operations(
687            &stmt,
688            effective_expr,
689            false,
690            &mut selectors,
691            &mut set_operations,
692        ) {
693            return Ok(None);
694        }
695        // The compiler decides which calls and shapes this route answers: a name it has no kernel for comes
696        // back as `NotImplemented`, which is a decline below.
697        let Ok(statement) = statement_grid(&stmt) else {
698            return Ok(None);
699        };
700        // The one grid every lowering path below binds: a subquery root is compiled on its child
701        // grid, and the rows it publishes carry that grid, so the split, the boundary and the
702        // segment nodes have to publish on it too rather than on the statement's.
703        let grid = child_grid.unwrap_or(statement);
704        if selectors.is_empty() {
705            let mut compile_stmt = stmt.clone();
706            compile_stmt.expr = effective_expr.clone();
707            let tree = match compile_statement_with_grid(&compile_stmt, Arc::clone(&grid)) {
708                Ok(tree) => tree,
709                Err(DataFusionError::NotImplemented(_)) => return Ok(None),
710                Err(error) => return Err(error).context(DataFusionPlanningSnafu),
711            };
712            // A frame operand is an evaluated sample root: a composition matches series, and a
713            // scalar root - `2`, `time()` - carries one value and no labels, so those keep the
714            // existing plan rather than becoming a frame the matcher cannot pair.
715            let evaluated = matches!(
716                &tree.root().output,
717                NativeType::Samples(schema) if schema.eval_grid.is_some()
718            );
719            if format == FusedOutputFormat::SeriesFrame && !evaluated {
720                return Ok(None);
721            }
722            // Bind only input tags: this data-free tree has no input, and its tags belong to its
723            // output schema.
724            let Some(output_tags) = fused_output_tags(tree.root(), &[]) else {
725                return Ok(None);
726            };
727
728            let Some(values) = native_root_fields(tree.root()) else {
729                return Ok(None);
730            };
731            // A label named `time` is the one collision the default time column can have: the
732            // value columns are named after the expression, so they never take that name. The
733            // time column is this route's own synthetic name - no label or value is renamed - so
734            // a statement whose output already holds a `time` column publishes its grid under the
735            // first free `native_time_N` instead of dropping or renaming the label.
736            let value_names = expression_field_names(&expression, &values);
737            let time_index = if value_names
738                .iter()
739                .chain(&output_tags)
740                .any(|name| name == DEFAULT_TIME_INDEX_COLUMN)
741            {
742                (0usize..)
743                    .map(|index| format!("native_time_{index}"))
744                    .find(|candidate| {
745                        !value_names
746                            .iter()
747                            .chain(&output_tags)
748                            .any(|name| name == candidate)
749                    })
750                    .expect("the time column candidate sequence is unbounded")
751            } else {
752                DEFAULT_TIME_INDEX_COLUMN.to_string()
753            };
754            // The metadata a consumer of a frame operand reads: the evaluated layout this tree's
755            // root declares on the statement grid, and the labels a `vector(s)` reports.
756            let metadata = match format {
757                FusedOutputFormat::PlainRows => None,
758                FusedOutputFormat::SeriesFrame => {
759                    Some((tree.root().output.clone(), output_tags.clone()))
760                }
761            };
762            // A data-free tree reads no input, so every field it answers is a float.
763            let output_schema = match format {
764                FusedOutputFormat::PlainRows => fused_output_schema(
765                    &expression,
766                    &values,
767                    &with_row_name_column(tree.root(), output_tags.clone()),
768                    &time_index,
769                    FieldKind::Float,
770                )?,
771                FusedOutputFormat::SeriesFrame => {
772                    let frame =
773                        FusedSeries::series_frame_schema(&tree).context(DataFusionPlanningSnafu)?;
774                    Arc::new(
775                        DFSchema::try_from(frame.as_ref().clone())
776                            .context(DataFusionPlanningSnafu)?,
777                    )
778                }
779            };
780            let node = FusedSeries::try_new_with_format(
781                Arc::from(expression.as_str()),
782                tree,
783                FusedSeriesBinding {
784                    grid: Arc::clone(&grid),
785                    time_index: time_index.clone(),
786                    tags: Vec::new(),
787                    metric_name: None,
788                },
789                Vec::new(),
790                output_schema,
791                format,
792            )
793            .context(DataFusionPlanningSnafu)?;
794            let plan = LogicalPlan::Extension(Extension {
795                node: Arc::new(node),
796            });
797            return Ok(Some(native_planned(
798                plan,
799                metadata,
800                FieldKind::Float,
801                time_index,
802                grid,
803            )));
804        }
805        let original_context = self.ctx.clone();
806        let preparation = async {
807            let mut prepared: Vec<PreparedInput> = Vec::new();
808            // The first metric logical-table id a selector's rewrite carried, and whether a later one
809            // carried a different id. See the `cross_table` use below.
810            let mut logical_scan_id: Option<u32> = None;
811            let mut logical_ids_differ = false;
812            // The kind every bound field carries. A statement declares one column per field, so
813            // selectors that disagree have no column to declare and keep the existing plan.
814            let mut statement_kind: Option<FieldKind> = None;
815            for (selector, under_rate_or_increase) in &selectors {
816                self.ctx = original_context.clone();
817                // These matchers are alternatives the one scan below the node cannot represent, so the
818                // query keeps the plan the existing path builds for it.
819                if !selector.matchers.or_matchers.is_empty() {
820                    return Ok(None);
821                }
822                // A selector that names no metric is answered by enumerating the schema's logical metric
823                // tables: one input per metric, each reading its own region, so every series keeps the
824                // identity the expression itself cannot name.
825                if discovers_metric_name(selector) {
826                    let name_matchers = selector.matchers.find_matchers(METRIC_NAME);
827                    let mut ordinary_matchers = selector.matchers.clone();
828                    ordinary_matchers
829                        .matchers
830                        .retain(|matcher| matcher.name != METRIC_NAME);
831                    // Name matchers constrain discovered table names rather than row columns.
832                    // Supplying a temporary name lets preprocessing reset the context and apply
833                    // schema/database and ordinary matchers without its expected NoMetricMatcher.
834                    let matchers = match self
835                        .preprocess_label_matchers(&ordinary_matchers, &Some(String::new()))
836                    {
837                        Ok(m) => m,
838                        Err(_) => return Ok(None),
839                    };
840                    let effective_schema = self
841                        .ctx
842                        .schema_name
843                        .clone()
844                        .unwrap_or_else(|| self.table_provider.query_ctx().current_schema());
845                    // Authorization is decided before anything is read: a table the caller may not
846                    // see never becomes a source, so its name reaches neither the plan nor an error.
847                    let scope = self.table_provider.query_ctx().metric_discovery_scope();
848                    if matches!(scope, MetricDiscoveryScope::Unavailable) {
849                        return Ok(None);
850                    }
851                    let mut metrics = self
852                        .table_provider
853                        .logical_metric_tables(&effective_schema)
854                        .await
855                        .map_err(|error| DataFusionError::External(Box::new(error)))
856                        .context(DataFusionPlanningSnafu)?;
857                    if let MetricDiscoveryScope::Allowed(allowed) = scope {
858                        let catalog = self.table_provider.query_ctx().current_catalog();
859                        // Borrowed keys, so a wide allowlist is one pass to build and one lookup
860                        // per metric rather than a scan of the allowlist for each of them.
861                        let permitted = allowed
862                            .iter()
863                            .map(|target| {
864                                (
865                                    target.catalog.as_str(),
866                                    target.schema.as_str(),
867                                    target.table.as_str(),
868                                )
869                            })
870                            .collect::<std::collections::HashSet<_>>();
871                        metrics.retain(|table| {
872                            let info = table.table_info();
873                            // Reject metadata that disagrees with where the table was enumerated.
874                            info.catalog_name == catalog
875                                && info.schema_name == effective_schema
876                                && permitted.contains(&(
877                                    info.catalog_name.as_str(),
878                                    info.schema_name.as_str(),
879                                    info.name.as_str(),
880                                ))
881                        });
882                    }
883                    metrics.retain(|table| {
884                        name_matchers
885                            .iter()
886                            .all(|matcher| matcher.is_match(&table.table_info().name))
887                    });
888                    // A label a table does not carry reads as the empty string on every one of its
889                    // rows, so a matcher that rejects the empty string cannot match anything there.
890                    metrics.retain(|table| {
891                        let schema = table.schema();
892                        matchers.matchers.iter().all(|matcher| {
893                            matcher.is_match("")
894                                || schema.column_schema_by_name(&matcher.name).is_some()
895                        })
896                    });
897                    metrics.sort_by_key(|table| table.table_info().name.clone());
898                    if metrics.len() > MAX_DISCOVERED_METRICS {
899                        return Err(DataFusionError::Plan(format!(
900                            "the selector matches {} metric tables, over the {MAX_DISCOVERED_METRICS} one query may scan; narrow it",
901                            metrics.len()
902                        )))
903                        .context(DataFusionPlanningSnafu);
904                    }
905                    if metrics.is_empty() {
906                        // Nothing matches the selector, so the query still has an answer: the empty vector.
907                        // Planning it here keeps a nameless selector that matches nothing from reaching the
908                        // existing planner, which has no table to bind and raises `TableNameNotFound`.
909                        //
910                        // An empty raw series frame is an ordinary input to the node; multi-input placement
911                        // and partition normalization are decided after compilation. A `__field__` matcher
912                        // is declined for a scan this route can read, and the same refusal keeps the empty
913                        // input from claiming a field layout the matcher would have decided.
914                        if self.ctx.field_column_matcher.is_some() {
915                            return Ok(None);
916                        }
917                        prepared.push(empty_discovered_input(
918                            self.ctx
919                                .time_index_column
920                                .clone()
921                                .unwrap_or_else(|| DEFAULT_TIME_INDEX_COLUMN.to_string()),
922                        )?);
923                        continue;
924                    }
925                    // One compiler source per selector: the discovered scans become one union
926                    // input, so the compiled tree still reads what the planner prepared.
927                    let mut sources = Vec::with_capacity(metrics.len());
928                    let mut selector_metadata: Option<DiscoveredSelectorMetadata> = None;
929                    // The union reads every discovered metric's region, so one partitioned metric
930                    // makes the whole input partitioned.
931                    let mut discovered_partitioned = false;
932                    let mut discovered_split_series = false;
933                    for table in metrics {
934                        self.ctx.table_name = Some(table.table_info().name.clone());
935                        if self.setup_context().await?.is_some() {
936                            return Ok(None);
937                        }
938                        let Some((
939                            scan,
940                            schema,
941                            metric,
942                            time,
943                            mut tags,
944                            partitioned,
945                            split_series,
946                        )) = self
947                            .prepare_one_scan(
948                                matchers.clone(),
949                                *under_rate_or_increase,
950                                &mut logical_scan_id,
951                                &mut logical_ids_differ,
952                                &mut statement_kind,
953                            )
954                            .await?
955                        else {
956                            return Ok(None);
957                        };
958                        discovered_partitioned |= partitioned;
959                        discovered_split_series |= split_series;
960                        // The union reads every discovered metric, so it is region-local only when
961                        // every metric it reads is.
962                        let Some(metric) = metric else {
963                            return Ok(None);
964                        };
965                        // The expression names no metric, so each source reports its own: the tag is
966                        // what tells two metrics with equal ordinary labels apart, and it is what a
967                        // grouping by the name groups on. It is part of the series' identity rather
968                        // than of how a result is displayed, so every plan declares it.
969                        if !tags.iter().any(|tag| tag == METRIC_NAME) {
970                            tags.push(METRIC_NAME.to_string());
971                        }
972                        let fields = schema
973                            .fields
974                            .iter()
975                            .map(|field| field.name.to_string())
976                            .collect();
977                        sources.push(LogicalPlan::Extension(Extension {
978                            node: Arc::new(
979                                RawSeriesSource::try_new(
980                                    metric.clone(),
981                                    tags.clone(),
982                                    fields,
983                                    scan,
984                                )
985                                .context(DataFusionPlanningSnafu)?,
986                            ),
987                        }));
988                        if let Some((first_schema, _, union_tags, _)) = &mut selector_metadata {
989                            let first_fields = first_schema
990                                .fields
991                                .iter()
992                                .map(|field| field.name.as_ref())
993                                .collect::<Vec<_>>();
994                            let metric_fields = schema
995                                .fields
996                                .iter()
997                                .map(|field| field.name.as_ref())
998                                .collect::<Vec<_>>();
999                            if first_fields != metric_fields {
1000                                return Err(DataFusionError::Plan(format!(
1001                                    "discovered metric {} has an unsupported field layout; expected {:?}, found {:?}",
1002                                    table.table_info().name,
1003                                    first_fields,
1004                                    metric_fields,
1005                                )))
1006                                .context(DataFusionPlanningSnafu);
1007                            }
1008                            union_tags.extend(tags);
1009                            union_tags.sort();
1010                            union_tags.dedup();
1011                        } else {
1012                            selector_metadata = Some((schema, time, tags, metric));
1013                        }
1014                    }
1015                    let Some((schema, time, mut tags, single_metric)) = selector_metadata else {
1016                        return Ok(None);
1017                    };
1018                    tags.sort();
1019                    tags.dedup();
1020                    let (union, metric) = if sources.len() == 1 {
1021                        (sources.pop().unwrap(), Some(single_metric))
1022                    } else {
1023                        (
1024                            LogicalPlan::Union(
1025                                Union::try_new_with_loose_types(
1026                                    sources.into_iter().map(Arc::new).collect(),
1027                                )
1028                                .context(DataFusionPlanningSnafu)?,
1029                            ),
1030                            None,
1031                        )
1032                    };
1033                    prepared.push((
1034                        union,
1035                        schema,
1036                        metric,
1037                        time,
1038                        tags,
1039                        discovered_partitioned,
1040                        discovered_split_series,
1041                    ));
1042                    continue;
1043                }
1044                let matchers =
1045                    match self.preprocess_label_matchers(&selector.matchers, &selector.name) {
1046                        Ok(m) => m,
1047                        Err(_) => return Ok(None),
1048                    };
1049                if self.setup_context().await?.is_some() {
1050                    return Ok(None);
1051                }
1052                let Some(one) = self
1053                    .prepare_one_scan(
1054                        matchers,
1055                        *under_rate_or_increase,
1056                        &mut logical_scan_id,
1057                        &mut logical_ids_differ,
1058                        &mut statement_kind,
1059                    )
1060                    .await?
1061                else {
1062                    return Ok(None);
1063                };
1064                prepared.push(one);
1065            }
1066            Ok(Some((prepared, logical_ids_differ, statement_kind)))
1067        }
1068        .await;
1069        self.ctx = original_context;
1070        let Some((mut prepared, logical_ids_differ, statement_kind)) = preparation? else {
1071            return Ok(None);
1072        };
1073        // `absent_over_time` reads its window through a fold that keeps the metric name, so the segment that
1074        // runs it reports names across a boundary. A nameless selector that discovery expands into more
1075        // than one metric binds no single name for that boundary, and the fused node refuses a tree
1076        // declaring `__name__` without one. A fold that dropped the name would plan, but it would read two
1077        // metrics sharing their ordinary labels as one series, so the route declines.
1078        //
1079        // A selector that matched no table is not that shape: its typed empty input holds no series.
1080        if reads_presence(prom_expr)
1081            && prepared
1082                .iter()
1083                .any(|(scan, _, metric, ..)| !is_empty_discovered_input(scan) && metric.is_none())
1084        {
1085            return Ok(None);
1086        }
1087        // Selectors over one table share one region, so the node runs there over every scan. When they read
1088        // more than one table, each scan answers from its own region and the node runs above them; see
1089        // `RawSeriesSource`. A metric logical table's id is part of the identity it reads: two ids are two
1090        // metrics even when one physical table holds both.
1091        //
1092        // The typed empty input of a selector that matched no table reads no region and counts as no
1093        // second table.
1094        let cross_table = !same_table_scans(
1095            prepared
1096                .iter()
1097                .map(|(scan, ..)| scan)
1098                .filter(|scan| !is_empty_discovered_input(scan)),
1099        ) || logical_ids_differ;
1100        // A multi-selector tree over a partitioned table has no region-local placement, but it does have a
1101        // frontend one - each occurrence reads the table through its own raw source and the node matches
1102        // above every region's contribution - so the tree is admitted on both routes.
1103        //
1104        // An empty selector has no table layout of its own: the set operator pairs its two sides' fields by
1105        // position, so an operand that reads no real input is laid out by the first real selector in the
1106        // other operand. That layout reaches every empty selector of the operand, nested set operations
1107        // included; a layout taken from the statement's first real input is not that sibling's and can
1108        // carry a different number of fields. With no such operand above it, an empty selector takes the
1109        // statement's first real layout, and the default layout of [`empty_discovered_input`] when every
1110        // selector is empty.
1111        let local_layouts = local_empty_layouts(&set_operations, &prepared);
1112        let statement_layout = prepared
1113            .iter()
1114            .find(|(scan, ..)| !is_empty_discovered_input(scan))
1115            .map(|(_, schema, ..)| Arc::clone(schema));
1116        for index in 0..prepared.len() {
1117            if !is_empty_discovered_input(&prepared[index].0) {
1118                continue;
1119            }
1120            let Some(schema) = local_layouts[index]
1121                .map(|sibling| Arc::clone(&prepared[sibling].1))
1122                .or_else(|| statement_layout.as_ref().map(Arc::clone))
1123            else {
1124                continue;
1125            };
1126            prepared[index].0 = empty_discovered_frame(&schema)?;
1127            prepared[index].1 = Arc::clone(&schema);
1128        }
1129        // A real input names the output's time index and, on one table, binds every scan.
1130        let Some((_, _, metric, time, tags, _, _)) = prepared
1131            .iter()
1132            .find(|(scan, ..)| !is_empty_discovered_input(scan))
1133            .or_else(|| prepared.first())
1134        else {
1135            return Ok(None);
1136        };
1137        let (metric, time, tags) = (metric.clone(), time.clone(), tags.clone());
1138        // The compiler binds one input per selector in the same pre-order `collect_selectors`
1139        // walks, so position i of both lists is the same occurrence. This is the guard that the
1140        // two walks agree: a mismatch is a compiler defect, not a query this route can plan.
1141        let identities: Vec<(Option<String>, Matchers, i64, Option<i64>)> = selectors
1142            .iter()
1143            .map(|(selector, _)| {
1144                let offset_ms = selector
1145                    .offset
1146                    .as_ref()
1147                    .map(|o| match o {
1148                        promql_parser::parser::Offset::Pos(d) => d.as_millis() as i64,
1149                        promql_parser::parser::Offset::Neg(d) => -(d.as_millis() as i64),
1150                    })
1151                    .unwrap_or_default();
1152                Ok((
1153                    selector.name.clone(),
1154                    selector.matchers.clone(),
1155                    offset_ms,
1156                    // The compiler records the raw anchor separately from the offset; compare
1157                    // that same canonical identity rather than the derived anchor-minus-offset.
1158                    self.at_ref_time(&selector.at, &None)?,
1159                ))
1160            })
1161            .collect::<Result<Vec<_>>>()?;
1162        let bind_index = std::cell::Cell::new(0usize);
1163        let mut compile_stmt = stmt.clone();
1164        compile_stmt.expr = effective_expr.clone();
1165        let compiled = match compile_selectors_with_grid(
1166            &compile_stmt,
1167            &|req| {
1168                let i = bind_index.get();
1169                bind_index.set(i + 1);
1170                let (Some((_, schema, ..)), Some(identity)) = (prepared.get(i), identities.get(i))
1171                else {
1172                    return Err(DataFusionError::Internal(
1173                        "a selector was bound that the planner did not prepare".into(),
1174                    ));
1175                };
1176                if *identity
1177                    != (
1178                        req.metric.clone(),
1179                        req.matchers.clone(),
1180                        req.offset_ms,
1181                        req.at_ms,
1182                    )
1183                {
1184                    return Err(DataFusionError::Internal(
1185                        "the compiler and the planner walk the selectors differently".into(),
1186                    ));
1187                }
1188                Ok(Arc::clone(schema))
1189            },
1190            NATIVE_ORDERING,
1191            Arc::clone(&grid),
1192            // The kind the prepared scans report for the statement's fields. An aggregate binds the
1193            // state its input's kind implies, so a `sum` over a native-histogram column has to be
1194            // compiled with that kind: bound as a float it would fold the payload as numbers. A
1195            // statement that reads no table reports `None` here, which is the data-free case.
1196            statement_kind,
1197        ) {
1198            Ok(v) => v,
1199            // The compiler refusing a shape is this route declining it.
1200            Err(DataFusionError::NotImplemented(_)) => return Ok(None),
1201            Err(e) => return Err(e).context(DataFusionPlanningSnafu),
1202        };
1203        if compiled.inputs.len() != prepared.len() {
1204            return Err(DataFusionError::Internal(
1205                "the compiled tree reads a different number of inputs than the planner prepared"
1206                    .into(),
1207            ))
1208            .context(DataFusionPlanningSnafu);
1209        }
1210        for (index, (compiled_input, (scan, _, _, time, _, _, _))) in
1211            compiled.inputs.iter().zip(prepared.iter_mut()).enumerate()
1212        {
1213            if compiled_input.source_index != index {
1214                return Ok(None);
1215            }
1216            // The range this selector reads is the compiler's own: a window and an instant differ in which
1217            // side of the lookback or range their scan starts on, and an anchor can move the whole range
1218            // outside the statement's. Two occurrences over different windows or offsets read different
1219            // rows even when nothing else about them differs.
1220            let (start, end, inclusive) = compiled_input
1221                .requirement
1222                .raw_scan_bounds()
1223                .context(DataFusionPlanningSnafu)?;
1224            let filter = scan_time_filter(start, end, inclusive, time);
1225            if let LogicalPlan::Extension(extension) = scan
1226                && extension.node.as_any().is::<RawSeriesSource>()
1227            {
1228                let mut inputs = extension
1229                    .node
1230                    .inputs()
1231                    .into_iter()
1232                    .cloned()
1233                    .collect::<Vec<_>>();
1234                let Some(LogicalPlan::TableScan(table_scan)) = inputs.first_mut() else {
1235                    return Err(DataFusionError::Internal(
1236                        "RawSeriesSource input is not a TableScan".into(),
1237                    ))
1238                    .context(DataFusionPlanningSnafu);
1239                };
1240                table_scan.filters.push(filter);
1241                let replacement = extension
1242                    .node
1243                    .with_exprs_and_inputs(vec![], inputs)
1244                    .context(DataFusionPlanningSnafu)?;
1245                *scan = LogicalPlan::Extension(Extension { node: replacement });
1246            } else if let LogicalPlan::Union(union) = scan {
1247                // A discovered selector's sources each read their own region, and the metric
1248                // engine checks that two logical metrics agree on their time column's unit, not on
1249                // its name. So each bound is built from the column that source actually carries.
1250                for child in &mut union.inputs {
1251                    let LogicalPlan::Extension(extension) = child.as_ref() else {
1252                        return Err(DataFusionError::Internal(format!(
1253                            "Union child at {index} is not a RawSeriesSource for time-bound pushdown"
1254                        )))
1255                        .context(DataFusionPlanningSnafu);
1256                    };
1257                    let source = extension
1258                        .node
1259                        .as_any()
1260                        .downcast_ref::<RawSeriesSource>()
1261                        .ok_or_else(|| {
1262                            DataFusionError::Internal(format!(
1263                                "Union child at {index} is not a RawSeriesSource for time-bound pushdown"
1264                            ))
1265                        })
1266                        .context(DataFusionPlanningSnafu)?;
1267                    let mut inputs = source.inputs().into_iter().cloned().collect::<Vec<_>>();
1268                    let Some(LogicalPlan::TableScan(table_scan)) = inputs.first_mut() else {
1269                        return Err(DataFusionError::Internal(format!(
1270                            "RawSeriesSource child at {index} is not backed by a TableScan"
1271                        )))
1272                        .context(DataFusionPlanningSnafu);
1273                    };
1274                    let source_time = table_scan
1275                        .projected_schema
1276                        .fields()
1277                        .iter()
1278                        .find(|field| {
1279                            matches!(
1280                                field.data_type(),
1281                                datafusion::arrow::datatypes::DataType::Timestamp(_, _)
1282                            )
1283                        })
1284                        .map(|field| field.name().clone());
1285                    let Some(source_time) = source_time else {
1286                        return Err(DataFusionError::Internal(format!(
1287                            "RawSeriesSource child at {index} has no timestamp column"
1288                        )))
1289                        .context(DataFusionPlanningSnafu);
1290                    };
1291                    let source_filter = scan_time_filter(start, end, inclusive, &source_time);
1292                    table_scan.filters.push(source_filter);
1293                    let replacement = extension
1294                        .node
1295                        .with_exprs_and_inputs(vec![], inputs)
1296                        .context(DataFusionPlanningSnafu)?;
1297                    *child = Arc::new(LogicalPlan::Extension(Extension { node: replacement }));
1298                }
1299            } else if let LogicalPlan::TableScan(table_scan) = scan {
1300                table_scan.filters.push(filter);
1301            } else if let LogicalPlan::EmptyRelation(_) = scan {
1302                // The typed empty input has no scan to constrain.
1303            } else {
1304                return Err(DataFusionError::Internal(format!(
1305                    "the child at {index} is not the table scan this route prepared"
1306                )))
1307                .context(DataFusionPlanningSnafu);
1308            }
1309        }
1310        let source_tags = prepared
1311            .iter()
1312            .map(|(_, _, _, _, tags, _, _)| tags.clone())
1313            .collect::<Vec<_>>();
1314        // The complete runtime label set of each input: a scan bound to one metric names every series it
1315        // hands over, so `__name__` is one of its labels even though it is not a tag column. Rewriting the
1316        // name of a named scan is therefore a rewrite of an existing label, and a discovered source
1317        // declares the name among its tags itself.
1318        let runtime_source_tags = prepared
1319            .iter()
1320            .map(|(_, _, metric, _, tags, _, _)| {
1321                let mut tags = tags.clone();
1322                if metric.is_some() && !tags.iter().any(|tag| tag == METRIC_NAME) {
1323                    tags.push(METRIC_NAME.to_string());
1324                }
1325                tags
1326            })
1327            .collect::<Vec<_>>();
1328        // Whether any input's table is split into regions along a partition column. Only the canonical
1329        // boundary claims a whole-query label-set answer, and a region-local producer cannot see the pieces
1330        // another region holds.
1331        let any_partitioned = prepared.iter().any(|input| input.5);
1332        // Admission and placement are separate: `independent_scan_pair` admits nested native matches, while
1333        // the physical locality classification decides whether their inputs need gathering or segmentation.
1334        // The pass puts a [`NativeExpr::Merge`] where a label rewrite can give two series one label set, so
1335        // a tree with no collapsing rewrite keeps every partition.
1336        let tree = match promql::native::canonicalize::merge_label_rewrites(
1337            &compiled.tree,
1338            &runtime_source_tags,
1339        ) {
1340            Ok(tree) => tree,
1341            Err(_) => return Ok(None),
1342        };
1343        let root = tree.root();
1344        // The placement facts the split and the segmentation below are chosen from, and the same
1345        // facts that say whether one node can run over the scans at all.
1346        let per_partition = region_local_segment(root);
1347        let locality = input_locality(root);
1348        let computed_key_case =
1349            matches!(locality, InputLocality::SinglePartition) && matching_operands_drop_key(root);
1350        let required_placement = !per_partition || computed_key_case;
1351        // The node reads more than one input when the tree has more than one selector occurrence: the
1352        // compiler binds one input per occurrence. Each is bound to its own source where the plan is split
1353        // over regions, or to one bare scan per occurrence where a region can run the node itself.
1354        let multi_input = selectors.len() > 1;
1355        // A region runs one node over its own scans only when the table it reads is not split into
1356        // regions and the tree's root is per-partition work: a partitioned table's region reads
1357        // neither the other scans nor the fragments another region holds, and a whole-vector
1358        // consumer has no region-local placement. Such a tree runs above the regions, and then each
1359        // occurrence reads through its own raw source. An empty frame likewise requires sourced
1360        // scans: physical planning accepts either all frames or all bare scans, not a mixture.
1361        // With a distributed planner every read is planned above the regions, so each occurrence
1362        // reads through its own source.
1363        let spans_regions = query_engine_state.with_dist_planner();
1364        let per_source_inputs = cross_table
1365            || spans_regions
1366            || (multi_input
1367                && (any_partitioned
1368                    || required_placement
1369                    || prepared
1370                        .iter()
1371                        .any(|(scan, ..)| is_empty_discovered_input(scan))));
1372        // A segment carries one source's identity. Keeping each occurrence's scan and metadata
1373        // aligned here lets the cutting step name that source independently of selector count.
1374        // Read the split-series fact before `prepared` is consumed by the child mapping below.
1375        let any_split_series = prepared.iter().any(|input| input.6);
1376        let bare_scans = prepared
1377            .iter()
1378            .map(|(scan, ..)| scan.clone())
1379            .collect::<Vec<_>>();
1380        let per_source = prepared
1381            .iter()
1382            .map(|(_, _, metric, time_index, tags, _, _)| {
1383                (metric.clone(), time_index.clone(), tags.clone())
1384            })
1385            .collect::<Vec<_>>();
1386        let children = prepared
1387            .into_iter()
1388            .map(|(scan, schema, metric, _, tags, _, split_series)| {
1389                // A discovered selector already carries its own sources: a single metric is one
1390                // `RawSeriesSource`, several are a `Union` of them, and each names the metric it
1391                // reads. Wrapping either again would nest a source in a source.
1392                let already_sourced = matches!(&scan, LogicalPlan::Union(_))
1393                    || matches!(
1394                        &scan,
1395                        LogicalPlan::Extension(extension)
1396                            if extension.node.as_any().is::<RawSeriesSource>()
1397                    );
1398                // The typed empty frame of a selector that matched no table is already the input: it reads
1399                // no region and has no metric to bind, so it stays itself on both routes.
1400                if is_empty_discovered_input(&scan) {
1401                    return Ok(scan);
1402                }
1403                // A scan stays bare only where a region runs the node over it. A plan split over regions
1404                // reads every input through a raw source: the source names each region's half and
1405                // reconciles the fragments of a series several regions hold. A partition that splits one
1406                // series across regions has to be read through a raw source even where no split is
1407                // planned, since a bare scan would hand a region only its own fragment.
1408                if (!per_source_inputs && !split_series) || already_sourced {
1409                    return Ok(scan);
1410                }
1411                let Some(metric) = metric else {
1412                    return Err(DataFusionError::Internal(
1413                        "a prepared selector has no metric name".into(),
1414                    ));
1415                };
1416                let fields = schema
1417                    .fields
1418                    .iter()
1419                    .map(|field| field.name.to_string())
1420                    .collect();
1421                Ok(LogicalPlan::Extension(Extension {
1422                    node: Arc::new(RawSeriesSource::try_new(metric, tags, fields, scan)?),
1423                }))
1424            })
1425            .collect::<std::result::Result<Vec<_>, DataFusionError>>()
1426            .context(DataFusionPlanningSnafu)?;
1427        // A canonical boundary routes each label set to one owner above its own producer, and a
1428        // region-local producer only sees the partitions of the region it runs in.
1429        //
1430        // A partitioned table's region read has no raw-series frame to give a canonical producer, so
1431        // physical planning cannot convert the node and the query fails after the plan is
1432        // committed, so such a statement declines here.
1433        //
1434        // The other placement is not a decline. A canonical boundary whose pieces of one label set
1435        // can be spread over regions reads `RawSeriesSource` children, one per region: the analyzer
1436        // expands them into merge scans, and the producer runs on the frontend above every region
1437        // with its canonical router above all of them, so each label set is collected from every
1438        // region's contribution, and a collision across regions is reported as Prometheus reports
1439        // it.
1440        //
1441        // A tree with no canonical merge claims no label-set answer, so it is untouched: a
1442        // per-series query on a partitioned table keeps fusing.
1443        if !spans_regions && any_partitioned && contains_canonical_merge(root) {
1444            return Ok(None);
1445        }
1446        // The kind the tree's root answers with, which every output column follows. It is not the kind the
1447        // inputs carry: `count_over_time`, `histogram_count` and `timestamp` reduce a histogram to a
1448        // float, while a selector, a histogram-answering range function and a label rewrite pass it on.
1449        // A shape whose kind cannot be named keeps the existing plan rather than declaring a column the
1450        // first batch might not fill.
1451        let root_kind = match statement_kind {
1452            Some(FieldKind::Histogram) => {
1453                // A histogram answer standing on a canonical merge would run through the canonical
1454                // boundary carrying histogram frames, a pairing nothing exercises yet, so such a
1455                // statement keeps the existing plan. Every merge counts, not only a root one.
1456                if merge_answers_histogram(root, FieldKind::Histogram) {
1457                    return Ok(None);
1458                }
1459                match root.output_field_kind(Some(FieldKind::Histogram)) {
1460                    Some(root_kind) => root_kind,
1461                    None => return Ok(None),
1462                }
1463            }
1464            Some(FieldKind::Float) | None => FieldKind::Float,
1465        };
1466        let frame_metadata = if format == FusedOutputFormat::SeriesFrame {
1467            let NativeType::Samples(schema) = &root.output else {
1468                return Ok(None);
1469            };
1470            if schema.eval_grid.is_none() {
1471                return Ok(None);
1472            }
1473            // A segment publishes frames, so it reports no name column of its own.
1474            let Some(output_tags) = fused_output_tags(root, &source_tags) else {
1475                return Ok(None);
1476            };
1477            Some((root.output.clone(), output_tags))
1478        } else {
1479            None
1480        };
1481        // A tree over more than one input needs no split: each input already answers from its own source,
1482        // and the one node above them folds every partition in one execution. The aggregate split folds
1483        // float state, and a node reading several sources runs over frames it reconciled rather than over
1484        // its own scans, so a histogram keeps the existing plan for both. The kind entering each
1485        // aggregate is what decides, not the shape of the root: `sum(h) * 2` has a binary root.
1486        if let Some(kind @ FieldKind::Histogram) = statement_kind
1487            && ((multi_input && per_source_inputs) || aggregate_reads_histogram(root, kind))
1488        {
1489            return Ok(None);
1490        }
1491        // The split keeps its prefix per-series, which is why it declines an operation whose
1492        // answer depends on the order its input arrives in. A node over more than one input reads
1493        // its inputs' partitions in the order they became ready, so that refusal holds there too.
1494        if multi_input && depends_on_input_order(root) {
1495            return Ok(None);
1496        }
1497        // The native output schema can name only compiled value fields, the time index and the tag
1498        // columns a source declares. A discovered source declares `__name__` because the name tells two
1499        // metrics with equal labels apart (#10106); a named source does not, so a tree reading more than
1500        // one such source cannot report the distinct groups and declines.
1501        if multi_input && groups_by_metric_name(root) {
1502            return Ok(None);
1503        }
1504        // Catch the shape refusals before choosing native execution: errors raised during physical
1505        // planning cannot fall back. This includes unsupported aggregates and `topk`, `limitk` or
1506        // CountValues groupings; it does not cover data-dependent errors raised while executing the
1507        // tree. A plan split over regions commits to the fused node without the split or a segment
1508        // above it, so it checks itself the same way before that choice.
1509        if (multi_input || per_source_inputs) && !native_tree_supported(&tree) {
1510            return Ok(None);
1511        }
1512        // A tree that ends in a canonical merge answers one series per label set, and the pieces of one
1513        // set were spread over the scan's partitions by the rewrite that created them. Lowering that
1514        // boundary keeps the scan width: each partition merges the pieces it holds and a canonical
1515        // router collects a label set from every partition.
1516        if selectors.len() == 1
1517            && matches!(&tree.root().expr, NativeExpr::Merge { input } if pointwise_operand(input) && canonical_local_prefix(input) && !contains_global_consumer(input))
1518            && let Some((plan, _)) = canonical_boundary_stages(
1519                Arc::from(expression.as_str()),
1520                &tree,
1521                &children,
1522                &source_tags,
1523                &grid,
1524                &time,
1525                &tags,
1526                &metric,
1527                format,
1528                root_kind,
1529                fused_output_tags,
1530                expression_field_names,
1531            )
1532        {
1533            return Ok(Some(native_planned(
1534                plan,
1535                frame_metadata,
1536                root_kind,
1537                time,
1538                grid,
1539            )));
1540        }
1541        if required_placement {
1542            // A tree whose fold can be split keeps that plan: it exports aggregate state rather than
1543            // whole samples. The general segmentation below is the fallback for the trees it declines,
1544            // and the split is decided before anything consumes a child. Its producer reads whatever
1545            // input the statement prepared.
1546            let split = if selectors.len() == 1 {
1547                FusedSeries::split_aggregate(&tree, &time).context(DataFusionPlanningSnafu)?
1548            } else {
1549                None
1550            };
1551            if let Some((partial, final_tree)) = split {
1552                // The split's output is the suffix's, so a histogram answer is only carried when the
1553                // cut aggregate's exported state is a histogram's too: `sum`/`avg` over native
1554                // histograms merge their own state across the boundary. A histogram answer whose
1555                // aggregate sits elsewhere - above the cut, or built by a function of a float -
1556                // still keeps the existing plan, because no state of this route carries it. The
1557                // partial stage may introduce labels before aggregation, so the columns come from
1558                // the complete tree rather than from the suffix alone.
1559                let histogram_state = split_exports_histogram_state(&partial);
1560                if root_kind != FieldKind::Float
1561                    && !(root_kind == FieldKind::Histogram && histogram_state)
1562                {
1563                    return Ok(None);
1564                }
1565                // The row-value layout is what the split is validated against whichever format the
1566                // caller asked for: it names one column per value the partial state accumulates,
1567                // while the encoded frame carries those values inside its own layout.
1568                let Some(value_schema) =
1569                    Self::fused_root_schema(&expression, &tree, &source_tags, &time, root_kind)?
1570                else {
1571                    return Ok(None);
1572                };
1573                // A frame operand also needs the evaluated layout its consumers decode, which is
1574                // the metadata derived above: a request that could not name one keeps the existing
1575                // plan rather than publishing rows to a frame consumer.
1576                if format == FusedOutputFormat::SeriesFrame && frame_metadata.is_none() {
1577                    return Ok(None);
1578                }
1579                let Some(rawinput) = children.into_iter().next() else {
1580                    return Ok(None);
1581                };
1582                let publish_grid = Arc::clone(&grid);
1583                let node = plan_split_aggregate(
1584                    Arc::from(expression.as_str()),
1585                    partial,
1586                    final_tree,
1587                    FusedSeriesBinding {
1588                        grid: publish_grid,
1589                        time_index: time.clone(),
1590                        tags,
1591                        metric_name: metric,
1592                    },
1593                    rawinput,
1594                    value_schema,
1595                    format,
1596                )?;
1597                let plan = LogicalPlan::Extension(Extension {
1598                    node: Arc::new(node),
1599                });
1600                return Ok(Some(native_planned(
1601                    plan,
1602                    frame_metadata,
1603                    root_kind,
1604                    time,
1605                    grid,
1606                )));
1607            }
1608            // A tree that folds native histograms anywhere and whose split declined keeps the
1609            // existing plan instead of being segmented. Segmentation cuts the tree into segments
1610            // that each fold their own samples and appends the pieces above them, so a group whose
1611            // contributions are spread over partitions would be folded once per segment - which for
1612            // a histogram sum means merging histograms that never met, and for a histogram average
1613            // means a mean of means. `cut_as_segment` returning false only declines to cut that
1614            // subtree and the collectors recurse into its children, so the refusal is here, at the
1615            // point the segment decision is made.
1616            if binds_histogram_state_anywhere(root) {
1617                return Ok(None);
1618            }
1619        }
1620        // A segment of a plan split over regions keeps the raw source as its input rather than a
1621        // bare scan: the segment's prefixes run on the frontend above the regions, so the raw series
1622        // source is what each of them reads.
1623        if required_placement || matches!(locality, InputLocality::SinglePartition) {
1624            let segment_metric = if cross_table { None } else { metric.clone() };
1625            let plan = segment_tree(
1626                Arc::from(expression.as_str()),
1627                &tree,
1628                &children,
1629                &source_tags,
1630                &bare_scans,
1631                &per_source,
1632                &grid,
1633                &time,
1634                &tags,
1635                &segment_metric,
1636                format,
1637                contains_canonical_merge(root),
1638                root_kind,
1639                // A cut must keep the source whenever a region's own read cannot hold what the cut
1640                // evaluates: a per-region prefix would evaluate a window over one region's fragment, so
1641                // `rate` never sees the samples the other region holds. That is a partition on a column
1642                // that is not a tag, and a partitioned table whose occurrences are source-backed.
1643                any_split_series || (per_source_inputs && any_partitioned),
1644                fused_output_tags,
1645                expression_field_names,
1646                PromPlanner::segmented_root_schema,
1647            );
1648            if let Some(plan) = plan {
1649                return Ok(Some(native_planned(
1650                    plan,
1651                    frame_metadata,
1652                    root_kind,
1653                    time,
1654                    grid,
1655                )));
1656            }
1657            // One input with no split or segment above it leaves a raw scan doing the work of a
1658            // cross-series consumer, and a single scan does not prove its region holds every
1659            // contribution the consumer needs. Keep that consumer on the existing plan; a tree over more
1660            // than one input is not this shape.
1661            if required_placement && !multi_input {
1662                return Ok(None);
1663            }
1664        }
1665        // The tags are asked for before the fields, because the walk answers for a tree the
1666        // compiler produced: a scalar root has no labels at all, and a sample root's are the ones
1667        // the walk derives. If it cannot derive them, this route declines.
1668        let output_tags = match &tree.root().output {
1669            // A scalar has no labels, and its value is named as a bare literal's is.
1670            NativeType::Scalar(_) => Vec::new(),
1671            NativeType::Samples(_) => match fused_output_tags(tree.root(), &source_tags) {
1672                Some(output_tags) => with_row_name_column(tree.root(), output_tags),
1673                None => return Ok(None),
1674            },
1675            NativeType::AggregateState(_) => return Ok(None),
1676        };
1677        let Some(root_fields) = native_root_fields(tree.root()) else {
1678            return Ok(None);
1679        };
1680        let output_schema = match format {
1681            FusedOutputFormat::PlainRows => {
1682                fused_output_schema(&expression, &root_fields, &output_tags, &time, root_kind)?
1683            }
1684            FusedOutputFormat::SeriesFrame => {
1685                let frame =
1686                    FusedSeries::series_frame_schema(&tree).context(DataFusionPlanningSnafu)?;
1687                Arc::new(
1688                    DFSchema::try_from(frame.as_ref().clone()).context(DataFusionPlanningSnafu)?,
1689                )
1690            }
1691        };
1692        // The children a node reads bind it: a `RawSeriesSource` child carries the frames and names the
1693        // metric it reads, so a node over them binds neither tags nor one metric name of its own. A node
1694        // whose children stay direct scans of one table reads that table through the one metric and tag
1695        // set they share.
1696        let (tags, metric) = if per_source_inputs {
1697            (Vec::new(), None)
1698        } else {
1699            (tags, metric)
1700        };
1701        // Every lowering path above publishes on the same grid the tree was compiled on, so the
1702        // binding is that grid rather than a per-shape choice.
1703        let publish_grid = Arc::clone(&grid);
1704        let node = FusedSeries::try_new_with_format(
1705            Arc::from(expression.as_str()),
1706            tree,
1707            FusedSeriesBinding {
1708                grid: publish_grid,
1709                // The node below names the same output column, so the binding takes a copy.
1710                time_index: time.clone(),
1711                tags,
1712                metric_name: metric,
1713            },
1714            children,
1715            output_schema,
1716            format,
1717        )
1718        .context(DataFusionPlanningSnafu)?;
1719        let plan = LogicalPlan::Extension(Extension {
1720            node: Arc::new(node),
1721        });
1722        Ok(Some(native_planned(
1723            plan,
1724            frame_metadata,
1725            root_kind,
1726            time,
1727            grid,
1728        )))
1729    }
1730
1731    /// The columns a [`FusedSeries`] node over `tree` produces.
1732    ///
1733    /// Fields and tags are derived from the native tree; the expression names the output fields.
1734    /// If this walk cannot derive a tag set, the native route declines rather than consulting the
1735    /// legacy planner.
1736    ///
1737    /// `Ok(None)` when the root is not a value the node can publish. A schema the output cannot
1738    /// declare is an error rather than a decline: duplicate names violate the expression-named
1739    /// native output contract, so construction reports the collision instead of publishing a
1740    /// layout the reader cannot address.
1741    fn fused_root_schema(
1742        expression: &str,
1743        tree: &NativeTree,
1744        source_tags: &[Vec<String>],
1745        time: &str,
1746        root_kind: FieldKind,
1747    ) -> Result<Option<DFSchemaRef>> {
1748        let output_tags = match &tree.root().output {
1749            NativeType::Scalar(_) => Vec::new(),
1750            NativeType::Samples(_) => {
1751                let Some(tags) = fused_output_tags(tree.root(), source_tags) else {
1752                    return Ok(None);
1753                };
1754                with_row_name_column(tree.root(), tags)
1755            }
1756            NativeType::AggregateState(_) => return Ok(None),
1757        };
1758        let Some(root_fields) = native_root_fields(tree.root()) else {
1759            return Ok(None);
1760        };
1761        // The kind is the one the statement's own root answers, derived before segmentation cut
1762        // anything. It cannot be recomputed here: a cut prefix is replaced by an input leaf whose
1763        // samples are already evaluated, so walking this tree would read every such leaf as the
1764        // kind its scan carried. `count_over_time(h[5m]) + on (__name__) ...` answers floats, and
1765        // its replaced leaf carries floats, while the scan below was a histogram.
1766        fused_output_schema(expression, &root_fields, &output_tags, time, root_kind).map(Some)
1767    }
1768
1769    /// The rows layout a segmented statement root publishes, under the segment builders' callback.
1770    ///
1771    /// A segment cannot carry this crate's error type, so a layout it cannot declare is a decline
1772    /// here: the route keeps the plan the existing planner would have built for the same statement.
1773    fn segmented_root_schema(
1774        expression: &str,
1775        tree: &NativeTree,
1776        source_tags: &[Vec<String>],
1777        time: &str,
1778        root_kind: FieldKind,
1779    ) -> Option<DFSchemaRef> {
1780        Self::fused_root_schema(expression, tree, source_tags, time, root_kind)
1781            .ok()
1782            .flatten()
1783    }
1784
1785    /// The statement being planned, rebuilt from the evaluation numbers the planner holds.
1786    ///
1787    /// The compiler reads the statement's grid, lookback and `@` anchors rather than the planner's mutable
1788    /// state. A nested binary is offered only while `ctx.start` and `ctx.end` are still the statement's
1789    /// bounds; anchored windows and subqueries can rewrite those bounds. `None` means the bounds are not
1790    /// representable as a [`SystemTime`].
1791    fn native_statement(&self, prom_expr: &PromExpr) -> Option<EvalStmt> {
1792        let start = epoch_millis(self.ctx.stmt_start)?;
1793        let end = epoch_millis(self.ctx.stmt_end)?;
1794        Some(EvalStmt {
1795            expr: prom_expr.clone(),
1796            start,
1797            end,
1798            interval: Duration::from_millis(self.ctx.interval as u64),
1799            lookback_delta: Duration::from_millis(self.ctx.lookback_delta as u64),
1800        })
1801    }
1802}
1803
1804/// The typed empty input of a discovered selector that matched no metric table.
1805///
1806/// No table matched, so there is no scan and no metric name: the input is an empty raw series frame, the
1807/// one input a [`FusedSeries`] node already reads. It is bound to a schema of one field and no grid
1808/// because that is the layout this route compiles a selector against; the planner re-lays it out in the
1809/// schema of the set operation it takes part in. No row is ever read, so a surviving name decides only
1810/// what an operator answering on its own - `absent` - calls its value column.
1811///
1812/// The empty plan declares the frame a scan would declare, so physical planning reads it as the frame
1813/// producer it is, with explicit labels rather than a scan's storage key.
1814fn empty_discovered_input(time_index: String) -> Result<PreparedInput> {
1815    let schema = empty_discovered_series_schema();
1816    let input = empty_discovered_frame(&schema)?;
1817    // No table stands behind this input, so no region splits it along a partition column.
1818    Ok((input, schema, None, time_index, Vec::new(), false, false))
1819}
1820
1821fn empty_discovered_frame(schema: &SeriesSchema) -> Result<LogicalPlan> {
1822    let frame =
1823        raw_series_frame_schema_with_ordering(schema, &RawLabelSource::Explicit, NATIVE_ORDERING)
1824            .context(DataFusionPlanningSnafu)?;
1825    Ok(LogicalPlan::EmptyRelation(EmptyRelation {
1826        produce_one_row: false,
1827        schema: Arc::new(
1828            DFSchema::try_from(frame.as_ref().clone()).context(DataFusionPlanningSnafu)?,
1829        ),
1830    }))
1831}
1832
1833/// The raw series schema of the typed empty input [`empty_discovered_input`] builds.
1834fn empty_discovered_series_schema() -> Arc<SeriesSchema> {
1835    Arc::new(SeriesSchema {
1836        fields: Arc::from([FieldSpec {
1837            name: Arc::from(DEFAULT_FIELD_COLUMN),
1838        }]),
1839        eval_grid: None,
1840    })
1841}
1842
1843/// Whether `expr` asks for `absent_over_time`, whose window is read through a fold that keeps the
1844/// metric name.
1845fn reads_presence(expr: &PromExpr) -> bool {
1846    #[derive(Default)]
1847    struct Presence(bool);
1848
1849    impl promql_parser::util::ExprVisitor for Presence {
1850        type Error = std::convert::Infallible;
1851
1852        fn pre_visit(&mut self, expr: &PromExpr) -> std::result::Result<bool, Self::Error> {
1853            if matches!(expr, PromExpr::Call(call) if call.func.name == "absent_over_time") {
1854                self.0 = true;
1855            }
1856            Ok(true)
1857        }
1858    }
1859
1860    let mut presence = Presence::default();
1861    let _ = promql_parser::util::walk_expr(&mut presence, expr);
1862    presence.0
1863}
1864
1865/// The moment `millis` milliseconds from the Unix epoch, on whichever side of it that lands.
1866///
1867/// A pre-epoch statement reaches the planner as a negative millisecond. `None` means the bound is
1868/// outside what a [`SystemTime`] represents.
1869fn epoch_millis(millis: i64) -> Option<SystemTime> {
1870    if millis.is_negative() {
1871        UNIX_EPOCH.checked_sub(Duration::from_millis(millis.unsigned_abs()))
1872    } else {
1873        UNIX_EPOCH.checked_add(Duration::from_millis(millis as u64))
1874    }
1875}
1876
1877/// Finds a subquery at the statement root, treating parentheses as transparent.
1878fn root_subquery(expr: &PromExpr) -> Option<&SubqueryExpr> {
1879    match expr {
1880        PromExpr::Subquery(subquery) => Some(subquery),
1881        PromExpr::Paren(paren) => root_subquery(&paren.expr),
1882        _ => None,
1883    }
1884}
1885
1886/// The native root's value columns, named from the compiled tree rather than legacy expressions.
1887fn native_root_fields(node: &NativeNode) -> Option<Vec<String>> {
1888    match &node.output {
1889        NativeType::Samples(schema) => Some(
1890            schema
1891                .fields
1892                .iter()
1893                .map(|field| field.name.to_string())
1894                .collect(),
1895        ),
1896        NativeType::Scalar(_) => Some(vec![DEFAULT_FIELD_COLUMN.to_string()]),
1897        NativeType::AggregateState(_) => None,
1898    }
1899}
1900
1901/// The names an expression gives the value columns of `fields`.
1902///
1903/// One value is named after the whole expression; several append their compiled field names to it,
1904/// because one name cannot stand for more than one column. Only the published layout is named this
1905/// way: the fields inside the native tree keep the names the compiler gave them.
1906fn expression_field_names(expression: &str, fields: &[String]) -> Vec<String> {
1907    fields
1908        .iter()
1909        .map(|field| {
1910            if fields.len() == 1 {
1911                expression.to_string()
1912            } else {
1913                format!("{expression}.{field}")
1914            }
1915        })
1916        .collect()
1917}
1918
1919/// The columns a [`FusedSeries`] node produces: its time index, one column per value, then its tags.
1920///
1921/// A single value is named after the expression, and multiple values append their compiled field
1922/// names to it, so a value is never published under a name the reader cannot address. The names
1923/// inside the native tree are unchanged.
1924///
1925/// The layout itself is [`segment::fused_output_schema`]'s, which is where a segment asks for the
1926/// same columns; this is that answer under this crate's error type, which is what the planner's own
1927/// call sites report.
1928fn fused_output_schema(
1929    expression: &str,
1930    fields: &[String],
1931    tags: &[String],
1932    time_index: &str,
1933    field_kind: FieldKind,
1934) -> Result<DFSchemaRef> {
1935    let value_names = expression_field_names(expression, fields);
1936    // A name appears twice when a value named after its expression - a bare selector is named after
1937    // its metric - lands on the table's own time index or on one of its tags, or when two values
1938    // take one name. `DFSchema` rejects that, but reports only that building the plan failed, which
1939    // names no column; the collision is detected here so the error names the columns that collide.
1940    let mut names = Vec::with_capacity(value_names.len() + tags.len() + 1);
1941    names.push(time_index.to_string());
1942    names.extend(value_names.iter().cloned());
1943    names.extend(tags.iter().cloned());
1944    let mut occurrences: std::collections::HashMap<&str, usize> =
1945        std::collections::HashMap::with_capacity(names.len());
1946    for name in &names {
1947        *occurrences.entry(name.as_str()).or_default() += 1;
1948    }
1949    let mut reported = std::collections::HashSet::new();
1950    let duplicates = names
1951        .iter()
1952        .filter(|name| occurrences[name.as_str()] > 1 && reported.insert(name.as_str()))
1953        .map(String::as_str)
1954        .collect::<Vec<_>>();
1955    ensure!(
1956        duplicates.is_empty(),
1957        DuplicateOutputColumnsSnafu {
1958            names: duplicates.join(", ")
1959        }
1960    );
1961    segment::fused_output_schema(&value_names, tags, time_index, field_kind)
1962        .context(DataFusionPlanningSnafu)
1963}
1964
1965/// Builds the two nodes a split native aggregate runs in.
1966///
1967/// The first is a [`FusedSeries`] over `rawinput` running the per-series prefix and a `Partial`
1968/// aggregate at its root, so each partition exports the state it folded. The second runs the `Final`
1969/// aggregate and everything the split moved above it: it reads state where the first reads series.
1970/// Between them the physical planner puts a `SeriesRepartitionExec`, which is what makes every row of
1971/// a group reach one final partition.
1972///
1973/// `format` is the representation the caller needs from the second node: the statement's row table,
1974/// or the evaluated series frame another native node reads as an operand.
1975///
1976/// `value_schema` is the statement's row-value layout; its value columns must match the partial
1977/// state's accumulator count.
1978fn plan_split_aggregate(
1979    promql: Arc<str>,
1980    partial: NativeTree,
1981    final_tree: NativeTree,
1982    binding: FusedSeriesBinding,
1983    rawinput: LogicalPlan,
1984    value_schema: DFSchemaRef,
1985    format: FusedOutputFormat,
1986) -> Result<FusedSeries> {
1987    // The kind a value column carries is the state's own: a numeric fold publishes `Float64`, a
1988    // native-histogram fold publishes the histogram value type. Reading it here keeps the layout and
1989    // the schema it is checked against in one place.
1990    let (state_accumulators, value_type) = match &partial.root().output {
1991        NativeType::AggregateState(state) => (
1992            state.accumulators.len(),
1993            if state.kind.is_histogram() {
1994                native_histogram_value_type().as_arrow_type()
1995            } else {
1996                ArrowDataType::Float64
1997            },
1998        ),
1999        _ => {
2000            return Err(DataFusionError::Plan(format!(
2001                "the partial tree for `{promql}` does not produce aggregate state"
2002            )))
2003            .context(DataFusionPlanningSnafu);
2004        }
2005    };
2006    let values = value_schema
2007        .fields()
2008        .iter()
2009        .filter(|field| field.data_type() == &value_type)
2010        .count();
2011    if values != state_accumulators {
2012        return Err(DataFusionError::Plan(format!(
2013            "the partial state for `{promql}` has {state_accumulators} accumulator(s), but the output schema declares \
2014             {values} value column(s)"
2015        )))
2016        .context(DataFusionPlanningSnafu);
2017    }
2018    // The partial tree publishes aggregate state on the cut aggregate's grid, which is not
2019    // necessarily the statement's when the suffix re-grids the values - a subquery above the cut
2020    // produces on its own grid. The final tree's binding is the one the caller derived for it.
2021    let partial_binding = FusedSeriesBinding {
2022        grid: match &partial.root().output {
2023            NativeType::AggregateState(state) => Arc::clone(&state.grid),
2024            _ => Arc::clone(&binding.grid),
2025        },
2026        ..binding.clone()
2027    };
2028    let partial = FusedSeries::try_new_state_export(
2029        Arc::clone(&promql),
2030        partial,
2031        partial_binding,
2032        vec![rawinput],
2033    )
2034    .context(DataFusionPlanningSnafu)?;
2035    let output_schema = match format {
2036        FusedOutputFormat::PlainRows => value_schema,
2037        // The final node's output is the frame its own evaluated root declares, so it is derived
2038        // from the tree it runs rather than from the row layout.
2039        FusedOutputFormat::SeriesFrame => {
2040            let frame =
2041                FusedSeries::series_frame_schema(&final_tree).context(DataFusionPlanningSnafu)?;
2042            Arc::new(DFSchema::try_from(frame.as_ref().clone()).context(DataFusionPlanningSnafu)?)
2043        }
2044    };
2045    FusedSeries::try_new_with_format(
2046        promql,
2047        final_tree,
2048        binding,
2049        vec![LogicalPlan::Extension(Extension {
2050            node: Arc::new(partial),
2051        })],
2052        output_schema,
2053        format,
2054    )
2055    .context(DataFusionPlanningSnafu)
2056}
2057
2058/// The time-range filter a selector's scan reads, from the bounds its compiled requirement names.
2059fn scan_time_filter(start: i64, end: i64, inclusive: bool, time_column: &str) -> DfExpr {
2060    let column = DfExpr::Column(datafusion::common::Column::from_name(time_column));
2061    let lower = DfExpr::Literal(
2062        datafusion::scalar::ScalarValue::TimestampMillisecond(Some(start), None),
2063        None,
2064    );
2065    let upper = DfExpr::Literal(
2066        datafusion::scalar::ScalarValue::TimestampMillisecond(Some(end), None),
2067        None,
2068    );
2069    let lower = if inclusive {
2070        column.clone().gt_eq(lower)
2071    } else {
2072        column.clone().gt(lower)
2073    };
2074    lower.and(column.lt_eq(upper))
2075}
2076
2077/// Whether any aggregate in `node` consumes histogram samples, wherever it sits in the tree.
2078///
2079/// The walk asks each aggregate what kind enters it rather than what the tree's root answers,
2080/// because an operator above an aggregate hides it: `sum(h) * 2` has a binary root. Only a
2081/// histogram entering an aggregate that would fold its payload is refused; a float-producing prefix
2082/// such as `count_over_time` over a histogram stays eligible, and so does an aggregate that skips the
2083/// sample instead of folding it.
2084fn aggregate_reads_histogram(node: &NativeNode, input_kind: FieldKind) -> bool {
2085    // `count` and `group` count a histogram as one present sample, and
2086    // `min`/`max`/`stddev`/`stdvar`/`quantile` skip it the way Prometheus does -- the legacy
2087    // planner maps all five through one branch (`create_native_histogram_aggregate_expr`), which
2088    // drops the samples and answers a Float NULL plus an info annotation, and the native fold does
2089    // the same thing at run time. Only `sum` and `avg` fold the payload, and an aggregate that
2090    // folds it runs here over a histogram when it binds the histogram state the kernel folds and
2091    // merges. `binds_histogram_state` is that binding, read from the same table the compiler and
2092    // the split bind from, so the gate and the runtime cannot disagree about which kinds fold.
2093    //
2094    // Everything else that is not provably a float entering it is still refused: "cannot name it"
2095    // is not "not a histogram", and a fold that read such a payload as a float would answer
2096    // something else. A canonical merge (`label_replace` collapsing a label) and a set operation
2097    // both hand on the samples they were given without the walk describing them, so they are what
2098    // this check still catches.
2099    node.any(&|node| {
2100        matches!(
2101            &node.expr,
2102            NativeExpr::Aggregate { input, op }
2103                if matches!(op.kind, AggregateKind::Sum | AggregateKind::Avg)
2104                    && !matches!(
2105                        input.output_field_kind(Some(input_kind)),
2106                        Some(FieldKind::Float)
2107                    )
2108                    && !binds_histogram_state(op)
2109        )
2110    })
2111}
2112
2113/// Whether this aggregate's state carries a native histogram.
2114///
2115/// It is the same table the compiler and the split bind from, so the gates and the runtime agree on
2116/// which aggregates fold a payload: `sum` and `avg` over histograms do, and every other aggregate
2117/// answers a float whatever it reads.
2118fn binds_histogram_state(op: &BoundAggregate) -> bool {
2119    aggregate_state_binding(op.kind, op.field_kind).is_some_and(|(kind, _)| kind.is_histogram())
2120}
2121
2122/// Whether any aggregate in `node` binds a state that carries a native histogram.
2123///
2124/// Unlike [`aggregate_reads_histogram`] this asks what each aggregate *keeps*, not what enters it:
2125/// a tree that folds a histogram anywhere in it needs the split (or nothing at all), because only
2126/// the split's state carries that fold across a partition boundary.
2127fn binds_histogram_state_anywhere(node: &NativeNode) -> bool {
2128    node.any(&|node| {
2129        matches!(
2130            &node.expr,
2131            NativeExpr::Aggregate { op, .. } if binds_histogram_state(op)
2132        )
2133    })
2134}
2135
2136/// Whether the state a split tree exports is a native histogram's.
2137///
2138/// The partial tree's root is the cut aggregate bound as `Partial`, so its own binding is what says
2139/// which state crosses the boundary; reading it there is what keeps the gate and the runtime from
2140/// disagreeing about the layout the suffix will merge.
2141fn split_exports_histogram_state(partial: &NativeTree) -> bool {
2142    match &partial.root().expr {
2143        NativeExpr::Aggregate { op, .. } => binds_histogram_state(op),
2144        _ => false,
2145    }
2146}
2147
2148/// Whether every plan is a scan of one table. Filters, projections and bounds are
2149/// occurrence-specific and deliberately do not participate in this check.
2150pub(crate) fn same_table_scans<'a>(plans: impl IntoIterator<Item = &'a LogicalPlan>) -> bool {
2151    let mut table = None;
2152    plans.into_iter().all(|plan| {
2153        let LogicalPlan::TableScan(scan) = plan else {
2154            return false;
2155        };
2156        *table.get_or_insert(&scan.table_name) == &scan.table_name
2157    })
2158}
2159
2160/// The most metric tables one discovered selector will scan.
2161///
2162/// A selector that matches everything is answered by narrowing it rather than by planning one query
2163/// that reads the whole schema at once.
2164const MAX_DISCOVERED_METRICS: usize = 1024;
2165
2166/// Whether a selector names no single table and has to enumerate the schema's metric tables.
2167///
2168/// Exported so the authorization layer can ask the same question before it authorizes what the
2169/// planner will scan; the two answers have to agree.
2170pub fn discovers_metric_name(selector: &VectorSelector) -> bool {
2171    let name_matchers = selector.matchers.find_matchers(METRIC_NAME);
2172    let has_non_equal_name_matcher = name_matchers
2173        .iter()
2174        .any(|matcher| !matches!(&matcher.op, MatchOp::Equal));
2175    let has_exact_name_matcher = name_matchers.len() == 1 && !has_non_equal_name_matcher;
2176    selector.name.is_none()
2177        && !has_exact_name_matcher
2178        && selector.matchers.or_matchers.is_empty()
2179        && (name_matchers.len() > 1
2180            || has_non_equal_name_matcher
2181            || selector.matchers.matchers.iter().any(|matcher| {
2182                !["__schema__", "__database__", "__field__", METRIC_NAME]
2183                    .contains(&matcher.name.as_str())
2184            }))
2185}
2186
2187/// Whether `node` holds an operation whose answer depends on the order its input arrives in.
2188///
2189/// `limitk` keeps the first `k` series of each group *in input order* ([`promql::select::limitk`]),
2190/// and a node with more than one input reads them through a gather that hands over whichever
2191/// partition became ready first, so the schedule would decide which series a query keeps. Only this
2192/// operation's selection depends on that order: `topk` breaks ties by label and `limit_ratio`
2193/// selects by a label hash.
2194fn depends_on_input_order(node: &NativeNode) -> bool {
2195    match &node.expr {
2196        NativeExpr::Input(_) | NativeExpr::Scalar(_) | NativeExpr::EvalTime { .. } => false,
2197        NativeExpr::Instant { input, .. }
2198        | NativeExpr::Merge { input }
2199        | NativeExpr::Window { input, .. }
2200        | NativeExpr::Map { input, .. }
2201        | NativeExpr::Timestamp { input }
2202        | NativeExpr::Aggregate { input, .. }
2203        // `vector()` and `scalar()` answer one series or one value from their input, and since
2204        // `scalar()` exists their input can hold an order-dependent selection:
2205        // `vector(scalar(limitk(1, a)))` keeps whichever `a` series the gather handed over first.
2206        | NativeExpr::VectorOf { input }
2207        | NativeExpr::ScalarOf { input } => depends_on_input_order(input),
2208        NativeExpr::ParameterizedMap {
2209            input, parameters, ..
2210        } => depends_on_input_order(input) || parameters.iter().any(depends_on_input_order),
2211        NativeExpr::ParameterizedTopK {
2212            input, parameter, ..
2213        } => depends_on_input_order(input) || depends_on_input_order(parameter),
2214        NativeExpr::ParameterizedHistogram {
2215            input, parameters, ..
2216        } => depends_on_input_order(input) || parameters.iter().any(depends_on_input_order),
2217        NativeExpr::Vector { input, op } => {
2218            matches!(op, BoundVectorOp::LimitK { .. }) || depends_on_input_order(input)
2219        }
2220        NativeExpr::Binary { left, right, .. } | NativeExpr::Set { left, right, .. } => {
2221            depends_on_input_order(left) || depends_on_input_order(right)
2222        }
2223        NativeExpr::Info { base, info, .. } => {
2224            depends_on_input_order(base) || depends_on_input_order(info)
2225        }
2226    }
2227}
2228
2229/// One side of a set operation, as the slice of the pre-order selector list it reads.
2230///
2231/// The slice is the side's whole subtree, so it also says whether the side reads a table at all.
2232#[derive(Clone, Copy, Debug)]
2233struct SetOperand {
2234    start: usize,
2235    end: usize,
2236}
2237
2238/// One set operation in the statement and the two operands it compares.
2239#[derive(Clone, Copy, Debug)]
2240struct SetOperation {
2241    lhs: SetOperand,
2242    rhs: SetOperand,
2243}
2244
2245/// [`collect_selectors`], also recording the set operations it passes.
2246///
2247/// The operands are recorded as index ranges of `out`, which is the pre-order the compiler binds its inputs in.
2248fn collect_selectors_with_set_operations<'a>(
2249    stmt: &EvalStmt,
2250    expr: &'a PromExpr,
2251    under_rate_or_increase: bool,
2252    out: &mut Vec<(Cow<'a, VectorSelector>, bool)>,
2253    set_operations: &mut Vec<SetOperation>,
2254) -> bool {
2255    match expr {
2256        PromExpr::VectorSelector(selector) => {
2257            out.push((Cow::Borrowed(selector), under_rate_or_increase))
2258        }
2259        PromExpr::MatrixSelector(MatrixSelector { vs, .. }) => {
2260            out.push((Cow::Borrowed(vs), under_rate_or_increase))
2261        }
2262        PromExpr::Paren(ParenExpr { expr }) => {
2263            return collect_selectors_with_set_operations(
2264                stmt,
2265                expr,
2266                under_rate_or_increase,
2267                out,
2268                set_operations,
2269            );
2270        }
2271        PromExpr::Call(call) if call.func.name == "info" => {
2272            let Ok(InfoInput { selector, .. }) = info_input(stmt, &call.args.args) else {
2273                return false;
2274            };
2275            if !collect_selectors_with_set_operations(
2276                stmt,
2277                &call.args.args[0],
2278                under_rate_or_increase,
2279                out,
2280                set_operations,
2281            ) {
2282                return false;
2283            }
2284            out.push((Cow::Owned(selector), under_rate_or_increase));
2285        }
2286        PromExpr::Binary(binary) => {
2287            let lhs_start = out.len();
2288            if !collect_selectors_with_set_operations(
2289                stmt,
2290                &binary.lhs,
2291                under_rate_or_increase,
2292                out,
2293                set_operations,
2294            ) {
2295                return false;
2296            }
2297            let lhs_end = out.len();
2298            if !collect_selectors_with_set_operations(
2299                stmt,
2300                &binary.rhs,
2301                under_rate_or_increase,
2302                out,
2303                set_operations,
2304            ) {
2305                return false;
2306            }
2307            if binary.op.is_set_operator() {
2308                set_operations.push(SetOperation {
2309                    lhs: SetOperand {
2310                        start: lhs_start,
2311                        end: lhs_end,
2312                    },
2313                    rhs: SetOperand {
2314                        start: lhs_end,
2315                        end: out.len(),
2316                    },
2317                });
2318            }
2319            return true;
2320        }
2321        // Literals contribute no selector; the compiler decides which scalar forms can be bound.
2322        PromExpr::NumberLiteral(_) => return true,
2323        PromExpr::Unary(unary) => {
2324            return collect_selectors_with_set_operations(
2325                stmt,
2326                &unary.expr,
2327                under_rate_or_increase,
2328                out,
2329                set_operations,
2330            );
2331        }
2332        // `histogram_quantile` and `histogram_fraction` take their vector last, and the compiler
2333        // compiles that vector before the arguments in front of it, so the walk reads it first: the
2334        // scan prepared at a position has to be the one the compiler binds there.
2335        PromExpr::Call(call)
2336            if matches!(call.func.name, "histogram_quantile" | "histogram_fraction") =>
2337        {
2338            let Some((vector, parameters)) = call.args.args.split_last() else {
2339                return false;
2340            };
2341            return collect_selectors_with_set_operations(
2342                stmt,
2343                vector,
2344                under_rate_or_increase,
2345                out,
2346                set_operations,
2347            ) && parameters.iter().all(|parameter| {
2348                collect_selectors_with_set_operations(
2349                    stmt,
2350                    parameter,
2351                    under_rate_or_increase,
2352                    out,
2353                    set_operations,
2354                )
2355            });
2356        }
2357        PromExpr::Call(call) => {
2358            if matches!(call.func.name, "label_replace" | "label_join") {
2359                let arity_valid = if call.func.name == "label_replace" {
2360                    call.args.args.len() == 5
2361                } else {
2362                    call.args.args.len() >= 3
2363                };
2364                return arity_valid
2365                    && matches!(call.args.args.first(), Some(arg) if matches!(arg.value_type(), ValueType::Vector | ValueType::Matrix))
2366                    && collect_selectors_with_set_operations(
2367                        stmt,
2368                        &call.args.args[0],
2369                        under_rate_or_increase,
2370                        out,
2371                        set_operations,
2372                    );
2373            }
2374            for arg in &call.args.args {
2375                if !collect_selectors_with_set_operations(
2376                    stmt,
2377                    arg,
2378                    under_rate_or_increase || matches!(call.func.name, "rate" | "increase"),
2379                    out,
2380                    set_operations,
2381                ) {
2382                    return false;
2383                }
2384            }
2385        }
2386        // The compiler compiles an aggregate's input and then its parameter (`topk`/`bottomk` take an expression
2387        // where the others take a number or a label), so a parameter that reads a selector is a second source
2388        // bound after the input. Walking both keeps the prepared scan and the bound input at the same position.
2389        PromExpr::Aggregate(aggregate) => {
2390            return collect_selectors_with_set_operations(
2391                stmt,
2392                &aggregate.expr,
2393                under_rate_or_increase,
2394                out,
2395                set_operations,
2396            ) && match &aggregate.param {
2397                Some(param) => collect_selectors_with_set_operations(
2398                    stmt,
2399                    param,
2400                    under_rate_or_increase,
2401                    out,
2402                    set_operations,
2403                ),
2404                None => true,
2405            };
2406        }
2407        // A subquery evaluates its expression on its own grid; its selectors are prepared like any
2408        // other, each with the scan bounds `raw_scan_bounds` derives from its own range and step.
2409        PromExpr::Subquery(subquery) => {
2410            // Keep the set operations inside the subquery in the same accumulator: a zero-match
2411            // selector there is laid out by its own set operand, not by the statement's layout.
2412            return collect_selectors_with_set_operations(
2413                stmt,
2414                &subquery.expr,
2415                under_rate_or_increase,
2416                out,
2417                set_operations,
2418            );
2419        }
2420        _ => {}
2421    }
2422    true
2423}
2424
2425/// The index of the real input each zero-match input is laid out by, in `prepared` order.
2426///
2427/// A set operation pairs its two sides' fields by position, so an operand that reads no real input is laid out
2428/// by the first real selector in the other operand, and that layout reaches every zero-match selector of the
2429/// operand, nested set operations included. An empty input with no such operand above it has no entry here.
2430fn local_empty_layouts(
2431    set_operations: &[SetOperation],
2432    prepared: &[PreparedInput],
2433) -> Vec<Option<usize>> {
2434    let mut layouts = vec![None; prepared.len()];
2435    let real = |index: usize| {
2436        prepared
2437            .get(index)
2438            .is_some_and(|(scan, ..)| !is_empty_discovered_input(scan))
2439    };
2440    // The operations are recorded inside out, so an inner one decides before the operation above it
2441    // reads the subtree it holds. An operand that reads no real input holds no real input inside it
2442    // either, so an operation that writes a layout here is the only one that reaches those indices.
2443    for operation in set_operations {
2444        for (empty, sibling) in [
2445            (operation.lhs, operation.rhs),
2446            (operation.rhs, operation.lhs),
2447        ] {
2448            // A side that reads a table lays its own selectors out: only a side that reads none
2449            // needs the layout of the comparison it takes part in.
2450            if (empty.start..empty.end).any(&real) {
2451                continue;
2452            }
2453            let Some(source) = (sibling.start..sibling.end).find(|index| real(*index)) else {
2454                continue;
2455            };
2456            for index in empty.start..empty.end {
2457                let Some(layout) = layouts.get_mut(index) else {
2458                    continue;
2459                };
2460                if layout.is_none() {
2461                    *layout = Some(source);
2462                }
2463            }
2464        }
2465    }
2466    layouts
2467}
2468
2469/// Whether `engine` can serve raw series frames to the fused-series node.
2470///
2471/// A scanner capability boundary: it avoids probing a region during logical planning.
2472fn supports_native_raw_series(engine: &str) -> bool {
2473    matches!(engine, MITO_ENGINE | MITO2_ENGINE | METRIC_ENGINE)
2474}
2475
2476/// Recognizes only the metric logical-table scan emitted by `create_table_scan_plan`, and reports
2477/// the logical table's id together with the scan: the rewrite's `__table_id = <id>` restriction is
2478/// the logical table the rewrite stands for, so it is the identity a selector over it reads.
2479fn metric_scan_and_table_id(
2480    plan: &LogicalPlan,
2481) -> Option<(datafusion::logical_expr::TableScan, Expr, u32)> {
2482    let plan = match plan {
2483        LogicalPlan::Projection(projection) => projection.input.as_ref(),
2484        plan => plan,
2485    };
2486    let plan = match plan {
2487        LogicalPlan::SubqueryAlias(alias) => alias.input.as_ref(),
2488        plan => plan,
2489    };
2490    let LogicalPlan::Filter(filter) = plan else {
2491        return None;
2492    };
2493    let Expr::BinaryExpr(binary) = &filter.predicate else {
2494        return None;
2495    };
2496    if binary.op != datafusion::logical_expr::Operator::Eq
2497        || !matches!(binary.left.as_ref(), Expr::Column(column) if column.name == DATA_SCHEMA_TABLE_ID_COLUMN_NAME)
2498    {
2499        return None;
2500    }
2501    let Expr::Literal(datafusion::scalar::ScalarValue::UInt32(Some(table_id)), _) =
2502        binary.right.as_ref()
2503    else {
2504        return None;
2505    };
2506    let LogicalPlan::TableScan(scan) = filter.input.as_ref() else {
2507        return None;
2508    };
2509    Some((scan.clone(), filter.predicate.clone(), *table_id))
2510}
2511
2512#[cfg(test)]
2513mod tests {
2514    use std::sync::Arc;
2515
2516    use std::time::{Duration, UNIX_EPOCH};
2517
2518    use datafusion::arrow::datatypes::TimeUnit as ArrowTimeUnit;
2519    use datafusion::physical_plan::ExecutionPlan;
2520    use datatypes::series::SeriesOrdering;
2521    use datatypes::series::samples::{FieldSpec, SeriesSchema};
2522    use promql::native::plan::{
2523        NativeExpr, NativeNode, NativeTree, fused_output_tags, reads_across_series,
2524    };
2525    use promql::native::segment::{cut_segments, region_local_segment};
2526    use session::context::QueryContextBuilder;
2527
2528    use super::{
2529        ArrowDataType, FieldKind, METRIC_NAME, NATIVE_PROMQL_EXTENSION_KEY, NativeType,
2530        PromPlanner, aggregate_reads_histogram, collect_selectors_with_set_operations,
2531        fused_output_schema, independent_scan_pair, native_promql_requested,
2532        native_promql_resolved, native_raw_plan_bounds_region_reads, scan_time_filter,
2533    };
2534
2535    /// The switch resolves from the two sources planning reads: what the query states (a request
2536    /// value over the session `SET` it inherits), and the engine default when it states nothing.
2537    /// The frontend reads the same resolver before a plan exists, so a query that never asks for
2538    /// the route is not bounded for discovery and one that does is.
2539    #[test]
2540    fn the_route_switch_resolves_over_the_engine_default() {
2541        const KEY: &str = "query.experimental_native_promql";
2542        for (engine_default, session, request, resolved) in [
2543            // Nothing is stated, so the engine default answers.
2544            (false, None, None, false),
2545            (true, None, None, true),
2546            // A session `SET` states it, and a request value outranks it in both directions.
2547            (false, Some("true"), None, true),
2548            (true, Some("false"), None, false),
2549            (false, Some("false"), Some("true"), true),
2550            (true, Some("true"), Some("false"), false),
2551            // The value is compared literally, as planning compares it.
2552            (false, None, Some("TRUE"), true),
2553        ] {
2554            let mut ctx = QueryContextBuilder::default().build();
2555            if let Some(value) = session {
2556                ctx.configuration_parameter()
2557                    .set_query_option(KEY, value)
2558                    .unwrap();
2559            }
2560            if let Some(value) = request {
2561                ctx.set_extension(KEY.to_string(), value.to_string());
2562            }
2563            assert_eq!(
2564                resolved,
2565                native_promql_resolved(&Arc::new(ctx), engine_default).unwrap(),
2566                "engine={engine_default}, session={session:?}, request={request:?}"
2567            );
2568        }
2569    }
2570
2571    #[test]
2572    fn native_raw_region_read_budget_needs_the_native_topology() {
2573        let schema = Arc::new(datafusion::arrow::datatypes::Schema::new(vec![
2574            datafusion::arrow::datatypes::Field::new(
2575                "ts",
2576                datafusion::arrow::datatypes::DataType::Int64,
2577                false,
2578            ),
2579        ]));
2580        let scan = || {
2581            Arc::new(datafusion::physical_plan::empty::EmptyExec::new(
2582                schema.clone(),
2583            )) as Arc<dyn ExecutionPlan>
2584        };
2585
2586        // No `FusedSeriesExec`: nothing here reads regions the way the budget assumes.
2587        assert!(!native_raw_plan_bounds_region_reads(&scan()));
2588        // A union drains its inputs one after another, so a body budget could stall it.
2589        let union = datafusion::physical_plan::union::UnionExec::try_new(vec![scan(), scan()])
2590            .expect("two inputs");
2591        assert!(!native_raw_plan_bounds_region_reads(&union));
2592    }
2593
2594    fn compiled_test_tree(query: &str) -> NativeTree {
2595        compiled_test_tree_with_fields(query, &["v0"])
2596    }
2597
2598    fn compiled_test_tree_with_fields(query: &str, fields: &[&str]) -> NativeTree {
2599        let statement = promql_parser::parser::EvalStmt {
2600            expr: promql_parser::parser::parse(query).unwrap(),
2601            start: UNIX_EPOCH,
2602            end: UNIX_EPOCH + Duration::from_secs(10),
2603            interval: Duration::from_secs(5),
2604            lookback_delta: Duration::from_secs(5),
2605        };
2606        let schema = Arc::new(SeriesSchema {
2607            fields: fields
2608                .iter()
2609                .map(|name| FieldSpec {
2610                    name: (*name).into(),
2611                })
2612                .collect::<Vec<_>>()
2613                .into(),
2614            eval_grid: None,
2615        });
2616        crate::promql::native_compile::compile_selectors(
2617            &statement,
2618            &|_| Ok(Arc::clone(&schema)),
2619            SeriesOrdering::KeyThenTime,
2620            Some(FieldKind::Float),
2621        )
2622        .unwrap()
2623        .tree
2624    }
2625
2626    #[test]
2627    fn aggregate_histogram_walk_descends_through_scalar_vector_wrappers() {
2628        let tree = compiled_test_tree("scalar(vector(scalar(sum(some_metric))))");
2629        assert_eq!(input_sources(tree.root()), vec![0]);
2630        assert!(aggregate_reads_histogram(tree.root(), FieldKind::Histogram));
2631        assert!(!aggregate_reads_histogram(tree.root(), FieldKind::Float));
2632    }
2633
2634    fn input_sources(root: &NativeNode) -> Vec<usize> {
2635        root.inputs()
2636            .into_iter()
2637            .map(|input| input.source_index)
2638            .collect()
2639    }
2640
2641    /// The selectors `query` names, in the order the compiler binds them.
2642    fn collected_selectors(query: &str) -> Vec<String> {
2643        let expr = promql_parser::parser::parse(query).expect("the query parses");
2644        let statement = promql_parser::parser::EvalStmt {
2645            expr: expr.clone(),
2646            start: UNIX_EPOCH,
2647            end: UNIX_EPOCH + Duration::from_secs(10),
2648            interval: Duration::from_secs(5),
2649            lookback_delta: Duration::from_secs(5),
2650        };
2651        let mut selectors = Vec::new();
2652        assert!(collect_selectors_with_set_operations(
2653            &statement,
2654            &expr,
2655            false,
2656            &mut selectors,
2657            &mut Vec::new()
2658        ));
2659        selectors
2660            .iter()
2661            .map(|(selector, _)| selector.name.clone().unwrap_or_default())
2662            .collect()
2663    }
2664
2665    /// The metric names the compiler binds selectors to, in the order it binds them.
2666    fn compiled_selector_order(query: &str) -> Vec<String> {
2667        let statement = promql_parser::parser::EvalStmt {
2668            expr: promql_parser::parser::parse(query).expect("the query parses"),
2669            start: UNIX_EPOCH,
2670            end: UNIX_EPOCH + Duration::from_secs(10),
2671            interval: Duration::from_secs(5),
2672            lookback_delta: Duration::from_secs(5),
2673        };
2674        let schema = Arc::new(SeriesSchema {
2675            fields: Arc::from([FieldSpec { name: "v0".into() }]),
2676            eval_grid: None,
2677        });
2678        let bound = std::cell::RefCell::new(Vec::new());
2679        crate::promql::native_compile::compile_selectors(
2680            &statement,
2681            &|requirement| {
2682                bound
2683                    .borrow_mut()
2684                    .push(requirement.metric.clone().unwrap_or_default());
2685                Ok(Arc::clone(&schema))
2686            },
2687            SeriesOrdering::KeyThenTime,
2688            Some(FieldKind::Float),
2689        )
2690        .expect("the compiler binds every selector of this query");
2691        bound.into_inner()
2692    }
2693
2694    #[test]
2695    fn selector_walk_keeps_plain_selector_identity() {
2696        for (query, expected) in [
2697            ("timestamp((x @ 2 offset -1s))", vec!["x"]),
2698            ("abs(timestamp(x @ 2 offset -1s))", vec!["x"]),
2699            ("timestamp(x @ start() offset 1s)", vec!["x"]),
2700            ("timestamp(x @ end() offset -1s)", vec!["x"]),
2701            (
2702                "timestamp(x @ 2 offset 1s) + y @ 2 offset 1s",
2703                vec!["x", "y"],
2704            ),
2705        ] {
2706            assert_eq!(collected_selectors(query), expected, "{query}");
2707        }
2708    }
2709
2710    #[test]
2711    fn collect_selectors_descends_into_aggregate_inputs() {
2712        for query in [
2713            "sum(x)",
2714            "sum by (job) (x)",
2715            "sum without (instance) (rate(x[5m]))",
2716        ] {
2717            assert_eq!(collected_selectors(query), vec!["x"], "{query}");
2718        }
2719        // A parameter is an expression of its own, and the compiler compiles the input before it, so
2720        // a parameter that reads a selector is a second source bound after the input. The order here
2721        // is that binding order, which is the one the planner prepares its scans in.
2722        for (query, expected) in [
2723            ("topk(scalar(a), b)", vec!["b", "a"]),
2724            ("bottomk(scalar(a), b)", vec!["b", "a"]),
2725            // A literal parameter and a label parameter contribute no selector at all.
2726            ("topk(3, b)", vec!["b"]),
2727            ("count_values(\"x\", b)", vec!["b"]),
2728            (
2729                "histogram_quantile(scalar(a), sum by (le) (rate(h[5m])))",
2730                vec!["h", "a"],
2731            ),
2732            (
2733                "histogram_fraction(scalar(a), scalar(b), sum by (le) (rate(h[5m])))",
2734                vec!["h", "a", "b"],
2735            ),
2736        ] {
2737            assert_eq!(collected_selectors(query), expected, "{query}");
2738            // The walk's contract is the compiler's binding order, so the two are compared rather
2739            // than kept in step by hand.
2740            assert_eq!(
2741                collected_selectors(query),
2742                compiled_selector_order(query),
2743                "{query}: the walk and the compiler must bind the same selectors in the same order"
2744            );
2745        }
2746    }
2747
2748    /// The compiler retains both source indices for independent selector occurrences.
2749    #[test]
2750    fn independent_scan_pair_keeps_both_numbered_occurrences() {
2751        for query in [
2752            "x + on(host) x",
2753            "x - (x * 2)",
2754            "rate(x[5s]) + rate(x[10s] offset 2s)",
2755            "x == on(host) x",
2756            "x > bool x",
2757            "2 * (x != on(host) x)",
2758            "x + on() x",
2759            "2 * (x > on() x)",
2760            "x + ignoring(host) x",
2761            "x * on(host) group_left x",
2762            "x * on(host) group_right x",
2763        ] {
2764            let tree = compiled_test_tree(query);
2765            assert_eq!(input_sources(tree.root()), vec![0, 1], "{query}");
2766            assert!(independent_scan_pair(tree.root()), "{query}");
2767        }
2768        assert!(!independent_scan_pair(
2769            compiled_test_tree("sum(x) + x").root()
2770        ));
2771    }
2772
2773    #[test]
2774    fn independent_scan_pair_admits_nested_matches() {
2775        for query in [
2776            "x + y + z",
2777            "(x - y) / on(host) z",
2778            "x / on(host) y * on(host) z",
2779            "abs(x - y) + 2 * z",
2780            "(x and y) or z",
2781            "(x + y) unless on(host) z",
2782            "(x == on(host) y) + z",
2783            "x > bool y + z",
2784            "(x * on(host) group_left y) + z",
2785            "(x * on(host) group_right y) + z",
2786            "(x + on() y) + z",
2787            "(x > on() y) + z",
2788        ] {
2789            let tree = compiled_test_tree(query);
2790            assert_eq!(input_sources(tree.root()), vec![0, 1, 2], "{query}");
2791            assert!(independent_scan_pair(tree.root()), "{query}");
2792        }
2793        assert!(!independent_scan_pair(
2794            compiled_test_tree("x + y + sum(z)").root()
2795        ));
2796    }
2797
2798    #[test]
2799    fn match_output_tags_follow_promql_vector_matching() {
2800        let tags = vec!["host".to_string(), "kind".to_string()];
2801        let sources = [tags.clone(), tags.clone()];
2802        let on = compiled_test_tree("x + on(host) x");
2803        assert_eq!(
2804            Some(vec!["host".to_string()]),
2805            fused_output_tags(on.root(), &sources)
2806        );
2807        let ignoring = compiled_test_tree("x + x");
2808        assert_eq!(
2809            Some(tags.clone()),
2810            fused_output_tags(ignoring.root(), &sources)
2811        );
2812        let empty_on = compiled_test_tree("x + on() x");
2813        assert_eq!(Some(vec![]), fused_output_tags(empty_on.root(), &sources));
2814
2815        // Two tables with different tags: the left side's labels pass through a wrapper and a
2816        // match, and `or` adds the labels only the right side carries.
2817        let sources = [
2818            vec!["host".to_string(), "kind".to_string()],
2819            vec!["host".to_string(), "zone".to_string()],
2820        ];
2821        let wrapped = compiled_test_tree("100 * (1 - x / on(host) y)");
2822        assert_eq!(
2823            Some(vec!["host".to_string()]),
2824            fused_output_tags(wrapped.root(), &sources)
2825        );
2826        let and = compiled_test_tree("x and on(host) y");
2827        assert_eq!(
2828            Some(sources[0].clone()),
2829            fused_output_tags(and.root(), &sources)
2830        );
2831        let or = compiled_test_tree("x or y");
2832        // `or` reports the series of both sides, so it reports each row's own name as well.
2833        assert_eq!(
2834            Some(vec![
2835                "host".to_string(),
2836                "kind".to_string(),
2837                "zone".to_string(),
2838                "__name__".to_string()
2839            ]),
2840            fused_output_tags(or.root(), &sources)
2841        );
2842        // An unmatched right series answers with its own matching labels under a left fill.
2843        let fill = compiled_test_tree("x + fill_left(0) y");
2844        assert_eq!(
2845            Some(vec![
2846                "host".to_string(),
2847                "kind".to_string(),
2848                "zone".to_string()
2849            ]),
2850            fused_output_tags(fill.root(), &sources)
2851        );
2852        let fill_on = compiled_test_tree("x + on(host) fill(0) y");
2853        assert_eq!(
2854            Some(vec!["host".to_string()]),
2855            fused_output_tags(fill_on.root(), &sources)
2856        );
2857        // Group modifiers retain the many-side labels and copy declared labels from the one side.
2858        let group_sources = [
2859            vec![
2860                "cluster".into(),
2861                "namespace".into(),
2862                "pod".into(),
2863                "container".into(),
2864            ],
2865            vec![
2866                "cluster".into(),
2867                "namespace".into(),
2868                "pod".into(),
2869                "workload".into(),
2870                "workload_type".into(),
2871            ],
2872        ];
2873        let group_left = compiled_test_tree(
2874            "x * on(cluster, namespace, pod) group_left(workload, workload_type) y",
2875        );
2876        assert_eq!(
2877            Some(
2878                vec![
2879                    "cluster",
2880                    "namespace",
2881                    "pod",
2882                    "container",
2883                    "workload",
2884                    "workload_type"
2885                ]
2886                .into_iter()
2887                .map(String::from)
2888                .collect()
2889            ),
2890            fused_output_tags(group_left.root(), &group_sources)
2891        );
2892        let group_right =
2893            compiled_test_tree("x * on(cluster, namespace, pod) group_right(container) y");
2894        assert_eq!(
2895            Some(
2896                vec![
2897                    "cluster",
2898                    "namespace",
2899                    "pod",
2900                    "workload",
2901                    "workload_type",
2902                    "container"
2903                ]
2904                .into_iter()
2905                .map(String::from)
2906                .collect()
2907            ),
2908            fused_output_tags(group_right.root(), &group_sources)
2909        );
2910        for query in [
2911            "x * on() group_left(workload) y",
2912            "x * on() group_right(container) y",
2913        ] {
2914            let tree = compiled_test_tree(query);
2915            let expected = if query.contains("group_left") {
2916                vec!["cluster", "namespace", "pod", "container", "workload"]
2917            } else {
2918                vec![
2919                    "cluster",
2920                    "namespace",
2921                    "pod",
2922                    "workload",
2923                    "workload_type",
2924                    "container",
2925                ]
2926            };
2927            let expected = Some(expected.into_iter().map(String::from).collect());
2928            assert_eq!(expected, fused_output_tags(tree.root(), &group_sources));
2929        }
2930        // An outer match narrows the labels the inner one already narrowed.
2931        let sources = [
2932            vec!["host".to_string(), "kind".to_string(), "zone".to_string()],
2933            vec!["host".to_string(), "kind".to_string()],
2934            vec!["host".to_string(), "az".to_string()],
2935        ];
2936        for (query, expected) in [
2937            ("(x - y) / on(host) z", vec!["host"]),
2938            ("x + ignoring(zone) y + ignoring(kind) z", vec!["host"]),
2939            // `or` reports the series of both sides, so each row's own name comes with them.
2940            (
2941                "x / on(host, kind) y or z",
2942                vec!["host", "kind", "az", "__name__"],
2943            ),
2944        ] {
2945            assert_eq!(
2946                Some(expected.into_iter().map(String::from).collect::<Vec<_>>()),
2947                fused_output_tags(compiled_test_tree(query).root(), &sources),
2948                "{query}"
2949            );
2950        }
2951        // An aggregate reports the grouping labels its input carries: `by` keeps exactly those, and `without`
2952        // keeps the rest and drops the metric name. `x` is bound to the three tag columns below, so
2953        // `without (instance)` keeps all three: `instance` is not one of them.
2954        for (query, expected) in [
2955            ("sum by (host) (x)", vec!["host"]),
2956            ("sum without (instance) (x)", vec!["host", "kind", "zone"]),
2957            ("sum(x)", Vec::new()),
2958        ] {
2959            let aggregate = compiled_test_tree(query);
2960            assert_eq!(
2961                Some(expected.into_iter().map(String::from).collect::<Vec<_>>()),
2962                fused_output_tags(aggregate.root(), &sources),
2963                "{query}"
2964            );
2965        }
2966        // Whole-vector operators that retain series keep the input labels, while `absent` derives
2967        // its output names from the compiler-bound label set and `count_values` adds its value tag.
2968        let hostname_source = [vec!["hostname".to_string()]];
2969        for query in [
2970            "topk(10, sum by (hostname) (rate(x[5m])))",
2971            "bottomk(10, sum by (hostname) (rate(x[5m])))",
2972            "limitk(10, sum by (hostname) (rate(x[5m])))",
2973            "limit_ratio(0.5, sum by (hostname) (rate(x[5m])))",
2974            "sort(sum by (hostname) (rate(x[5m])))",
2975        ] {
2976            assert_eq!(
2977                Some(vec!["hostname".to_string()]),
2978                fused_output_tags(compiled_test_tree(query).root(), &hostname_source),
2979                "{query}"
2980            );
2981        }
2982        let absent = compiled_test_tree("absent(x{host=\"a\", job=\"b\"})");
2983        assert_eq!(
2984            Some(vec!["host".to_string(), "job".to_string()]),
2985            fused_output_tags(absent.root(), &sources)
2986        );
2987        // A per-point `k` keeps the input's labels too: it selects the same series the bound form
2988        // selects, so it reports the same set. Its parameter reads a source of its own, so this tree
2989        // binds two.
2990        assert_eq!(
2991            Some(vec!["hostname".to_string()]),
2992            fused_output_tags(
2993                compiled_test_tree("topk(scalar(x), sum by (hostname) (rate(x[5m])))").root(),
2994                &[vec!["hostname".to_string()], vec!["hostname".to_string()]],
2995            ),
2996            "a per-point k reports its input's labels"
2997        );
2998        let count_values =
2999            compiled_test_tree("count_values by (host) (\"sample\", sum by (host) (x))");
3000        assert_eq!(
3001            Some(vec!["host".to_string(), "sample".to_string()]),
3002            fused_output_tags(count_values.root(), &sources)
3003        );
3004        // A destination already present in the grouping is reported once, not duplicated.
3005        let count_values = compiled_test_tree("count_values by (host) (\"host\", x)");
3006        assert_eq!(
3007            Some(vec!["host".to_string()]),
3008            fused_output_tags(count_values.root(), &sources)
3009        );
3010        // Selecting some series keeps each one's own labels, whatever the grouping was.
3011        let topk = compiled_test_tree("topk(1, x)");
3012        assert_eq!(
3013            Some(sources[0].clone()),
3014            fused_output_tags(topk.root(), &sources),
3015            "topk keeps the labels of the series it selects"
3016        );
3017        for query in [
3018            r#"label_replace(x, "dst", "$1", "src", "(.*)")"#,
3019            r#"label_join(x, "dst", "-", "src", "src")"#,
3020        ] {
3021            let rewrite = compiled_test_tree(query);
3022            assert_eq!(
3023                Some(
3024                    vec!["host", "kind", "zone", "dst"]
3025                        .into_iter()
3026                        .map(String::from)
3027                        .collect()
3028                ),
3029                fused_output_tags(rewrite.root(), &sources),
3030                "{query}"
3031            );
3032        }
3033    }
3034
3035    /// Pins the placement flip the name-preserving window unification caused. The inner window of a
3036    /// subquery over an evaluated selector now answers `Some(true)`, so the outer window does not
3037    /// read across series and both are region-local. While the inner window answered `Some(false)`
3038    /// the outer one crossed series and was placed on the frontend above the `MergeScan`; a
3039    /// regression in that unification shows up here as a frontend placement.
3040    #[test]
3041    fn nested_name_keeping_windows_are_region_local() {
3042        let tree = compiled_test_tree("max_over_time(last_over_time(some_metric[5m:1m])[10m:1m])");
3043        assert!(
3044            !reads_across_series(tree.root()),
3045            "nested name-keeping windows answer one series per label set"
3046        );
3047        assert!(
3048            region_local_segment(tree.root()),
3049            "the dist analyzer must place the nested windows region-side"
3050        );
3051    }
3052
3053    #[test]
3054    fn recursive_segmentation_rewrites_nested_cuts_with_dense_inputs() {
3055        let tree = compiled_test_tree("sum(abs(rate(x[1m])))");
3056        let segment = cut_segments(tree.root(), true);
3057        assert!(!segment.cut.is_empty());
3058        assert_eq!(segment.cut.len(), 1);
3059        assert_eq!(vec![0], input_sources(&segment.cut[0]));
3060    }
3061
3062    #[test]
3063    fn segmentation_leaves_a_data_free_only_candidate_unchanged() {
3064        for query in ["sum(vector(1))", "sum(abs(vector(1)))"] {
3065            let tree = compiled_test_tree(query);
3066            let segment = cut_segments(tree.root(), false);
3067            assert!(segment.sources.is_empty(), "{query}");
3068            assert!(segment.cut.is_empty(), "{query}");
3069            assert_eq!(
3070                tree.to_string(),
3071                NativeTree::try_new(segment.node).unwrap().to_string(),
3072                "{query}"
3073            );
3074        }
3075    }
3076
3077    #[test]
3078    fn group_left_copies_included_labels_into_output_tags() {
3079        let sources = [
3080            vec!["pod".into(), "workload".into()],
3081            vec!["pod".into(), "container".into()],
3082        ];
3083        let tree = compiled_test_tree("x * on(pod) group_left(container) y");
3084        assert_eq!(
3085            Some(vec!["pod".into(), "workload".into(), "container".into()]),
3086            fused_output_tags(tree.root(), &sources)
3087        );
3088    }
3089
3090    #[test]
3091    fn output_tags_without_grouping_drops_metric_name() {
3092        let sources = [vec![
3093            "instance".to_string(),
3094            METRIC_NAME.to_string(),
3095            "job".to_string(),
3096        ]];
3097
3098        let sum = compiled_test_tree("sum without (instance) (x)");
3099        assert_eq!(
3100            Some(vec!["job".to_string()]),
3101            fused_output_tags(sum.root(), &sources)
3102        );
3103
3104        let count_values = compiled_test_tree("count_values without (instance) (\"sample\", x)");
3105        assert_eq!(
3106            Some(vec!["job".to_string(), "sample".to_string()]),
3107            fused_output_tags(count_values.root(), &sources)
3108        );
3109
3110        let count_values =
3111            compiled_test_tree("count_values without (sample, instance) (\"sample\", x)");
3112        assert_eq!(
3113            Some(vec!["job".to_string()]),
3114            fused_output_tags(count_values.root(), &sources)
3115        );
3116    }
3117
3118    /// A rows layout declares the per-row name column, and only a rows layout does.
3119    ///
3120    /// The walk is the authority on the name's values - it keeps it exactly where the operator keeps
3121    /// it - so the column it is read from has to exist whether the walk kept the name or dropped it.
3122    #[test]
3123    fn rows_layouts_declare_the_name_column() {
3124        let one = || vec![vec!["host".to_string()]];
3125        let two = || vec![vec!["host".to_string()], vec!["host".to_string()]];
3126        for (query, sources) in [
3127            ("x", one()),
3128            ("abs(x)", one()),
3129            ("rate(x[5m])", one()),
3130            ("sum(x)", one()),
3131            // A set operation binds one source per occurrence.
3132            ("x or y", two()),
3133        ] {
3134            let tree = compiled_test_tree(query);
3135            let schema =
3136                PromPlanner::fused_root_schema(query, &tree, &sources, "ts", FieldKind::Float)
3137                    .unwrap()
3138                    .unwrap_or_else(|| panic!("{query}: a samples root declares a rows layout"));
3139            let names = schema
3140                .fields()
3141                .iter()
3142                .map(|field| field.name().as_str())
3143                .collect::<Vec<_>>();
3144            assert_eq!(Some(&METRIC_NAME), names.last(), "{query}: {names:?}");
3145            assert_eq!(
3146                1,
3147                names.iter().filter(|name| **name == METRIC_NAME).count(),
3148                "{query}: one name column: {names:?}"
3149            );
3150            let name = schema.field_with_unqualified_name(METRIC_NAME).unwrap();
3151            assert!(
3152                datatypes::schema::is_metric_name_field(name),
3153                "{query}: the column is the layout's name column"
3154            );
3155            assert_eq!(ArrowDataType::Utf8, *name.data_type(), "{query}");
3156        }
3157        let scalar = compiled_test_tree("1 + 2");
3158        let schema = PromPlanner::fused_root_schema("1 + 2", &scalar, &[], "ts", FieldKind::Float)
3159            .unwrap()
3160            .unwrap();
3161        assert_eq!(
3162            // A scalar root declares no name column, and its one value is named after the
3163            // expression, as every other rows layout names its values.
3164            vec!["ts", "1 + 2"],
3165            schema
3166                .fields()
3167                .iter()
3168                .map(|field| field.name().as_str())
3169                .collect::<Vec<_>>()
3170        );
3171    }
3172
3173    /// A label set that already names the metric keeps the one column it has.
3174    #[test]
3175    fn a_present_name_tag_is_not_declared_twice() {
3176        let sources = [vec!["host".to_string(), METRIC_NAME.to_string()]];
3177        let tree = compiled_test_tree("x");
3178        let schema = PromPlanner::fused_root_schema("x", &tree, &sources, "ts", FieldKind::Float)
3179            .unwrap()
3180            .unwrap();
3181        assert_eq!(
3182            vec!["ts", "x", "host", METRIC_NAME],
3183            schema
3184                .fields()
3185                .iter()
3186                .map(|field| field.name().as_str())
3187                .collect::<Vec<_>>()
3188        );
3189    }
3190
3191    /// The value columns are named after the expression, so a tree whose own field is named
3192    /// `__name__` still publishes that value under the expression's name - the name column is the
3193    /// layout's own. A time index of that name collides with it, and the collision is reported
3194    /// rather than published as a layout the reader cannot address.
3195    #[test]
3196    fn a_time_index_named_after_the_metric_name_is_reported() {
3197        let sources = [vec!["host".to_string()]];
3198        // The field is renamed by the expression, so it no longer stands where the name column is.
3199        let tree = compiled_test_tree_with_fields("x", &[METRIC_NAME]);
3200        let schema = PromPlanner::fused_root_schema("x", &tree, &sources, "ts", FieldKind::Float)
3201            .unwrap()
3202            .unwrap_or_else(|| panic!("the value is named after the expression"));
3203        assert_eq!(
3204            vec!["ts", "x", "host", METRIC_NAME],
3205            schema
3206                .fields()
3207                .iter()
3208                .map(|field| field.name().as_str())
3209                .collect::<Vec<_>>()
3210        );
3211        // A time index of that name collides with the row-name column, and the error names it.
3212        let tree = compiled_test_tree("x");
3213        let error =
3214            PromPlanner::fused_root_schema("x", &tree, &sources, METRIC_NAME, FieldKind::Float)
3215                .expect_err("a time index named after the metric collides with the name column");
3216        let message = error.to_string().to_lowercase();
3217        assert!(message.contains("duplicate"), "{message}");
3218        assert!(message.contains(METRIC_NAME), "{message}");
3219    }
3220
3221    /// A `__name__` rewrite publishes a name column, canonicalizes the complete runtime label set,
3222    /// and leaves the name dropped wherever a kernel computes a value of its own.
3223    #[test]
3224    fn name_rewrite_publishes_a_column_and_is_canonicalized() {
3225        let columns = [vec!["host".to_string(), "kind".to_string()]];
3226        let runtime = [vec![
3227            "host".to_string(),
3228            "kind".to_string(),
3229            METRIC_NAME.to_string(),
3230        ]];
3231        let tree =
3232            compiled_test_tree(r#"label_replace(x, "__name__", "same", "__name__", "(.*)")"#);
3233        assert_eq!(
3234            Some(vec!["host".into(), "kind".into(), METRIC_NAME.into()]),
3235            fused_output_tags(tree.root(), &columns),
3236            "a written name is a column the output publishes"
3237        );
3238        let collected = promql::native::canonicalize::merge_label_rewrites(&tree, &runtime)
3239            .expect("the pass produces a legal tree");
3240        assert!(
3241            matches!(collected.root().expr, NativeExpr::Merge { .. }),
3242            "a name rewrite writes an existing runtime label: {collected}"
3243        );
3244        assert_eq!(
3245            fused_output_tags(tree.root(), &columns),
3246            fused_output_tags(collected.root(), &columns),
3247            "collecting the pieces does not change the columns"
3248        );
3249
3250        // A delete-only rewrite over a scan whose columns carry no name publishes none.
3251        let deleted = compiled_test_tree(r#"label_replace(x, "__name__", "", "__name__", "(.*)")"#);
3252        assert_eq!(
3253            Some(vec!["host".into(), "kind".into()]),
3254            fused_output_tags(deleted.root(), &columns)
3255        );
3256
3257        // A kernel that computes a value of its own drops the name a rewrite below it wrote.
3258        for query in [
3259            r#"abs(label_replace(x, "__name__", "same", "__name__", "(.*)"))"#,
3260            r#"histogram_count(label_replace(x, "__name__", "same", "__name__", "(.*)"))"#,
3261            r#"timestamp(label_replace(x, "__name__", "same", "__name__", "(.*)"))"#,
3262            r#"sum(label_replace(x, "__name__", "same", "__name__", "(.*)"))"#,
3263        ] {
3264            let tree = compiled_test_tree(query);
3265            let tags = fused_output_tags(tree.root(), &columns)
3266                .unwrap_or_else(|| panic!("{query} derives its columns"));
3267            assert!(
3268                !tags.iter().any(|tag| tag == METRIC_NAME),
3269                "{query}: {tags:?}"
3270            );
3271        }
3272    }
3273
3274    /// A name write is collected even above a kernel that dropped the name: the scan below it can
3275    /// still hold several metrics whose ordinary labels are equal, so writing one name can fold them
3276    /// into one identity. The output still publishes the written name.
3277    #[test]
3278    fn a_name_rewrite_above_a_dropped_name_is_collected() {
3279        let runtime = [vec![
3280            "host".to_string(),
3281            "kind".to_string(),
3282            METRIC_NAME.to_string(),
3283        ]];
3284        let tree =
3285            compiled_test_tree(r#"label_replace(abs(x), "__name__", "same", "missing", "(.*)")"#);
3286        let collected = promql::native::canonicalize::merge_label_rewrites(&tree, &runtime)
3287            .expect("the pass produces a legal tree");
3288        assert!(
3289            matches!(collected.root().expr, NativeExpr::Merge { .. }),
3290            "the merge sits above the name rewrite: {collected}"
3291        );
3292        assert_eq!(
3293            1,
3294            collected.to_string().matches("Merge").count(),
3295            "exactly one merge: {collected}"
3296        );
3297        // The rewrite writes a name over a dropped one, so the output publishes a name column.
3298        assert_eq!(
3299            Some(vec!["host".into(), "kind".into(), METRIC_NAME.into()]),
3300            fused_output_tags(collected.root(), &[vec!["host".into(), "kind".into()]])
3301        );
3302
3303        // A fresh ordinary destination above the same kernel is still uncollected: no scan can carry
3304        // an ordinary label it does not declare.
3305        let fresh = compiled_test_tree(r#"label_replace(abs(x), "dst", "$1", "host", "(.*)")"#);
3306        let collected = promql::native::canonicalize::merge_label_rewrites(&fresh, &runtime)
3307            .expect("the pass produces a legal tree");
3308        assert!(
3309            !collected.to_string().contains("Merge"),
3310            "a fresh ordinary destination does not alias: {collected}"
3311        );
3312    }
3313
3314    #[test]
3315    fn group_right_copies_included_labels_into_output_tags() {
3316        let sources = [
3317            vec!["pod".into(), "container".into()],
3318            vec!["pod".into(), "workload".into()],
3319        ];
3320        let tree = compiled_test_tree("x * on(pod) group_right(container) y");
3321        assert_eq!(
3322            Some(vec!["pod".into(), "workload".into(), "container".into()]),
3323            fused_output_tags(tree.root(), &sources)
3324        );
3325    }
3326
3327    /// `group_left(__name__)` copies the one side's name onto an arithmetic result: the operation
3328    /// drops the name before it copies an included label, so the copied name is a column. A one side
3329    /// without a name cannot provide one, so the column leaves the set.
3330    #[test]
3331    fn an_included_metric_name_is_an_output_column() {
3332        let sources = [
3333            vec!["host".to_string()],
3334            vec!["host".to_string(), METRIC_NAME.to_string()],
3335        ];
3336        let included = compiled_test_tree(
3337            r#"x * on(host) group_left(__name__) label_replace(y, "__name__", "renamed", "__name__", "(.*)")"#,
3338        );
3339        assert_eq!(
3340            Some(vec!["host".to_string(), METRIC_NAME.to_string()]),
3341            fused_output_tags(included.root(), &sources)
3342        );
3343        let unnamed = compiled_test_tree(r#"x * on(host) group_left(__name__) y"#);
3344        assert_eq!(
3345            Some(vec!["host".to_string()]),
3346            fused_output_tags(
3347                unnamed.root(),
3348                &[vec!["host".to_string()], vec!["host".to_string()]]
3349            )
3350        );
3351    }
3352
3353    #[test]
3354    fn numeric_aggregate_projection_keeps_grouping_tags_and_value_schema() {
3355        let sources = [vec![
3356            "host".to_string(),
3357            "kind".to_string(),
3358            "zone".to_string(),
3359        ]];
3360        for query in [
3361            "sum by (host, zone) ((x))",
3362            "min by (host, zone) ((x))",
3363            "max without (kind) ((x))",
3364        ] {
3365            let tree = compiled_test_tree(query);
3366            let NativeType::Samples(schema) = &tree.root().output else {
3367                panic!("{query} must produce evaluated samples");
3368            };
3369            assert_eq!(1, schema.fields.len(), "{query}");
3370            assert_eq!("v0", schema.fields[0].name.as_ref(), "{query}");
3371            let tags = fused_output_tags(tree.root(), &sources).unwrap();
3372            assert_eq!(
3373                vec!["host", "zone"],
3374                tags.iter().map(String::as_str).collect::<Vec<_>>(),
3375                "{query}"
3376            );
3377        }
3378
3379        let tree = compiled_test_tree_with_fields("sum by (zone, host) ((x))", &["v0", "v1"]);
3380        let NativeType::Samples(schema) = &tree.root().output else {
3381            panic!("multi-field aggregate must produce evaluated samples");
3382        };
3383        assert_eq!(
3384            vec!["v0", "v1"],
3385            schema
3386                .fields
3387                .iter()
3388                .map(|field| field.name.as_ref())
3389                .collect::<Vec<_>>()
3390        );
3391        let expression = "sum by (zone, host) ((x))";
3392        let output = fused_output_schema(
3393            expression,
3394            &["v0".to_string(), "v1".to_string()],
3395            &["zone".to_string(), "host".to_string()],
3396            "ts",
3397            FieldKind::Float,
3398        )
3399        .unwrap();
3400        assert_eq!(
3401            vec![
3402                "ts".to_string(),
3403                format!("{expression}.v0"),
3404                format!("{expression}.v1"),
3405                "zone".to_string(),
3406                "host".to_string(),
3407            ],
3408            output
3409                .fields()
3410                .iter()
3411                .map(|field| field.name().as_str())
3412                .collect::<Vec<_>>()
3413        );
3414        assert_eq!(
3415            ArrowDataType::Timestamp(ArrowTimeUnit::Millisecond, None),
3416            *output.field(0).data_type()
3417        );
3418        assert_eq!(ArrowDataType::Float64, *output.field(1).data_type());
3419        assert_eq!(ArrowDataType::Float64, *output.field(2).data_type());
3420        assert_eq!(ArrowDataType::Utf8, *output.field(3).data_type());
3421        assert_eq!(ArrowDataType::Utf8, *output.field(4).data_type());
3422    }
3423
3424    #[test]
3425    fn histogram_quantile_output_tags_drop_bucket_and_metadata_labels() {
3426        let sources = [vec![
3427            "le".to_string(),
3428            "__name__".to_string(),
3429            "__type__".to_string(),
3430            "__unit__".to_string(),
3431            "job".to_string(),
3432        ]];
3433        let tree = compiled_test_tree("histogram_quantile(0.9, x)");
3434        assert_eq!(
3435            Some(vec!["job".to_string()]),
3436            fused_output_tags(tree.root(), &sources)
3437        );
3438    }
3439
3440    /// A map that only computes values passes its input's labels through unchanged.
3441    #[test]
3442    fn match_output_tags_pass_through_pointwise_math() {
3443        let sources = [vec!["host".to_string(), "kind".to_string()]];
3444        let tree = compiled_test_tree("abs(x) * 2");
3445        assert_eq!(
3446            Some(vec!["host".to_string(), "kind".to_string()]),
3447            fused_output_tags(tree.root(), &sources)
3448        );
3449    }
3450
3451    #[test]
3452    fn millisecond_scan_bounds_preserve_open_closed_and_maximum_edges() {
3453        let inclusive = scan_time_filter(0, 10, true, "ts").to_string();
3454        assert!(inclusive.contains(">="), "{inclusive}");
3455        assert!(inclusive.contains("<="), "{inclusive}");
3456
3457        let exclusive = scan_time_filter(0, 10, false, "ts").to_string();
3458        assert!(exclusive.contains("> "), "{exclusive}");
3459        assert!(!exclusive.contains(">="), "{exclusive}");
3460        assert!(exclusive.contains("<="), "{exclusive}");
3461
3462        let maximum = scan_time_filter(i64::MAX, i64::MAX, false, "ts").to_string();
3463        assert!(maximum.contains("> "), "{maximum}");
3464        assert!(!maximum.contains(">="), "{maximum}");
3465        assert!(maximum.contains("<="), "{maximum}");
3466    }
3467
3468    #[test]
3469    fn native_promql_requested_is_false_when_extension_is_absent() {
3470        let query_ctx = Arc::new(QueryContextBuilder::default().build());
3471
3472        assert!(!native_promql_requested(&query_ctx));
3473    }
3474
3475    #[test]
3476    fn native_promql_requested_accepts_true_case_insensitively() {
3477        for value in ["true", "TRUE", "TrUe"] {
3478            let query_ctx = Arc::new(
3479                QueryContextBuilder::default()
3480                    .set_extension(NATIVE_PROMQL_EXTENSION_KEY.to_string(), value.to_string())
3481                    .build(),
3482            );
3483
3484            assert!(native_promql_requested(&query_ctx), "value: {value}");
3485        }
3486    }
3487
3488    #[test]
3489    fn native_promql_requested_rejects_false_values() {
3490        for value in ["false", "FALSE", "False"] {
3491            let query_ctx = Arc::new(
3492                QueryContextBuilder::default()
3493                    .set_extension(NATIVE_PROMQL_EXTENSION_KEY.to_string(), value.to_string())
3494                    .build(),
3495            );
3496
3497            assert!(!native_promql_requested(&query_ctx), "value: {value:?}");
3498        }
3499    }
3500}