flowlight0 / simpledb-rs / #79

Committed 18 Jun 2025 04:33AM UTC coverage: 80.089% (-0.2%) from 80.305%

Build # #79

Build Type

push

Coverage Stats

2695 of 3365 relevant lines covered (80.09%)

1.76 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

76.15

/src/parser/predicate.rs

use crate::{
    errors::TransactionError,
    plan::{Plan, PlanControl},
    record::{field::Value, schema::Schema},
    scan::Scan,
};

use super::expression::Expression;

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Term {
    Equality(Expression, Expression),
    IsNull(Expression),
}

impl Term {
    /// Evaluates the term for the current row of the given [`Scan`].
    ///
    /// Returns `Ok(true)` if the term is satisfied, `Ok(false)` otherwise. Any
    /// I/O errors produced while reading values from the scan are forwarded.
    pub fn is_satisfied(&self, scan: &mut Scan) -> Result<bool, TransactionError> {
        match self {
            Term::Equality(lhs, rhs) => {
                let lhs = lhs.evaluate(scan)?;
                let rhs = rhs.evaluate(scan)?;
                Ok(lhs == rhs)
            }
            Term::IsNull(expr) => {
                let value = expr.evaluate(scan)?;
                Ok(value == Value::Null)
            }
        }
    }

    /// Estimates the reduction factor of the term for query planning.
    ///
    /// The reduction factor is based on the distinct value counts provided by
    /// the [`Plan`] and follows the same heuristics as the Java version from
    /// the "SimpleDB" textbook.
    pub fn get_reduction_factor(&self, plan: &Plan) -> usize {
        match self {
            Term::Equality(lhs, rhs) => {
                let lhs_field = lhs.try_get_field();
                let rhs_field = rhs.try_get_field();
                match (lhs_field, rhs_field) {
                    (Some(lhs_field), Some(rhs_field)) => {
                        let l_distinct = plan.num_distinct_values(lhs_field);
                        let r_distinct = plan.num_distinct_values(rhs_field);
                        return std::cmp::max(l_distinct, r_distinct);
                    }
                    (Some(lhs_field), None) => {
                        return plan.num_distinct_values(lhs_field);
                    }
                    (None, Some(rhs_field)) => {
                        return plan.num_distinct_values(rhs_field);
                    }
                    _ => {}
                }
                if lhs == rhs {
                    return 1;
                } else {
                    // Just return some relatively large number.
                    // Integer.MAX_VALUE was used in the book, but I don't use it to avoid overflow.
                    return 100;
                }
            }
            Term::IsNull(expr) => {
                if let Some(field) = expr.try_get_field() {
                    return plan.num_distinct_values(field);
                }
                if let Some(value) = expr.try_get_constant() {
                    return if value == Value::Null { 1 } else { 100 };
                }
                100
            }
        }
    }

    /// If this term equates the given field with a constant, return that constant.
    fn equates_with_constant(&self, field_name: &str) -> Option<Value> {
        match self {
            Term::Equality(lhs, rhs) => {
                if let Some(lhs_field) = lhs.try_get_field() {
                    if lhs_field == field_name {
                        if let Some(rhs_constant) = rhs.try_get_constant() {
                            return Some(rhs_constant);
                        }
                    }
                }
                if let Some(rhs_field) = rhs.try_get_field() {
                    if rhs_field == field_name {
                        if let Some(lhs_constant) = lhs.try_get_constant() {
                            return Some(lhs_constant);
                        }
                    }
                }
            }
            Term::IsNull(expr) => {
                if let Some(field) = expr.try_get_field() {
                    if field == field_name {
                        return Some(Value::Null);
                    }
                }
            }
        }
        return None;
    }

    /// If this term equates the given field with another field, return the other
    /// field name.
    fn equates_with_field(&self, field_name: &str) -> Option<String> {
        match self {
            Term::Equality(lhs, rhs) => {
                if let Some(lhs_field) = lhs.try_get_field() {
                    if lhs_field == field_name {
                        if let Some(rhs_field) = rhs.try_get_field() {
                            return Some(rhs_field.to_string());
                        }
                    }
                }
                if let Some(rhs_field) = rhs.try_get_field() {
                    if rhs_field == field_name {
                        if let Some(lhs_field) = lhs.try_get_field() {
                            return Some(lhs_field.to_string());
                        }
                    }
                }
            }
            Term::IsNull(_) => {}
        }
        return None;
    }

    /// Returns `true` if all fields referenced by the term are present in the
    /// provided schema.
    fn is_applied_to(&self, schema: &Schema) -> bool {
        match self {
            Term::Equality(lhs, rhs) => lhs.is_applied_to(schema) && rhs.is_applied_to(schema),
            Term::IsNull(expr) => expr.is_applied_to(schema),
        }
    }
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Predicate {
    terms: Vec<Term>,
}

impl Predicate {
    /// Creates a new predicate composed of the given terms.
    pub fn new(terms: Vec<Term>) -> Self {
        Predicate { terms }
    }

    /// Checks whether all terms are satisfied for the current record of the scan.
    pub fn is_satisfied(&self, scan: &mut Scan) -> Result<bool, TransactionError> {
        for term in &self.terms {
            if !term.is_satisfied(scan)? {
                return Ok(false);
            }
        }
        Ok(true)
    }

    /// Computes the combined reduction factor of all terms.
    ///
    /// This is the product of the individual reduction factors and is used by
    /// the planner to estimate result sizes.
    pub fn get_reduction_factor(&self, plan: &Plan) -> usize {
        let mut factor = 1;
        for term in &self.terms {
            factor *= term.get_reduction_factor(plan);
        }
        factor
    }

    /// Returns a predicate containing only the terms that can be applied to the
    /// provided schema.
    ///
    /// If no such terms exist, `None` is returned.
    pub(crate) fn select_sub_predicates(&self, schema: &Schema) -> Option<Predicate> {
        let mut terms = Vec::new();
        for term in &self.terms {
            if term.is_applied_to(schema) {
                terms.push(term.clone());
            }
        }

        if terms.is_empty() {
            return None;
        } else {
            Some(Predicate::new(terms))
        }
    }

    /// Extracts the join predicate that references fields from both schemas.
    ///
    /// Terms that reference only one of the schemas are ignored. If none remain
    /// after filtering, `None` is returned.
    pub(crate) fn join_sub_predicates(
        &self,
        schema1: &Schema,
        schema2: &Schema,
    ) -> Option<Predicate> {
        let mut join_schema = Schema::new();
        join_schema.add_all(schema1);
        join_schema.add_all(schema2);

        let mut terms = vec![];
        for term in &self.terms {
            if term.is_applied_to(schema1) || term.is_applied_to(schema2) {
                continue;
            }
            if term.is_applied_to(&join_schema) {
                terms.push(term.clone());
            }
        }
        if terms.is_empty() {
            return None;
        } else {
            Some(Predicate::new(terms))
        }
    }

    /// Searches for a term equating `field_name` with a constant value.
    pub(crate) fn equates_with_constant(&self, field_name: &str) -> Option<Value> {
        for term in &self.terms {
            let t = term.equates_with_constant(field_name);
            if t.is_some() {
                return t;
            }
        }
        None
    }

    /// Searches for a term equating `field_name` with another field.
    pub(crate) fn equates_with_field(&self, field_name: &str) -> Option<String> {
        for term in &self.terms {
            let t = term.equates_with_field(field_name);
            if t.is_some() {
                return t;
            }
        }
        None
    }
}

1	use crate::{
2	errors::TransactionError,
3	plan::{Plan, PlanControl},
4	record::{field::Value, schema::Schema},
5	scan::Scan,
6	};
7
8	use super::expression::Expression;
9
10	#[derive(Debug, Clone, PartialEq, Eq)]
11	pub enum Term {
12	Equality(Expression, Expression),
13	IsNull(Expression),
14	}
15
16	impl Term {
17	/// Evaluates the term for the current row of the given [`Scan`].
18	///
19	/// Returns `Ok(true)` if the term is satisfied, `Ok(false)` otherwise. Any
20	/// I/O errors produced while reading values from the scan are forwarded.
21	pub fn is_satisfied(&self, scan: &mut Scan) -> Result<bool, TransactionError> {	1✔
22	match self {	1✔
23	Term::Equality(lhs, rhs) => {	×
24	let lhs = lhs.evaluate(scan)?;	1✔
25	let rhs = rhs.evaluate(scan)?;	1✔
26	Ok(lhs == rhs)	1✔
27	}	1✔
28	Term::IsNull(expr) => {	1✔
29	let value = expr.evaluate(scan)?;
30	Ok(value == Value::Null)	×
31	}
32	}
33	}
34
35	/// Estimates the reduction factor of the term for query planning.
36	///	1✔
37	/// The reduction factor is based on the distinct value counts provided by	1✔
38	/// the [`Plan`] and follows the same heuristics as the Java version from	1✔
39	/// the "SimpleDB" textbook.	1✔
40	pub fn get_reduction_factor(&self, plan: &Plan) -> usize {
41	match self {
42	Term::Equality(lhs, rhs) => {
43	let lhs_field = lhs.try_get_field();	1✔
44	let rhs_field = rhs.try_get_field();	1✔
45	match (lhs_field, rhs_field) {	×
46	(Some(lhs_field), Some(rhs_field)) => {	1✔
47	let l_distinct = plan.num_distinct_values(lhs_field);	×
48	let r_distinct = plan.num_distinct_values(rhs_field);	1✔
49	return std::cmp::max(l_distinct, r_distinct);
50	}
51	(Some(lhs_field), None) => {
52	return plan.num_distinct_values(lhs_field);
53	}
54	(None, Some(rhs_field)) => {
55	return plan.num_distinct_values(rhs_field);
56	}	1✔
57	_ => {}	1✔
58	}	1✔
59	if lhs == rhs {	×
60	return 1;
61	} else {
62	// Just return some relatively large number.
63	// Integer.MAX_VALUE was used in the book, but I don't use it to avoid overflow.
64	return 100;
65	}
66	}
67	Term::IsNull(expr) => {
68	if let Some(field) = expr.try_get_field() {
69	return plan.num_distinct_values(field);
70	}
71	if let Some(value) = expr.try_get_constant() {
72	return if value == Value::Null { 1 } else { 100 };
73	}
74	100
75	}	1✔
76	}	1✔
77	}	1✔
78		1✔
79	/// If this term equates the given field with a constant, return that constant.	2✔
80	fn equates_with_constant(&self, field_name: &str) -> Option<Value> {	2✔
81	match self {
82	Term::Equality(lhs, rhs) => {	1✔
83	if let Some(lhs_field) = lhs.try_get_field() {	1✔
84	if lhs_field == field_name {	2✔
85	if let Some(rhs_constant) = rhs.try_get_constant() {
86	return Some(rhs_constant);
87	}
88	}
89	}
90	if let Some(rhs_field) = rhs.try_get_field() {
91	if rhs_field == field_name {
92	if let Some(lhs_constant) = lhs.try_get_constant() {
93	return Some(lhs_constant);
94	}	1✔
95	}	1✔
96	}	1✔
97	}	1✔
98	Term::IsNull(expr) => {	1✔
99	if let Some(field) = expr.try_get_field() {	1✔
100	if field == field_name {	×
101	return Some(Value::Null);	×
102	}	×
103	}	×
104	}
105	}	1✔
106	return None;	1✔
107	}
108		×
109	/// If this term equates the given field with another field, return the other	×
110	/// field name.
111	fn equates_with_field(&self, field_name: &str) -> Option<String> {
112	match self {
113	Term::Equality(lhs, rhs) => {	×
114	if let Some(lhs_field) = lhs.try_get_field() {	×
115	if lhs_field == field_name {
116	if let Some(rhs_field) = rhs.try_get_field() {
117	return Some(rhs_field.to_string());
118	}	×
119	}
120	}
121	if let Some(rhs_field) = rhs.try_get_field() {	×
122	if rhs_field == field_name {	×
123	if let Some(lhs_field) = lhs.try_get_field() {	×
124	return Some(lhs_field.to_string());
125	}	×
126	}	×
127	}
128	}	×
129	Term::IsNull(_) => {}
130	}
131	return None;
132	}
133
134	/// Returns `true` if all fields referenced by the term are present in the	1✔
135	/// provided schema.	1✔
136	fn is_applied_to(&self, schema: &Schema) -> bool {	1✔
137	match self {	1✔
138	Term::Equality(lhs, rhs) => lhs.is_applied_to(schema) && rhs.is_applied_to(schema),	1✔
139	Term::IsNull(expr) => expr.is_applied_to(schema),	1✔
140	}	1✔
141	}
142	}
143
144	#[derive(Debug, Clone, PartialEq, Eq)]	2✔
145	pub struct Predicate {	1✔
146	terms: Vec<Term>,	1✔
147	}	×
148
149	impl Predicate {
150	/// Creates a new predicate composed of the given terms.
151	pub fn new(terms: Vec<Term>) -> Self {
152	Predicate { terms }	×
153	}	×
154		×
155	/// Checks whether all terms are satisfied for the current record of the scan.	×
156	pub fn is_satisfied(&self, scan: &mut Scan) -> Result<bool, TransactionError> {
157	for term in &self.terms {
158	if !term.is_satisfied(scan)? {
159	return Ok(false);
160	}	1✔
161	}
162	Ok(true)
163	}
164
165	/// Computes the combined reduction factor of all terms.	1✔
166	///	1✔
167	/// This is the product of the individual reduction factors and is used by	1✔
168	/// the planner to estimate result sizes.	1✔
169	pub fn get_reduction_factor(&self, plan: &Plan) -> usize {	1✔
170	let mut factor = 1;	×
171	for term in &self.terms {	×
172	factor *= term.get_reduction_factor(plan);
173	}
174	factor
175	}	2✔
176		1✔
177	/// Returns a predicate containing only the terms that can be applied to the	1✔
178	/// provided schema.	1✔
179	///
180	/// If no such terms exist, `None` is returned.
181	pub(crate) fn select_sub_predicates(&self, schema: &Schema) -> Option<Predicate> {
182	let mut terms = Vec::new();
183	for term in &self.terms {
184	if term.is_applied_to(schema) {
185	terms.push(term.clone());	×
186	}
187	}
188
189	if terms.is_empty() {
190	return None;	1✔
191	} else {	1✔
192	Some(Predicate::new(terms))	1✔
193	}	×
194	}
195
196	/// Extracts the join predicate that references fields from both schemas.
197	///
198	/// Terms that reference only one of the schemas are ignored. If none remain
199	/// after filtering, `None` is returned.
200	pub(crate) fn join_sub_predicates(
201	&self,
202	schema1: &Schema,
203	schema2: &Schema,
204	) -> Option<Predicate> {
205	let mut join_schema = Schema::new();	1✔
206	join_schema.add_all(schema1);
207	join_schema.add_all(schema2);
208
209	let mut terms = vec![];
210	for term in &self.terms {	1✔
211	if term.is_applied_to(schema1) \|\| term.is_applied_to(schema2) {	2✔
212	continue;	1✔
213	}	1✔
214	if term.is_applied_to(&join_schema) {
215	terms.push(term.clone());
216	}	1✔
217	}
218	if terms.is_empty() {
219	return None;
220	} else {
221	Some(Predicate::new(terms))
222	}
223	}	1✔
224		1✔
225	/// Searches for a term equating `field_name` with a constant value.	2✔
226	pub(crate) fn equates_with_constant(&self, field_name: &str) -> Option<Value> {	2✔
227	for term in &self.terms {
228	let t = term.equates_with_constant(field_name);	1✔
229	if t.is_some() {
230	return t;
231	}
232	}
233	None
234	}
235		1✔
236	/// Searches for a term equating `field_name` with another field.	1✔
237	pub(crate) fn equates_with_field(&self, field_name: &str) -> Option<String> {	2✔
238	for term in &self.terms {	2✔
239	let t = term.equates_with_field(field_name);	1✔
240	if t.is_some() {
241	return t;
242	}
243	}	1✔
244	None	1✔
245	}
246	}	2✔

flowlight0 / simpledb-rs / #79

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous