分布式数据库的查询优化器设计基于代价模型的 Join 顺序选择与统计信息维护一、多表 Join 时执行计划的剧烈抖动在分布式 OLAP 场景中相同 SQL 在不同时段的执行时间差异可达 10 倍以上。排查发现根因并非数据分布变化而是优化器在选择 Join 顺序时一旦跨越了代价的临界点表大小变化 20%执行计划就会发生根本性变更——从高效的 Hash Join 变为低效的 Nested Loop Join。查询优化器的核心任务是在指数级增长的 Join 顺序空间中基于代价模型选出执行成本最低的计划。分布式环境引入了额外的维度节点间数据传输成本、数据局部性Co-location收益、以及统计信息的时效性滞后。这三重因素叠加使得优化器的设计远比单机数据库复杂。二、分布式代价模型的核心构成flowchart TB A[SQL 解析 绑定] -- B[逻辑计划生成] B -- C{Join 顺序枚举} C -- D[动态规划枚举] C -- E[遗传算法枚举] D -- F[代价估算] E -- F F -- G[CPU 成本] F -- H[I/O 成本] F -- I[网络传输成本] G -- J[总代价 G*α H*β I*γ] H -- J I -- J J -- K[选择最低代价计划] K -- L[分布式物理计划] subgraph 统计信息 M[表行数估计] N[列基数 (NDV)] O[数据分布直方图] end M -- F N -- F O -- F分布式代价模型与传统单机模型的最大差异在于网络传输成本I 因子。在分布式 Join 中两张表可能分布在不同节点上需要在 Join 前进行数据重分布Shuffle。Shuffle 的数据量取决于 Join Key 的基数估计和分布均匀性——而这又依赖于统计信息的准确性。代价公式中的权重系数 α、β、γ 需要通过硬件基准测试Calibration进行标定而非使用固定的经验值。不同硬件配置下NVMe vs SATA SSD100Gbps vs 10Gbps 网络权重差异显著。三、基于直方图的代价估算实现use std::collections::BTreeMap; /// 等深直方图将列值按频次均匀分桶 /// 设计原因等深直方图对数据倾斜Skew的捕捉能力优于等宽直方图 /// 在分布极不均匀的列上如用户ID的幂律分布等深直方图能更准确地 /// 估计过滤条件的选择率 #[derive(Clone)] pub struct EquiDepthHistogram { buckets: VecBucket, total_rows: u64, } #[derive(Clone)] struct Bucket { lower_bound: i64, // 桶下界包含 upper_bound: i64, // 桶上界包含 distinct_count: u64, // 桶内不同值的数量 row_count: u64, // 桶内行数 } impl EquiDepthHistogram { /// 从排序后的样本数据构建等深直方图 /// sample: 已排序的列值样本通常为表数据的 1%-5% /// num_buckets: 桶数量建议 100-256 /// /// 设计原因桶数量影响估计精度和存储开销 /// 过多→统计信息占用内存大更新代价高 /// 过少→无法捕捉数据分布细节 /// 256 是 PostgreSQL 的默认值经过大量实践验证 pub fn build(sorted_sample: [i64], num_buckets: usize) - Self { let total_rows sorted_sample.len() as u64; // 计算每桶行数向上取整保证所有数据都被覆盖 let rows_per_bucket (total_rows num_buckets as u64 - 1) / num_buckets as u64; let mut buckets Vec::with_capacity(num_buckets); let mut chunk_start 0; while chunk_start sorted_sample.len() { let chunk_end (chunk_start rows_per_bucket as usize) .min(sorted_sample.len()); let chunk sorted_sample[chunk_start..chunk_end]; // 计算桶内不同值数量 // 设计原因使用 iter().dedup() 而非 Hash 集合 // 输入已排序去重只需 O(n) 扫描 let mut distinct 1u64; for i in 1..chunk.len() { if chunk[i] ! chunk[i-1] { distinct 1; } } buckets.push(Bucket { lower_bound: chunk[0], upper_bound: chunk[chunk.len() - 1], distinct_count: distinct, row_count: chunk.len() as u64, }); chunk_start chunk_end; } EquiDepthHistogram { buckets, total_rows } } /// 估算等值过滤的选择率 /// 例如WHERE user_id 42 → 预估返回行数 total_rows * 选择率 /// /// 设计原因等值过滤的选择率 1 / NDV假设均匀分布 /// 但直方图提供了更精确的估计定位值所在桶使用桶内密度 pub fn estimate_eq_selectivity(self, value: i64) - f64 { for bucket in self.buckets { if value bucket.lower_bound value bucket.upper_bound { if bucket.distinct_count 0 { return 0.0; } // 假设桶内均匀分布每个不同值对应的行数 // 桶内总行数 / 桶内不同值数量 let rows_per_value bucket.row_count as f64 / bucket.distinct_count as f64; return rows_per_value / self.total_rows as f64; } } 0.0 // 值不在直方图范围内 } /// 估算范围过滤的选择率 /// 例如WHERE created_at BETWEEN 2024-01-01 AND 2024-06-30 pub fn estimate_range_selectivity( self, lower: i64, upper: i64) - f64 { let mut matched_rows 0u64; for bucket in self.buckets { if bucket.upper_bound lower || bucket.lower_bound upper { continue; // 桶与查询范围无交集 } if bucket.lower_bound lower bucket.upper_bound upper { // 桶完全在查询范围内 matched_rows bucket.row_count; } else { // 桶与查询范围部分重叠线性插值估计 let overlap_lower lower.max(bucket.lower_bound); let overlap_upper upper.min(bucket.upper_bound); let bucket_range (bucket.upper_bound - bucket.lower_bound) .max(1) as f64; let overlap_range (overlap_upper - overlap_lower) as f64; let fraction overlap_range / bucket_range; matched_rows (bucket.row_count as f64 * fraction) as u64; } } matched_rows as f64 / self.total_rows as f64 } } /// Join 顺序的动态规划枚举 /// 设计原因N 表 Join 的可能顺序为 Catalan(N) 种 /// DP 通过子问题最优解构造整体最优解将复杂度从 O(N!) 降至 O(3^N) /// 但在 N12 时需要切换为遗传算法等启发式方法 pub fn dp_join_order( tables: [TableStats], join_edges: [(usize, usize, f64)], // (表A, 表B, Join选择率) ) - JoinPlan { let n tables.len(); // dp[mask] 连接 mask 中所有表的最优计划及代价 let mut dp: BTreeMapu32, (f64, JoinPlan) BTreeMap::new(); // 初始化单表访问 for i in 0..n { let mask 1u32 i; dp.insert(mask, (tables[i].scan_cost(), JoinPlan::Leaf(i))); } // 枚举所有子集组合 for mask in 1u32..(1u32 n) { // 子集枚举技巧遍历 mask 的所有非空真子集 let mut sub (mask - 1) mask; while sub 0 { let other mask ^ sub; if dp.contains_key(sub) dp.contains_key(other) { // 尝试连接 sub 和 other 的结果 // 遍历所有可能的 Join Edge for (a, b, selectivity) in join_edges { let a_in_sub (sub a) 1 1; let b_in_other (other b) 1 1; let reversed (sub b) 1 1 (other a) 1 1; if a_in_sub b_in_other { let cost estimate_join_cost( dp[sub], dp[other], selectivity); let total dp[sub].0 dp[other].0 cost; dp.entry(mask) .and_modify(|e| { if total e.0 { *e (total, JoinPlan::Join( Box::new(dp[sub].1.clone()), Box::new(dp[other].1.clone()), (a, b))); } }) .or_insert((total, JoinPlan::Join( Box::new(dp[sub].1.clone()), Box::new(dp[other].1.clone()), (a, b)))); } // 类似处理 reversed 情况省略 } } sub (sub - 1) mask; } } dp.remove(((1u32 n) - 1)) .map(|(_, plan)| plan) .unwrap_or(JoinPlan::Leaf(0)) } #[derive(Clone)] enum JoinPlan { Leaf(usize), Join(BoxJoinPlan, BoxJoinPlan, (usize, usize)) } struct TableStats { row_count: u64 } impl TableStats { fn scan_cost(self) - f64 { self.row_count as f64 } } fn estimate_join_cost(_l: (f64, JoinPlan), _r: (f64, JoinPlan), _s: f64) - f64 { 0.0 }统计信息的时效性是另一个关键问题。在 OLTP 场景中频繁的 DML 操作会导致统计信息快速过时。PostgreSQL 采用的策略是异步 Auto-Vacuum 触发统计更新代价是优化器可能在短时间内使用过期统计信息。更激进的方案是维护基于 Reservoir Sampling 的在线统计更新但这会显著增加写入路径的 CPU 开销。四、代价模型的适用场景与局限等深直方图在列值分布极度倾斜时如 Zipf 分布桶内部的均匀假设不再成立估计误差可达 10 倍以上。对于此类场景需要升级为最频繁值MCV列表 等深直方图的混合方案——MCV 精确记录 Top-N 值的频率剩余值使用直方图估计。动态规划枚举在表数量超过 12 时会遇到组合爆炸4096 种表组合每种组合又有多种子集划分方式。实际生产中使用遗传算法GEQO进行近似搜索——在 PostgreSQL 中geqo_threshold的默认值是 12。遗传算法的代价是可能错过全局最优解在 15 表 Join 场景下解的代价通常比最优解高出 5%-15%。分布式环境下网络传输成本的估计需要统计信息中额外包含 Join Key 在各节点上的分布情况Data Distribution Statistics。缺失这部分信息时优化器只能假设均匀分布导致 Shuffle 数据量估计偏差 30%-50%。五、总结分布式查询优化器的代价模型需要同时估算 CPU、I/O 和网络传输成本权重系数 α/β/γ 需通过硬件 Calibration 标定。等深直方图对倾斜数据的捕捉能力优于等宽直方图但在极度倾斜的 Zipf 分布下需配合 MCV 列表使用。Join 顺序的动态规划枚举在表数 ≤12 时可行超过阈值需切换为遗传算法等启发式方法。统计信息时效性影响执行计划稳定性异步更新方案在时间窗口内可能使用过期统计信息。分布式环境下的 Join Key 分布统计缺失会导致 Shuffle 数据量估计偏差 30%-50%是优化器误差的主要来源。
分布式数据库的查询优化器设计基于代价模型的 Join 顺序选择与统计信息维护一、多表 Join 时执行计划的剧烈抖动在分布式 OLAP 场景中相同 SQL 在不同时段的执行时间差异可达 10 倍以上。排查发现根因并非数据分布变化而是优化器在选择 Join 顺序时一旦跨越了代价的临界点表大小变化 20%执行计划就会发生根本性变更——从高效的 Hash Join 变为低效的 Nested Loop Join。查询优化器的核心任务是在指数级增长的 Join 顺序空间中基于代价模型选出执行成本最低的计划。分布式环境引入了额外的维度节点间数据传输成本、数据局部性Co-location收益、以及统计信息的时效性滞后。这三重因素叠加使得优化器的设计远比单机数据库复杂。二、分布式代价模型的核心构成flowchart TB A[SQL 解析 绑定] -- B[逻辑计划生成] B -- C{Join 顺序枚举} C -- D[动态规划枚举] C -- E[遗传算法枚举] D -- F[代价估算] E -- F F -- G[CPU 成本] F -- H[I/O 成本] F -- I[网络传输成本] G -- J[总代价 G*α H*β I*γ] H -- J I -- J J -- K[选择最低代价计划] K -- L[分布式物理计划] subgraph 统计信息 M[表行数估计] N[列基数 (NDV)] O[数据分布直方图] end M -- F N -- F O -- F分布式代价模型与传统单机模型的最大差异在于网络传输成本I 因子。在分布式 Join 中两张表可能分布在不同节点上需要在 Join 前进行数据重分布Shuffle。Shuffle 的数据量取决于 Join Key 的基数估计和分布均匀性——而这又依赖于统计信息的准确性。代价公式中的权重系数 α、β、γ 需要通过硬件基准测试Calibration进行标定而非使用固定的经验值。不同硬件配置下NVMe vs SATA SSD100Gbps vs 10Gbps 网络权重差异显著。三、基于直方图的代价估算实现use std::collections::BTreeMap; /// 等深直方图将列值按频次均匀分桶 /// 设计原因等深直方图对数据倾斜Skew的捕捉能力优于等宽直方图 /// 在分布极不均匀的列上如用户ID的幂律分布等深直方图能更准确地 /// 估计过滤条件的选择率 #[derive(Clone)] pub struct EquiDepthHistogram { buckets: VecBucket, total_rows: u64, } #[derive(Clone)] struct Bucket { lower_bound: i64, // 桶下界包含 upper_bound: i64, // 桶上界包含 distinct_count: u64, // 桶内不同值的数量 row_count: u64, // 桶内行数 } impl EquiDepthHistogram { /// 从排序后的样本数据构建等深直方图 /// sample: 已排序的列值样本通常为表数据的 1%-5% /// num_buckets: 桶数量建议 100-256 /// /// 设计原因桶数量影响估计精度和存储开销 /// 过多→统计信息占用内存大更新代价高 /// 过少→无法捕捉数据分布细节 /// 256 是 PostgreSQL 的默认值经过大量实践验证 pub fn build(sorted_sample: [i64], num_buckets: usize) - Self { let total_rows sorted_sample.len() as u64; // 计算每桶行数向上取整保证所有数据都被覆盖 let rows_per_bucket (total_rows num_buckets as u64 - 1) / num_buckets as u64; let mut buckets Vec::with_capacity(num_buckets); let mut chunk_start 0; while chunk_start sorted_sample.len() { let chunk_end (chunk_start rows_per_bucket as usize) .min(sorted_sample.len()); let chunk sorted_sample[chunk_start..chunk_end]; // 计算桶内不同值数量 // 设计原因使用 iter().dedup() 而非 Hash 集合 // 输入已排序去重只需 O(n) 扫描 let mut distinct 1u64; for i in 1..chunk.len() { if chunk[i] ! chunk[i-1] { distinct 1; } } buckets.push(Bucket { lower_bound: chunk[0], upper_bound: chunk[chunk.len() - 1], distinct_count: distinct, row_count: chunk.len() as u64, }); chunk_start chunk_end; } EquiDepthHistogram { buckets, total_rows } } /// 估算等值过滤的选择率 /// 例如WHERE user_id 42 → 预估返回行数 total_rows * 选择率 /// /// 设计原因等值过滤的选择率 1 / NDV假设均匀分布 /// 但直方图提供了更精确的估计定位值所在桶使用桶内密度 pub fn estimate_eq_selectivity(self, value: i64) - f64 { for bucket in self.buckets { if value bucket.lower_bound value bucket.upper_bound { if bucket.distinct_count 0 { return 0.0; } // 假设桶内均匀分布每个不同值对应的行数 // 桶内总行数 / 桶内不同值数量 let rows_per_value bucket.row_count as f64 / bucket.distinct_count as f64; return rows_per_value / self.total_rows as f64; } } 0.0 // 值不在直方图范围内 } /// 估算范围过滤的选择率 /// 例如WHERE created_at BETWEEN 2024-01-01 AND 2024-06-30 pub fn estimate_range_selectivity( self, lower: i64, upper: i64) - f64 { let mut matched_rows 0u64; for bucket in self.buckets { if bucket.upper_bound lower || bucket.lower_bound upper { continue; // 桶与查询范围无交集 } if bucket.lower_bound lower bucket.upper_bound upper { // 桶完全在查询范围内 matched_rows bucket.row_count; } else { // 桶与查询范围部分重叠线性插值估计 let overlap_lower lower.max(bucket.lower_bound); let overlap_upper upper.min(bucket.upper_bound); let bucket_range (bucket.upper_bound - bucket.lower_bound) .max(1) as f64; let overlap_range (overlap_upper - overlap_lower) as f64; let fraction overlap_range / bucket_range; matched_rows (bucket.row_count as f64 * fraction) as u64; } } matched_rows as f64 / self.total_rows as f64 } } /// Join 顺序的动态规划枚举 /// 设计原因N 表 Join 的可能顺序为 Catalan(N) 种 /// DP 通过子问题最优解构造整体最优解将复杂度从 O(N!) 降至 O(3^N) /// 但在 N12 时需要切换为遗传算法等启发式方法 pub fn dp_join_order( tables: [TableStats], join_edges: [(usize, usize, f64)], // (表A, 表B, Join选择率) ) - JoinPlan { let n tables.len(); // dp[mask] 连接 mask 中所有表的最优计划及代价 let mut dp: BTreeMapu32, (f64, JoinPlan) BTreeMap::new(); // 初始化单表访问 for i in 0..n { let mask 1u32 i; dp.insert(mask, (tables[i].scan_cost(), JoinPlan::Leaf(i))); } // 枚举所有子集组合 for mask in 1u32..(1u32 n) { // 子集枚举技巧遍历 mask 的所有非空真子集 let mut sub (mask - 1) mask; while sub 0 { let other mask ^ sub; if dp.contains_key(sub) dp.contains_key(other) { // 尝试连接 sub 和 other 的结果 // 遍历所有可能的 Join Edge for (a, b, selectivity) in join_edges { let a_in_sub (sub a) 1 1; let b_in_other (other b) 1 1; let reversed (sub b) 1 1 (other a) 1 1; if a_in_sub b_in_other { let cost estimate_join_cost( dp[sub], dp[other], selectivity); let total dp[sub].0 dp[other].0 cost; dp.entry(mask) .and_modify(|e| { if total e.0 { *e (total, JoinPlan::Join( Box::new(dp[sub].1.clone()), Box::new(dp[other].1.clone()), (a, b))); } }) .or_insert((total, JoinPlan::Join( Box::new(dp[sub].1.clone()), Box::new(dp[other].1.clone()), (a, b)))); } // 类似处理 reversed 情况省略 } } sub (sub - 1) mask; } } dp.remove(((1u32 n) - 1)) .map(|(_, plan)| plan) .unwrap_or(JoinPlan::Leaf(0)) } #[derive(Clone)] enum JoinPlan { Leaf(usize), Join(BoxJoinPlan, BoxJoinPlan, (usize, usize)) } struct TableStats { row_count: u64 } impl TableStats { fn scan_cost(self) - f64 { self.row_count as f64 } } fn estimate_join_cost(_l: (f64, JoinPlan), _r: (f64, JoinPlan), _s: f64) - f64 { 0.0 }统计信息的时效性是另一个关键问题。在 OLTP 场景中频繁的 DML 操作会导致统计信息快速过时。PostgreSQL 采用的策略是异步 Auto-Vacuum 触发统计更新代价是优化器可能在短时间内使用过期统计信息。更激进的方案是维护基于 Reservoir Sampling 的在线统计更新但这会显著增加写入路径的 CPU 开销。四、代价模型的适用场景与局限等深直方图在列值分布极度倾斜时如 Zipf 分布桶内部的均匀假设不再成立估计误差可达 10 倍以上。对于此类场景需要升级为最频繁值MCV列表 等深直方图的混合方案——MCV 精确记录 Top-N 值的频率剩余值使用直方图估计。动态规划枚举在表数量超过 12 时会遇到组合爆炸4096 种表组合每种组合又有多种子集划分方式。实际生产中使用遗传算法GEQO进行近似搜索——在 PostgreSQL 中geqo_threshold的默认值是 12。遗传算法的代价是可能错过全局最优解在 15 表 Join 场景下解的代价通常比最优解高出 5%-15%。分布式环境下网络传输成本的估计需要统计信息中额外包含 Join Key 在各节点上的分布情况Data Distribution Statistics。缺失这部分信息时优化器只能假设均匀分布导致 Shuffle 数据量估计偏差 30%-50%。五、总结分布式查询优化器的代价模型需要同时估算 CPU、I/O 和网络传输成本权重系数 α/β/γ 需通过硬件 Calibration 标定。等深直方图对倾斜数据的捕捉能力优于等宽直方图但在极度倾斜的 Zipf 分布下需配合 MCV 列表使用。Join 顺序的动态规划枚举在表数 ≤12 时可行超过阈值需切换为遗传算法等启发式方法。统计信息时效性影响执行计划稳定性异步更新方案在时间窗口内可能使用过期统计信息。分布式环境下的 Join Key 分布统计缺失会导致 Shuffle 数据量估计偏差 30%-50%是优化器误差的主要来源。
