gitql_engine/
engine_join.rs

1use std::collections::HashMap;
2
3use gitql_ast::statement::Join;
4use gitql_ast::statement::JoinKind;
5use gitql_ast::statement::JoinOperand;
6use gitql_ast::statement::TableSelection;
7use gitql_core::environment::Environment;
8use gitql_core::object::Row;
9use gitql_core::values::boolean::BoolValue;
10use gitql_core::values::null::NullValue;
11use gitql_core::values::Value;
12
13use crate::engine_evaluator::evaluate_expression;
14
15#[inline(always)]
16pub(crate) fn apply_join_operation(
17    env: &mut Environment,
18    all_rows: &mut Vec<Row>,
19    joins: &Vec<Join>,
20    tables_selections: &Vec<TableSelection>,
21    selected_rows_per_table: &mut HashMap<String, Vec<Row>>,
22    hidden_selection_per_table: &HashMap<String, usize>,
23    titles: &[String],
24) -> Result<(), String> {
25    // If no join, just merge them, can be optimized to append only the first value in the map
26    if joins.is_empty() {
27        for table_selection in tables_selections {
28            let table_rows = selected_rows_per_table
29                .get_mut(&table_selection.table_name)
30                .unwrap();
31            all_rows.append(table_rows);
32        }
33        return Ok(());
34    }
35
36    let mut current_tables_rows: Vec<Row> = vec![];
37    let mut all_rows_hidden_count = 0;
38
39    // Apply join operator depend on the join type
40    for join in joins {
41        let mut current_join_rows: Vec<Row> = vec![];
42
43        let left_rows: &Vec<Row>;
44        let left_hidden_count: usize;
45
46        let right_rows: &Vec<Row>;
47        let right_hidden_count: usize;
48
49        match &join.operand {
50            JoinOperand::OuterAndInner(outer, inner) => {
51                left_hidden_count = *hidden_selection_per_table.get(outer).unwrap_or(&0);
52                right_hidden_count = *hidden_selection_per_table.get(inner).unwrap_or(&0);
53                all_rows_hidden_count += left_hidden_count + right_hidden_count;
54
55                left_rows = selected_rows_per_table.get(outer).unwrap();
56                right_rows = selected_rows_per_table.get(inner).unwrap();
57            }
58
59            JoinOperand::Inner(inner) => {
60                left_hidden_count = all_rows_hidden_count;
61                right_hidden_count = *hidden_selection_per_table.get(inner).unwrap_or(&0);
62                all_rows_hidden_count += right_hidden_count;
63
64                left_rows = &current_tables_rows;
65                right_rows = selected_rows_per_table.get(inner).unwrap();
66            }
67        }
68
69        // Don't apply CROSS JOIN if left or right rows are empty
70        if join.kind == JoinKind::Cross && (left_rows.is_empty() || right_rows.is_empty()) {
71            continue;
72        }
73
74        // Perform nested loops straight forward join algorithm
75        for outer in left_rows {
76            for inner in right_rows {
77                let row_len = outer.values.len() + inner.values.len();
78                let mut joined_row: Vec<Box<dyn Value>> = Vec::with_capacity(row_len);
79                joined_row.append(&mut outer.values.clone());
80
81                let inner_rows = inner.values.clone();
82                let inner_hidden_values = &inner_rows[0..right_hidden_count];
83                joined_row.splice(
84                    left_hidden_count..left_hidden_count,
85                    inner_hidden_values.to_vec(),
86                );
87
88                let inner_other_values = &inner_rows[right_hidden_count..];
89                joined_row.extend_from_slice(inner_other_values);
90
91                // If join has predicate, insert the joined row only if the predicate value is true
92                if let Some(predicate) = &join.predicate {
93                    let predicate_value = evaluate_expression(env, predicate, titles, &joined_row)?;
94                    if let Some(bool_value) = predicate_value.as_any().downcast_ref::<BoolValue>() {
95                        if bool_value.value {
96                            current_join_rows.push(Row { values: joined_row });
97                            continue;
98                        }
99                    }
100
101                    // For LEFT and RIGHT Join only if the predicate is false we need to create new joined row
102                    // The new joined row will have nulls as LEFT table row values if the join type is `RIGHT OUTER` or
103                    // Nulls as RGIHT table row values if the join type is `LEFT OUTER`
104                    match join.kind {
105                        JoinKind::Left => {
106                            let mut left_joined_row: Vec<Box<dyn Value>> =
107                                Vec::with_capacity(row_len);
108                            // Push the LEFT values row
109                            left_joined_row.append(&mut outer.values.clone());
110                            // Push (N * NULL) values as RIGHT values row
111                            for _ in 0..inner.values.len() {
112                                left_joined_row.push(Box::new(NullValue));
113                            }
114                        }
115                        JoinKind::Right => {
116                            let mut right_joined_row: Vec<Box<dyn Value>> =
117                                Vec::with_capacity(row_len);
118                            // Push (N * NULL) values as LEFT values row
119                            for _ in 0..outer.values.len() {
120                                right_joined_row.push(Box::new(NullValue));
121                            }
122                            // Push the RIGHT values row
123                            right_joined_row.append(&mut inner.values.clone());
124                        }
125                        _ => {}
126                    }
127                    continue;
128                }
129
130                // If the condition has no predicate, just insert it
131                current_join_rows.push(Row { values: joined_row });
132            }
133        }
134
135        // Clear the previous join rows if exists
136        current_tables_rows.clear();
137        // Set the current tables rows as the result of the join
138        current_tables_rows.append(&mut current_join_rows);
139    }
140
141    // Push the result to the all_rows ref
142    all_rows.append(&mut current_tables_rows);
143
144    Ok(())
145}
gitql_engine/engine_join.rs

gitql_engine/
engine_join.rs
