第六章-扫描路径

一句话概括本章详细介绍了PostgreSQL查询优化器中扫描路径的生成机制包括代价模型、路径结构、以及顺序扫描/索引扫描/位图扫描三种核心扫描方式的实现原理。一、代价Cost体系1.1 代价基准单位PostgreSQL采用相对代价模型不追求绝对真实的代价只要路径间可比较即可。基准类型默认值GUC参数说明顺序IO1.0seq_page_cost顺序读写一个页面随机IO4.0random_page_cost随机读写机械硬盘寻道预读CPU元组0.01cpu_tuple_cost处理一条元组CPU索引元组0.005cpu_index_tuple_cost处理一条索引元组CPU表达式0.0025cpu_operator_cost表达式求值并行元组传输0.1parallel_tuple_costWorker→Gather传递元组并行初始化1000.0parallel_setup_costIPC初始化代价缓存大小524288页effective_cache_size估计缓存中的页面数关键点顺序IO vs 随机IO 差距4倍源于机械硬盘寻道时间和磁盘预读机制支持表空间级别自定义代价CREATE TABLESPACE ... WITH (SEQ_PAGE_COST2, RANDOM_PAGE_COST3)SSD场景下4倍差距可能不再适用需根据硬件调整1.2 启动代价 vs 整体代价Total Cost Startup Cost Run CostStartup Cost从执行到返回第一条元组的代价Total Cost语句执行的全部代价为什么区分→ LIMIT子句场景无LIMITSeqScanSort总代价869 IndexScan总代价7373 → 选SeqScan有LIMIT 1IndexScan启动代价0.29远低于SeqScanSort的230 → 选IndexScan带LIMIT时查询优化器采用TOP-K堆排序降低排序启动代价1.3 表达式代价计算通过cost_qual_eval/cost_qual_eval_node递归计算核心结构typedefstructQualCost{Cost startup;// 启动代价部分Cost per_tuple;// 应用到元组上的代价}QualCost;表达式类型计算方式FuncExpr/OpExpr/DistinctExpr/NullIfExprper_tuple procost × cpu_operator_costScalarArrayOpExprper_tuple procost × cpu_operator_cost × sizeof(ARRAY) × 0.5RowCompareExpr按元素个数累加SubPlanstartup subplan-startup_cost; per_tuple subplan-per_call_costCurrentOfExprstartup disable_cost强制选择TID扫描二、路径Path结构2.1 Path结构体基类typedefstructPath{NodeTag type;NodeTag pathtype;// 路径类型 T_IndexPath / T_NestPath 等RelOptInfo*parent;// 服务于哪个RelOptInfoPathTarget*pathtarget;// 投影信息ParamPathInfo*param_info;// 参数化信息bool parallel_aware;// 是否真正应用了并行bool parallel_safe;// 路径是否并行安全intparallel_workers;// 并行度doublerows;// 中间结果估计行数Cost startup_cost;// 启动代价Cost total_cost;// 整体代价List*pathkeys;// 排序键NULL表示无序}Path;2.2 并行参数parallel_workers实际并行度通过compute_parallel_worker计算并行度参考值 min(heap_pages, index_pages) 的 log₃受max_parallel_workers_per_gather限制参数说明min_parallel_table_scan_size启用并行表扫描的最小页面数min_parallel_index_scan_size启用并行索引扫描的最小页面数max_parallel_workers_per_gather每个Gather下的最大并行度parallel_aware vs parallel_safeparallel_safe路径能否并行执行受子路径和RelOptInfo影响parallel_aware路径是否真正被分配了并行Worker2.3 参数化路径问题A JOIN B ON A.a B.b中NestLoop时A表取出一条元组后需要扫描整个B表。解决方案将A.a B.b转换为B.b {Param of A.a}利用B.b上的索引。外表获取一条元组 → 提取参数 → 用参数扫描内表索引关键结构typedefstructNestLoopParam{NodeTag type;intparamno;// PARAM_EXEC参数编号Var*paramval;// 外表的Var}NestLoopParam;限制只有Nestloop Join支持参数传递外表驱动内表HashJoin/MergeJoin不具备驱动关系不支持示例SELECT*FROMTEST_A,TEST_BWHERETEST_A.aTEST_B.aANDTEST_A.a9000;-- 执行计划NestLoop SeqScan(A) IndexScan(B, a test_a.a)2.4 PathKey排序键作用避免重复排序支持排序复用。PlannerInfo-query_pathkeysNon-SPJ→SPJ的期望顺序自上而下Path-pathkeys当前路径的输出顺序自下而上typedefstructPathKey{NodeTag type;EquivalenceClass*pk_eclass;// 等价类Oid pk_opfamily;// 操作符族intpk_strategy;// 升序/降序bool pk_nulls_first;// NULL值优先级}PathKey;关键优化B树索引天然有序 → IndexScan可省ORDER BYMergeJoin需要两端排序 → 利用已有PathKey可省排序等价类中成员等价ORDER BY A.a等价于ORDER BY B.a当A.a B.a三、make_one_rel函数3.1 路径生成两阶段make_one_rel ├── set_base_rel_pathlists() -- 生成扫描路径本章重点 └── make_rel_from_joinlist() -- 生成连接路径3.2 普通表扫描路径入口set_plain_rel_pathlist(rel)├──create_seqscan_path()--顺序扫描 ├──create_plain_partial_paths()--并行顺序扫描 ├──create_index_paths()--索引扫描 └──create_tidscan_paths()--TID扫描四、顺序扫描SeqScan4.1 原理全表扫描算法复杂度 O(N)直接使用Path结构体无需单独结构体适用场景选择率高、表较小、无合适索引4.2 代价计算disk_run_cost seq_page_cost × 页面数 cpu_run_cost (cpu_tuple_cost 表达式代价) × 元组数 total_cost startup_cost cpu_run_cost disk_run_cost并行优化CPU代价分摊cpu_run_cost / parallel_divisorparallel_divisor 1.0 - (0.3 × parallel_workers)Worker越多促进越小4.3 参数化顺序扫描仅当Lateral变量出现在投影中时才生成如SELECT*FROMTEST_ALEFTJOINLATERAL(SELECTa,TEST_A.aFROMTEST_B)bbONTRUE;五、索引扫描IndexScan5.1 索引类型索引类型说明B-tree默认支持等值/范围/排序Hash仅等值O(1)复杂度GiST几何/全文搜索GIN倒排索引SP-GiST空间分区BRIN块范围索引5.2 索引扫描路径类型(1) 普通索引扫描Index ScanSELECT*FROMTEST_AWHEREa9000;-- Index Scan using test_a_abc_idx on test_a两步B树查找索引项 → 随机读堆表获取元组随机IO代价高random_page_cost4(2) 快速索引扫描Index Only ScanSELECTa,b,cFROMTEST_AWHEREa9000;-- Index Only Scan using test_a_abc_idx on test_a投影列是索引列子集时可用省去堆表访问直接从索引取值(3) 位图索引扫描Bitmap Index ScanSELECTa,b,cFROMTEST_AWHEREa9000;-- Bitmap Heap Scan → Bitmap Index Scan先扫描索引生成位图记录堆表元组地址位图排序后顺序读堆表 → 随机读转顺序读适用场景选择率中等5.3 索引键匹配约束条件三类匹配baserestrictinfo→ 普通索引扫描joininfo→ 参数化路径等价类隐含约束 → 参数化路径支持的表达式表达式匹配方式OpExprindexkey op const / const op indexkeyBooleanTest直接匹配/NOT递归/BooleanTest参数RowCompareExpr仅B树只匹配第一个操作数ScalarArrayOpExpr仅indexkey op const仅ANYNullTest需索引支持amsearchnulls特殊处理LIKE abc→ 提取a abc约束a ANY(ARRAY[1,2,3])→ 支持a ALL(ARRAY[1,2,3])→ 不支持5.4 索引代价计算索引自身代价btcostestimateindexBoundQuals 第一个非等值约束之前的所有约束 numIndexTuples 基于indexBoundQuals选择率估算 indexTotalCost IO代价 CPU代价IO代价模型基于Mackert-Lohman模型有效缓存页面数 b (effective_cache_size / total_pages) × T索引相关系数单键索引统计信息中的相关系数 ρ多键索引第一键相关系数 × 0.75堆表扫描代价cost_indexio_cost max_IO_cost ρ² × (min_IO_cost - max_IO_cost)max_IO_cost完全不相关ρ0全随机读min_IO_cost完全正相关ρ1顺序读5.5 索引PathKey记录条件需同时满足非位图扫描路径无ScalarArrayOpExpr或在第一键索引操作符族保证有序sortopfamily ! NULL有序性质有用有MergeJoin或ORDER BY期望六、位图扫描Bitmap Scan6.1 核心思想将索引扫描的随机堆表读取转换为顺序堆表读取。6.2 路径结构BitmapHeapPath顶层 ├── BitmapAndPathAND操作 │ ├── IndexPath叶子 │ └── IndexPath叶子 └── BitmapOrPathOR操作 ├── IndexPath叶子 └── BitmapOrPath嵌套结构体typedefstructBitmapHeapPath{Path path;Path*bitmapqual;// IndexPath / BitmapAndPath / BitmapOrPath}BitmapHeapPath;typedefstructBitmapAndPath{Path path;List*bitmapquals;// IndexPaths和BitmapOrPathsSelectivity bitmapselectivity;}BitmapAndPath;typedefstructBitmapOrPath{Path path;List*bitmapquals;// IndexPaths和BitmapAndPathsSelectivity bitmapselectivity;}BitmapOrPath;6.3 BitmapOrPath生成支持OR类型约束条件SELECT*FROMTEST_AWHEREA1ORA2;-- BitmapOr → Bitmap Index Scan(A1) Bitmap Index Scan(A2)6.4 BitmapAndPath生成三阶段组合算法筛选相同约束条件集合的路径保留代价低的排序按代价升序代价相同则选择率低优先组合O(N²)组合组合后代价升高则淘汰6.5 位图扫描代价路径类型代价计算IndexPath叶子仅索引自身代价indextotalcostBitmapOrPath子节点代价和 100×cpu_operator_cost并集操作BitmapAndPath子节点代价和BitmapHeapPath启动代价子节点总代价IO代价使用插值公式BitmapHeap IO代价公式io_cost random_page_cost - (random_page_cost - seq_page_cost) × √(pages_fetched / T)有序但非连续 → 不完全等于seq_page_cost选择率低时跳过预读范围 → 接近random_page_cost七、核心要点总结7.1 扫描路径选择决策树选择率高 → SeqScan 选择率低 → IndexScanB树等值/范围 选择率中等 → BitmapScan 有索引且投影列在索引中 → IndexOnlyScan 有多个索引条件组合 → BitmapAnd/BitmapOr7.2 关键优化手段参数化路径NestLoop中利用外表值驱动内表索引PathKey复用避免重复排序支持MergeJoin优化位图扫描随机读转顺序读支持多索引组合并行扫描分摊CPU代价受限于GUC参数启动代价区分支持LIMIT场景的路径选择7.3 常见GUC参数速查-- 代价调整SETseq_page_cost1.0;SETrandom_page_cost4.0;SETcpu_tuple_cost0.01;SETcpu_operator_cost0.0025;-- 并行控制SETmin_parallel_table_scan_size8MB;SETmin_parallel_index_scan_size512kB;SETmax_parallel_workers_per_gather2;-- 缓存估计SETeffective_cache_size4GB;