radixdb_executor/access/
index.rs

1//! Eligibility checks for physical index access paths.
2
3use radixdb_sql::ast::{Expression, InfixOperator, SelectStatement};
4use radixdb_storage::mvcc::engine::MVCCEngine;
5use radixdb_storage::traits::Engine;
6use rustc_hash::FxHashSet;
7
8use crate::operators::index_nested_loop::IndexLookupStrategy;
9use crate::utils::{extract_base_column_name, flatten_and_predicates};
10
11pub type IndexNestedLoopOpportunity = (String, IndexLookupStrategy, String, String, bool);
12
13/// Select the strongest usable point-lookup edge from an INNER/LEFT JOIN ON
14/// predicate. The complete equality set is retained to prove 0..1 cardinality
15/// through PK or full non-partial UNIQUE metadata.
16pub fn index_nested_loop_opportunity(
17    engine: &MVCCEngine,
18    right_expression: &Expression,
19    join_condition: Option<&Expression>,
20    join_type: &str,
21    left_alias: Option<&str>,
22    right_alias: Option<&str>,
23) -> Option<IndexNestedLoopOpportunity> {
24    if join_type.contains("RIGHT") || join_type.contains("FULL") {
25        return None;
26    }
27
28    let (table_name, effective_alias) = indexable_source(right_expression)?;
29    let condition = join_condition?;
30    let right_table_alias = effective_alias
31        .as_deref()
32        .or(right_alias)
33        .unwrap_or(&table_name);
34    let right_alias_lower = right_table_alias.to_lowercase();
35    let right_alias_len = right_alias_lower.len();
36    let starts_with_alias = |column: &str, alias: &str, alias_len: usize| {
37        column.len() > alias_len
38            && column.starts_with(alias)
39            && column.as_bytes()[alias_len] == b'.'
40    };
41
42    let transaction = engine.begin_transaction().ok()?;
43    let table = transaction.get_table(&table_name).ok()?;
44    let schema = table.schema();
45    let left_alias_lower = left_alias.map(str::to_lowercase);
46    let mut best: Option<(u8, IndexLookupStrategy, String, String)> = None;
47    let mut equality_inner_columns = FxHashSet::default();
48
49    for predicate in flatten_and_predicates(condition) {
50        let Some((left_column, right_column)) = simple_join_key(&predicate) else {
51            continue;
52        };
53        let left_lower = left_column.to_lowercase();
54        let right_lower = right_column.to_lowercase();
55        let (inner, outer) = if starts_with_alias(&left_lower, &right_alias_lower, right_alias_len)
56        {
57            (left_column, right_column)
58        } else if starts_with_alias(&right_lower, &right_alias_lower, right_alias_len) {
59            (right_column, left_column)
60        } else {
61            continue;
62        };
63        if let Some(left_alias) = left_alias_lower.as_deref() {
64            let outer_lower = outer.to_lowercase();
65            if !starts_with_alias(&outer_lower, left_alias, left_alias.len()) {
66                continue;
67            }
68        }
69
70        let inner_unqualified = extract_base_column_name(&inner).to_string();
71        let inner_lower = inner_unqualified.to_lowercase();
72        equality_inner_columns.insert(inner_lower.clone());
73        let candidate = if schema
74            .pk_column_index()
75            .is_some_and(|index| schema.columns[index].name_lower == inner_lower)
76        {
77            (3, IndexLookupStrategy::PrimaryKey)
78        } else if table.has_cold_segments() {
79            if table
80                .collect_row_ids_by_index_values(&inner_unqualified, &[])
81                .is_none()
82            {
83                continue;
84            }
85            let Some(index) = table.get_index_on_column(&inner_unqualified) else {
86                continue;
87            };
88            let priority = if index.is_unique() { 2 } else { 1 };
89            (
90                priority,
91                IndexLookupStrategy::SegmentedSecondaryIndex {
92                    column_name: inner_unqualified.clone(),
93                    index_name: index.name().to_string(),
94                },
95            )
96        } else {
97            let Some(index) = table.get_index_on_column(&inner_unqualified) else {
98                continue;
99            };
100            let priority = if index.is_unique() { 2 } else { 1 };
101            (priority, IndexLookupStrategy::SecondaryIndex(index))
102        };
103        if best
104            .as_ref()
105            .is_none_or(|(priority, _, _, _)| candidate.0 > *priority)
106        {
107            best = Some((candidate.0, candidate.1, inner_unqualified, outer));
108        }
109    }
110
111    let pk_unique = schema.pk_column_index().is_some_and(|index| {
112        equality_inner_columns.contains(schema.columns[index].name_lower.as_str())
113    });
114    let declared_unique = table
115        .get_unique_non_pk_indexes()
116        .into_iter()
117        .filter(|index| index.partial_predicate().is_none())
118        .any(|index| {
119            !index.column_names().is_empty()
120                && index
121                    .column_names()
122                    .iter()
123                    .all(|column| equality_inner_columns.contains(column.to_lowercase().as_str()))
124        });
125    best.map(|(_, strategy, inner, outer)| {
126        (
127            table_name,
128            strategy,
129            inner,
130            outer,
131            pk_unique || declared_unique,
132        )
133    })
134}
135
136fn indexable_source(expression: &Expression) -> Option<(String, Option<String>)> {
137    match expression {
138        Expression::TableSource(source) if source.as_of.is_none() => {
139            Some((source.name.value_lower.to_string(), None))
140        }
141        Expression::Aliased(aliased) => match aliased.expression.as_ref() {
142            Expression::TableSource(source) if source.as_of.is_none() => {
143                Some((source.name.value_lower.to_string(), None))
144            }
145            Expression::SubquerySource(source) => Some((
146                simple_passthrough_table(&source.subquery)?,
147                source.alias.as_ref().map(|alias| alias.value.to_string()),
148            )),
149            _ => None,
150        },
151        Expression::SubquerySource(source) => Some((
152            simple_passthrough_table(&source.subquery)?,
153            source.alias.as_ref().map(|alias| alias.value.to_string()),
154        )),
155        _ => None,
156    }
157}
158
159fn simple_join_key(condition: &Expression) -> Option<(String, String)> {
160    match condition {
161        Expression::Infix(infix) if infix.op_type == InfixOperator::Equal => Some((
162            qualified_column_name(&infix.left)?,
163            qualified_column_name(&infix.right)?,
164        )),
165        Expression::Infix(infix) if infix.op_type == InfixOperator::And => {
166            simple_join_key(&infix.left).or_else(|| simple_join_key(&infix.right))
167        }
168        _ => None,
169    }
170}
171
172fn qualified_column_name(expression: &Expression) -> Option<String> {
173    match expression {
174        Expression::QualifiedIdentifier(identifier) => Some(format!(
175            "{}.{}",
176            identifier.qualifier.value, identifier.name.value
177        )),
178        Expression::Identifier(identifier) => Some(identifier.value.to_string()),
179        _ => None,
180    }
181}
182
183fn simple_passthrough_table(statement: &SelectStatement) -> Option<String> {
184    if statement.with.is_some()
185        || !statement.set_operations.is_empty()
186        || !statement.group_by.columns.is_empty()
187        || statement.having.is_some()
188        || !statement.order_by.is_empty()
189        || statement.limit.is_some()
190        || statement.offset.is_some()
191        || statement.where_clause.is_some()
192        || statement.distinct
193        || !statement.window_defs.is_empty()
194    {
195        return None;
196    }
197    match statement.table_expr.as_deref()? {
198        Expression::TableSource(source) => Some(source.name.value_lower.to_string()),
199        Expression::Aliased(aliased) => match aliased.expression.as_ref() {
200            Expression::TableSource(source) => Some(source.name.value_lower.to_string()),
201            _ => None,
202        },
203        _ => None,
204    }
205}
206
207#[cfg(test)]
208mod tests {
209    use super::*;
210    use radixdb_sql::parse_sql;
211
212    #[test]
213    fn passthrough_source_rejects_semantic_modifiers() {
214        let mut statements = parse_sql("SELECT * FROM t WHERE id > 0").unwrap();
215        let radixdb_sql::ast::Statement::Select(statement) = statements.remove(0) else {
216            panic!("expected SELECT");
217        };
218        assert_eq!(simple_passthrough_table(&statement), None);
219    }
220}
radixdb_executor/access/index.rs

radixdb_executor/access/
index.rs
