1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
//! Public API for join order optimization
use super::{config::ParallelSearchConfig, context::JoinOrderContext, reorder::JoinOrderAnalyzer};
use crate::optimizer::aggregate_analysis::AggregateAnalysis;
/// Performs join order optimization via exhaustive search
pub struct JoinOrderSearch {
pub(super) context: JoinOrderContext,
}
impl JoinOrderSearch {
/// Create a new join order search from an analyzer with real table statistics
pub fn from_analyzer(
analyzer: &JoinOrderAnalyzer,
database: &vibesql_storage::Database,
) -> Self {
Self::from_analyzer_with_predicates(
analyzer,
database,
&std::collections::HashMap::new(),
&std::collections::HashMap::new(),
)
}
/// Create a new join order search with WHERE clause selectivity applied
///
/// This version accounts for table-local predicates when estimating cardinalities,
/// which helps choose better join orders for queries like TPC-H Q3 where filter
/// predicates significantly reduce table sizes before joining.
///
/// # Parameters
/// - `alias_to_table`: Maps table aliases (e.g., "n1", "n2") to actual table names (e.g.,
/// "nation"). This is critical for queries with self-joins (like TPC-H Q7 with two nation
/// aliases) to correctly look up table cardinalities and statistics.
pub fn from_analyzer_with_predicates(
analyzer: &JoinOrderAnalyzer,
database: &vibesql_storage::Database,
table_local_predicates: &std::collections::HashMap<String, Vec<vibesql_ast::Expression>>,
alias_to_table: &std::collections::HashMap<String, String>,
) -> Self {
let edges = analyzer.edges().to_vec();
let edge_selectivities =
JoinOrderContext::compute_edge_selectivities(&edges, database, alias_to_table);
let num_tables = analyzer.tables().len();
// Extract base cardinalities (before filters) for cascading filter tracking
let table_base_cardinalities =
JoinOrderContext::extract_base_cardinalities(analyzer, database, alias_to_table);
let context = JoinOrderContext {
all_tables: analyzer.tables().clone(),
edges,
table_cardinalities: JoinOrderContext::extract_cardinalities_with_selectivity(
analyzer,
database,
table_local_predicates,
alias_to_table,
),
table_base_cardinalities,
edge_selectivities,
config: ParallelSearchConfig::with_table_count(num_tables),
aggregate_analysis: None,
};
Self { context }
}
/// Create a new join order search with aggregate-aware optimization
///
/// This version accepts aggregate analysis results and can adjust join order
/// decisions based on GROUP BY/HAVING clauses. When HAVING filters are selective,
/// the optimizer may prefer different join orders that enable early aggregation.
///
/// # Parameters
/// - `alias_to_table`: Maps table aliases to actual table names for database lookups.
pub fn from_analyzer_with_aggregates(
analyzer: &JoinOrderAnalyzer,
database: &vibesql_storage::Database,
table_local_predicates: &std::collections::HashMap<String, Vec<vibesql_ast::Expression>>,
alias_to_table: &std::collections::HashMap<String, String>,
aggregate_analysis: AggregateAnalysis,
) -> Self {
let edges = analyzer.edges().to_vec();
let edge_selectivities =
JoinOrderContext::compute_edge_selectivities(&edges, database, alias_to_table);
let num_tables = analyzer.tables().len();
// Extract base cardinalities (before filters) for cascading filter tracking
let table_base_cardinalities =
JoinOrderContext::extract_base_cardinalities(analyzer, database, alias_to_table);
let context = JoinOrderContext {
all_tables: analyzer.tables().clone(),
edges,
table_cardinalities: JoinOrderContext::extract_cardinalities_with_selectivity(
analyzer,
database,
table_local_predicates,
alias_to_table,
),
table_base_cardinalities,
edge_selectivities,
config: ParallelSearchConfig::with_table_count(num_tables),
aggregate_analysis: Some(aggregate_analysis),
};
Self { context }
}
/// Find optimal join order by exploring search space
///
/// Returns list of table names in the order they should be joined.
///
/// For small queries (≤3 tables), uses sequential DFS since the search space
/// is trivial (at most 6 orderings) and parallel overhead isn't worth it.
///
/// When time-bounded search is enabled (default), uses parallel BFS for
/// multi-table queries (4+) with a configurable time budget. This allows
/// optimization of large queries (9+ tables) while preventing excessive search time.
///
/// When time-bounded search is disabled, uses legacy behavior: parallel BFS for
/// 3-6 table queries with highly connected join graphs, DFS for others.
pub fn find_optimal_order(&self) -> Vec<String> {
if self.context.all_tables.is_empty() {
return Vec::new();
}
// For small queries (≤3 tables), use sequential DFS
// The search space is trivial (at most 3! = 6 orderings) and
// rayon thread pool overhead can cause delays under contention
if self.context.all_tables.len() <= 3 {
return self.context.find_optimal_order_dfs();
}
// Use time-bounded BFS for larger multi-table queries when enabled
if self.context.config.use_time_budget {
// Time-bounded BFS handles all query sizes with time budget protection
self.context.find_optimal_order_parallel()
} else {
// Legacy behavior: table-count based decision
if self.should_use_parallel_search() {
self.context.find_optimal_order_parallel()
} else {
self.context.find_optimal_order_dfs()
}
}
}
/// Determine whether to use parallel BFS or sequential DFS
pub(super) fn should_use_parallel_search(&self) -> bool {
// Don't parallelize if disabled
if !self.context.config.enabled {
return false;
}
let num_tables = self.context.all_tables.len();
// Don't parallelize small queries (< 3 tables)
if num_tables < 3 {
return false;
}
// Don't parallelize beyond depth limit (memory constraints)
if num_tables > self.context.config.max_depth {
return false;
}
// Parallel BFS beneficial for highly connected graphs
// Calculate edge density: edges per table
let edge_density = self.context.edges.len() as f64 / num_tables as f64;
// High edge density suggests complex join graph → parallel beneficial
// Threshold of 1.5 means we need at least 1-2 edges per table
edge_density >= 1.5
}
}