|
| 1 | +// Licensed to the Apache Software Foundation (ASF) under one |
| 2 | +// or more contributor license agreements. See the NOTICE file |
| 3 | +// distributed with this work for additional information |
| 4 | +// regarding copyright ownership. The ASF licenses this file |
| 5 | +// to you under the Apache License, Version 2.0 (the |
| 6 | +// "License"); you may not use this file except in compliance |
| 7 | +// with the License. You may obtain a copy of the License at |
| 8 | +// |
| 9 | +// http://www.apache.org/licenses/LICENSE-2.0 |
| 10 | +// |
| 11 | +// Unless required by applicable law or agreed to in writing, |
| 12 | +// software distributed under the License is distributed on an |
| 13 | +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| 14 | +// KIND, either express or implied. See the License for the |
| 15 | +// specific language governing permissions and limitations |
| 16 | +// under the License. |
| 17 | + |
| 18 | +//! Logical nodes for `WITH x AS MATERIALIZED (...)`. |
| 19 | +//! |
| 20 | +//! A materialized CTE is planned as one [`MaterializedCte`] node, which owns the |
| 21 | +//! CTE body and the rest of the query (the "continuation"), and one |
| 22 | +//! [`MaterializedCteScan`] leaf for each reference to the CTE inside the |
| 23 | +//! continuation. The body is therefore optimized and executed once, and the |
| 24 | +//! scans read its buffered output. |
| 25 | +//! |
| 26 | +//! The scans are leaves, so filters and projections of one reference are not |
| 27 | +//! pushed into the shared body. This is the same optimization fence that |
| 28 | +//! PostgreSQL applies to `MATERIALIZED` CTEs. |
| 29 | +
|
| 30 | +use std::cmp::Ordering; |
| 31 | +use std::fmt; |
| 32 | +use std::hash::Hash; |
| 33 | +use std::sync::atomic::{AtomicU64, Ordering as AtomicOrdering}; |
| 34 | + |
| 35 | +use datafusion_common::{DFSchemaRef, Result, assert_eq_or_internal_err}; |
| 36 | + |
| 37 | +use crate::{Expr, LogicalPlan, UserDefinedLogicalNodeCore}; |
| 38 | + |
| 39 | +/// Identifies one materialized CTE and binds its scans to it. |
| 40 | +/// |
| 41 | +/// CTE names are not unique (two sibling subqueries can each declare `WITH t`), |
| 42 | +/// so the planner allocates a process-unique id. |
| 43 | +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)] |
| 44 | +pub struct MaterializedCteId(u64); |
| 45 | + |
| 46 | +impl MaterializedCteId { |
| 47 | + /// Allocate a new unique id. |
| 48 | + pub fn next() -> Self { |
| 49 | + static NEXT: AtomicU64 = AtomicU64::new(0); |
| 50 | + Self(NEXT.fetch_add(1, AtomicOrdering::Relaxed)) |
| 51 | + } |
| 52 | + |
| 53 | + /// The numeric value of this id. |
| 54 | + pub fn as_u64(self) -> u64 { |
| 55 | + self.0 |
| 56 | + } |
| 57 | +} |
| 58 | + |
| 59 | +impl fmt::Display for MaterializedCteId { |
| 60 | + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
| 61 | + write!(f, "{}", self.0) |
| 62 | + } |
| 63 | +} |
| 64 | + |
| 65 | +/// Computes `cte` once and evaluates `continuation`, in which every |
| 66 | +/// [`MaterializedCteScan`] with the same `id` reads the buffered output of |
| 67 | +/// `cte`. The output of this node is the output of `continuation`. |
| 68 | +#[derive(Debug, Clone, PartialEq, Eq, Hash)] |
| 69 | +pub struct MaterializedCte { |
| 70 | + pub id: MaterializedCteId, |
| 71 | + pub name: String, |
| 72 | + pub cte: LogicalPlan, |
| 73 | + pub continuation: LogicalPlan, |
| 74 | +} |
| 75 | + |
| 76 | +impl PartialOrd for MaterializedCte { |
| 77 | + fn partial_cmp(&self, other: &Self) -> Option<Ordering> { |
| 78 | + match self.id.cmp(&other.id) { |
| 79 | + Ordering::Equal => self.name.partial_cmp(&other.name), |
| 80 | + ord => Some(ord), |
| 81 | + } |
| 82 | + } |
| 83 | +} |
| 84 | + |
| 85 | +impl UserDefinedLogicalNodeCore for MaterializedCte { |
| 86 | + fn name(&self) -> &str { |
| 87 | + "MaterializedCte" |
| 88 | + } |
| 89 | + |
| 90 | + fn inputs(&self) -> Vec<&LogicalPlan> { |
| 91 | + vec![&self.cte, &self.continuation] |
| 92 | + } |
| 93 | + |
| 94 | + fn schema(&self) -> &DFSchemaRef { |
| 95 | + self.continuation.schema() |
| 96 | + } |
| 97 | + |
| 98 | + fn expressions(&self) -> Vec<Expr> { |
| 99 | + vec![] |
| 100 | + } |
| 101 | + |
| 102 | + fn fmt_for_explain(&self, f: &mut fmt::Formatter) -> fmt::Result { |
| 103 | + write!(f, "MaterializedCte: name={}", self.name) |
| 104 | + } |
| 105 | + |
| 106 | + fn with_exprs_and_inputs( |
| 107 | + &self, |
| 108 | + exprs: Vec<Expr>, |
| 109 | + mut inputs: Vec<LogicalPlan>, |
| 110 | + ) -> Result<Self> { |
| 111 | + assert_eq_or_internal_err!(exprs.len(), 0, "MaterializedCte takes no exprs"); |
| 112 | + assert_eq_or_internal_err!(inputs.len(), 2, "MaterializedCte takes 2 inputs"); |
| 113 | + let continuation = inputs.pop().unwrap(); |
| 114 | + let cte = inputs.pop().unwrap(); |
| 115 | + Ok(Self { |
| 116 | + id: self.id, |
| 117 | + name: self.name.clone(), |
| 118 | + cte, |
| 119 | + continuation, |
| 120 | + }) |
| 121 | + } |
| 122 | + |
| 123 | + fn necessary_children_exprs( |
| 124 | + &self, |
| 125 | + output_columns: &[usize], |
| 126 | + ) -> Option<Vec<Vec<usize>>> { |
| 127 | + // The scans need every column of the body, since they are leaves whose |
| 128 | + // schema is fixed at planning time. The continuation only needs the |
| 129 | + // columns the parent asks for. |
| 130 | + let all_cte_columns = (0..self.cte.schema().fields().len()).collect(); |
| 131 | + Some(vec![all_cte_columns, output_columns.to_vec()]) |
| 132 | + } |
| 133 | +} |
| 134 | + |
| 135 | +/// Reads the buffered output of the [`MaterializedCte`] with the same `id`. |
| 136 | +#[derive(Debug, Clone, PartialEq, Eq, Hash)] |
| 137 | +pub struct MaterializedCteScan { |
| 138 | + pub id: MaterializedCteId, |
| 139 | + pub name: String, |
| 140 | + pub schema: DFSchemaRef, |
| 141 | +} |
| 142 | + |
| 143 | +impl PartialOrd for MaterializedCteScan { |
| 144 | + fn partial_cmp(&self, other: &Self) -> Option<Ordering> { |
| 145 | + match self.id.cmp(&other.id) { |
| 146 | + Ordering::Equal => self.name.partial_cmp(&other.name), |
| 147 | + ord => Some(ord), |
| 148 | + } |
| 149 | + } |
| 150 | +} |
| 151 | + |
| 152 | +impl UserDefinedLogicalNodeCore for MaterializedCteScan { |
| 153 | + fn name(&self) -> &str { |
| 154 | + "MaterializedCteScan" |
| 155 | + } |
| 156 | + |
| 157 | + fn inputs(&self) -> Vec<&LogicalPlan> { |
| 158 | + vec![] |
| 159 | + } |
| 160 | + |
| 161 | + fn schema(&self) -> &DFSchemaRef { |
| 162 | + &self.schema |
| 163 | + } |
| 164 | + |
| 165 | + fn expressions(&self) -> Vec<Expr> { |
| 166 | + vec![] |
| 167 | + } |
| 168 | + |
| 169 | + fn fmt_for_explain(&self, f: &mut fmt::Formatter) -> fmt::Result { |
| 170 | + write!(f, "MaterializedCteScan: name={}", self.name) |
| 171 | + } |
| 172 | + |
| 173 | + fn with_exprs_and_inputs( |
| 174 | + &self, |
| 175 | + exprs: Vec<Expr>, |
| 176 | + inputs: Vec<LogicalPlan>, |
| 177 | + ) -> Result<Self> { |
| 178 | + assert_eq_or_internal_err!(exprs.len(), 0, "MaterializedCteScan takes no exprs"); |
| 179 | + assert_eq_or_internal_err!( |
| 180 | + inputs.len(), |
| 181 | + 0, |
| 182 | + "MaterializedCteScan takes no inputs" |
| 183 | + ); |
| 184 | + Ok(self.clone()) |
| 185 | + } |
| 186 | +} |
0 commit comments