vibesql_executor/select/join/mod.rs
1use std::{collections::HashMap, sync::Arc};
2
3use super::{cte::CteResult, from_iterator::FromIterator};
4use crate::{
5 errors::ExecutorError, evaluator::CombinedExpressionEvaluator, optimizer::combine_with_and,
6 schema::CombinedSchema, timeout::TimeoutContext,
7};
8
9mod bloom_filter;
10mod expression_mapper;
11mod hash_anti_join;
12pub(crate) mod hash_join;
13mod hash_join_iterator;
14mod hash_semi_join;
15mod join_analyzer;
16mod nested_loop;
17pub mod reorder;
18pub mod search;
19
20// Re-export Bloom filter for use in hash join implementations
21pub(crate) use bloom_filter::BloomFilter;
22
23#[cfg(test)]
24mod tests;
25
26// Re-export join reorder analyzer for public tests
27// Re-export hash_join functions for internal use
28use hash_anti_join::{hash_anti_join, hash_anti_join_with_filter};
29use hash_join::{
30 hash_join_inner, hash_join_inner_arithmetic, hash_join_inner_multi, hash_join_left_outer,
31 hash_join_left_outer_multi, hash_join_left_outer_with_filter,
32};
33// Re-export hash join iterator for public use
34pub use hash_join_iterator::HashJoinIterator;
35use hash_semi_join::{hash_semi_join, hash_semi_join_with_filter};
36// Re-export nested loop join variants for internal use
37use nested_loop::{
38 nested_loop_anti_join, nested_loop_cross_join, nested_loop_full_outer_join,
39 nested_loop_inner_join, nested_loop_left_outer_join, nested_loop_right_outer_join,
40 nested_loop_semi_join,
41};
42pub use reorder::JoinOrderAnalyzer;
43// Re-export join order search for public tests
44pub use search::JoinOrderSearch;
45
46/// Iterator over `FromData` rows without forcing full materialization
47///
48/// This enum wraps either a Vec iterator or a lazy `FromIterator`, allowing
49/// uniform iteration over rows regardless of how they were stored.
50///
51/// # Issue #4060
52///
53/// This type enables deferred row materialization for LIMIT queries:
54/// - `SELECT * FROM t LIMIT 10` only clones 10 rows, not all of `t`
55/// - Memory usage is O(LIMIT) instead of O(table_size)
56#[allow(dead_code)]
57pub(crate) enum FromDataIterator {
58 /// Iterator over a materialized Vec<Row>
59 Vec(std::vec::IntoIter<vibesql_storage::Row>),
60 /// Lazy iterator from FromIterator (table scan)
61 Lazy(FromIterator),
62}
63
64impl Iterator for FromDataIterator {
65 type Item = vibesql_storage::Row;
66
67 #[inline]
68 fn next(&mut self) -> Option<Self::Item> {
69 match self {
70 Self::Vec(iter) => iter.next(),
71 Self::Lazy(iter) => iter.next(),
72 }
73 }
74
75 #[inline]
76 fn size_hint(&self) -> (usize, Option<usize>) {
77 match self {
78 Self::Vec(iter) => iter.size_hint(),
79 Self::Lazy(iter) => iter.size_hint(),
80 }
81 }
82}
83
84/// Data source for FROM clause results
85///
86/// This enum allows FROM results to be either materialized (Vec<Row>) or lazy (iterator).
87/// Materialized results are used for JOINs, CTEs, and operations that need multiple passes.
88/// Lazy results are used for simple table scans to enable streaming execution.
89pub(crate) enum FromData {
90 /// Materialized rows (for JOINs, CTEs, operations needing multiple passes)
91 Materialized(Vec<vibesql_storage::Row>),
92
93 /// Shared rows (for zero-copy CTE references without filtering)
94 ///
95 /// This variant enables O(1) cloning when CTEs are referenced multiple times
96 /// without any filtering. Only materializes to Vec when mutation is needed.
97 SharedRows(Arc<Vec<vibesql_storage::Row>>),
98
99 /// Lazy iterator (for streaming table scans)
100 Iterator(FromIterator),
101}
102
103impl FromData {
104 /// Get rows, materializing if needed
105 ///
106 /// For SharedRows, this will clone only if the Arc is shared.
107 /// If the Arc has a single reference, the Vec is moved out efficiently.
108 pub fn into_rows(self) -> Vec<vibesql_storage::Row> {
109 match self {
110 Self::Materialized(rows) => rows,
111 Self::SharedRows(arc) => Arc::try_unwrap(arc).unwrap_or_else(|arc| (*arc).clone()),
112 Self::Iterator(iter) => iter.collect_vec(),
113 }
114 }
115
116 /// Returns an iterator over rows without forcing full materialization
117 ///
118 /// This is more efficient than `into_rows()` when you don't need all rows,
119 /// particularly for LIMIT queries where only a subset will be consumed.
120 ///
121 /// For Materialized and SharedRows variants, this returns an iterator over
122 /// the owned/cloned Vec. For Iterator variant, it returns the lazy iterator
123 /// directly without collecting.
124 ///
125 /// # Performance
126 ///
127 /// - `into_rows()`: O(n) allocation + cloning for all rows
128 /// - `into_iter()`: O(k) where k is the number of rows actually consumed
129 ///
130 /// Use `into_iter()` when:
131 /// - Processing with LIMIT (only need first N rows)
132 /// - Filtering results (may discard many rows)
133 /// - Streaming output without full materialization
134 #[allow(dead_code)]
135 pub fn into_iter(self) -> FromDataIterator {
136 match self {
137 Self::Materialized(rows) => FromDataIterator::Vec(rows.into_iter()),
138 Self::SharedRows(arc) => {
139 // Try to unwrap the Arc; if shared, clone the Vec
140 let rows = Arc::try_unwrap(arc).unwrap_or_else(|arc| (*arc).clone());
141 FromDataIterator::Vec(rows.into_iter())
142 }
143 Self::Iterator(iter) => FromDataIterator::Lazy(iter),
144 }
145 }
146
147 /// Get a reference to materialized rows, or materialize if iterator
148 ///
149 /// For SharedRows, returns a reference to the shared data without cloning.
150 pub fn as_rows(&mut self) -> &Vec<vibesql_storage::Row> {
151 // If we have an iterator, materialize it
152 if let Self::Iterator(iter) = self {
153 #[cfg(feature = "profile-q6")]
154 let materialize_start = std::time::Instant::now();
155
156 let rows = std::mem::replace(iter, FromIterator::from_vec(vec![])).collect_vec();
157 *self = Self::Materialized(rows);
158
159 #[cfg(feature = "profile-q6")]
160 {
161 let materialize_time = materialize_start.elapsed();
162 if let Self::Materialized(rows) = self {
163 eprintln!(
164 "[Q6 PROFILE] Row materialization (collect_vec): {:?} ({} rows, {:?}/row)",
165 materialize_time,
166 rows.len(),
167 materialize_time / rows.len() as u32
168 );
169 }
170 }
171 }
172
173 // Now we're guaranteed to have materialized or shared rows
174 match self {
175 Self::Materialized(ref rows) => rows,
176 Self::SharedRows(ref arc) => arc.as_ref(),
177 Self::Iterator(_) => unreachable!(),
178 }
179 }
180
181 /// Get a slice reference to the underlying rows without triggering materialization
182 ///
183 /// This is a zero-cost operation that directly accesses the underlying Vec<Row>
184 /// without calling collect_vec(). This avoids the 137ms row materialization
185 /// bottleneck in Q6 by skipping iteration entirely.
186 ///
187 /// Critical for columnar execution performance (#2521).
188 pub fn as_slice(&self) -> &[vibesql_storage::Row] {
189 match self {
190 Self::Materialized(rows) => rows.as_slice(),
191 Self::SharedRows(arc) => arc.as_slice(),
192 Self::Iterator(iter) => iter.as_slice(),
193 }
194 }
195}
196
197/// Result of executing a FROM clause
198///
199/// Contains the combined schema and data (either materialized or lazy).
200pub(crate) struct FromResult {
201 pub(crate) schema: CombinedSchema,
202 pub(crate) data: FromData,
203 /// If present, indicates that results are already sorted by the specified columns
204 /// in the given order (ASC/DESC). This allows skipping ORDER BY sorting.
205 pub(crate) sorted_by: Option<Vec<(String, vibesql_ast::OrderDirection)>>,
206 /// If true, indicates that WHERE clause filtering has already been fully applied
207 /// during the scan (e.g., by index scan with predicate pushdown). This allows
208 /// skipping redundant WHERE clause evaluation in the executor.
209 pub(crate) where_filtered: bool,
210}
211
212impl FromResult {
213 /// Create a FromResult from materialized rows
214 pub(super) fn from_rows(schema: CombinedSchema, rows: Vec<vibesql_storage::Row>) -> Self {
215 Self { schema, data: FromData::Materialized(rows), sorted_by: None, where_filtered: false }
216 }
217
218 /// Create a FromResult from shared rows (zero-copy for CTEs)
219 ///
220 /// This variant is used when CTE rows can be shared without cloning,
221 /// enabling O(1) memory usage for CTE references without filtering.
222 pub(super) fn from_shared_rows(
223 schema: CombinedSchema,
224 rows: Arc<Vec<vibesql_storage::Row>>,
225 ) -> Self {
226 Self { schema, data: FromData::SharedRows(rows), sorted_by: None, where_filtered: false }
227 }
228
229 /// Create a FromResult from materialized rows with sorting metadata
230 pub(super) fn from_rows_sorted(
231 schema: CombinedSchema,
232 rows: Vec<vibesql_storage::Row>,
233 sorted_by: Vec<(String, vibesql_ast::OrderDirection)>,
234 ) -> Self {
235 Self {
236 schema,
237 data: FromData::Materialized(rows),
238 sorted_by: Some(sorted_by),
239 where_filtered: false,
240 }
241 }
242
243 /// Create a FromResult from materialized rows with WHERE filtering already applied
244 pub(super) fn from_rows_where_filtered(
245 schema: CombinedSchema,
246 rows: Vec<vibesql_storage::Row>,
247 sorted_by: Option<Vec<(String, vibesql_ast::OrderDirection)>>,
248 ) -> Self {
249 Self { schema, data: FromData::Materialized(rows), sorted_by, where_filtered: true }
250 }
251
252 /// Create a FromResult from an iterator
253 pub(super) fn from_iterator(schema: CombinedSchema, iterator: FromIterator) -> Self {
254 Self { schema, data: FromData::Iterator(iterator), sorted_by: None, where_filtered: false }
255 }
256
257 /// Get the rows, materializing if needed
258 pub(super) fn into_rows(self) -> Vec<vibesql_storage::Row> {
259 self.data.into_rows()
260 }
261
262 /// Returns an iterator over rows without forcing full materialization
263 ///
264 /// This delegates to `FromData::into_iter()` and is more efficient than
265 /// `into_rows()` when only a subset of rows will be consumed.
266 ///
267 /// # Example Use Cases
268 ///
269 /// - LIMIT queries: `result.into_iter().take(10).collect()`
270 /// - Filtered iteration: `result.into_iter().filter(|r| ...).collect()`
271 /// - Early termination: Stop iterating when a condition is met
272 ///
273 /// # Issue #4060
274 #[allow(dead_code)]
275 pub(super) fn into_iter(self) -> FromDataIterator {
276 self.data.into_iter()
277 }
278
279 /// Take up to N rows without full materialization
280 ///
281 /// This is a convenience method equivalent to `self.into_iter().take(n).collect()`.
282 /// It's optimized for LIMIT queries where only a small subset of rows is needed.
283 ///
284 /// # Performance
285 ///
286 /// For a table with 10,000 rows and `take(10)`:
287 /// - `into_rows()` + truncate: clones all 10,000 rows, then discards 9,990
288 /// - `take(10)`: clones only 10 rows
289 ///
290 /// # Issue #4060
291 #[allow(dead_code)]
292 pub(super) fn take(self, n: usize) -> Vec<vibesql_storage::Row> {
293 self.into_iter().take(n).collect()
294 }
295
296 /// Get a mutable reference to the rows, materializing if needed
297 ///
298 /// For SharedRows, this triggers copy-on-write: the shared data is cloned
299 /// into owned Materialized data to allow mutation.
300 #[allow(dead_code)]
301 pub(super) fn rows_mut(&mut self) -> &mut Vec<vibesql_storage::Row> {
302 // Convert iterator or shared to materialized
303 match &mut self.data {
304 FromData::Iterator(iter) => {
305 let rows = std::mem::replace(iter, FromIterator::from_vec(vec![])).collect_vec();
306 self.data = FromData::Materialized(rows);
307 }
308 FromData::SharedRows(arc) => {
309 // Copy-on-write: clone the shared data to allow mutation
310 let rows = arc.as_ref().clone();
311 self.data = FromData::Materialized(rows);
312 }
313 FromData::Materialized(_) => {}
314 }
315
316 // Now we're guaranteed to have materialized rows
317 match &mut self.data {
318 FromData::Materialized(rows) => rows,
319 FromData::SharedRows(_) | FromData::Iterator(_) => unreachable!(),
320 }
321 }
322
323 /// Get a reference to rows, materializing if needed
324 pub(super) fn rows(&mut self) -> &Vec<vibesql_storage::Row> {
325 self.data.as_rows()
326 }
327
328 /// Get a slice reference to rows without triggering materialization
329 ///
330 /// This is a zero-cost operation that accesses the underlying data directly
331 /// without calling collect_vec(). This is critical for performance as it
332 /// avoids the row materialization bottleneck (up to 57% of query time).
333 ///
334 /// Unlike `rows()` which may trigger iterator collection, this method
335 /// provides direct access to the underlying Vec<Row> or iterator buffer.
336 pub(super) fn as_slice(&self) -> &[vibesql_storage::Row] {
337 self.data.as_slice()
338 }
339}
340
341/// Helper function to combine two rows without unnecessary cloning
342/// Only creates a single combined row, avoiding intermediate clones
343///
344/// Note: This preserves existing row_ids from both rows when present.
345/// For optimal ROWID tracking in JOINs, use combine_rows_with_schema.
346#[inline]
347fn combine_rows(
348 left_row: &vibesql_storage::Row,
349 right_row: &vibesql_storage::Row,
350) -> vibesql_storage::Row {
351 let mut combined_values = Vec::with_capacity(left_row.values.len() + right_row.values.len());
352 combined_values.extend_from_slice(&left_row.values);
353 combined_values.extend_from_slice(&right_row.values);
354
355 // Merge existing row_ids from both rows (issue #4370)
356 // This handles nested joins where intermediate results already have row_ids
357 let mut combined_row_ids = std::collections::HashMap::new();
358 let mut has_row_ids = false;
359
360 if let Some(ref row_ids) = left_row.row_ids {
361 combined_row_ids.extend(row_ids.iter().map(|(k, v)| (k.clone(), *v)));
362 has_row_ids = true;
363 }
364 if let Some(ref row_ids) = right_row.row_ids {
365 combined_row_ids.extend(row_ids.iter().map(|(k, v)| (k.clone(), *v)));
366 has_row_ids = true;
367 }
368
369 if has_row_ids {
370 vibesql_storage::Row::with_row_ids(combined_values, combined_row_ids)
371 } else {
372 vibesql_storage::Row::new(combined_values)
373 }
374}
375
376/// Apply a post-join filter expression to join result rows
377///
378/// This is used to filter rows produced by hash join with additional conditions
379/// from the WHERE clause that weren't used in the hash join itself.
380///
381/// Issue #3562: Added cte_results parameter so IN subqueries in filter expressions
382/// can resolve CTE references.
383///
384/// Issue #4994: Added outer_row and outer_schema parameters so correlated column
385/// references from outer queries can be resolved in JOIN conditions.
386fn apply_post_join_filter(
387 result: FromResult,
388 filter_expr: &vibesql_ast::Expression,
389 database: &vibesql_storage::Database,
390 cte_results: &HashMap<String, CteResult>,
391 outer_row: Option<&vibesql_storage::Row>,
392 outer_schema: Option<&crate::schema::CombinedSchema>,
393) -> Result<FromResult, ExecutorError> {
394 // Extract schema before moving result
395 let schema = result.schema.clone();
396 // Issue #3562: Use evaluator with CTE context if CTEs exist
397 // Issue #4994: Also pass outer context for correlated column references
398 let evaluator = match (cte_results.is_empty(), outer_row, outer_schema) {
399 (true, None, _) | (true, _, None) => {
400 CombinedExpressionEvaluator::with_database(&schema, database)
401 }
402 (false, None, _) | (false, _, None) => {
403 CombinedExpressionEvaluator::with_database_and_cte(&schema, database, cte_results)
404 }
405 (true, Some(outer_row), Some(outer_schema)) => {
406 CombinedExpressionEvaluator::with_database_and_outer_context(
407 &schema,
408 database,
409 outer_row,
410 outer_schema,
411 )
412 }
413 (false, Some(outer_row), Some(outer_schema)) => {
414 CombinedExpressionEvaluator::with_database_and_outer_context_and_cte(
415 &schema,
416 database,
417 outer_row,
418 outer_schema,
419 cte_results,
420 )
421 }
422 };
423
424 // Filter rows based on the expression
425 let mut filtered_rows = Vec::new();
426 for row in result.into_rows() {
427 match evaluator.eval(filter_expr, &row)? {
428 vibesql_types::SqlValue::Boolean(true) => filtered_rows.push(row),
429 vibesql_types::SqlValue::Boolean(false) => {} // Skip this row
430 vibesql_types::SqlValue::Null => {} // Skip NULL results
431 // SQLLogicTest compatibility: treat integers as truthy/falsy
432 vibesql_types::SqlValue::Integer(0) => {} // Skip 0
433 vibesql_types::SqlValue::Integer(_) => filtered_rows.push(row),
434 vibesql_types::SqlValue::Smallint(0) => {} // Skip 0
435 vibesql_types::SqlValue::Smallint(_) => filtered_rows.push(row),
436 vibesql_types::SqlValue::Bigint(0) => {} // Skip 0
437 vibesql_types::SqlValue::Bigint(_) => filtered_rows.push(row),
438 vibesql_types::SqlValue::Float(0.0) => {} // Skip 0.0
439 vibesql_types::SqlValue::Float(_) => filtered_rows.push(row),
440 vibesql_types::SqlValue::Real(0.0) => {} // Skip 0.0
441 vibesql_types::SqlValue::Real(_) => filtered_rows.push(row),
442 vibesql_types::SqlValue::Double(0.0) => {} // Skip 0.0
443 vibesql_types::SqlValue::Double(_) => filtered_rows.push(row),
444 other => {
445 return Err(ExecutorError::InvalidWhereClause(format!(
446 "Filter expression must evaluate to boolean, got: {:?}",
447 other
448 )))
449 }
450 }
451 }
452
453 Ok(FromResult::from_rows(schema, filtered_rows))
454}
455
456/// Perform join between two FROM results, optimizing with hash join when possible
457///
458/// This function now supports predicate pushdown from WHERE clauses. Additional equijoin
459/// predicates from WHERE can be passed to optimize hash join selection and execution.
460///
461/// Note: This function combines rows from left and right according to the join type
462/// and join condition. For queries with many tables and large intermediate results,
463/// consider applying WHERE filters earlier to reduce memory usage.
464///
465/// Issue #3562: Added cte_results parameter so post-join filters with IN subqueries
466/// can resolve CTE references.
467///
468/// Issue #4994: Added outer_row and outer_schema parameters so JOIN conditions
469/// that reference columns from outer queries (correlated derived tables) can
470/// be properly evaluated.
471#[allow(clippy::too_many_arguments)]
472pub(super) fn nested_loop_join(
473 left: FromResult,
474 right: FromResult,
475 join_type: &vibesql_ast::JoinType,
476 condition: &Option<vibesql_ast::Expression>,
477 natural: bool,
478 using_columns: Option<&[String]>,
479 database: &vibesql_storage::Database,
480 additional_equijoins: &[vibesql_ast::Expression],
481 timeout_ctx: &TimeoutContext,
482 cte_results: &HashMap<String, CteResult>,
483 outer_row: Option<&vibesql_storage::Row>,
484 outer_schema: Option<&crate::schema::CombinedSchema>,
485) -> Result<FromResult, ExecutorError> {
486 // Try to use hash join for INNER JOINs with simple equi-join conditions
487 if let vibesql_ast::JoinType::Inner = join_type {
488 // Get column count and right table info once for analysis
489 // IMPORTANT: Sum up columns from ALL tables in the left schema,
490 // not just the first table, to handle accumulated multi-table joins
491 let left_col_count = left.schema.total_columns;
492
493 // Use merge to preserve all tables from nested joins for column resolution
494 let temp_schema = CombinedSchema::merge(left.schema.clone(), right.schema.clone());
495
496 // Phase 3.1: Try ON condition first (preferred for hash join)
497 // Now supports multi-column composite keys for better performance
498 if let Some(cond) = condition {
499 // First try multi-column hash join for composite keys (2+ equi-join conditions)
500 if let Some(multi_result) =
501 join_analyzer::analyze_multi_column_equi_join(cond, &temp_schema, left_col_count)
502 {
503 // Use multi-column hash join if there are 2+ join columns
504 if multi_result.equi_joins.left_col_indices.len() >= 2 {
505 // Save schemas for NATURAL JOIN processing before moving left/right
506 let (left_schema_for_dedup, right_schema_for_dedup) =
507 if natural || using_columns.is_some() {
508 (Some(left.schema.clone()), Some(right.schema.clone()))
509 } else {
510 (None, None)
511 };
512
513 let mut result = hash_join_inner_multi(
514 left,
515 right,
516 &multi_result.equi_joins.left_col_indices,
517 &multi_result.equi_joins.right_col_indices,
518 )?;
519
520 // Apply remaining conditions as post-join filter
521 if !multi_result.remaining_conditions.is_empty() {
522 if let Some(filter_expr) =
523 combine_with_and(multi_result.remaining_conditions)
524 {
525 result = apply_post_join_filter(
526 result,
527 &filter_expr,
528 database,
529 cte_results,
530 outer_row,
531 outer_schema,
532 )?;
533 }
534 }
535
536 // For NATURAL JOIN or USING clause, remove duplicate columns from the result
537 if natural {
538 if let (Some(ref left_schema), Some(ref right_schema_orig)) =
539 (left_schema_for_dedup, right_schema_for_dedup)
540 {
541 // Use the original right schema directly to handle nested joins
542 // with multiple tables (e.g., t1 NATURAL JOIN (t2 JOIN t3))
543 result = remove_duplicate_columns_for_natural_join(
544 result,
545 left_schema,
546 right_schema_orig,
547 join_type,
548 )?;
549 }
550 } else if let Some(using_cols) = using_columns {
551 if let (Some(ref left_schema), Some(ref right_schema_orig)) =
552 (left_schema_for_dedup, right_schema_for_dedup)
553 {
554 result = remove_duplicate_columns_for_using_join(
555 result,
556 left_schema,
557 right_schema_orig,
558 using_cols,
559 join_type,
560 )?;
561 }
562 }
563
564 return Ok(result);
565 }
566
567 // Single-column equi-join: use standard hash join (more efficient for single key)
568 // Save schemas for NATURAL JOIN processing before moving left/right
569 let (left_schema_for_dedup, right_schema_for_dedup) =
570 if natural || using_columns.is_some() {
571 (Some(left.schema.clone()), Some(right.schema.clone()))
572 } else {
573 (None, None)
574 };
575
576 let mut result = hash_join_inner(
577 left,
578 right,
579 multi_result.equi_joins.left_col_indices[0],
580 multi_result.equi_joins.right_col_indices[0],
581 )?;
582
583 // Apply remaining conditions as post-join filter
584 if !multi_result.remaining_conditions.is_empty() {
585 if let Some(filter_expr) = combine_with_and(multi_result.remaining_conditions) {
586 result = apply_post_join_filter(
587 result,
588 &filter_expr,
589 database,
590 cte_results,
591 outer_row,
592 outer_schema,
593 )?;
594 }
595 }
596
597 // For NATURAL JOIN or USING clause, remove duplicate columns from the result
598 if natural {
599 if let (Some(ref left_schema), Some(ref right_schema_orig)) =
600 (left_schema_for_dedup, right_schema_for_dedup)
601 {
602 // Use the original right schema directly to handle nested joins
603 // with multiple tables (e.g., t1 NATURAL JOIN (t2 JOIN t3))
604 result = remove_duplicate_columns_for_natural_join(
605 result,
606 left_schema,
607 right_schema_orig,
608 join_type,
609 )?;
610 }
611 } else if let Some(using_cols) = using_columns {
612 if let (Some(ref left_schema), Some(ref right_schema_orig)) =
613 (left_schema_for_dedup, right_schema_for_dedup)
614 {
615 result = remove_duplicate_columns_for_using_join(
616 result,
617 left_schema,
618 right_schema_orig,
619 using_cols,
620 join_type,
621 )?;
622 }
623 }
624
625 return Ok(result);
626 }
627 }
628
629 // Phase 3.2: Try OR conditions with common equi-join (TPC-H Q19 optimization)
630 // For expressions like `(a.x = b.x AND ...) OR (a.x = b.x AND ...) OR (a.x = b.x AND ...)`,
631 // extract the common equi-join `a.x = b.x` for hash join
632 if let Some(cond) = condition {
633 if let Some(or_result) =
634 join_analyzer::analyze_or_equi_join(cond, &temp_schema, left_col_count)
635 {
636 // Save schemas for NATURAL JOIN processing before moving left/right
637 let (left_schema_for_dedup, right_schema_for_dedup) =
638 if natural || using_columns.is_some() {
639 (Some(left.schema.clone()), Some(right.schema.clone()))
640 } else {
641 (None, None)
642 };
643
644 let mut result = hash_join_inner(
645 left,
646 right,
647 or_result.equi_join.left_col_idx,
648 or_result.equi_join.right_col_idx,
649 )?;
650
651 // Apply remaining OR conditions as post-join filter
652 if !or_result.remaining_conditions.is_empty() {
653 if let Some(filter_expr) = combine_with_and(or_result.remaining_conditions) {
654 result = apply_post_join_filter(
655 result,
656 &filter_expr,
657 database,
658 cte_results,
659 outer_row,
660 outer_schema,
661 )?;
662 }
663 }
664
665 // For NATURAL JOIN or USING clause, remove duplicate columns from the result
666 if natural {
667 if let (Some(ref left_schema), Some(ref right_schema_orig)) =
668 (left_schema_for_dedup, right_schema_for_dedup)
669 {
670 // Use the original right schema directly to handle nested joins
671 // with multiple tables (e.g., t1 NATURAL JOIN (t2 JOIN t3))
672 result = remove_duplicate_columns_for_natural_join(
673 result,
674 left_schema,
675 right_schema_orig,
676 join_type,
677 )?;
678 }
679 } else if let Some(using_cols) = using_columns {
680 if let (Some(ref left_schema), Some(ref right_schema_orig)) =
681 (left_schema_for_dedup, right_schema_for_dedup)
682 {
683 result = remove_duplicate_columns_for_using_join(
684 result,
685 left_schema,
686 right_schema_orig,
687 using_cols,
688 join_type,
689 )?;
690 }
691 }
692
693 return Ok(result);
694 }
695 }
696
697 // Phase 3.3: Try arithmetic equi-join (TPC-DS Q2 optimization)
698 // For expressions like `col1 = col2 - 53`, extract the arithmetic offset for hash join
699 if let Some(cond) = condition {
700 if let Some(arith_info) =
701 join_analyzer::analyze_arithmetic_equi_join(cond, &temp_schema, left_col_count)
702 {
703 // Save schemas for NATURAL JOIN processing before moving left/right
704 let (left_schema_for_dedup, right_schema_for_dedup) =
705 if natural || using_columns.is_some() {
706 (Some(left.schema.clone()), Some(right.schema.clone()))
707 } else {
708 (None, None)
709 };
710
711 let mut result = hash_join_inner_arithmetic(
712 left,
713 right,
714 arith_info.left_col_idx,
715 arith_info.right_col_idx,
716 arith_info.offset,
717 )?;
718
719 // For NATURAL JOIN or USING clause, remove duplicate columns from the result
720 if natural {
721 if let (Some(ref left_schema), Some(ref right_schema_orig)) =
722 (left_schema_for_dedup, right_schema_for_dedup)
723 {
724 // Use the original right schema directly to handle nested joins
725 // with multiple tables (e.g., t1 NATURAL JOIN (t2 JOIN t3))
726 result = remove_duplicate_columns_for_natural_join(
727 result,
728 left_schema,
729 right_schema_orig,
730 join_type,
731 )?;
732 }
733 } else if let Some(using_cols) = using_columns {
734 if let (Some(ref left_schema), Some(ref right_schema_orig)) =
735 (left_schema_for_dedup, right_schema_for_dedup)
736 {
737 result = remove_duplicate_columns_for_using_join(
738 result,
739 left_schema,
740 right_schema_orig,
741 using_cols,
742 join_type,
743 )?;
744 }
745 }
746
747 return Ok(result);
748 }
749 }
750
751 // Phase 3.4: Try multi-column hash join from WHERE clause conditions
752 // When there are multiple equijoin conditions (e.g., ps_suppkey = l_suppkey AND ps_partkey
753 // = l_partkey), using composite key hash join is critical for performance.
754 // Single-key hash join with post-filter can cause catastrophic performance issues
755 // (48B cartesian products in Q9 at SF=0.1).
756 if additional_equijoins.len() >= 2 {
757 // Collect all valid equi-join conditions
758 let mut left_col_indices = Vec::new();
759 let mut right_col_indices = Vec::new();
760 let mut used_indices = Vec::new();
761
762 for (idx, equijoin) in additional_equijoins.iter().enumerate() {
763 if let Some(equi_join_info) =
764 join_analyzer::analyze_equi_join(equijoin, &temp_schema, left_col_count)
765 {
766 left_col_indices.push(equi_join_info.left_col_idx);
767 right_col_indices.push(equi_join_info.right_col_idx);
768 used_indices.push(idx);
769 }
770 }
771
772 // If we found 2+ equi-join conditions, use multi-column hash join
773 if left_col_indices.len() >= 2 {
774 // Save schemas for NATURAL JOIN processing before moving left/right
775 let (left_schema_for_dedup, right_schema_for_dedup) =
776 if natural || using_columns.is_some() {
777 (Some(left.schema.clone()), Some(right.schema.clone()))
778 } else {
779 (None, None)
780 };
781
782 let mut result =
783 hash_join_inner_multi(left, right, &left_col_indices, &right_col_indices)?;
784
785 // Apply remaining conditions (non-equijoins) as post-join filters
786 let remaining_conditions: Vec<_> = additional_equijoins
787 .iter()
788 .enumerate()
789 .filter(|(i, _)| !used_indices.contains(i))
790 .map(|(_, e)| e.clone())
791 .collect();
792
793 if !remaining_conditions.is_empty() {
794 if let Some(filter_expr) = combine_with_and(remaining_conditions) {
795 result = apply_post_join_filter(
796 result,
797 &filter_expr,
798 database,
799 cte_results,
800 outer_row,
801 outer_schema,
802 )?;
803 }
804 }
805
806 // For NATURAL JOIN or USING clause, remove duplicate columns from the result
807 if natural {
808 if let (Some(ref left_schema), Some(ref right_schema_orig)) =
809 (left_schema_for_dedup, right_schema_for_dedup)
810 {
811 // Use the original right schema directly to handle nested joins
812 // with multiple tables (e.g., t1 NATURAL JOIN (t2 JOIN t3))
813 result = remove_duplicate_columns_for_natural_join(
814 result,
815 left_schema,
816 right_schema_orig,
817 join_type,
818 )?;
819 }
820 } else if let Some(using_cols) = using_columns {
821 if let (Some(ref left_schema), Some(ref right_schema_orig)) =
822 (left_schema_for_dedup, right_schema_for_dedup)
823 {
824 result = remove_duplicate_columns_for_using_join(
825 result,
826 left_schema,
827 right_schema_orig,
828 using_cols,
829 join_type,
830 )?;
831 }
832 }
833
834 return Ok(result);
835 }
836 }
837
838 // Phase 3.5: If no multi-column hash join, try single-column WHERE clause equijoins
839 // Iterate through all additional equijoins to find one suitable for hash join
840 for (idx, equijoin) in additional_equijoins.iter().enumerate() {
841 if let Some(equi_join_info) =
842 join_analyzer::analyze_equi_join(equijoin, &temp_schema, left_col_count)
843 {
844 // Save schemas for NATURAL JOIN processing before moving left/right
845 let (left_schema_for_dedup, right_schema_for_dedup) =
846 if natural || using_columns.is_some() {
847 (Some(left.schema.clone()), Some(right.schema.clone()))
848 } else {
849 (None, None)
850 };
851
852 // Found a WHERE clause equijoin suitable for hash join!
853 let mut result = hash_join_inner(
854 left,
855 right,
856 equi_join_info.left_col_idx,
857 equi_join_info.right_col_idx,
858 )?;
859
860 // Apply remaining equijoins and conditions as post-join filters
861 let remaining_conditions: Vec<_> = additional_equijoins
862 .iter()
863 .enumerate()
864 .filter(|(i, _)| *i != idx)
865 .map(|(_, e)| e.clone())
866 .collect();
867
868 if !remaining_conditions.is_empty() {
869 if let Some(filter_expr) = combine_with_and(remaining_conditions) {
870 result = apply_post_join_filter(
871 result,
872 &filter_expr,
873 database,
874 cte_results,
875 outer_row,
876 outer_schema,
877 )?;
878 }
879 }
880
881 // For NATURAL JOIN or USING clause, remove duplicate columns from the result
882 if natural {
883 if let (Some(ref left_schema), Some(ref right_schema_orig)) =
884 (left_schema_for_dedup, right_schema_for_dedup)
885 {
886 // Use the original right schema directly to handle nested joins
887 // with multiple tables (e.g., t1 NATURAL JOIN (t2 JOIN t3))
888 result = remove_duplicate_columns_for_natural_join(
889 result,
890 left_schema,
891 right_schema_orig,
892 join_type,
893 )?;
894 }
895 } else if let Some(using_cols) = using_columns {
896 if let (Some(ref left_schema), Some(ref right_schema_orig)) =
897 (left_schema_for_dedup, right_schema_for_dedup)
898 {
899 result = remove_duplicate_columns_for_using_join(
900 result,
901 left_schema,
902 right_schema_orig,
903 using_cols,
904 join_type,
905 )?;
906 }
907 }
908
909 return Ok(result);
910 }
911 }
912
913 // Phase 3.6: Try arithmetic equijoins from WHERE clause for hash join
914 // For expressions like `col1 = col2 - 53` in WHERE clause with Inner joins
915 // This enables hash join for derived table joins with arithmetic conditions (TPC-DS Q2)
916 for (idx, equijoin) in additional_equijoins.iter().enumerate() {
917 if let Some(arith_info) =
918 join_analyzer::analyze_arithmetic_equi_join(equijoin, &temp_schema, left_col_count)
919 {
920 // Save schemas for NATURAL JOIN processing before moving left/right
921 let (left_schema_for_dedup, right_schema_for_dedup) =
922 if natural || using_columns.is_some() {
923 (Some(left.schema.clone()), Some(right.schema.clone()))
924 } else {
925 (None, None)
926 };
927
928 // Found an arithmetic equijoin suitable for hash join!
929 let mut result = hash_join_inner_arithmetic(
930 left,
931 right,
932 arith_info.left_col_idx,
933 arith_info.right_col_idx,
934 arith_info.offset,
935 )?;
936
937 // Apply remaining equijoins as post-join filters
938 let remaining_conditions: Vec<_> = additional_equijoins
939 .iter()
940 .enumerate()
941 .filter(|(i, _)| *i != idx)
942 .map(|(_, e)| e.clone())
943 .collect();
944
945 if !remaining_conditions.is_empty() {
946 if let Some(filter_expr) = combine_with_and(remaining_conditions) {
947 result = apply_post_join_filter(
948 result,
949 &filter_expr,
950 database,
951 cte_results,
952 outer_row,
953 outer_schema,
954 )?;
955 }
956 }
957
958 // For NATURAL JOIN or USING clause, remove duplicate columns from the result
959 if natural {
960 if let (Some(ref left_schema), Some(ref right_schema_orig)) =
961 (left_schema_for_dedup, right_schema_for_dedup)
962 {
963 // Use the original right schema directly to handle nested joins
964 // with multiple tables (e.g., t1 NATURAL JOIN (t2 JOIN t3))
965 result = remove_duplicate_columns_for_natural_join(
966 result,
967 left_schema,
968 right_schema_orig,
969 join_type,
970 )?;
971 }
972 } else if let Some(using_cols) = using_columns {
973 if let (Some(ref left_schema), Some(ref right_schema_orig)) =
974 (left_schema_for_dedup, right_schema_for_dedup)
975 {
976 result = remove_duplicate_columns_for_using_join(
977 result,
978 left_schema,
979 right_schema_orig,
980 using_cols,
981 join_type,
982 )?;
983 }
984 }
985
986 return Ok(result);
987 }
988 }
989 }
990
991 // Try to use hash join for LEFT OUTER JOINs with equi-join conditions
992 // This optimization is critical for Q13 (customer LEFT JOIN orders)
993 if let vibesql_ast::JoinType::LeftOuter = join_type {
994 // Get column count and right table info for analysis
995 let left_col_count = left.schema.total_columns;
996
997 // Use merge to preserve all tables from nested joins for column resolution
998 let temp_schema = CombinedSchema::merge(left.schema.clone(), right.schema.clone());
999
1000 // Try ON condition for hash join with multi-column support
1001 // Use multi-column analysis to include ALL equi-join conditions in the hash join
1002 // This is critical for LEFT JOIN correctness: post-filter conditions on NULL columns
1003 // (from unmatched rows) incorrectly filter out valid LEFT JOIN results
1004 if let Some(cond) = condition {
1005 if let Some(multi_result) =
1006 join_analyzer::analyze_multi_column_equi_join(cond, &temp_schema, left_col_count)
1007 {
1008 // Save schemas for NATURAL JOIN processing before moving left/right
1009 let (left_schema_for_dedup, right_schema_for_dedup) =
1010 if natural || using_columns.is_some() {
1011 (Some(left.schema.clone()), Some(right.schema.clone()))
1012 } else {
1013 (None, None)
1014 };
1015
1016 // Build the remaining filter expression (if any)
1017 let remaining_filter = combine_with_and(multi_result.remaining_conditions);
1018
1019 // Use multi-column hash join when there are multiple equi-join columns
1020 // For remaining conditions, use hash_join_left_outer_with_filter which
1021 // applies the filter DURING the join (not as post-filter) to preserve
1022 // LEFT JOIN semantics: rows that match equi-join but fail filter get NULLs
1023 let mut result = if multi_result.equi_joins.left_col_indices.len() > 1 {
1024 // Multi-column equi-join (remaining conditions not yet supported)
1025 // TODO: Add hash_join_left_outer_multi_with_filter
1026 let mut r = hash_join_left_outer_multi(
1027 left,
1028 right,
1029 &multi_result.equi_joins.left_col_indices,
1030 &multi_result.equi_joins.right_col_indices,
1031 )?;
1032 // For now, apply as post-filter (known issue for multi-column)
1033 if let Some(ref filter_expr) = remaining_filter {
1034 r = apply_post_join_filter(
1035 r,
1036 filter_expr,
1037 database,
1038 cte_results,
1039 outer_row,
1040 outer_schema,
1041 )?;
1042 }
1043 r
1044 } else if let Some(ref filter_expr) = remaining_filter {
1045 // Single column with additional filter - use LEFT JOIN-aware filter
1046 // This applies the filter DURING the join to preserve unmatched rows
1047 hash_join_left_outer_with_filter(
1048 left,
1049 right,
1050 multi_result.equi_joins.left_col_indices[0],
1051 multi_result.equi_joins.right_col_indices[0],
1052 filter_expr,
1053 &temp_schema,
1054 database,
1055 )?
1056 } else {
1057 // Single column without additional filter
1058 hash_join_left_outer(
1059 left,
1060 right,
1061 multi_result.equi_joins.left_col_indices[0],
1062 multi_result.equi_joins.right_col_indices[0],
1063 )?
1064 };
1065
1066 // For NATURAL JOIN or USING clause, remove duplicate columns from the result
1067 if natural {
1068 if let (Some(ref left_schema), Some(ref right_schema_orig)) =
1069 (left_schema_for_dedup, right_schema_for_dedup)
1070 {
1071 // Use the original right schema directly to handle nested joins
1072 // with multiple tables (e.g., t1 NATURAL JOIN (t2 JOIN t3))
1073 result = remove_duplicate_columns_for_natural_join(
1074 result,
1075 left_schema,
1076 right_schema_orig,
1077 join_type,
1078 )?;
1079 }
1080 } else if let Some(using_cols) = using_columns {
1081 if let (Some(ref left_schema), Some(ref right_schema_orig)) =
1082 (left_schema_for_dedup, right_schema_for_dedup)
1083 {
1084 result = remove_duplicate_columns_for_using_join(
1085 result,
1086 left_schema,
1087 right_schema_orig,
1088 using_cols,
1089 join_type,
1090 )?;
1091 }
1092 }
1093
1094 return Ok(result);
1095 }
1096 }
1097 }
1098
1099 // Try to use hash join for SEMI/ANTI JOINs with equi-join conditions
1100 if matches!(join_type, vibesql_ast::JoinType::Semi | vibesql_ast::JoinType::Anti) {
1101 // Get column count for analysis
1102 let left_col_count = left.schema.total_columns;
1103
1104 // Use merge to preserve all tables from nested joins for column resolution
1105 let temp_schema = CombinedSchema::merge(left.schema.clone(), right.schema.clone());
1106
1107 // Try ON condition first - use analyze_compound_equi_join to handle complex conditions
1108 // This enables hash join optimization for EXISTS subqueries with additional predicates
1109 // Example: EXISTS (SELECT * FROM t WHERE t.x = outer.x AND t.y <> outer.y)
1110 // The equi-join (t.x = outer.x) is used for hash join, and the inequality is a post-filter
1111 if let Some(cond) = condition {
1112 if let Some(compound_result) =
1113 join_analyzer::analyze_compound_equi_join(cond, &temp_schema, left_col_count)
1114 {
1115 // Build the combined remaining condition (if any)
1116 let remaining_filter = combine_with_and(compound_result.remaining_conditions);
1117
1118 let result = if matches!(join_type, vibesql_ast::JoinType::Semi) {
1119 hash_semi_join_with_filter(
1120 left,
1121 right,
1122 compound_result.equi_join.left_col_idx,
1123 compound_result.equi_join.right_col_idx,
1124 remaining_filter.as_ref(),
1125 &temp_schema,
1126 database,
1127 )?
1128 } else {
1129 hash_anti_join_with_filter(
1130 left,
1131 right,
1132 compound_result.equi_join.left_col_idx,
1133 compound_result.equi_join.right_col_idx,
1134 remaining_filter.as_ref(),
1135 &temp_schema,
1136 database,
1137 )?
1138 };
1139
1140 return Ok(result);
1141 }
1142 }
1143
1144 // Try WHERE clause equijoins
1145 for equijoin in additional_equijoins.iter() {
1146 if let Some(equi_join_info) =
1147 join_analyzer::analyze_equi_join(equijoin, &temp_schema, left_col_count)
1148 {
1149 let result = if matches!(join_type, vibesql_ast::JoinType::Semi) {
1150 hash_semi_join(
1151 left,
1152 right,
1153 equi_join_info.left_col_idx,
1154 equi_join_info.right_col_idx,
1155 )?
1156 } else {
1157 hash_anti_join(
1158 left,
1159 right,
1160 equi_join_info.left_col_idx,
1161 equi_join_info.right_col_idx,
1162 )?
1163 };
1164
1165 return Ok(result);
1166 }
1167 }
1168 }
1169
1170 // Try to use hash join for CROSS JOINs when equijoin conditions exist in WHERE clause
1171 // This is critical for Q21 and other TPC-H queries with implicit (comma-separated) joins
1172 // CROSS JOIN with equijoin predicates should be executed as hash INNER JOIN
1173 if let vibesql_ast::JoinType::Cross = join_type {
1174 if !additional_equijoins.is_empty() {
1175 // Get column count and right table info for analysis
1176 let left_col_count = left.schema.total_columns;
1177
1178 // Use merge to preserve all tables from nested joins for column resolution
1179 let temp_schema = CombinedSchema::merge(left.schema.clone(), right.schema.clone());
1180
1181 // Try WHERE clause equijoins for hash join
1182 for (idx, equijoin) in additional_equijoins.iter().enumerate() {
1183 if let Some(equi_join_info) =
1184 join_analyzer::analyze_equi_join(equijoin, &temp_schema, left_col_count)
1185 {
1186 // Found a WHERE clause equijoin suitable for hash join!
1187 // Execute CROSS JOIN as hash INNER JOIN with the equijoin condition
1188 let mut result = hash_join_inner(
1189 left,
1190 right,
1191 equi_join_info.left_col_idx,
1192 equi_join_info.right_col_idx,
1193 )?;
1194
1195 // Apply remaining equijoins as post-join filters
1196 let remaining_conditions: Vec<_> = additional_equijoins
1197 .iter()
1198 .enumerate()
1199 .filter(|(i, _)| *i != idx)
1200 .map(|(_, e)| e.clone())
1201 .collect();
1202
1203 if !remaining_conditions.is_empty() {
1204 if let Some(filter_expr) = combine_with_and(remaining_conditions) {
1205 result = apply_post_join_filter(
1206 result,
1207 &filter_expr,
1208 database,
1209 cte_results,
1210 outer_row,
1211 outer_schema,
1212 )?;
1213 }
1214 }
1215
1216 return Ok(result);
1217 }
1218 }
1219
1220 // Try arithmetic equijoins for hash join (TPC-DS Q2 optimization)
1221 // For expressions like `col1 = col2 - 53` in WHERE clause
1222 for (idx, equijoin) in additional_equijoins.iter().enumerate() {
1223 if let Some(arith_info) = join_analyzer::analyze_arithmetic_equi_join(
1224 equijoin,
1225 &temp_schema,
1226 left_col_count,
1227 ) {
1228 // Found an arithmetic equijoin suitable for hash join!
1229 let mut result = hash_join_inner_arithmetic(
1230 left,
1231 right,
1232 arith_info.left_col_idx,
1233 arith_info.right_col_idx,
1234 arith_info.offset,
1235 )?;
1236
1237 // Apply remaining equijoins as post-join filters
1238 let remaining_conditions: Vec<_> = additional_equijoins
1239 .iter()
1240 .enumerate()
1241 .filter(|(i, _)| *i != idx)
1242 .map(|(_, e)| e.clone())
1243 .collect();
1244
1245 if !remaining_conditions.is_empty() {
1246 if let Some(filter_expr) = combine_with_and(remaining_conditions) {
1247 result = apply_post_join_filter(
1248 result,
1249 &filter_expr,
1250 database,
1251 cte_results,
1252 outer_row,
1253 outer_schema,
1254 )?;
1255 }
1256 }
1257
1258 return Ok(result);
1259 }
1260 }
1261 }
1262 }
1263
1264 // Prepare combined join condition including additional equijoins from WHERE clause
1265 let mut all_join_conditions = Vec::new();
1266 if let Some(cond) = condition {
1267 all_join_conditions.push(cond.clone());
1268 }
1269 all_join_conditions.extend_from_slice(additional_equijoins);
1270
1271 // Combine all join conditions with AND
1272 let combined_condition = combine_with_and(all_join_conditions);
1273
1274 // Fall back to nested loop join for all other cases
1275 // For NATURAL JOIN, we need to preserve the original schemas for duplicate removal
1276 let (left_schema_for_dedup, right_schema_for_dedup) = if natural || using_columns.is_some() {
1277 (Some(left.schema.clone()), Some(right.schema.clone()))
1278 } else {
1279 (None, None)
1280 };
1281
1282 // Issue #4994: Pass outer context to nested loop joins for correlated column resolution
1283 let mut result = match join_type {
1284 vibesql_ast::JoinType::Inner => nested_loop_inner_join(
1285 left,
1286 right,
1287 &combined_condition,
1288 database,
1289 timeout_ctx,
1290 outer_row,
1291 outer_schema,
1292 ),
1293 vibesql_ast::JoinType::LeftOuter => nested_loop_left_outer_join(
1294 left,
1295 right,
1296 &combined_condition,
1297 database,
1298 timeout_ctx,
1299 outer_row,
1300 outer_schema,
1301 ),
1302 vibesql_ast::JoinType::RightOuter => nested_loop_right_outer_join(
1303 left,
1304 right,
1305 &combined_condition,
1306 database,
1307 timeout_ctx,
1308 outer_row,
1309 outer_schema,
1310 ),
1311 vibesql_ast::JoinType::FullOuter => nested_loop_full_outer_join(
1312 left,
1313 right,
1314 &combined_condition,
1315 database,
1316 timeout_ctx,
1317 outer_row,
1318 outer_schema,
1319 ),
1320 vibesql_ast::JoinType::Cross => {
1321 // CROSS JOIN with any condition (from USING clause, NATURAL, or explicit ON)
1322 // should be executed as INNER JOIN - the condition filters the Cartesian product.
1323 // Note: `using_columns` may be None here if USING deduplication is handled
1324 // post-process by the caller (join_scan.rs), but `combined_condition` will
1325 // contain the generated USING equality conditions.
1326 if combined_condition.is_some() {
1327 nested_loop_inner_join(
1328 left,
1329 right,
1330 &combined_condition,
1331 database,
1332 timeout_ctx,
1333 outer_row,
1334 outer_schema,
1335 )
1336 } else {
1337 nested_loop_cross_join(
1338 left,
1339 right,
1340 &combined_condition,
1341 database,
1342 timeout_ctx,
1343 outer_row,
1344 outer_schema,
1345 )
1346 }
1347 }
1348 vibesql_ast::JoinType::Semi => nested_loop_semi_join(
1349 left,
1350 right,
1351 &combined_condition,
1352 database,
1353 timeout_ctx,
1354 outer_row,
1355 outer_schema,
1356 ),
1357 vibesql_ast::JoinType::Anti => nested_loop_anti_join(
1358 left,
1359 right,
1360 &combined_condition,
1361 database,
1362 timeout_ctx,
1363 outer_row,
1364 outer_schema,
1365 ),
1366 }?;
1367
1368 // For NATURAL JOIN or USING clause, remove duplicate columns from the result
1369 // For RIGHT/FULL OUTER JOINs, the updated remove_duplicate_columns_for_natural_join
1370 // now handles hiding the correct side and adding coalesce pairs (issue #4781, #4802)
1371 if natural {
1372 if let (Some(ref left_schema), Some(ref right_schema)) =
1373 (&left_schema_for_dedup, &right_schema_for_dedup)
1374 {
1375 result = remove_duplicate_columns_for_natural_join(
1376 result,
1377 left_schema,
1378 right_schema,
1379 join_type,
1380 )?;
1381 }
1382 } else if let Some(using_cols) = using_columns {
1383 if let (Some(ref left_schema), Some(ref right_schema)) =
1384 (&left_schema_for_dedup, &right_schema_for_dedup)
1385 {
1386 // For RIGHT/FULL OUTER JOIN, coalesce USING columns before hiding duplicates
1387 if matches!(
1388 join_type,
1389 vibesql_ast::JoinType::RightOuter | vibesql_ast::JoinType::FullOuter
1390 ) {
1391 coalesce_using_columns_for_outer_join(
1392 &mut result,
1393 left_schema,
1394 right_schema,
1395 using_cols,
1396 );
1397 }
1398 result = remove_duplicate_columns_for_using_join(
1399 result,
1400 left_schema,
1401 right_schema,
1402 using_cols,
1403 join_type,
1404 )?;
1405 }
1406 }
1407
1408 Ok(result)
1409}
1410
1411/// Coalesce USING column values for RIGHT/FULL OUTER JOIN
1412///
1413/// For RIGHT JOIN and FULL JOIN with USING clause, when a left row is NULL (unmatched),
1414/// the USING column value should come from the right side, not the left.
1415///
1416/// SQL standard semantics: USING clause columns use COALESCE(left.col, right.col)
1417/// - INNER JOIN: values are equal, doesn't matter
1418/// - LEFT OUTER JOIN: unmatched rows have right=NULL, so left value is used (no change needed)
1419/// - RIGHT OUTER JOIN: unmatched rows have left=NULL, so right value should be used
1420/// - FULL OUTER JOIN: COALESCE(left, right) is used for both unmatched cases
1421///
1422/// This function updates left column values to COALESCE(left, right) for USING columns only.
1423fn coalesce_using_columns_for_outer_join(
1424 result: &mut FromResult,
1425 left_schema: &CombinedSchema,
1426 right_schema: &CombinedSchema,
1427 using_cols: &[String],
1428) {
1429 use std::collections::{HashMap, HashSet};
1430
1431 // Create a set of USING column names (lowercase for case-insensitive comparison)
1432 let using_cols_lower: HashSet<String> = using_cols.iter().map(|c| c.to_lowercase()).collect();
1433
1434 // Build a map: lowercase column name -> list of left column indices
1435 // Only include columns that are in the USING list
1436 let mut left_column_map: HashMap<String, Vec<usize>> = HashMap::new();
1437 for (table_start_idx, table_schema) in left_schema.table_schemas.values() {
1438 for (col_idx, col) in table_schema.columns.iter().enumerate() {
1439 let lowercase = col.name.to_lowercase();
1440 if using_cols_lower.contains(&lowercase) {
1441 left_column_map.entry(lowercase).or_default().push(table_start_idx + col_idx);
1442 }
1443 }
1444 }
1445
1446 // Build pairs of (left_idx, right_idx) for USING columns
1447 let left_col_count = left_schema.total_columns;
1448 let mut coalesce_pairs: Vec<(usize, usize)> = Vec::new();
1449
1450 for (table_start_idx, table_schema) in right_schema.table_schemas.values() {
1451 for (col_idx, col) in table_schema.columns.iter().enumerate() {
1452 let lowercase = col.name.to_lowercase();
1453 if let Some(left_indices) = left_column_map.get(&lowercase) {
1454 let right_idx = left_col_count + table_start_idx + col_idx;
1455 // For each left column with this name, create a coalesce pair
1456 for &left_idx in left_indices {
1457 coalesce_pairs.push((left_idx, right_idx));
1458 }
1459 }
1460 }
1461 }
1462
1463 // Apply COALESCE to each row: if left value is NULL, use right value
1464 if !coalesce_pairs.is_empty() {
1465 let rows = result.rows_mut();
1466 for row in rows {
1467 for &(left_idx, right_idx) in &coalesce_pairs {
1468 if row.values[left_idx] == vibesql_types::SqlValue::Null {
1469 row.values[left_idx] = row.values[right_idx].clone();
1470 }
1471 }
1472 }
1473 }
1474}
1475
1476/// Mark duplicate columns as hidden for NATURAL JOIN
1477///
1478/// NATURAL JOIN should only include common columns once (from the left side) in `SELECT *`.
1479/// However, qualified wildcards like `SELECT t1.*` should still return all columns from t1.
1480///
1481/// This function marks duplicate columns from the right side as hidden in the schema,
1482/// rather than removing them. This allows:
1483/// - `SELECT *` to correctly deduplicate columns (skips hidden columns)
1484/// - `SELECT t1.*` to return all columns from t1 (includes hidden columns)
1485///
1486/// Issue #4466: table.* should return all columns in NATURAL JOIN context
1487fn remove_duplicate_columns_for_natural_join(
1488 mut result: FromResult,
1489 left_schema: &CombinedSchema,
1490 right_schema: &CombinedSchema,
1491 join_type: &vibesql_ast::JoinType,
1492) -> Result<FromResult, ExecutorError> {
1493 use std::collections::HashMap;
1494
1495 // For RIGHT/FULL OUTER JOINs, we need to hide left-side columns and add coalesce pairs
1496 // For other join types, we hide right-side columns
1497 let is_right_or_full =
1498 matches!(join_type, vibesql_ast::JoinType::RightOuter | vibesql_ast::JoinType::FullOuter);
1499
1500 // Find common column names (case-insensitive)
1501 // Use table_start_idx to compute correct absolute positions
1502 // (HashMap iteration order is non-deterministic, so we can't use a sequential counter)
1503 let mut left_column_map: HashMap<String, Vec<(String, String, usize)>> = HashMap::new(); // lowercase -> [(table, actual_name, idx)]
1504 for (table_name, (table_start_idx, table_schema)) in &left_schema.table_schemas {
1505 for (col_idx, col) in table_schema.columns.iter().enumerate() {
1506 let lowercase = col.name.to_lowercase();
1507 left_column_map.entry(lowercase).or_default().push((
1508 table_name.to_string(),
1509 col.name.clone(),
1510 table_start_idx + col_idx,
1511 ));
1512 }
1513 }
1514
1515 // Identify which columns from the right side are duplicates
1516 // Use table_start_idx from right_schema to compute correct absolute positions
1517 let left_col_count = left_schema.total_columns;
1518
1519 if is_right_or_full {
1520 // For RIGHT/FULL OUTER JOINs: hide left-side columns and add coalesce pairs
1521 // This ensures SELECT * shows the right-side value (which is non-NULL for unmatched rows)
1522 // while qualified references like t5.id still return the actual NULL value
1523
1524 // Build a set of columns that are replacement targets from the left schema
1525 // (i.e., columns that other columns point to for their replacement value)
1526 let existing_replacement_targets: std::collections::HashSet<usize> =
1527 left_schema.column_replacement_map.values().copied().collect();
1528
1529 for (table_start_idx, table_schema) in right_schema.table_schemas.values() {
1530 for (col_idx, col) in table_schema.columns.iter().enumerate() {
1531 let lowercase = col.name.to_lowercase();
1532 if let Some(left_entries) = left_column_map.get(&lowercase) {
1533 let right_idx = left_col_count + table_start_idx + col_idx;
1534
1535 // Handle chained NATURAL JOINs: update existing replacements that point
1536 // to columns being hidden in this join. For example:
1537 // t5 NATURAL RIGHT JOIN t4 NATURAL RIGHT JOIN t6
1538 // After first join: {0 -> 2}
1539 // After second join: 2 is being hidden, so update {0 -> 4}
1540 for (_, _, left_idx) in left_entries {
1541 // If this column is a replacement target from a previous join,
1542 // we need to update all replacements that point to it
1543 if existing_replacement_targets.contains(left_idx) {
1544 // Find and update all replacements pointing to this column
1545 for (source, target) in left_schema.column_replacement_map.iter() {
1546 if *target == *left_idx {
1547 // Update the existing replacement to point to the new right column
1548 result.schema.add_column_replacement(*source, right_idx);
1549 }
1550 }
1551 } else {
1552 // Normal case: add replacement for this column
1553 result.schema.add_column_replacement(*left_idx, right_idx);
1554 }
1555 }
1556
1557 // Hide all left columns that are common (replacement targets get hidden too)
1558 for (_, _, left_idx) in left_entries {
1559 result.schema.hide_column(*left_idx);
1560 }
1561
1562 // Add coalesce pair for COALESCE(left, right) semantics on unqualified references
1563 // Use the first left column entry for the coalesce pair
1564 // Issue #4906: For nested parenthesized JOINs, the right_schema may already have
1565 // a coalesce chain for this column. We need to extend the chain with ALL indices
1566 // from the right side, not just the current right column.
1567 if let Some((_, actual_name, left_idx)) = left_entries.first() {
1568 // Check if right_schema already has a coalesce chain for this column
1569 if let Some(right_coalesce_indices) =
1570 right_schema.using_coalesce_indices.get(&lowercase)
1571 {
1572 // Add left_idx first
1573 result.schema.add_using_coalesce_pair(
1574 actual_name,
1575 *left_idx,
1576 *left_idx,
1577 );
1578 // Then add all indices from the right side's chain
1579 for &existing_idx in right_coalesce_indices {
1580 let adjusted_idx = left_col_count + existing_idx;
1581 result.schema.add_using_coalesce_pair(
1582 actual_name,
1583 *left_idx,
1584 adjusted_idx,
1585 );
1586 }
1587 } else {
1588 // No existing chain, just add the single pair
1589 result.schema.add_using_coalesce_pair(
1590 actual_name,
1591 *left_idx,
1592 right_idx,
1593 );
1594 }
1595 }
1596
1597 // Mark as joined column for ambiguity resolution
1598 result.schema.add_joined_column(&col.name);
1599
1600 // Also hide the right column since it will be output via replacement
1601 result.schema.hide_column(right_idx);
1602 }
1603 }
1604 }
1605 } else {
1606 // For INNER/LEFT/CROSS JOINs: hide right-side columns (original behavior)
1607 for (table_start_idx, table_schema) in right_schema.table_schemas.values() {
1608 for (col_idx, col) in table_schema.columns.iter().enumerate() {
1609 let lowercase = col.name.to_lowercase();
1610 if left_column_map.contains_key(&lowercase) {
1611 // This is a common column, mark it as hidden for SELECT * expansion
1612 // Position in result = left_col_count + position_in_right_schema
1613 let hidden_idx = left_col_count + table_start_idx + col_idx;
1614 result.schema.hide_column(hidden_idx);
1615
1616 // Also mark this column as a "joined column" so it won't be
1617 // considered ambiguous when referenced without table qualification (issue #4517)
1618 result.schema.add_joined_column(&col.name);
1619 }
1620 }
1621 }
1622 }
1623
1624 Ok(result)
1625}
1626
1627/// Mark USING columns as hidden for USING clause JOIN
1628///
1629/// USING clause should only include the specified columns once (from the left side) in `SELECT *`.
1630/// However, qualified wildcards like `SELECT t1.*` should still return all columns from t1.
1631///
1632/// This function marks USING columns from the right side as hidden in the schema,
1633/// rather than removing them. This allows:
1634/// - `SELECT *` to correctly deduplicate columns (skips hidden columns)
1635/// - `SELECT t1.*` to return all columns from t1 (includes hidden columns)
1636///
1637/// Issue #4466: table.* should return all columns in NATURAL JOIN context
1638fn remove_duplicate_columns_for_using_join(
1639 mut result: FromResult,
1640 left_schema: &CombinedSchema,
1641 right_schema: &CombinedSchema,
1642 using_cols: &[String],
1643 join_type: &vibesql_ast::JoinType,
1644) -> Result<FromResult, ExecutorError> {
1645 use std::collections::HashSet;
1646
1647 // Create a set of USING column names (lowercase for case-insensitive comparison)
1648 let using_cols_lower: HashSet<String> = using_cols.iter().map(|c| c.to_lowercase()).collect();
1649
1650 // Mark all USING columns as "joined columns" so they won't be
1651 // considered ambiguous when referenced without table qualification (issue #4517)
1652 for col in using_cols {
1653 result.schema.add_joined_column(col);
1654 }
1655
1656 // Count columns in left schema
1657 let left_col_count = left_schema.total_columns;
1658
1659 // For RIGHT OUTER and FULL OUTER joins, we need COALESCE semantics:
1660 // The USING column value should be COALESCE(left.col, right.col)
1661 // - RIGHT OUTER: left can be NULL for unmatched rows from right
1662 // - FULL OUTER: either side can be NULL for unmatched rows
1663 // Issue #4783: USING column semantics differ from SQLite in OUTER JOINs
1664 let _needs_coalesce =
1665 matches!(join_type, vibesql_ast::JoinType::RightOuter | vibesql_ast::JoinType::FullOuter);
1666
1667 // Build a map of column name -> leftmost left column index
1668 // This is the index that unqualified references will resolve to
1669 //
1670 // Issue #4786: We ALWAYS need to build this map, not just for FULL/RIGHT joins.
1671 // When a LEFT/INNER join has USING on a right side with nested USING joins,
1672 // we need to add the left column to the coalesce chain so that the inner
1673 // join's visible column becomes a non-first position and gets properly
1674 // filtered by is_using_coalesce_right_side() in projection.
1675 let mut leftmost_left_indices: std::collections::HashMap<String, usize> =
1676 std::collections::HashMap::new();
1677 for (table_start_idx, table_schema) in left_schema.table_schemas.values() {
1678 for (col_idx, col) in table_schema.columns.iter().enumerate() {
1679 let lowercase = col.name.to_lowercase();
1680 if using_cols_lower.contains(&lowercase) {
1681 let absolute_idx = table_start_idx + col_idx;
1682 leftmost_left_indices
1683 .entry(lowercase)
1684 .and_modify(|e| {
1685 if absolute_idx < *e {
1686 *e = absolute_idx
1687 }
1688 })
1689 .or_insert(absolute_idx);
1690 }
1691 }
1692 }
1693
1694 // Identify which columns from the right side are USING columns to hide
1695 // Use table_start_idx from right_schema to compute correct absolute positions
1696 for (table_start_idx, table_schema) in right_schema.table_schemas.values() {
1697 for (col_idx, col) in table_schema.columns.iter().enumerate() {
1698 let lowercase = col.name.to_lowercase();
1699 if using_cols_lower.contains(&lowercase) {
1700 // This is a USING column, mark it as hidden for SELECT * expansion
1701 // Position in result = left_col_count + position_in_right_schema
1702 let right_idx = left_col_count + table_start_idx + col_idx;
1703 result.schema.hide_column(right_idx);
1704
1705 // Issue #4786: ALWAYS register the coalesce pair in the schema, not just
1706 // for FULL/RIGHT joins. This ensures that when a nested USING join's
1707 // visible column is hidden by an outer LEFT/INNER USING join, the
1708 // is_using_coalesce_right_side() check in projection will correctly
1709 // filter it out (because it's no longer first in the chain).
1710 //
1711 // For LEFT/INNER joins, the COALESCE semantics won't be applied in
1712 // output (the left column value is used directly), but the chain
1713 // structure is needed for correct column filtering.
1714 if let Some(&left_idx) = leftmost_left_indices.get(&lowercase) {
1715 result.schema.add_using_coalesce_pair(&col.name, left_idx, right_idx);
1716 }
1717 }
1718 }
1719 }
1720
1721 Ok(result)
1722}